Formalizing and Mitigating Structural Distortion in LLM Attention for Zero-Shot Graph Reasoning
For researchers using LLMs on graph-structured data, this work reveals a fundamental mechanism behind performance degradation and offers a simple fix, though the improvement is incremental.
The paper identifies that linearizing graphs into sequences for LLMs causes bandwidth-dependent attention decay due to rotary positional embeddings, suppressing attention between graph-adjacent nodes. They propose GaLA, a lightweight inference-time modification that biases attention toward graph-adjacent nodes, improving performance on TAG benchmarks with negligible overhead.
Large Language Models (LLMs) have shown promise for reasoning over Text-Attributed Graphs (TAGs). However, applying LLMs to graphs requires linearizing their structure into sequences, introducing distortion rooted in the graph bandwidth problem. While this distortion has been shown to degrade performance, it is often attributed to prompt design or model scale, leaving the underlying mechanism unclear. In this work, we show \textit{how} rotary positional embeddings turn graph linearization into bandwidth-dependent attention decay, suppressing attention between graph-adjacent nodes that are forced far apart in the serialized sequence. This shifts the focus of LLM-based graph reasoning from prompt engineering and scaling toward correcting attention misalignment. Motivated by this analysis, we propose \textbf{G}raph-\textbf{a}ligned \textbf{L}anguage \textbf{A}ttention (\textbf{GaLA}), a lightweight, inference-time modification for LLMs. GaLA biases attention toward graph-adjacent nodes while preserving the LLM's sequential inductive biases. Across TAG benchmarks, GaLA improves performance with negligible overhead, demonstrating that distortion is a correctable bottleneck in LLM-based graph reasoning.