Transformers Provably Learn Graph Search: Training Dynamics and the Exponential Power of Depth
cs.AI
Submitted: 2026-11-10
Updated: 2026-11-10
Code: https://github.com/xutaoma/transformer_search_code_lean
Terminology
Sources
- A Mechanistic Analysis of a Transformer Trained on a Symbolic Multi-Step Reasoning Task
- The Mystery of the Pathological Path-star Task for Language Models
- DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning
- Transformers Provably Learn to Internalize Chain-of-Thought
- LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks
- Beyond A*: Better Planning with Transformers via Search Dynamics Bootstrapping
- Exact Expressive Power of Transformers with Padding
- In-context Learning and Induction Heads
- One-layer transformers fail to solve the induction heads task
- Transformers, parallel computation, and logarithmic depth
- Transformers Struggle to Learn to Search
- GPT-4 Doesn't Know It's Wrong: An Analysis of Iterative Prompting for Reasoning Problems
- Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits
- Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannot
- Multi-head Transformers Provably Learn Symbolic Multi-step Reasoning via Gradient Descent
- Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformers
- Emergence of Superposition: Unveiling the Training Dynamics of Chain of Continuous Thought
- Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought
Related papers
- Multi-Objective Structured Pruning of LLMs for Latency and Model Size Optimization
- MAVEN-T: Reinforced Heterogeneous Distillation for Real-Time Multi-Agent Trajectory Prediction
- Model Discovery Agent: LLM-assisted Bayesian experiment design for data-efficient discovery of mechanistic world models
- Embeddings for Preferences, Not Semantics
- Can We Trust Item Response Theory for AI Evaluation?
- Diagnosing Task Insensitivity in Language Agents