mlsanityData to 14 Oct 2026

Limitations on Autoregressive Token Generation via Sequential Sampling

arXiv 2610.14615 ↗First posted 10 Oct 2026cs.IT cs.AI cs.CRcited by 0

Not on the map. Why?

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.

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

8 of 20 references.

References · 8

  1. 2025Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusionscited by 214
  2. 2019Insertion Transformer: Flexible Sequence Generation via Insertion Operationscited by 125
  3. 2020Limitations of Autoregressive Models and Their Alternativescited by 55
  4. 2019An improper estimator with optimal excess risk in misspecified density estimation and logistic regressioncited by 25
  5. 2023Concentration Bounds for Discrete Distribution Estimation in KL Divergencecited by 7
  6. 2025On Powerful Ways to Generate: Autoregression, Diffusion, and Beyondcited by 6
  7. 2025Diffusion Language Models are Provably Optimal Parallel Samplerscited by 6
  8. 2026Language Modeling is Monotone Compressioncited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Controlled Decoding Attacks on Black-Box LLMs
  2. 2026Seed Hijacking of LLM Sampling and Quantum Random Number Defense
  3. 2025The Coding Limits of Robust Watermarking for Generative Models
  4. 2026MemLineage: Lineage-Guided Enforcement for LLM Agent Memory
  5. 2025An Efficient Private GPT Never Autoregressively Decodes
  6. 2026Step-Wise Refusal Dynamics in Autoregressive and Diffusion Language Models
  7. 2026Improving the Trade-off Between Watermark Strength and Speculative Sampling Efficiency for Language Models
  8. 2025Membership Inference Attacks on Sequence Models