Transformers Provably Learn Algorithmic Solutions for Graph Connectivity, But Only with the Right Data

Qilin Ye, Deqing Fu, Robin Jia, Vatsal Sharan
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:148293-148324, 2026.

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 can compute connectivity in graphs with diameters up to $3^L$, implementing an algorithm equivalent to computing powers of the adjacency matrix. By analyzing training dynamics, we prove that whether the model learns this strategy hinges on whether most training instances are within this model capacity. Within-capacity graphs (diameter $\leq 3^L$) drive the learning of the algorithmic solution while beyond-capacity graphs drive the learning of a simple heuristic based on node degrees. Finally, we empirically show that our insights transfer to standard Transformers: restricting training data to stay within a model’s capacity makes both standard and Disentangled Transformers learn the exact algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-ye26f, title = {Transformers Provably Learn Algorithmic Solutions for Graph Connectivity, But Only with the Right Data}, author = {Ye, Qilin and Fu, Deqing and Jia, Robin and Sharan, Vatsal}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {148293--148324}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/ye26f/ye26f.pdf}, url = {https://proceedings.mlr.press/v306/ye26f.html}, 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 can compute connectivity in graphs with diameters up to $3^L$, implementing an algorithm equivalent to computing powers of the adjacency matrix. By analyzing training dynamics, we prove that whether the model learns this strategy hinges on whether most training instances are within this model capacity. Within-capacity graphs (diameter $\leq 3^L$) drive the learning of the algorithmic solution while beyond-capacity graphs drive the learning of a simple heuristic based on node degrees. Finally, we empirically show that our insights transfer to standard Transformers: restricting training data to stay within a model’s capacity makes both standard and Disentangled Transformers learn the exact algorithm.} }
Endnote
%0 Conference Paper %T Transformers Provably Learn Algorithmic Solutions for Graph Connectivity, But Only with the Right Data %A Qilin Ye %A Deqing Fu %A Robin Jia %A Vatsal Sharan %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-ye26f %I PMLR %P 148293--148324 %U https://proceedings.mlr.press/v306/ye26f.html %V 306 %X 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 can compute connectivity in graphs with diameters up to $3^L$, implementing an algorithm equivalent to computing powers of the adjacency matrix. By analyzing training dynamics, we prove that whether the model learns this strategy hinges on whether most training instances are within this model capacity. Within-capacity graphs (diameter $\leq 3^L$) drive the learning of the algorithmic solution while beyond-capacity graphs drive the learning of a simple heuristic based on node degrees. Finally, we empirically show that our insights transfer to standard Transformers: restricting training data to stay within a model’s capacity makes both standard and Disentangled Transformers learn the exact algorithm.
APA
Ye, Q., Fu, D., Jia, R. & Sharan, V.. (2026). Transformers Provably Learn Algorithmic Solutions for Graph Connectivity, But Only with the Right Data. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:148293-148324 Available from https://proceedings.mlr.press/v306/ye26f.html.

Related Material