First-come, first-served beam decoding
Algorithms AIMech:FCFSBeamDecoding DRAFT
Aliases: FCFS beam decoding
The sequence beam-decoding procedure described by Kasai and colleagues that stores completed hypotheses separately from the continuing beam and stops when the accumulated number of completed hypotheses reaches the beam width, returning the highest-scoring stored completion.
Identity Notes & Concept Scope
FCFS here names a sequence-decoding policy, not first-in-first-out queue scheduling. Completed sequences leave the active beam and remain in a separate set. This differs from the paper’s vanilla beam decoder, where finished and unfinished hypotheses compete for the same beam slots, and from score-prioritized per-length best-first beam search. The original policy is the patience-controlled family’s p=1 case. No normalized identity match was found across the 442 AIO and 141 prior native records; ignored-inclusive text hits in the main checkout were prior discovery leads and incidental substrings such as builds in records, source text and dependencies, not existing concept records.
Claims & Grounded Evidence
2 Claims
Mechanism
#search-procedure
At each sequence length, expand the continuing hypotheses and scan the candidate pool in decreasing score order. Move an encountered EOS-ending hypothesis into the persistent finished set; otherwise keep it in the next continuing beam, up to width k. Stop during this selection when k completed hypotheses have accumulated and return the best stored completion. The paper also imposes a maximum generation length.
Scope
#finished-versus-active
Finished hypotheses accumulate outside the k-wide continuing beam in FCFS. In the contrasted vanilla procedure, completed hypotheses remain among the beam candidates and can later fall out. These are different search policies despite a shared beam width.
⚠️ Curated Limitations & Negative Results
- The count-based stopping rule can discard unfinished candidates and is not a global optimality certificate or a guarantee of equality to vanilla beam decoding.
- The record identifies the paper’s specified procedure. Claims about particular library defaults are historical context, not assertions about current software versions.
- The simplified pseudocode assumes that candidate selection and completion return are defined. Exhausted candidate pools, absence of any EOS completion, ties and maximum-length handling require explicit implementation policies.
- The score and any length penalty affect candidate selection and comparison of completed outputs. A fixed beam width alone does not determine output quality.
- The paper’s favorable comparisons are task/model dependent; no numerical benchmark gain or universal generation-quality claim is curated.
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 sequence-decoding policies for natural-language generation, including translation and summarization. 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
|
Jungo Kasai, Keisuke Sakaguchi, Ronan Le Bras, Dragomir Radev, Yejin Choi, Noah A. Smith
|
primary paper
full_text
|
sha256:7d090ee35511…
|
finished-versus-active
|
Jungo Kasai, Keisuke Sakaguchi, Ronan Le Bras, Dragomir Radev, Yejin Choi, Noah A. Smith
|
primary paper
full_text
|
sha256:7d090ee35511…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T06:26:52Z
Updated: 2026-10-11T06:26:52Z
Source File:
data/curated/FCFSBeamDecoding.yaml