mlsanityData to 7 Oct 2026

Parallel Sampling via Counting

arXiv 2408.09442 ↗First posted 18 Aug 2024cs.DS cs.AI cs.LGcited by 7

Not on the map. Why?

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.

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

Builds on

19 of 43 references.

References · 19

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2020Language Models are Few-Shot Learnerscited by 32,199
  4. 2019XLNet: Generalized Autoregressive Pretraining for Language Understandingcited by 2,801
  5. 2016Categorical Reparameterization with Gumbel-Softmaxcited by 2,708
  6. 2022Fast Inference from Transformers via Speculative Decodingcited by 1,615
  7. 2023Accelerating Large Language Model Decoding with Speculative Samplingcited by 975
  8. 2016Pixel Recurrent Neural Networkscited by 814
  9. 2023Parallel Sampling of Diffusion Modelscited by 112
  10. 2022Training and Inference on Any-Order Autoregressive Models the Right Waycited by 64
  11. 2020Accelerating Feedforward Computation via Parallel Nonlinear Equation Solvingcited by 51
  12. 2018An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximationcited by 13
7 more
  1. 2020Predictive Sampling with Forecasting Autoregressive Modelscited by 10
  2. 2020A polynomial lower bound on adaptive complexity of submodular maximizationcited by 4
  3. 2020Sampling Arborescences in Parallelcited by 3
  4. 2023Parallelising Glauber dynamicscited by 3
  5. 2021A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersectioncited by 1
  6. 2022Quadratic Speedups in Parallel Sampling from Determinantal Distributionscited by 1
  7. 2022Improved Lower Bounds for Submodular Function Minimizationcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 5; 2026: 2.

7 papers.

  1. 2025Accelerating Diffusion LLMs via Adaptive Parallel Decodingcited by 108
  2. 2025Optimal Inference Schedules for Masked Diffusion Modelscited by 25
  3. 2025From Bits to Rounds: Parallel Decoding with Exploration for Diffusion Language Modelscited by 22
  4. 2025Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculationcited by 11
  5. 2025Parallel Sampling via Autospeculationcited by 5
  6. 2026A Mathematical Introduction to Diffusion Modelscited by 1
  7. 2026Conditional Total Correlation and the Serial Depth of Adaptive Parallel Samplingcited by 1