- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces PetriBench, a procedurally generated benchmark for evaluating LLM reasoning over dynamic state spaces represented by Petri nets. It comprises six tasks spanning finite and infinite-horizon properties and uses automatically verified ground truth. Experiments across proprietary and open-weight models investigate accuracy, reasoning effort, structural difficulty, and task-specific capability profiles.
Critical strengths
The work presents a coherent and extensible evaluation framework, with a formal foundation, exact answer verification, controlled generation, and a broad empirical study. The analyses of reasoning effort and task-specific performance go beyond simple leaderboard comparisons. The benchmark could be useful to the community if its validity and generalization properties are further established.
Critical weaknesses
The main concern is construct validity. Because several task families are built using property-preserving generators, strong performance on the benchmark may reflect recognition of generator-specific structures rather than generalizable Petri-net reasoning. The simple-feature shortcut analysis does not adequately rule out stronger structural shortcuts. The proposed complexity controls also vary in meaning across tasks and may be confounded by graph size and prompt length. In addition, cross-model comparisons are affected by differing inference configurations, while the external ranking correlation does not establish incremental validity beyond general model strength.
Questions for authors
How do you establish that PetriBench measures general Petri-net reasoning rather than models’ ability to exploit recurring motifs or structural patterns in your generator? How do you ensure that the Easy/Medium/Hard settings and comparisons across models reflect reasoning ability rather than confounds such as graph size, prompt length, branching factor, and inference-time compute?
4 comments
Rebuttal by Authors (2/3)
Disentangling Complexity and Input Length - (W4)
We agree that increasing causal depth necessarily introduces additional net structure and therefore increases input length, reflecting a broader challenge in evaluating increasingly complex reasoning problems [1,2,3,4]. However, to demonstrate that input length alone does not explain the observed difficulty progression, we introduce a new experiment in Appendix A.7, comparing causal-heavy nets, generated predominantly through property-relevant causal structure, and distractor-heavy nets, generated predominantly through distractor structure, while maintaining approximately matched input-token lengths across difficulty levels. Despite comparable input lengths, we observe accuracy differences of up to 23 percentage points, demonstrating that structural composition substantially influences difficulty beyond prompt length alone. Furthermore, the original PetriBench instances generally remain more challenging than either alternative, supporting our choice to jointly incorporate causal and distractor structure to maximize difficulty within a constrained token budget.
Accompanied by preliminary experiments with simple chain-structured Petri nets, where even relatively weak models successfully handled nets containing over 5,000 places, these results demonstrate that input length alone cannot account for the observed difficulty differences, substantially weakening the argument that PetriBench's difficulty progression is primarily driven by increasing prompt length.
Inference Configuration Differences - (W5)
Inference configurations naturally differ across model providers, making perfectly standardized comparisons impossible, as certain parameters, such as temperature, output-token limits, and reasoning effort, are not uniformly exposed or configurable across APIs. Wherever possible, we follow the default inference settings recommended by the respective model providers, rather than imposing arbitrary configurations. We explicitly report all reasoning efforts and inference parameters in Table 15. Furthermore, we provide both accuracy as a function of reasoning-token count in Figure 4 and accuracy as a function of evaluation cost in Figure 21, allowing models to be compared along multiple axes. These measures represent the most rigorous comparisons possible under current API constraints, and we would welcome greater standardization if model providers exposed consistent inference controls.
[1] Hendrycks et al. "Measuring Mathematical Problem Solving With the MATH Dataset" NeurIPS 2021
[2] Tang et al. "Grapharena: Evaluating and exploring large language models on graph computation" ICLR 2025
[3] Zhoou et al. "GSM-Infinite: How Do Your LLMs Behave over Infinitely Increasing Context Length and Reasoning Complexity?" ICML 2025
[4] He et al. "Can LLMs Reason Structurally? Benchmarking via the Lens of Data Structures" ICML 2026
Rebuttal by Authors (3/3)
Correlation and Benchmark Contribution - (W6)
Our contribution is not to identify an orthogonal dimension of intelligence or produce substantially different model rankings, but to offer a more principled framework for evaluating these capabilities. As PetriBench is designed to evaluate fundamental reasoning capabilities, the strong correlation with existing intelligence indices is precisely what we would hope to observe. Notably, in Appendix A.5, we show that PetriBench correlates more strongly with the Intellgence Index (0.94) than with the Agentic (0.85) or Long-Context (0.74) indices. This alignment is consistent with PetriBench primarily evaluating fundamental reasoning capabilities underlying general model intelligence, rather than specialized capabilities such as long-context processing or agentic execution.
However, PetriBench offers several advantages over the benchmarks underlying the reported 0.94 correlation, including:
- Self-Contained Evaluation: All necessary semantics are specified in the prompt through a small set of transition rules, eliminating dependence on external domain knowledge, unlike mathematical [1] or programming benchmarks [2] that require substantial prior knowledge.
- Exact Verifiability: Every answer is objectively determined either by construction or through formal methods, eliminating the need for subjective evaluation or LLM-based judges [3].
- Procedural Scalability: Unseen, solver-verified instances can be generated automatically across controlled difficulty levels, avoiding the manual problem construction and annotation required by many widely used reasoning benchmarks [4].
- Representational Compactness: Relatively small Petri nets can induce state spaces ranging from a single marking to infinitely many reachable markings, supporting diverse reasoning tasks within a single, unified formalism.
Thus, taken together, PetriBench's core contribution lies in it's ability to evaluate fundamental reasoning capabilities without many of the methodological and practical challenges faced by existing benchmarks. We have updated the manuscript to better emphasize these contributions in response to the reviewer's feedback.
[1] Hendrycks et al. "Measuring Mathematical Problem Solving With the MATH Dataset" NeurIPS 2021
[2] Jimenez et al. "SWE-bench: Can Language Models Resolve Real-world Github Issues?" ICLR 2024
[3] Zheng et al. "Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena" NeurIPS 2023
[4] *Cobbe et al. "Training Verifiers to Solve Math Word Problems" arXiv 2021
Friendly reminder
Thank you again for your valuable time and insightful feedback on our work. We have submitted our rebuttal addressing the concerns you raised, and we would be very grateful to know if our responses have clarified these points. We are eager to engage in further discussion if any questions remain.
Rebuttal by Authors (1/3)
We thank the reviewer for their careful reading and constructive feedback! We discuss the main points raised below.
Construct Validity and Generation Bias - (W1)
We appreciate the reviewer's concern regarding the potential influence of generator-specific structures on model performance. Any procedurally generated benchmark necessarily samples from a particular distribution, and exhaustive coverage of the infinite space of possible Petri nets is impossible. PetriBench addresses this through substantial structural diversity, with randomized generation across broad ranges of causal and distractor factors. Importantly, all evaluations are independent, and models receive only the serialized Petri net, without access to generator identities, construction rules, or labels. Moreover, recognizing structural properties is itself a legitimate form of Petri-net reasoning, particularly when identifying cycles, invariants, and enabling conditions.
We nevertheless investigate the reviewer's concern directly through a new experiment in Appendix A.4, constructing counterfactual variants of existing PetriBench instances through minimal structural modifications that change their formally verified answers. Boolean labels are flipped and integer answers are altered, while nearly all of the original net structure is preserved. We observe broadly consistent model accuracy across original and modified instances, despite the changes in correct answers. If models relied primarily on superficial features of the original generated structures, we would expect these modifications to substantially degrade performance. Instead, these results provide additional empirical evidence that models respond to the semantic consequences of structural changes rather than relying on generation-specific biases.
We further emphasize the 0.94 correlation with the Artificial Analysis Intelligence Index reported in Appendix A.6. This strong alignment with established measures of general model reasoning ability points towards PetriBench evaluating broadly relevant reasoning abilities rather than disproportionately favoring models that happen to perform well on particular generator-specific structures.
Taken together, PetriBench's structural diversity, its strong alignment with general model capabilities, and the counterfactual results provide strong evidence for the validity of our procedural generation approach and indicate that models are reasoning over the underlying Petri nets rather than relying on spurious shortcuts to arrive at the correct answers.
Structural Shortcut Analysis - (W2)
We believe our existing shortcut analysis in Appendix A.3 provides meaningful evidence against superficial label inference, as it evaluates whether directly observable structural features of the nets can predict the correct answers, even when explicitly trained to do so. Importantly, all PetriBench evaluations are independent trials and zero-shot: models receive neither previous instances nor their answers, preventing any in-context learning of genreator-specific correlations. Unlike the supervised shortcut baseline, models are therefore not provided with examples from which to learn statistical relationships between net features and correct answers. Furthermore, recognizing more complex structural properties, such as cycles and invariants, is itself a legitimate form of Petri-net reasoning rather than a shortcut.
To further substantiate this argument, we point the reviewer to the new experiment in Appendix A.4, discussed above, in which minimal modifications change the verified answers while preserving nearly all of the original net structure. Model accuracy remains broadly consistent across original and modified instances, whereas reliance on superficial structural cues associated with the original answers would be expected to reduce performance. Together, these complementary analyses provide strong evidence that model predictions reflect the underlying Petri net semantics rather than spurious correlations/biases.
Task-Specific Complexity Controls - (W3)
The task-specific nature of our complexity controls is intentional, as different Petri net properties require different reasoning operations, making a universal complexity metric neither natural nor necessarily informative. Nevertheless, our controls follow a common underlying principle: increasing the depth of property-relevant causal dependencies independently of the amount of additional distractor structure.