# Arithmetic Sampling: Parallel Diverse Decoding for Large Language Models

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 30 references that are in the map.
- First posted on arXiv 18 Oct 2022.

## Builds on (most cited first, 20 of 20)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Learning to summarize from human feedback](https://mlsanity.com/paper/2009.01325/) (2020)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [Sequence Level Training with Recurrent Neural Networks](https://mlsanity.com/paper/1511.06732/) (2015)
- [Neural Text Generation with Unlikelihood Training](https://mlsanity.com/paper/1908.04319/) (2019)
- [Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement](https://mlsanity.com/paper/1903.06059/) (2019)
- [Scaling Up Models and Data with textttt5x and textttseqio](https://mlsanity.com/paper/2203.17189/) (2022)
- [Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels](https://mlsanity.com/paper/1412.8293/) (2014)
- [Quasi-Monte Carlo Variational Inference](https://mlsanity.com/paper/1807.01604/) (2018)
- [Language Models for Image Captioning: The Quirks and What Works](https://mlsanity.com/paper/1505.01809/) (2015)
- [Noisy Parallel Approximate Decoding for Conditional Recurrent Language Model](https://mlsanity.com/paper/1605.03835/) (2016)
- [Determinantal Beam Search](https://mlsanity.com/paper/2106.07400/) (2021)
- [Implicit Unlikelihood Training: Improving Neural Text Generation with Reinforcement Learning](https://mlsanity.com/paper/2101.04229/) (2021)
- [Conditional Poisson Stochastic Beam Search](https://mlsanity.com/paper/2109.11034/) (2021)
- [Attention-based Contextual Language Model Adaptation for Speech Recognition](https://mlsanity.com/paper/2106.01451/) (2021)

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

- [Probabilistic Inference in Language Models via Twisted Sequential Monte Carlo](https://mlsanity.com/paper/2404.17546/) (2024)
- [Detecting Machine-Generated Texts by Multi-Population Aware Optimization for Maximum Mean Discrepancy](https://mlsanity.com/paper/2402.16041/) (2024)
- [Training LLMs over Neurally Compressed Text](https://mlsanity.com/paper/2404.03626/) (2024)
- [Conformal Generative Modeling with Improved Sample Efficiency through Sequential Greedy Filtering](https://mlsanity.com/paper/2410.01660/) (2024)
- [Semantic-guided Diverse Decoding for Large Language Model](https://mlsanity.com/paper/2506.23601/) (2025)
- [Priority Sampling of Large Language Models for Compilers](https://mlsanity.com/paper/2402.18734/) (2024)
- [p-less Sampling: A Robust Hyperparameter-Free Approach for LLM Decoding](https://mlsanity.com/paper/2509.23234/) (2025)
- [Annotations Mitigate Post-Training Mode Collapse](https://mlsanity.com/paper/2605.09995/) (2026)
- [Unused information in token probability distribution of generative LLM: improving LLM reading comprehension through calculation of expected values](https://mlsanity.com/paper/2406.10267/) (2024)
- [Quasi-random Multi-Sample Inference for Large Language Models](https://mlsanity.com/paper/2411.06251/) (2024)
- [Advancing Decoding Strategies: Enhancements in Locally Typical Sampling for LLMs](https://mlsanity.com/paper/2506.05387/) (2025)
- [When are likely answers right? On Sequence Probability and Correctness in LLMs](https://mlsanity.com/paper/2606.27359/) (2026)
- [Decoding as Optimisation on the Probability Simplex: From Top-K to Top-P (Nucleus) to Best-of-K Samplers](https://mlsanity.com/paper/2602.18292/) (2026)
- [Efficient Test-Time Inference via Deterministic Exploration of Truncated Decoding Trees](https://mlsanity.com/paper/2604.20500/) (2026)
- [DecompressionLM: Deterministic, Diagnostic, and Zero-Shot Concept Graph Extraction from Language Models](https://mlsanity.com/paper/2602.00377/) (2026)
- [Improving the Diversity of LLM Outputs without a Trade-off](https://mlsanity.com/paper/2609.33038/) (2026)
- [Composable Decoding on the Probability Simplex: Theory and Implementation](https://mlsanity.com/paper/2609.34992/) (2026)
- [Self-Repulsive Sampling for Diffusion Language Models](https://mlsanity.com/paper/2609.39560/) (2026)
- [Truncation Samplers Are Nested: Comparing Decoding Rules Is a Measurement Problem](https://mlsanity.com/paper/2610.15570/) (2026)

## Abstract (arXiv)

Decoding methods for large language models often trade-off between diversity of outputs and parallelism of computation. Methods such as beam search and Gumbel top-k sampling can guarantee a different output for each element of the beam, but are not easy to parallelize. Alternatively, methods such as temperature sampling and its modifications (top-k sampling, nucleus sampling, typical decoding, and others), are embarrassingly parallel, but have no guarantees about duplicate samples. We present a framework for sampling according to an arithmetic code book implicitly defined by a large language model, compatible with common sampling variations, with provable beam diversity under certain conditions, as well as being embarrassingly parallel and providing unbiased and consistent expectations from the original model. We demonstrate the effectiveness of our approach on WMT machine translation, more than halving the standard deviation when estimating expected BLEU score reward, and closing the BLEU score gap between independent sampling and beam search by up to 63%.