Transformers' Graph Connectivity Learning Depends on Graph Structure

A new study investigates whether transformer-based Large Language Models (LLMs) can learn to infer transitive relations from training examples, a capability essential for reasoning tasks such as causal inference. The task is equivalent to determining connectivity in directed graphs: if A connects to B and B connects to C, then A connects to C. Prior work examined in-context learning of transitivity, but this research focuses on learning from training data and the impact of scaling. The findings reveal that transformers can learn connectivity in some graph structures but not others, highlighting limitations in their reasoning abilities.