acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
datasets and benchmarks
Keywords:
Graph Reasoning, Long-Range Graph Reasoning Algorithmic Banchmark, Graph Transformers

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_2GzNOpenReview ↗
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
  1. 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.
  2. 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.
  3. 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.
  4. 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
  1. 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.
  2. 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.
  3. 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.
  4. 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

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:

Length/depthPathBFS
16.880.8
22.24.8
32.22.0
41.02.6
50.21.8
60.0—

Path executes the first path_hops edges. 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.

DepthGraphGPS ref.GraphGPS perm.Exphormer ref.Exphormer perm.Qwen2-VL-2B ref.Qwen2-VL-2B perm.
125.424.2 ± 0.927.628.0 ± 0.522.622.4 ± 0.3
25.45.9 ± 1.28.27.9 ± 0.47.67.6 ± 0.2
33.24.0 ± 0.55.44.1 ± 0.54.45.1 ± 0.5
44.43.6 ± 0.92.42.8 ± 0.44.44.6 ± 0.2
52.62.4 ± 0.31.82.2 ± 0.24.23.9 ± 0.1

“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):

Taskallop
BFS-110.8
BFS-25.4
BFS-34.6
BFS-45.0
BFS-54.8

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):

LengthTraceAnswerJointAnswer given correct traceOracle answer
1100.099.499.499.498.6
299.820.620.620.633.4
379.610.28.610.810.6
467.09.25.68.411.4
560.06.04.67.77.0
651.05.22.44.75.4

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+1N=5D+1 nodes at depth DD, so depth, graph size, and execution length increase together. Test-set means are:

DepthNNodes found (incl. source)StepsMax. layer widthPeak FIFO queueEdge inspections
165.04.04.04.04.0
2119.08.05.05.49.1
31613.012.05.56.114.2
42116.915.95.86.519.2
52620.919.96.16.824.5

We also report a fixed-24-node control. “Scaled” denotes N=5D+1N=5D+1:

DepthGraphGPS scaledGraphGPS 24 nodesQwen2-VL scaledQwen2-VL 24 nodes
125.44.022.63.8
25.42.27.64.4
33.21.84.44.6
44.42.84.43.8
52.62.44.23.4

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.

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.

Reviewer_j5wuOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

GraphTraceBench studies whether graph Transformers and large language models can truly perform long-range, multi-step reasoning on graphs. The benchmark contains two tasks: GraphLR-Path requires executing arithmetic operations edge by edge along the unique directed path from the source node to the target node; GraphLR-BFS requires executing the same operations in the BFS discovery order starting from the source node. The data are synthetic: the generator controls graph size, reasoning horizon, operators, value range, and distractor structure, and each sample comes with the complete path and traversal trace. The authors evaluate nine graph Transformers, two LoRA-fine-tuned open-source models (Qwen2-VL, Qwen3-VL), and two zero-shot closed-source models (GPT-5.4, Claude Opus 4.7). The results show that accuracy drops markedly as reasoning depth increases, that models struggle to generalize to path lengths or traversal depths not seen during training, and that the BFS task is harder than the single-path task.

Critical strengths
  1. The synthetic data generation pipeline is clear. The generator is clean, controllable, and precisely verifiable: path uniqueness is strictly enforced, BFS layers and order are verified by simulation, the symbolic solver reaches 100% accuracy, and the complete traces are publicly released.
  2. Appendix C.1, Table 2 reports perfect path-trace prediction but only 9.0% answer accuracy for the jointly trained Qwen2-VL model at path length six. This separates explicit trace prediction from successful arithmetic execution in that configuration. The symbolic solver checks consistency on evaluated instances; it does not establish that every neural model receives the ordering information needed for the BFS target.
Critical weaknesses
  1. Section 4.1 and Appendix B acknowledge the unmatched adaptation protocols, so the comparison limits controlled ranking claims rather than concealing an unfair setup. A matched zero-shot control is useful; adding more model families is secondary. More essential are the full prompts, exact checkpoints, output budgets, reasoning settings, parser rules, and invalid-output rates. For graph transformers, the task is described as regression, but the prediction head, loss, normalization, and conversion to integer predictions are insufficiently specified for interpreting exact-match accuracy. Please document these and audit representative short-horizon failures.
  2. Table 1 reports 5,000 graphs per fixed-horizon dataset, 20,000 per mixed dataset, and an 80/10/10 split. The missing information is the mapping of each result to its training horizons, checkpoint, test split, and evaluated sample count. Section 3.3 describes leave-one-horizon-out training, whereas Section 4.2 and Figure 2 describe single train-horizon/test-horizon pairs. These are different protocols; an interior held-out horizon tests interpolation rather than extrapolation beyond the training range. The original concerns about absent few-shot results and the input-modality claim remain valid: the GT/LLM comparison changes architecture and adaptation as well as modality.
  3. The BFS target requires a precise, model-visible traversal convention. Mixed arithmetic makes within-layer discovery order affect the answer. Section 4.1 supplies LLMs with edges in inspection order, while the GT input description lists node values, markers, connectivity, and operators. Edge storage order alone is unavailable to an edge-permutation-invariant architecture. Figure 1 mentions pseudotime features without defining their role, and Appendix C.4 shuffles edges while preserving traces and labels. Please specify the tie-break and order-bearing features for every model and show that each control retains enough information to identify its target. This is an unresolved specification issue, not proof that the implemented dataset is invalid.
  4. The mechanistic conclusions exceed the controls. A less hop-separated t-SNE plot does not establish greater dependence on graph structure, and label-noise sensitivity across differently pretrained and adapted models does not isolate that dependence (Sections 4.4–4.5). Please narrow these claims or use focused controls, such as removing the explicitly supplied horizon and reporting absolute corrupted-label performance. The operator discussion should also retain Appendix C.6's caveat: at depth/length three, MD has roughly 28% modal-label frequency and 42–44% identity steps, so higher raw accuracy does not establish greater multiplication/division competence.
Questions for authors
  1. For a benchmark, evaluating only four LLMs is narrow coverage. Could you evaluate more models, including open-source text-only LLMs of different sizes (e.g., Qwen3, Llama, DeepSeek), models with and without reasoning modes, and other closed-source families (e.g., Gemini)?
  2. Could you report zero-shot results for the open-source models without fine-tuning, so that open- and closed-source models are compared under the same protocol? Could you also report the mean and standard deviation over multiple repetitions?
  3. What determines and encodes BFS inspection order for each GT, and how is it preserved in the edge-order control? Please reconcile the generalization protocols and provide the prediction and parsing details above. For uncertainty, distinguish independent training seeds from repeated decoding; repeated deterministic decoding does not measure training variability.
4 comments

We thank the reviewer for the careful reading and constructive feedback. We address the main concerns below.

1. Experimental details

Thank you. Settings and code are already provided; full prompts are in the linked scripts and will be added to the appendix.

  • Checkpoints: GTs use best.pt (lowest validation MAE); Qwen2-VL uses Qwen2-VL-2B-Instruct with the final task-specific LoRA adapter.
  • Budgets: 128 new tokens for SFT answer-only evaluation, 256 for joint trace/answer evaluation, and 4,096 for the added zero-shot/reasoning comparisons.
  • Reasoning: Qwen2-VL has no dedicated thinking mode. GPT-5.4 default omits the reasoning parameter; our interface defaults to none.
  • Parsing: We accept complete/trailing answer JSON or a plain integer, count unparseable outputs as incorrect, and separately report parsing failures and strict JSON compliance.
  • GT prediction: An MLP outputs a scalar; training uses MSE on raw, unnormalized targets. Accuracy uses torch.round; MAE/RMSE use unrounded predictions. We will add short-horizon failures with targets, raw predictions, and rounded outputs.

2. Zero-shot, reasoning, and training seeds

All accuracies below are percentages; Qwen denotes Qwen2-VL-2B. Default is the original interface configuration (none).

ModelSettingPath-3BFS-3
GPT-5.4default19.025.0
GPT-5.4medium100.098.0
GPT-5.4high99.0100.0
QwenZero-shot7.05.0

Qwen uses the original Instruct checkpoint without fine-tuning, temperature 0, and 4,096 output tokens; Path-3 uses 100 samples. With reasoning enabled, GPT-5.4 reaches 98–100% on fixed 100-example subsets per task. We restrict failure claims to the evaluated direct-answer settings; default failures do not establish general capability limits. Model-size/family coverage remains limited.

We added training seeds 42/43/44 for selected revised configurations, keeping data and splits fixed. SD is the sample standard deviation across independent training runs, not repeated decoding. Qwen below uses LoRA.

ModelTask424344Mean±SD
GraphGPSPath-199.299.899.899.6±0.3
GraphGPSPath-352.452.655.253.4±1.6
GraphGPSPath-616.213.015.414.9±1.7
GraphGPSBFS-125.428.633.629.2±4.1
GraphGPSBFS-33.23.22.63.0±0.3
GraphGPSBFS-52.61.42.22.1±0.6
QwenPath-198.298.898.698.5±0.3
QwenPath-38.68.68.68.6±0.0
QwenPath-65.45.45.45.4±0.0
QwenBFS-122.623.224.423.4±0.9
QwenBFS-34.44.85.04.7±0.3
QwenBFS-54.23.83.83.9±0.2

All seeds show the overall decline in accuracy with increasing execution horizon.

3. BFS order, permutations, and protocols

The original GT inputs lacked required BFS ordering information. Revised GTs encode edge positions and receive bfs_depth. BFS still uses FIFO and local outgoing-edge order. Permutations interleave edges from different sources while preserving order within each source. On 2,500 base graphs and 12,500 permutations, we verified unchanged discovery order, parent edges, intermediate values, and answers.

R/P denote reference/permuted inputs. Each depth has 500 test samples; P reports mean±sample SD over five permutations with fixed checkpoints, not training-seed variation.

DepthGraphGPS RGraphGPS PExphormer RExphormer PQwen RQwen P
125.424.2±0.927.628.0±0.522.622.4±0.3
25.45.9±1.28.27.9±0.47.67.6±0.2
33.24.0±0.55.44.1±0.54.45.1±0.5
44.43.6±0.92.42.8±0.44.44.6±0.2
52.62.4±0.31.82.2±0.24.23.9±0.1

Small average accuracy changes do not establish complete permutation invariance.

As clarified in the General Response, RQ1 trains on one length/depth and tests across horizons. RQ3 trains on all horizons jointly and uses independent test splits at each horizon to analyze one model's performance and representations. RQ3 therefore does not test unseen-horizon generalization. We will correct Section 3.3, distinguish these settings, and add RQ3 test results.

Most GTs concatenate mean-pooled graph and source/target-node representations before the MLP; GraphGPT/G2PT use a sequence-summary token.

4. t-SNE interpretation

After removing explicit length cues such as hop=n from Qwen inputs, Path t-SNE representations still show hop-associated local clustering. Thus, direct reading of the hop field alone cannot explain the pattern. Representation differences imply neither correct execution nor structural reliance; we will narrow the corresponding mechanistic claims.

Dear Reviewer j5wu,

As the discussion period closes on November 18, we would like to briefly check whether our response addresses your concerns. In summary:

  • Protocol details: we documented checkpoints, output budgets, reasoning settings, parser rules, and the GT regression head and rounding.
  • BFS ordering: GTs now receive edge-position features, so the inspection order is available to both model families; label-preserving permutations were verified on 12,500 instances.
  • Generalization protocols: we corrected the inaccurate leave-one-out description and removed the unfulfilled few-shot claim from RQ2.
  • Uncertainty and coverage: we added three-seed results, zero-shot Qwen2-VL, and GPT-5.4 with reasoning enabled, and restricted our claims about frontier LLMs to direct-answer inference.
  • Interpretation: we narrowed the t-SNE and label-noise conclusions and added majority-label baselines.

We would be glad to clarify anything further.

Thanks for the detailed response. I believe that some of my concerns are solved. The protocol details, the fix for the BFS ordering in the GTs, and the three training seeds are helpful.

However, the response mainly adds results, with little analysis. Since this is a benchmark paper, my first question asked for more models, including models with and without reasoning modes. No new model families are added, and the response itself says that model coverage remains limited.

My main concern is the new GPT-5.4 experiment. GPT-5.4 is no longer the newest frontier model, and the original results were obtained with reasoning turned off. Once reasoning is on, it already reaches 98-100% on both horizon-3 tasks in the response. If I were the authors, after getting this table, I would run the reasoning setting on the longer horizons and the full test sets, and also try other frontier models, to check whether the LLM failures still hold. The response does not do this and only restricts the failure claims to direct-answer inference. I guess most people now use frontier LLMs with reasoning, so this restriction makes the main conclusion much narrower.

This experiment does not close the loop. It makes me question whether the paper's core conclusion about LLM failures in long-range graph reasoning still holds, and whether the benchmark is challenging enough for current LLMs. So I will keep my score at 1.

Thank you for suggesting this follow-up. We extended the evaluation of GPT-5.4 with reasoning effort set to high to Path-6 and BFS-5, the longest horizons in the released benchmark. This configuration achieved nearly 100% accuracy on both evaluated subsets.

These results support your concern: the current horizon range does not provide sufficient difficulty to distinguish the capabilities of GPT-5.4 under the high reasoning setting. We therefore withdraw the broad interpretation that frontier LLMs generally fail on these tasks. The observed failures apply to the specific models and inference configurations evaluated, rather than establishing a general limitation of reasoning-enabled LLMs.

We will incorporate these results and revise the abstract, discussion, and conclusion accordingly. The benchmark still enables controlled comparisons and trace-level diagnosis, but we acknowledge that its current range is saturated by GPT-5.4 under the high reasoning setting on the evaluated subsets. Evaluating longer horizons and broader model coverage remains necessary to establish its usefulness as a challenging benchmark for current frontier models.

Reviewer_EMZ4OpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper introduces GraphTraceBench, a synthetic benchmark for testing long-range reasoning over directed graphs. It has two tasks: arithmetic computation along a unique path and arithmetic computation over BFS traversal order. The benchmark provides control over graph size, depth, operators and distractors, along with detailed execution traces. The authors evaluate graph transformers, fine-tuned Qwen models and zero-shot closed-source LLMs. Results show that performance drops as reasoning depth increases. The appendix also studies trace prediction, distractors, operator distributions and label noise. The benchmark is useful, but some issues in the BFS task definition, inconsistent results and unsupported claims need to be addressed.

Critical strengths
  1. The benchmark has a carefully designed data generator with validation checks and detailed execution traces. This makes it useful for studying graph reasoning and analysing errors at intermediate steps.

  2. The appendix provides useful diagnostic experiments. For example, Qwen2-VL achieves high trace accuracy but much lower answer accuracy at greater depths. Removing distractors also improves its length-2 accuracy from 12% to 83%. These results help identify where the model struggles.

  3. The benchmark allows graph transformers and LLMs to be evaluated on the same graph instances. It also provides control over depth, operators and distractors, which can support further research.

Critical weaknesses
  1. The BFS task has a possible issue with how the traversal order is defined. The paper says edge inspection order determines BFS discovery order, but the appendix says randomising edge order preserves the labels. Since subtraction and division are order-dependent, this needs clarification. Otherwise, graph transformers may not have enough information to predict the correct label.

  2. The reported results are inconsistent across sections. For example, Qwen2-VL's length-2 Path accuracy is reported as both 12% and 63.8%, while other results also differ across tables. The paper provides no seed-wise results or confidence intervals. These issues reduce confidence in the benchmark's reference results.

  3. Some main claims are not sufficiently supported. The LLM evaluation uses zero-shot, answer-only outputs without clearly reporting reasoning settings. The cross-length generalisation claim is mainly supported by graph transformer experiments, while the operator difficulty results may be explained by differences in label distributions. The claims should be narrowed or supported with further experiments.

Questions for authors
  1. What exactly determines sibling order in BFS, and how is this information provided to graph transformers? How is this consistent with the claim that randomising edge order preserves labels?

  2. Can the authors explain the inconsistent accuracy numbers across sections and tables, especially Qwen2-VL's length-2 Path results? Can they provide results across multiple seeds?

  3. Which reasoning settings were used for GPT-5.4 and Claude Opus 4.7? Would the conclusions change if reasoning were enabled?

  4. What is the majority-label baseline for each operator setting? This would help establish whether the reported operator difficulty is due to actual reasoning difficulty or differences in label distributions.

1 comment

We thank the reviewer for the careful reading and constructive feedback. We address the main concerns below.

1. BFS order and edge permutations

BFS uses a FIFO queue and inspects each node's outgoing edges in their input-list order, applying arithmetic only upon first discovery. Our earlier wording overlooked that arbitrary edge permutations can change the traversal and answer. We now interleave edges from different sources while preserving each source's local outgoing-edge order. All 12,500 permuted instances preserve discovery order, discovery-parent edges, intermediate values, and answers.

GTs jointly encode current edge positions, endpoint features, and operators; positions are recomputed after permutation. LLMs receive the ordered edge list. Both also receive bfs_depth, providing the order and stopping condition needed to determine the target.

DepthGraphGPS ref.perm.Exphormer ref.perm.Qwen2-VL-2B ref.perm.
125.424.227.628.022.622.4
25.45.98.27.97.67.6
33.24.05.44.14.45.1
44.43.62.42.84.44.6
52.62.41.82.24.23.9

All accuracies are percentages. Each fixed checkpoint is tested on 500 revised examples per depth; permuted accuracy averages five permutations. Reference denotes the revised serialization. Average changes are small, consistent with the paper's overall observation.

2. Different configurations and training seeds

The 12% result uses answer-only prediction; Table 2's 63.8% uses a separately trained, jointly supervised model generating the path and answer in one response. We will label each table's objective, output format, and checkpoint explicitly.

Below are three independent training seeds, with fixed data and splits. Seed values are ordered 42/43/44; SD is the sample standard deviation.

TaskGraphGPS seedsMean±SDQwen2-VL-2B seedsMean±SD
Path-199.2/99.8/99.899.6±0.398.2/98.8/98.698.5±0.3
Path-352.4/52.6/55.253.4±1.68.6/8.6/8.68.6±0.0
Path-616.2/13.0/15.414.9±1.75.4/5.4/5.45.4±0.0
BFS-125.4/28.6/33.629.2±4.122.6/23.2/24.423.4±0.9
BFS-33.2/3.2/2.63.0±0.34.4/4.8/5.04.7±0.3
BFS-52.6/1.4/2.22.1±0.64.2/3.8/3.83.9±0.2

All seeds show the same overall decline with increasing execution horizon.

3. Reasoning settings

Original GPT-5.4 and Claude Opus 4.7 experiments used our interfaces' defaults; GPT-5.4's interface default was none. No dedicated thinking mode was enabled for the selected open models. We additionally compared GPT-5.4 configurations on fixed subsets of 100 Path-3 and 100 BFS-3 examples, with a 4,096-token output budget.

GPT-5.4 settingPath-3BFS-3
default (none)19.025.0
medium100.098.0
high99.0100.0

Explicit reasoning achieves 98–100% on these subsets. We restrict frontier-model failure claims to the evaluated direct-answer configurations; default-setting failures do not establish a general capability limitation.

4. Majority-label baselines

For each task/horizon/operator setting, we select the training-set mode and predict it for every test example. Ties use the smaller label; test labels never determine the prediction.

TaskASMDallop
Path-17.628.417.2
Path-24.426.812.0
Path-33.828.08.6
Path-45.028.68.8
Path-53.627.84.8
Path-62.226.05.4
BFS-13.429.110.8
BFS-21.826.85.4
BFS-32.233.84.6
BFS-41.830.05.0
BFS-53.027.84.8

The mode is 1 for MD/allop and varies for AS. Training sets contain 4,000 examples; test sets contain 500, except BFS-1 MD (501). MD's higher baseline agrees with Appendix C.6's distribution audit.

Qwen2-VL's Path-3/6 outputs are uniformly 1 across seeds, exactly matching the 8.6%/5.4% baselines. These configurations exhibit majority-label collapse. At BFS depths 3–5, model accuracies are generally near or below this baseline. We will report it alongside model scores; near-floor performance limits the diagnostic strength of permutation controls, which are more informative at depths 1–2.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response: Modifications and Corrections

General Response

We thank all reviewers for their careful reading and constructive feedback. Several concerns are shared across the reviews. We summarize the corresponding revisions here and provide further details in our individual responses.

1. Correcting the serialization shortcut

In the original version, the target path edges in Path and the ordered BFS discovery-tree edges in BFS formed an ordered prefix of the edge list. We have revised the serialization procedure: Path now randomly permutes the entire edge list; BFS randomly interleaves the outgoing-edge lists of different source nodes while preserving the relative order within each list, which defines the local inspection order of the task. These BFS permutations preserve the labels. All 12,500 permuted BFS instances passed consistency checks for discovery order, discovery edges, intermediate accumulator values, and final answers.

2. Providing BFS ordering information to graph transformers

The original graph transformer (GT) inputs did not include the information needed to determine the BFS inspection order. GT models now receive edge-position features, recomputed after each permutation, together with bfs_depth.

3. Updated experiments

The numerical tables in these responses report results obtained under the revised setup. We will update the corresponding results in the revised manuscript.

4. Corrections to the manuscript

  • Table 1: BFS graphs use N=5D+1N=5D+1 nodes, corresponding to 6–26 nodes for depths 1–5, rather than a fixed 24 nodes. The 24-node setting applies only to GraphLR-Path. This correction is consistent with the BFS edge-count range of [3, 42] reported in the same table.
  • Evaluation protocols in Section 3.3: The statement that one length/depth is held out for testing while the remaining lengths/depths are used for training is inaccurate and does not describe the protocol actually used. We will replace it with the actual settings: RQ1 trains on a single length/depth and evaluates on all lengths/depths; RQ3 trains on a mixture of all lengths/depths and evaluates on independent test splits at each length/depth. Because all RQ3 test horizons are represented during training, this setting does not evaluate generalization to unseen horizons.
  • Scope of RQ2: We will remove the commitment to a zero-shot/few-shot comparison from the formulation of RQ2.
  • BFS workload: We replace the claim that the number of possible computation paths grows exponentially with depth with measured BFS workload statistics.
AuthorsOpenReview ↗

General Response

Manuscript revision and status of the remaining experiments

We have uploaded a revised manuscript that clarifies the BFS traversal convention and model inputs, corrects the dataset statistics and evaluation protocol, and documents the prompts and scoring procedures. It also includes the updated Qwen2-VL-2B joint trace-and-answer results.

We do not expect to complete the full set of reruns before the discussion deadline. The main result figures therefore retain the results from the original experimental setup, which are labeled accordingly. We will incorporate the remaining results once they have been completed and verified, in accordance with the venue’s revision instructions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.