PaperlayerView exact revision on arXiv

Source-linked AI summary

Epsilon Sampling Rocks: Investigating Sampling Strategies for Minimum Bayes Risk Decoding for Machine Translation

Markus Freitag, Behrooz Ghorbani, Patrick Fernandes

arXiv:2305.09860v2cs.CLcs.AIcs.LG

TL;DR

MBR decoding performance depends on how candidate translations are sampled, motivating comparisons of sampling strategies. The paper applies epsilon sampling to MBR and reports that, in human evaluations across four language pairs, it significantly outperforms beam search and MBR with the other tested sampling approaches.

  • Problem

    The paper examines how sampling strategies for generating MBR candidate lists affect decoding performance.

    Source: §1 · pp. 1–2

  • Method

    The authors compare ancestral, nucleus, and top-k sampling for MBR and explore epsilon sampling, which prunes tokens below a probability threshold.

    Source: §1 · pp. 1–2

  • Results

    Across four language pairs, human evaluations find that epsilon-sampling MBR significantly outperforms beam search and MBR with all other tested sampling approaches.

    Source: §1 · p. 2, §6 · p. 8

  • Takeaways & Limitations

    The findings identify epsilon sampling as promising for improving MBR quality and as a direction for generation tasks beyond MBR.

    Source: §6 · p. 8

    In the reported experiments, MBR required 1,024 samples per source sentence, and its utility-computation cost is generally quadratic in sample count, making the current approach expensive and impractical for most use cases.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Recent advances in machine translation (MT) have shown that Minimum Bayes Risk (MBR) decoding can be a powerful alternative to beam search decoding, especially when combined with neural-based utility functions. However, the performance of MBR decoding depends heavily on how and how many candidates are sampled from the model. In this paper, we explore how different sampling approaches for generating candidate lists for MBR decoding affect performance. We evaluate popular sampling approaches, such as ancestral, nucleus, and top-k sampling. Based on our insights into their limitations, we experiment with the recently proposed epsilon-sampling approach, which prunes away all tokens with a probability smaller than epsilon, ensuring that each token in a sample receives a fair probability mass. Through extensive human evaluations, we demonstrate that MBR decoding based on epsilon-sampling significantly outperforms not only beam search decoding, but also MBR decoding with all other tested sampling methods across four language pairs.

1 Introduction

The paper investigates how candidate-sampling strategies affect MBR decoding and introduces epsilon sampling as an alternative to conventional approaches. Human evaluations report that epsilon-based MBR outperforms beam search and the other tested sampling approaches across four language pairs.

1 Introduction

  • The paper positions MBR as a decision rule with potential to overcome some biases of beam search in neural machine translation.The introduction cites Eikema and Aziz (2020), Müller and Sennrich (2021), Eikema and Aziz (2021), Freitag et al. (2022a), and Fernandes et al. (2022).Source: §1 · p. 1
  • Prior work found that sampling-based MBR with neural metrics fine-tuned on human judgment can outperform beam search in expert human evaluation.Earlier work also proposed unbiased sampling to address shortcomings of MAP decoding.Source: §1 · p. 1
  • The study compares ancestral, nucleus, and k-best sampling for BLEURT-based MBR, then explores epsilon sampling and sampling temperature.Epsilon sampling prunes tokens below a probability threshold; the authors report that incorrect samples can hurt MBR, especially for long sequences.Source: §1 · pp. 1–2
  • Epsilon-sampling MBR significantly outperforms beam search and MBR with all other tested sampling approaches across four language pairs.The authors use extensive human evaluations to assess translation quality.Source: §1 · p. 2

2 Methods

The methods describe four ways to sample translation candidates and formulate MBR decoding as selecting a hypothesis by expected utility. Because the human-reference distribution is unknown and the output space is infinite, the method estimates expected utility using model samples.

2.1 Sampling Approaches

  • Ancestral sampling draws from the model distribution, while other strategies trim its tail because low-probability tokens are considered unreliable.Ancestral sampling is described as faithful to the model but sensitive to biases and errors in its estimated distribution.Source: §2.1 · p. 2
  • Top-k sampling restricts choices to the k highest-probability tokens, while nucleus sampling uses the smallest token set covering probability mass p.Nucleus sampling discards the remaining 1 − p fraction of tokens from the lower tail.Source: §2.1 · p. 2
  • Epsilon sampling prunes low-probability tokens, and the paper argues it can suit machine translation because outputs are conditioned on inputs with limited possible continuations.Hewitt et al. (2022) argue that epsilon sampling breaks the relative probability principle, particularly for open-ended generation.Source: §2.1 · pp. 2–3

2.2 Minimum Bayes Risk Decoding

  • MBR selects a hypothesis by expected utility against human references, but substitutes the model distribution and estimates the expectation with finite model-sampled pseudo-references.The substitution assumes the model approximates the true human-translation distribution.Source: §2.2 · p. 3
  • Using the same samples as candidates and pseudo-references improves the expected-utility approximation as the pool grows, but increases sampling and cross-utility costs.The paper notes that utility computation is generally quadratic in the number of samples.Source: §2.2 · p. 3

3 Experimental Setup

Experiments use English↔German and English↔Chinese translation models, with newstest2019 for checkpoint selection and newstest2021 for testing. The setup specifies model and decoding configurations and evaluates translation quality using document-context MQM.

3.1 Data and Model

  • Experiments cover English↔German and English↔Chinese, using filtered web-crawled training data and newstest2019 for development and newstest2021 for testing.The filtered training sets contain 625 million En↔De examples and 1.32 billion En↔Zh examples.Source: §3.1 · p. 3

3.2 Model

  • The translation models are 581M-parameter Transformers, and beam search uses beam size 4 with length penalty α=0.5.For MBR, the experiments generate 1,024 samples per source sentence and use BLEURT as the utility function.Source: §3.2 · pp. 3–4

3.3 Human Evaluation

  • Human evaluation measures translation quality with document-context MQM using the same error categories, severity levels, and weighting schema as the referenced setup.Major errors receive weight 5, minor errors 1, and minor punctuation errors 0.1; segment-level scores average annotator scores.Source: §3.3 · p. 4

4 Experimental Results

The experiments compare sampling strategies for MBR, analyzing their distributional behavior and selecting BLEURT-based settings before expert MQM evaluation. Across four language pairs, MBR with BLEURT beats beam search in MQM, and epsilon sampling at ϵ=0.02, τ=1.0 outperforms other MBR runs.

4.1 Distributional Properties of Sampling Approaches

  • Top-k’s fixed token count ignores confidence, while nucleus can retain many low-probability tokens; epsilon prunes below ϵ and varies both set size and retained mass.With 1,024 samples, epsilon covers greater cumulative sentence probability mass than the other approaches, possibly supporting more diverse translations and better utility estimates.Source: §4.1 · pp. 4–5

4.2 Hyperparameter Search

  • English→German served as the development pair: 1–2 settings per sampler were selected using BLEURT and reused unchanged across other language pairs.The final evaluation examined how BLEURT scores relate to human assessment as both utility and evaluation metric.Source: §4.2 · p. 5

4.2.1 Ancestral Sampling

  • Figure 5 shows lower temperature (τ) favors small candidate lists, where likely tokens matter, while higher temperatures perform better for larger lists; for large candidate sizes, the paper uses τ=1.0.Source: §4.2.1 · p. 5

4.2.2 Top-K Sampling

  • For large candidate lists, top-k settings had nearly identical quality; the study carried forward k=10 and k=50, both at τ=1.0.Source: §4.2.2 · p. 5

4.2.3 Nucleus Sampling

  • For 1,024 candidates, nucleus sampling with p=0.9 and τ=1.5 outperformed other tested settings; lower τ favored smaller lists.The authors selected p=0.9, τ=1.5 for final evaluation.Source: §4.2.3 · p. 6

4.2.4 Epsilon Sampling

  • For large lists, higher τ raised epsilon BLEURT; unlike traditional methods, epsilon looked promising at τ≥2, prompting comparison of τ=2 and 1 at ϵ=0.02.Traditional ancestral, top-k, and nucleus sampling showed sharp quality drops at very high temperatures.Source: §4.2.4 · p. 6

4.3 Final Evaluation

  • Higher τ often scored better on BLEURT but humans preferred τ=1, while BLEU favored beam search; the German→English human reference also contained many errors.The authors suggest high temperature might exploit weaknesses in the utility function.Source: §4.3 · pp. 6, 8
  • Across all four language pairs, MBR decoding with BLEURT outperforms beam search regardless of sampling approach, while MBR Epsilon (ϵ=0.02, τ=1.0) sampling outperforms all other MBR runs.Table 1 reports actual utility, log-likelihood (logP), and MQM scores for different MBR methods and beam search on newstest2021.Source: §4.3 · p. 6, Table 1 · p. 7

5 Related Work

Prior work applied MBR across several fields and renewed interest in it for machine translation, where sampling and neural utility metrics have been explored. Related studies also note potential weaknesses in neural metrics and propose other sampling strategies.

5 Related Work

  • MBR has been applied to parsing, speech recognition, word alignment, and machine translation, including overlap-metric optimization in statistical MT.The approach has also appeared in machine- and speech-translation shared-task submissions.Source: §5 · p. 8
  • Eikema and Aziz proposed unbiased sampling for MBR, reporting that model samples reflect training-data statistics more faithfully than beam search.Their sampling-based approximation is adopted in this paper’s experiments.Source: §5 · p. 8
  • Neural utility functions such as BLEURT and COMET have outperformed lexical overlap metrics, while MBR may exploit neural-metric biases toward faulty high-scoring translations.Alternatives to ancestral sampling have also been reported to improve MBR performance.Source: §5 · p. 8
  • Typical sampling prunes tokens whose probabilities deviate from model entropy, and its proponents report reduced degenerate repetitions and improved generation quality.It may prune both high- and low-probability tokens.Source: §5 · p. 8

6 Conclusion

The paper compares ancestral, nucleus, top-k, and epsilon sampling for MBR and reports expert human evaluations across four language pairs. Epsilon-based MBR significantly outperforms beam search and MBR with the other tested sampling approaches.

6 Conclusion

  • The study compared ancestral, nucleus, top-k, and epsilon sampling during MBR decoding, analyzing limitations of traditional sampling approaches.The authors suggest epsilon sampling may also be promising beyond MBR and for non-open-ended generation tasks.Source: §6 · p. 8
  • Across four language pairs, epsilon-sampling MBR significantly outperformed beam search and MBR with every other tested sampling approach.The authors identify epsilon-sampling as promising for improving MBR translation quality.Source: §6 · p. 8
  • Further human assessment is planned to test how smaller candidate lists affect MBR performance.The authors state this as future work.Source: §6 · p. 8

Limitations

The authors identify evaluation risks from metric overlap, limited human assessment, and MBR’s decoding cost. These constraints qualify how comprehensively translation quality can be assessed and how practical the method is.

Limitations

  • When evaluation metrics and the MBR utility function are the same or related, automatic scores may favor metric honey pots that are not necessarily high-quality translations.MBR is particularly susceptible because it selects translations with high metric scores.Source: Limitations · p. 9
  • Human assessment covered only a subset of translations because it is expensive and time-consuming, so unassessed translations may be higher quality than assessed ones.The authors say a final human assessment is necessary to address potential metric overfitting.Source: Limitations · p. 9
  • Experiments required 1024 samples per source sentence and hyperparameter setting, with utility computation generally quadratic in sample count, making current MBR expensive and impractical for most use cases.Sampling cost is linear in the candidate-set size.Source: Limitations · p. 9

Ethics Statement

The ethics statement describes annotator protections and test-set access.

Ethics Statement

  • Annotators were fairly compensated, could withhold personal information, and could label sensitive information; all test sets were publicly available.The authors report these conditions for the annotation process and study test sets.Source: Ethics Statement · p. 9

A Token-Level Probabilities

The section links major MQM error spans to tokens below the experiment’s 0.02 epsilon threshold. Epsilon-based MBR excludes the top-k- and nucleus-based translations associated with those errors.

A Token-Level Probabilities

  • All examined major error spans contained at least one token below 0.02, and the corresponding top-k or nucleus translations were absent from epsilon-based MBR’s candidate pool.In Example 3, the first token of each error span—Newly, professional, and .—was below 0.02.Source: A Token-Level Probabilities · pp. 11–12
  • The authors attribute epsilon-based MBR’s strong results mainly to the threshold guarding against translations with even one low-probability token.They describe the guard as requiring every token to have at least some decent probability mass from the model.Source: A Token-Level Probabilities · p. 11
  • In the illustrated German→English examples, epsilon-based MBR avoided the highlighted major errors, and its translations were error-free.The examples compare epsilon sampling with nucleus and top-k sampling.Source: A Token-Level Probabilities · p. 11, Table 2 · p. 12

Related papers

Loading 2305.09860v2…