# Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement

arXiv: https://arxiv.org/abs/1903.06059 · HTML: https://mlsanity.com/paper/1903.06059/

## Key facts

- Cited by 211 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Mar 2019.

## Built on by (most cited first, 30 of 211)

- [Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions](https://mlsanity.com/paper/2102.05379/) (2021)
- [Data Selection for Language Models via Importance Resampling](https://mlsanity.com/paper/2302.03169/) (2023)
- [A Contrastive Framework for Neural Text Generation](https://mlsanity.com/paper/2202.06417/) (2022)
- [Self-Evaluation Guided Beam Search for Reasoning](https://mlsanity.com/paper/2305.00633/) (2023)
- [Streaming Long Video Understanding with Large Language Models](https://mlsanity.com/paper/2405.16009/) (2024)
- [A Reparameterized Discrete Diffusion Model for Text Generation](https://mlsanity.com/paper/2302.05737/) (2023)
- [MemSkill: Learning and Evolving Memory Skills for Self-Evolving Agents](https://mlsanity.com/paper/2602.02474/) (2026)
- [Truncation Sampling as Language Model Desmoothing](https://mlsanity.com/paper/2210.15191/) (2022)
- [Online Coreset Selection for Rehearsal-based Continual Learning](https://mlsanity.com/paper/2106.01085/) (2021)
- [Pixel Contrastive-Consistent Semi-Supervised Semantic Segmentation](https://mlsanity.com/paper/2108.09025/) (2021)
- [MATES: Model-Aware Data Selection for Efficient Pretraining with Data Influence Models](https://mlsanity.com/paper/2406.06046/) (2024)
- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [Revisiting the Test-Time Scaling of o1-like Models: Do they Truly Possess Test-Time Scaling Capabilities?](https://mlsanity.com/paper/2502.12215/) (2025)
- [Informed Correctors for Discrete Diffusion Models](https://mlsanity.com/paper/2407.21243/) (2024)
- [Machine Translation Decoding beyond Beam Search](https://mlsanity.com/paper/2104.05336/) (2021)
- [MIST: Multi-modal Iterative Spatial-Temporal Transformer for Long-form Video Question Answering](https://mlsanity.com/paper/2212.09522/) (2022)
- [Self-evolving Agents with reflective and memory-augmented abilities](https://mlsanity.com/paper/2409.00872/) (2024)
- [Differentiable Subset Pruning of Transformer Heads](https://mlsanity.com/paper/2108.04657/) (2021)
- [Differentiable DAG Sampling](https://mlsanity.com/paper/2203.08509/) (2022)
- [VX2TEXT: End-to-End Learning of Video-Based Text Generation From Multimodal Inputs](https://mlsanity.com/paper/2101.12059/) (2021)
- [EfficientZero V2: Mastering Discrete and Continuous Control with Limited Data](https://mlsanity.com/paper/2403.00564/) (2024)
- [Stochastic Batch Acquisition: A Simple Baseline for Deep Active Learning](https://mlsanity.com/paper/2106.12059/) (2021)
- [Structure Learning with Continuous Optimization: A Sober Look and Beyond](https://mlsanity.com/paper/2304.02146/) (2023)
- [SIMPLE: A Gradient Estimator for k-Subset Sampling](https://mlsanity.com/paper/2210.01941/) (2022)
- [Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement](https://mlsanity.com/paper/2403.15180/) (2024)
- [Adaptive Slot Attention: Object Discovery with Dynamic Slot Number](https://mlsanity.com/paper/2406.09196/) (2024)
- [Tell What You Hear From What You See -- Video to Audio Generation Through Text](https://mlsanity.com/paper/2411.05679/) (2024)
- [Optimizing Temperature for Language Models with Multi-Sample Inference](https://mlsanity.com/paper/2502.05234/) (2025)
- [You should evaluate your language model on marginal likelihood over tokenisations](https://mlsanity.com/paper/2109.02550/) (2021)

## Abstract (arXiv)

The well-known Gumbel-Max trick for sampling from a categorical distribution can be extended to sample k elements without replacement. We show how to implicitly apply this 'Gumbel-Top-k' trick on a factorized distribution over sequences, allowing to draw exact samples without replacement using a Stochastic Beam Search. Even for exponentially large domains, the number of model evaluations grows only linear in k and the maximum sampled sequence length. The algorithm creates a theoretical connection between sampling and (deterministic) beam search and can be used as a principled intermediate alternative. In a translation task, the proposed method compares favourably against alternatives to obtain diverse yet good quality translations. We show that sequences sampled without replacement can be used to construct low-variance estimators for expected sentence-level BLEU score and model entropy.