# RegexPSPACE: A Benchmark for Evaluating LLM Reasoning on PSPACE-complete Regex Problems

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 14 of its 45 references that are in the map.
- First posted on arXiv 10 Oct 2025.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

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

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [gpt-oss-120b & gpt-oss-20b Model Card](https://mlsanity.com/paper/2508.10925/) (2025)
- [Qwen2.5-Coder Technical Report](https://mlsanity.com/paper/2409.12186/) (2024)
- [Phi-4 Technical Report](https://mlsanity.com/paper/2412.08905/) (2024)
- [Qwen2.5-1M Technical Report](https://mlsanity.com/paper/2501.15383/) (2025)
- [Phi-4-reasoning Technical Report](https://mlsanity.com/paper/2504.21318/) (2025)
- [SATBench: Benchmarking LLMs' Logical Reasoning via Automated Puzzle Generation from SAT Formulas](https://mlsanity.com/paper/2505.14615/) (2025)
- [EXAONE 4.0: Unified Large Language Models Integrating Non-reasoning and Reasoning Modes](https://mlsanity.com/paper/2507.11407/) (2025)
- [Quantifying Generalization Complexity for Large Language Models](https://mlsanity.com/paper/2410.01769/) (2024)
- [NPHardEval4V: Dynamic Evaluation of Large Vision-Language Models with Effects of Vision](https://mlsanity.com/paper/2403.01777/) (2024)

## Built on by (most cited first, 1 of 1)

- [NCO: A Versatile Plug-in for Handling Negative Constraints in Decoding](https://mlsanity.com/paper/2605.10065/) (2026)

## Abstract (arXiv)

Large language models (LLMs) show strong performance across natural language processing (NLP), mathematical reasoning, and programming, and recent large reasoning models (LRMs) further emphasize explicit reasoning. Yet their computational limits, particularly spatial complexity constrained by finite context windows, remain poorly understood. While recent works often focus on problems within the NP complexity class, we push the boundary by introducing a novel benchmark grounded in two PSPACE-complete regular expression (regex) problems: equivalence decision (RegexEQ) and minimization (RegexMin). PSPACE-complete problems serve as a more rigorous standard for assessing computational capacity, as their solutions require massive search space exploration. We perform a double-exponential space exploration to construct a labeled dataset of over a million regex instances with a sound filtering process to build the benchmark. We conduct extensive evaluations on 6 LLMs and 5 LRMs of varying scales, revealing common failure patterns such as verbosity and repetition. With its well-defined structure and quantitative evaluation metrics, this work presents the first empirical investigation into the spatial computational limitations of LLMs and LRMs, offering a new framework for evaluating their advanced reasoning capabilities. Our code is available at https://github.com/hyundong98/RegexPSPACE .