A-star beam search for sequence decoding
Algorithms AIMech:SequenceAStarBeamSearch DRAFT
Aliases: A* beam search for sequence decoding
A sequence-decoding beam framework that ranks active hypotheses by accumulated score plus an optimistic future-score heuristic, uses shorter length to break score ties, and limits accepted expansions to k hypotheses per sequence length.
Identity Notes & Concept Scope
This names the finite-beam A-star decoding framework in Meister, Vieira and Cotterell, not every algorithm informally called A-star beam search. The h=0 specialization has its own per-length best-first record. A finite per-length budget distinguishes the framework from unpruned A* and from a whole-frontier capacity cap. 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
2 Claims
Mechanism
#search-procedure
Use Algorithm 2 with the A-star beam settings in Table 1: prioritize the sum of current score and h, maintain a separate length counter, and suppress expansions beyond that length’s k budget. For maximization, an admissible h is optimistic about achievable future reward. The framework’s top-completed-hypothesis stopping rule operates over this already-pruned agenda; a finite beam can exclude globally superior paths.
Limitation
#finite-beam-heuristic
With finite pruning, even an admissible future-score heuristic can alter which hypotheses survive compared with ordinary width-k beam search. The paper distinguishes the zero-heuristic equivalence result from this more general framework.
⚠️ 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.
- Admissibility of h does not preserve the zero-heuristic beam’s output after finite pruning. This is explicitly acknowledged in Section 4.1.
- Unpruned A-star guarantees cannot be transferred to the finite-beam framework merely because its heuristic is admissible. No unrestricted nonmonotonic stopping theorem is asserted.
- Application to a particular score requires checking the direction and validity of its future-reward bound, terminal behavior and stopping policy.
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
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Clara Meister, Tim Vieira, Ryan Cotterell
|
primary paper
full_text
|
ID: doi:10.1162/tacl_a_00346
sha256:46728395bd4f…
|
finite-beam-heuristic
|
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/SequenceAStarBeamSearch.yaml