# Parallel Sampling via Counting

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 43 references that are in the map.
- First posted on arXiv 18 Aug 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Pixel Recurrent Neural Networks](https://mlsanity.com/paper/1601.06759/) (2016)
- [Parallel Sampling of Diffusion Models](https://mlsanity.com/paper/2305.16317/) (2023)
- [Training and Inference on Any-Order Autoregressive Models the Right Way](https://mlsanity.com/paper/2205.13554/) (2022)
- [Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving](https://mlsanity.com/paper/2002.03629/) (2020)
- [An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation](https://mlsanity.com/paper/1804.06355/) (2018)
- [Predictive Sampling with Forecasting Autoregressive Models](https://mlsanity.com/paper/2002.09928/) (2020)
- [A polynomial lower bound on adaptive complexity of submodular maximization](https://mlsanity.com/paper/2002.09130/) (2020)
- [Sampling Arborescences in Parallel](https://mlsanity.com/paper/2012.09502/) (2020)
- [Parallelising Glauber dynamics](https://mlsanity.com/paper/2307.07131/) (2023)
- [A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection](https://mlsanity.com/paper/2111.07474/) (2021)
- [Quadratic Speedups in Parallel Sampling from Determinantal Distributions](https://mlsanity.com/paper/2203.11190/) (2022)
- [Improved Lower Bounds for Submodular Function Minimization](https://mlsanity.com/paper/2207.04342/) (2022)

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

- [Accelerating Diffusion LLMs via Adaptive Parallel Decoding](https://mlsanity.com/paper/2506.00413/) (2025)
- [Optimal Inference Schedules for Masked Diffusion Models](https://mlsanity.com/paper/2511.04647/) (2025)
- [From Bits to Rounds: Parallel Decoding with Exploration for Diffusion Language Models](https://mlsanity.com/paper/2511.21103/) (2025)
- [Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation](https://mlsanity.com/paper/2505.03983/) (2025)
- [Parallel Sampling via Autospeculation](https://mlsanity.com/paper/2511.07869/) (2025)
- [A Mathematical Introduction to Diffusion Models](https://mlsanity.com/paper/2607.01693/) (2026)
- [Conditional Total Correlation and the Serial Depth of Adaptive Parallel Sampling](https://mlsanity.com/paper/2608.25505/) (2026)
- [Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure](https://mlsanity.com/paper/2609.37841/) (2026)

## Abstract (arXiv)

We show how to use parallelization to speed up sampling from an arbitrary distribution μ on a product space [q]n, given oracle access to counting queries: mathbbPX~ μ[XS=σS] for any Ssubseteq [n] and σS ∈ [q]S. Our algorithm takes O(n2/3· operatornamepolylog(n,q)) parallel time, to the best of our knowledge, the first sublinear in n runtime for arbitrary distributions. Our results have implications for sampling in autoregressive models. Our algorithm directly works with an equivalent oracle that answers conditional marginal queries mathbbPX~ μ[Xi=σi;vert; XS=σS], whose role is played by a trained neural network in autoregressive models. This suggests a roughly n1/3-factor speedup is possible for sampling in any-order autoregressive models. We complement our positive result by showing a lower bound of widetildeOmega(n1/3) for the runtime of any parallel sampling algorithm making at most operatornamepoly(n) queries to the counting oracle, even for q=2.