When Do Transformers Learn Heuristics for Graph Connectivity?
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.
68f9b3f2b9b2e4ae04673918
Qilin Ye
68f9b3f2b9b2e4ae04673919
Deqing Fu
claimed_verified
2025-10-23T14:46:13.568Z
63c8454e46421a2efe82709d
https://cdn-avatars.huggingface.co/v1/production/uploads/63c8454e46421a2efe82709d/3BcSk4KOwAgWHEPVtsAV3.png
Deqing Fu
user
deqing
68f9b3f2b9b2e4ae0467391a
Robin Jia
68f9b3f2b9b2e4ae0467391b
Vatsal Sharan
When Do Transformers Learn Heuristics for Graph Connectivity?
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.
Transformers struggle with generalizable algorithms, preferring heuristics; a disentangled Transformer can learn graph algorithms within its capacity but resorts to heuristics otherwise.
Transformers disentangled Transformer graph connectivity adjacency matrix training-dynamics model capacity graph diameter algorithmic solution degree-based heuristic