# Limitations on Autoregressive Token Generation via Sequential Sampling

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 20 references that are in the map.
- First posted on arXiv 10 Oct 2026.

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

- [Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions](https://mlsanity.com/paper/2502.06768/) (2025)
- [Insertion Transformer: Flexible Sequence Generation via Insertion Operations](https://mlsanity.com/paper/1902.03249/) (2019)
- [Limitations of Autoregressive Models and Their Alternatives](https://mlsanity.com/paper/2010.11939/) (2020)
- [An improper estimator with optimal excess risk in misspecified density estimation and logistic regression](https://mlsanity.com/paper/1912.10784/) (2019)
- [Concentration Bounds for Discrete Distribution Estimation in KL Divergence](https://mlsanity.com/paper/2302.06869/) (2023)
- [On Powerful Ways to Generate: Autoregression, Diffusion, and Beyond](https://mlsanity.com/paper/2510.06190/) (2025)
- [Diffusion Language Models are Provably Optimal Parallel Samplers](https://mlsanity.com/paper/2512.25014/) (2025)
- [Language Modeling is Monotone Compression](https://mlsanity.com/paper/2610.11031/) (2026)

## Abstract (arXiv)

We study autoregressive token generation through the notion of sequential samplers: A circuit that samples the next symbol only given the previous ones and possibly a small amount of state. We show that (1) a sequential sampler with k bits of state can be simulated by a stateless one at a roughly O(2k) size overhead; (2) efficient insertional sampling (Stern, Chan, Kiros, Uszkoreit, ICML 2019) is more powerful than efficient sequential sampling in any fixed order; (3) sequential samplers with small state cannot establish certain forms of covert cryptographic channels. Result (1), together with the pseudoentropy vs. sequential sampleability duality of Vadhan and Zheng (STOC 2012), characterizes efficient sequential sampleability with small state. Result (3) provides a potential safety mechanism against subliminal coordination among malicious LLM agents.