Source-linked AI summary
If beam search is the answer, what was the question?
Clara Meister, Tim Vieira, Ryan Cotterell
TL;DR
Exact MAP decoding can produce low-quality neural text, while beam search often performs better despite substantial search error, motivating a different decoding objective. The paper frames beam search as exact decoding under a regularized objective linked to uniform information density, then tests UID-promoting objectives. In NMT experiments, surprisal variance strongly relates to BLEU, and the regularizers alleviate quality degradation from larger beam widths.
Problem
Exact MAP decoding frequently produces low-quality neural text, while beam search performs better despite its high search error, indicating that MAP alone does not capture desired text properties.
Method
The paper reverse-engineers a regularized decoding objective whose exact solution matches beam search and develops objectives that explicitly promote uniform information density.
Results
In NMT experiments, surprisal variance strongly relates to BLEU, while UID-promoting regularizers achieve beam-search-like performance and alleviate quality degradation at larger beam widths.
Takeaways & Limitations
Beam search can be interpreted as exact decoding with a UID-promoting inductive bias, helping explain its practical success for neural language generation.
Takeaways & Limitations
The empty-string failure rate decreases for larger models but can remain a considerable percentage, and formal guarantees apply only when greedy local optimality implies global optimality.
Abstract
from arXiv · showhide
Quite surprisingly, exact maximum a posteriori (MAP) decoding of neural language generators frequently leads to low-quality results. Rather, most state-of-the-art results on language generation tasks are attained using beam search despite its overwhelmingly high search error rate. This implies that the MAP objective alone does not express the properties we desire in text, which merits the question: if beam search is the answer, what was the question? We frame beam search as the exact solution to a different decoding objective in order to gain insights into why high probability under a model alone may not indicate adequacy. We find that beam search enforces uniform information density in text, a property motivated by cognitive science. We suggest a set of decoding objectives that explicitly enforce this property and find that exact decoding with these objectives alleviates the problems encountered when decoding poorly calibrated language generation models. Additionally, we analyze the text produced using various decoding strategies and see that, in our neural machine translation experiments, the extent to which this property is adhered to strongly correlates with BLEU.
1 Introduction
Beam search often outperforms exact decoding for neural text generation despite its high search error, suggesting that its success reflects a hidden inductive bias. The paper links this bias to uniform information density and tests regularized objectives that reproduce beam-search-like behavior.
- 1 Introduction: Exact search returns the empty string in > 50% of cases, whereas beam search often produces better text than exact search or very large beams.This indicates beam search’s success does not primarily come from approximating exact decoding.
- 1 Introduction: The paper reverse-engineers a regularized objective whose exact solution is equivalent to the solution found by beam search.The regularizer is interpreted through the uniform information density hypothesis.
- 1 Introduction: Uniform information density describes text that distributes surprisal evenly across a sentence, and the proposed beam-search regularizer encourages this property.Surprisal is defined as negative log-probability.
- 1 Introduction: A close relationship between surprisal standard deviation and BLEU suggests that higher-quality NMT text more strongly exhibits uniform information density.The experiments also find that regularized exact decoding achieves performance similar to beam search on standard NMT benchmarks.
- 1 Introduction: The proposed regularizers alleviate the text-quality degradation typically observed when decoding with larger beam sizes.The empty-string rate tends to decrease for larger models, although it can remain considerable.
2 Neural Probabilistic Text Generation
Neural text generation searches an exponentially large hypothesis space, making exact MAP decoding computationally difficult and motivating heuristic decoding. Beam search became standard, yet larger beams can worsen quality because neural models may favor short, generic outputs or even the empty string.
- Neural probabilistic text generation: Neural generators define distributions over exponentially many output hypotheses, making exhaustive decoding impractical.The full hypothesis space grows exponentially with vocabulary size, and exact recurrent-neural decoding is formally NP-hard.
- Beam search: Beam search is a pruned breadth-first heuristic that expands at most k hypotheses at each time step.It is widely used because neural models make full-space evaluation infeasible, despite lacking a formal guarantee of finding the highest-scoring candidate.
- Beam-search behavior: Increasing beam size beyond 5 can hurt BLEU and ROUGE, while beam search can still produce coherent, human-like text when the model’s global optimum is empty.The paper frames this counterintuitive performance pattern as a potential blessing rather than merely a curse.
- Alternative decoding objectives: Exact MAP decoding often produces short outputs dominated by high-frequency words, motivating length and coverage normalization.These methods modify the MAP objective with additive rewards or multiplicative factors during decoding.
- Alternative decoding objectives: Length and coverage rewards can improve neural machine translation, but text quality may still degrade as beam size increases.The paper therefore treats these methods as patches that do not address inherent text-generation problems and motivates linguistically informed regularizers.
3 Deriving Beam Search
The paper reverse-engineers beam search as exact decoding under a regularized objective rather than as an approximation to MAP. The resulting regularizer favors locally probable decisions and extends to beam sets, connecting beam search to a principled objective.
- Regularized decoding: The paper asks which regularizer makes beam search recoverable as an exact-decoding algorithm.This reframes beam search as optimizing log probability minus a strategically chosen regularization term.
- Surprisal and information: Time-dependent surprisal measures the amount of new information expressed at each generation step.The paper uses surprisals to connect beam-search behavior with information-theoretic and cognitive-science ideas.
- Greedy decoding: For greedy decoding, a regularizer that encourages each local decision toward the minimally surprising choice recovers greedy search as λ →∞.The theorem formalizes greedy search as the limiting exact solution of the regularized objective.
- Full beam search: Beam search’s regularizer operates on sets of partial and completed hypotheses expanded through each time step.The corresponding set objective scores hypothesis sets and uses a set-level regularizer to recover beam search.
- Full beam search: Theorem 3.2 states that maximizing log pθ(Y | x) − λ · R(Y) is computed by beam search with beam size k = |Y| as λ →∞.The construction generalizes the greedy-search result from individual hypotheses to sets.
- Computational scope: The regularized set objective is mainly an analytical tool because selecting the optimal subset is computationally prohibitive.For single-output decoding, the highest-probability sequence in the selected set can be returned, but the subset-selection formulation remains intractable.
4 From Beam Search to UID
The paper proposes that beam search’s hidden inductive bias is connected to uniform information density (UID), which favors distributing information more evenly across text. It frames beam search as exact decoding for a regularized objective and tests whether UID explains its empirical success.
- UID hypothesis: Uniform information density favors utterances that distribute information evenly across the signal when grammaticality and information content are held constant.The paper motivates UID through cognitive science and psycholinguistics.
- UID hypothesis: Including an optional relativizer can spread information across two words, avoiding a high-surprisal first word and producing a more uniform sentence.The example illustrates how syntactic choices can affect information density without changing grammaticality.
- Beam search and UID: Beam search narrows each decoding step to low-surprisal candidates, but its connection to UID emerges from the resulting distribution of surprisals across the completed sequence.The paper uses time-dependent surprisal curves to make this relationship visible.
- Beam search and UID: Exact MAP decoding can select locally high-surprisal decisions to obtain later compensation, producing non-uniform text; with λ = 0, it returns the empty string.The paper identifies the empty-string outcome as an extreme violation of its operationalized UID property.
- Cognitive motivation: The paper hypothesizes that beam search is cognitively motivated because it inherently biases language-generation decoding toward text humans prefer.This hypothesis links beam search’s practical success to a UID-related preference rather than approximation of MAP decoding.
- Cognitive motivation: Beam search is treated as exact decoding for a regularized objective whose qualitative behavior is related to UID, enabling empirical tests with explicit UID regularizers.The regularized framework is used to operationalize UID and evaluate the hypothesis.
5 Generalized UID Decoding
The paper develops sentence-level regularizers that explicitly encode uniform information density for exact and beam decoding. It evaluates whether these regularizers preserve performance and reduce degradation associated with larger beam sizes.
- Regularized decoding: The paper compares sentence-level UID measures as regularizers within a regularized decoding framework using downstream evaluation metrics.The goal is to test whether explicit UID objectives can match beam search’s behavior and performance.
- UID regularizers: Variance regularization operationalizes UID by penalizing variation in surprisals across a sentence.The measure targets the distribution of information over decoding time steps.
- UID regularizers: Local consistency regularization encourages adjacent surprisals to have similar magnitudes, making the sequence closer to uniform.The formulation applies across decoding steps, including the BOS-defined initial step.
- UID regularizers: The max regularizer penalizes decisions that move surprisal away from 0 and directly targets extreme compensation during decoding.The paper also notes a connection between this regularizer and entropy regularization.
- UID regularizers: The squared regularizer uses a squared penalty to push all surprisals close to 0 while pursuing a uniform distribution.It exploits the low-surprisal objective of MAP decoding.
6 Experiments
Experiments test UID-regularized decoding on NMT models using exact decoding and beam search, measuring BLEU and surprisal variation. UID regularization improves exact-decoding quality and reduces degradation at larger beam widths.
- Exact decoding: Increasing UID-regularizer strength makes exact-decoding results approach the BLEU of optimal beam search.The greedy UID regularizer also produces an inverse relationship between BLEU and per-sentence surprisal standard deviation.
- Regularized beam search: Standard MAP beam search generally loses text quality as beam size increases, whereas UID regularization alleviates this degradation.The greedy and squared regularizers help most at larger beam sizes; other regularizers retain only a slight performance drop.
- Regularizer comparison: Variance and local-variance regularizers perform worst despite being direct UID encodings, possibly because they do not also penalize high surprisal.The explanation is presented as an argument rather than a demonstrated causal finding.
- Combined regularization: Combining UID regularizers outperforms standard and length-normalized beam search, especially for larger beams, but offers less improvement than expected.This suggests that one UID-enforcing method may be sufficient for promoting generated-text quality.
7 Related Work
Related work situates the beam-search curse within broader degeneration problems in neural text generation and reviews normalization methods developed to address them.
- Neural generation problems: Neural probabilistic text generators often produce generic, unnatural, or nonexistent text, while larger beam sizes can worsen performance.The beam-search curse is described as a specific degradation phenomenon studied by prior work.
8 Conclusion
The paper frames beam search as exact decoding for a regularized objective linked to UID, then tests UID-based objectives in NMT experiments.
- Contribution: Beam search is framed as the solution to an exact decoding problem with an inductive bias linked to uniform information density.UID concerns the even distribution of information in linguistic signals.
- Empirical findings: Surprisal variance strongly relates to BLEU, and UID-oriented objectives alleviate quality degradation as beam widths increase.These observations are reported from NMT experiments.
A Theory
The theory proves that the greedy UID regularizer makes the regularized optimum equal the sequence found by greedy decoding. The proof proceeds by induction over time steps.
- Proof strategy: The proof defines yR as the argmax of log pθ(y | x) − λ · Rgreedy(y) and ygreedy as the greedy-search solution.It establishes equality by comparing the two hypotheses at each time step.
- Theorem conclusion: Induction shows that every feasible regularized optimum chooses the greedy word at every time step, yielding ygreedy = yR.The base case is the BOS token, and the inductive step preserves agreement through the sequence.
- Regularizer behavior: At time step t, the limiting greedy regularizer assigns a penalty of either 0 or ∞ depending on whether the decoding choice is greedy.Because minimum surprisal corresponds to maximum log-probability, non-greedy choices drive the objective to −∞.
B Parameters
The decoding experiments select regularization strengths through validation-set search. Table 2 reports the λ settings used for decoding in Fig. 3 and Table 1.
- λ values for Fig. 3 are selected by grid search using validation-set performance.The search considers λ values from 0.2 to 10.
- Combined UID regularization searches five strength parameters across 50 validation-set trials.Each parameter is sampled from the specified candidate values.
- The best reported settings are λ = 5 for the greedy regularizer and λ = 2 for the squared regularizer.
- Table 2 lists the λ settings used during decoding in Fig. 3 and Table 1.
C Additional Plots
Figure 4 plots BLEU against the standard deviation of surprisals for beam-search translations from IWSLT’14 and WMT’14. Point size encodes beam width, and the x-axis is linear rather than logarithmic.
- C Additional Plots: The x-axis is the standard deviation of surprisals, while the y-axis is BLEU.The plot covers beam-search translations on IWSLT’14 and WMT’14 test sets.
- C Additional Plots: Point size represents beam width, ranging from 5 to 100.Larger points therefore indicate different beam-search widths.
- C Additional Plots: Unlike the corresponding subgraph of Fig. 1, Figure 4 uses a non-log-scaled x-axis.This changes how standard-deviation differences are displayed along the horizontal axis.