QUEST: Quality-Aware Metropolis-Hastings Sampling for Machine Translation

Authors: r a gonçalo
  faria
sweta  agrawal
antónio  farinhas
ricardo  rei
josé g c de souza
andré f t martins
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 11:43:43

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).

Main paper: 
 introduction: 
 Machine translation (MT) is becoming increasingly more accurate and powerful, as 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 a serious issue when translating high-risk content, as in medical and legal domains (Khoong et al., 2019; Taira et al., 2021; Shen et al., 2023; Guerreiro et al., 2023b; Sanz-Valdivieso and López-Arroyo, 2023; Grimm et al., 2024) . Developing procedures for sampling higher-quality translations is therefore in high demand.It is 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, 2020; Peters and Martins, 2021; Eikema, 2024) ; and improving search often makes things worse (Koehn 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, a string of work has been initiated towards "quality-aware decoding", which leverages powerful quality estimation (QE) and evaluation metrics, such as COMET (Rei et al., 2022) or BLEURT (Yan et al., 2023) , to explore and rerank a broader range of candidate hypotheses generated via sampling from the model's distribution, selecting the best-1 (Freitag et al., 2022a; Fernandes et al., 2022b; Farinhas et al., 2023) or the best-k (Jinnai et al., 2024; Singhal et al., 2023) according to these learned metrics.Figure 1 : QUEST samples an index from the current translation (y t ), removes all elements to the right of the index, generates a new continuation, and then uses the Metropolis-Hastings acceptance criterion to decide whether to accept or reject the resulting new translation. The process continues for a fixed number of T iterations.Despite the benefits, reranking-based methods have their own drawbacks. There is a 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., 2022b) . 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 a very large pool size.One potential way to remedy these issues, which we explore in 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 a Gibbs distribution cannot be performed autoregressively, and it 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 a suitable proposal distribution. Our method, Quality-Aware Metropolis-Hastings (QUEST) Sampling, uses a novel proposal distribution that is compatible with sentencelevel evaluation metrics, common in text generation tasks like MT (Figure 1 ). 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 is 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}) 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 a larger pool size.2 2 Background 
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 x, which is a sequence of tokens (x 1 , x 2 , . . . , x L ) ∈ 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 ∈ Y, given the prompt x, can be factorized as the product of conditional probabilities over individual tokens (y 1 , y 2 , . . . , y N ), where each y i ∈ V. The probability of a particular translation y for a given input x can be written asp LM (y|x) = N i=1 p LM (y i |y <i , x).(1)Here, y <i := (y 1 , y 2 , . . . , y i-1 ). During inference, a translation is generated by sampling one token at a time from the distribution p LM (y i |y <i , x), adjusted by a temperature, τ . The (adjusted) probability of generating a particular token y i , given the preceding tokens y <i and the input x, is defined as:p LM,τ (y i = v|y <i , x) = p LM (y i = v|y <i , x) 1/τ v ′ ∈V p LM (y i = v ′ |y <i , x) 1/τ .(EQUATIONLower temperature values τ 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 as a measure for translation quality (Ott et al., 2018; Stahlberg and Byrne, 2019; Eikema and Aziz, 2020; Freitag et al., 2022a; Eikema, 2024) . Instead of solely relying on the likelihood, these works advocate using an 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 to 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.Automatic quality assessment of machine-generated translations has received considerable attention recently, resulting in metrics that attain high correlations with human judgment of translation quality (Freitag et al., 2022b (Freitag et al., , 2023b)) . These automatic metrics are meant to assess the quality of a 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 et al., 2022; Yan et 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 as an alternative to human feedback during MT training (Shen et al., 2016; Wieting et al., 2019; He et al., 2024; Xu et al., 2024b) or decoding Shen et al. (2004) ; Fernandes et al. (2022b) ; Freitag et al. (2022a Freitag et al. ( , 2023a)) . Freitag et al. (2022a) show the efficacy of using reference-based neural metrics as utility functions for MBR decoding over lexical alternatives. Further, Fernandes et al. (2022a) use QE metrics like COMET-QE to select 1-best or N-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 to be taken when optimizing systems for these metrics, as the improvements might be attributable to overfitting or "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. 
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 to address the following questions:Can we sample directly in proportion to their corresponding quality values? Can we use automatic metrics that already give us a reliable estimate of human-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-aware 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 (Nida, 1964; Dreyer and Marcu, 2012; Ott et al., 2018; Mayhew et al., 2020) , the ability to generate diverse translation hypotheses is paramount.To this end, we first present background on Metropolis-Hastings 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.The problem of sampling translation hypotheses in proportion to a metric, r(x, y), can be framed as sampling from the following Gibbs distribution:EQUATIONwhere Z β (x) = y exp r(y,x) β and β is the temperature of the Gibbs distribution. We denote the corresponding unnormalized density by πβ (y|x), which unlike Z β (x) can be evaluated for any (x, y).While several algorithms have been proposed to sample approximately from such intractable distributions (Miao et al., 2018; Berglund et al., 2015; Amini et al., 2023) , we resort to Metropolis-Hastings (Metropolis et al., 1953, MH) due to its simplicity and flexibility in handling a wide range of proposal distributions. The MH algorithm generates a sequence of samples from a target distribution, here π β (y|x), by constructing a Markov chain (y 0 , y 1 , . . . , y T ) that has π β (y|x) as its equilibrium distribution. It starts from an arbitrary hypothesis y 0 . In the t th iteration, it draws a new hypothesis y from a proposal distribution q(y|y t , x). This hypothesis is accepted with an acceptance probability α β (y, y t ) ∈ [0, 1] given by:EQUATIONIf the candidate y is accepted, the next state in the chain becomes y t+1 = y; if rejected, the chain stays at y t+1 = y t . The process repeats for some number of steps T and in the end it returns the hypothesis y T . Note that, while computing the likelihood π β (y|x) of a particular hypothesis y under the Gibbs distribution is intractable (due to the intractable partition function Z β (x)), evaluating the acceptance criterion α β (y, y t ) is easy, because it depends only on the likelihood ratio, in which the normalization constants cancel out, i.e.:EQUATIONMH converges to the unique stationary distribution π β (y|x), regardless of the initial distribution we start with, if the transition distribution of the Markov chain, i.e., p(y t |y t-1 , x) = q(y t |y t-1 , x)α(y t , y t-1 ) satisfies the Markov chain ergodic theorem (Neal, 2011) .This requires a suitable proposal distribution q(y|y t , x) 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 to any other state with a nonzero probability in a finite number of steps. Aperiodicity ensures that the Markov chain does not get stuck in a cyclic behavior, where it keeps returning to the same states in a fixed pattern. Additionally, due to the acceptance criterion defined in Eq. 4, the transition distribution satisfies the detailed balance condition:EQUATIONIt is trivial to show that the chain has the target distribution, π β (y|x) as its stationary distribution:EQUATIONNote 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 a suitable proposal distribution for the task is essential. We next describe our proposal distribution, q(y|y t , x), which overcomes these limitations and satisfies the required constraints.Previous works (Berglund et al., 2015; Miao et al., 2018; Su et al., 2018) use proposal distributions that generate hypotheses with one-word or token-level modifications. The different formulations in their most basic form propose a Markov chain in which the state comprises the sentence y t ∈ Y and an index variable i t ∈ {0, . . . , |y t-1 |}. At every step, an index is sampled that determines the token to be changed, and a new token is then sampled based on the following full conditional distribution:q(y i |y <i , y >i ) = π(y <i , y i , y >i )EQUATION)where V is created by considering the k most likely tokens (k is generally large) under p LM (y i |y <i ).This procedure, however, has several limitations: first, it makes it difficult to handle more general combinatorial constraints, in our case more sophisticated metrics. As we only explore adjacent positions in the sentence space due to small local changes, the Markov chain risks becoming trapped in infeasible states, necessitating a very large number of steps T to converge. Second, relying solely on token-level modifications makes it exceedingly difficult to generate plausible text, making it impractical to align generations with QE metrics or general reward models. We show that this is indeed the case in Section 5.2.We instead propose a simple and effective procedure that only requires generating a single hypothesis from the model p LM and a single evaluation from the metric, r(y, x), and still allows the Markov chain to converge to the target distribution. We characterize the proposal by the following procedure:1. Given an instance y t with length n t := |y t |, sample an index i, i ∼ q(i|n t ).2. Generate a completion y ≥i from p LM (y ≥i |y t <i , x).Note that, due to the nature of our proposal distribution, y t and y share a common substructure (prefix) before the index i, i.e., y t <i = y <i , which implies thatEQUATIONwhere δ(y j , y t j ) is the Kronecker delta function, which assigns zero probability to prefix tokens which are different from y t <i and probability one to tokens matching the prefix. The complete proposal when we include the index distribution q(i|n t ), which depends on the previous sentence lengths n t := |y t |, is given asEQUATIONAlgorithm 1 Quality-Aware Metropolis-Hastings (QUEST) Sampling1: Input: x, p LM , r, T 2: Hyperparameters: τ , t burning , β 3: Sample initial response y 0 ∼ p LM (• | x) 4: t ← 1 5: for 1 to T do 6: Sample index i ∼ q(i|n t-1 ) 7: Sample y ≥i ∼ p LM (•|y t-1 <i , x) 8: y ← (y t-1 <i , y ≥i ) 9:Compute α β (y, y t-1 ) through Eq. 410:Sample α uniformly in [0, 1] 11:if α ≤ α β (y, y t-1 ) then 12:y t ← y 13: t ← t + 1 14:end if 15: end for 16: return y tburning , . . . , y tWe will use the uniform distribution as the index distribution, i.e., q(i|n t ) = 1/n t for each i ∈ [n t ], unless otherwise stated. Algorithm 1 describes the complete sampling process. This proposal is both irreducible and aperiodic as there is a non-zero probability of going from a particular sentence to any other sentence and back. When i = 0, we can generate any text from the language model, which, when using ancestral sampling, implies that we can sample any possible sequence. As our approach only requires access to the token-level log probabilities and the ability to generate good continuations given a prefix, it can also be used with closed 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.Reinforcement Learning with Human Feedback (RLHF) leverages human feedback to guide the learning process of complex NLP tasks (Stiennon et al., 2022; Fernandes et al., 2023; Kaufmann et al., 2023) . The process is as follows. Given a language model, one generates hypotheses y ∈ Y given an input prompt x and gathers human feedback about which outputs are preferable. This preference data is then used to train a proxy reward model r ϕ (y, x). Finally, reinforcement learning (RL) methods are used to optimize the original LM with respect to the reward model, followingEQUATIONMany works show that the optimal solution to 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) :EQUATIONwhere Z β (x) = y∈Y p LM (y|x) exp r(x,y) β . While we cannot sample autoregressively from this distribution, this density can be represented as a Gibbs distribution with the corresponding reward function r(x, y) = log p LM (y|x) + r(x,y) β . 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. 11 directly. If we formulate the acceptance criterion using this target density and our proposal distribution introduced in Eq. 10, we obtain the following:EQUATION)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. 3 and Eq. 12) using QUEST in Appendix C.4. 
experimental settings: 
 Data and Evaluation We test our approach on the WMT23 test sets (Kocmi et al., 2023) covering four language pairs, ENGLISH ↔ {GERMAN, RUSSIAN}.We evaluate the quality and the diversity of the generated texts as follows. Suppose Ȳ is the set of hypotheses generated for the source text x with reference hypothesis y ⋆ and D = {(x, y ⋆ , Ȳ)} represents the evaluation set. We compute the mean quality over each set of hypotheses using XCOMET-XL (Guerreiro et al., 2023a) as1 |D| (x,y ⋆ , Ȳ)∈D 1 | Ȳ| y∈ Ȳ XCOMET-XL(x,y, y ⋆ ). Similarly, we measure the mean diversity using the average pairwise BLEU (Papineni et al., 2002; Shen et al., 2019) as 1 -1 |D| (x,y ⋆ , Ȳ)∈D 1 | Ȳ|(| Ȳ|-1) (y,y ′ )∈ Ȳ2 s.t. y̸ =y ′ BLEU(y, y ′ ). 3Models We use TOWER-7B (Alves et al., 2024, Unbabel/TowerInstruct-7B-v0.2) and ALMA-7B (Xu et al., 2024a , haoranxu/ALMA-7B), 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-7B uses bilingual MT data as well as datasets from MT-related tasks during training. Prompts are shown in Appendix B.Automatic Metrics for QUEST We use COMETKIWI-XL (Rei et al., 2023) , a reference-free QE model built on top of XLM-R XL (Goyal et al., 2021) and trained to predict human-rated direct assessments (Graham 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 a logit transformation with clamping applied to mitigate overflow. Decoding Configurations For ancestral sampling, we consider temperature values τ 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 use the number of output tokens as a metric to compare the different approaches. For the sake of simplicity, let us assume that the output sentence has a fixed size of N . On average, QUEST in T steps generates T -1 2 + 1 N = (T +1)N 2 tokens, N tokens for the initial hypothesis, and then on average N 2 tokens for the remaining T -1 steps in the chain. If we contrast against sampling T sentences using ancestral sampling, we decode T × N tokens. This suggests that for an equal number of samples generated using ancestral sampling and QUEST, the latter results in about 2T (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, 1 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. 
main findings: 
 The main results of our experiments are presented in Figure 2 .QUEST results in better translation quality-diversity trade-offs. Across language directions and models, the samples generated by QUEST tend to have better or similar quality than ancestral sampling as measured by XCOMET-XL. 4 As 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. (c) Distribution of # of accepted samples: high β results in higher acceptance rates.(d) Reward differences between an initial hypothesis and proposal hypotheses given the initial hypothesis.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-XL scores across the board (see Appendix Figure 7 ), suggesting that better and more robust QE models can result in improved translation quality.5 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), we 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.We present further analysis on 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 our approach results in hypotheses from unexplored regions (Fig. 3a ). Compared to ancestral, QUEST results in hypotheses that are not found in the larger pool (4×) of ancestral samples as illustrated by a higher mass at 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 LM and still attain, on average, better quality and diversity.Average reward improves over decoding steps. Figure 3b shows the average reward with increasing 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 are gradually sampled in the direction of higher-quality 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 a better target distribution.High β value results in higher acceptance rates. Figure 3c shows the distribution of accepted samples when varying β, 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 β 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 a 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 ′ ): r(y ′ , x) -r(y, x). 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 masked-language models. Prior works (Miao et al., 2018; Zhang et al., 2020) use MH with a proposal distribution that makes token-level modifications for constrained generation tasks. Since masked language models (MLM) do not have a 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, Goyal 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. Mireshghallah 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 et al., 2023; Du et al., 2023 ) also adapt the Hamiltonian MCMC algorithms originally designed for high-dimensional continuous distributions for the discrete scenario (Duane et al., 1987; Neal, 2011) . Furthermore, Hu et al. (2024) apply GFlowNets (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 diversity-promoting 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 a single best hypothesis. Concurrently, Jinnai 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 note that we do not directly promote diversity-rather, diverse translations are a side product of efficiently exploring multiple high-quality regions from the model's distribution.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: See Section 4. Our proposed method works at inference time. We report the test data used and all the hyperparameters in the beginning of Section 4 in dedicated paragraphs.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a 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, or as supplemental material. 
conclusion: 
 We propose a 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-Hastings algorithm. Our experiments on four language directions and two strong decoderonly 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.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: We show all our results aggregated over a 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 5 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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• 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 or 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 a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
limitations and broad impact: 
 QUEST requires generating many samples to reach high-density regions sequentially from an LLM for each input prompt, which can be computationally expensive for time-critical applications. Additionally, 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.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 errors generated by these systems. However, despite the high correlations of evaluation metrics 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 erroneous translations. We believe these risks will be mitigated as better metrics are constantly being developed-our 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 a very low QE score. C.2 MCMC results in better outputs for shorter segments.We show the XCOMET-XL scores on WMT23 English-German pairs bucketed by the length of the source text. In general, the quality of samples degrades with increased source length when decoding via MCMC as shown in Figure 5a . One possible factor could be the uniform indexselection 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 highquality translations for longer sequences. As these quality estimation metrics have not been trained on longer sequences, due to a 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 illustrates how the distribution of accepted indices changes with decreasing β: lower β values tighten acceptance criteria, favoring states with higher rewards and a greater likelihood of returning to the previous state. Consequently, transitions tend to yield minor alterations, typically at the end of the sentence. Altering the beginning necessitates sampling small indices values, risking a complete sentence change. This plot highlights the current limitations of our proposal, especially the downstream implications on the diversity of prefixes we get for a particular motivating the use of parallel chains and potential avenues for improvement for future work.Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: We discuss the compute used and run time in a dedicated paragraph in Section 4.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the 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 (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: Our research conforms with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 to Section 8.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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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 as 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a 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. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?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 4.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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 creators. 
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 https://www.questdecoding.com/.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was 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. 
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 to 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS 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. 
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 not conduct any human study.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• 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. 
 
 Appendix: We compare QUEST with the alternative discussed in Section 3.3 where the target distribution in Eq. 3 is replaced with Eq. 12, referred to as "RLHF-QUEST". We compare sampling using the two target distributions in Figure 6 . Our results indicate that both approaches result in comparable translation quality, with QUEST resulting in slightly higher diversity on average than RLHF-QUEST. We leave the detailed exploration of these two methods to future work.Figure 6 : Average Quality by XCOMET-XL (left) and COMETKIWI-XL on English-Russian dataset using TOWER-7BWe report the quality as measured by the metric used in sampling, i.e., COMETKIWI-XL in Figure 7 .QUEST results in higher quality across the board compared to ancestral sampling.We further expanded our evaluation to four additional language pairs, as shown in Figure 8 : WMT23 English-Chinese (EN→ZH, high-resource), WMT23 English-Czech (EN→CS, medium-resource), WMT22 English-Icelandic (EN→IS), and Icelandic-English (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.We report the quality as measured by COMET22 (Rei et al., 2022) in Figure 9 . QUEST results in higher quality across the board compared to ancestral sampling. Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We use publicly available models and datasets in our experiments. We release the code to replicate our experiments at https://www.questdecoding.com/.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.We release the code to replicate our experiments at https://www.questdecoding.com.https://github.com/mjpost/sacrebleu/tree/masterWe provide results on four additional language pairs in Appendix C.6.Kocmi et al. (2024) report that a difference of 2.7 COMETKIWI-XL on average is statistically significant with a 98.9% accuracy. QUEST improvements are always greater than this value across the board. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: Same with questions.
questions: 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.
-- 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?
-- It will be better if there is one main figure to illustrate your method.
-- The formula is good and makes sense. However, adding more examples will be more clear.
-- The evaluation metrics of QUEST seem not very popular.
--If you can provide more results of other common datasets, it will be convincing.
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The authors may consider expanding their experiments to include a wider range of language pairs beyond just German and Russian.

2. 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.
questions: questions: N/A
limitations: limitations: N/A
paper_summary: paper_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.

This 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.
strength_weakness: strength_weakness: - 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.
- This approach might work well with high-resource data. How do you overcome in case of data scarcity?
questions: 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?
- 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?
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

(Please note here that I consider all weaknesses to be minor)
questions: questions: - While average quality and diversity can be higher than for ancestral sampling, does it result in the general higher quality of the MT?
- 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?
- 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: limitations: N/A, Limitations are addressed in section 8

Comments: title: Thanks for response
comment: I thank the authors for their response. I keep my positive view and maintain my scores.
Thank you for your reply and providing additional results. After carefully reading rebuttal response and other reviewers comments, I decided to keep my score unchanged