Learning to Rank Generation with Pairwise Partial Rewards
Authors: Youngwon Lee
Jinu Lee
seung-won hwang
Venue: EMNLP 2023 Main (2023)
Keywords: Reinforcement learning
learning to rank
reward shaping
conditional text generation

Abstract: This paper studies the use of reinforcement learning for conditional text generation, which overcomes the limitation of the prevalent supervised maximum likelihood estimation approach. However, it still suffers from challenges including the large action space and the delayed reward, as the reward can be computed only after an entire sequence is generated. To address these challenges, we propose a method that provides partial rewards for intermediate actions taken on partial sequences. This enables the model to promptly prioritize actions that lead to the generation of more desirable sequences. Our method's key contribution lies in its focus on distinguishing relatively more desirable actions rather than striving to precisely estimate pointwise values for arbitrary partial sequences. Instead, our model learns to discern the relative desirability between pairs of actions, or rank actions in a pairwise manner, only when necessary and feasible. This is materialized in an efficient way by leveraging the prefix tree constructed from the sampled sequences. Experimental results on paraphrase generation and constrained machine translation tasks showcase the effectiveness of our method.

Learning to Rank Generation with Pairwise Partial Rewards
Youngwon Lee; Jinu Lee; Seung-won Hwang Seoul National University
ywlee@ldi. snu. kr. (aquamrn, seungwonh ac. kr
Abstract
state, action at time step
final outcome
(a) be
?
at home.
75
This paper studies the use of reinforcement learning for conditional text generation, which overcomes the limitation of the prevalent super- vised maximum likelihood estimation approach. However, it still suffers from challenges includ- ing the large action space and the delayed re- ward, as the reward can be computed only af- ter an entire sequence is generated. To address these challenges,
want to
(b) go
?
back home.
(c) return
home.
Pointwise estimate
Figure I: Reinforcement learning boils down to either implicitly or explicitly maintain pointwise estimates of values at each state, corresponding to utility of partially generated sequences.
propose method that pro- vides partial rewards for intermediate actions taken on partial sequences. This enables the model to promptly prioritize actions that lead to the generation of more desirable sequences. Our method's 's key contribution lies in focus on distinguishing relatively more desirable ac- tions rather than striving to precisely estimate pointwise values for arbitrary partial sequences. Instead, our reward shaping method learns to discern the relative desirability between pairs of actions, rank actions in pairwise ner, only when necessary and feasible. This is materialized in an efficient way by leveraging the prefix tree constructed from the sampled sequences. Experimental results on paraphrase generation and constrained machine transla- tion tasks showcase the effectiveness of our method.
Cao and Wan, 2020; Nighojkar and Licato, 2021, inter alia).
Supervised learning, particularly maximum like- lihood estimation (MLE) training, has typically been the standard approach for conditional text generation. In this approach, the model is trained to maximize the likelihood of the reference given the source. During inference, generates output sequences for which assigns high probability.
This approach is known to suffer from two sig- nificant challenges: exposure bias and train-test objective discrepancy (Ranzato et al., 2016). To ad- dress both challenges, reinforcement learning (RL) has gained attention 2016; Kreutzer et al., 2017). RL formulates au- toregressive text generation Markov decision process where state corresponds to a generated prefix under construction, an action represents the selection of the next token, guided by the policy network, which is essentially the language model. The agent's goal is to maximize the reward it re- ceives, which is determined by the utility of the output sequence.
alternative (Shen et al..
1 Introduction
Conditional text generation encompasses various tasks, with the objective of generating sequence y based a given source sequence x, in a way that maximizes the utility u. For example, in para- rumning
phrase generation, which use example, u is high when (I) y matches the mean- ing of the source sequence x, (2) y fluent in terms of language modeling, and (3) it has high lexical dissimilarity from x (Kumar et al., 2020;
However, this utility can be computed only af- the generation is finished. This sparse and delayed reward problem introduces challenges in learning the impact of each action taken by the model, known as the credit assignment problem in RL, as depicted in Figure (Guo et al., 2022: Li
Equal contribution.
Corresponding author.
'Our code is publicly available at: com/
ji mullee-v/Painne wttpee///aaaiisseaaaaaallleeaa
2Or, defined to include the source, (x,y

---

state, action at time step
final outcome
(C)
Ours (C)
(a) be
at home. back home.
75
Performance
(B)
want to
(b) go
Baseline (B)
(c) return
home.
violates resilience
Partial order
(A)
Figure 3: The proposed PPR learns to rank actions, defining partial (rather than total) order over partial sequences. The model receives partial reward, instead of waiting for the delayed reward.
Baseline (A) violates monotonicity
Beam size
Figure 2: (Beam monotonicity and resilience) Baselines fall into either the failure cases: (A) fails to achieve monotonicity while (B) exhibits monotonicity but fails at resilience. Our method (C) achieves both, retaining the performance even with smaller beam sizes.
Figure 2C, by adjusting an overly ambitious re- quirement of full ordering, to partially ordering a subset of possible pairs of partial sequences. Essen- tially, we aim to train the model to choose actions that will lead to better outcomes, aligning with our training objective. This approach also provides the model with partial rewards, offering direct feed- back on individual actions long before the delayed reward becomes available.
et al., 2017). When a pointwise estimation of each partial candidate is unreliable, generation leads to undesirable sequences such as blank or repeated n-grams (Holtzman et al., 2020).
Our method, called PPR (Pairwise Partial Re- ward), implements this idea by utilizing pre- fix tree constructed from the sampled sequences. PPR employs pairwise ranking objective for the branching nodes in the prefix tree. Firstly, we as- sess the desirability of following each branch by considering the Icaf nodes in the corresponding sub- tree and their associated observed utilities. Then, we compare pairs of branches and encourage the model to prefer the branch with a higher expected return, effectively establishing partial order over partially generated sequences. For example, in Figure PPR can encourage the model to prefer action (or the resulting partial sequence) e over a or defining ordering of a + e and + e as shown in the figure.
We hypothesize that such pointwise estimation of state values, or equivalently expecting models to predict total order over all partially generated sequences, is an overly ambitious objective. this sense, while text degeneration is often attributed to the failure of decoding, we show that the policy, the model itself, is more responsible to the failure.
To support our claim that language models in- deed struggle with the pointwise estimation of the final outcome from partially generated sequences, we suggest comparing their performance with beam search using different beam sizes, as illustrated in Figure 2. Beam search can be seen as providing some tolerance for the model's mistakes by hold- ing candidate sequences even when its prefix values are underestimated (Meister et al., 2020). Ideally, if the model's belief about the sequence's utility aligns positively with the actual utility of the fully generated sequence, increasing the beam size should only increase such a tolerance. We refer to this property as beam monotonicity, which is violated in baseline model shown in Figure 2A. Similarly, reducing the beam size should not significantly hurt the performance if the model accurately estimates values of prefixes in earlier stages, as higher-ranked candidates would still sur- vive with smaller beam size. We call this property beam resilience, which is violated in Figure 2B. A reliable policy should satisfy both properties, as shown in Figure 2C.
Importantly, PPR does not require the model to direetly compare its value estimate of with other partial sequences apart from b. Additionally, can be seen as the model receiving partial reward for choosing the action c. In summary, this paper makes two contributions:
We introduce a novel method for reward shap- ing in conditional text generation through pair- wise learning to rank.
We demonstrate the effectiveness of our ap- proach, showcasing not only high-quality gen- eration but also improved estimation of partial sequence values through beam monotonicity and resilience.
Our distinction proposing a reliable policy in

---

2 Background
of y with tempering. The weight term q is similar to the importance weight in importance sampling. but it differs that here g values are normalized over the set Y.
As a background, we formulate the description of how autoregressive conditional text generation is formulated as a Markov decision process and the enveneenvironment interaction is defined to transform the task into an RL problem. As men- tioned before, state 8t at time step corresponds (x, yt),, and the possible action a this mo- ment is the act of choosing the next token, yt+1 to reach the next state 8t11- Here the environ- ment is fully observable and the state transition given the action is deterministic, that is, select- ing an action (the next token) is equivalent to se- lecting the next state (prefix with length increased by 1). A conditional language model then can be regarded as directly parameterizing the policy, To (ay st) (3( x, yst).
3.1.2 BRIO
BRIO (Liu et al., 2022), one of the state-of-the-ar models for abstractive summarization, also serves as the baseline for our study.
Contrastive learning has been proven effec- tive at learning embeddings of images and sen- tences (Chen al., 2020; Gao et al., 2021), and has recently gained attention within conditional text generation. BRIO utilizes a contrastive objec- tive between full sequences for rank learning. It assigns higher bennth-normalizerr probability f to sequences with high utility u using pairwise contrastive loss
Typically, the interaction with the environment is simulated as the delayed reward
L Σ max (0, f(f) + 1)), asa
-)),
(u(y:)), Rτ 0,
if lyl, otherwise,
(3)
(1)
where and j are the ranks of two samples y' and yy, with being the higher rank, that is. u' == u(y':x) > =(y);x) =: u², and f(i) == (1/T9) log (o x, y is the length penal- ized log likelihood of the sequence y' with length penalty hyperparameter a. is hyperparameter for determining the margin which is proportional to the rank difference j - i. This contrastive loss then used in conjunction with the MLE loss (the negative log- lig-liielihood loss for the reference) to train the model:
where Rg = R(s)-1, st) is the reward for making transition from 1 1 9t by choosing the action aç. Delayed reward hinders the model from figuring out which actions in the past should be attributed to the final outcome.
3 Method
3.1
Baselines
We first briefly introduce the bascline methods we consider and proceed to our proposed method.
3.1.1 Minimum risk training
L = LMLE + Lo.
(4)
Minimum risk training (MRT) (Shen et al., 2016) is one of the most representative RI. practices for conditional text generation. It is slightly altered variation of the REINFORCE algorithm (Williams, 1992), or Monte Carlo policy gradient. Initially adopted in NLP for machine translation task, MRT uses sequences sampled from the model estimate the gradient of the expected cumulative reward to be obtained under the current policy. minimizes the risk, or the negative expected reward
3.2 Motivation
Our primary goal is to have the ability to evaluate individual actions. However, MRT and BRIO can compare only fully generated sequences y and y making it challenging to estimate the values of individual actions partial sequences y!, and y?, within those sequences.
To address this limitation and enable the model to understand the consequences of individual ac- tions, we have the following requirements:
-= E<(r)u(yi:s yeY
We need way measure the desirabil- ity of action or a partial sequence based on sparse sequence-level utility u. This would allow us to estimate how desirable a partial se- quence is, even with this limited information.
R1:
where Y the set of samples generated with beam search, and q(y) is the weight of y. which is com- puted as the normalized assigned likelihood

---

R2:
We should be able to determine which actions or partial sequences participate in the model update. When we modify the BRIO objective to focus on partial sequences instead of full sequences, we should identify a subset of partial sequence pairs that contribute to rank learning, to avoid requiring the model to meet overly ambitious goal of estimating full order of partial sequences.
Generate outputs and rank with uQ.
1. What is the best way to deal with social anxiety?
2. How can I get rid of social anxiety
3. What is the best way to get over social anxiety?
4. How can I get over social anxiety?
5. How do you get over social anxiety?
Construct prefix tree from outputs.
By fulfilling these requirements, we can over- come the limitations of existing methods and en- able the model to learn the value of individual ac- tions and enhance their estimation of desirability.
3. Train for p(plp)) - p(p)lz) > A for each branch.
Mctaction higher final score
1s: prefix
deal
with social anxiety?
3.3 Proposed: PPR
What is the best way to
r/taction to lower final score
We now formally present our proposed method, PPR, that addresses RI and R2, posed in 3.2, ele- gantly at once. This is achieved by leveraging the prefix tree TI constructed from the set of sample se- quences Y generated from the model conditioned the source sequence x.
get
over social anxicty?
Figure 4: Brief illustration of the PPR training objective. For all 'branching nodes' found from prefix tree of outputs, PPR applies max-margin style loss function assign higher probabilities to actions that will eventually lead higher sequence-lewe utility scores.
For R1, PPR infers the value (y of a par- tially generated sequence ysr using the prefix tree T as
provides a natural solution. We select the branch- ing nodes in the prefix tree and compare the actions corresponding to each branch.
Vr(ys)):= = max x(y:;x,, Va.
(5)
where the max operator ranges over y' Y. In other words, (y the highest utility ob- served among the sequences sharing the common prefix Yçt- serves as the missing ground- truth quality measure for partially generated sequences, just as the utility metric evaluates fully generated sequences.
The branching nodes in the prefix tree T are well-suited for the task of selecting a feasible and necessary set of pairs to maximize the benefit of learning to rank. This is because:
We present the model with pairs of partial se- quences that share all but the last token. This requirement allows the model assess the impact of one-step move, which more feasible compared to distinguishing pairs of partial sequences with much longer chains of differing actions.
The prefix tree structure allows efficiently enu- merate over all sequences with the prefix Yst, as they correspond to the leaf nodes of the subtrce rooted at the node yst- This way, Vy can be efficiently determined for any given prefix yss.
As previously explained in Section although with Vr we can measure the desirableness of any prefix of any sequence in Y, can be an unrealistic goal to learn to make pointwise estimates Vr. which requires the model to decide ordering for arbitrary pairs of partially generated sequences in essence. Rather, we adopt the pairwise ranking approach of considering two actions as a pair and encourage the model to find the action that results in partial sequence with higher Vy.
The branches in the prefix tree were kept during the beam search because they were assigned sufficient probability mass by the model. Therefore, the model should be capa- ble of distinguishing these challenging pairs in order to perform well.
We now provide a detailed description of how the pairwise ranking objective is obtained. As illustrated in Figure 4, we begin by construct- ing a prefix tree T using the outputs generated with
Regarding R2 and how to construct the set of pairs to present to the model, the prefix tree also

---

the beam search. In this tree, each node repre- sents a prefix of at least one sample sequence in Y, and each edge corresponds to a token.
4
Experiments
4.1 Experiment settings
Next, we determine the rank of each token ue following the same prefix v in accordance to mar(V)(E)), the maximum possible utility when the generation starting from v ow; is complete. For all branching node in T with deg(v) > 1 children nodes, we rank the associated edges w; and next states of by (e;). As a result, select- ing wi and transitioning from v to 01 leads to the best outcome, while choosing (eeg(v) is the worst choice possible.
4.1.1 Task
As a main evaluation task, we focus on paraphrase generation to evaluate the effectiveness of the pro- posed PPR for conditional text generation, we ex- periment the paraphrase generation task. A paraphrase y of the source exhibits high utility u(y;x) x) if it (1) preserves the meaning x conveys, (2) a fluent sentence, and (3) deviates lexically and structurally from x, discouraging the copying behaviors y = x as a low utility. Regarding gener- alization to other tasks, please see Subsection 5.4.
We provide a higher reward for assigning a higher probability to w, as the next token compared to W i < j. The resulting pairwise ranking loss of PPR is in the form
4.1.2 Architecture and training details
We utilize an encoder-decoder transformer archi- tecture as the policy network. Specifically, we start from the pretrained checkpoints of BART (Lewis et al., 2020) and T5 (Raffel et 2020). We pro- vide the detailed hyperparmeter settings and other relevant configuration in Appendix A.
L. Σ
Σ
X),
deg(e)22 (i.)
(6)
where (1:)) == (ww x) is the probability of choosing the token wy conditioned on the source x and the prefix v, and P. is the set of pairs of indices that will participate in the comparison. For nodes with more than two children, deg(v) > 2, there are several possibílities for selecting which pairs to contrast, Pa. We considered the following candidates,
4.1.3 Datasets
We use two popular benchmarks on paraphrase gen- eration, namely QQP-Pos (Chen al., 2017) and MSCOCO (Lin al., 2014) for training and evalu- ation. QQP-Pos is subset of Quora Question Pairs (QQP) paraphrase identification corpus, where only positive paraphrase pairs are selected. Throughout this paper, we denote QQP-Pos as QQP for simplic- ity. MSCOCO is a dataset for image captioning, and two captions that describe the same image are treated as paraphrase pair. For both datasets, we use the standard data splits.
Dominate:
P. ((1.2), (1,3), (,,,),,,,,,,,,N))) (I,
Adjacent pairs:
P. (1, (2, (N - 1,,
All pairs:
P.
Roughly, QQP consists of more semantically and lexically similar paraphrases than MSCOCO. The self-BLEU (BLEU score between two paraphrases) measured from the test split is 18.35 in QQP, while only 2.46 in MSCOCO.
where N = deg(v). and proceeded with Dominate which performed well in preliminary experi- ments. In practice, the difference was almost indis- tinguishable as most of the branching nodes had two children.
Finally, we add pseudo-reference loss L'ILE where the sequence with the highest utility in Y serves as another reference sequence to obtain the following training objective for PPR:
4.1.4 Metries
While numerous metrics have been proposed for evaluating paraphrase generation automatically (Cao and Wan, 2020; Shen et al., 2022; Nigho- jkar and Licato, 2021), we choose BERT-iBLEU (Niu al., 2021), which is reference-free metric capturing both semantic similarity (using BERT- score) and lexical dissimilarity (using iBLEU). It is reported to outperform most of the source-only and reference-only metrics in human judgement
C = LMEE + L'LLE + L.
(7)
C'ILE encourages the model to prefer high-quality sequences it has generated on sequence-level, as elaborated in Section 5.
AA prefix tree is generated on-fly per each input sequences, as descrihed in Equation 7.

---

correlation with low computation overhead (Shen
QQP dataset
al., 2022; Nighojkar and Licato, 2021).
Model
Sampling
Bcam=l
Beam=10
MLE
75.86
67.92
68.64
BERT-iBLEU score is calculated as weighted harmonic mean of the BERT-score and the iBLEU score between the source and the output. Following the original paper, we set the weight hyperparam- eter 3 = 1 to match the scale of the two metrics. Outputs that are nearly identical to the source sen- tence result in low iBLEU, and thus penalized in terms of BERT-iBLEU score.
MRT
78.12
73.64
77.59
BART
BRIO
80.04
81.49
95.39
PPR
93.62
96,65
96,79
MLE
71.81
52.16
45.57
MRT
72.20
67.57
65,06
T5
BRIO
80.88
84.84
95.27
PPR
92.14
95.31
95.64
Reference
79.28
MSCOCO dataset
Model
Sampling
Beam=1
Beam=16
MILE
73.72
76.40
75.32
MRT
73.98
77.10
76,20
B +
BART
BRIO
75.91
81.89
96.62
BERT-iBLEU
PPR
90.78
96.03
97.00
BERT-score
BLEU
MIE
73.72
74.93
71,22
MRT
68.94
72.13
71,70
We used BERT-iBLEU as the utility u(.), that is, both for evaluating the model performance and for rewarding the model during training.
T5
BRIO 74.25
81.74
95.87
PPR 91.39
95.96
96,10
Reference
73.61
4.2 Results
Table 1: BERT-iBLEU scores paraphrase generation with different decoding strategies: unbiased sampling, greedy ('Beam=1') and beam search ("Beam=16') The row 'Reference' denotes the average score of reference paraphrases.
The result on two base architectures (BART, TS) and two paraphrase generation benchmarks (QQP. MSCOCO) is presented in Table 1. We have evalu- ated the models with different decoding strategies, namely (1) unbiased sampling and (2) beam search with varying beam sizes (1, 2, 4, and 16) where beam size of is precisely the greedy decoding. The full results, including scores for all beam sizes along with the standard deviation can be found in Appendix C; also, the score-beam size plot can be found in Figure 5.
Model
QQP
MSCOCO
MLE
12.41
2.26
MRT
BART
BRIO
0.07
0.00
PPR
MILE
38.56
6.47
MRT
36.02
5.66
T5
BRIO
0.01
0.00
PPR
0.02
0.00
Our proposed PPR consistently outperforms all baselines in all (model, dataset) pairs. We also present the interpretation of these results through the lens beam monotonicty and resilience intro- duced in Section 1.
Table 2: The portion of model output exactly copying the source sequence (%). MLE clearly fails to learn that copying is not desirable.
First, regarding the beam monotonicity, MLE and MRT failing to benefit from increasing beam size and thus violating it indicates poor correla- tion calibration between the likelihood assigned by these models and the target utility score. This suggests that the values of partial sequences implic- itly maintained by these models do not align well with the final desired outcome.
Our distinction is that PPR exhibits a nearly flat curve in Figure 5, indicating that the values of par- tial sequences estimated by our model align well with the actual final rewards obtained by continuing generation from those sequences. Although PPR was not explicitly designed for fully stochastic pol- icy scenarios, where unbiased sampling used for decoding, demonstrates significant performance improvement in such cireumstances.
Second, for beam resilience, while BRIO does show performance improvement with larger beam sizes, its significant performance decline with smaller beam sizes unbiased sampling, failing to achieve resilience indicates failure to consistently estimate the values of partial sequences. This sug- gests that BRIO's s high-ranking candidates are not trustworthy in early decoding stages, as we further anayze in Section 5.2.
Now we examine the failure of MLE in more detail. In addition to its BERT-iBLEU scores gen- erally ranking the lowest, Table 2 highlights its another weakness: the exact copy rate. This metric represents the percentage of model outputs that are exactly the same as the input sequence. Despite the training data consisting (source, reference) pairs that explicitly discourage exact copying as a

---

Model
T5
5.2 Step-wise analysis
Dataset
QQP
MSCOCO
AMLE
45.57
71.22
We analyze the model's beam resilience in a de- tailed, step-wise fashion. First, we select the top- ranked sequence with a beam size of 16 (referred as lop beam). For each generation step, we computed the reciprocal rank of the chosen token within the entire vocabulary and averaged it over all sequences with length of 10 (including EOS), which was the most common length observed.
LALE
77.41
91.24
Le
82.48
96.21
ÉMLE + LiALE
43.48
70.37
Le + OALE
94.50
95,44
C. + CAIEE
95.50
96.42
All
95.64
96.10
Table 3: Ablation results for three training objectives in Equation 7, with beam size of 16 at inference time. Results are from single-run experiments.
Figure 6 illustrates an interesting finding regard- ing the behavior of baseline methods compared to PPR. During the early to middle steps, baselines often do not consider the prefix of the top beam sequence as desirable. However, they progress, they change their decisions and favor the prefix. In contrast, PPR consistently achieves high token MRR scores across all time steps and in all cases. This implics that, even with greedily following the best actions, PPR is able to generate a sequence that closely resembles the one obtained through beam search.
desirable paraphrase, MLE training fails to capture this aspect from the data.
From an RL perspective, MLE training can be seen as behavioral cloning, where an expert demon- strates desirable sequences of actions, and the agent learns by simply imitating those actions. Our re- sults indicate that, when the desired goal is com- plex and multifaceted, simply following good paths leads to simple copying behaviors, which is wors- ened in QQP, which contains larger proportion of similar (quantitatively, high self-BLEU) para- phrases compared to MSCOCO.
This observation has two important implications. Firstly, it directly explains PPR's success in achiev- ing beam resilience during greedy decoding. Sec- ondly, strongly supports the effectiveness of PPR's pairwise ranking loss for partial sequences enabling the model to consistently and accurately estimate the values of partial sequences, climinat- ing the need for looking ahead possible continua- tions in beam search, to obtain sequences with high utility.
5 Analysis
We provide in-depth analysis of the behavior of our
model and baselines.
5.1 Ablation study
Table 3 presents the ablation study results, where we compare the different composition of training objective components listed in Equation 7.
5.3 Additional metrics
To prove robustness of the proposed PPR against different metrics, we propose a variant of BERT- iBLEU, BiP (BERT-iBLEU--PLL) which includes an additional perplexity term for measuring fluency of the generated paraphrase. When output y's perplexity is higher than the source sentence in scale of k. the score is proportionally penalized.
First, the importance of the contrastive objective
L. clearly demonstrated, as models trained with L. generally outperform ones trained without it. Furthermore, alongside the performance gain in sufficient beam sizes, Le alone can achieve beam monotonicity and resilience, i.e. model's robust- ness with varying beam sizes during inference as illustrated in Table 7.
BiP BERT-iBLEU min (1, k (.PP(((x) <PP(y))
Also, the pseudo-reference loss plays a key role in promoting the top-ranked candidate based on sequence-level utility. More detailed results regard- ing the pseudo-reference loss are available in Table 8. Finally, training without the reference loss, or reference-free in other words, led small drop in score for the QQP task but gain for MSCOCO. This suggests that the reference sequences QQP were better aligned with the source sequences, pro- viding more helpful guidance during training.
(9)
Automatic evaluation results for models trained with BiP as utility are provided in Table 4, where PPR clearly demonstrates beam monotoniticy and resilience together with high performance. For this purpose we have also reported results obtained by evaluating with metrics other than BiP, including ParaScore (Shen et al., 2022), which was designed to better align with human judgment.

---

TS-QQP
T6-MSCOCD
BART-QQP
BART-MSCOC
Cur
EROO
90-
90
50-
MRT
Teal BERT-iRK FU
85
85
85
85
70
70
70
70
85
65
16
Beam size
Figure 5: Test BERT-iBLEU score obtained from beam search decoding with varying beam sizes, to 16. Shaded area represents standard deviation. The MLE curve for TS-QQP is excluded due to y-axis coverage.
T5-00P
TS-MSCOCO
BART-OOP
BART-MSCOCO
10
1.0
1.0
1.0
Moan Mean Recipreca Rank
0.8
0.8
0.8
0.8
MRT
MLE
0.6
0.6
0.9
0.6
0.-
04-
0.4
0.4
02
0.2
02-
02-
0.
0.0
0.0 Token position
0.0
Figure 6: The token mean reciprocal rank (MRR) for the top ranked sequence over time steps. The curve from PPR consistently remains the top, maintaining values close to as opposed to baseline methods displaying their strong dependence the tolerance provided by beam search. Shaded area represents standard deviation.
BiP
fluency. a result, PPR won 24%/58% of the case and lost 18% 12% of the case compared to BRIO and MLE, respectively. Qualitatively, our strength was found with respect to faithfulness out of the three main requirements. Examples of generated samples and more details (automatic) evaluation results can be found in Appendix C and B.
Model
Sampling
Beam=]
Beam=10 16
MIE
54.01
69.47
67.28
TS
BRIO
$1.53
81.11
88.84
PPR
74.84
87.79
88.57
BERT-iBLEU
Model
Sampling
Bean=1
Beam=16
MLE
73.72
74.93
71.22
T5
BRIO
75.12
85.30
90.52
PPR
85.37
90.13
90.55
Parascore
5,4
Generalizing PPR to constrained MT
Model
Sampling
Beam=]
Beam=16
MLE
32.55
17.35
3.00
In addition to the paraphrase generation task mainly considered in this paper, we also conducted ex- periments on lexically constrained machine trans- lation, where the goal is to output hypothesis given source sentence to translate plus lexical constraints, which series of chunks of tokens that must appear on the generated sentence. This dual goal generating plausible and constraints- satisfying translation has been assessed with two metrics, namely BLEU and copying success rate (CSR1) (Wang et al., 2022; Chen et al., 2021).
T5
BRIO
72.91
85.46
89.91
PPR
84.52
89.89
89.98
Table 4: Automatic evaluation results of T5 models trained on BiP and MSCOCO dataset. We also present cross-evaluation results to show the effectiveness of training with PPR using BiP metric.
Also, we report human evaluation results for different models. We performed example-wise comparison between randomly chosen outputs of PPR and BRIO/MLE trained models (generated by beam search with beam size of 16), asking the an- notators to decide which one better paraphrase the given source sentence, or if they are compara- ble in terms of faithfulness, lexical divergence and
Table shows the results constrained machine translation task on the WMT16 En-Ro benchmark. BRIO and PPR used BLEU-CSR, the product of sentence-level BLEU score and CSR as the util-
"Smeetimss also denoted as EM (exact match).

---

BLEU
6.2 Reward shaping
Model
Sampling
Bcam=l
Beam= 16
MLE
22.92
27.01
27.79
On the other hand, reward shaping can be em- ployed to directly address the value prediction prob- lem, either by (1) providing additional reward on top of the original one to nudge the model towards accomplishing subgoals, or (2) distributing the ward over actions through potential-based method. An example of the former is Chan al. (2019), where generating each keyphrase is rewarded by using recall as the utility in keyphrase generation.
Marian
BRIO
23.67
26.37
27.21
PPR
24.70
27.86
28.46
CSR
Model
Sampling
Beam=l
Beam=16
MLE
81.96
83.97
84,99
Marian
BRIO
89.48
90.29
92.33
PPR
89.98
92.33
93.23
BLEU CSR
Model
Sampling
Beam=1
Beam=16
MLE
20.01
23.97
24.87
Marian
BRIO
21.76
24.81
25.59
As an example of the latter, in the potential- based method proposed by Bahdanau et al. (2017) for training actor-critic model on neural machine translation task, partial reward at each time step is defined the difference between the BLEU scores of the prefix of length t and 1 with respect the entire reference sentence:
PPR
23.12
26.36
27.14
Table 5: BLEU, CSR (Copying Success Rate), and BLEU-CSR scores from the constrained machine trans- lation task in WMT16 En-Ro benchmark.
ity for training. It is shown that our proposed PPR effectively pursues the dual goal of generating plau- sible translation containing the required constraints. Further experimental details and complete results can be found in Appendix and C.
R₂ () (y<(,)))),,,
(10)
where the potential, or the utility of a partial se- quence 1hp (y( x) = (, is the BLEU score of the partial sequence yse with respect the whole reference sequence ý.
6 Related work
However, it is hard to define such a task-specific potential over all states so that the resulting rewards would faithfully reflect the desirableness of each action, which explains marginal gain from the above partial reward. In contrast, our design of PPR allows to provide partial rewards directly based the values of the resulting states.
This section describes previous work addressing the misbehavior often observed from conditional text generation. Null sequences, repeated n-grams and gibberish can be generated the model as- signs high probability to them under certain cir- cumstances (Stahlberg and Byrne, 2019; Holtzman et al., 2020, inter alia). We categorize efforts based on whether they attribute these to the decoding method (Subsection 6.1) I) or to the model's policy (Subsection 6.2).
Conclusion
We proposed PPR (Pairwise Partial Reward), a novel approach to reward shaping through provid- ing partial rewards in reinforcement learning for conditional text generation. Our method utilizes prefix tree constructed from the set of sample se- quences learn to rank between action pairs, sup- porting any sequence-level utility metries for opti- mization. By considering samples collectively, our approach enables the model to reflect on its past de- cisions and immediately determine which actions led to favorable outcomes. This allows PPR to ef- fectively guide the model in estimating values and selecting desirable actions during generation. Ex- perimental results demonstrate that our model out- performs baselines, especially with smaller beam sizes or unbiased sampling, indicating a signifi- cant improvements in assessing the values of par- tial sequences and enhancing language models as stochastic policies.
6.1 Decoding methods
Some attribute the degeneration problem to the decoding method itself, as Meister et al. (2020) examined the inductive bias of beam search. Alter- native decoding methods to mitigate ill-formed out- puts, such as sampling- based approaches (Fan et al., 2018: Holtzman et al., 2020), regularized beam search (Yang et al., 2018; Meister et al., 2020), and constrained decoding (Kajiwara, 2019; Niu et al., 2021) have been propsoed. In paraphrase gener- ation, constrained decoding has been explored to discourage direct copying of the input.
These methods can be seen as ad-hoc solutions without addressing the root cause, unreliable value estimation, as we argue with beam monotonicity and resilience Section 4.2.

---

Acknowledgements
Ting Chen, Simon Kornblith, Mohammad Norouzi. and Geoffrey Hinton. 2020. A simple framework for contrastive learning of visual representations. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Reseurch, pages 1597-1607. PMIR.
This work was supported by Institute of Informa- tion & Communications Technology Planning & Evaluation (IITP) grant funded by the Korean gov- ernment (MSIT) (No. 2022-0-00077, AI Tech- nology Development for Commonsense Extrac- tion, Reasoning, and Inference from Heteroge- neous Data).
Zihang Chen, Hongbo Zhang, Xiaoji Zhang, and Leqi Zhao. 2017. Quora question pairs.
Angela Fan, Mike Lewis, and Yann Dauphin. 2018. Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume Long Papers). pages 889-898, Melbourne, Australia, Association for Computational Linguistics.
Limitations
One limitation of our work is that it incurs explo- ration (sampling) overhead during training, which is common among reinforcement learning ap- proaches to text generation. With this, PPR may require more time to update the model parame- ters compared to MLE, but surpasses MLE with a smaller number of updates. The trade-off analysis between two factors needs further exploration.
Tianyu Gao, Xingcheng Yao, and Danqi Chen. 2021. SimCSE: Simple contrastive learning of sentence em- beddings. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Process- ing, pages 6894-6910, Online and Punta Cana, Do- minican Republic. Association for Computational Linguistics.
Another limitation of this paper is that, though our work is readily applicable to any conditional generation tasks with any sequence-level evalua- tion metric, it still requires an extensive analysis of generalization more diverse set of tasks with pos- sibly longer target sequences and utility functions with even more complex designs.
Han Guo, Bowen Tan, Zhengzhong Liu, Eric Xing, and Zhiting Hu. 2022. Efficient (soft) Q-learning for text generation with limited good data. In Findings of the Association for Computational Linguistics: EMNLP 2022, pages 6969-6991 Abu Dhabi, United Arab Emirates. Association for Computational Linguisties.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020. The curious case of neural text degeneration. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 60, 2020. OpenReview.net.
References
Dzmitry Bahdanau, Philemon Brakel, Kelvin Xu, Anirudh Goyal, Ryan Lowe, Joelle Pineau, Aaron C. Courville, and Yoshua Bengio. 2017. An actor-critic algorithm for sequence prediction. In 5th Inter- national Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Con- ference Track Proceedings. OpenReview.net.
Tomoyuki Kajiwara. 2019. Negative lexically con- strained decoding for paraphrase generation. In Pro- ceedings of the 57th Annual Meeting of the Asso- ciation for Computational Linguistics, pages 6047- 6052, Florence, Italy. Association for Computational Linguistics.
Julia Kreutzer, Artem Sokolov, and Stefan Riezler. 2017. Bandit structured prediction for neural sequence-to sequence learning. In Proceedings of the 55th Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers). pages 1503-1513. Vancouver, Canada. Association for Computational Linguistics.
Yue Cao and Xiaojun Wan. 2020. DivGAN: Towards di- verse paraphrase generation via diversified generative adversarial network. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 2411-2421, Online. Association for Computational Linguistics.
Hou Pong Chan, Wang Chen, Lu Wang, and Irwin King. 2019. Neural keyphrase generation via reinforcement learning with adaptive rewards. Proceedings of the 57th Annual Meeting of the Association for Com- putational Linguistics, pages 2163-2174, Florence, Italy, Association for Computational Linguisties.
Ashutosh Kumar, Kabir Ahuja, Raghuram Vadapalli. and Partha Talukdar. 2020. Syntax-guided controlled generation of paraphrases. Transactions of the Asso- ciation for Computational Linguistics, 8:329-3:4 345.
Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, AbdeIrahman Mohamed, Omer Levy. Veselin Stoyanov. and Luke Zettlemoyer. 2020. BART: Denoising sequence-to-sequenee pre-training for natural language generation, translation, and com- prehension. In Proceedings of the 58th Annual Meet- ing of the Association for Compulational Linguistics,
Guanhua Chen, Yun Chen, and Victor O.K. Li. 2021. Lexically constrained neural machine translation with explicit alignment guidance. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14); 12300-12638.

---

pages 7871-7880, Online, Association for Computa- tional Linguistics.
transformer. Journal of Machine Learning Research, 21(140):1-67.
Jiwei Li, Will Monroe, Tianlin Shi, Sébastien Jean, Alan Ritter, and Dan Jurafsky. 2017. Adversarial learning for neural dialogue generation. In Proceedings of the 2017 Conference on Empirical Methods in Natu- ral Language Processing, pages 2157-2169, Copen- hagen, Denmark. Association for Computational Lin- guistics.
Mare' Aurelio Ranzato, Sumit Chopra, Michael Auli, and Wojciech Zaremba. 2016. Sequence level train- ing with recurrent neural networks. In 4th Inter- national Conference on Learning Representations, ICIR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings.
Lingfeng Shen, Lemao Liu, Haiyun Jiang, and Shuming Shi. 2022. On the evaluation metrics for paraphrase generation. In Proceedings of the 2022 Conference on Empirical Methods Natural Language Process- ing, pages 31 3178-199,, Abu Dhabi, United Arab Emi- rates. Association for Computational Linguistics.
Tsung-Yi Yi Lin, Michael Maire, Serge J. Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick. 2014. Microsoft COCO: common objects in context. In Computer Vision- ECCV 2014 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V, volume 8693 of Lecture Notes in Computer Science, pages 740-755. Springer.
Shiqi Shen, Yong Cheng, Zhongjun He, Wei He, Hua Wu, Maosong Sun, and Yang Liu. 2016. Minimum risk training for neural machine translation. In Pro- ceedings of the 54th Annual Meeting of the Associa- tion for Computational Linguistics (Volume Long Papers), pages 1683-1692, Berlin, Germany, Associ- ation for Computational Linguistics.
Yixin Liu, Pengfei Liu, Dragomir Radev, and Graham Neubig. 2022. BRIO; Bringing order to abstractive summarization, In Proceedings of the 60th Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pages 1890-2903, Dublin, Ireland. Association for Computational Lin- guistics.
Felix Stahlberg and Bill Byme. 2019. On NMT search errors and model errors: Cat got your tongue? Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Lan- guage Processing (EMNLP-IJCNLPP pages 3356- 3362, Hong Kong, China. Association for Computa- tional Linguisties.
Clara Meister, Ryan Cotterell, and Tim Vieira. 2020. If beam search is the answer, what was the question? In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 2173-2185, Online. Association for Computa- tional Linguisties.
Shuo Wang, Peng Li, Zhixing Tan, Zhaopeng Tu, Maosong Sun, and Yang Liu. 2022. A template- based method for constrained neural machine trans- lation. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 3665-3679, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
Nathan Ng, Kyra Yee, Alexei Baevski, Myle Ott, Michael Auli, and Sergey Edunov. 2019. Facebook FAIR's s WMT19 news translation task submission. Proceedings of the Fourth Conference on Machine Translation ( (Volume 2: Shared Task Papers. Day 1). pages 314-319, Florence, Italy, Association for Computational Linguistics.
Ronald J. Williams. 1992. Simple statistical gradient- following algorithms for connectionist reinforcement learning. Mach. Learn.,
Animesh Nighojkar and John Licato. 2021. Improv- ing paraphrase detection with the adversarial para- phrasing task. In Proceedings of the 59th Annual Meeting of the Association for Computational Lin- guistics and the 11th International Joint Conference on Natural Language Processing (Volume I: Long Papers), pages 7106-7116, Online. Association for Computational Linguistics.
Yilin Yang. Liang Huang, and Mingbo Ma. 2018. Break- ing the beam search curse: A study of (re-)scoring methods and stopping criteria for neural machine translation. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Process- ing, pages 3054-3059, Brussels. Belgium. Associa- tion for Computational Linguistics.
Tong NIu, Semih Yavuz, Yingho Zhou, Nitish Shirish Keskar, Huan Wang, and Caiming Xiong. 2021. Un- supervised paraphrasing with pretrained language models. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 5136-510 5150, Online and Punta Cana, Domini- can Republic. Association for Computational Lin- guistics.
Colin Raffel, Noam Shazeer, Adam Roberts, Kather- ine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020. Exploring the limits of transfer learning with a unified text-to-text

---

A Experimental settings in detail
approach of extracting constraints from public MT benchmarks for unconstrained MT in which only paired sentences without constraints are available. In order to best align with the actual use case of con- strained MT in practice, we leveraged a pretrained MarianMT model trained on En-Ro direction avail- able at Huggingface Transformers", and the corre- sponding tokenizer (with approximately 59k vocab size) to identify the words in the target sentences that the model is least confident with, based on the model's output log probabilities. Note that we used word-level constraints, rather than token-level ones, allowing a series of tokens to constitute a single constraint; the confidence for word was calculated as the average confidence for tokens in that word. We selected 1-3 words constraints, proportional to the sentence length. In order for the extracted constraints to be reasonable, we applied language filtering based on language detection tools which is a widely adopted practice in building MT' systems based on publicly available data (Ng et al., 2019), removing noisy examples such as those containing (dem sentences. Among the 610k training examples in WMT16 En-Ro dataset, we only used pairs of which (1) source sentence is classified En and target sentence is classified Ro, and (2) both source and target sentences are shorter than 32 tokens, which leaves slightly less than 100k sam- plcs. The constraints were appended to the source sentence, where the source and constraints were separated by <eos> token, to be fed as input to the model. Validation and test splits were processed in the same manner.
Here we provide the detailed experimental settings.
A.1 Paraphrase Generation experiments
We used pretrained T3-small (60M) and BART- base (139M) checkpoints, publicly available at Huggingface Transformers' with each correspond- ing tokenizers (with approximately 30k and 50k vocab size).
We used Adam optimizer with (81,82) (.9, .999) and e = le 8. We also used the linear learning rate scheduler with initial learning rate of 5e-5, batch size of 16, dropout rate of 0.1. We trained models for 5 epochs for both QQP and MSCOCO datasets and then chose the best check- point with target metric score (BERT-iBLEU) on the development set.
For methods other than MLE, we used beam search for obtaining on-po on-oolic samples at train time. For MRT, we used the fixed beam size of 16. For BRIO and PPR, we experimented with both 16 and 32, and chose the one with better performance on the development set. As result, for all model and dataset combinations, BRIO performed better with 16 while ours enjoyed the benefit of the larger beam size, 32.
Now we describe method-specific hyperparame- ter settings for BRIO and PPR. For BRIO, we used the fixed length penalty of a = 1.0 for normal- izing the sequence likelihood. We have searched over .001, .0,0011000 .05 .1 for determining the unit margin X, and X = .1 was the best for all configura- tions. For the loss scale hyperparameter we found that 7 10 worked the best for most of the cases, over 1, 3, 5, 10 while 7 = 2 gave the best result for BART on MSCOCO.
We initialized the models with the aforemen- tioned pretrained MarianMT checkpoint, which exhibited nearly 40-50% of CSR on its own. The models were trained for 5 epochs with initial learn- ing rate 2c-5, effective batch size 128 and beam size 16. For other method-specific hyperparameters we used the same values as in the main experiments.
For PPR, all the -odel-dttaset combinations shared the same best performing hyperparameter settings, where we have determined the contrastive loss scale hyperparamter y as 10 in the same way as for BRIO, and the margin as X 0.5 among 0.1, 0.5. As described before, we have put the same weight on the negative log-likelihood loss from the ground-truth truth reference sequence and the pseudo- reference sequence.
B Examples of generated paraphrases
Table includes generated paraphrase samples from models trained with different metrics and training objectives.
Models trained with MLE often generate a direct copy of the source shown in Table 2, or omit important details. On the other hand, PPR and BRIO trained with BERT-iBLEU clearly learns
A.2 Constrained MT experiments
Following previous works, as fully annotated set of training examples for constrained machine trans- lation task is not widely available, we chose the
htt http://huggggggcccee htt.c//...ooeeiiieeeeeeeeeee wwteeesiiiiiiiii....... opus-nt nt- en-ro
hattps://githun hattp::://gttuub.mm//uugggg wwwp:///gg.ggg.ae////tstttoooom.

---

exploit the design of BERT-IBLEU, which allows copying up to 3-grams from the source to maintain high semantic similarity captured by BERTscore yet still avoiding being penalized by BLEU score.
for models trained in BiP. Strong performance gain achieved with PPR compared its counterparts, especially with unbiased sampling and beam search decoding with small beam sizes.
The difference between models trained on BRIO and PPR is best shown in BiP examples. BRIO often leads to generating false information that is not faithful to the content of the source, high- lighted in italic. In contrast, PPR effectively re- tains, at least does not flip or change the mean- ing of important keywords present in the source sentence through directly contrasting token-level actions given the prefix, leading to better choices in critical steps. This showcases our method's ef- fectiveness in token-level credit assignment in au- toregressive conditional text generation.
Finally, Table 11 shows the full results on lexi- cally constrained machine translation task, where PPR outperforms others not only in the given met- ric for training, BRIO-CSR, but also in its individ- ual components (BRIO and CSR). While models trained using MLE or BRIO objectives tend fre- quently violate beam monotonicity, PPR can gener- ally take advantage of the increased beam size.
BERT-iBLEU
Model
Example
office cubicle with four different types computers.
Input
office cubicle with four different types
MLE
computers.
An office cubicle,with different computers types.
BRIO
An office cubicle containing different types computers.
PPR
Input
A Marine that is looking at his cell phone.
MILE
A man is looking at his cell phone.
BRIO
A Marine that's looking at his cell- sell-phone.
PPR
A Marine who is looking on his cellphone.
BiP
Model
Example
Input
A hotel has small tv on the dresser.
MLE
A tv on a dresser in hotel room.
A hotel is equipped with a large TV on top of
BRIO
the dresser.
PPR
A hotel features tv on top of the dresser.
Two yellow fruits hanging on branches full of leaves.
Input
MLE
Two fruits are hanging on the branches of tree. Two orange fruits are hanging a branch full of leaves.
BRIO
PPR
Two yellow fruits hang branch full of leaves.
Table 6: Generation examples from models trained with BERT-iBLEUU and BiP on MSCOCO dataset with as the base architecture.
C Complete results
Table 9 shows the results for paraphrasing in more detail including the standard deviation of each re- ported figure. Substantially improved performance with oracle reranker shows that MLE and MRT failing achieve beam monotonicity is largely due that their failing to align probability and target utility.
In addition, Table 10 displays the complete result

---

Model-Datasee Sampling
Beam=1
Beam=2
Beam=4
Beam=8
Beam=16
Oracle
T5-MSCOCO
92.21
96.02
96. 18
96.21
96.21
96.21
97.29
Table 7: BERT-IBLEU scores only trained with L., without any NLL loss( Limr)).
Model-Dataset
Sampling
Beam=1
Beam=2
Beam=4
Beam=8
Beam=16
Oracle
BART-QQP
90.021
96.721
96.77
96.78æ
96.78a
96.79..01
97
BART-MSCOCO
82.75+
96.31
96.65
96.68
96.69
96.69
97.33
T5-QQP
88.03 1.05
94.24
94.53
94.59
94.59 1..0
94.59 1.os
96.34
T5-MSCOCO
84.77+
95.13+..0
95.34
95.42+
95.43
95.44
96.7 +.05
Table 8: BERT-iBLEU scores from PPR without the pseudo-reference loss. Still, shrinking the beam size has little effect on the performance.
QQP dataset
Model
Sampling
Beam=
Beam=2
Beam=4
Beam=
Beam= 16
Oracle
MLE
75.86=.44
67.92 24
69.60+ 1.5
68.32= 26
68.50+ .22
68.64+.2
88.61 ::05
MRT
78.122.11
m3.64=.7
76.97
37
77.49
77.59
88.75
BART
BRIO
+0.04
81.49
90.51 +:71
94.06
95.04
95.39+.13
96.16+117
PPR
93.62.1.0
96.652.12
96.78m..
96.80
96.80..0
96.791.0
97.23
MLE
71.81 1.00
52. 16
47.81 4:43
46.23
45.72
45.57
88.60=00
MRT
72.20
67.57 #.16
65.98
65,34
65.13
65.06
81.71
T5
BRIO
80.8811.16
84.84_110
92.51
94.92_.11
95.23
95.27
96.51
PPR
92.14
95.31
95.59
95.63_..
95.64
95.641.26
97.00
Reference
79.28
MSCOCO dataset
Model
Sampling
Beam=1
Beam=2
Beam=4
Beam=8
Beam=16
Oracle
MLE
73.722.3
76.40
76.30
75.78_.5
75.481.4
75.321
84.33
MRT
73.98
77.10=..
76.99
76.67-.1
76.42+.a
76.20+.1
84.57
BART
BRIO
75.91 2.08
81
12.15
95.68=16
96.43
96.62
96.85
PPR
90.78++.1
96.93
96.99 -.0
97.00-.10
97.00+.10
97.00+.10
97.57
MLE
73.72+.11
74.93
73.99 =//
72.52-11
71.69
71.22+30
85,45 4
MRT
68.944.0
72.13
72.24
72.05
71.87
71.70
78.96
T5
BRIO
74.25 +.50
81.74
90.96
94.88
95.634.14
95.87+.11
96.37
PPR
91.39
95.96=00
96.09
96.10_m
96.10
96.10
97.162.02
Reference
73.61
Table BERT-BBLEU scores on paraphrase generation with different decoding strategies, with standard deviation. The column 'Oracle" denotes the average score of the sequence with the highest score in each set of candidates generated with beam search (of heam size 16), that is, the score obtained with oracle reranking. Our model not only outperforms baselines in all cases but also retains the performance with greedy decoding or unbiased sampling compared to applying beam search with beam size 16, which clearly demonstrates its excelling at estimating the values of partial sequences. All values are averaged over runs with different random seeds. Boldfaced numbers indicate statistical significance under p < .05, while boldfaced with indicate p < .07.

---

BiP
Model
Sampling
Beam=1
Beam=2
Beam=4
Beam=8
Beam=16
Oracle
MLE
54.01
69.47
68.40
68.36
67.77
67.28
84.03
T5
BRIO
51.53
81.11
86.44
88.17
88.60
88.84
92.24
PPR
74.84
87.79
88.37
88.49
88.57
88.57
92.58
BERT-iBLEU
Model
Sampling
Beam=1
Beam=2
Beam=4
Beam=8
Beam=16 16
Oracle
MLE
73.72
74.93
73.99
72.52
71.69
71.22
85.45
T5
BRIO
75.12
85.30
88.77
90.04
90.40
90.52
92.73
PPR
85.37
90.13
90.46
90.54
90.54
90.55
93.46
Parascore
Model
Sampling
Beam=1
Beam=2
Beam=4
Beam=8
Beam= 16
Oracle
MLE
32.55
17.35
11.69
6.91
4.32
3.01
34.39
T5
BRIO
72.91
85.46
88.39
89.50
89.81
89.91
92.06
PPR
84.52
89.69
89.89
89.96
89.97
89.98
92.25
Table 10: Complete automatic evaluation results of T5 models trained with BiP metric as utility on MSCOCO dataset, evaluated by different metrics. Note that significant performance gain be achieved in sampling and small beam size settings when trained with PPR, and even when assessed with different evaluation metrics other than the one used as the utility (reward) train the model, PPR exhibits beam monotonicity and resilience, Values for BRIO and PPR are from single-run experiments.
BLEU
Model
Sampling
Beam=1
Beam=2
Beam=4
Beam=8
Beam=16
MLE
22.92
27.01
27.39
27.89
27.82
27.79
MarianMT
BRIO
23.67
26.37
27.01
27.36
27.36
27.21
PPR
24.70
27.86
28.33
28.21
28.43
28.46
CSR
Model
Sampling
Beam=1
Beam=2
Beam=4
Beam=8
Beam=16
MLE
81.96
83.97
84.31
85.55
85.21
84.99
MarianMT
BRIO
89.48
90.29
92.10
92.10
92.43
92.33
PPR
89.98
92.33
92.66
92.89
93.00
93.23
BLEU-CSP
Model
Sampling
Beam=1
Beam=2
Beam=4
Beam=8
Beam=16
MLE
20.01
23.97
24.17
25.00
24.95
24.87
MarianMT
BRIO
21.76
24.81
25.49
25.69
25.73
25.59
PPR
23.12
26.36
26.90
26.82
27.06
27.14
Table 11: BLEU, CSR(Copying Success Rate%) and BLEU-CSR scores from the constrained machine translation task on WMT16 En-Ro benchmark. BRIO and PPR used BLEU-CS CSR as utility. Values are from single-run experiments.


Reviews:
[{"review_id": "1i3xTl41vL", "reviewer": "Reviewer_4L43", "summary": "", "questions": "- In the ablation study (Section 5.1), how about the score using\n  $L_{MLE}$ + $L'_{MLE}$? I want to know the effectiveness of\n  $L_c$ alone?\n", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Regarding organization and notations:** Thanks for the suggestion. We will follow those to reorganize our paper.\n\n**Regarding ablation study:** Using only the reference loss $L_{\\textrm{MLE}}$ and the pseudo-reference loss $L^\\prime_{\\textrm{MLE}}$ without the contrastive loss $L_c$ gave nearly the same result as using the reference loss only (\"MLE\").\nSimilarly, excluding both of them incurred minimal changes in performance or training dynamics.\nThe following results are from single-run experiments.\n\n| Training objective | Sampling  | Greedy    | BS=2      | 4         |\n|:------:|:---------:|:---------:|:---------:|:---------:|\n| $L_{\\textrm{MLE}} + L^\\prime_{\\textrm{MLE}}$ | 73.69 | 74.78 | 73.26 | 71.64 |\n| $L_c$ | 92.21 | 96.02 | 96.18 | 96.21 |\n\n**Regarding limitation section:** Please see our answer for WfAY.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The proposed method is well motivated.\n\n- The proposed method achieves a substantial gain over the widely-used\n  baseline methods.\n\n- The extensive analysis supports the motivation of the proposed\n  method.\n", "reasons_to_reject": "- It is little difficult to follow the paper, and the paper\n  organization is worth reviewing. Figure 4 is the easiest to\n  understand, and should be presented in Section 1. Furthermore,\n  Figure 2 is difficult to understand as the beginning of the paper\n  (especially, the meaning of the baselines (A) and (B) is hard to\n  understand). This section should be described after the proposed\n  method is described.\n\n- The notations for the proposed method are difficult to\n  follow. Please refer to \"Typos Grammar Style And Presentation\n  Improvements\".\n\n- Although mentioned in the Limitations section, the proposed method\n  is validated only on the paraphrase generation task. It is not clear\n  that the proposed method is effective on the machine translation or\n  summarization tasks, where the reinforcement learning is widely\n  used.\n", "questions_to_authors": "- In the ablation study (Section 5.1), how about the score using\n  $L_{MLE}$ + $L'_{MLE}$? I want to know the effectiveness of\n  $L_c$ alone?\n", "paper_topic_and_main_contributions": "The supervised learning for conditional text generation suffers from\nthe exposure bias problem, and reinforcement learning has been widely\nused to avoid this problem. However, this method faces the sparse and\ndelayed reword problem, where the reward can be obtained only when the\ngeneration is finished.\n\nTo deal with this problem, this paper presents PPR (Pairwise Partial\nReword), a method for providing partial rewords for intermediate\naction tokens. The proposed method first constructs a prefix tree\nusing sampled sequences, and employs a pairwise ranking objective for\nthe branching nodes. Then, the model is encouraged to prefer the\nbranch with a higher expected reward.\n\nThe experimental results on the paraphrase generation task demonstrate\nthe proposed method outperforms several baseline methods.\n\nThe proposed method is well motivated, and achieves a substantial gain\nover the baseline methods. The extensive analysis supports the\nmotivation of the proposed method.\n", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "None"}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "- l042: likelihood -> probability\n\n- l215: .. y^2. making .. -> .. y^2, making ..\n\n- l242: address -> addresses\n\n- l242: 3.2 -> Section 3.2\n\n- l295: When is \"we begin by constructing a prefix tree..\"\n  performed? This is performed before training the proposed method\n  using a pre-trained model? Please clarify this.\n\n- l298: from the beam search -> with the beam search\n\n- l304: It is hard to follow the presented notations. The subscript\n  \"1\" in w_1 and v_1 and deg(v) in w_{deg(v)} and v_{deg(v)} are hard\n  to understand.\n\n- l313: p'(v_{j}) -> log p'(v_{j}), p'(v_{i}) -> log p'(v_{i})\n\n- l320: We have considered -> We consider\n\n- l340: section 5.1 -> Section 5.1"}}, {"review_id": "nSali0C6KN", "reviewer": "Reviewer_yfPs", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Regarding human evaluation:** We agree that human evaluations would help us evaluate whether the reward aligns with human perception of quality and will report in the revised draft.\nMeanwhile, we also want to clarify by pointing out that the design of reward is not our contribution.\nSee our answer for reviewer WfAY, on how our work is orthogonal to the choice of reward metrics and our findings remain unchanged for such choice.\n\n**Regarding missing references:** Thanks for the suggestion.\nAs the reviewer suggested, the adaptive rewards in Chan et al., 2019 could be seen as providing a partial reward for each keyphrase generation, though the task context differs from ours.\nWe will add discussion to the revised paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The motivation of this work is very clear and is well supported by quantitative analysis on the monotonicity and resilience of beam search decoding. \n\nThe proposed reward shaping technique for providing partial reward feedback to text generation models is very novel. It is the first work that applies prefix tree for reward shaping in text generation. \n\nThe proposed method outperforms previous reinforcement learning and contrastive learning algorithms for text generation. \n\nThe automatic evaluations are comprehensive. It extensively analyzes the performance of different algorithms with varying beam sizes. It also conducts a stepwise analysis on the beam resilience of PLMs. \n", "reasons_to_reject": "This paper does not conduct human evaluations to verify the quality of the model-generated outputs. The reviewer suggests the authors conduct human evaluation on a random subset of the model outputs. ", "questions_to_authors": "", "paper_topic_and_main_contributions": "This paper aims to address the credit assignment problem of reinforcement learning algorithms in text generation tasks. To this end, it proposes a reward-shaping method to provide partial reward on partially decoded sequences. The idea is to teach a model to distinguish the relative desirability between pairs of decoding actions by utilizing the prefix tree constructed from the sampled sequence. ", "excitement": 4, "reproducibility": 5, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Missing_References": "Please add the citation to the following paper. The following paper also assigns partial rewards to present keyphrases and absent keyphrases for keyphrase generation models:\n\nNeural Keyphrase Generation via Reinforcement Learning with Adaptive Rewards. ACL 2019. "}}, {"review_id": "Z6BYcwR3vG", "reviewer": "Reviewer_WfAY", "summary": "", "questions": "A) Why did the authors not experiment on summarization, given that one of the comparison methods (BRIO) is designed for summarization?\n\nB) Since beam search often leads to a set of fairly similar hypotheses, did the authors experiment with using other sampling methods to generate the candidate outputs used to construct the prefix tree?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Regarding BERT-iBLEU metric and the 'Related work' section:**\nAs the reviewers have pointed out, we are aware that some metrics may not properly correlate with human evaluation or be vulnerable to inadequate outputs, and RL methods using them as rewards can exploit such properties (Pang et al., 2023; [Yan et al., 2023](https://aclanthology.org/2023.acl-long.297)). These are addressed by improved metrics, while the optimization methods are rather orthogonal to the issue (Pang et al., 2023; [Skalse et al., 2022](https://openreview.net/forum?id=yb3HOXO3lX2); [Hao et al., 2023](https://openreview.net/forum?id=1_gypPuWUC3)). We stress our target is the optimization method itself, not the design of the metric, as ours can be applied to any given metric.\n\nHowever, we acknowledge with the reviewer’s suggestion to discuss these concerns in the prior literature and consider adopting Pang et al. (2023) to penalize gaming via perplexity measure ([Fabre et al., 2021](https://aclanthology.org/2021.eacl-main.180)) for BERT-iBLEU, which we denote as BERT-iBLEU-PPL. Considering another metric also helps us address the reviewer's concern that whether our finding is consistent when training-evaluation metrics differ: Below are additional experiments where we used BERT-iBLEU-PPL for training and evaluated with different metrics, where ours outperforms in all settings.\n\nWe will report full results including human evaluation in the revised paper.\n\n#### Evaluation with BERT-iBLEU-PPL\n| Method | Sampling  | Greedy    | BS=2      | 4         |\n|:------:|:---------:|:---------:|:---------:|:---------:|\n| MLE    | 54.01     | 69.47     | 68.40     | 68.36     |\n| BRIO*  | 51.53     | 81.11     | 86.44     | 88.17     |\n| Ours*  | **74.84** | **87.79** | **88.37** | **88.49** |\n\ncf. reference sentences score 55.24\n\n#### Evaluation with BERT-iBLEU\n| Method | Sampling  | Greedy    | BS=2      | 4         |\n|:------:|:---------:|:---------:|:---------:|:---------:|\n| MLE    | 73.72     | 74.93     | 73.99     | 72.52     |\n| BRIO*  | 75.12     | 85.30     | 88.77     | 90.04     |\n| Ours*  | **85.27** | **90.03** | **90.46** | **90.54** |\n\n#### Evaluation with Parascore ([On the Evaluation Metrics for Paraphrase Generation](https://aclanthology.org/2022.emnlp-main.208) (EMNLP 2022))\n| Method | Sampling  | Greedy    | BS=2      | 4         |\n|:------:|:---------:|:---------:|:---------:|:---------:|\n| MLE    | 72.47     | 80.92     | 82.32     | 84.36     |\n| BRIO*  | 72.91     | 85.46     | 88.39     | 89.50     |\n| Ours*  | **84.52** | **89.69** | **89.89** | **89.96** |\n\nThe above results are obtained with T5 on MSCOCO dataset, single run experiments with the same set of hyperparameters used in the draft; we will report the average and the standard deviation from multiple runs as we did before in the revised paper.\nCompared to BERT-iBLEU, BERT-iBLEU-PPL additionally takes into account the fluency of the generated paraphrase by penalizing the score when the perplexity of the generated sentence is higher than that of the source sentence.\n\n**Regarding comparison to other paraphrase systems:** We compare our BERT-iBLEU scores with previous paraphrasing systems using pretrained T5 checkpoint and Quora Question Pairs (QQP) dataset, which is the most widely available combination from literature.\nAs demonstrated, our claim about the effectiveness from the paper remain unchanged.\n\n| Method | BERT-iBLEU |\n|:------:|:----------:|\n| Ours (as in draft) | 95.64 |\n| Dynamic blocking   | 83.1  |\n| TASSDB      | 77.73 |\n| + RulePG    | 81.97 |\n| Separator   | 80.19 |\n| HRQVAE      | 65.01 |\n\nThe numbers are from [Unsupervised Paraphrasing with Pretrained Language Models](https://aclanthology.org/2021.emnlp-main.417) (Niu et al., EMNLP 2021) and [RulePG: Syntactic Rule-enhanced Paraphrase Generation](https://ieeexplore.ieee.org/document/10191854) (Lan et al., IJCNN 2023).\nNote that our result is based on `T5-small` architecture, while other systems have used either `T5-base` or `T5-large`, its larger counterparts.\n\n**Regarding other tasks:** As the reviewer pointed out, as in BRIO, our approach can be straightforwardly adapted for the summarization task. Though we see preliminary promising results, due to the resources required for conducting extensive experiments on summarization benchmarks containing much longer texts, conclusive results will be reported later, either in discussion or the revised draft.\n\n**Regarding sampling methods during training:**\nWe have experimented with diverse beam search ([Vijayakumar et al., 2016](https://ojs.aaai.org/index.php/AAAI/article/view/12340)) and unbiased sampling as the sampling method at training time, which was not effective and thus unreported. We susepct two possible causes; (1) prefix trees constructed with these methods tend to branch too early, making it difficult to provide supervisory signals on later steps, and (2) less important actions(tokens) can be over-represented via random sampling or diversification.\n\n**Regarding presentation:** Thanks for the suggestion. We will reorganize the tables for ablation study results in the revised paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The authors propose an elegant solution to an important problem, with potential relevance to RLHF.\n\nThe paper is well written and clearly explained.\n\nExperiments are fairly thorough with ablations included. The insight about beam monotonicity and resilience (Figs 2 and 5) is interesting and nicely motivates the proposed method.", "reasons_to_reject": "The evaluation is based solely on BERT-iBLEU, which is the same metric used as a training objective. It is no surprise therefore that the scores increase! No analysis is performed as to whether the method leads to truly higher quality (and more diverse) paraphrases, or whether it leads to degenerate output that scores highly but is not useful: see e.g. Evaluating Rewards for Question Generation Models, Hosking & Riedel (2019), On Improving Summarization Factual Consistency from Natural Language Feedback, Liu et al. (2023), Reward Gaming in Conditional Text Generation, Pang et al. (2023) and many others for examples of reward gaming. In my view this is a fundamental issue with the paper as it stands and is the main reason for my soundness score.\n\nNo human evaluation is included to confirm the automatic results.\n\nAlthough I recognise that the paper is focussed on sampling from general models, it would be good to see a comparison to other paraphrasing systems.\n\nEDIT: Additional results presented in the rebuttal show that reward gaming does not seem to be an issue. The authors indicate that they will include a human evaluation in any revised version of the paper.", "questions_to_authors": "A) Why did the authors not experiment on summarization, given that one of the comparison methods (BRIO) is designed for summarization?\n\nB) Since beam search often leads to a set of fairly similar hypotheses, did the authors experiment with using other sampling methods to generate the candidate outputs used to construct the prefix tree?", "paper_topic_and_main_contributions": "The paper proposes a method for improving credit assignment when training text generation models using RL. The method uses a prefix tree to store the rewards assigned to a set of complete candidate generations, and thus to assign rewards to the partial generations. It concentrates on the task of paraphrase generation, with experiments performed on two base models and two datasets. Aside from a major issue with evaluation, this is a well written and interesting paper.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "Table 4 caption could be more informative. Also, the authors could consider combining Table 4 and 5."}, "extra_text": {"Missing_References": "The related work section is a little sparse - I suspect there is significant previous work within RL about credit assignment and partial rewards, although I’m not familiar enough with the area to suggest specific papers."}}]

Author rebuttal:

Meta-review: The paper targets the problem of large action space and the delayed reward problem when RL is used for conditional text generation. A thorough evaluation is conducted. A common concern of reviewers is of human evaluation which authors agree to include in the final version of the paper. All the other experiments using different metrics and comparisons with other baselines are provided during rebuttal.
Decision: Accept-Main