mlsanityData to 14 Oct 2026

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

arXiv 1903.06059 ↗First posted 14 Mar 2019cs.LG stat.MLcited by 211

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 22; 2022: 25; 2023: 29; 2024: 33; 2025: 40; 2026: 62.

211 papers.

Sort:

By area:

  1. 2021Argmax Flows and Multinomial Diffusion: Learning Categorical Distributionscited by 574
  2. 2023Data Selection for Language Models via Importance Resamplingcited by 329
  3. 2022A Contrastive Framework for Neural Text Generationcited by 225
  4. 2023Self-Evaluation Guided Beam Search for Reasoningcited by 196
  5. 2024Streaming Long Video Understanding with Large Language Modelscited by 167
  6. 2023A Reparameterized Discrete Diffusion Model for Text Generationcited by 152
  7. 2026MemSkill: Learning and Evolving Memory Skills for Self-Evolving Agentscited by 142
  8. 2022Truncation Sampling as Language Model Desmoothingcited by 123
  9. 2021Online Coreset Selection for Rehearsal-based Continual Learningcited by 117
  10. 2021Pixel Contrastive-Consistent Semi-Supervised Semantic Segmentationcited by 101
  11. 2024MATES: Model-Aware Data Selection for Efficient Pretraining with Data Influence Modelscited by 100
  12. 2021A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learningcited by 82
38 more
  1. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 71
  2. 2025Revisiting the Test-Time Scaling of o1-like Models: Do they Truly Possess Test-Time Scaling Capabilities?cited by 70
  3. 2024Informed Correctors for Discrete Diffusion Modelscited by 57
  4. 2021Machine Translation Decoding beyond Beam Searchcited by 55
  5. 2022MIST: Multi-modal Iterative Spatial-Temporal Transformer for Long-form Video Question Answeringcited by 55
  6. 2024Self-evolving Agents with reflective and memory-augmented abilitiescited by 52
  7. 2021Differentiable Subset Pruning of Transformer Headscited by 47
  8. 2022Differentiable DAG Samplingcited by 47
  9. 2021VX2TEXT: End-to-End Learning of Video-Based Text Generation From Multimodal Inputscited by 42
  10. 2024EfficientZero V2: Mastering Discrete and Continuous Control with Limited Datacited by 40
  11. 2021Stochastic Batch Acquisition: A Simple Baseline for Deep Active Learningcited by 36
  12. 2023Structure Learning with Continuous Optimization: A Sober Look and Beyondcited by 36
  13. 2022SIMPLE: A Gradient Estimator for k-Subset Samplingcited by 34
  14. 2024Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvementcited by 34
  15. 2024Adaptive Slot Attention: Object Discovery with Dynamic Slot Numbercited by 34
  16. 2024Tell What You Hear From What You See -- Video to Audio Generation Through Textcited by 34
  17. 2025Optimizing Temperature for Language Models with Multi-Sample Inferencecited by 33
  18. 2021You should evaluate your language model on marginal likelihood over tokenisationscited by 30
  19. 2024Stochastic RAG: End-to-End Retrieval-Augmented Generation through Expected Utility Maximizationcited by 29
  20. 2025Learning-Order Autoregressive Models with Application to Molecular Graph Generationcited by 29
  21. 2022AdaProp: Learning Adaptive Propagation for Graph Neural Network based Knowledge Graph Reasoningcited by 28
  22. 2023Graph Deep Learning for Time Series Forecastingcited by 26
  23. 2022Latent Graph Inference using Product Manifoldscited by 23
  24. 2022Sparse Graph Learning from Spatiotemporal Time Seriescited by 22
  25. 2024Revisiting Non-Autoregressive Transformers for Efficient Image Synthesiscited by 22
  26. 2023LightZero: A Unified Benchmark for Monte Carlo Tree Search in General Sequential Decision Scenarioscited by 20
  27. 2021Straight to the Gradient: Learning to Use Novel Tokens for Neural Text Generationcited by 19
  28. 2022Arithmetic Sampling: Parallel Diverse Decoding for Large Language Modelscited by 19
  29. 2023MonoLSS: Learnable Sample Selection For Monocular 3D Detectioncited by 19
  30. 2021Determinantal Beam Searchcited by 18
  31. 2023Neural Latent Geometry Search: Product Manifold Inference via Gromov-Hausdorff-Informed Bayesian Optimizationcited by 18
  32. 2021Efficient Classification of Very Large Images with Tiny Objectscited by 17
  33. 2023On Strengthening and Defending Graph Reconstruction Attack with Markov Chain Approximationcited by 16
  34. 2021Diversity driven Query Rewriting in Search Advertisingcited by 15
  35. 2021NWT: Towards natural audio-to-video generation with representation learningcited by 14
  36. 2022Learning Graph Augmentations to Learn Graph Representationscited by 14
  37. 2023GRASP: A Rehearsal Policy for Efficient Online Continual Learningcited by 14
  38. 2023MiniZero: Comparative Analysis of AlphaZero and MuZero on Go, Othello, and Atari Gamescited by 14

50 most cited of 211 All 211 (JSON)