# Incremental Sampling Without Replacement for Sequence Models

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Feb 2020.

## Built on by (most cited first, 23 of 23)

- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement](https://mlsanity.com/paper/2403.15180/) (2024)
- [Determinantal Beam Search](https://mlsanity.com/paper/2106.07400/) (2021)
- [CrossBeam: Learning to Search in Bottom-Up Program Synthesis](https://mlsanity.com/paper/2203.10452/) (2022)
- [Conditional Poisson Stochastic Beam Search](https://mlsanity.com/paper/2109.11034/) (2021)
- [Priority Sampling of Large Language Models for Compilers](https://mlsanity.com/paper/2402.18734/) (2024)
- [Scaling Neural Program Synthesis with Distribution-based Search](https://mlsanity.com/paper/2110.12485/) (2021)
- [LambdaBeam: Neural Program Search with Higher-Order Functions and Lambdas](https://mlsanity.com/paper/2306.02049/) (2023)
- [GraphXForm: Graph transformer for computer-aided molecular design](https://mlsanity.com/paper/2411.01667/) (2024)
- [Predictive Querying for Autoregressive Neural Sequence Models](https://mlsanity.com/paper/2210.06464/) (2022)
- [Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization](https://mlsanity.com/paper/2407.17206/) (2024)
- [Unbiased and Efficient Sampling of Dependency Trees](https://mlsanity.com/paper/2205.12621/) (2022)
- [AbstractBeam: Enhancing Bottom-Up Program Synthesis using Library Learning](https://mlsanity.com/paper/2405.17514/) (2024)
- [Knowledge Transfer for Pseudo-code Generation from Low Resource Programming Language](https://mlsanity.com/paper/2303.09062/) (2023)
- [Efficient Test-Time Inference via Deterministic Exploration of Truncated Decoding Trees](https://mlsanity.com/paper/2604.20500/) (2026)
- [Low-Variance Policy Gradient Estimation with World Models](https://mlsanity.com/paper/2010.15622/) (2020)
- [Efficient Sampling of Dependency Structures](https://mlsanity.com/paper/2109.06521/) (2021)
- [Searching for Better Database Queries in the Outputs of Semantic Parsers](https://mlsanity.com/paper/2210.07201/) (2022)
- [Towards Model-Agnostic Posterior Approximation for Fast and Accurate Variational Autoencoders](https://mlsanity.com/paper/2403.08941/) (2024)
- [Scaling Automatic Extraction of Pseudocode](https://mlsanity.com/paper/2406.04635/) (2024)
- [Sample Efficient Generative Molecular Optimization with Joint Self-Improvement](https://mlsanity.com/paper/2602.10984/) (2026)
- [Rank-Conditioned Sample Reuse for the Plackett--Luce Best-of-K Objective](https://mlsanity.com/paper/2607.11146/) (2026)
- [Improving the Diversity of LLM Outputs without a Trade-off](https://mlsanity.com/paper/2609.33038/) (2026)

## Abstract (arXiv)

Sampling is a fundamental technique, and sampling without replacement is often desirable when duplicate samples are not beneficial. Within machine learning, sampling is useful for generating diverse outputs from a trained model. We present an elegant procedure for sampling without replacement from a broad class of randomized programs, including generative neural models that construct outputs sequentially. Our procedure is efficient even for exponentially-large output spaces. Unlike prior work, our approach is incremental, i.e., samples can be drawn one at a time, allowing for increased flexibility. We also present a new estimator for computing expectations from samples drawn without replacement. We show that incremental sampling without replacement is applicable to many domains, e.g., program synthesis and combinatorial optimization.