When Do Transformers Learn Heuristics for Graph Connectivity?
This addresses the problem of algorithmic generalization in transformers for researchers, providing insights into training dynamics, but it is incremental as it builds on existing work on model capacity and heuristics.
The paper investigates why transformers often learn brittle heuristics instead of generalizable algorithms, using graph connectivity as a test case, and shows that training within a model's capacity leads to learning an exact algorithm, while beyond-capacity training results in a degree-based heuristic.
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.