PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation

Matt Post, David Vilar

arXiv:1804.06609v2cs.CL

TL;DR

Neural machine translation makes manual output control difficult, while existing lexically constrained decoding methods become computationally expensive as constraints increase. The paper introduces dynamic beam allocation, a fixed-beam algorithm with O(1) complexity in the number of constraints, and reports practical speed and translation-quality results.

  • Problem

    Existing lexically constrained decoding methods restore target-side control in NMT but have linear or exponential complexity in the number of constraints and complicate batching.

  • Method

    Dynamic beam allocation groups hypotheses into constraint banks and dynamically divides a fixed-size beam across them at each decoding step.

  • Results

    O(1) complexity in the number of constraints enables DBA to decode at about 0.6 seconds per sentence on a Tesla V100 regardless of constraint count, while DBA achieves BLEU 26.7 versus 25.6 for GBS/1 at the same runtime.

  • Takeaways & Limitations

    DBA provides a practical way to incorporate arbitrary target-side constraints within the standard beam-decoding paradigm.

  • Takeaways & Limitations

    The paper notes that GBS has a variable beam size that complicates computation-graph optimization and throughput operations such as batching.

Abstract

from arXiv · show

The end-to-end nature of neural machine translation (NMT) removes many ways of manually guiding the translation process that were available in older paradigms. Recent work, however, has introduced a new capability: lexically constrained or guided decoding, a modification to beam search that forces the inclusion of pre-specified words and phrases in the output. However, while theoretically sound, existing approaches have computational complexities that are either linear (Hokamp and Liu, 2017) or exponential (Anderson et al., 2017) in the number of constraints. We present a algorithm for lexically constrained decoding with a complexity of O(1) in the number of constraints. We demonstrate the algorithms remarkable ability to properly place these constraints, and use it to explore the shaky relationship between model and BLEU scores. Our implementation is available as part of Sockeye.

1 Introduction

Neural machine translation makes manual control over output more difficult, motivating lexically constrained decoding. The paper introduces dynamic beam allocation, which keeps constraint handling constant in the number of constraints while improving practicality.

  • 1 Introduction: NMT makes interventions such as domain-specific dictionaries and forced translation choices more difficult than in phrase-based translation.These interventions supported interactive machine translation and domain adaptation.
  • 1 Introduction: Lexically constrained decoding forces specified target-side words and phrases to appear in the output.It modifies beam search and does not require source-word or alignment information.
  • 1 Introduction: Existing constrained-decoding methods have linear or exponential complexity in the number of constraints, and can complicate throughput-oriented operations such as batching.GBS has linear complexity, while CBS has exponential complexity in the constraint count.
  • 1 Introduction: Dynamic beam allocation (DBA) has O(1) complexity in the number of constraints.The algorithm dynamically divides a fixed-size beam across banks of hypotheses grouped by the number of constraints met.
  • 1 Introduction: DBA is designed to scale to large constraint sets, including those produced by sub-word processing such as BPE.The paper reports empirical speed advantages over GBS and provides the implementation through Sockeye.

2 Beam Search and Grid Beam Search

Beam search maintains a fixed set of high-scoring translation hypotheses, while grid beam search adds separate banks to ensure that all lexical constraints are met. This guarantees constraint coverage but increases complexity and reduces practicality as the constraint count grows.

  • 2 Beam Search and Grid Beam Search: Beam search maintains k active hypotheses and repeatedly expands them over the target vocabulary before retaining the k-best states.The decoder produces a k × |V_T| score matrix at each time step.
  • 2 Beam Search and Grid Beam Search: Grid beam search groups hypotheses by the number of constraints met and returns the highest-scoring completed hypothesis from the bank satisfying all C constraints.It maintains C + 1 separate banks and tracks constraint completion during decoding.
  • 2 Beam Search and Grid Beam Search: GBS has decoding complexity linear in the number of constraints because its effective beam size is k · (C + 1).The beam expands with the constraint count rather than remaining fixed.
  • 2 Beam Search and Grid Beam Search: Variable beam sizes make GBS impractical for standard decoder computation graphs and throughput optimizations such as batching.This is especially problematic when computation is optimized for GPUs.
  • 2 Beam Search and Grid Beam Search: DBA addresses these issues by keeping one fixed beam of size k and dynamically allocating its slots across constraint banks.Its bookkeeping overhead is constant in the number of constraints while preserving the standard beam-decoding paradigm.

3 Dynamic Beam Allocation (DBA)

DBA keeps a fixed-size beam while dynamically allocating it across banks of hypotheses grouped by the number of constraints met. It generates candidates that preserve constraint progress, handles phrasal-constraint interruptions, and reallocates unused bank capacity.

  • Beam allocation: DBA divides a fixed-size beam across banks grouping hypotheses by how many constraints they have met.The allocation changes across sentences and decoder timesteps, rather than multiplying the beam by the number of constraints.
  • Candidate generation: The decoder builds candidates from overall top-k scores, unmet-constraint extensions, and each hypothesis’s single-best token.These candidates are grouped by constraints met and sorted within banks before allocation.
  • Phrasal constraints: When a phrasal constraint is interrupted, the decoder unwinds its already-met tokens so generation can abandon that partial phrase.This permits prefixes that occur naturally in the sentence without forcing completion of the phrase.
  • Beam allocation: Each bank initially receives ⌊k/C⌋ slots, with remaining capacity assigned to the maximally constrained bank.Bank adjustment redistributes slots when banks have too few candidates, including when C may exceed k.
  • Finishing: Completed hypotheses may generate ⟨/s⟩ only after meeting all constraints, and the highest-scoring completed item is returned.DBA’s k-best extraction operates on a k × |VT | matrix of model states.

4 Experimental Setup

The experiments use a Sockeye English–German NMT system trained on WMT’17 data with a 32k-operation joint BPE vocabulary. Decoding is evaluated on newstest2014 with normalized scores, threshold pruning, and a single Volta P100 GPU.

  • Model and training: The model is a 4-layer attention-based RNN trained on the complete WMT’17 English–German training corpora.Training uses Moses tokenization, a joint 32k-operation BPE vocabulary, and Adam with batch size 80.
  • Decoding: Completed hypotheses are scored by dividing cumulative sentence score by the number of words.Decoding stops when all remaining hypotheses are complete or the maximum length N is reached.
  • Decoding: Threshold pruning removes hypotheses whose log probability is more than 20 below the best completed hypothesis.The threshold applies to complete and incomplete hypotheses unless otherwise noted.
  • Evaluation: BLEU is computed on detokenized newstest2014 English–German output using SACREBLEU.The developer test set contains 2,737 sentences, making scores directly comparable with WMT evaluations.

5 Validation Experiment

The validation experiments test randomly selected reference words and phrases after BPE, comparing DBA with simulated GBS across constraint counts. DBA’s runtime remains constant in constraint count and can improve BLEU over comparable GBS settings, although low beam sizes limit gains for many independent constraints.

  • Constraint sets: The experiments extract one to four random reference words or a random four-word phrase, then apply BPE, often increasing token-constraint counts.The test set contains 2,737 sentences, and constraint-count distributions are summarized after BPE.
  • Runtime: DBA’s decoding time remains constant as post-BPE constraint count increases, while GBS follows a clear linear runtime trend.With k = 10, DBA takes about 0.6 seconds/sentence regardless of constraint count, about 3x slower than unconstrained decoding.
  • Comparison with GBS: DBA achieves BLEU 26.7 vs. 25.6 for GBS/1 with the same runtime and a fixed rather than variable-sized beam.GBS/1 has beam size k ≥10 when C ≥9.
  • Beam-size stress test: DBA remains usable when C >= k and improves BLEU over GBS at k = 5, reaching 23.5 vs. 22.3.Bank adjustment enables operation when the number of constraints is at least the beam size.
  • Constraint placement: Low k relative to C considerably reduces the observed BLEU improvement, with the only failure to beat baseline occurring for four random constraints at k = 5.DBA still meets the constraints at beam size 5, while phrasal constraints are placed without trouble.

6 Analysis

DBA places lexical constraints sensibly, but decoding quality depends on beam size and pruning. Its analysis also exposes a reference-aversion pattern in which lower model scores can accompany higher BLEU.

  • 6.1 Placement: All constraint sets improve as beam size increases, while rand4 falls below the unconstrained baseline when the beam is too small.DBA still meets constraints with beam size 5, but translation quality suffers.
  • 6.1 Placement: Pearson’s r = 0.82 between reference and constrained-output constraint locations indicates that DBA generally places constraints correctly.The comparison uses each constraint’s first-word location normalized by sentence length.
  • 6.2 Reference Aversion: Forcing even one reference word lowers model score while improving BLEU, and the model-score penalty grows as more constraints are added.The constrained hypotheses nevertheless improve as beam size increases.
  • 6.2 Reference Aversion: The observed inverse relationship between model score and BLEU complements earlier findings that larger beams can raise model scores while lowering BLEU.The paper presents both results as evidence of a poorly understood disconnect between the two metrics.
  • 6.3 Effects of Pruning: A pruning threshold of 20 is needed for BLEU to exceed the unpruned setting; without pruning, decoding takes nearly twice as long.Lower pruning thresholds harm BLEU, whereas pruning removes hypotheses sufficiently far below the best completed hypothesis.
  • 6.4 Garbage Generation: Without pruning, the decoder continues to the maximum timestep after finishing good hypotheses and fills the beam with low-cost garbage.Early stopping fixes the runtime increase but produces lower BLEU scores.

7 Related Work

Prior lexically constrained decoding methods extend beam search to enforce target-side words and phrases, but differ in their constraint-tracking machinery and computational cost.

  • 7 Related Work: Grid beam search allows arbitrary target-side words as hard constraints by restructuring beam search.Its beam grows with the number of constraints.
  • 7 Related Work: Constrained beam search tracks completed constraint subsets with a finite-state machine, incurring exponential cost in the number of constraints.Both GBS and CBS use target-side constraints without source-word or alignment information.
  • 7 Related Work: Lexically constrained decoding generalizes prefix decoding by including the start symbol as the first word of a constraint.
  • 7 Related Work: The placeholder approach masks identifiable input elements during preprocessing and restores their source-language strings during postprocessing.

8 Summary

Lexically constrained decoding restores a form of output control to NMT through target-side constraints. DBA makes this approach practical with constant constraint overhead and fast decoding even for large constraint sets.

  • 8 Summary: Lexically constrained decoding restores fine-grained control over NMT output using only specified target-side constraints.The decoder can correctly place constraints without source-word or alignment information.
  • 8 Summary: DBA dynamically allocates a fixed-size beam across constraint banks, replacing linear or exponential constraint complexity with constant overhead.The method maintains one beam of size k rather than C + 1 beams.
  • 8 Summary: About 0.6 seconds per sentence on a Volta GPU makes DBA practical with 10+ constraints for latency-sensitive applications.The paper notes that further optimizations may improve runtime.

A Appendix: Failed Experiments

The paper reports DBA as a fast algorithmic improvement but does not corroborate earlier interactive-translation and domain-adaptation experiments, and other tested applications were unsuccessful.

  • A Appendix: Failed Experiments: The study did not attempt to corroborate prior interactive translation and domain adaptation experiments, and several other applications were unsuccessful.The authors present these experiments as a brief report in the interest of open scientific inquiry.

A.1 Automatic Constraint Selection

The experiments tested automatically selected phrase constraints and found that, unlike random reference phrases, these selections did not improve translation on WMT or IWSLT data.

  • Random reference constraints produced substantial BLEU gains, reaching 10+ points with a four-word phrase.A single random reference word increased BLEU by one point, and two random words added another point.
  • Only about 18% of random reference unigrams appeared in unconstrained outputs, with lower overlap for longer n-grams.
  • Automatically selected phrase-table constraints did not improve translation on WMT or IWSLT data.Selection criteria included longest phrase, highest significance, highest probability, and combinations of these criteria.

A.2 Name Entity Translation

The paper examined dictionary-based constraints for named entities, but a noisy automatically extracted dictionary did not improve translation; higher-quality manual dictionaries may help.

  • NMT systems often perform poorly on rare words, particularly named entities, even when BPE represents them in the vocabulary.Correct translations may not follow source or subword patterns, especially for named entities.
  • The authors created a German–English named-entity corpus by tagging both sides of OpenSubtitles and retaining shared Person, Location, and Organization tags.
  • Adding translations from the extracted named-entity dictionary as decoding constraints did not help because the dictionary remained too noisy.The authors suggest that a manually curated, high-quality dictionary may produce improvements.
Loading 1804.06609v2…