Stochastic beam search
Algorithms AIMech:StochasticBeamSearch DRAFT
Aliases: SBS
The sequence-sampling algorithm of Kool, van Hoof and Welling that implements Gumbel-Top-k without replacement implicitly on a locally normalized sequence tree by propagating conditional perturbed subtree maxima and retaining the k highest-scoring prefixes at each level.
Identity Notes & Concept Scope
This record denotes the 2019 Gumbel-based sequence sampler, not every search algorithm called stochastic beam search. The generic Gumbel-Top-k distributional construction is a separate record. The method differs from independently resampling prefixes at every beam step, ordinary probability-ranked beam decoding, and diversity-penalized beam groups. An earlier search hit about coalition-formation scatter search is a separate title lead, not evidence of equivalence. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 328 preceding native IDs/names/aliases. Full-checkout fixed-string searches included ignored and hidden files in worktree and main, returning 49 and 49 lines respectively. All 2 unique hit contents were inspected: a saved stochastic-beam/Gumbel discovery lead and a search-result title about coalition-formation scatter search, not existing candidate records. Exact checkout counts and differences are retained in the ledger. Nine exact AIO CLASS nodes with scoped synonyms/comments and outgoing edges and four full native neighboring records were inspected. Absence is bounded to this snapshot and semantic neighborhood.
Claims & Grounded Evidence
3 Claims
Mechanism
#method
Represent complete sequences as leaves of a finite locally normalized prefix tree, using a declared common horizon or probability-preserving padding of completed sequences. A prefix log probability is the log of its descendant probability mass. Its stochastic score represents the maximum perturbed leaf log probability in that subtree. Start at the root; its maximum may be sampled from Gumbel(0) or fixed at zero as in Algorithm 1, since the maximum is independent of the selected ranking. For each retained parent with stochastic score T, sample independent child values G_i from Gumbel(phi_i), where phi_i is the child’s cumulative log probability; let Z=max_i G_i, then transform each to −log(exp(−T)−exp(−Z)+exp(−G_i)). This samples child maxima conditionally on their maximum being the parent’s T. Pool child candidates and retain up to k with the largest transformed scores, repeating through the declared horizon. Under the stated finite normalized tree construction this returns the same ordered without-replacement sequence distribution as explicitly applying Gumbel-Top-k to all complete leaves. The ordering is by perturbed score, not raw sequence probability.
Application
#language-generation
The paper develops sequence sampling as an alternative to ordinary sampling and deterministic beam decoding for language generation, and studies translation as its principal application. This is a procedure operating on a probability-supplying model, not a trained model identity or a universal translation-quality claim.
Scope
#prefix-consistency
Retained branches carry a consistent conditional perturbation. More than one final sample may share a prefix; requiring exactly one descendant per earlier beam member changes the sampling procedure. The source also distinguishes this construction from independently choosing fresh random prefixes at every depth.
⚠️ Curated Limitations & Negative Results
- The requested sample count must not exceed the number of positive-probability complete leaves. Zero-mass branches require exclusion or an explicit limiting representation; an exhausted support is not a source of additional distinct samples.
- The exact sampling statement requires consistent conditional subtree maxima and the declared normalized sequence distribution. Independently resampling prefixes at each depth, using raw length-normalized scores, or transplanting ordinary beam early stopping does not inherit that statement.
- The paper assumes common-length sequences with padding possible. Variable-length generation requires an explicit terminal/EOS policy preserving the intended leaf distribution; arbitrary forced truncation or nonterminating probability mass is not silently covered.
- The linear-in-k-and-length claim concerns the number of model evaluations. Vocabulary expansion, top-k selection, neural-state storage and numerical operations still have costs; this is not a bound independent of vocabulary size or model cost.
- The conditional-maximum formula can be numerically unstable in direct exponential form. Appendix B supplies stable transformations; exact distributional reasoning is not a certification of finite-precision implementation.
- Distinct complete samples can share prefixes and need not have high semantic diversity or be the unperturbed MAP sequences. Without-replacement samples are dependent, and arbitrary unweighted sample averages are not automatically unbiased.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:NaturalLanguageProcessing
Natural Language Processing
|
related_match | The inspected primary paper develops this decoder for natural-language sequence generation, including machine translation. The exact AIO CLASS denotes the language-processing task. This is an algorithm-to-application-domain relationship, not equivalence or an is-a assertion; the decoder is separate from the model supplying probabilities and is not restricted to natural-language sequences. |
Evidence Sources & Primary Literature
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Wouter Kool, Herke van Hoof, Max Welling
|
primary paper
full_text
|
sha256:0e5d71684fae…
|
conditional-sampling
|
Wouter Kool, Herke van Hoof, Max Welling
|
primary paper
full_text
|
sha256:a0a844d8b0e4…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T16:13:12Z
Updated: 2026-10-11T16:14:58Z
Source File:
data/curated/StochasticBeamSearch.yaml