Research map / Architectures and efficiency / Attention and transformers
Understanding Transformer Reasoning Capabilities via Graph Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a representational hierarchy of graph reasoning tasks (retrieval, parallelizable, search) by transformer depth/width/pause-token scaling regimes, with proofs and GraphQA experiments.
Problem
Which transformer scaling regimes (depth, width, number of blank pause tokens) can perfectly solve different classes of graph algorithmic reasoning tasks, given realistic parameter scalings?
Approach
Classifies graph tasks into retrieval, parallelizable, and search classes via MPC round-equivalence and proves matching depth/width bounds for transformers in four scaling regimes (D1, LD, LDP, LDW); logarithmic depth is necessary and sufficient for parallelizable tasks, single-layer small-width suffices for retrieval tasks.
Key results
- A 60M transformer trained on 100K samples reaches 97.1% connectivity accuracy versus at most ~58.6% for GIN/GCN/MPNN-style GNNs at 100K samples in the reported table.
- Fine-tuned 11B T5 reaches 92.8% on shortest path with 1K training samples, versus 57.4% for the 60M transformer at 1K.
- Trained transformers outperform zero-shot, CoT and other prompting of LLMs on GraphQA, e.g. 11B FT transformer 98.4% connectivity vs best prompting 84.9% zero-shot.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train a 60M transformer explicitly on GraphQA instead of using the strongest listed prompting strategy | 60M transformer-100K · Node count | accuracy: 27.6 -> 100.0 | Helped |
| Train a 60M transformer explicitly on GraphQA instead of using the strongest listed prompting strategy | 60M transformer-100K · Edge count | accuracy: 12.8 -> 100.0 | Helped |
| Train a 60M transformer explicitly on GraphQA instead of using the strongest listed prompting strategy | 60M transformer-100K · Edge existence | accuracy: 44.5 -> 96.1 | Helped |
| Train a 60M transformer explicitly on GraphQA instead of using the strongest listed prompting strategy | 60M transformer-100K · Node degree | accuracy: 29.2 -> 91.7 | Helped |
| Train a 60M transformer explicitly on GraphQA instead of using the strongest listed prompting strategy | 60M transformer-100K · Connectivity | accuracy: 84.9 -> 98.0 | Helped |
| Train a 60M transformer explicitly on GraphQA instead of using the strongest listed prompting strategy | 60M transformer-100K · Cycle check | accuracy: 76.0 -> 98.0 | Helped |
| Train a 60M transformer explicitly on GraphQA instead of using the strongest listed prompting strategy | 60M transformer-100K · Shortest path | accuracy: 40.4 -> 97.2 | Helped |
| Train a 60M transformer explicitly on GraphQA instead of using the strongest listed prompting strategy | 60M transformer-100K · Triangle counting | accuracy: 12.7 -> 40.5 | Helped |
| Increase training data from 1K to 100K samples | 60M transformer · Connectivity | accuracy: 57.4 -> 97.1 | Helped |
| Increase training data from 1K to 100K samples | 60M transformer · Shortest path | accuracy: 57.4 -> 97.2 | Helped |
| Use a fine-tuned T5-11B instead of the 60M transformer trained on 1K samples | GraphQA models · Connectivity | accuracy: 92.9 -> 98.4 | Helped |
| Use a fine-tuned T5-11B instead of the 60M transformer trained on 1K samples | GraphQA models · Shortest path | accuracy: 57.4 -> 92.8 | Helped |
Surprising findings
- GNNs (MPNN) outperform small transformers on node degree and cycle check in the low-sample (1K) regime, despite transformers' expressivity.
- Chain-of-thought prompting of LLMs reduces connectivity accuracy (e.g., cot 45.2% vs zero-shot 84.9%).
Limitations
- Positive results rely on unbounded-size MLP assumption and bidirectional model; expressivity does not imply learnability.
- Minimum depth for search tasks at small width is unknown; LDP for search tasks unresolved.
- Empirical evaluation limited to GraphQA with small-scale models and no broader scaling-law study.
Experimental setup
Datasets: GraphQA
Benchmarks: GraphQA
Metrics: accuracy
Baselines: GCN MPNN GIN zero-shot zero-cot few-shot cot cot-bag
Builds on: MPC model GraphQA pause tokens bounded communication transformer model
Closest papers by meaning
- Simulation of Graph Algorithms with Looped Transformers (ICML 2024 · similarity 0.89)
- Transformers Struggle to Learn to Search (ICLR 2025 · similarity 0.89)
- The Expressive Power of Transformers with Chain of Thought (ICLR 2024 · similarity 0.88)
- A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers (NeurIPS 2025 · similarity 0.88)
- KnowFormer: Revisiting Transformers for Knowledge Graph Reasoning (ICML 2024 · similarity 0.88)
- Towards Principled Graph Transformers (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.