acceptodds
Under review as a conference paper at ICLR 2027

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 performing 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- circuit on inputs can be simulated by a neuron of dimension using 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-size circuits and hence 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.

Primary area:
learning theory
Keywords:
Chain-of-Thought, Expressivity, Learning Theory, Autoregressive Models

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_3qGiOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the minimal requirements for an autoregressive generative model to be Turing-complete, building on the many existing Turing-completeness results of specific neural architectures such as transformers and RNNs. The authors find that even a single neuron (with threshold activation for discrete computation and many different non-linear functions for continuous computation) suffices for Turing completeness. To prove this, the authors show how to construct a single neuron with sufficiently many inputs that can simulate any given circuit, and rely on an interesting application of a Sidon set. The paper also discusses the implications of the result on learnability with autoregressive thoughts (chain of thought) and the optimality of the neuron size.

Critical strengths
  • The paper asks the innovative question of the minimal set of capabilities an architecture requires for Turing completeness with autoregression. This abstracts away any specific architecture and shows that, in a sense, Turing completeness is a somewhat natural consequence of autoregression.
  • The paper is easy to follow and well written. The notation is clear, the claims well-supported and presented understandably.
  • I think the methodology is novel and interesting, and could be of use to much follow-up work.
  • The authors not only derive the expressivity results but also discuss the implications for learnability.
  • The experiments complement the theoretical results well.
Critical weaknesses

None

Questions for authors
  • Your result sits on one end of the spectrum with just one neuron, and, e.g., Turing completeness results for transformers are on the other end with a very specific architecture. Do you think we can also gain any insights into the expressivity of small fixed-size circuits (larger than a single neuron)?
Reviewer_Zq4uOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the expressivity and learnability of a single fixed neuron with autoregressive Chain-of-Thought (CoT).

  1. A single autoregressive neuron can simulate feedforward circuits with the same activation, including threshold and ReLU. A size-ss circuit on nn inputs requires dimension O(ns+s2)O(ns+s^2) and O(s2)O(s^2) generation steps. Both bounds are independent of circuit depth. The construction uses Sidon sets to prevent weight collisions.

  2. Complete CoT supervision enables efficient learning of threshold and ReLU neurons. For threshold neurons, learning from final answers alone is computationally hard if one-way functions exist.

  3. Under direct edge alignment, the paper proves a matching worst-case lower bound of Ω(s2)\Omega(s^2) generation steps.

The paper provides theoretical proofs and a CIFAR-10 experiment. A shared ReLU neuron learns from 4,000 complete CNN activation traces. It achieves 72.106% test accuracy, compared with the teacher’s 72.150%, and agrees with the teacher on 99.484% of test examples.

Critical strengths
  1. The Sidon-set construction is a simple solution to the parameter-sharing difficulty. Its polynomial overhead removes a major limitation of earlier results, strengthening the case that CoT can support general computation with a simple predictor.

  2. The learning results identify a benefit of intermediate supervision beyond expressivity. Complete CoT supervision can make complex computation efficiently learnable, giving a concrete reason to study which intermediate steps a teacher should expose.

Critical weaknesses
  1. Scalability to larger and deeper networks remains unresolved. For a ReLU circuit with ss gates and n=O(s)n=O(s) inputs, the sufficient sample bound is O~(s6/ϵ)\widetilde{O}(s^6/\epsilon) (lines 1062–1086). This bound gives a prohibitively large data budget for large networks, so it does not establish that they can be learned with realistic amounts of training data. The computational guarantee also depends on satisfying all training constraints exactly, while the implementation uses approximate fitting through finite Adam updates (lines 1043–1053 and 1216–1231). As networks become deeper, errors in fitted gates can affect more subsequent computations. The paper does not establish how accurately these gates must be fitted, or how much training this requires, to maintain final prediction accuracy as depth increases.

  2. The supervision requirement sharply limits the practical value of the learning result. Every training example must reveal all neuron activations (lines 1035–1040). This requires access to the teacher’s internal computation, so teachers that provide only answers or written CoT cannot supply the required data. Even with internal access, collecting and processing these activations adds a supervision burden that grows with the entire teacher network. Applying the method to larger teachers therefore requires increasingly extensive training data, even when the task itself needs only a short answer.

  3. The experiment does not resolve the uncertainty about scaling. Recovery of one 244K-parameter CNN does not establish whether training costs remain manageable and teacher agreement remains high for larger and deeper networks (lines 1168–1184). If computational resources were limited, the absence of larger experiments should not itself count against acceptance.

Questions for authors
  1. Can you try larger scale experiment?
Reviewer_PZjfOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the expressivity and learnability of a single autoregressive neuron with CoT. The authors show that a single neuron with shared parameters can simulate arbitrary feedforward circuits with s neurons and n inputs, using O(ns+s^2) parameters and O(s^2) autoregressive steps, independent of circuit depth. The key technique is a construction based on Sidon sets that avoids collisions when encoding circuit weights into the shared neuron. The results imply that autoregressive threshold neurons can simulate polynomial-time Turing machines. The authors also establish efficient learnability under complete CoT supervision and computational hardness under end-to-end supervision. Experiments on CIFAR-10 demonstrate that a single autoregressive neuron can reproduce the predictions of a CNN teacher with approximately 99% agreement.

Critical strengths

I am not super familiar with this sub-area, please see my weaknesses below.

Critical weaknesses

First, I am not particularly familiar with the literature on the expressivity of Chain-of-Thought models.

My main concern is about the significance of the expressivity result. Prior work, such as Autoregressive Large Language Models are Computationally Universal (Schuurmans et al., 2024) and The Expressive Power of Transformers with Chain of Thought (Merrill and Sabharwal, 2024), has already established that autoregressive generation with CoT can enable universal computation.

What does it mean/how can I intrepret you have a result says we only need poly compute for simulating arbitrary feedforward circuits?

Questions for authors

See the weaknesses above

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.