The Surprising Expressivity of a Single Neuron with Autoregressive Chain-of-Thought
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.
The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.
Research summary
The paper demonstrates that a single autoregressive neuron can efficiently simulate general computation via Chain-of-Thought, leveraging Sidon sets to achieve depth-independent polynomial bounds. This theoretical breakthrough clarifies the role of CoT in enabling simple models to perform complex tasks, with significant implications for understanding the efficiency and learnability of autoregressive language models.
Methodology
The paper introduces a rigorous theoretical framework for the expressivity of autoregressive single-neuron models. The core innovation is the use of Sidon sets (additive combinatorics) to construct collision-free encodings of circuit weights within a single shared parameter vector. This allows a single neuron to simulate feedforward circuits of arbitrary depth with polynomial bounds on dimension and generation steps, independent of circuit depth. This is a significant improvement over prior work (Joshi et al., 2025) which suffered from exponential scaling with depth. The methodology is mathematically sound, providing tight upper and lower bounds under natural assumptions.
Results & evaluation
The experimental section is minimal but illustrative. It demonstrates that a single autoregressive ReLU neuron can be trained to mimic a CNN teacher on CIFAR-10 using activation traces. While the results (99% agreement with teacher) are strong, the experiment is a toy setup designed to validate the theory rather than a competitive benchmark. It does not compare against standard baselines or evaluate on unseen tasks, limiting its practical impact.
Reproducibility
The theoretical proofs are detailed and self-contained. The experimental setup is described with sufficient detail (Adam optimizer, sparse implementation, 4000 trajectories) to be reproducible, though the code is not explicitly linked in the provided text.
Limitations
The primary limitation is the gap between theory and practice. The simulation requires a specific feature map and structured CoT traces that are not naturally available in standard LLM training. The experiment is a controlled simulation, not a demonstration of a practical LLM architecture. The lower bounds rely on the "direct edge alignment" assumption, which may not hold for all potential simulation strategies.
Broader impact
This paper provides a foundational theoretical insight into why Chain-of-Thought (CoT) is effective: it allows simple predictors to simulate complex computations by exposing intermediate states. It bridges the gap between circuit complexity and neural network learning, offering a rigorous basis for understanding the efficiency of autoregressive models. It may influence future work on minimal architectures and the design of CoT supervision signals. The paper demonstrates that a single autoregressive neuron can efficiently simulate general computation via Chain-of-Thought, leveraging Sidon sets to achieve depth-independent polynomial bounds. This theoretical breakthrough clarifies the role of CoT in enabling simple models to perform complex tasks, with significant implications for understanding the efficiency and learnability of autoregressive language models.
Author of this paper? Send a correction.