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 analyze the training-dynamics, and show that the learned strategy hinges on whether most training instances are within this model capacity. 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. Large language models (LLMs) based on the Transformer architecture have demonstrated remarkable capabilities, yet their success is often shadowed by failures on tasks that demand robust, algorithmic reasoning. A growing body of evidence shows that, instead of learning generalizable algorithms, these models frequently rely on brittle shortcuts and spurious correlations that exploit statistical cues in the training data (Niven & Kao, 2019; Geirhos et al., 2020; Tang et al., 2023; Y uan et al., 2024; Zhou et al., 2024b; Y e et al., 2024). This shortcut reliance contributes to poor out-of-distribution (OOD) generalization, vulnerability to adversarial prompts, and unreliability on multi-step reasoning tasks (Zou et al., 2023; Deng et al., 2024; Li et al., 2024). Evidence spans domains: in natural language inference, models pick up lexical-overlap heuristics rather than syntactic reasoning (McCoy et al., 2019; Cosma et al., 2024); and in mathematical problem solving, strong in-distribution scores often fail to transfer as problem structure or size shifts (Saxton et al., 2019; Kao et al., 2024; Zhou et al., 2025). This motivates a foundational question: When and why do Transformers learn heuristics over verifiably correct algorithms, even when the task admits an algorithmic solution? To study when Transformers learn algorithms rather than shortcuts, we adopt graph connectivity as a controlled testbed. Connectivity offers a unique ground-truth solution: given an adjacency matrix A with self-loops, reachability equals the transitive closure and is computable by classical dynamic programming (Warshall, 1962; Floyd, 1962), so the target is unambiguous.