RegexPSPACE benchmark evaluates LLMs and reasoning models on PSPACE-complete regular expression problems

Researchers introduced a benchmark grounded in two PSPACE-complete regular expression problems: equivalence decision (RegexEQ) and minimization (RegexMin), using a dataset of over a million regex instances constructed through double-exponential space exploration.

Evaluations on 6 LLMs (AI models that understand and generate text) and 5 large reasoning models (LRMs — models that emphasize explicit reasoning steps) revealed common failure patterns such as verbosity and repetition, offering empirical investigation into the spatial computational limitations of these systems.

The work presents the first rigorous framework for assessing computational capacity of LLMs and LRMs by focusing on PSPACE-complete problems, which require massive search space exploration and serve as a more demanding standard than problems in the NP complexity class.