QUEST: Quality-Aware Metropolis-Hastings Sampling for Machine Translation
Authors: Gonçalo Faria
Sweta Agrawal
António Farinhas
Ricardo Rei
José G. C. de Souza
Andre Martins
Venue: NeurIPS 2024 poster (2024)
Keywords: Machine Translation
Decoding
Quality Estimation
Primary area: natural_language_processing
TL;DR: This paper presents a method to generate diverse and high-quality machine translations by sampling from a Gibbs distribution using the Metropolis-Hastings algorithm.

Abstract: An important challenge in machine translation (MT) is to generate high-quality and diverse translations. 
Prior work has shown that the estimated likelihood from the MT model correlates poorly with translation quality. 
In contrast, quality evaluation metrics (such as COMET or BLEURT) exhibit high correlations with human judgments, which has motivated their use as rerankers (such as quality-aware and minimum Bayes risk decoding). However, relying on a single translation with high estimated quality increases the chances of "gaming the metric''. 
In this paper, we address the problem of sampling a set of high-quality and diverse translations. 
We provide a simple and effective way to avoid over-reliance on noisy quality estimates by using them as the energy function of a Gibbs distribution. Instead of looking for a mode in the distribution, we generate multiple samples from high-density areas through the Metropolis-Hastings algorithm, a simple Markov chain Monte Carlo approach. 
 The results show that our proposed method leads to high-quality and diverse outputs across multiple language pairs (English$\leftrightarrow$\{German, Russian\}) with two strong decoder-only LLMs (Alma-7b, Tower-7b).

QUEST: Quality-Aware Metsonolis-aastings Sampling for Machine Translation
Gonçalo R. A. Faria' Sweta Agrawal', António Farinhas
Ricardo Rei José G. C. de Souza?, André E.T. Martins2.3,, UUniversity of Washington, Instituto de Telecomunicações, Instituto Superior Técnico, Universidade de Lisboa, 4Unbabel, "ELLIS Unit Lisbon gfaria@cs. washington.
Abstract
An important challenge in machine translation is to generate high-quality and diverse translations. Prior work has shown that the estimated likelihood from the MT model correlates poorly with translation quality. In contrast, quality evaluation metrics (such COMET or BLEURT) exhibit high correlations with human judgments, which has motivated their use as rerankers (such as quality-aware and minimum Bayes risk decoding). However, relying on single translation with high estimated quality increases the chances of "gaming the metric". In this paper, we address the problem of sampling a set high-quality and diverse translations. We provide a simple and effective way to avoid over-reliance on noisy quality estimates by using them as the energy function of Gibbs distribution. Instead of looking for a mode in the distribution, we generate multiple samples from high-density areas through the Metropolis-Hann Hastings algorithm, simple Markov chain Monte Carlo approach. The results show that our proposed method leads to high-quality and diverse outputs across multiple language pairs DENGLISHI+(GERMAM) RUSSIAN]) with two strong decoder-only LLMs (ALMA-7B, TOWER-7B).
Introduction
Machine translation (MT) is becoming increasingly more accurate and powerful, it benefits from the many capabilities and acquired knowledge of large language models (LLMs) (Freitag et al.
2023b Hendy et al. 2023). However, for many domains and languages the quality of translation is still not satisfactory for example, hallucinations or critical errors are serious issue when translating high-risk content, as in medical and legal domains (Khoong et al., 2019 Taira al. 2021 Shen jet al. 2023) Guerreiro et al., [2023b] Sanz- Valdivieso and López-Arry 2023] Grimm et al. 2024). Developing procedures for sampling higher-quality translations is therefore in high demand.
known that the output quality of the translations generated by maximizing the model likelihood is limited because of the inadequacy of the mode-models tend to produce distributions over outputs that are highly peaked, favoring a single hypothesis (Eikema and Aziz 20200 Peters and Martins 202 Eikemma 2024): and improving search often makes things worse (Kochn and Knowles 2017 Stahlberg and Byrne 2019). In general, maximizing model likelihood tends to overlook hypotheses that could be equally valid and more appropriate in certain contexts. To address this limitation, string of work has been initiated towards "quality- -awae decoding". which leverages powerful quality estimation (QE) and evaluation metrics, such as COMET (Rei et al. 2022) BLEURT (Yan et al.) 2023), to explore and rerank a broader range candidate hypotheses generated via sampling from 2022a Fernandes et al. 2022b Farinhas
the model's distribution, selecting the best-1 (Freitag et al.
et al. 2023) or the best-k (Jinnai et al. 2024 Singhal et al.
2023) according to these learned metrics.
WWok done while Instituto de Telccomunicações.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

1. Sample index
2. Generate
3. Accept/Reject
y t+1
Figure 1:
QUEST samples an index from the current translation (y"), removes all elements to the right of the index, generates continuation, and then uses the Metropolis- -eatopolis-Hastingss acceptance criterion to decide whether to accept or reject the resulting new translation. The process continues for fixed number of T iterations.
Despite the benefits, reranking-basee methods have their own drawbacks. There is risk of these approaches overfitting to the metrics used, potentially leading to illusory gains in quality, as the translations obtained via optimizing these metrics may not always be preferred by humans when compared to other alternatives (Fernandes et al. 20226). Secondly, their effectiveness is limited by the quality of the initial candidate set. For instance. Vernikos and Popescu- Belis (2024) show that many high-quality translations, generated by combining translation hypotheses, are less likely to be sampled from the model's distribution even with very large pool size.
One potential way to remedy these issues, which we explore this paper, is to use these automatic metric proxies as the energy function of a Gibbs distribution. However, sampling hypotheses from this distribution presents a difficult challenge: unlike likelihood-based sampling. "quality-based sampling" from Gibbs distribution cannot be performed autoregressively, and is intractable to enumerate and score all possible hypotheses. We address this challenge by proposing a simple and effective Markov chain Monte Carlo approach (MCMC) method, combining the Metropolis- Hastings algorithm with suitable proposal distribution. Our method, Quality-Aware Metropolis- Hastings (QUEST) Sampling, uses novel proposal distribution that compatible with sentence- level evaluation metrics, common in text generation tasks like MT (Figure [.. We further note that while we focus on MT, where automatic QE metrics are more developed and robust, our proposed method is general and can be applied to other natural language processing (NLP) tasks. Furthermore, as our method agnostic to the specific quality metric used in the Gibbs distribution, it can directly benefit from any future improvements in the metrics.
We show that QUEST sampling results in high-quality and diverse samples on multiple test beds (WMT23 ENGLISH ++ [GERMAN, RUSSIAN 1) and with multiple decoder-only LLMs (ToWER-7B, ALMA-7B), Our method generates many novel hypotheses from the high-density regions unlikely to be generated via ancestral sampling. Furthermore, with increasing chain size, average quality as measured by automatic metrics continues to improve, unlike ancestral sampling, where the candidate set quality remains unchanged even with larger pool size
Background
2.1 Large Language Models for Machine Translation
Generating translations from autoregressive LLMs (either encoder-decoder or decoder-only) involves conditioning the language model on a prompt æ, which is a sequence of tokens (I1, T2, ......... Zi, E X encoding the text to be translated coupled with a translation instruction (Raffel et al. 2020 Hendy et al. 2023). Let V be a fixed vocabulary and y = V* its Kleene closure. The joint distribution over the output translations, y E V, given the prompt æ, can be factorized as the product of conditional probabilities over individual tokens (V1, V/...., VN), where each E V. The probability of
We release the code replicate our experiments https: https://ww..qussteccoingg

---

particular translation y for given input can be written as
N PLM(U| = II PLM(UAVVe
Here, ycs := (y1, 92..... Vo-1). 1). During inference, translation is generated by sampling token at a time from the distribution PLM (ys Meci, x). adjusted by a temperature, т. The (adjusted) probability of generating a particular token yis given the preceding tokens V<i and the input x is defined
PIM(U: = oly<i,
PLM, (yi = v)) Evey (LM 2'),
Lower temperature values 7 make the distribution more deterministic, favoring the most probable tokens, whereas higher values make the distribution flatter, approximating a uniform distribution.
However, multiple works have scrutinized the reliability of model likelihood
measure for
translation quality (Ott et al., 2018 Stahlberg and Byme 2019 Fikema and Aziz 2020) Freitag et al. 2022a Eikema 2024). Instead of solely relying on the likelihood, these works advocate using automatic translation quality metric as a utility function for minimum Bayes risk (MBR) decoding or reranking based on QE metrics. This shift not only improves the selection of translations but also facilitates the exploration of the underlying distribution learned by the models. However, it is crucial acknowledge that the overall translation quality is still contingent on the quality of the candidate pool. We next discuss common automatic metrics used for assessing translation quality.
2.2 Automatic Metrics for Machine Translation
Automatic quality assessment of machine-gencee generated translations has received considerable attention recently, resulting in metrics that attain high correlations with human judgment of translation quality (Freitag al. 2022b 2023b). These automatic metrics meant to assess the quality of translation across multiple dimensions (e.g. fluency, adequacy) and can provide reliable feedback when human judgments are unavailable. Among these metrics, neural learned metrics that are trained on human translation quality assessment scores or error span annotations have gained significant traction (Rei
al. 2022
Yan al. 2023 Guerreiro et al. 2023a Perrella et al. 2022).
For aligning automatically generated translations with human quality preferences, many works have proposed to use automatic metrics
alternative to human feedback during MT training (Shen ct al. 2016, Wieting et al. 2219)] He et al. 2024 Xu et al.] (024b) or decoding Shen et al. (2004); Fernandes et al. (022b); Freitag et al. (2022a 2023a). Freitag et al. (222a) show the efficacy of using reference-based neural metrics as utility functions for MBR decoding over lexical alternatives. Further, Fernandes al. (2022a) use QE metries like COMET-QU to select 1-best M-best translations from a pool of candidate hypotheses. Their analysis shows that while these automatic metrics can be useful, they might not always reflect human preferences accurately. Additionally, extra care has be taken when optimizing systems for these metrics, as the improvements might be attributable to overfitting "gaming the metric", rather than being genuine improvements in translation quality. Nevertheless, these metrics encode useful information about the quality of translations and can still be useful to obtain high-quality translations.
3 An MCMC-based Decoding Approach for Text Generation
Given that we have access to an automatic metric that quantifies how desirable a particular translation is, we aim address the following questions:
Can we sample directly in proportion to their corresponding quality values? Can we use automatic metrics that already give reliable estimate of human- human-perceivee perceived quality to achieve that? Finally, can we use this process to obtain diverse high-quality samples?
To answer these questions and to address the limitations of quality- -warr decoders, we propose to take an alternative approach, quality-aware sampling, which ensures high quality and diversity. Recognizing that naturally occurring texts can have numerous valid translations (Nidal 1964 Dreyer and Marcu, 2012, Out al. 2018, Mayhew et al.] 2020), the ability to generate diverse translation hypotheses paramount.
3

---

To this end, we first present background on MestinollisHaatinns in Section 3.1 Section 3.2 discusses our proposal distribution. Finally, we connect our approach to reinforcement learning with human feedback (RLHF) in Section 3.3
3.1
Netrrpolis-Hastinng
The problem of sampling translation hypotheses in proportion to a metric, r(z, can be framed as sampling from the following Gibbs distribution:
(v.
<o(y|=)
Zz(Ø) exp
(3)
8
where 2z(z) Ey exp r(g.x) and 3 is the temperature of the Gibbs distribution. We denote the corresponding unnormalized density by Tz(y)z), which unlike (x can be evaluated for any (z, y).
While several algorithms have been proposed to sample approximately from such intractable distribu- tions (Miao et al., 2018 Berglund et al. 2013 Amini et al. 2023). we resort to Netropolis-Hastimme (Metropolis et al., 1953 MH) due to its simplicity and flexibility in handling wide range of pro- posal distributions. The MH algorithm generates a sequence of samples from a target distribution, here ())r) by constructing a Markov chain (v²: "y"...... ;....;.. .y²) that has x ( ()) as its equilibrium distribution. It starts from arbitrary hypothesis yº. In the th iteration, it draws new hypothesis from a proposal distribution q(vly', 2)) This hypothesis is accepted with an acceptance probability ag(y. v²) [0, 1] given by:
as(v.v') = min {1. Ts (wlx) (y y.
min To (v'lz) (ylv'
If the candidate is accepted, the next state in the chain becomes y = y: if rejected, the chain stays at y/+1 = y¹ The process repeats for some number of steps T and in the end returns the hypothesis y² Note that, while computing the likelihood T (x) of particular hypothesis under the Gibbs distribution intractable (due to the intractable partition function (z)),,, evaluating the acceptance criterion (3 y²) is easy, because it depends only the likelihood ratio, in which the normalization constants cancel out, i.e.:
[
* ()
exp (r(U..) (v/
(5)
3
MH converges to the unique stationary distribution (z(y)z), regardless of the initial distribu- tion we start with, the transition distribution of the Markov chain, i.e., p(y"ly/ 1,,) =
"(v'ly'-1, [y'" ,y" 1) satisfies the Markov chain ergodic theorem (Neal 2011).
This requires suitable proposal distribution 4(yly', 2)) which must be irreducible and aperiodic. To ensure irreducibility, the proposal distribution should have sufficient support, such that it is possible to transition from any state any other state with nonzero probability Aperiodicity ensures that the Markov chain does not get stuck in cyclic behavior, where it keeps returning to the same states in a fixed pattern. Additionally, due to the acceptance criterion defined in Eq. the transition distribution satisfies the detailed balance condition:
finite number of steps.
Ta (y|z) p (u' lv, 2) = Ty (s' (z) p (z)
(6)
It is trivial to show that the chain has the target distribution, TT (y/(r) its stationary distribution:
Σ Myll/.2)TT(0 y'Ey
Note that MH can work with almost any proposal distribution. However, if the detailed balance conditions are far from holding, the acceptance probability will be low for transitions, making the convergence to the target distribution very slow and the approach impractical. Hence, choosing suitable proposal distribution for the task essential. We next describe our proposal distribution, q(vly', 2), which overcomes these limitations and satisfies the required constraints.

---

3.2 Proposal distribution
Previous works (Berglund al. 2013 Miao et al. 2018 Su et al. 2018) use proposal distributions that generate hypotheses with one-word or token-lever modifications. The different formulations in their most basic form propose a Markov chain which the state comprises the sentence y y and an index variable i E (O....; ") be changed, and a new token then sampled based on the following full conditional distribution:
At every step, an index is sampled that determines the token
#(yei, Vi, U>S)
q = ΣiEE #lys y/ F>1)
(8)
where V is created by considering the most likely tokens (k is generally large) under PLM (Ye Mes))
This procedure, however, has several limitations: first, it makes it difficult to handle more general combinatorial constraints, in our case more sophisticated metrics. As only explore adjacent positions in the sentence space due to small local changes, the Markov chain risks becoming trapped in infeasible states, necessitating very large number of steps T converge. Second, relying solely on token-level modifications makes it exceedingly difficult to generate plausible text, making impractical align generations with QE metrics general reward models. We show that this is indeed the case in Section 5.2
We instead propose simple and effective procedure that only requires generating single hypothesis from the model PLM and a single evaluation from the metric, r(y.z), and still allows the Markov chain converge to the target distribution. We characterize the proposal by the following procedure:
Given an instance yy with length nz' := |y"1, sample an index i, i ~ g(ilne)).
2. Generate a completion y2i from PLM .).
Note that, due to the nature of our proposal distribution, y² and share common substructure (prefix) before the index i, i.e., v = Vec.. which implies that
avvly' Mll xr PIM x) II 80u)
jKi
where ر1y uf) is the Kronecker delta function, which assigns zero probability prefix tokens which are different from yle, and probability one tokens matching the prefix.
The complete proposal when we include the index distribution q(ilnn), which depends on the previous sentence lengths n² := 1,'1. is given as
gly, ily', .) u(ilnn) (iiln"))rmii (PM Wee II JCL
[1g wz).
(10)
We will use the uniform distribution as the in- dex distribution, i.e., q(iln') 1/n't for each i E [n²],, unless otherwise stated. Algorithm describes the complete sampling process.
Algorithm Quality-Awan Metropolis- Hastings (QUEST) Sampling
1: Input: 2. PLM. r, T
2: Hyperparameters: т, Iturning |
This proposal is both irreducible and aperiodic there is non-zero probability of going from
3: Sample initial response yo ~ PLM(- x))
4: ++
a particular sentence to any other sentence and we can generate any text
5: for to T do
6: Sample index q(ippe-1)
back. When from the language model, which, when using ancestral sampling, implies that we can sample any possible sequence. As our approach only re- quires access to the token-level log probabilities and the ability to generate good continuations given prefix, can also used with closed
7: Sample Yor ~ PLM ( (-11'te ,2)
8:
+ (v 922)
9: Compute a3 11 through Eq.
Sample a uniformly in [0, 1]
11:
if a ag - then
+++ y
LLMs through an API as long as the it provides access to the sample likelihoods. However, we limit our experiments to open-source models due to the incurred cost and lack of training details about these black-box models.
13:
1+t+l end
15: end for
return f
5

---

3.3 Connections to Reinforcement Learning with Human Feedback
Reinforcement Learning with Human Feedback (RLHF) leverages human feedback to guide the learning process of complex NLP tasks (Stiennon et al. [022 Fernandes et al. [203]] Kaufmann et al. 2023). The process is as follows. Given language model, one generates hypotheses y J given an input prompt and gathers human feedback about which outputs are preferable. This preference data then used to train proxy reward model ry x). Finally, reinforcement learning (RI.) methods are used to optimize the original LM with respect to the reward model, following
ro v) B
max (yll)()
DKL [)(())) || (LM()/=)]
(11)
Many works show that the optimal solution the KL-constrained reward maximization objective
takes the form (Peters and Schaal 2007 Peng et al. 2019 Korbak et al. 2022b a Go et al. 2023):
1
r(y, x) B
Ty/ax
(LM(U)a) exp
(12)
Zz(x)
where Zz(x)= EUeyPLM(UV exp [/ distribution, this density can be represented Gibbs distribution with the corresponding reward
While we cannot sample autoregressively from this
function F(x, y) = log logPLM(()z r(aa))
Instead of the target distribution expressed in Eq. 3 we could define the above distribution as our target when using QUEST to sample from it, avoiding optimizing the objective in Eq. direecly. If we formulate the acceptance criterion using this target density and our proposal distribution introduced we obtaín the following:
Eq. 10
r (r(y.))
- (r (1),xx))
ao(y,y") min
exp
exp
(13)
3
The full derivation is in Appendix A
Using this approach, we can align language model generations
without access to the model weights, log probabilities, or RL. We provide a preliminary experimental comparison using the two target distributions (Eq. 3land Eq. 12) using QUEST in Appendix C.4
4 Experimental Settings
Data and Evaluation We test our approach on the WMT23 test sets (Kocmi al. 2023 covering four language pairs, ENGLISH ++ (GERMAN, RUSSIAN).
We evaluate the quality and the diversity of the generated texts follows. Suppose y is the set of hypotheses generated for the source text x with reference hypothesis y" and ((r, y², )))
represents the evaluation set. We compute the mean quality over each set of hypotheses using XCOMET-XL (Guerreiro et al.
2023a) as [D] ((arr))) DJ' > yey SCOMET-XL(E) v,y"). Simi-
larly, measure the mean diversity using the average pairwise BLEU (Papineni et al. 2002 Shen
ct al. 2019) as 1 D ((x.y"))))
D) - (y..")e su. wžy" BLEU
Models
We use TOWER- 7B Alves et al. 2024
2) and ALMA-
7B (Xu et al. 2024a AoLoaanuAAAMA--- two strong decoder-only MT models based on LLAMA2- 7B (Touvron et al.) 2023) as these models achieve competitive translation quality with GPT-4 and productized models like Google Translate. Unlike ALMA-7B, TOWER-78 uses bilingual MT data as well as datasets from MT-related tasks during training. Prompts are shown in Appendix B
Automatic Metries for QUEST We use COMETKIWI-XL (Rei al. 2023), a reference-free QE model built on top of XLM-R XI. (Goyal et al. 2021) and trained to predict human-rated direct assessments (Grhamm et al. 2013). This metric showed the highest correlations with human judgments on the QE Shared Task organized by the eighth conference on Machine Translation (WMT 2023) Blain et al. (2023). We transform the normalized scores from the QE model into z-scores using logit transformation with clamping applied to mitigate overflow.

---

TOWER EN-RU
TOWER RU-EN
TOWER EN
TOWER DE-EN
04.0
530
08.5
40.5
08
120
615
Arcestial
t10
Ancestral QUEST
Ancesdal
Ancesval QUEST
925
QUEST
051
Lnuical Divers
50
Leoical Diveriiy
Loviaal Doviallieeniyy Divendyy
53 Lookal (iverdyy
AL MA EN-RU
Al MA RU-EN
ALMA EN-OE
ALMA DE-EN
04
Arcenttal QUEST
Arcentral QUEST
Arcentral QUEST
Arcentral QUEST
15
75
65 Lokcol Divors by
70
55 Diveriity
65
Diversty
Diverity
Figure 2: Average quality vs. diversity on WMT23 datasets. Different points represent different hyperparameter values. QUEST outperforms ancestral sampling in six out of eight settings.
Decoding Configurations For ancestral sampling, we consider temperature values 7 between 0.2 and 1.0, with an equally spaced interval of 0.1. For generations with QUEST, we sample from the proposal distribution using - 0.8 and vary the parameter / of the target Gibbs distribution from the following range of values {0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1.0). The number of ancestral samples and decoding steps are both set to 128. We use VLLM (Kwon et al. 2023), a high-throughput and memory-efficient inference engine for generating outputs.
Compute Comparison:
Ancestral Vs QUEST We the number of output tokens metric to compare the different approaches. For the sake of simplicity, let us assume that the output sentence has fixed size of N. On average, QUEST in T steps generates (ي= + +) (T+1)N tokens, N tokens for the initial hypothesis, and then on average NNd tokens for the remaining T steps in the chain. If we contrast against sampling 7 sentences using ancestral sampling, we decode T x N tokens. This suggests that for an equal number of samples generated using ancestral sampling and QUEST, the latter results in about (T+1) = 2 times as many tokens, on average. Note, however, that the computational cost of QUEST is higher than ancestral sampling, as the hypotheses are generated sequentially and evaluated at every step. We run our experiments on NVIDIA RTX A6000 GPUs. Each ancestral sampling and QUEST for run with T = 128 takes, on average. I hour and 6 hours, respectively, for 2000 unique source texts on a single GPU. The compute bottleneck for QUEST also arises from using a large QE metric, potentially distilling this metric into smaller models could help reduce the compute time. We leave this to future work.
22'
5 Results
5.1
Main Findings
The main results of our experiments are presented in Figure 2
QUEST results in better translation quality-diverst models, the samples generated by QUEST tend to have better or similar quality than ancestral sampling as measured by XCOMET-XL A QUEST does not directly use the reference-based metric, XCOMET-XL, we reduce the chance of overfitting to the metric and thus the gains represent the ability of QUEST to improve translation quality more realistically. We also report Comet-22 vs diversity results in the Appendix Figure 9 the trends remain the same. The benefits of the proposed approach are more noticeable when translating from English (EN - (DE, RU)). Specifically, for EN < Ru, our model improves XCOMET-XL. by up to 2 points for both language models, showing the efficacy of QUEST over ancestral sampling.
trade-offs. Across language directions and
'We provide results four additional language pairs in Appendix C.6
7

---

EN-RU
10000
Method
Ansestral
0.06
Accepted
Unique accopoed
0.04
0.05.5
Count
0-003
6000
B-022
0.02
0.00
100
Average number accepted samples
2000
(c) Distribution # of accepted samples: high / results in higher acceptance rates.
10
20
30
40
Comparison proposal distributions
Overlap
Token-LLeel Uniform
2.0
Tokeen-Level Gibbs
(a) Sample Overlap between ancestral and QUEST.
Quest
Average Reward Path MA EN-RU
Densiyy
B 0.05
CometKial
8-0.1
0.2
0.
A-1 1
0.5
0.3
0.5
0.4
(rly'x) (yyx))
(d) Reward differences between an initial hypoth- esis and proposal hypotheses given the initial hy- pothesis.
(b) Average quality over MCMC steps and number of ancestral samples t.
Although ancestral exhibits better quality than QUEST for DE-EN, further analysis suggests that this discrepancy may stem from the constraints of the QE metric used to model the translation preferences. Notably, QUEST demonstrates significantly higher COMETKIWI-XX scores across the board (see Appendix Figure 7 suggesting that better and more robust QE models can result in improved transla- tion quality Furthermore, WMT23 DE-EN includes short passages that might require additional steps to reach the high-density regions. Based on a length analysis (See Appendix C.2) observe that the quality of QUEST lags behind ancestral sampling, specifically for longer sentences. We leave the exploration of finding optimal steps for convergence and adapting the proposal distribution for document-level MT to future work.
5.2 Ablation Analysis
We present further analysis some properties of our proposed approach using WMT23 EN-RU datasets with translations generated using ALMA-7B.
QUEST generates less-likely high-quality samples. We compute the set overlap for QUEST and ancestral samples (T = 128) with an independent draw of 512 ancestral samples to investigate whether approach results in hypotheses from unexplored regions (Fig. 3a). Compared to ancestral, QUEST results in hypotheses that are not found in the larger pool (4x) of ancestral samples as illustrated by higher mass the overlap value of 0. This demonstrates that QUEST effectively gets to regions of the output manifold that would be less likely sampled by the L. and still attain, on average, better quality and diversity.
Average reward improves over decoding steps. Figure 3b shows the average reward with in- creasing decoding steps and the sample size for QUEST and ancestral respectively. As ancestral results in independent samples, the mean reward estimate remains unchanged for different sample sizes. However, for QUEST, hypotheses regions, closer to the target density, resulting in increased average reward with more steps. We can also observe that the standard deviation of the reward over all samples decreases with the increasing number of steps, suggesting that the model eventually reaches better target distribution.
gradually sampled in the direction of higher-quality
Kocmi et al. 2024) report that difference of 2.7 COMETKIWI-X -L average is statistically significant with 98.9% accuracy. QUEST improvements always greater than this value across the board.

---

High 3 value results in higher acceptance rates. Figure 3c shows the distribution of accepted samples when varying 3, considering all (blue) versus unique (red) accepted samples. As expected, on average, the number of accepted samples is smaller than the number of steps T depending upon the rejection rate-low 8 values lead to higher rejection rates. Furthermore, within the accepted samples, we also observe many repeats. This can be attributed to the observation that the language model has a low entropy distribution for continuations when the sample indices lie at the end of sentences. Moreover, for probable sentences, only a few have high reward, which could result in the Markov chain getting stuck in a particular state. Increasing the temperature of the LM or adjusting the index distribution to have less density in the last few tokens could potentially reduce the number of repeats. We leave this exploration to future work.
Our sentence-level proposal generates better candidates. For a random example sampled from the WMT23 dataset, we generate 25k hypotheses using three proposal distributions: a) token-level modification with uniform probability b) token-level modification with full posterior presented in Eq. 8 and c) our sentence-level proposal (Eq, 10 and calculate the reward differences between the original (y) and the generated hypothesis (y' rly x) r(y, xr). Figure 3d shows its distribution: for proposals (a) and (b), the reward for the generated hypotheses is almost always lower than the initial translation. On the other hand, our proposal results in assigning half of the probability mass to
hypotheses that improve over y, leading to faster convergence over token-level alternatives.
Related Work
Sampling from Intractable Gibbs distributions. Several methods have been proposed to sample approximately from Gibbs distributions in text generation using autoregressive and musked-languuge models. Prior works (Miao et al.) 2018 Zhang et al. (2020) use MH with proposal distribution that makes token-level modifications for constrained generation tasks. Since masked language models (MLM) do not have straightforward mechanism for sampling text, MCMC has been widely explored using variations of Gibbs sampling (Berglund et al. 2015) Su et al. 2018 Wang and Cho 2019) Yamakoshi et al. 2022). However, Gooyal et al. (2022) shows that the masked conditional distributions from MLMs result in invalid Gibbs samplers and, therefore, proposes to use MH on the masked conditionals, resulting in higher-quality text. MMrrehggaalah et al. (2022); Forristal et al. (2023) build
on this work and use MLMs for sampling from Gibbs distributions. Some works (Kumar et al. 2022
Qin et al. 2022 Amini al. 2023 Du et al. 2023) also adapt the Hamiltonian MCMC algorithms originally designed for high- digh-dimensional continuous distributions for the discrete scenario (Duane al., 1987, Neal, 2011). Furthermore, Hu et al. (2024) apply GFlowNetss (Bengio et al., (2021) )
to fine-tune language models for solving posterior inference problems, which can be considered as sampling in proportion to an intractable Gibbs distribution. In our work, we instead aim to use MCMC for MT to sample translations in proportion to a sentence-level evaluation metric.
Diverse Decoding for Machine Translation. Variants of beam search (Cho 2016 Vijayakumar
et al. 2017; Kulikov et al., 2019 Tam 2020) have been proposed to produce a diverse set of translations using Seveesity-promoooe
objectives. However, the increased computation cost with the model size and beam width makes it infeasible and impractical to use with LLMs and it fails to yield consistent improvement over ancestral with an increase in beam width (Stahlberg and Byrne 2019 Eikema and Aziz 2020 Pang et al., 2024). Quality-aware decoding approaches on the other hand are almost always used to generate single best hypothesis. Concurrently, Dinnai et al. (2024) add diversity promoting objective to MBR decoding to generate a set of high-quality diverse candidates. However, their approach only allows for the selection of hypotheses from a predefined set. We further diverse translations are side product of
note that we do not directly promote efficiently exploring multiple high-quality regions from the model's 's distribution.
7 Conclusion
We propose new decoding approach for MT. Quality-Aware Metropolis- Hastings (QUEST) sampling based on MCMC that enables the generation of hypotheses in proportion to an automatic QE metric. We present a simple and novel proposal distribution that satisfies the constraints imposed by the Metropolis-Hastinnn algorithm. Our experiments on four language directions and two strong decoder- only language models show the efficacy of our approach over baselines. We further show that our

---

approach results in samples from underexplored high-density regions and that the average quality continues to improve as the Markov chain size increases.
Limitations and Broad Impact
QUEST requires generating many samples to reach for each input prompt, which can computationally expensive for time-critical applications. Addi- tionally, the required number of steps may vary depending on the input and the quality of the initial hypothesis. Furthermore, our proposal distribution only modifies the sentence suffix, which becomes restrictive once the chain reaches a high-quality region. As at this point, only minor changes to the hypothesis are accepted, slowing the mixing process. Addressing these limitations and extending this approach to other NLP tasks are avenues for future work.
regions sequentially from an LLM
Furthermore, we leverage recent advances in QE methods for MT and integrate them directly in the generation process of LLMs, which can potentially reduce the emrors generated by these systems. However, despite the high correlations of evaluation metries with human judgments, they are sometimes hard to interpret and occasionally fail to detect simple mistakes such as incorrect translations of numbers or entities (Amrhein and Sennrich], 2022). In such cases, sampling from the Gibbs distributions induced by these metrics might increase the chances of sampling those erroncous translations. We believe these risks will be mitigated as better metrics are constantly being developed-ove method, being agnostic to the specific quality metric, will directly benefit from it. In addition, since QUEST supports any Gibbs distribution, it can also incorporate multiple QE models or additional checks which can rule out problematic samples by assigning them very low QE score.
Acknowledgments
We thank Ben Peters, Marcos Treviso, and Sergey Troshin for their helpful and constructive feedback on the initial versions of the paper. Part of this work supported by the EU's Horizon Europe Research and Innovation Actions (UTTER, contract 101070631), by the project DECOLLAGE (ERC-2022-Ca) 2022-CoG 101088763), by the Portuguese Recovery and Resilience Plan through project C645008882- 00000055 (Center for Responsible AI), and by Fundação para a Ciência e Tecnologia through contract UIDB/50008/2000.
References
Duarte M. Alves, José Pombal, Nuno M. Guerreiro, Pedro H. Martins, João Alves, Amin Farajian, Ben Peters, Ricardo Rei, Patrick Fernandes, Sweta Agrawal, Pierre Colombo, José G. C. de Souza, and André F. T. Martins. 2024. reelated tasks!
Tower: An open multilingual large language model for translation
Afra Amini, Li Du, and Ryan Cotterell. 2023. Structured voronoi sampling
Chantal Amrhein and Rico Sennrich. 2022. Identifying weaknesses in machine translation metrics through minimum Bayes risk decoding: A case study for COMET In Proceedings of the 2nd Conference of the Aaca-Pe Chapter of the Association for Computational Linguistics and the 12th International Joint Conference Natural Language Processing (Volume 1: Long Papers), pages 1125-1141, Online only. Association for Computational Linguistics.
Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. 2021. Flow network based generative models for non-iterative diverse candidate generation
Mathias Berglund, Tapani Raiko, Mikko Honkala, Leo Kärkkäänen, Akos Vetek, and Juha Karhunen. 2015. Bidirectional recurrent neural networks as generative models reconstructing gaps time series
Frederic Blain, Chrysoula Zerva, Ricardo Rei, Nuno M. Guerreiro, Diptesh Kanojia, José G. C. de Souza, Beatriz Silva, Tânia Vaz, Yan Jingxuan, Fatemeh Azadi, Constantin Orasan, and André Martins. 2023. Findings of the WMT 2023 shared task on quality estimation In Proceedings of the Eighth Conference on Machine Translation, pages 629-653, Singapore. Association for Computational Linguistics.
10

---

Kyunghyun Cho. 2016. Noisy parallel approximate decoding for conditional recurrent language model, arXiv preprint 1rXvv.660..0885.
Markus Dreyer and Daniel Marcu. 2012. Hyter: Meaning-equivalent semanties for translation evalua- tion. In Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, pages 162-171.
Li Du, Afra Amini, Lucas Torroba Hennigen, Xinyan Velocity Yu, Jason Eisner, Holden Lee, and Ryan Cotterell. 2023. Principled gradient-based markov chain monte carlo for text generation
Simon Duane, A.D. Kennedy, Brian J. Pendleton, and Duncan Roweth. 1987. Hybrid monte carlo Physics Letters B, 195(2):216-222.
Bryan Eikema. 2024. The effect of generalisation the inadequacy of the mode, In Proceedings of the 1st Workshop on Uncertainty- NLP (UncertaiNLP 2024), pages 87-92, St Julians, Malta. Association for Computational Linguistics.
Bryan Eikema and Wilker Aziz. 2020.
Is MAP decoding all you need? the inadequacy of the In Proceedings of the 28th International Conference on Computational Linguistics, pages 4506 4520, Barcelona, Spain (Online). International Committee on Computational Linguistics.
mode in neural machine translation
António Farinhas, José de Souza, and Andre Martins. 2023. An empirical study of translation
hypothesis ensembling with large language models] In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 1 11956-11970, Singapore. Association for Computational Linguisties.
Patrick Fernandes, António Farinhas, Ricardo Rei, José G. C. de Souza, Perez Ogayo, Graham Neubig, and Andre Martins. 2022a. Quality-aware decoding for neural machine translation In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 1396-1412, Seattle, United States. Association for Computational Linguisties.
Patrick Fernandes, António Farinhas, Ricardo Rei, José G. C. de Souza, Perez Ogayo, Graham Neubig, and André F. T. Martins. 2022b. Quality-aware decoding for neural machine translation.
Patrick Fernandes, Aman Madaan, Emmy Liu, António Farinhas, Pedro Henrique Martins, Amanda Bertsch, José G. C. de Souza, Shuyan Zhou, Tongshuang Wu, Graham Neubig, and André F, T. Martins, 2023. BBridging the Gap: A Survey on Integrating (Human) Feedback for Natural Language Generation Transactions of the Association for Computational Linguistics, 11:1643-1665
Jarad Forristal, Niloofar Mireshghallah, Greg Durrett, and Taylor Berg- King-Kiikaatrick.. 2023. A block metropolis-hastingg sampler for controllable energy-based text generation
Markus Freitag, Behrooz Ghorbani, and Patrick Fernandes. 2023a. Epsilon sampling rocks: Investi-
gating sampling strategies for minimum Bayes risk decoding for machine translation In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 9198-9209, Singapore. Association for Computational Linguistics.
Markus Freitag, David Grangier, Qijun Tan, and Bowen Liang. 2022a. High quality rather than high model probability: Minimum Bayes risk decoding with neural metries Transactions of the Association for Computational Linguistics, 10:811-825.
Markus Freitag, Nitika Mathur, Chi-kiu Lo, Eleftherios Avramidis, Ricardo Rei, Brian Thompson, Tom Kocmi, Frederic Blain, Daniel Deutsch, Craig Stewart, Chrysoula Zerva, Sheila Castilho, Alon Lavie, and George Foster. 2023b. Results of WMT23 metrics shared task: Metrics might be guilty but references are not innocent In Proceedings of the Eighth Conference on Machine Translation, pages 578 628, Singapore. Association for Computational Linguistics.
Markus Freitag, Ricardo Rei, Nitika Mathur, Chi-kiu Lo, Craig Stewart, Eleftherios Avramidis, Tom Koemi, George Foster, Alon Lavie, and André F. T. Martins. 2022b. Results of WMT22 metrics shared task: Stop using BLEU neural metrics are better and more robust) In Proceedings of the Seventh Conference on Machine Translation ( (WMT), pages 46-68, Abu Dhabi, United Arab Emirates (Hybrid), Association for Computational Linguistics.
11

---

Dongyoung Go, Tomasz Korbak, Germán Kruszewski, Jos Rozen, Nahyeon Ryu, and Mare Dymet- man. 2023. Aligning language models with preferences through I-divergence minimization
Kartik Goyal. Chris Dyer, and Taylor Barg-Kirkpatrick. 2022, Exposing the implicit energy networks behind masked language models via metropolis hastings
Naman Goyal, Jingfei Du, Myle Ott, Giri Anantharaman, and Alexis Conneau. 2021. Larger- transformers for multilingual masked language modeling, In Proceedings of the 6th Workshop on Representation Learning for NLP (RepLANLP-202I), pages 29-33, Online. Association for Computational Linguistics.
Yvette Graham, Timothy Baldwin, Alistair Moffat, and Justin Zobel. 2013. Continuous measurement Scaaes in human evaluation of machine translation] In Proceedings of the 7th Linguistic Annotation Workshop and Interoperability with Discourse, pages 33-41, Sofia, Bulgaria. Association for Computational Linguistics.
David R Grimm, Yu-Jin Lee, Katherine Hu, Longsha Liu, Omar Garcia, Karthik Balakrishnan, and Noel F Ayoub. 2024. The utility of chatgpt as a generative medical translator. European Archives of Ole-Rhino-Larryngolosy pages 1-5.
Nuno M. Guerreiro, Ricardo Rei, Daan van Stigt, Luisa Coheur, Pierre Colombo, and André F, T. Martins. 2023a. xcomet: Transparent machine translation evaluation through fine-grained error detection
Nuno Miguel Guerreiro, Duarte M Alves, Jonas Waldendorf, Barry Haddow, Alexandra Birch, Pierre Colombo, and André FT Martins. 2023b. Hallucinations in large multilingual translation models. Transactions of the Association for Computational Linguistics, 11.
Zhiwei He, Xing Wang, Wenxiang Jiao, Zhuosheng Zhang, Rui Wang, Shuming Shi, and Zhaopeng Tu. 2024. Improving machine translation with human feedback: An exploration of quality estimation as a reward model. arXiv preprint 24Xi:22401.12877
Amr Hendy, Mohamed Abdelrchim, Amr Sharaf, Vikas Raunak, Mohamed Gabr, Hitokazu Mat- sushita, Young Jin Kim, Mohamed Afify, and Hany Hassan Awadalla. 2023. How good are gpt models at machine translation? comprehensive evaluation. arXiv preprint arX1v:2302.092210.
Edward Hu, Moksh Jain, Eric Elmoznino, Younesse Kaddar, Guillaume Lajoie, Yoshua Bengio, and Nikolay Malkin. 2024. Amortizing intractable inference in large language models
Yuu Jinnai, Ukyo Honda, Tetsuro Morimura, and Peinan Zhang. 2024. Generating diverse and high-quality texts by minimum bayes risk decoding. arXiv preprint arXiv:2401.0500
Timo Kaufmann, Paul Weng, Viktor Bengs, and Eyke Hüllermeier. 2023. A survey of reinforcement learning from human feedback. arXiv preprint 4rX1v:2312.14925.
Elaine C Khoong, Eric Steinbrook, Cortlyn Brown, and Alicia Fernandez. 2019. Assessing the use of google translate for spanish and chinese translations of emergency department discharge instructions. JAMA internal medicine. 179(4):50--582
Tom Koemi, Eleftherios Avramidis, Rachel Bawden, Ondřej Bojar, Anton Dvorkovich, Christian Federmann, Mark Fishel, Markus Freitag, Thamme Gowda, Roman Grundkiewicz, Barry Haddow, Philipp Koehn, Benjamin Marie, Christof Monz, Makoto Morishita. Kenton Murray, Makoto Nagata, Toshiaki Nakazawa, Martin Popel, Maja Popović, and Mariya Shmatova. 2023. FFindings of the 2023 conference on machine translation (WMT23): LLMS are here but not quite there yet In Proceedings of the Eighth Conference on Machine Translation, pages 42, Singapore. Association for Computational Linguistics.
Tom Koemi, Vilém Zouhar, Christian Federmann, and Matt Post. 2024. Navigating the metrics maze: Reconciling score magnitudes and accuracies. arXiv preprint arXiv:2401.066 006660.
Philipp Koehn and Rebecca Knowles. 2017. Six challenges for neural machine translation In
Proceedings of the First Workshop on Neural Muchine Translation, pages 28-39, Vancouver. Association for Computational Linguistics.
12

---

Tomasz Korbak, Hady Elsahar, Germán Kruszewski, and Mare Dymetman. 2022a. On reinforcement learning and distribution matching for fine-tuning language models with no catastrophic forgetting
Tomasz Korbak. Ethan Perez, and Christopher L Buckley, 2022b. RI with kl penalties is better viewed as bayesian inference.
Ilia Kulikov, Alexander Miller, Kyunghyun Cho, and Jason Weston. 2019. Importance of search and evaluation strategies in neural dialogue modeling In Proceedings of the 12th International Confer- ence on Natural Language Generation, pages 76-87, Tokyo, Japan. Association for Computational Linguistics.
Sachin Kumar, Biswajit Paria, and Yulia Tsvetkov. 2022. Gradient-based constrained sampling from language models
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. 2023. Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles.
Stephen Mayhew, Klinton Bicknell, Chris Brust, Bill McDowell, Will Monroe, and Burr Settles. 2020. Simultaneous translation and paraphrase for language education In Proceedings of the Fourth Workshop on Neural Generation and Translation, pages 232-243, Online. Association for Computational Linguistics.
Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, and A. H. Teller. 1953. Equation of state calculations by fast computing machines Journal of Chemical Physics, 21:1087-
1092.
Ning Miao, Hao Zhou, Lili Mou, Rui Yan, and Lei Li. 2018. CGMH: constrained sentence generation by metropolis- caattoposssssstiinss sampling CoRR, abs/ fass//8111 1.0966...
Fatemehsadat Mireshghallah, Kartik Goyal, and Taylor Berg-Kirkpatrick. 2022. Mix and match Learning-free controllable text generationusing energy language models) In Proceedings of the 60th Annual Meeting of the Association for Computational Linguisties ( (Volume I: Long Papers), pages 401-415, Dublin, Ireland. Association for Computational Linguistics.
Radford M. Neal. 2011.
Probabilistic inference using markov chain monte carlo methods
Eugene Albert Nida. 1964. Toward a science of translating: with special reference to principles and procedures involved in Bible translating. Brill Archive.
Myle Ott, Michael Auli, David Grangier, and Mare' Aurelio Ranzato. 2018. Analyzing uncertainty in neural machine translation. In International Conference on Machine Learning, pages 3956-3965.
PMLR.
Jianhui Pang, Fanghua Ye, Longyue Wang, Dian Yu, Derek F Wong, Shuming Shi, and Zhaopeng Tu. 2024. Salute the classic: Revisiting challenges of machine translation in the age of large language models. arXiv preprint arXiv:2401.083355
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. Bleu: method for automatic evaluation of machine translation] In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pages 311-318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.
Xue Bin Peng, Aviral Kumar, Grace Zhang, and Sergey Levine. 2019. wdvintage-weiggted regression Simple and scalable off-policy reinforcement learning
Stefano Perrella, Lorenzo Proietti, Alessandro Scirè, Niccolò Campolungo, and Roberto Navigli. 2022. MaTESee Machine translation evaluation as sequence tagging problem In Proceedings of the Seventh Conference on Machine Translation ( (WMT), pages 569-577, Abu Dhabi, United Arab Emirates (Hybrid), Association for Computational Linguistics.
13

---

Ben Peters and André F. T. Martins. 2021. Smoothing and shrinking the sparse Seq2Seq search space In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages for Computational Linguisties.
Online. Association
Jan Peters and Stefan Schaal. 2007. Reinforcement learning by reward-weightn regression for opeerational space control In Proceedings of the 24th International Conference on Machine Learning, ICML '07, page 745-750, New York, NY, USA. Association for Computing Machinery.
Lianhui Qin, Sean Welleck, Daniel Khashabi, and Yejin Choi. 2022. Cold decoding: Energy-based constrained text generation with langevin dynamics
Alec Radford, Jeff Wu, Rewon Child, David I Luan, Dario Amodei, and Ilya Sutskever. 2019. Language models are unsupervised multitask learners
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhoo,, Wei Li, and Peter J Liu. 2020. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21:1-67.
Ricardo Rei, José G. C. de Souza, Duarte Alves, Chrysoola Zerva, Ana C Farinha, Taisiya Glushkova, Alon Lavie, Luisa Coheur, and André F. 'T. Martins. 2022. [OMET-22: Unbabel-IST 2022 isubmission for the metrics shared task] In Proceedings of the Seventh Conference on Machine Translation (WMT), pages 578-585, Abu Dhabi, United Arab Emirates (Hybrid), Association for Computational Linguistics.
Ricardo Rei, Nuno M. Guerreiro, JosÅ@ Pombal, Daan van Stigt, Marcos Treviso, Luisa Coheur, José G. C. de Souza, and André Martins. 2023. [Scaling up CometKiwi: Unbabel-IST 2023 submission for the quality estimation shared task In Proceedings of the Eighth Conference on Machine Translation, pages 841-848, Singapore. Association for Computational Linguistics.
Lucfa Valz-Valdivieso and Belén López-Arroyo. 2023. Google translate chatgpt: Can non- language professionals trust them for specialized translation? In International Conference Human- informed Translation and Interpreting Technology (HITTIT 2023), pages 97-107.
Libin Shen, Anoop Sarkar, and Franz Josef Och. 2004. Discriminative reranking for machine translation In Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics: HLT-NAACL 2004, pages 177-184, Boston, Massachusetts, USA. Association for Computational Linguistics.
Shiqi Shen, Yong Cheng, Zhongjun He, Wei He, Hua Wu, Maosong Sun, and Yang Liu, 2016. Minimum risk training for neural machine translation, In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Pupers), pages 1683-1692, Berlin, Germany. Association for Computational Linguisties.
Tianxiao Shen, Myle Ott, Michael Auli, and Mare' Aurelio Ranzato. 2019. Mixture models for diverse machine translation: Tricks of the trade. In International conference machine learning, pages 5719-5728. PMLR.
Yiqiu Shen, Laura Heacock, Jonathan Elias, Keith D Hentel, Beatriu Reig, George Shih, and Linda Moy. 2023. Chatgpt and other large language models are double-edged swords.
Prasann Singhal, Jiacheng Xu, Xi Ye, and Greg Durrett. 2023. Bel: Efficiently encoding lattices for reranking
Felix Stahlberg and Bill Byrne. 2019. On NMT search errors and model errors: Cat got your tongue? In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference Natural Language Processing (EMNLL-)JCNNPP), pages 3356-3362, Hong Kong, China. Association for Computational Linguistics.
Nisan Stiennon, Long Ouyang, Jeff Wu, Daniel M. Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul Christiano. 2020. Learning to summarize from human feedback. In NeurIPS.
14

---

Nisan Stiennon, Long Ouyang. Jeff Wu, Daniel M. Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford,
Dario Amodei, and Paul Christiano. 2022. Learning to summarize from human feedback
Jinyue Su, Jiacheng Xu, Xipeng Qiu, and Xuanjing Huang. 2018. Incorporating discriminator in
Sentence generation: a gibbs sampling method
Breena R Taira, Vanessa Kreger, Aristides Orue, and Lisa C Diamond. 2021. A pragmatic assessment of google translate for emergency department instructions. Journal of General Internal Medicine, 36(11):3361-3365
Yik-Cheung Tam. 2020. Cluster-based beam search for pointer-generator chatbot grounded by knowledge. Computer Speech & Language, 64:101094.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cris- tian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, llyaan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. 2023. Llama 2: Open foundation and fine-tuned chat models)
Giorgos Vernikos and Andrei Aapescu-Belis. 2024. Don't rank, combine! combining machine translation hypotheses using quality estimation. arXiv preprint arXiv:2401.06668.
Ashwin K Vijayakumar, Michael Cogswell, Ramprasaath R. Selvaraju, Qing Sun, Stefan Lee, David Crandall, and Dhruv Batra. 2017. Diverse beam search: Decoding diverse solutions from neural ssqquence models
Alex Wang and Kyunghyun Cho. 2019. BERT has a mouth, and it must speak: BERT as a markov random field language model] CoRR, 190.1992..4494
John Wieting, Taylor Berg- Kirg-Kirkpatrick, Kevin Gimpel, and Graham Neubig. 2019. Beyond BLEUniiiinng neural machine translation with semantic similarity In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4344 4355, Florence, Italy, Association for Computational Linguistics.
Haoran Xu, Young Jin Kim, Amr Sharaf, and Hany Hassan Awadalla. 2024a. A paradigm shift in machine translation: Boosting translation performance of large language models,
Haoran Xu, Amr Sharaf, Yunmo Chen, Weiting Tan, Lingfeng Shen, Benjamin Van Durme, Kenton Murray, and Young Jin Kim. 2024b. Contrastive preference optimization: Pushing the boundaries of IIm performance machine translation. arXiv preprint 4rXiv:2401.08-11
Takateru Yamakoshi, Thomas Griffiths, and Robert Hawkins. 2022. Probing BERT's 's priors with serial reproduction chains) In Findings of the Association for Computational Linguistics: ACL 2022, pages 3977-3992, Dublin, Ireland. Association for Computational Linguistics.
Yiming Yan, Tao Wang, Chengqi Zhao, Shujian Huang, Jiajun Chen, and Mingxuan Wang. 2023. BLEURT has universal translations: An analysis of automatic metrics by minimum risk training In Proceedings of the 6lst Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 5428-5443, Toronto, Canada. Association for Computational Linguistics.
Maosen Zhang, Nan Jiang, Lei Li, and Yexiang Xue. 2020. Language generation via combinatorial constraint satisfaction: A tree search enhanced Monte- approach In Findings of the Asxoci- ation for Computational Linguistics: EMNLP 2020, pages 1286-1295 Online. Association for Computational Linguistics.
15

---

A Connection to RLHF derivation
If we take the target distribution have the following form:
(((, y) B
ग. <y/2²)
2(x) PLM PLM (xlx))))) exp
(14)
then the likelihood ratio becomes:
<v) (1(x, 1) r(,,y")
PLA (VZi Iu PLAS (u 2: 2:)
exp
(15)
π (v x))
Note that the target log ratio contains the inverse of the probability of returning, iee.
q y. x.
(16)
, x. (yM.
this allows simplifying the criterion follows:
a'((.vV") = min {
(r( r (2r (2)
g((]m)
1, exp
(17)
B
((in)))
B Prompts used for MT
For both the ALMA-7B 7B and TOWER- 7B we adhere to the prompt format recommended for transla- tion the original papers shown below:
ALMA-7B:
Translate this sentence from (source language) (target language). (source language) Source: (source sentence).
(target language) Translation:
TOWER-7B
<| </insstar\/user
Translate the following (source_language) source text to [target_ languae:
Loourcee_anguagee [source_sente )eenteeeeetecee (target_ 
 <|im_start/>assisee
Additional Results
C.1
Toy problem: Validating the Approach
To validate that our approach works, we test QUEST on a controlled setting, a toy summarization problem, where the ground truth reward is known. We consider the following reward function:
r(z, y) logit (clamp (N (lvl:= 7.5, o² 3.75?)))
(18)
where clamp(z) = max 1002 (ni 1))
We use GPT2 (Radford et al. (211)) fine-tuned on the Reddit dataset Stiennon et al. (0200) to generate summaries for 128 examples randomly sampled from the test split. We compare the distribution of rewards obtained by different sampling techniques (Ancestral, QUEST and Truncated (runcate-GGibb)) to the ground truth reward in Figure 4al For Truncated-Gibe Gibbs sampling, we estimate the partition function using the ancestral samples and resample them based on the probability distribution induced by the rewards. Unlike ancestral sampling which results in samples that are far from the high-reward regions, our sampling strategy, QUEST, results in the best approximation of the ground truth distribution. This simplified reward task serves as an useful example to show the efficacy of our approach over alternatives.
16

---

Distribution of Rewards
Exact Gibbs
Ancestral
0.10
Quest
Truncated-Gibbs
0.08
Frequency
0.06
0.04
0.00
20
40
60
80
100
Reward
(a) Distribution of rewards for sampled hypotheses for the toy summarization problem.
ALMA EN-DE
Accepted Indices ALMA EN-RU
3166
momc (5-6
0.8
Ancestral (c 0.3)
2.5
69
2.0
0.6
24
Densty
1.5
0-05
==0.1
$ 0.2
1.0
0.1
0.5
0.0
0:50
50-100
100-150
150-200
200-250
2504
8.0
1.0
Sentence size
normalized index
(a) XCOMET-XL by source length.
Distribution Accepted indices.
C.2 MCMC results in better outputs for shorter segments.
We show the XCOMET-XL XL scores WMT23 English- Gerimnn pairs bucketed by the length of the source text. In general, the quality of samples degrades with increased source length when decoding via MCMC shown in Figure 5a One possible factor could be the uniform index- selection exploration strategy where the proposal might require more steps as the sentence length increases. Another factor could be the limitations of the reward function itself for selecting high- quality translations for longer sequences. As these quality estimation metrics have not been trained longer sequences, due distribution shift, they might not be representative of true quality for these output lengths. We believe the latter option could be the more significant factor as the reward optimized still improves regardless of the sentence length (see Figure 7).
C.3 Accepted proposals are skewed towards the end of the sentence.
Figure 5b llsttrats how the distribution of accepted indices changes with decreasing 3: lower / values tighten acceptance criteria, favoring states with higher rewards and greater likelihood of returning to the previous state. Consequently, transitions tend to yield minor alterations, typically at end of the sentence. Altering the beginning necessitates sampling small indices values, risking complete sentence change. This plot highlights the current limitations of our proposal, especially the downstream implications on the diversity of prefixes we get for particular motivating the use of parallel chains and potential avenues for improvement for future work.
17

---

C.4
Comparing RLHF-QUEST vs QUEST
We compare QUEST with the alternative discussed in Section 3.3 where the target distribution in Eq. is replaced with Eq. 12 referred to
We compare sampling using the two target Our results indicate that both approaches result comparable translation quality, with QUEST resulting in slightly higher diversity on average than RI.H-QUEES.. We leave the detailed exploration of these two methods to future work.
distributions Figure 6
QUEST VS QUEST-RLHF
QUEST QUEST-RLHF
78
90
76
xCometXi
88
CometKiwiXi
72
86
70
84
68
Ancestral
Ancestral
82
QUEST
66
QUEST
QUEST-RLHF
64
QUEST-RLHF
50
55
60
65
70
75
80
50
55
60
65
70
75
80
Lexical Diversity
Lexical Diversity
Figure 6: Average Quality by XCOMET-XL (left) and COMETKIWI-XL on English-Russian dataset
using TOWER-7B
C.5 QE Results
We report the quality measured by the metric used in sampling, iee., COMETKIWI-XL in Figure QUEST results in higher quality across the board compared to ancestral sampling.
C.6 Additional Language Pairs
We further expanded our evaluation to four additional language pairs, shown in Figure WMT23 Boglish-Chinese (EN-ZZH high-resource), WMT23 English-Czech (EN (EN->CS, medium-rcsource)) WMT22 English-Icelandic (EN->1S) and Icelandic-Engliss (IS EN, low-resource), using ALMA-7B. We did not include TOWER in these experiments because it was trained on the WMT22 test sets. Across all language pairs, QUEST consistently outperforms ancestral sampling, providing better quality-diversity trade-offs.
C.7 C0MET22 Results
We report the quality measured by COMET22 (Rei et al., 2022) in Figure QUEST results in higher quality across the board compared to ancestral sampling.
18

---

TOWER EN-RU
TOWER RU-EN
78
75
76
CometKivi.XX XL
74
CometKiwiix XL
73
72
72
70
88
Ancestral
Ancestral
QUEST
x
QUEST
66
70
50
55
80
70
75
45
50
55
65
Lexical Diversity
Lexical Diversity
TOWER EN-DE
TOWER DE-EN
71
70
CometKiwi XL
CometKKwi-x WW
70
69
88
88
64
Ancestral
Ancestral
67
x
QUEST
QUEST
35
55
60
45
60
Lexical Diversity
Lexical Diversity
ALMA EN-RU
ALMA RU-EN
78
74
CometKiwi.X XL
72
CometKiwi.y XL
72
70
71
88
70
86
89
68
62
Ancestral
Ancestral QUEST
QUEST
67
60
86
50
55
60
65
Lexical Diversity
Lexical Diversity
ALMA EN-DE
ALMA DE-EN
86
70
69
CometKlwi XL
82
CometKlwi-XI
86
80
66
56
85
Ancestral
Ancestral
QUEST
64
QUEST
54
45
50
55
60
65
70
75
80
40
45
50
55
60
65
70
Lexical Diversity
Lexical Diversity
Figure 7: Average quality (LL vs. diversity (BURWISE-BLEU) on WMT23 datasets. Different points represent different hyperparameter values.
19

---

ALMA EN-15
ALMA IS-EN
05
80
90
XComet-Xi
75
xComet-XL
89
70
86
65
84
60
QUEST Ancestral
82
QUEST
55
Ancestral
30
40
50
60
70
80
20
30
40
50
60
70
Lexical Diversity
Lexical Diversity
ALMA EN-CS
ALMA EN-ZH
90
00
XComet-XL
80
XComet-XL
-5
75
70
65
QUEST
QUEST
Ancestral
Ancestral
10
20
30
50
60
70
80
30
50
60
70
80
90
Lexical Diversity
Lexical Diversity
Figure& 8: Average quality XL) vs. diversity (PAIRWISE-BLEE on additional LPs from WMT23 and WMT22, Different points represent different hyperparameter values.
WMT23 ALMA EN-RU
WMT23 AL AL RU-EN
0.84
0.820
0.83
0.815
Comet22
0.82
Comet22
0.810
0.81
0.805
0.80
0.800
0.79
QUEST
0.795
QUEST
Ancestral
Ancestral
0.78
0.790
0.55
0.60 0.65 0.70 0.75
0.80
0.50
0.55 0.60 0.65 0.70
0.75
Lexical Diversity
Lexical Diversity
WMT23 TOWER EN-RU
WMT23 TOWER RU-EN
0.830
0.855
0.828
0.850
0.826
Comet22
0.845
Comet22
0.824
0.840
0.822
0.835
0.820
0.830
QUEST Ancestral
0.818
QUEST
0.825
Ancestral
0.816
0.50
0.55
0.60
0.65
0.70
0.45
0.50
0.55
0.60
0.65
Lexical Diversity
Lexical Diversity
Figure 9: Average quality (COMET22) vs. diversity (PAIRWISE-BLEUU) on RU and RU-EN. Different points represent different hyperparameter values.
20

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We present the main contributions and results in the last two paragraphs the
appendix which supported by experiments detailed in Section 4 and findings presented in Section 3.2
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We present some the limitations of our work in the ablation analysis presented in Section 5.2 additionally, we list other limitations in Section g
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
21

---

Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide all necessary details to reproduce the experiments in Section 4
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
22

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: use publicly available models and datasets in our experiments. We release the code to replicate our experiments at httthtps//ww// www.wdecosssiing....mmmmo .om/
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (httpss//nips.. cc/
bublic/guides//CoeeSuuuu Stw.ooddeeoummssssoooooolooo for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (ht htte:///uidee/oeeeuubiiii www.moolissooooooooooooocc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See Section Our proposed method works at inference time. We report the test data used and all the hyperparameters in the beginning of Section in dedicated paragraphs.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We show all results aggregated over sample size of 500-2000 source sentences across multiple language pairs and models. Furthermore, we report statistical significance for results using the optimized QE metric in Section and Appendix C.5
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
23

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We discuss the compute used and run time in dedicated paragraph in Section
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
Our research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Please refer Section
g
Guidelines:
The answer NA means that there is no societal impact of the work performed.

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work poses no such risks. We utilize existing models and resources to improve translation quality.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We provide all details with citations for the WMT23 dataset and the models (ALMA-7b, Tower-7b) in dedicated paragraphs in Section
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
25

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paaper thcode. cww/cooo////oooooo coomdatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We release the code at htttts::www..uussreecooi.......
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
We do not conduct any human study.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do conduct any human study.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
26

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "MXGN9D2V4E", "reviewer": "Reviewer_L9No", "summary": "This essay proposes one method to solve the challenge of balancing the generation quality and diversity of machine translation.  This essay proposes this problem of sampling a set of high-quality and diverse translations. It is said that this proposed method can lead to high-quality and diverse outputs.", "questions": "-- The motivation of balancing the quality and diversity of machine translation is good but difficult. In fact, the quality of machine translation is good. So, can we induce that your method aims to improve the diversity of mt, which seems not very promising.\n-- In your method, you will sample from a set of high-quality and diverse translations. Where do these translations come? What is the retrieval set? Or How to generate them?\n-- It will be better if there is one main figure to illustrate your method.\n-- The formula is good and makes sense. However, adding more examples will be more clear.\n-- The evaluation metrics of QUEST seem not very popular.\n--If you can provide more results of other common datasets, it will be convincing.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The methodology and formula of this essay are detailed and makes sense.", "weaknesses": "Same with questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. \n\n> “In fact, the quality of machine translation is good. So, can we induce that your method aims to improve the diversity of mt, which seems not very promising.” \n\n\nThe goal of our paper is to maintain or improve MT quality while increasing the diversity of the generated translations. We believe that this is an important problem which has been overlooked in the literature. Naturally occurring texts have many possible valid translations (L112-113) and in many practical scenarios, providing alternative translations can improve communication and user experience [1] or can even be combined in parts to potentially generate even better translation hypotheses [2]. Existing methods either sacrifice quality to achieve diversity or aim only at high-quality translations that are not diverse. Our proposed method achieves both.   \nWe show an example in Figure 1 for a commonly used method, ancestral sampling. As shown in Figure 1, increasing the temperature for ancestral sampling results in diverse but overall lower quality pool of samples. On the other hand, our approach (QUEST) improves both the quality and diversity over ancestral samples in six out of eight settings, by incorporating a reward signal in the generation process.\nWe hope this alleviates your concern. \n\n\n > “In your method, you will sample from a set of high-quality and diverse translations. Where do these translations come? What is the retrieval set? Or How to generate them?” \n\n\nThis is explained in  lines 125-132 and lines 165-169 in Section 3, where we give full details about how and where these high quality diverse translations come from. There is no retrieval involved. \nWe recap here what our procedure is (also stated as Algorithm 1 in the paper):\n\n **1.** Sample an initial translation from the model using ancestral sampling (e.g. y_1 = The cat sits on the mat)\n\n **2.** Select a position in the candidate (e.g. 4)\n\n **3.** Regenerate continuation from the LLM starting that position (e.g. y_2 = The cat sits **behind the sofa**)\n\n **4.** Score both y_1 and y_2 using an automatic metric (s_1 and s_2) and extract their likelihoods (l_1 and l_2).\n\n **5.** Compute the ratio in  equation 4; if alpha > some threshold, the new hypothesis is y_2 else it is y_1.\n\n **6.** Repeat steps 2-5 for k iterations.\n\nAt the end of k iterations, we get x (<k) number of high-quality diverse translations. \nWe hope this clarifies. \n\n > “It will be better if there is one main figure to illustrate your method.” \n\nThis is a good suggestion. We will add a figure in the paper illustrating the procedure above, to provide more intuition about how our method works. \n\n > The evaluation metrics of QUEST seem not very popular. If you can provide more results of other common datasets, it will be convincing.\n\n\nWe respectfully disagree with the claim that the evaluation metrics are not “popular” and the datasets are not “common”. We use the most recent WMT23 datasets for our evaluation, as well as state-of-the-art metrics (xCOMET-XL), which obtained the highest correlations with human judgments in WMT metrics shared task 2023 (see [3]). These datasets and metrics to the best of our knowledge are the most recent and best methods for evaluating machine translation. \nNevertheless, we also provide COMET22 vs diversity plots in the attached pdf (Figure 2). As you can see, the trends remain the same. We will add these plots to the final version as an appendix. \n\n\n[1] Ge Gao, Bin Xu, David C. Hau, Zheng Yao, Dan Cosley, and Susan R. Fussell. 2015. Two is Better Than One: Improving Multilingual Collaboration by Giving Two Machine Translation Outputs. In Proceedings of the 18th ACM Conference on Computer Supported Cooperative Work &amp; Social Computing (CSCW '15). Association for Computing Machinery, New York, NY, USA, 852–863. https://doi.org/10.1145/2675133.2675197\n\n[2] Giorgos Vernikos and Andrei Popescu-Belis. Don't Rank, Combine! Combining Machine Translation Hypotheses Using Quality Estimation. arXiv preprint arXiv:2401.06688 (2024).\n\n[3] Results of WMT23 Metrics Shared Task: Metrics Might Be Guilty but References Are Not Innocent (Freitag et al., WMT 2023)", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "n0IE0YrsD1", "reviewer": "Reviewer_Pz9P", "summary": "This paper presents a novel approach called QUEST Sampling, designed to generate high-quality and diverse translations in machine translation. The authors proposed methods to obtain high-quality and diverse parallel data and provide an effective way to avoid over-reliance on noisy quality estimates by using them as the energy function of a Gibbs distribution.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors propose QUEST sampling, which addresses a significant issue in machine translation: the bias that arises when reranking by a quality-estimated model. This bias occurs because both the sampling and evaluation processes use the same metric.", "weaknesses": "1. The authors may consider expanding their experiments to include a wider range of language pairs beyond just German and Russian.\n\n2. Since the sampling is still based on the quality-estimated model, there remains a risk of \"gaming the metric.\" It would be beneficial for the authors to include human evaluations to validate their results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the constructive feedback and insightful comments.\n\n > “The authors may consider expanding their experiments to include a wider range of language pairs beyond just German and Russian.”\n\nWe agree that expanding the evaluation to more language pairs will strengthen our paper further.  In the original submisison, we tested on 4 language directions (EN-DE, DE-EN, EN-RU and RU-EN) using two strong decoder-only MT models (ALMA and Tower).  We now followed your suggestion and extended the evaluation to four new language pairs (please see Figure 1 in the attached pdf). This includes English-Chinese (high-resource), English-Czech (medium resource), English-Icelandic and Icelandic-English (low-resource). We observe that QUEST still results in a slightly better quality-diversity tradeoffs compared to ancestral sampling for beta values corresponding to the medium diversity regime. In the very high diversity regime, the results of QUEST degrade -- we posit that this is because CometKiwi-XL cannot provide a reliable indication of translation quality for very diverse samples, as it was not trained to predict human quality assessments for these language pairs. Improving the reward model should further improve the quality of translations generated by our method, as suggested by the experiments in EN-DE, DE-EN, EN-RU and RU-EN. We will add a discussion to comment on these new results. \n\n > “Since the sampling is still based on the quality-estimated model, there remains a risk of \"gaming the metric.\" It would be beneficial for the authors to include human evaluations to validate their results.”\n\nWe emphasize that our method, QUEST, is designed to decrease this risk compared to existing methods in the following ways:\n\n **1.** Unlike popular reranking approaches, we do not use the metric directly to select the hypothesis, instead we sample from the distribution induced by the reward model.\n\n **2.** We are not aiming to generate one best hypothesis that might overexploit metric biases but rather a pool of translations which are sampled from the high-quality (according to reward) regions of the underlying model.  By doing this, we try to ensure that the translations are not narrowly tailored to specific metrics but are generally robust and of high quality.\n\nHowever, we acknowledge that this risk still exists: for example, Figure 4 in the appendix shows that the gains obtained in the metric optimized for (reference-less CometKiwi-XL) are much larger. Yet, these gains are also validated via translation quality improvements when measured in the reference-based evaluation metric, XCOMET-XL. We do agree that human evaluation would provide further validation of our claims. However, these would require annotating large sets of translation hypotheses for each source sentence,  which is extremely costly and could not fit our  budget and time constraints.", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ob7BsgrkLN", "reviewer": "Reviewer_DVBo", "summary": "This paper proposes a novel approach called Quality-Aware Metropolis-Hastings (QUEST) Sampling, using a proposal distribution that is compatible with sentence-level metrics. The authors conducted experiments in the machine translation task with four directions En <> {Ru, De} and employed multiple decoder-only LLMs (Tower-7B and ALMA-7B). The experimental results show that the proposed approach leads to high-quality and diverse outputs.\n\nThis paper is well organized with focused contributions. The proposed approach could be applied to text generation tasks, though experiments are carried out in machine translation tasks. It is unclear how this approach is robust in low-resource directions or longer sequence text generation. Further discussion would be helpful to understand prros/cons of the proposed approach.", "questions": "- Since LLMs can handle longer text sequences, discussion on how to extend this idea to document-level metrics would be interesting. What kind of challenges would lie? From Section 5.1, QUEST might struggle more as sentence gets longer?\n- Do you think if this proposed approach works well with a small amount of data? \n- This approach might work well with high-resource data. How do you overcome in case of data scarcity?\n- Are those tested translation tasks considered high-resource? How robust does this approach in low-resource directions?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- well-organized paper with focused contributions\n- technically sound in most cases, except De->En direction. Experimental results show the efficiency of QUEST.", "weaknesses": "- this is not a major concern though this work is limited to sentence-level metrics. Since LLMs can handle longer text sequences, discussion on how to extend this idea to document-level metrics would be interesting.\n- This approach might work well with high-resource data. How do you overcome in case of data scarcity?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> “Since LLMs can handle longer text sequences, discussion on how to extend this idea to document-level metrics would be interesting. What kind of challenges would lie? From Section 5.1, QUEST might struggle more as sentence gets longer?”\n\nThis is a very good question. Please note that, in Appendix Section C.3, we analyzed how our method performs on short passages present in WMT23 English-German dataset (corresponding to L269) and hypothesized that QUEST could benefit from more document tailored proposal distributions (e.g. sampling an entire sentence) or a larger number of iterations. We also note the limitation of existing sentence level metrics in providing reliable assessment on such texts. We agree and appreciate the suggestion on using document level metrics (for eg SLiDE [1]) for handling longer text translations in future work. We will also add this discussion in the paper. \n\n[1] SLIDE: Reference-free Evaluation for Machine Translation using a Sliding Document Window (Raunak et al., NAACL 2024).\n\n > “Do you think if this proposed approach works well with a small amount of data? This approach might work well with high-resource data. How do you overcome in case of data scarcity? Are those tested translation tasks considered high-resource? How robust does this approach in low-resource directions?”\n\nOur proposed method is an inference-only strategy independent of the quantity of the data for the language pair being evaluated. It only depends upon two factors 1) The underlying LLM should be able to generate a reasonable set of hypotheses (good and bad quality) and 2) the reward metric should be able to provide a reliable indication of quality.  Recent work has shown that LLMs like ALMA are capable of generating reasonable quality translations for low-resource language pairs with small number of parallel data (~10k) albeit not to the extent of higher-resource language pairs like English-German or English-Russian. \n\nTo address your question, we ran new experiments in four more language pairs, including a low-resource setting of English-Icelandic and Icelandic-English. We evaluate our method against ancestral with CometKiwi-XL. The results are shown in Figure 1 in the attached pdf. We find that QUEST can provide a slightly better quality-diversity tradeoffs than ancestral even in this low-resource scenario. However, this does not happen for all values of beta for QUEST. We hypothesize that this could be because COMETKiwi-XL might not be a good reward model for this setting. While the underlying pretrained model that supports CometKiwi-XL is trained on Icelandic, CometKiwi-XL is not trained on any human assessment for English-Icelandic language pair which might impact the quality of judgments generated for this language pair for diverse translations. So, a reward model trained on human assessments for the specific language pair should yield better results.", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pqFBNPDYUr", "reviewer": "Reviewer_SYtr", "summary": "This paper proposes novel quality-aware sampling for neural machine translation, namely Quality-Aware Metropolis-Hastings Sampling. The main idea is that sampling from a model in proportion to a metric can be seen as sampling from a Gibbs distribution, and Metropolis-Hastings MCMC algorithm can be used for this purpose. Empirical results on 4 WMT language pairs show that QUEST can generate diverse high-quality set of hypothesis compared to the ancestral sampling.", "questions": "- While average quality and diversity can be higher than for ancestral sampling, does it result in the general higher quality of the MT?\n- Figure 1: `Different points represent different hyperparameter values`: I am not sure I understand to what hyperparameters this refers to. Are they the same across al plots?\n- Line 247-248: `Note, however, that the computational cost of QUEST is higher than ancestral sampling` - do you know the rough speed ratio between those two?", "limitations": "N/A, Limitations are addressed in section 8", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Paper is well-written and easy to follow\n- Novel idea for sampling a set of high-quality, diverse hypothesis rather than re-ranking using quality metrics\n- Comparison with the ancestral sampling shows the usefulness of the proposed method", "weaknesses": "- While you have a comparison on the sampling quality/diversity, I would also be interested in the performance of the translation model on common translation metrics.\n\n(Please note here that I consider all weaknesses to be minor)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive and insightful comments. We address your questions below:\n\n > “While you have a comparison on the sampling quality/diversity, I would also be interested in the performance of the translation model on common translation metrics.”\n\nThis is a good suggestion. We report additional machine translation metrics in Figure 2  in the attached pdf (although our choice of xCOMET-based metrics in our submission is justified by the fact that they were found to be higher correlated with human judgments of translation quality, over COMET22 and BLEURT,  in WMT23 Metrics Shared Task Campaign). We observe that the trends are mostly similar to xCOMET-XL, which further validate our claims.\n\n > “Figure 1: Different points represent different hyperparameter values: I am not sure I understand to what hyperparameters this refers to. Are they the same across al plots?”\n\nFor ancestral, these refers to different temperature values and for QUEST, different beta values. \n\n > “Line 247-248: Note, however, that the computational cost of QUEST is higher than ancestral sampling - do you know the rough speed ratio between those two?”\n\nYou are right and we acknowledge this in L249: for 2000 source texts, QUEST can be 6x slower.\n\n > “While average quality and diversity can be higher than for ancestral sampling, does it result in the general higher quality of the MT?”\n\nWe report the best-of-n translations (using reference-based xCOMET-XL) for the 128 candidates generated using ancestral and QUEST in Figure 3 in the attached PDF. The overall quality of translations is better for ancestral and QUEST for EN-ZH and EN-CS, respectively.  Our current results show that the best-of-n according to an automatic metric is not always higher for QUEST.", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their constructive and helpful feedback. We have attached a pdf to support additional experiments performed during the rebuttal period.

We are glad that the reviewers found our approach to be novel (SYtr), the paper well-written and well-organized (SYtr, DVBo, L9No) and the method technically sound (DVBo).

We believe the revisions will significantly improve the quality and clarity of our paper. We will release the code to facilitate the reproducibility of our results on acceptance. If we have succeeded in responding to your comments, kindly consider raising the scores. We are happy to address any more questions you might have.



Thank you,

Authors

Meta-review: This paper proposes QUEST (Quality-Aware Metropolis-Hastings) Sampling, a novel approach for generating diverse and high-quality machine translations. 

It uses evaluation metrics as the energy function of a Gibbs distribution to avoid over-reliance on noisy quality estimates; employs the Metropolis-Hastings algorithm to generate multiple samples from high-density areas; demonstrates quality-diversity trade-offs compared to ancestral sampling across multiple language pairs and models.

**Strengths:** Novel idea for sampling diverse, high-quality hypotheses rather than just reranking; technically sound approach with strong empirical results; addresses an important challenge in MT of balancing quality and diversity.

**Weaknesses:** Limited language pair evaluation in initial submission (addressed in rebuttal); lack of human evaluation to validate metric-based improvements; computational cost; potential struggles with longer sentences and low-resource settings.
Decision: Accept (poster)