Gumbel-Top-k trick
Mathematical Methods AIMech:GumbelTopKTrick DRAFT
Aliases: Gumbel top-k sampling
A categorical sampling construction that adds independent standard Gumbel noise to each category’s log weight and returns the indices of the k largest perturbed values in descending order, producing an ordered sample without replacement under successive renormalization of the remaining weights.
Identity Notes & Concept Scope
This is the finite categorical Gumbel-Top-k construction formalized by Kool and colleagues, who credit an earlier observation by Vieira. The k=1 case is the Gumbel-Max trick. It is distinct from truncating a language model to its k most probable tokens and then sampling, from a continuous Gumbel-Softmax relaxation, and from the separate stochastic beam algorithm that applies the construction implicitly to sequences. 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
2 Claims
Mechanism
#method
For n categories with positive finite weights w_i and 1≤k≤n, draw independent G_i with the standard Gumbel distribution, equivalently G_i=−log(−log U_i) for independent U_i uniform on (0,1). Rank log(w_i)+G_i and return the first k distinct indices in that perturbed order. The probability of an ordered distinct tuple (i_1,…,i_k) is the product over j of w_i_j divided by the total weight remaining after indices i_1,…,i_(j−1) are removed. Common weight normalization is unnecessary because it adds only a common shift to all log scores. This is an exact distributional statement for the specified random variables, not an assertion that the selected indices are the highest-probability unperturbed categories.
Limitation
#inclusion-boundary
Without replacement here means sequential categorical sampling with the remaining weights renormalized after every selected index. It does not mean that each category’s probability of appearing anywhere in the k-sample is proportional to its original probability. The source explicitly distinguishes these quantities.
⚠️ Curated Limitations & Negative Results
- The ordered sampling probabilities differ from marginal inclusion probabilities; inclusion is not generally proportional to the original weight or equal to k times its normalized probability. At k=n every supported category is included.
- The stated construction assumes positive finite weights and k no larger than the positive support. Zero weights require exclusion or a declared limiting convention; invalid weights and k beyond support are not covered.
- Exactness assumes the specified independent continuous noise and exact ranking. Finite precision, random-number endpoints and numerical ties require implementation policies; no software implementation was certified.
- Direct finite-domain application perturbs all n category scores. It does not by itself supply an efficient algorithm for exponentially many complete sequences, a differentiable relaxation, or an unbiased sample-mean estimator for arbitrary without-replacement outputs.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No suitable target for the generic ordered categorical sampling procedure was established in this inspected snapshot and semantic neighborhood. Shared probability, categorical and sampling terminology does not justify a forced model, function, bias or task mapping.
Search Scope: All 442 pinned AIO labels/scoped synonyms and 328 preceding maintained IDs/names/aliases; ignored/hidden-inclusive full text in both checkouts; semantic labels/scoped synonyms for Gumbel, beam, sampling, autoregression, inference, decoding, sequence, categorical, reparameterization, temperature, search and reasoning; nine exact AIO CLASS nodes and four complete native beam-search neighbors.
| Examined AIO Candidate | Rejection Reason |
|---|---|
AIO:AutoregressiveLanguageModel
|
A language model supplying next-token probabilities is different from this generic finite categorical sampling rule; it does not define the rule’s identity or required application. |
AIO:NaturalLanguageProcessing
|
The generic categorical rule is not restricted to natural-language data; its sequence-model application is curated separately. |
AIO:SoftmaxFunction
|
Softmax normalizes scores to probabilities; Gumbel-Top-k returns discrete ordered random indices. Their mathematical relationship does not make the sampling operation the normalization function. |
AIO:MathematicalFunction
|
This record specifies an ordered stochastic sampling procedure and its distributional identity, not a deterministic input-output function class. |
AIO:SelectionAndSamplingBias
|
Sampling without replacement from a specified categorical distribution is not the ontology’s nonrepresentative-selection bias concept. |
AIO:CategoricalFeaturesPreprocessingLayer
|
Categorical random outcomes do not make the sampling rule a neural feature-preprocessing layer. |
AIO:ProbabilisticGraphicalModel
|
The finite categorical trick requires no graphical conditional-dependence representation; the tree-based sequence construction is a separate concept. |
AIO:MachineLearningTask
|
Drawing random indices from supplied weights does not itself learn from data. |
AIO:TrainingStrategy
|
No model training or training-data preprocessing is required by the sampling identity. |
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…
|
sampling-proof
|
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:13:12Z
Source File:
data/curated/GumbelTopKTrick.yaml