按年被提到
20242024 · 2 次2026
大模型与语言模型›量化、解码与分词·arXiv:2410.03170 · cs.CL

Autoregressive Large Language Models are Computationally Universal

Dale Schuurmans, Hanjun Dai, Francesco Zanini · 2024
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2024-10-19 · 最近 2024-12-24
2不同的人
2活跃月份
2讨论串
9被引(OpenAlex)
arXiv 摘要(候选层不写导读)

We show that autoregressive decoding of a transformer-based language model can realize universal computation, without external intervention or modification of the model's weights. Establishing this result requires understanding how a language model can process arbitrarily long inputs using a bounded context. For this purpose, we consider a generalization of autoregressive decoding where, given a long input, emitted tokens are appended to the end of the sequence as the context window advances. We first show that the resulting system corresponds to a classical model of computation, a Lag system, that has long been known to be computationally universal. By leveraging a new proof, we show that a universal Turing machine can be simulated by a Lag system with 2027 production rules. We then investigate whether an existing large language model can simulate the behaviour of such a universal Lag system. We give an affirmative answer by showing that a single system-prompt can be developed for gemini-1.5-pro-001 that drives the model, under deterministic (greedy) decoding, to correctly apply each of the 2027 production rules. We conclude that, by the Church-Turing thesis, prompted gemini-1.5-pro-001 with extended autoregressive (greedy) decoding is a general purpose computer.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论br0tl1 · 2024-12

“I think that's an oversimplification. LLMs have a limited context window of tokens. But that isn't necessarily a limitation: it's been proven that a LLM can simulate any algorithm even with a limited context window (https://arxiv.org/abs/2410.03170), making it computationally universal. Even if that weren't true, the context windows can be quite large an…”

Can AI do maths yet? Thoughts from a mathematician原评论 ↗
被提交为 story · 1 次