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+s2) using O(s2) 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.
Related
- A surprising generalization of the Möbius function
- Some surprising properties of essential data points visualization
- Approximating the Euclidean Ball by Polytopes: Surprising Rates in High Dimensions
- Algebraic Expressivity Certificates for Shallow Polynomial Neural Networks
- Expressivity of Contradiction Graphs
BibTeX
@misc{magen2026surprising,
title = {{The Surprising Expressivity of a Single Neuron with Autoregressive Chain-of-Thought}},
author = {Roey Magen and Nirmit Joshi and Gal Vardi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17283},
eprint = {2610.17283},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17283},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Surprising Expressivity of a Single Neuron with Autoregressive Chain-of-Thought
AU - Roey Magen
AU - Nirmit Joshi
AU - Gal Vardi
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.17283
UR - https://arxiv.org/abs/2610.17283
AB - 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.
ER -