When Do Transformers Learn Heuristics for Graph Connectivity?
Qilin Ye, Deqing Fu, Robin Jia, Vatsal Sharan
2025-10-23
Summary
This research investigates why powerful Transformer models, often used in artificial intelligence, sometimes learn to solve problems in a clever but ultimately limited way, instead of learning a general, reliable solution.
What's the problem?
Transformers are really good at many tasks, but they often rely on shortcuts and patterns specific to the training data rather than truly understanding the underlying rules of a problem. This means they don't generalize well to new situations. The researchers wanted to understand *why* this happens, specifically looking at problems involving graphs – networks of connected points.
What's the solution?
The researchers simplified a Transformer model and studied how it learned to analyze graphs. They mathematically proved that this simplified model can only reliably solve graph problems where the graphs aren't too 'spread out' (specifically, graphs with a 'diameter' of up to 3 raised to the power of the number of layers in the model). They found that if the training data consists of graphs within this limit, the model learns the correct algorithm. However, if the training data includes more complex graphs, the model learns a simpler, less accurate rule based on how many connections each point in the graph has. They then tested this by carefully controlling the complexity of the training data and showing that limiting the data to simpler graphs forces the Transformer to learn the correct algorithm.
Why it matters?
This work is important because it helps us understand the limitations of Transformers and how to build more robust AI systems. By understanding *how* these models learn, and what kinds of data lead to good or bad learning, we can design better training strategies and architectures that encourage Transformers to learn generalizable algorithms instead of relying on fragile shortcuts.
Abstract
Transformers often fail to learn generalizable algorithms, instead relying on brittle heuristics. Using graph connectivity as a testbed, we explain this phenomenon both theoretically and empirically. We consider a simplified Transformer architecture, the disentangled Transformer, and prove that an L-layer model has capacity to solve for graphs with diameters up to exactly 3^L, implementing an algorithm equivalent to computing powers of the adjacency matrix. We analyze the training-dynamics, and show that the learned strategy hinges on whether most training instances are within this model capacity. Within-capacity graphs (diameter leq 3^L) drive the learning of a correct algorithmic solution while beyond-capacity graphs drive the learning of a simple heuristic based on node degrees. Finally, we empirically demonstrate that restricting training data within a model's capacity leads to both standard and disentangled transformers learning the exact algorithm rather than the degree-based heuristic.