Skip to content
MDM
2025

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

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 width234510
Beam search71.9572.1572.4072.4272.53
Grid beam search74.0073.0976.3775.0374.89
Grid beam search, PMI constraints70.6570.5871.2071.9571.68

chrF on 200 English-French sentence pairs; higher is better. BLEU and chrF++ show the same pattern.

Bar chart of chrF by beam width 2, 3, 4, 5 and 10 for beam search, grid beam search with random constraints, and grid beam search with PMI constraints. Grid beam search with random constraints is highest at every width, peaking at 76.37 at width 4.

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.