Transformer theory / Open question
Can Transformers Learn to Search?
Searching a graph is a simple test of whether a transformer can discover a scalable reasoning procedure.
Seed catalog · Showing the bundled record.
Problem statement
Consider directed graphs on n vertices with maximum out-degree Delta, encoded as randomly ordered edge lists plus source/target queries. Train a causal softmax transformer to decide reachability using a distribution balanced between reachable and unreachable pairs, including matched-degree examples. Characterize the sample, depth and width requirements for minibatch gradient training to achieve error at most epsilon on graphs with up to N vertices and path length D; distinguish distribution-specific guarantees from uniform guarantees over all bounded-degree graphs.
Assumptions and scope
- Fix graph encoding, graph family, diameter distribution and query sampling; test graph size and diameter are separate axes.
- Specify model size, finite precision, initialization, loss and gradient updates. Do not transfer a hard-attention construction directly to softmax training.
- Compare depth and width at a charged computational budget; include datasets beyond architectural capacity as possible sources of misleading gradients.
What would settle it?
A finite-data convergence and size-transfer theorem for a nontrivial graph family, or a sharp obstruction distinguishing representable algorithms from those learned by the specified optimizer.
Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.
Status and evidence
Log-depth representation theorems already exist. Ye et al. prove data-dependent learning of adjacency-power connectivity in a Disentangled Transformer; Saparov et al. document empirical failures on larger graphs. The remaining target concerns standard softmax training and quantified transfer, not the first construction of a connectivity circuit. This is an editorial, source-motivated research target. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.
Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.
Sources and further reading
- Sanford et al. — Understanding Transformer Reasoning Capabilities via Graph Algorithms ↗partial theory · source checked 2026-11-19
Abstract checked: a representational hierarchy; logarithmic depth is necessary and sufficient for graph connectivity in the stated regimes.
- Merrill and Sabharwal — The Expressive Power of Log-Depth Transformers ↗partial theory · source checked 2026-11-19
Abstract checked: Θ(log n)-depth uniform transformers express regular-language recognition and graph connectivity; trainability evidence is empirical.
- Ye et al. — Transformers Provably Learn Algorithmic Solutions for Graph Connectivity, But Only with the Right Data ↗partial theory · source checked 2026-11-19
Abstract checked: for a simplified Disentangled Transformer, training dynamics learn adjacency-power connectivity when training graphs are within depth capacity, and a degree heuristic otherwise.
- Saparov et al. — Transformers Struggle to Learn to Search ↗empirical motivation · source checked 2026-11-19
Abstract checked: empirical difficulty of learning search as graph size grows, not fixed by more parameters or in-context search.