Limitations on Autoregressive Token Generation via Sequential Sampling

Gal Arnon; Andrej Bogdanov; Paul Lou; Giulio Malavolta; Alon Rosen; Lorenzo Taschin

cs.ITOct 10, 2026

Limitations on Autoregressive Token Generation via Sequential Sampling

Authors: Gal Arnon, Andrej Bogdanov, Paul Lou, Giulio Malavolta, Alon Rosen, Lorenzo Taschin

Organizations: NTT Research · University of Ottawa · Bocconi University

Abstract

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(2^{k})$ 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.

Figures & tables

Panel of Figure 1 — Figure 1: A three-token sequential sampler.

Autoregressive Generation

Autoregressive generation creates structured outputs step by step, conditioning each prediction on what has already been generated.

See all 109 papers

Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End
Apr 13, 2026Steve Hanneke, Idan Mehalel, Shay MoranCoT Supervision Sample Complexity
Purdue University · The Hebrew University · Technion and Google Research
Watermarkable Multi-Draft Speculative Sampling via Poisson Processes
Sep 18, 2026Yanxiao Liu, Sicheng Wan, Zhan Gao +1Speculative Decoding LLM Inference Acceleration
Imperial College London · University of Washington
Seed Hijacking of LLM Sampling and Quantum Random Number Defense
May 8, 2026Ziyang You, Xiaoke Yang, Zhanling Fan +3LLM Backdoor Attacks LLM Security
School of Electronic, Electrical and Physics, Fujian University of Technology, Fuzhou 350118, China · School of Humanities, Fujian University of Technology, Fuzhou 350118, China · Department of Investigation, Fujian Police College, Fuzhou 350007, China +1

Apr 13, 2026J/K move · Enter open · S save

Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End

Steve Hanneke, Idan Mehalel, Shay Moran

Purdue University · The Hebrew University · Technion and Google Research

CoT Supervision Sample Complexity Autoregressive Language Modeling

Open paper AskPDF arXiv

Modern large language models generate text autoregressively, producing tokens one at a time. To study the learnability of such systems, Joshi et al. (COLT 2025) introduced a PAC-learning framework for next-token generators, the primitive underlying autoregressive models. In this framework, an unknown next-token generator maps a sequence of tokens to the next token and is iteratively applied for

T

steps, producing a chain of tokens whose final token constitutes the model's output. The learning task is to learn the input-output mapping induced by this autoregressive process. Depending on the available supervision, training examples may reveal only the final output (End-to-End supervision) or the entire generated chain (Chain-of-Thought supervision). This raises two natural questions: how the sample complexity depends on the generation length

T

, and how much Chain-of-Thought supervision can reduce this dependence. In this work we give a nearly complete answer to both questions by uncovering a taxonomy of how the sample complexity scales with

T

. For End-to-End learning, we show that the landscape is remarkably rich: subject to mild conditions, essentially any growth rate

r(T)

between constant and linear can arise as the sample complexity, and combined with the linear upper bound of Joshi et al., this yields an essentially complete characterization. In contrast, under Chain-of-Thought supervision we show that the sample complexity is independent of

T

, demonstrating that access to intermediate reasoning steps can eliminate the dependence on the generation length altogether. Our analysis introduces new combinatorial tools, and as corollaries we resolve several open questions posed by Joshi et al. regarding the dependence of learnability on the generation length and the role of Chain-of-Thought supervision.

Abstract

Autoregressive Generation

Explore similar work

Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End

Watermarkable Multi-Draft Speculative Sampling via Poisson Processes

Seed Hijacking of LLM Sampling and Quantum Random Number Defense