Back

Auto-Regressive Next-Token Predictors are Universal Learners

Eran Malach

article2024ICML62 citations

Proves that even simple linear next-token predictors trained on chain-of-thought sequences can approximate any efficiently computable Turing machine, demonstrating that the reasoning power of modern language models stems fundamentally from autoregressive supervision rather than specific transformer architectures.

Listen

Modern artificial intelligence heavily relies on massive large language models that perform complex reasoning and problem-solving. A central question facing decision-makers and technical leaders is whether these advanced capabilities stem from complex neural architectures, such as transformers, or from the fundamental training objective of predicting the next token in a sequence. The article addresses this fundamental question to determine what truly drives reasoning performance in machine learning models.

The article demonstrates that the power of modern language models is primarily driven by sequential, step-by-step next-token prediction rather than complex model architectures. It evaluates how basic linear predictors and shallow multi-layer networks perform when trained with intermediate reasoning sequences, commonly known as chain of thought, to show that these simple frameworks can theoretically learn any computation that a standard computer can execute.

To establish these results, the article combines formal mathematical proofs with targeted empirical experiments. The theoretical analysis adapts standard learning theory to the sequential next-token prediction setting, establishing proof that linear predictors can simulate general computer algorithms when provided with intermediate steps. The empirical evaluation tests these principles in practice: a basic linear network is trained on a synthetic short-story dataset across fifty evaluation prompts, and a shallow 775-million-parameter network without attention mechanisms is trained on four-digit multiplication tasks using one hundred million training sequences.

The article presents several key findings. Theoretically, auto-regressive next-token prediction allows simple linear models to approximate any efficiently computable function, provided they receive step-by-step reasoning data. The article also introduces length complexity, showing that the number of intermediate reasoning tokens can be systematically traded against computational and sample complexity. In empirical tests, a shallow four-layer network without attention achieved 96.9% exact accuracy on four-digit multiplication, matching a specialized seven-billion-parameter transformer and substantially outperforming leading commercial models, which achieved approximately 1% to 5% accuracy on direct calculation without intermediate steps. Additionally, a simple linear model trained on short stories produced grammatically sound and coherent text across standard benchmarks.

These findings carry significant strategic implications for machine learning design, computational cost, and resource allocation. They indicate that complex reasoning can be unlocked in smaller, simpler models without relying exclusively on compute-heavy architectures, provided that high-quality intermediate supervision is available. Organizations can potentially achieve high task performance and lower operational latency by investing in rich step-by-step training data rather than solely scaling model parameter counts.

Leaders should focus machine learning strategies on data quality and task decomposition, especially for logical and algorithmic domains. When designing systems for mathematical, symbolic, or multi-step logic tasks, teams should integrate explicit step-by-step supervision into data pipelines rather than assuming larger architectures are necessary. Further work should explore automated generation of intermediate data sequences and investigate the trade-offs of length complexity in production environments.

The primary limitation of this approach is its heavy dependence on detailed intermediate supervision, as generating extensive step-by-step training data can be labor-intensive and costly. Furthermore, the empirical validation focused on controlled domains—short stories and arithmetic—meaning confidence is high for structured algorithmic tasks, but additional validation is required before extending these architectural simplifications to broader, open-ended tasks.

Harvard UniversityKemper Institute for the Study of Natural and Artificial Intelligenceauto-regressive next-token predictorsnext-token predictionuniversal learners
arXiv: 2309.06979
  • Paper: Chain-of-Thought Prompting Elicits Reasoning in Large Language Models, Jason Wei et al. (2022). This foundational work introduced chain-of-thought prompting in autoregressive language models, establishing the empirical reasoning paradigm whose theoretical and architectural necessity is scrutinized in the source paper.
  • Paper: Why think step by step? Reasoning emerges from the locality of experience, Ben Prystawski et al. (2023). This paper establishes how step-by-step intermediate variables reduce estimation bias in autoregressive models, providing essential theoretical and statistical groundwork for understanding why sequential next-token prediction drives reasoning.
  • Paper: Teaching Small Language Models to Reason, Lucie Charlotte Magister et al. (2023). This study demonstrates that small student models can acquire multi-step reasoning when trained on intermediate teacher traces, directly preceding the source paper's thesis that simple autoregressive learners thrive on step-by-step supervision.
  • Paper: Exploring Length Generalization in Large Language Models, Cem Anil et al. (2022). This paper examines how length generalization and sequential scratchpads operate in transformer architectures, directly motivating the source's formal introduction of length complexity in next-token predictors.
  • Paper: Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought, Abulhair Saparov et al. (2023). This formal analysis shows that autoregressive models execute local reasoning steps effectively but struggle with global planning, contextualizing the source's findings on the expressive power and limits of sequential next-token predictors.
  • Paper: Large Language Models are Zero-Shot Reasoners, Takeshi Kojima et al. (2022). This work demonstrates that simple sequential prompting triggers multi-step problem solving in autoregressive models, providing key empirical context for the source's claim that sequential prediction fundamentally unlocks universal computation.
  • Paper: CoT-Valve: Length-Compressible Chain-of-Thought Tuning, Xinyin Ma et al. (2025). This work builds on the trade-offs of intermediate reasoning sequences by introducing parameter-space mechanisms to compress chain-of-thought length while maintaining task accuracy.
  • Paper: Towards System 2 Reasoning in LLMs: Learning How to Think With Meta Chain-of-Thought, Violet Xiang et al. (2025). This paper advances the study of sequential intermediate supervision by training language models to internalize non-linear trial-and-error search and meta-reasoning traces.
  • Paper: s1: Simple test-time scaling, Niklas Muennighoff et al. (2025). This paper operationalizes the test-time length trade-off proven in the source by implementing budget forcing to scale reasoning performance with minimal compute and data.
  • Paper: Training Large Language Models to Reason in a Continuous Latent Space, Shibo Hao et al. (2024). This study extends sequential autoregressive reasoning beyond discrete token sequences by demonstrating how intermediate steps can be computed effectively in a continuous latent space.
  • Paper: Hierarchical Reasoning Model, Guan Wang et al. (2025). This work explores an alternative architectural paradigm for sequential reasoning, using a compact recurrent framework with deep supervision to solve complex planning tasks without token-by-token explicit traces.
  • Paper: Reasoning Models Generate Societies of Thought, Junsol Kim et al. (2026). This study analyzes the internal structure of long autoregressive reasoning traces, showing how complex multi-step generation manifests as simulated multi-perspective dialogue.
  • Paper: Understanding R1-Zero-Like Training: A Critical Perspective, Zichen Liu et al. (2025). This paper examines whether reasoning in autoregressive models emerges autonomously from reinforcement learning or relies on latent capabilities instilled during next-token pre-training.
  • Paper: Efficient Reasoning on the Edge, Yelysei Bondarenko et al. (2026). This work applies the principles of compact reasoning models and length control to edge deployment, demonstrating how to adapt small models under tight compute budgets.
Cover for Auto-Regressive Next-Token Predictors are Universal Learners

Abstract

Large language models display remarkable capabilities in logical and mathematical reasoning, allowing them to solve complex tasks. Interestingly, these abilities emerge in networks trained on the simple task of next-token prediction. In this work, we present a theoretical framework for studying auto-regressive next-token predictors. We demonstrate that even simple models such as linear next-token predictors, trained on Chain-of-Thought (CoT) data, can approximate any function efficiently computed by a Turing machine. We introduce a new complexity measure—length complexity—which measures the number of intermediate tokens in a CoT sequence required to approximate some target function, and analyze the interplay between length complexity and other notions of complexity. Finally, we show experimentally that simple next-token predictors, such as linear networks and shallow Multi-Layer Perceptrons (MLPs), display non-trivial performance on text generation and arithmetic tasks. Our results demonstrate that the power of today's LLMs can be attributed, to a great extent, to the auto-regressive next-token training scheme, and not necessarily to a particular choice of architecture.

Keywords

auto-regressive next-token predictorsnext-token predictionuniversal learnersautoregressive learningAR learnabilityPAC learnabilitynoise-tolerant learningparity learningintermediate supervisionlarge language models

Table of Contents

  • 1. Introduction
  • 2. Related Work
  • 3. Theory
  • 3.1. Learnability Results
  • Linear Decoder
  • 3.2. Approximation Results
  • Approximation Capacity of Linear Hypotheses
  • 3.3. Length Complexity
  • Length Complexity of Parities
  • 4. Experiments
  • 4.1. Tiny Stories
  • 4.2. Multiplication
  • 5. Discussion
  • Impact Statement
  • References
  • A. Proofs
  • B. Additional Figures
  • C. TinyStories GPT-4 Evaluation

Knowls

  1. Knowl 1 — Universal computation from linear next-token prediction

    theoretical result

    For every Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\} computable by a Turing machine in time τ(n)\tau(n), and for every input distribution PP over {0,1}n\{0,1\}^n, the paper constructs a dataset of token sequences whose lengths are polynomial in τ(n)\tau(n) such that efficiently training a linear auto-regressive next-token predictor on this dataset produces a predictor whose final generated token approximates ff with respect to PP. The construction encodes the intermediate computation of a machine realizing ff as chain-of-thought supervision. Thus, the expressive power comes from auto-regressive generation with deterministic argmax decoding and intermediate tokens, rather than from nonlinear hidden layers or a particular architecture.

  2. Knowl 2 — Linear auto-regressive predictors simulate threshold circuits

    theoretical result

    Let f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\} be computed by a Boolean linear-threshold circuit with at most TT gates. A linear auto-regressive predictor can compute ff exactly in TT generated steps. Each generated token represents the output of one circuit gate, and the linear next-token rule at step tt receives the original input bits and the outputs generated at earlier steps. A linear threshold gate x↦1[⟨w,x⟩+b≥0]x\mapsto\mathbf{1}[\langle w,x\rangle+b\ge 0] is implemented by choosing the larger of two linear token scores. The final generated token is the circuit output.

  3. Knowl 3 — Auto-regressive learnability reduces to per-position PAC learning

    theoretical result

    Let D\mathcal{D} be a finite token dictionary, let X=Dn\mathcal{X}=\mathcal{D}^n be the input-context space, and fix a maximum sequence length TT. An auto-regressive hypothesis is a deterministic function h:X×D∗→Dh:\mathcal{X}\times\mathcal{D}^*\to\mathcal{D}. A distribution PP over X×DT\mathcal{X}\times\mathcal{D}^T is realizable by hh when h(x,z<t)=zth(x,z_{<t})=z_t for every t≤Tt\le T with probability one, where z<tz_{<t} is the prefix before token ztz_t. An auto-regressive learner must, from m(ϵ,δ)m(\epsilon,\delta) realizable sequences, output h^\widehat h such that

    Pr⁡(x,z)∼P[∃t≤T:h^(x,z<t)≠zt]≤ϵ\Pr_{(x,z)\sim P}\left[\exists t\le T:\widehat h(x,z_{<t})\ne z_t\right]\le\epsilon

    with probability at least 1−δ1-\delta. If the position-specific classes Ht⊆(X×Dt−1→D)\mathcal{H}_t\subseteq(\mathcal{X}\times\mathcal{D}^{t-1}\to\mathcal{D}) are PAC learnable with sample complexity m(ϵ,δ)m(\epsilon,\delta), then their product class H=H1×⋯×HT\mathcal{H}=\mathcal{H}_1\times\cdots\times\mathcal{H}_T is auto-regressively learnable with sample complexity m(ϵ/T,δ/T)m(\epsilon/T,\delta/T). Polynomial-time PAC learners therefore yield a polynomial-time auto-regressive learner.

  4. Knowl 4 — Linear next-token hypothesis class is efficiently learnable

    model/method

    For a token dictionary D\mathcal{D} with q=∣D∣q=|\mathcal{D}| tokens, choose an embedding ψ:D→Rd\psi:\mathcal{D}\to\mathbb{R}^d. For an input context x∈Dnx\in\mathcal{D}^n and a generated prefix z∈Dtz\in\mathcal{D}^t, let ψ([x,z])∈Rd(n+t)\psi([x,z])\in\mathbb{R}^{d(n+t)} be the concatenated embedding sequence. For each position tt, a weight matrix W∈Rq×d(n+t)W\in\mathbb{R}^{q\times d(n+t)} defines the deterministic next-token predictor

    hW(x,z)=arg max⁡v∈D⟨Wv,ψ([x,z])⟩,h_W(x,z)=\operatorname*{arg\,max}_{v\in\mathcal{D}}\langle W_v,\psi([x,z])\rangle,

    where WvW_v is the row associated with token vv. The position-specific linear class is HtLin={hW:W∈Rq×d(n+t)}\mathcal{H}^{\mathrm{Lin}}_t=\{h_W:W\in\mathbb{R}^{q\times d(n+t)}\}, and the full linear auto-regressive class is HLin=H1Lin×⋯×HTLin\mathcal{H}^{\mathrm{Lin}}=\mathcal{H}^{\mathrm{Lin}}_1\times\cdots\times\mathcal{H}^{\mathrm{Lin}}_T. Each position-specific class is PAC learnable in polynomial time under the paper's margin and surrogate-loss conditions; consequently, the full linear auto-regressive class is efficiently auto-regressively learnable.

  5. Knowl 5 — Teacher-forced learning transfers to final generated outputs

    theoretical result

    For an auto-regressive function hh and input x∈Dnx\in\mathcal{D}^n, define its generated tokens recursively by h(1)(x)=h(x,∅)h^{(1)}(x)=h(x,\varnothing) and

    h(t)(x)=h(x,h(1)(x),…,h(t−1)(x)).h^{(t)}(x)=h\bigl(x,h^{(1)}(x),\ldots,h^{(t-1)}(x)\bigr).

    The function computed by hh after TT steps is h(T)h^{(T)}. If an auto-regressive hypothesis class is learnable from teacher-forced next-token sequences and the training distribution is realizable by some hh in that class, then the learned predictor h^\widehat h has, with probability at least 1−δ1-\delta, a final generated output satisfying

    Pr⁡x∼P[h^(T)(x)≠h(T)(x)]≤ϵ\Pr_{x\sim P}\left[\widehat h^{(T)}(x)\ne h^{(T)}(x)\right]\le\epsilon

    when trained with the sample size required for auto-regressive error ϵ,δ\epsilon,\delta. Therefore, controlling errors on ground-truth prefixes can guarantee agreement during inference, even though inference feeds the predictor's own generated prefixes back into the model.

  6. Knowl 6 — Length complexity measures the required chain-of-thought supervision

    definition

    For a target class F\mathcal{F} of functions Dn→D\mathcal{D}^n\to\mathcal{D} and an auto-regressive hypothesis class H\mathcal{H}, the length complexity is the minimum number TT of intermediate generated tokens such that every f∈Ff\in\mathcal{F} has some h∈Hh\in\mathcal{H} with h(T)(x)=f(x)h^{(T)}(x)=f(x) for every input xx. Under an input distribution PP, approximate length complexity TT requires, for every f∈Ff\in\mathcal{F}, some h∈Hh\in\mathcal{H} satisfying

    Pr⁡x∼P[h(T)(x)≠f(x)]≤ϵ.\Pr_{x\sim P}\left[h^{(T)}(x)\ne f(x)\right]\le\epsilon.

    This measure treats the number of intermediate chain-of-thought tokens as a learning resource separate from sample complexity and computational runtime. The paper emphasizes that universal linear predictors may require polynomially long intermediate computations, making the corresponding supervision costly or impractical; richer hypothesis classes can shorten the sequences at the cost of harder learning.

  7. Knowl 7 — Linear auto-regressive predictors learn arbitrary parities with logarithmic length

    theoretical result

    For Boolean inputs, define the parity class

    Pn={χA:χA(x)=(∑i∈Axi) mod 2, A⊆[n]}.\mathcal{P}_n=\left\{\chi_A:\chi_A(x)=\left(\sum_{i\in A}x_i\right)\bmod 2,\ A\subseteq[n]\right\}.

    Because every parity on nn bits has a linear-threshold circuit of size O(log⁡n)O(\log n), the linear auto-regressive class computes every function in Pn\mathcal{P}_n with length complexity O(log⁡n)O(\log n). Since the linear auto-regressive class is efficiently learnable under teacher-forced next-token supervision, parity functions become efficiently learnable when the training sequences contain only O(log⁡n)O(\log n) intermediate tokens. This differs from ordinary linear supervised learning, whose predictors cannot represent or approximate the parity class in the corresponding standard setting.

  8. Knowl 8 — Richer per-step parity classes trade computational difficulty for shorter sequences

    theoretical result

    For k≤nk\le n, let

    Pn,k={χA:A⊆[n], ∣A∣≤k}\mathcal{P}_{n,k}=\{\chi_A:A\subseteq[n],\ |A|\le k\}

    be the class of parities involving at most kk input bits, and define the auto-regressive class H(k)=Pn,k×Pn+1,k×⋯\mathcal{H}^{(k)}=\mathcal{P}_{n,k}\times\mathcal{P}_{n+1,k}\times\cdots, whose generated token at each step is a parity of at most kk available bits. The paper shows that H(k)\mathcal{H}^{(k)} computes the full parity class Pn\mathcal{P}_n with length complexity

    Θ(nk).\Theta\left(\frac{n}{k}\right).

    The upper bound comes from combining groups of at most kk bits in a tree of intermediate parities; the lower bound follows because each step can enlarge the subset represented by the current parity by at most kk. Increasing kk therefore shortens the required chain of thought, but makes the underlying supervised learning problem harder: the paper reports statistical-query runtime on the order of (n≤k)=O((n/k)k)\binom{n}{\le k}=O((n/k)^k) and sample complexity O(klog⁡n)O(k\log n) for learning Pn,k\mathcal{P}_{n,k}.

  9. Knowl 9 — A simple linear model generates partially coherent TinyStories text

    empirical result

    The paper trained a masked linear next-token model on TinyStories, a synthetic corpus of short stories. The model used context length T=64T=64, token embeddings of dimension d=256d=256, a position-mixing masked linear layer, and an output embedding; parameter sharing across positions makes it a close proxy rather than an exact instance of the idealized linear class. It had approximately 162M active parameters and was trained for 5.5 hours on one A100 GPU. The architecture visualization on page 7 shows the input embedding, masked linear map, and output embedding used for each position. Text was generated from 50 prompts, and GPT-4 graded grammar, creativity, consistency with the prompt, and plot sense on a 1--10 scale; LanguageTool measured the percentage of outputs without grammatical errors.

    Model Grammar GPT-4 / LT Creativity GPT-4 Consistency GPT-4 Plot GPT-4
    TS-33M 8.00.8/62% 7.20.5 7.01.2 6.90.8
    TS-1M 6.90.9/59% 6.71.0 6.01.5 5.61.3
    LINEAR 6.32.0/64% 6.21.8 5.91.8 5.21.8

    The linear predictor was inferior to the transformer baselines in average GPT-4 ratings, but it frequently produced grammatical and contextually coherent continuations, demonstrating non-trivial language-generation ability without attention.

  10. Knowl 10 — An attention-free 775M-parameter MLP solves four-digit multiplication with chain-of-thought data

    empirical result

    The paper trained a four-layer MLP from scratch to multiply two four-digit numbers. The network used token embeddings of dimension d=128d=128, a masked context-wide linear layer with ReLU and context length T=307T=307, a per-token linear-ReLU layer, and an output embedding. It had 775M active parameters and no attention mechanism. Training data unfolded the multiplication algorithm into many intermediate steps, used separate tokens for digits, signs, and digit-pair products, and applied zero-padding so sequences had uniform length. Arbitrarily splitting all operand pairs gave 75% training and 25% validation data; training processed more than 100M sampled sequences, totaling 307M tokens, for 17 hours on one A100 GPU. Evaluation used 1,000 validation examples.

    The page-8 multiplication comparison reports the following exact-answer and per-digit accuracies:

    Model Exact accuracy Per-digit accuracy
    MLP-775M 96.9% 99.5%
    GPT-3.5 1.2% 61.9%
    GPT-4^* 5.3% 61.8%
    GOAT-7B^* 96.9% 99.2%

    The starred GPT-4 and GOAT-7B values were reported from prior work, whereas GPT-3.5 was evaluated on the same examples. The MLP matched GOAT-7B on exact answers, slightly exceeded it on per-digit accuracy, and outperformed GPT-3.5 and GPT-4 on this task.

Coverage note — No substantial contributed material was omitted. The qualitative prompt examples, the complete list of TinyStories prompts, appendix proof details, and the 70M-parameter transformer ablation were omitted because they support or illustrate the main theoretical and experimental results rather than adding comparably significant contributions.

References

  1. 1.Abbe, E. and Sandon, C. Provable limitations of deep learning. arXiv preprint arXiv:1812.06369, 2018.
  2. 2.Arora, S. and Barak, B. Computational complexity: a modern approach. Cambridge University Press, 2009.
  3. 3.Belanger, D. and Kakade, S. A linear dynamical system model for text. In International Conference on Machine Learning, pp. 833–842. PMLR, 2015.
  4. 4.Bender, E. M., Gebru, T., McMillan-Major, A., and Shmitchell, S. On the dangers of stochastic parrots: Can language models be too big? In Proceedings of the 2021 ACM conference on fairness, accountability, and transparency, pp. 610–623, 2021.
  5. 5.Blum, A., Kalai, A., and Wasserman, H. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM (JACM), 50(4):506–519, 2003.
  6. 6.Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877–1901, 2020.
  7. 7.Bubeck, S., Chandrasekaran, V., Eldan, R., Gehrke, J., Horvitz, E., Kamar, E., Lee, P., Lee, Y. T., Li, Y., Lundberg, S., et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:2303.12712, 2023.
  8. 8.Daniely, A. and Malach, E. Learning parities with neural networks. Advances in Neural Information Processing Systems, 33:20356–20365, 2020.
  9. 9.Dauphin, Y. N., Fan, A., Auli, M., and Grangier, D. Language modeling with gated convolutional networks. In International conference on machine learning, pp. 933–941. PMLR, 2017.
  10. 10.Edelman, B. L., Goel, S., Kakade, S., and Zhang, C. Inductive biases and variable creation in self-attention mechanisms. In International Conference on Machine Learning, pp. 5793–5831. PMLR, 2022.
  11. 11.Eldan, R. and Li, Y. Tinystories: How small can language models be and still speak coherent english? arXiv preprint arXiv:2305.07759, 2023.
  12. 12.Feng, G., Gu, Y., Zhang, B., Ye, H., He, D., and Wang, L. Towards revealing the mystery behind chain of thought: a theoretical perspective. arXiv preprint arXiv:2305.15408, 2023.
  13. 13.Giannou, A., Rajput, S., Sohn, J.-y., Lee, K., Lee, J. D., and Papailiopoulos, D. Looped transformers as programmable computers. arXiv preprint arXiv:2301.13196, 2023.
  14. 14.Hochreiter, S. and Schmidhuber, J. Long short-term memory. Neural computation, 9(8):1735–1780, 1997.
  15. 15.Katharopoulos, A., Vyas, A., Pappas, N., and Fleuret, F. Transformers are rnns: Fast autoregressive transformers with linear attention. In International conference on machine learning, pp. 5156–5165. PMLR, 2020.
  16. 16.Kautz, W. H. The realization of symmetric switching functions with linear-input logical elements. IRE Transactions on Electronic Computers, (3):371–378, 1961.
  17. 17.Kearns, M. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6):983–1006, 1998.
  18. 18.Kojima, T., Gu, S. S., Reid, M., Matsuo, Y., and Iwasawa, Y. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199–22213, 2022.
  19. 19.LanguageTool. Languagetool, 2024. URL https://languagetool.org/. Accessed: 2024-06-03.
  20. 20.Lee, N., Sreenivasan, K., Lee, J. D., Lee, K., and Papailiopoulos, D. Teaching arithmetic to small transformers. arXiv preprint arXiv:2307.03381, 2023.
  21. 21.Li, L. H., Hessel, J., Yu, Y., Ren, X., Chang, K.-W., and Choi, Y. Symbolic chain-of-thought distillation: Small models can also” think” step-by-step. arXiv preprint arXiv:2306.14050, 2023.
  22. 22.Li, S., Chen, J., Shen, Y., Chen, Z., Zhang, X., Li, Z., Wang, H., Qian, J., Peng, B., Mao, Y., et al. Explanations from large language models make small reasoners better. arXiv preprint arXiv:2210.06726, 2022.
  23. 23.Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., Leike, J., Schulman, J., Sutskever, I., and Cobbe, K. Let’s verify step by step. arXiv preprint arXiv:2305.20050, 2023.
  24. 24.Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C. Transformers learn shortcuts to automata. arXiv preprint arXiv:2210.10749, 2022.
  25. 25.Liu, H., Dai, Z., So, D., and Le, Q. V. Pay attention to mlps. Advances in Neural Information Processing Systems, 34:9204–9215, 2021.
  26. 26.Liu, T. and Low, B. K. H. Goat: Fine-tuned llama outperforms gpt-4 on arithmetic tasks. arXiv preprint arXiv:2305.14201, 2023.
  27. 27.Lu, P., Qiu, L., Yu, W., Welleck, S., and Chang, K.-W. A survey of deep learning for mathematical reasoning. arXiv preprint arXiv:2212.10535, 2022.
  28. 28.Magister, L. C., Mallinson, J., Adamek, J., Malmi, E., and Severyn, A. Teaching small language models to reason. arXiv preprint arXiv:2212.08410, 2022.
  29. 29.Malach, E. and Shalev-Shwartz, S. When hardness of approximation meets hardness of learning. The Journal of Machine Learning Research, 23(1):3942–3965, 2022.
  30. 30.Mikolov, T., Karafiat, M., Burget, L., Cernock ´ y, J., and ` Khudanpur, S. Recurrent neural network based language model. In Interspeech, volume 2, pp. 1045–1048. Makuhari, 2010.
  31. 31.Minsky, M. and Papert, S. A. Perceptrons, reissue of the 1988 expanded edition with a new foreword by Leon Bottou: an introduction to computational geometry. MIT press, 2017.
  32. 32.Muffo, M., Cocco, A., and Bertino, E. Evaluating transformer language models on arithmetic operations using number decomposition. arXiv preprint arXiv:2304.10977, 2023.
  33. 33.Nogueira, R., Jiang, Z., and Lin, J. Investigating the limitations of transformers with simple arithmetic tasks. arXiv preprint arXiv:2102.13019, 2021.
  34. 34.Nye, M., Andreassen, A. J., Gur-Ari, G., Michalewski, H., Austin, J., Bieber, D., Dohan, D., Lewkowycz, A., Bosma, M., Luan, D., et al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint arXiv:2112.00114, 2021.
  35. 35.OpenAI. Gpt-4 technical report. ArXiv, abs/2303.08774, 2023.
  36. 36.Peng, B., Alcaide, E., Anthony, Q., Albalak, A., Arcadinho, S., Cao, H., Cheng, X., Chung, M., Grella, M., GV, K. K., et al. Rwkv: Reinventing rnns for the transformer era. arXiv preprint arXiv:2305.13048, 2023.
  37. 37.Qian, J., Wang, H., Li, Z., Li, S., and Yan, X. Limitations of language models in arithmetic and symbolic induction. arXiv preprint arXiv:2208.05051, 2022.
  38. 38.Raz, R. Fast learning requires good memory: A time-space lower bound for parity learning. Journal of the ACM (JACM), 66(1):1–18, 2018.
  39. 39.Rosenblatt, F. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, 65(6):386, 1958.
  40. 40.Roy, S. and Roth, D. Solving general arithmetic word problems. arXiv preprint arXiv:1608.01413, 2016.
  41. 41.Shalev-Shwartz, S. and Ben-David, S. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
  42. 42.Shalev-Shwartz, S., Shamir, O., and Shammah, S. Failures of gradient-based deep learning. In International Conference on Machine Learning, pp. 3067–3075. PMLR, 2017.
  43. 43.Siegelmann, H. T. and Sontag, E. D. On the computational power of neural nets. In Proceedings of the fifth annual workshop on Computational learning theory, pp. 440–449, 1992.
  44. 44.Thoppilan, R., De Freitas, D., Hall, J., Shazeer, N., Kulshreshtha, A., Cheng, H.-T., Jin, A., Bos, T., Baker, L., Du, Y., et al. Lamda: Language models for dialog applications. arXiv preprint arXiv:2201.08239, 2022.
  45. 45.Tolstikhin, I. O., Houlsby, N., Kolesnikov, A., Beyer, L., Zhai, X., Unterthiner, T., Yung, J., Steiner, A., Keysers, D., Uszkoreit, J., et al. Mlp-mixer: An all-mlp architecture for vision. Advances in neural information processing systems, 34:24261–24272, 2021.
  46. 46.Valiant, L. G. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984.
  47. 47.Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. Attention is all you need. Advances in neural information processing systems, 30, 2017.
  48. 48.Wei, C., Chen, Y., and Ma, T. Statistically meaningful approximation: a case study on approximating turing machines with transformers. Advances in Neural Information Processing Systems, 35:12071–12083, 2022a.
  49. 49.Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35:24824–24837, 2022b.
  50. 50.Wies, N., Levine, Y., and Shashua, A. Sub-task decomposition enables learning in sequence to sequence tasks. arXiv preprint arXiv:2204.02892, 2022.
  51. 51.Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S. J., and Kumar, S. Are transformers universal approximators of sequence-to-sequence functions? arXiv preprint arXiv:1912.10077, 2019.
  52. 52.Zhai, S., Talbott, W., Srivastava, N., Huang, C., Goh, H., Zhang, R., and Susskind, J. An attention free transformer. arXiv preprint arXiv:2105.14103, 2021.

Citation

MLA
Malach, E. “Auto-Regressive Next-Token Predictors Are Universal Learners”. arXiv, 2023, http://arxiv.org/abs/2309.06979v3.
APA
Malach, E. (2023). Auto-Regressive Next-Token Predictors are Universal Learners. arXiv. http://arxiv.org/abs/2309.06979v3
Chicago
Malach, E. 2023. “Auto-Regressive Next-Token Predictors Are Universal Learners”. arXiv. http://arxiv.org/abs/2309.06979v3.
Harvard
Malach, E. (2023) “Auto-Regressive Next-Token Predictors are Universal Learners”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2309.06979v3.
Vancouver
1. Malach E (2023) Auto-Regressive Next-Token Predictors are Universal Learners. arXiv

BibTeX

@article{malach2023auto,
  title = {Auto-Regressive Next-Token Predictors are Universal Learners},
  author = {Malach, Eran},
  year = {2023},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2309.06979v3},
  eprint = {2309.06979}
}
Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: https://creativecommons.org/licenses/by/4.0/