Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation
Matt Post, David Vilar
cs.CL
2018-04-18
DBA makes lexically constrained decoding cost constant in constraint count: about 0.6s per EN-DE sentence no matter how many words are forced in, beating grid beam search on BLEU.
End-to-end neural machine translation is fully automatic, which is also its weakness: you can barely steer the output. In the old statistical-translation era, dropping in a domain dictionary or forcing a specific word to translate a certain way was routine. The neural paradigm cut most of those manual levers away.
Lexically constrained decoding brings one lever back. At decoding time you specify a set of target words or phrases that must appear in the output. The problem is that the two existing algorithms are expensive. Hokamp and Liu's grid beam search (GBS) scales linearly in the number of constraints; Anderson et al.'s constrained beam search (CBS) scales exponentially. Add many constraints and decoding grinds to a halt, and both restructure beam search so heavily that batching and other speedups no longer fit.
DBA (Dynamic Beam Allocation) swaps GBS's multiplication for division. GBS reserves a separate sub-beam for each constraint-completion state, so the total beam is k times the number of states, growing wider with every constraint. DBA keeps a single fixed beam of size k and dynamically decides each step which states get how many of those slots.
Concretely, candidates are grouped into "banks", each bank representing how many constraints have been satisfied so far. Each step collects three kinds of candidates: the top-k tokens overall, every still-unmet constraint (to force progress), and the single best token per hypothesis (to keep partial completions alive). An allocation function then decides how many slots each bank gets this step, and rebalances the next. The complexity drops to O(Nk), independent of the number of constraints.
The decisive trick is bank adjustment: it lets DBA keep working when the constraint count C exceeds the beam width k, a regime where GBS simply fails.
Experiments run on English-to-German translation, WMT'17 training data, a 4-layer RNN, in the Sockeye decoder. The test set has about 2,737 sentences.
The speed gap is stark. GBS time per sentence climbs linearly with the constraint count; DBA is a nearly flat line. On a Tesla V100, DBA (k=10) takes about 0.6 seconds per sentence no matter how many constraints are added, roughly 3× the cost of unconstrained decoding (about 1.4s on a K80).
On quality DBA also holds up. The unconstrained baseline (k=10) scores BLEU 22.3; DBA reaches 26.7 at k=10 and 27.2 at k=20. Against GBS on a fair footing, with GBS's base beam set to 1 (so its beam also reaches 10+ when constraints are many), GBS scores 25.6. DBA matches that runtime with a fixed beam and scores 26.7.
| Setting | BLEU | Note |
| Unconstrained (k=10) | 22.3 | baseline |
| DBA (k=10) | 26.7 | fixed beam, cost independent of constraint count |
| DBA (k=20) | 27.2 | |
| GBS base beam=1 (k≥10) | 25.6 | same runtime |
The authors also confirm the constraints land in the right place, not merely inflating n-gram counts by appearing somewhere: the correlation between the reference position and the output position of each constraint's first word is 0.82, achieved without any source-side word alignment information.
This 2018 paper was written for machine translation, but the underlying problem is hot again in the agent era. Forcing a large model to emit specified tokens or a specified format during decoding is exactly the machinery behind function calling, structured output (JSON schema), and tool use, collectively called guided generation. The headline result here is that "more constraints means slower decoding" can be defeated: the cost can be made independent of how many constraints there are.
The authors also surface an old grievance in translation: model score and BLEU are not the same thing. As constraints are added and the output is pushed toward the reference, the model likelihood gets steadily worse (log-probability falls from −1039 down to −4396 for the full reference) while BLEU gets better (22.3 up to 95.9). The sentences the model finds least likely are the highest-quality translations. Treating perplexity as a proxy for translation quality has real water in it.
Experiments cover only the English-to-German language pair, and the main results use an RNN; the authors only claim the code runs on a Transformer "without modification" and give no Transformer benchmarks. The constraint count cannot be too large relative to the beam, or quality drops, and the authors note that correctly placing many independent constraints is itself an exponentially hard permutation problem. The paper also documents a decoder pathology: once forced into a low-probability region, the decoder keeps generating nonsense in the lower beam, held in check only by pruning.