Home / Curated / Algorithms / Best-first beam search with per-length budgets

Best-first beam search with per-length budgets

Algorithms AIMech:SequenceBestFirstBeamSearch DRAFT

The sequence-decoding beam procedure of Meister, Vieira and Cotterell that prioritizes active hypotheses by decreasing accumulated score, breaks score ties by shorter length, and limits accepted expansions to k hypotheses at each sequence length without a future-score heuristic.

Identity Notes & Concept Scope This is the 2020 sequence-decoding meaning of best-first beam search. Its per-length budget is distinct from AIMech:GlobalFrontierBeamSearch, which caps the entire open list. The qualified name avoids treating those different pruning rules as exact synonyms. The h=0 procedure is a specialization of the paper’s A-star beam framework. No normalized identity match was found across the 442 AIO and 135 prior native records; ignored-inclusive text hits in the main checkout were prior discovery leads, source citations, scope contrasts and DCBSS substring matches, plus seven public certificate-data substring matches, not existing concept records.

Claims & Grounded Evidence

3 Claims

Mechanism #search-procedure

Maintain a score-prioritized agenda and a count for each hypothesis length; skip expansion after k hypotheses of that length have been accepted. Under scores that never increase on extension and h=0, the paper shows that the top completed hypothesis agrees with its specified width-k layer beam, with compatible tie and EOS conventions. Once k hypotheses of a later length have been accepted, earlier unfinished layers can be removed under those same monotonicity assumptions.

supports Source: Best-First Beam Search · Locator: Algorithm 2 and Table 1, printed pp. 797–798 / PDF pp. 3–4; Sections 3.2–4.1, printed pp. 798–801 / PDF pp. 4–7

Limitation #heuristic-boundary

The paper explicitly limits its beam-output equivalence proof to the zero-heuristic case; an optimistic future-score heuristic can change which paths survive finite-beam pruning.

supports Source: Best-First Beam Search · Locator: Section 4.1, A Note on Heuristics, printed p. 801 / PDF p. 7

Application #decoding-context

The method is defined for sequential structured prediction and developed in the paper around natural-language sequence transduction, including translation and abstractive summarization. The decoder is separate from the trained model that supplies scores.

supports Source: Best-First Beam Search · Locator: Sections 1–2, printed pp. 795–796 / PDF pp. 1–2

⚠️ Curated Limitations & Negative Results

The finite beam is an approximation to exact sequence-model decoding; equality to a specified beam procedure is not global MAP optimality.
Sequence length limits, EOS handling and compatible deterministic tie conventions are part of the comparison. Arbitrary implementations with different stopping or tie rules need not return identical hypotheses.
Queue counts are counts of retained hypotheses, not total bytes including neural states, model parameters, backpointers and temporary successors. No numerical speedup or benchmark-quality claim is curated.
The beam-equivalence claim is restricted to nonincreasing scores and h=0. The paper also asserts a nonmonotonic stop-only extension; this record does not adopt that guarantee because a saved curator finite-tree counterexample exposes a conflict with unchanged per-length pruning.
The optimized queue-of-beams representation can retain hypotheses at several lengths. The per-length budget is not a global queue-capacity bound.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:NaturalLanguageProcessing` Natural Language Processing	related_match	The primary paper defines these decoding procedures for sequential structured prediction and develops them around natural-language transduction. The exact AIO CLASS describes the language-processing task. This is an algorithm-to-application-domain relationship, not equivalence or an is-a assertion; the decoder is not a trained language model and can also be used outside NLP.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`method-source`	Best-First Beam Search Clara Meister, Tim Vieira, Ryan Cotterell	primary paper full_text	ID: doi:10.1162/tacl_a_00346 sha256:46728395bd4f…
`heuristic-boundary`	Best-First Beam Search Clara Meister, Tim Vieira, Ryan Cotterell	primary paper full_text	ID: doi:10.1162/tacl_a_00346 sha256:46728395bd4f…
`decoding-context`	Best-First Beam Search Clara Meister, Tim Vieira, Ryan Cotterell	primary paper full_text	ID: doi:10.1162/tacl_a_00346 sha256:46728395bd4f…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-11T06:16:04Z

Updated: 2026-10-11T06:16:04Z

Source File: data/curated/SequenceBestFirstBeamSearch.yaml