PetriBench tests large language models on complex changing systems
PetriBench: Benchmarking LLM Reasoning over Dynamic State Spaces
Computation and LanguageArtificial IntelligenceLogic in Computer Science
Summary
Understanding how large language models (LLMs) reason through problems that involve changing situations is still hard. This paper introduces PetriBench, which uses a formal way to describe complex, changing systems called Petri nets to test LLM reasoning. The benchmark includes problems that vary in difficulty and length, with clear correct answers for evaluation. The researchers tested several LLMs and found that performance dropped as problems got harder, revealing different strengths depending on the task. They also discovered that more computing power at test time can help, but its effect changes with different problem types.
What this means in practice
- •For ai developers: Evaluate how well AI models handle reasoning about complex, changing scenarios using a formal, extensible set of tests.
- •For software testers: Use a scalable benchmark to check if AI tools accurately follow state changes in concurrent or distributed system simulations.
Authors
Pyrros Koussios, Benjamin Jäger, John Hua Yao, Ajay Sridhar, Violet Xiang, Chenhao Li
Abstract
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.