- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces GraphTraceBench, which includes two synthetic tasks designed to evaluate graph execution. In the Path task, models perform arithmetic along a unique directed path; in the BFS task, they perform arithmetic according to the order in which nodes are discovered by breadth-first search. The benchmark provides annotations of the intermediate execution traces and evaluates graph transformers and language models across tasks with different execution horizons.
Critical strengths
- The benchmark asks models to follow graph-dependent procedures, rather than only predict a graph-level label. The Path and BFS tasks cover two distinct forms of execution: following a specified route and processing nodes in discovery order.
- Providing execution traces makes it possible to examine where a model's answer diverges from the intended procedure. This gives the benchmark more diagnostic detail than final-answer accuracy alone.
- Varying the number of steps allows the paper to examine how performance changes as the required computation grows. This is useful for assessing whether a model can sustain a procedure beyond short examples.
- Evaluating both graph transformers and language models broadens the empirical scope and provides a starting point for studying how different architectures handle the two tasks.
Critical weaknesses
- A deterministic edge-order shortcut undermines the benchmark's central evaluation claim. In all 3,000 inspected Path test examples, the first path_hops edges form the target path, and arithmetic over this prefix yields the correct answer; in all 2,500 inspected BFS test examples, discovery-tree edges occupy an ordered prefix that likewise suffices to reproduce every answer. Consequently, perfect accuracy on these released LLM test files is possible without recovering the path or performing BFS, so answer accuracy alone cannot support claims about latent graph-execution ability. This finding does not establish that the evaluated models used the shortcut or that it occurs in other splits. The authors should randomize edge order independently of the target trace, regenerate the affected data, and report edge-order baselines and results across multiple permutations of each graph.
- In the joint-output setting, Qwen2-VL's Path trace accuracy is near 100% at longer lengths while answer accuracy falls sharply. Oracle-path results likewise leave substantial execution errors. These findings require a narrower interpretation of what the benchmark has diagnosed.
- Section 3.3 describes leave-one-length-out training, but Figure 2 and Section 4.2 report single train-length/test-length comparisons, leaving the generalization setting unclear. RQ2 promises a zero-shot versus few-shot analysis without reporting a controlled comparison. Moreover, cross-family results mix graph transformers trained from scratch, LoRA-adapted language models, and zero-shot API models, so performance differences cannot be attributed to architecture alone. The authors should clarify each training and testing protocol, add the promised prompting comparison, and qualify conclusions drawn across model families.
- Section 4.2 explains the difficulty of BFS by stating "the number of possible computational paths grows exponentially with depth", which is not accurate: the task is to execute a definite BFS discovery sequence. It is recommended to describe the growth of the number of discovered nodes, the size of the frontier, and the number of execution steps, and provide statistics.
Questions for authors
See weakness.
2 comments
Dear Reviewer 2GzN,
As the discussion period closes on November 18, we would like to briefly check whether our response addresses your concerns. In summary:
- Edge-order shortcut: we confirmed the issue and regenerated the data with fully shuffled Path edges and interleaved, locally order-preserving BFS edges; the prefix baseline no longer solves the tasks beyond BFS depth 1.
- Trace vs. answer: we reran the joint-output and oracle-path experiments on the revised data and narrowed our interpretation accordingly.
- Protocols: we clarified the training and testing setting of each experiment and removed the unfulfilled few-shot claim.
- BFS difficulty: we replaced the "exponential paths" statement with measured statistics (discovered nodes, peak queue size, arithmetic steps).
We would be glad to clarify anything further.
We thank the reviewer for the careful reading and constructive feedback. We address the main concerns below.
All accuracies below are percentages.
1. Edge-order shortcut
Thank you for identifying this issue. The original serialization placed target-path or ordered BFS discovery-tree edges first, allowing prefix computation to bypass graph execution. We revised the pipeline: Path permutes all edges; BFS interleaves outgoing-edge lists from different sources while preserving each source's local order. Indices are updated, and discovery order, discovery-parent edges, intermediate values, and answers are checked for consistency.
On revised allop test sets (500 examples per horizon), the prefix baselines yield:
Path executes the first
path_hopsedges. BFS scans until an edge's source is undiscovered or its destination is already discovered, without a FIFO queue. All test examples enter the denominator. The previously perfect rule is no longer generally effective. BFS-1 remains high; unlike deeper BFS, it requires only source-level discovery, without multi-level FIFO expansion.For BFS, we also evaluated five permutations (seeds 1001–1005) of the same 500 graphs per depth using frozen RQ1 checkpoints. All 12,500 instances passed the consistency checks above.
“Ref.” is the revised test set's reference serialization, not the original dataset. “Perm.” reports mean ± sample SD across five permutations. The maximum change in mean accuracy is 1.28 percentage points (before rounding). However, deeper-BFS accuracy is near the majority-label baseline, so permutation stability does not exclude other shortcuts.
Majority baselines always predict the training-set modal label (see Reviewer 1):
2. Trace recovery and answer generation
The original prefix directly exposed the target trace; near-perfect trace accuracy therefore did not establish that the model learned path recovery from graph structure. We reran joint trace-and-answer prediction on revised data and evaluated answer generation with correct path information in the oracle setting.
Qwen2-VL-2B results (500 test examples per length):
At length 6, trace accuracy is 51.0%, but answer accuracy given a correct trace is 4.7%. Long-horizon answer accuracy is also near majority-label levels in both the original and revised experiments. We will replace all LLM results based on the original serialization.
3. Evaluation protocols
RQ1 trains at one horizon and tests across horizons. RQ3 trains jointly on all horizons and evaluates independent test splits at each horizon to analyze performance and representations. All RQ3 test horizons occur during training; it does not test unseen-horizon generalization. We will correct Section 3.3, distinguish these settings, and add the RQ3 test results.
We will remove the unreported zero-shot/few-shot comparison from RQ2 and restrict RQ2 and Section 4.3's title to operator sensitivity.
4. BFS difficulty
BFS executes one deterministic discovery sequence, not all possible paths. We will remove the claim of exponentially growing computation paths and report actual workload statistics instead.
The main setting uses N=5D+1 nodes at depth D, so depth, graph size, and execution length increase together. Test-set means are:
We also report a fixed-24-node control. “Scaled” denotes N=5D+1:
With 24 nodes, both models perform poorly even at shallow depths, without monotonic decline. We will distinguish depth from execution length and report node, queue, and inspection counts. This does not imply that depth has no effect.