CS Paper Radar

The Surprising Expressivity of a Single Neuron with Autoregressive Chain-of-Thought

Roey Magen, Nirmit Joshi, Gal Vardi

cs.LG stat.ML ·submitted 2026-10-12 18:35 UTC · v1
hot direction

Abstract

The success of autoregressive language models trained with Chain-of-Thought~(CoT) supervision raises a fundamental question: How simple can a next-token predictor be while still enabling the efficient simulation of general computation through its autoregressively generated CoT? Surprisingly, we show that a single neuron suffices. For a broad family of activations, including threshold and ReLU, a single autoregressive neuron can simulate any feedforward circuit with the same activation. Specifically, a size-$s$ circuit on $n$ inputs can be simulated by a neuron of dimension $O(ns+s^2)$ using $O(s^2)$ generation steps, with both bounds independent of circuit depth and tight under natural assumptions. For threshold activations, this improves upon the simulation of Joshi et al. (COLT 2025), whose bounds scale exponentially with circuit depth. Consequently, autoregressive threshold neurons can simulate polynomial-time Turing machines, while remaining efficiently learnable from CoT supervision. Our main expressivity result relies on a novel connection to Sidon sets from additive combinatorics. As an experimental illustration, we efficiently train a single autoregressive ReLU neuron to mimic a neural network teacher with nontrivial test accuracy on CIFAR-10.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Autoregressive Chain-of-Thought Learning via Bagging

cs.LG stat.ML ·2026-11-16 ·Awni Altabaa, John Lafferty, Omar Montasser
similarity 0.63
Abstract

We study how to learn an autoregressive next-token generator $f\colonΣ^\star\toΣ$ from a class $\mathcal{F}$, given chain-of-thought (CoT) demonstrations of length $T$ generated by $f$. We present a simple algorithm based on bagging, which outputs a majority vote of generators that are trained to be CoT-consistent on bootstrap samples of the training data. For binary token sets, it achieves the optimal sample complexity of $O((d_{\mathrm{VC}}+\log(1/δ))/ε)$, independent of the CoT length $T$, where $d_{\mathrm{VC}}$ is the VC dimension of $\mathcal{F}$. For finite token sets $Σ$, the VC dimension is replaced by a multiclass analogue, the Graph dimension $d_{\mathrm{G}}$, and the sample complexity is optimal up to a $\log|Σ|$ factor. The number of generators in the majority-vote ensemble is $O(\log(T/δ))$, and we show that the ensemble can be distilled into a single generator in $\mathcal{F}$ at the expense of $n\log(nT)$ unlabeled prompts.

0.20

Linear RNN Scaling Laws: When Longer Sequences Beat More Sequences

cs.LG ·2026-08-23 ·Ziyan Chen, Zhongzhu Zhou, Linhe Zheng, Peilin Liu, Ding-Xuan Zhou
similarity 0.60
Abstract · 43 pages, 3 figures

Empirical scaling laws for autoregressive language models relate prediction loss to model size, data size, and optimization compute, but their theoretical origin is still poorly understood in sequential pretraining settings. We study this question in a tractable teacher--student model where a stable latent linear RNN generates trajectories and a sketched linear recurrent student is trained by safeguarded full-batch WSD gradient descent on next-token prediction. The sketch dimension $M$ plays the role of model size, while $N$ independent trajectories of length $P$ provide the training tokens. We allow the innovation and initialization covariances to have different power-law exponents $α$ and $θ$. The induced design spectrum produces explicit approximation, optimization, and statistical scaling laws separated by spectral crossovers. When $θ\geα$, the original one-scale rates $M^{1-β_α}$, $R^{(1-β_α)/α}$, and $(NP)^{-1}\min\{M,R^{1/α}\}$ are recovered. When $α-2r\leθ<α$, the heavier initialization tail changes the rates beyond $P$-dependent model and optimization crossovers. The proof uses a covariance event only internally and a globally safeguarded step size on its complement. The variance retains the factor $(NP)^{-1}$, while sequence length also suppresses the initialization transient, so $N$ and $P$ cease to be fully interchangeable in the two-scale regime.

0.25

Learn Your Own Thoughts: Abstract Token Curriculum

cs.LG cs.AIcs.CLstat.ML ·2026-09-17 ·Khashayar Gatmiry, Avrajit Ghosh, Parsa Mirtaheri, Jason D. Lee, Nika Haghtalab +2 more
similarity 0.60
Abstract

Large Language Models (LLMs) have achieved remarkable reasoning capabilities by utilizing chain-of-thought (CoT) as a scratchpad for intermediate stages of thinking. However, CoT techniques require explicit supervision on thinking tokens, which requires rich, task-specific data. In this work, we propose Abstract Token Curriculum (ATC), a novel curriculum learning framework that elicits effective continuous intermediate representations without direct supervision or manual scratchpad design. ATC gradually increases problem complexity through a sequence of distributions, training the model to develop internal abstract ``thoughts'' in the continuous representation space. This paper provides both theoretical and experimental evidence for the benefits of ATC and its advantages over previous methods for training continuous thoughts. Theoretically, we show that for learning parity functions with single-layer softmax attention using ATC, attention naturally focuses on the CoT tokens in the context that provide the ``easiest path'' to predicting the next token. Experimentally, we show ATC's effectiveness on graph reachability and arithmetic learning tasks.

0.20

Learning Depth-3 Circuits with Polynomial Savings

cs.DS cs.CC ·2026-09-16 ·Xi Chen, Animesh Fatehpuria, Shyamal Patel, Rocco Servedio
similarity 0.60
Abstract

We study the challenging problem of learning depth-three circuits in the mistake-bound model of (realizable) online learning, which is a more difficult model than distribution-free PAC learning. Prior algorithms for this problem, due to Servedio and Tan [ST17], could only learn polynomial-size depth-three circuits of poly$(n)$ size over $\{0,1\}^n$ with a running time of $2^{n - Ω(n/\log n)}$, and hence they ran in time $N^{1-o(1)}$ where $N=2^n$ is the running time of a naive memorization-based approach. In this work we substantially improve on the [ST17] result: for any constant $γ\geq1$, we give an algorithm that learns depth-three circuits of size $n^γ$ with running time \[ 2^{n-c_γn}, \] where $c_γ>0$ depends only on $γ$ and not on $n$. Hence we achieve a polynomial savings over the naive approach for learning any polynomial-size depth-three circuit. The main driving force behind our improvement is an improved bound on the approximate degree of width-$k$ CNFs. Inspired by Szegedy [Sze04] and Magniez et al. [MNRS11], the rough idea of our construction is to use a Chebyshev polynomial to efficiently amplify the spectral gap of a carefully designed random walk. This is combined with a random-restriction-like approach to separately learn different subfunctions corresponding to different assignments to a randomly chosen set of variables, using the Perceptron algorithm over a specially designed feature space. A simplified warmup instantiation of our approach achieves $c_γ= \exp(-O(γ))$; by augmenting this warmup with further ingredients we obtain the sharp form of our result, which achieves $c_γ=Ω(1)/γ$.

0.20

Understanding the Out-of-Distribution Generalization of Chain-of-Thought Reasoning in LLMs

cs.LG stat.ML ·2026-11-04 ·Nuo-Jing Liang, Xiao-Tong Yuan, Pan Zhou
code/data similarity 0.59
Abstract

Chain-of-Thought (CoT) reasoning substantially improves Large Language Models (LLMs), yet its out-of-distribution (OOD) generalization mechanism remains theoretically underexplored. We study CoT as compositional OOD generalization: the target task lacks complete reasoning trajectories or direct input-output pairs, while training provides only in-distribution (ID) atomic step data. We show that CoT generalizes by repeatedly applying a shared single-step predictor to compose reusable ID transitions. Theoretically, let $T$ denote the number of reasoning steps in the target task, $n$ the number of training samples per sub-task, and $k$ the number of output tokens per step; then the OOD task risk is controlled by the sum of the ID sub-task risks, scaled by a coefficient of order $\mathcal{O}(k)$ that is independent of $T$, although the summed risk itself may still grow with $T$. A Rademacher-complexity analysis further shows that the estimation term is of order $\mathcal{O}(\sqrt{T/n})$, rather than linear in $T$, due to predictor sharing under a uniform capacity control on the shared class. For autoregressive Next-Token Prediction, the final-task risk is bounded by the best-in-class step-level risk scaled by the same coefficient of order $\mathcal{O}(k)$, plus an estimation term of order $\widetilde{\mathcal{O}}\big(k\sqrt{T/n}\big)$. A parity-coupled construction further shows that, for the sub-task empirical risk minimizer, the expected final-task risk is at least the best in-class risk plus $Ω(\sqrt{T/n})$ when $T\le n$. Experiments on Atom-Task and GSM8K support the theory: CoT enables short-to-long and compositional generalization, while explicit state tracking is crucial. Our code is available at https://github.com/maxliang114514/CoT-OOD.

0.44

Learning to Read Out: Unembedding Dynamics in Language Model Pretraining

cs.CL cs.AIcs.LG ·2026-10-14 ·Matteo He, William F. Shen, Alex Iacob, Andrej Jovanovic, Xinchi Qiu +1 more
publishedcode/data similarity 0.59
Abstract · NeurIPS 2026. 10 pages main text, 51 pages total. Code: https://github.com/hematteo/learning-to-read-out

When does a language model acquire a capability? Developmental studies usually answer this by tracking when models start producing the correct token. But that prediction passes through the unembedding matrix, or readout, which is itself still being learned during pretraining. We show that a model's hidden states can encode task information before its own readout expresses it, so timelines read from outputs conflate what the model encodes with what its readout expresses. To track the readout directly, we introduce parameter-trajectory crosscoding, which fits one sparse dictionary to every token's readout row at every checkpoint. Unlike crosscoders on activations, it needs only checkpoint weights. We use it to locate a narrow early window, 0.4-1.1% of the way through Pythia's pretraining, in which the readout reorganizes and WordNet word categories become decodable from its rows. By then, linear probes on the hidden states already decode task information that the model's own outputs do not yet show. To test whether such gaps depend on how fast the readout learns, we pretrain small models from scratch that differ only in the readout's learning rate. We find that raising it makes the readout develop earlier and the gap close sooner, with little effect on final loss. Together, these results imply that early in training, where many developmental transitions are dated, a behavioral date can reflect when the readout learns to express task information and not when the model learns it.

0.52

Compute Has Shape: Self-Morphing the Internal Computation of Frozen LLMs

cs.AI ·2026-10-28 ·Junxi Wu, Yiwen Guo, Shu-Tao Xia
code/data similarity 0.59
Abstract

Test-time scaling improves large language models through additional computation, but how to adapt the topology of internal computation to individual inputs remains underexplored. Existing approaches largely fix recurrent or parallel architectures during training, or reconfigure frozen models along a single structural axis. We introduce SelfMorph, which makes computational shape an input-dependent inference-time decision. It unifies the original forward path (BASE), serial reuse of a layer span (REPEAT), and local branching and merging of perturbed hidden states (BRANCH) in a unified space parameterized by type, location, and intensity. Since they offer complementary benefits rather than uniform dominance, we use a lightweight selector that reads the backbone's depth-wise hidden state trajectory on the prompt to choose a morphology before response generation. We train the selector by distilling utility-based distribution from offline morphing that jointly account for task performance and computational cost. Evaluated on three LLMs spanning 4B-27B, SelfMorph achieves a 8.06% mean relative improvement on five in-distribution benchmarks and 4.45% on four unseen benchmarks. It achieves the strongest performance in 24 of 27 settings. These findings identify input-adaptive computational topology as a complementary axis of test-time scaling beyond generating more tokens. Our code is available at https://github.com/creator-xi/SelfMorph.

0.30

Language models suffer from a curse of ambiguity

cs.CL cs.LGcs.NE ·2026-08-15 ·Nicolas Zucchet, Hyun Dong Lee, Scott Linderman
similarity 0.58
Abstract

Large language models increasingly rely on sampling as a driver of their own improvement, making the fidelity of their learned distributions more critical than ever. Yet, not all distributions are equally easy to learn. In this work, we identify a curse of ambiguity: in large language models, and more broadly in all neural networks that produce discrete probability distributions, the more ambiguous a next-token distribution is, the harder it is to learn accurately. Through an extensive theoretical analysis, we trace this curse to architectural and learning roots. More ambiguous distributions require more capacity to be stored, larger embeddings to be represented, more steps to be fitted, and amplify token-sampling noise. We validate these findings on synthetic tasks with controlled ground truth and observe the same signatures in language models trained on real data. Our results provide a new perspective on the statistical capabilities of large language models and a practical framework for when to trust their output distribution.

0.39