mlsanityData to 14 Oct 2026

Arithmetic Sampling: Parallel Diverse Decoding for Large Language Models

arXiv 2210.15458 ↗First posted 18 Oct 2022cs.CL cs.LG stat.MLcited by 19

Not on the map. Why?

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%.

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

20 of 30 references.

References · 20

  1. 2020Language Models are Few-Shot Learnerscited by 32,419
  2. 2022Training language models to follow instructions with human feedbackcited by 15,971
  3. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,599
  4. 2017Deep reinforcement learning from human preferencescited by 3,912
  5. 2019The Curious Case of Neural Text Degenerationcited by 2,916
  6. 2020Learning to summarize from human feedbackcited by 2,588
  7. 2016Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translationcited by 1,475
  8. 2018Hierarchical Neural Story Generationcited by 1,193
  9. 2015Sequence Level Training with Recurrent Neural Networkscited by 576
  10. 2019Neural Text Generation with Unlikelihood Trainingcited by 503
  11. 2019Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacementcited by 211
  12. 2022Scaling Up Models and Data with textttt5x and textttseqiocited by 187
8 more
  1. 2014Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernelscited by 42
  2. 2018Quasi-Monte Carlo Variational Inferencecited by 24
  3. 2015Language Models for Image Captioning: The Quirks and What Workscited by 19
  4. 2016Noisy Parallel Approximate Decoding for Conditional Recurrent Language Modelcited by 18
  5. 2021Determinantal Beam Searchcited by 18
  6. 2021Implicit Unlikelihood Training: Improving Neural Text Generation with Reinforcement Learningcited by 16
  7. 2021Conditional Poisson Stochastic Beam Searchcited by 11
  8. 2021Attention-based Contextual Language Model Adaptation for Speech Recognitioncited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 7; 2025: 3; 2026: 9.

19 papers.

Sort:

By area:

  1. 2024Probabilistic Inference in Language Models via Twisted Sequential Monte Carlocited by 90
  2. 2024Detecting Machine-Generated Texts by Multi-Population Aware Optimization for Maximum Mean Discrepancycited by 20
  3. 2024Training LLMs over Neurally Compressed Textcited by 17
  4. 2024Conformal Generative Modeling with Improved Sample Efficiency through Sequential Greedy Filteringcited by 10
  5. 2025Semantic-guided Diverse Decoding for Large Language Modelcited by 9
  6. 2024Priority Sampling of Large Language Models for Compilerscited by 8
  7. 2025p-less Sampling: A Robust Hyperparameter-Free Approach for LLM Decodingcited by 5
  8. 2026Annotations Mitigate Post-Training Mode Collapsecited by 5
  9. 2024Unused information in token probability distribution of generative LLM: improving LLM reading comprehension through calculation of expected valuescited by 4
  10. 2024Quasi-random Multi-Sample Inference for Large Language Modelscited by 4
  11. 2025Advancing Decoding Strategies: Enhancements in Locally Typical Sampling for LLMscited by 4
  12. 2026When are likely answers right? On Sequence Probability and Correctness in LLMscited by 4
7 more
  1. 2026Decoding as Optimisation on the Probability Simplex: From Top-K to Top-P (Nucleus) to Best-of-K Samplerscited by 2
  2. 2026Efficient Test-Time Inference via Deterministic Exploration of Truncated Decoding Treescited by 1
  3. 2026DecompressionLM: Deterministic, Diagnostic, and Zero-Shot Concept Graph Extraction from Language Modelscited by 0
  4. 2026Improving the Diversity of LLM Outputs without a Trade-offcited by 0
  5. 2026Composable Decoding on the Probability Simplex: Theory and Implementationcited by 0
  6. 2026Self-Repulsive Sampling for Diffusion Language Modelscited by 0
  7. 2026Truncation Samplers Are Nested: Comparing Decoding Rules Is a Measurement Problemcited by 0