GraphTraceBench: Diagnosing Long-Range Reasoning in Graph Transformers and Large Language Models

Long-range reasoning over graphs requires models to recover latent computation traces and execute multi-step operations beyond local neighborhoods. We introduce GraphTraceBench, a synthetic benchmark suite for controlled evaluation of long-range graph reasoning. GraphTraceBench contains two complementary tasks: GraphLR-Path, where the target is obtained by executing arithmetic operators along the unique directed path from a source node to a destination node, and GraphLR-BFS, where the target is defined by an arithmetic program executed over the breadth-first discovery order of a directed graph. The benchmark allows independent control over graph size, reasoning depth, operator vocabulary, value range, and distractor density, and provides explicit path and traversal annotations for fine-grained error analysis at different execution horizons. We evaluate graph-native transformers and foundation models under matched graph-execution tasks, using both structured and text-serialized graph inputs. Across models, performance degrades sharply as reasoning depth increases, and cross-length generalization remains poor, suggesting that current models often fail to learn length-invariant graph execution procedures. Additional analyses reveal that operator composition, distractor structure, and input modality substantially affect model behavior. GraphTraceBench provides a diagnostic testbed for studying whether graph-native and large language models can perform controlled long-range execution over directed graphs.