Constrained translation with grid beam search
A from-scratch reimplementation of grid beam search (Hokamp and Liu, ACL 2017), a decoding algorithm that forces a translation model to include given words or phrases.
- Kind
- AI system
- Context
- Advanced NLP course, KU Leuven, about 100 hours
- Result
- Higher chrF than ordinary beam search at every beam width tested, up to 76.4 versus 72.4.
- Built with
- Python, PyTorch, Hugging Face Transformers, T5, sacreBLEU
- Status
The goal
Sometimes a translation must contain specific terms: a product name, a legal phrase, a glossary word. Ordinary beam search cannot guarantee that. Grid beam search can. I implemented it from scratch, following the original paper.
One sentence, with and without three required terms:
Source: Solve the riddle lurking behind the murder.
Constraints: Résoudre, se cache, mystère
Beam search: Solver le dénuement qui se cache derrière le meurtre.
Grid beam: Résoudre le mystère qui se cache derrière le meurtre.
How the decoder works
- Hypotheses are organised in a grid by how many constraint tokens they have covered so far.
- Three operations move through the grid: generate a free token, start a constraint, or continue one.
- Hypotheses that can no longer satisfy all constraints are pruned, and at most one constraint is in progress at a time.
- Efficiency: shallow copies of hypotheses, cached encoder outputs, and constraint tracking that is linear in the number of constraints.
Experiments
I used Hugging Face T5-small on an English-to-French CCMatrix dataset, compared against ordinary beam search with the same model, beam width and length limits. Constraints came from two sources: random words or word pairs from the reference translation, and a selector I built based on pointwise mutual information (PMI) that does not look at the reference.
Result
| Beam width | 2 | 3 | 4 | 5 | 10 |
|---|---|---|---|---|---|
| Beam search | 71.95 | 72.15 | 72.40 | 72.42 | 72.53 |
| Grid beam search | 74.00 | 73.09 | 76.37 | 75.03 | 74.89 |
| Grid beam search, PMI constraints | 70.65 | 70.58 | 71.20 | 71.95 | 71.68 |
chrF on 200 English-French sentence pairs; higher is better. BLEU and chrF++ show the same pattern.

chrF by beam width for the three decoders. Figure from the original project.
With the right terms given, as from a glossary, grid beam search wins at every beam width. Picking those terms automatically is harder: the PMI selector only sees the English source, and its constraints scored below plain beam search.