arXiv：cs.AI· Gal Arnon, Andrej Bogdanov, Paul Lou, Giulio Malavolta, Alon Rosen, Lorenzo Taschin·· 16 小时前
自回归 token 生成的局限：顺序采样器研究
Limitations on Autoregressive Token Generation via Sequential Sampling
AI 导读
研究通过“顺序采样器”（仅凭前序符号和少量状态采样下一符号的电路）分析自回归 token 生成，证明带 k bits 状态的顺序采样器可由无状态采样器以约 O(2^k) 规模开销模拟。结果还表明高效插入式采样（Stern 等，ICML 2019）强于任意固定顺序的高效顺序采样，且小状态顺序采样器无法建立某些形式的隐蔽密码信道，为防范恶意 LLM 智能体间的潜意识协同提供了潜在安全机制。
正文
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.
| Comments: | In submission to ICLR 2027 |
| Subjects: | Information Theory (cs.IT); Artificial Intelligence (cs.AI); Cryptography and Security (cs.CR) |
| Cite as: | arXiv:2610.14615 [cs.IT] |
| (or arXiv:2610.14615v1 [cs.IT] for this version) | |
| https://doi.org/10.48550/arXiv.2610.14615 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Paul Lou [view email]
[v1]
Sat, 10 Oct 2026 05:59:16 UTC (6,673 KB)
来源：arXiv：cs.AI · arxiv.org