Memory-reduced best-first beam search for sequence decoding
Algorithms AIMech:MemoryReducedSequenceBeamSearch DRAFT
A capacity-limited variant of per-length best-first sequence beam search that, when its chosen total queue capacity is reached, removes the worst-scoring active hypothesis from the earliest active sequence length.
Identity Notes & Concept Scope
This is the memory-reduced variant in Meister, Vieira and Cotterell Section 3.3. Its eviction first chooses the earliest active length, so it differs from globally removing the worst-ranked hypothesis. It also differs from the base per-length best-first procedure, which can retain hypotheses at several lengths without this extra capacity pruning. 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
Organize active hypotheses in queues for their sequence lengths and prioritize lengths by their best available score. Apply the base per-length beam limits and an additional total active-queue capacity. To make room, evict the minimum-scoring item in the earliest nonempty length queue; then continue decoding the surviving agenda.
Limitation
#capacity-boundary
The variant adds pruning to the base decoder by limiting queue capacity and targeting the earliest active time step for eviction. The paper presents it as a separate memory-reduced method, not as the unchanged monotone-beam equivalence construction.
⚠️ 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.
- Additional capacity eviction can remove paths retained by the unmodified beam procedure, so its same-output guarantee is not inherited. The memory/quality tradeoff is empirical and problem dependent.
- The queue cap does not bound the entire decoder or neural model memory. The earliest-length eviction is not a global worst-score eviction rule.
- No guarantee for arbitrary nonmonotonic scores or globally optimal sequence decoding is asserted.
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…
|
capacity-boundary
|
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/MemoryReducedSequenceBeamSearch.yaml