Discovering Mechanisms in Tokenized Graph Transformers

We investigate the internal mechanisms of a tokenized graph transformer — a T5 encoder trained on graphs represented as sequences of node and edge tokens — to understand how a transformer can understand and solve graph tasks. Using mechanistic interpretation tools such as activation patching and linear probing, we aim to understand the model under three fundamental graph tasks: degree counting, ring membership, and shortest-path distance. Our analysis reveals a common early local-structure computation, where degree-like features emerge in shallow layers and directly used to solve degree counting. Then, the model composes this early signal differently according to each task. In ring membership, we find that the model solves this problem by gathering non-ring node evidence rather than building a cycle detection circuit. In the shortest-path distance task, causal evidence supports a serial pipeline in which early local topology feeds a single adjacency-copy head, followed by later refinement of a distance-like representation. Finally, we provide discussions on how much will our empirical evidence will hold across different settings, as well as limitations and potential research directions.