Reproduce “Simulation of Graph Algorithms with Looped Transformers” 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

Artur Back de Luca, Kimon Fountoulakis

This paper constructively proves that a looped Transformer architecture, featuring a novel attention mechanism interacting directly with an adjacency matrix, can simulate classical graph algorithms (BFS, DFS, Dijkstra, SCC) with a constant number of parameters, enabling scale-generalization to graphs of arbitrary size. The work also demonstrates the architecture's Turing completeness and highlights practical training challenges due to ill-conditioned loss landscapes.

Key insights

  • A Transformer architecture can theoretically simulate complex graph algorithms with a constant network width, enabling true scale-invariant generalization.
  • Integrating direct adjacency matrix access via specialized attention heads is crucial for achieving parameter-efficient graph processing in a Transformer model.
  • While theoretically capable, neural networks face severe ill-conditioning during gradient-based training when approximating discontinuous algorithmic operations, highlighting a significant learnability challenge.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.