Transformers learn graph connectivity selectively, not universally
New research shows transformers can infer transitive relations on grid-structured graphs but fail on fragmented ones, with scaling helping only certain architectures.
Transformers learn to infer transitive relations on grid-like graphs but struggle with disconnected graph structures.
- — Transformers can infer connectivity on grid-structured directed graphs where nodes embed in low-dimensional space.
- — Graph dimensionality predicts learning difficulty; higher-dimensional grids challenge transformers more than low-dimensional ones.
- — Larger models generalize better to connectivity inference on grid graphs as scale increases.
- — Transformers fail to learn connectivity when graphs contain many disconnected components.
- — Transitive reasoning ability depends on graph topology, not just model capacity or training data volume.
- — Prior work tested in-context learning of transitivity; this study examines learning from training examples.
- — Results suggest transformers rely on geometric structure rather than abstract logical rules for reasoning.
Astrobobo tool mapping
- Knowledge Capture When documenting domain knowledge, explicitly map how separate systems connect. Flag isolated components and create bridging facts before feeding to LLM training or prompts.
- Focus Brief Before deploying an LLM for causal or logical reasoning, write a brief listing all disconnected subgraphs in your domain. Identify which ones the model must reason across and plan explicit linking.
- Reading Queue Queue follow-up papers on transformer mechanistic interpretability and graph neural networks to understand whether hybrid architectures (GNNs + transformers) solve the disconnected-graph problem.
Frequently asked
- Transformers can learn transitive reasoning on grid-structured graphs where nodes embed naturally in low-dimensional space. However, they struggle when graphs contain many disconnected components. Success depends on graph topology, not just model size. Scaling helps on grid graphs but doesn't fix failures on fragmented structures.
cite ▸
APA
Amit Roy, Abulhair Saparov. (2026, April 23). Transformers learn graph connectivity selectively, not universally. Astrobobo Content Engine (rewrite of arxiv/cs.AI). https://astrobobo-content-engine.vercel.app/article/transformers-learn-graph-connectivity-selectively-not-universally-c1d363
MLA
Amit Roy, Abulhair Saparov. "Transformers learn graph connectivity selectively, not universally." Astrobobo Content Engine, 23 Apr 2026, https://astrobobo-content-engine.vercel.app/article/transformers-learn-graph-connectivity-selectively-not-universally-c1d363. Based on "arxiv/cs.AI", https://arxiv.org/abs/2509.22343.
BibTeX
@misc{astrobobo_transformers-learn-graph-connectivity-selectively-not-universally-c1d363_2026,
author = {Amit Roy, Abulhair Saparov},
title = {Transformers learn graph connectivity selectively, not universally},
year = {2026},
url = {https://astrobobo-content-engine.vercel.app/article/transformers-learn-graph-connectivity-selectively-not-universally-c1d363},
note = {Astrobobo rewrite of arxiv/cs.AI, https://arxiv.org/abs/2509.22343},
}