When Do Transformers Learn Heuristics for Graph Connectivity?
Authors: name: Qilin Ye, name: Deqing Fu, name: Robin Jia, name: Vatsal Sharan

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.