REVIEW 37 cited by
The Expressive Power of Transformers with Chain of Thought
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
Recent theoretical work has identified surprisingly simple reasoning problems, such as checking if two nodes in a graph are connected or simulating finite-state machines, that are provably unsolvable by standard transformers that answer immediately after reading their input. However, in practice, transformers' reasoning can be improved by allowing them to use a "chain of thought" or "scratchpad", i.e., generate and condition on a sequence of intermediate tokens before answering. Motivated by this, we ask: Does such intermediate generation fundamentally extend the computational power of a decoder-only transformer? We show that the answer is yes, but the amount of increase depends crucially on the amount of intermediate generation. For instance, we find that transformer decoders with a logarithmic number of decoding steps (w.r.t. the input length) push the limits of standard transformers only slightly, while a linear number of decoding steps, assuming projected pre-norm (a slight generalization of standard pre-norm), adds a clear new ability (under standard complexity conjectures): recognizing all regular languages. Our results also imply that linear steps keep transformer decoders within context-sensitive languages, and polynomial steps with generalized pre-norm make them recognize exactly the class of polynomial-time solvable problems -- the first exact characterization of a type of transformers in terms of standard complexity classes. Together, this provides a nuanced framework for understanding how the length of a transformer's chain of thought or scratchpad impacts its reasoning power.
Forward citations
Cited by 37 Pith papers
-
The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought
The sample complexity of exact-trace learning for autoregressive Chain-of-Thought is O((DSdim(H) + log(1/δ))/ε), matching the local next-token class with no dependence on rollout length.
-
Tight Sample Complexity of Transformers
Depth-L transformers with W parameters have VC dimension Theta(L W log(T W)), yielding matching O(L W log((T+T')W)) upper and Omega(L W log((T+T')W/L)) lower bounds on sample complexity for chain-of-thought learning.
-
Tight Sample Complexity of Transformers
Hard-attention Transformers with W parameters and depth L have VC dimension Θ(WL log(TW)); teacher forcing is sample-optimal for chain-of-thought learning.
-
Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
Sliding-window transformers without positional encodings are Turing complete because the sliding window breaks permutation symmetry and suffices to simulate Post machines via a constant-size histogram state.
-
Transformers Provably Learn to Internalize Chain-of-Thought
L-layer transformers under Log-ICoT curriculum provably learn k-parity with poly(n) samples and log k stages, matching explicit CoT efficiency without inference overhead.
-
Beyond Accuracy: Diagnosing Algebraic Reasoning Failures in LLMs Across Nine Complexity Dimensions
A nine-dimension algebraic complexity framework shows that LLMs suffer a scale-invariant working memory bottleneck, collapsing at 20-30 parallel branches regardless of parameter count from 8B to 235B.
-
When Does In-Context Search Help? A Sampling-Complexity Theory of Reflection-Driven Reasoning
When reflections localize early errors, in-context search solves exp-small pass-rate problems with poly sequential attempts; otherwise it offers no asymptotic gain over parallel sampling, and the update is learnable a...
-
Agentic Transformers Provably Learn to Search via Reinforcement Learning
In a stochastic k-ary tree, a two-head transformer learns randomized DFS via policy gradient under depth-wise curriculum, generalizes to deeper trees, and adapts to imbalanced goals via discounting.
-
Pseudo-Formalization for Automatic Proof Verification
Pseudo-Formalization decomposes proofs into self-contained natural language modules for independent LLM-based Block Verification, outperforming LLM-as-judge baselines on olympiad and research math benchmarks while rel...
-
A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning
Online mistake bounds for autoregressive output learning can grow logarithmically with generation horizon M under end-to-end feedback but become independent of M with chain-of-thought trajectory access.
-
Problem Reductions at Scale: Agentic Integration of Computationally Hard Problems
A harness for AI agents enabled construction of a Rust library with 100+ problem types and 200+ reduction rules for NP-hard problems in three months.
-
Internalized Reasoning for Long-Context Visual Document Understanding
A synthetic pipeline creates and internalizes reasoning traces in VLMs for long-context visual document understanding, with a 32B model surpassing a 235B model on MMLongBenchDoc and showing 12.4x fewer output tokens.
-
Turbo Connection: Reasoning as Information Flow from Higher to Lower Layers
An architecture that routes hidden states from higher to lower layers between consecutive tokens improves reasoning accuracy and length generalization in fine-tuned LLMs.
-
Training Large Language Models to Reason in a Continuous Latent Space
Coconut lets LLMs perform reasoning directly in continuous latent space by recycling hidden states as inputs, outperforming standard chain-of-thought on search-intensive logical tasks with better accuracy-efficiency t...
-
From Reasoning Traces to Reusable Modules: Understanding Compositional Generalization in Language Model Reasoning
SFT supplies entangled compositional traces of atomic skills and routing modules; RL identifies those modules and enables recombination on novel compositions outside the SFT support.
-
Internalized Reasoning for Long-Context Visual Document Understanding
Synthetic page-ranked reasoning traces plus low-strength model merging give a 32B VLM 58.3 on MMLongBenchDoc, beating a 235B teacher while cutting output tokens ~12× versus explicit reasoning.
-
From Reasoning Traces to Reusable Modules: Understanding Compositional Generalization in Language Model Reasoning
Introduces a hierarchical latent selection model showing SFT supplies raw module materials in compound traces while RL decomposes them to identify atomic modules and enable recombination for new reasoning configurations.
-
Pretraining Recurrent Networks without Recurrence
SMT reduces RNN training to supervised learning on memory transitions (m_t, x_{t+1}) to m_{t+1} obtained from a Transformer encoder, enabling time-parallel training with O(1) gradient paths.
-
The Power of Power Law: Asymmetry Enables Compositional Reasoning
Power-law data sampling creates beneficial asymmetry in the loss landscape that lets models acquire high-frequency skill compositions first, enabling more efficient learning of rare long-tail skills than uniform distr...
-
The Power of Power Law: Asymmetry Enables Compositional Reasoning
Power-law data distributions outperform uniform ones for compositional reasoning by creating asymmetry that lets frequent skill compositions scaffold rare ones with less data.
-
Diagnosing CFG Interpretation in LLMs
LLMs maintain surface syntax for novel CFGs but fail to preserve semantics under recursion and branching, relying on keyword bootstrapping rather than pure symbolic reasoning.
-
Geometric Capacity of Transformers: A Tropical Geometry Perspective
Self-attention in transformers corresponds exactly to Power Voronoi diagrams under tropical geometry, yielding tight bounds of Theta(N to the power of d_model times L) linear regions.
-
Do Transformers Use their Depth Adaptively? Evidence from a Relational Reasoning Task
Transformers show limited adaptive depth use on relational reasoning, with clearer evidence after finetuning on the task.
-
Self-Supervised Bootstrapping of Action-Predictive Embodied Reasoning
R&B-EnCoRe uses self-supervised importance-weighted variational inference to distill action-predictive reasoning datasets that improve VLA performance on manipulation, navigation, and driving tasks without external verifiers.
-
Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently
Under hand-designed masks and task-specific activations, RL fine-tuning learns a k-sparse Boolean reasoning chain in one gradient update while SFT learns it one CoT step per update.
-
Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling
In a cellular automata rule-inference task designed to block memorization, neural models achieve high next-step accuracy but accuracy falls sharply with longer reasoning chains; depth, recurrence, memory, and test-tim...
-
LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code
LiveCodeBench collects 400 recent contest problems to create a contamination-free benchmark evaluating LLMs on code generation and related capabilities like self-repair and execution.
-
Pre-Strings Lectures on Artificial Intelligence
Lecture notes define neural-network field theory and survey how it recovers known QFT/string results plus applied AI techniques for string problems.
-
Not All LLM Reasoning is Visible in the Chain-of-Thought
Semantically empty filler tokens improve accuracy across several frontier LLMs on synthetic math tasks and let Claude Opus 4.5 satisfy a hidden modular constraint, evidence of computation invisible in output tokens.
-
Einstein World Models
Einstein World Models integrate visual rollouts from a callable world-module into LLM reasoning traces to support complex thought beyond language.
-
Pseudo-Formalization for Automatic Proof Verification
Pseudo-Formalization decomposes natural language proofs into modular blocks for independent LLM verification via Block Verification, outperforming LLM-as-judge baselines on error detection in olympiad and research mat...
-
NoisyCoconut: Counterfactual Consensus via Latent Space Reasoning
Injecting noise into LLM latent trajectories creates diverse reasoning paths whose agreement acts as a confidence signal for selective abstention, cutting error rates from 40-70% to under 15% on math tasks.
-
The Serial Scaling Hypothesis
The serial scaling hypothesis formalizes inherently serial problems in complexity theory and demonstrates that diffusion models cannot solve them.
-
Efficient Reasoning with Hidden Thinking
Heima compresses verbose CoT into hidden thinking tokens via information-theoretic analysis and an adaptive interpreter, claiming maintained or improved zero-shot accuracy on reasoning benchmarks.
-
Pretraining Recurrent Networks without Recurrence
SMT trains nonlinear RNNs by imitating one-step memory-transition labels generated by a Transformer, replacing BPTT's unrolled credit assignment with time-parallel supervised learning.
-
Measuring AI Reasoning: A Guide for Researchers
Reasoning in language models should be measured by the faithfulness and validity of their multi-step search processes and intermediate traces, not final-answer accuracy.
-
Geometric Capacity of Transformers: A Tropical Geometry Perspective
The paper claims transformer expressivity is governed by power-diagram partitions, with a tight Θ(N^{min{H,d-1}L}) linear-region bound, but the proof's multi-head vertex bound and lower-bound construction are not sound.
Discussion (0). Sign in to comment.