REVIEW 4 cited by
Simulation of Graph Algorithms with Looped Transformers
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
The execution of graph algorithms using neural networks has recently attracted significant interest due to promising empirical progress. This motivates further understanding of how neural networks can replicate reasoning steps with relational data. In this work, we study the ability of transformer networks to simulate algorithms on graphs from a theoretical perspective. The architecture we use is a looped transformer with extra attention heads that interact with the graph. We prove by construction that this architecture can simulate individual algorithms such as Dijkstra's shortest path, Breadth- and Depth-First Search, and Kosaraju's strongly connected components, as well as multiple algorithms simultaneously. The number of parameters in the networks does not increase with the input graph size, which implies that the networks can simulate the above algorithms for any graph. Despite this property, we show a limit to simulation in our solution due to finite precision. Finally, we show a Turing Completeness result with constant width when the extra attention heads are utilized.
Forward citations
Cited by 4 Pith papers
-
Beyond Test-Time Memory: State-Space Optimal Control for LLM Reasoning
A symplectic LQR layer inserted as an adapter into pretrained LLMs yields large gains on MATH-500, AMC and AIME by solving a latent optimal-control problem at inference time.
-
Loop the Loopies!
With two recurrent passes per layer and a compute-matched scaling recipe, 20B and 6B MoE models beat vanilla Transformers trained on the same wall-clock budget.
-
Spectral Journey: How Transformers Predict the Shortest Path
Two-layer transformers learn shortest paths on small graphs by building embeddings that correlate with spectral decomposition of the line graph, yielding an approximate spectral path-finding algorithm.
-
A Survey on Latent Reasoning
A survey that organizes latent reasoning methods into vertical recurrence, horizontal recurrence, and infinite-depth diffusion, arguing that silent reasoning can beat explicit chain-of-thought.
Discussion (0). Continue with ORCID to comment.