PetriBench: Benchmarking LLM Reasoning over Dynamic State Spaces
Pyrros Koussios, Benjamin J\"ager, John Hua Yao, Ajay Sridhar, Violet Xiang, Chenhao Li
cs.CL · cs.AI · cs.LO
Quick verdict
Claims a scalable exactly-verified Petri-net LLM reasoning benchmark; credible design, but Hard-tier floor effects and single-run noise temper conclusions.
Summary
The authors introduce PetriBench, a procedurally generated benchmark that evaluates LLM reasoning over dynamic state spaces using weighted place-transition Petri nets. Six tasks span a 2×2 taxonomy of local versus global scope and finite versus infinite horizon: MinimumTokenSteps and ReachableMarkings (integer answers), L0/L4 liveness, deadlock, and boundedness (binary answers). Generators fix the queried property by construction, verified independently with the TINA solver; three difficulty tiers of 1,600 questions each (4,800 total) vary causal generation depth and distractor structure. Evaluating 36 proprietary and open-weight configurations with exact-match scoring, accuracy falls consistently from Easy to Hard (e.g., GPT-5.6 Sol at XHigh: 96.4→77.8), weaker models collapse toward the ~25% aggregate baseline, and the first principal component of task-level performance drops from 91.7% to 78.9%, indicating diverging capability profiles. Rankings correlate strongly (ρ=0.94, n=28) with the Artificial Analysis Intelligence Index. Ablations show serialization format changes absolute scores by at most 6.4 points, CoT prompting matters little at fixed reasoning effort, while disabling internal reasoning collapses accuracy. Main limitations: Hard-tier floor effects for mid/low-tier models, headline tables lack confidence intervals despite single completions at temperature 1.0, and shortcut testing is limited to linear surface statistics rather than learned structural probes.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- PetriBench provides a compact, fully self-contained, procedurally scalable benchmark for LLM reasoning over dynamic state spaces, with six tasks spanning local/global scope and finite/infinite horizon and exact solver-verified ground truth.
- Accuracy decreases consistently with structural difficulty, and harder instances expose increasingly distinct task-specific capability profiles (first principal component drops from 91.7% to 78.9% explained variance).
- Test-time compute improves performance overall, but the relationship between reasoning length and correctness is task-dependent, with only MinimumTokenSteps retaining a positive correlation at the individual-response level after normalization.
- PetriBench model rankings align strongly with established external evaluations (Spearman ρ=0.94 with the Artificial Analysis Intelligence Index, n=28 configurations).
- Benchmark answers cannot be recovered from surface statistics alone (shortcut baselines within ~5pp of trivial baselines on all six tasks).
Strengths
Exact, solver-verified ground truth throughout
Every instance is independently verified with the TINA solver or counterexamples (§3.3, B.1.1); scoring is deterministic exact-match with parse failures counted as incorrect (B.3.2). No LLM judges anywhere — a rare and valuable property for a reasoning benchmark.
Principled property-preserving procedural generation with two difficulty axes
Generators construct the answer-determining core first and add label-preserving distractor structure (§3.2, B.1); difficulty scaling is validated empirically for two models (Fig 6, Fig 12), and identifier permutation plus matched bounded/unbounded and deadlock/non-deadlock pairs (B.1.2) guard against construction-order and surface-size cues.
Shortcut resistance is tested, not just asserted
Informative analyses beyond the leaderboard
Strong external validity and full artifact release
Weaknesses
Hard-tier floor effects compress discrimination
No confidence intervals or repeated sampling on headline results
Template-learnability risk is not fully ruled out
ReachableMarkings horizon is very narrow
Error taxonomy is LLM-generated with limited human verification
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
PetriBench (arXiv 2609.19883, ETH Zürich + Stanford) is a procedurally generated benchmark of 4,800 questions testing LLM reasoning over dynamic state spaces via weighted place-transition Petri nets. Six tasks instantiate a 2×2 taxonomy — local vs global scope crossed with finite vs infinite horizon: MinimumTokenSteps and ReachableMarkings (integer targets), L0/L4 liveness, deadlock, and boundedness (binary targets), each at Easy/Medium/Hard with 1,600 questions per tier (Table 14). The paper claims: (1) a compact, self-contained, extensible benchmark with exact ground truth; (2) monotone accuracy decline with difficulty coupled to increasingly divergent task-specific capability profiles; (3) beneficial but task-dependent test-time compute; (4) external validity via rank correlation with the Artificial Analysis Intelligence Index. The evidence broadly supports these claims, with the caveats below.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is PetriBench?
PetriBench is a benchmark of 4,800 procedurally generated questions testing whether large language models can reason about Petri nets — formal models of concurrent systems with places, tokens, and transitions. It spans six tasks (minimum firing steps, reachable-marking counts, L0/L4 liveness, deadlock, boundedness) across local/global scope and finite/infinite horizon, at three difficulty levels, with every answer verified exactly by the TINA solver.
Which models perform best on PetriBench?
In the paper's 36-configuration evaluation, GPT-5.6 Sol at XHigh reasoning effort leads overall with 96.4% (Easy), 90.9% (Medium), and 77.8% (Hard) exact-match accuracy, followed by Grok 4.6 XHigh and Claude Opus 5 XHigh. Open-weight models such as GLM-5, DeepSeek V3.2, Kimi K2.5, and Qwen3-235B score near the ~25% aggregate random baseline on Hard, driven largely by the integer-counting tasks.
Is PetriBench saturated by frontier models?
No. The best configuration reaches only 77.8% on Hard, and frontier models still lose many points on the integer-counting tasks ReachableMarkings and MinimumTokenSteps. However, several Hard binary tasks (deadlock, boundedness) sit near the 50% chance level for almost all models, so remaining headroom is uneven across task types.
Can models pass PetriBench by exploiting shortcuts?
The authors trained linear models on surface statistics (place/transition/arc counts, token counts, question constants) and found they gain at most about 5 percentage points over trivial baselines across all six tasks. The caveat: because each answer label is tied to a specific generator template, more sophisticated learned structural shortcuts were not tested.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figures 3, 4, 11, 16-18 appear as plot extractions with embedded numeric labels; exact point placements and some stacked-bar compositions could not be fully verified from the extracted text.
- Generator source code and random seeds are referenced as released artifacts but are not part of the extracted text; generation parameters were checked only via Table 12 and Appendix B.1.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.