Large Language Models as Graph Computational Solvers via Topology-aware Residual Attention

Large language models increasingly serve as general-purpose reasoning engines, yet they remain unreliable on graph computation tasks whose inputs are discrete, permutation-equivalent, and algorithmic. We propose TRACER, a post-training framework that turns LLMs into native graph computational solvers. Our central thesis is that graph computation failures arise from mismatches within the Transformer computation itself: token order obscures graph symmetries, self-attention is biased toward textual proximity instead of graph topology, and autoregressive decoding weakly constrains algorithmic traces. TRACER addresses these challenges at three coupled levels. At the input level, we introduce permutation-invariant graph encoding, which encourages the LLM to map different serialization variants of a graph to a shared internal graph representation, thereby preserving graph symmetries. At the representation level, we enhance self-attention with the Topology-aware Residual Attention mechanism to inject graph topological signals into the attention kernel. At the reasoning level, we employ process-reward RL to encourage faithful execution of graph algorithmic traces. Across linear-time, polynomial-time, and NP-complete graph tasks, TRACER delivers substantial gains over baselines. These results suggest that equipping LLMs with graph-aware internal computation offers a practical path toward reliable neural solvers for structured algorithmic reasoning. The code is anonymously available here.