# Reviving Any-Subset Autoregressive Models with Principled Parallel Sampling and Speculative Decoding

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion LLM and MoE inference, one of 12 directions in Efficient LLM inference and serving.
- Builds on 39 of its 46 references that are in the map.
- First posted on arXiv 29 Apr 2025.

## Placed in

- Efficient LLM inference and serving / [Diffusion LLM and MoE inference](https://mlsanity.com/inference/diffusion-llm-and-moe-inference/)

## Builds on (most cited first, 30 of 39)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [HuggingFace's Transformers: State-of-the-art Natural Language Processing](https://mlsanity.com/paper/1910.03771/) (2019)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Decoupled Weight Decay Regularization](https://mlsanity.com/paper/1711.05101/) (2017)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Large Language Diffusion Models](https://mlsanity.com/paper/2502.09992/) (2025)
- [Simple and Effective Masked Diffusion Language Models](https://mlsanity.com/paper/2406.07524/) (2024)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [StarCoder: may the source be with you!](https://mlsanity.com/paper/2305.06161/) (2023)
- [InCoder: A Generative Model for Code Infilling and Synthesis](https://mlsanity.com/paper/2204.05999/) (2022)
- [A Continuous Time Framework for Discrete Denoising Models](https://mlsanity.com/paper/2205.14987/) (2022)
- [A Corpus and Evaluation Framework for Deeper Understanding of Commonsense Stories](https://mlsanity.com/paper/1604.01696/) (2016)
- [MADE: Masked Autoencoder for Distribution Estimation](https://mlsanity.com/paper/1502.03509/) (2015)
- [LayerSkip: Enabling Early Exit Inference and Self-Speculative Decoding](https://mlsanity.com/paper/2404.16710/) (2024)
- [Break the Sequential Dependency of LLM Inference Using Lookahead Decoding](https://mlsanity.com/paper/2402.02057/) (2024)
- [Scaling Diffusion Language Models via Adaptation from Autoregressive Models](https://mlsanity.com/paper/2410.17891/) (2024)
- [Efficient Training of Language Models to Fill in the Middle](https://mlsanity.com/paper/2207.14255/) (2022)
- [Autoregressive Diffusion Models](https://mlsanity.com/paper/2110.02037/) (2021)
- [Masked Diffusion Models are Secretly Time-Agnostic Masked Models and Exploit Inaccurate Categorical Sampling](https://mlsanity.com/paper/2409.02908/) (2024)
- [Hydra: Sequentially-Dependent Draft Heads for Medusa Decoding](https://mlsanity.com/paper/2402.05109/) (2024)
- [Energy-Based Diffusion Language Models for Text Generation](https://mlsanity.com/paper/2410.21357/) (2024)

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

- [Accelerated Sampling from Masked Diffusion Models via Entropy Bounded Unmasking](https://mlsanity.com/paper/2505.24857/) (2025)
- [Accelerating Diffusion LLMs via Adaptive Parallel Decoding](https://mlsanity.com/paper/2506.00413/) (2025)
- [A Survey on Parallel Text Generation: From Parallel Decoding to Diffusion Language Models](https://mlsanity.com/paper/2508.08712/) (2025)
- [Learning Unmasking Policies for Diffusion Language Models](https://mlsanity.com/paper/2512.09106/) (2025)
- [Set Block Decoding is a Language Model Inference Accelerator](https://mlsanity.com/paper/2509.04185/) (2025)
- [Self-Speculative Masked Diffusions](https://mlsanity.com/paper/2510.03929/) (2025)
- [Enabling Approximate Joint Sampling in Diffusion LMs](https://mlsanity.com/paper/2509.22738/) (2025)
- [Demystifying MaskGIT Sampler and Beyond: Adaptive Order Selection in Masked Diffusion](https://mlsanity.com/paper/2510.04525/) (2025)
- [DUEL: Exact Likelihood for Masked Diffusion via Deterministic Unmasking](https://mlsanity.com/paper/2603.01367/) (2026)
- [Partition Generative Modeling: Masked Modeling Without Masks](https://mlsanity.com/paper/2505.18883/) (2025)
- [S2D2: Fast Decoding for Diffusion LLMs via Training-Free Self-Speculation](https://mlsanity.com/paper/2603.25702/) (2026)
- [Set Diffusion: Interpolating Token Orderings Between Autoregression and Diffusion for Fast and Flexible Decoding](https://mlsanity.com/paper/2607.01775/) (2026)
- [Why Any-Order Autoregressive Models Need Two-Stream Attention: A Structural-Semantic Tradeoff](https://mlsanity.com/paper/2602.16092/) (2026)
- [Diffusion Language Model Parallel Decoding via Product-of-Experts Bridge](https://mlsanity.com/paper/2606.08048/) (2026)
- [AutoIndexer: Flexible-Order Decoding by Training Causal Models on Chains of Edits](https://mlsanity.com/paper/2610.12545/) (2026)

## Abstract (arXiv)

In arbitrary-order language models, it is an open question how to sample tokens in parallel from the correct joint distribution. With discrete diffusion models, the more tokens they generate in parallel, the less their predicted distributions adhere to the originally learned data distribution, as they rely on a conditional independence assumption that only works with infinitesimally small timesteps. We find that a different class of models, any-subset autoregressive models (AS-ARMs), holds the solution. As implied by the name, AS-ARMs can generate tokens in any order, and in parallel. Moreover, AS-ARMs support parallelized joint probability density estimation, allowing them to correct their own parallel-generated token distributions, via our Any-Subset Speculative Decoding (ASSD) algorithm. ASSD provably enables generation of tokens from the correct joint distribution, with the number of neural network calls upper bounded by the number of tokens predicted. We empirically verify that ASSD speeds up language generation, without sacrificing quality. Furthermore, we provide a mathematically justified scheme for training AS-ARMs for generation, and show that AS-ARMs achieve state-of-the-art performance among sub-200M parameter models on infilling benchmark tasks, and nearly match the performance of models 50X larger on code generation. Our theoretical and empirical results indicate that the once-forgotten AS-ARMs are a promising direction of language modeling.