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

Wouter Kool, Herke van Hoof, Max Welling

Abstract

Generating high-quality, diverse sequences is a fundamental challenge in natural language processing. Traditional methods like beam search are deterministic and lack diversity, while random sampling often produces redundant duplicates. This paper introduces Stochastic Beam Search (SBS), a principled algorithm that extends the Gumbel-Max trick to sample $k$ unique sequences without replacement. By combining the probabilistic rigor of importance sampling with the efficiency of beam search, SBS provides a powerful framework for generating diverse outputs and building low-variance statistical estimators.

Introduction

In sequence-to-sequence tasks such as machine translation or image captioning, the goal is often to explore the output space for high-probability sequences. Currently, practitioners rely on two primary paradigms:

  1. Beam Search: A heuristic, deterministic search that identifies high-probability sequences. While efficient, it lacks a clear probabilistic interpretation and often suffers from low diversity.
  2. Random Sampling: Drawing sequences according to their model probability. While theoretically grounded, sampling with replacement in large spaces frequently yields duplicate sequences, which is computationally wasteful.

The ideal solution is to sample $k$ unique sequences (sampling without replacement) from the exponentially large space of possible outputs. While rejection sampling can achieve this, it is prohibitively expensive. This paper proposes a novel approach that bridges the gap between search and sampling.

Methodology: The Gumbel-Top-$k$ Trick

The authors' core contribution is the application of the Gumbel-Top-$k$ trick to sequence trees. This method generalizes the Gumbel-Max trick—which samples a single item by adding Gumbel noise to log-probabilities—to the task of sampling $k$ items without replacement.

Stochastic Beam Search (SBS)

The SBS algorithm works by adding Gumbel-distributed noise to the log-probabilities of every potential branch in the sequence tree. By performing a beam search to find the $k$ sequences with the highest "perturbed" scores, the algorithm implicitly draws an ordered sample without replacement.

Visualization of the Stochastic Beam Search process, showing how Gumbel noise is propagated and nodes are selected or pruned.

Key technical features include:

  • Top-Down Sampling: Gumbel noise is propagated down the tree such that only visited branches need to be instantiated, maintaining efficiency.
  • Computational Efficiency: The algorithm's complexity grows linearly with the number of samples $k$ and the sequence length, making it as scalable as standard beam search.

Experimental Evaluation

The method was evaluated on the WMT14 English-French (newstest2014) benchmark using a pre-trained convolutional sequence-to-sequence model.

Key Results

The experiments focused on the trade-off between translation quality (BLEU score) and output diversity (unique n-grams).

BLEU score vs. Diversity for various sampling methods across different beam sizes (k=5, 10, 20).
  • Superior Diversity-Quality Trade-off: SBS consistently outperformed "Diverse Beam Search" (DBS). For any given level of diversity, SBS achieved higher mean and maximum BLEU scores.
  • Statistical Estimation: Because SBS is a principled sampling method, it can be used for Importance Sampling. The authors demonstrated that the normalized SBS estimator has significantly lower variance than standard Monte Carlo sampling when estimating metrics like expected sentence-level BLEU.
  • Efficiency: SBS eliminates the "duplicate" problem inherent in standard sampling without the overhead of rejection sampling.

Discussion and Future Work

While SBS provides a rigorous framework, it does have limitations. Common NMT heuristics like length normalization and early stopping can break the exact probabilistic interpretation of the Gumbel-Top-$k$ trick. In this study, these were disabled for theoretical consistency, though they can still be applied as heuristics in practice.

The probabilistic interpretation of beam search introduced here opens new avenues for research, particularly in developing training objectives that optimize sequence-level metrics more effectively. By providing a "missing link" between deterministic search and random sampling, SBS allows for fine-grained control over generation diversity via a temperature parameter while maintaining search efficiency.

Summary updated

BibTeX
@inproceedings{kool2019stochastic,
  author = {Wouter Kool and Herke van Hoof and Max Welling},
  title = {{Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=sTbbKGrDqLM},
}
Figure