Research map / Graph learning / Graph algorithms and clustering
Simulation of Graph Algorithms with Looped Transformers
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.
Shows by construction that a looped transformer with graph-adjacency attention heads and constant width can simulate Dijkstra, BFS, DFS, Kosaraju SCC, a multitask model, and SUBLEQ (Turing complete), with empirical validation on CLRS.
Problem
Whether transformers can simulate graph algorithms on graphs of arbitrary size, since standard architectures store the graph in the input and their width/depth scale with graph size.
Approach
A looped transformer with extra attention heads that multiply attention by the (padded) adjacency matrix (and its transpose) lets the graph be accessed as architecture rather than input, so parameter count and width stay constant across graph sizes; positional encodings on a circle enumerate nodes.
Key results
- Constructed looped transformers with constant width (O(1)) simulate BFS (17 layers, 3 heads), DFS (15 layers), Dijkstra (17 layers), and SCC (22 layers, 4 heads) for graphs up to bounds set by the precision parameters.
- Empirical validation on CLRS gives 100% accuracy for BFS, DFS, Dijkstra and SCC on train, validation (32) and test (32, 64-node graphs) splits, including a multitask model.
- Shows a Turing-complete result: a constant-width looped transformer with the adjacency attention heads simulates a modified SUBLEQ with 11 layers.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the looped-transformer simulation for BFS, DFS, Dijkstra, and SCC | Looped transformer · CLRS Train, Validation, and Test | accuracy: 100% | Helped |
| Increase Ω beyond 50 in the if-else construction | If-else construction · if-else function | condition number: above 50 -> above 10^{16} | Hurt |
| Increase Ω | If-else construction · if-else function | simulation quality | Helped |
| Decrease ε | Less-than construction · less-than function | simulation quality | Helped |
Surprising findings
- Training to recover the constructive simulation parameters is hard: the Hessian condition number exceeds 1e16 once Omega exceeds 50, so even initialization near the solution fails to converge.
Limitations
- Simulation guarantees are bounded by finite-precision parameters: node count capped by O(1/delta-hat), and by Omega for BFS/DFS/SCC (Omega/3 for SCC).
- Gradient-based training struggles to recover the constructed parameters due to ill-conditioning from discontinuous functions such as less-than and conditional selection.
- Empirical validation relies on softmax with a temperature and rounding layers rather than the exact hardmax construction.
Experimental setup
Datasets: CLRS Algorithmic Reasoning Benchmark
Benchmarks: CLRS Algorithmic Reasoning Benchmark
Metrics: accuracy
Builds on: CLRS Algorithmic Reasoning Benchmark Looped transformer Universal Transformers
Closest papers by meaning
- Understanding Transformer Reasoning Capabilities via Graph Algorithms (NeurIPS 2024 · similarity 0.89)
- Stability and Generalization in Looped Transformers (NeurIPS 2026 · similarity 0.86)
- Deep Equilibrium Algorithmic Reasoning (NeurIPS 2024 · similarity 0.86)
- The Expressive Power of Transformers with Chain of Thought (ICLR 2024 · similarity 0.86)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.85)
- Efficiently Representing Algorithms With Chain-of-Thought Transformers (NeurIPS 2026 · similarity 0.85)
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.