# PetriBench: Benchmarking LLM Reasoning over Dynamic State Spaces

arXiv: https://arxiv.org/abs/2609.19883 · HTML: https://mlsanity.com/paper/2609.19883/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 24 of its 36 references that are in the map.
- First posted on arXiv 17 Sep 2026.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)

## Builds on (most cited first, 24 of 24)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [SafetyBench: Evaluating the Safety of Large Language Models](https://mlsanity.com/paper/2309.07045/) (2023)
- [ARC-AGI-2: A New Challenge for Frontier AI Reasoning Systems](https://mlsanity.com/paper/2505.11831/) (2025)
- [Talk like a Graph: Encoding Graphs for Large Language Models](https://mlsanity.com/paper/2310.04560/) (2023)
- [GraphArena: Evaluating and Exploring Large Language Models on Graph Computation](https://mlsanity.com/paper/2407.00379/) (2024)
- [Entity Tracking in Language Models](https://mlsanity.com/paper/2305.02363/) (2023)
- [PM-LLM-Benchmark: Evaluating Large Language Models on Process Mining Tasks](https://mlsanity.com/paper/2407.13244/) (2024)
- [LLM CHESS: Benchmarking Reasoning and Instruction-Following in LLMs through Chess](https://mlsanity.com/paper/2512.01992/) (2025)
- [GraCoRe: Benchmarking Graph Comprehension and Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2407.02936/) (2024)
- [Lost in Serialization: Invariance and Generalization of LLM Graph Reasoners](https://mlsanity.com/paper/2511.10234/) (2025)
- [Exploring State Tracking Capabilities of Large Language Models](https://mlsanity.com/paper/2511.10457/) (2025)
- [The Illusion of Procedural Reasoning: Measuring Long-Horizon FSM Execution in LLMs](https://mlsanity.com/paper/2511.14777/) (2025)
- [Computational Reasoning of Large Language Models](https://mlsanity.com/paper/2504.20771/) (2025)
- [A Two-Stage Reflection and Reprompting Framework for LLM-Based Solution of Petri Net Reachability Problems in Industrial Applications](https://mlsanity.com/paper/2606.29627/) (2026)

## Abstract (arXiv)

Characterizing LLM reasoning remains an open challenge, as many existing benchmarks isolate specific reasoning skills, rely on external knowledge, or are costly to extend. We introduce PetriBench, a compact, fully self-contained, and scalable benchmark for evaluating LLM reasoning over dynamic state spaces using Petri nets, a mature formalism for modeling real-world concurrent and distributed systems. PetriBench organizes reasoning into four task families varying by scope and temporal horizon, with Easy, Medium, and Hard levels generated by increasing structural complexity and evaluated against exact ground truth. Across a diverse set of proprietary and open-weight models, accuracy decreases consistently with difficulty, while harder instances expose increasingly distinct task-specific capability profiles. Additional analyses show that test-time compute improves performance but interacts differently with different reasoning tasks, and that procedural generation yields smooth scaling with structural complexity. Together, these results show that PetriBench provides a unified and extensible setting for probing the strengths, limits, and scaling behavior of LLM reasoning.