Reproduce “Transformers Provably Learn Graph Search: Training Dynamics and the Exponential Power of Depth” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Xutao Ma, Somayeh Sojoudi
The authors study transformer depth and representation size for depth-first search on directed graphs. A two-layer model uses one attention layer to expose trace information and another to choose unexplored children or backtrack, achieving O(N log N) representation size, while one-layer models require Ω(N²) on dense graphs. Additional layers extend bounded-reachability look-ahead; learning is shown under a fixed-layer curriculum. These results concern representation size and constrained learning, not runtime or language-model reasoning.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.