Beam decoding with a monotone-score stopping certificate
Algorithms AIMech:OptimalStoppingBeamDecoding DRAFT
Aliases: Optimal-ending beam search
A layer-based sequence beam decoder that retains the best completed hypothesis seen so far and stops when the highest current prefix score cannot exceed that incumbent under a score that never increases with extension.
Identity Notes & Concept Scope
This is Huang, Zhao and Ma’s 2017 optimal-ending procedure, with optimality explicitly limited by the retained beam. It differs from stopping on a completed top-ranked item without remembering earlier completions, from counting completed outputs, and from score-prioritized best-first expansion with per-length budgets. No normalized identity match was found across the 442 AIO and 146 prior native records; both checkout text searches included ignored and hidden files and returned no matches for the selected exact IDs, full labels, aliases and source titles.
Claims & Grounded Evidence
2 Claims
Mechanism
#method
Expand the current beam by one token and retain the highest-scoring candidates under a fixed beam policy. Do not extend EOS-complete hypotheses. Maintain the best completed hypothesis encountered in retained beams. Once that incumbent exists, stop when the maximum current prefix score is at most its score. Products of conditional probabilities in [0,1], or their cumulative log probabilities, cannot increase with extension, so descendants of retained active prefixes cannot improve the incumbent when the inequality holds.
Limitation
#score-versus-quality
The unmodified probability objective can favor short translations; the source therefore introduces bounded length rewards. The stopping certificate is a search-score statement, not a quality guarantee.
⚠️ Curated Limitations & Negative Results
- The certificate concerns descendants of retained beam prefixes. It does not recover prefixes pruned by finite width or guarantee global MAP decoding.
- A non-increasing extension score and a stored completed incumbent are required. Length normalization or positive rewards can invalidate the raw-prefix bound and need a different certificate.
- The paper compares stopping times under the same beam evolution and a specific historical top-completed baseline. It does not establish universally fastest decoding or current software defaults.
- Better model score does not imply better translation quality; the source reports short-output problems under pure probability scoring.
- Finite resource limits, absent EOS completions, empty beams and tie conventions need explicit implementation policies. No unconditional finite-time termination claim is made.
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 this sequence scoring, stopping or pruning method for natural-language generation, with neural machine translation as its central setting. The exact AIO CLASS describes the language-processing task. This is an method-to-application-domain relationship, not equivalence or an is-a assertion; the method is not a trained language-model instance and may also apply outside NLP. |
Evidence Sources & Primary Literature
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Liang Huang, Kai Zhao, Mingbo Ma
|
primary paper
full_text
|
ID: doi:10.18653/v1/D17-1227
sha256:7b9ed5e8c842…
|
score-versus-quality
|
Liang Huang, Kai Zhao, Mingbo Ma
|
primary paper
full_text
|
ID: doi:10.18653/v1/D17-1227
sha256:7b9ed5e8c842…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T06:36:44Z
Updated: 2026-10-11T06:37:11Z
Source File:
data/curated/OptimalStoppingBeamDecoding.yaml