RegexPSPACE

RegexPSPACE数据集是针对PSPACE完全正则表达式（regex）问题构建的，用于评估大型语言模型（LLM）和大型推理模型（LRM）的空间计算能力。数据集包括超过一百万个正则表达式实例，涵盖了正则表达式等价性判定（RegexEQ）和最小化（RegexMin）两个PSPACE完全问题。该数据集通过双指数空间探索构建，并经过严格的过滤过程，旨在揭示LLM和LRM在空间复杂性约束下的计算局限性，并为评估它们的先进推理能力提供一个新框架。

The RegexPSPACE dataset is constructed for PSPACE-complete regular expression (regex) problems, aiming to evaluate the spatial computational capabilities of Large Language Models (LLMs) and Large Reasoning Models (LRMs). The dataset contains over one million regular expression instances, covering two PSPACE-complete problems: regular expression equivalence checking (RegexEQ) and minimization (RegexMin). This dataset is built via double-exponential space exploration and has undergone a rigorous filtering process, designed to reveal the computational limitations of LLMs and LRMs under spatial complexity constraints and provide a novel framework for evaluating their advanced reasoning capabilities.

搜集汇总

数据集介绍

构建方式

在正则表达式理论研究中，RegexPSPACE数据集的构建采用了双重指数空间探索方法，通过深度优先枚举策略生成超过百万个正则表达式实例。研究团队基于固定字母表{a,b,c,d}，采用自底向上的树形结构生成算法，将表达式深度限制在3层以内以控制组合爆炸。通过等价类划分技术，利用确定性有限自动机验证工具对生成的表达式进行精确分组，并采用基于字符串接受的启发式过滤机制降低计算复杂度，最终构建出包含严格标注的等价类与最小化表达式的基准数据集。

使用方法

使用该数据集时需遵循形式化正则表达式规范，禁止使用捕获组等非正则操作符。评估时采用三重指标：最小化率衡量输出与理论最短表达式的匹配度，等价率检验输出与输入的语言一致性，长度比通过几何平均计算表达式压缩效率。对于等价判定任务，除准确率外还需结合F1分数以平衡类别分布。基准测试支持零样本与少样本提示策略，要求模型在限定上下文窗口内完成双重验证——既需保证推导过程的逻辑严谨性，又需满足多项式空间约束下的计算可行性。

背景与挑战

背景概述

RegexPSPACE数据集由延世大学计算机科学系Jin Hyundong、Hahn Joonghyuk和Han Yo-Sub团队于2025年构建，旨在评估大语言模型在PSPACE完全正则表达式问题上的推理能力。该数据集聚焦于形式语言理论中的正则表达式等价性判定与最小化问题，通过构造包含百万级标注实例的基准，首次系统性地探索了语言模型在空间复杂度约束下的计算边界。其创新性在于将评估范围从传统的NP类问题扩展至更具挑战性的PSPACE完全类，为理解语言模型的理论计算能力提供了重要实证基础。

当前挑战

该数据集面临双重挑战：在领域问题层面，正则表达式等价性判定与最小化作为PSPACE完全问题，要求模型具备大规模搜索空间探索能力，而现有语言模型受限于有限上下文窗口，在空间复杂度约束下难以有效处理此类问题；在构建过程中，由于PSPACE完全问题的难解性，标注数据集面临双重指数级搜索空间带来的计算瓶颈，需通过深度限制和字母表约束来平衡标注质量与可行性，同时需设计定量评估指标以精确衡量模型输出的等价性与最小化程度。

常用场景

经典使用场景

在形式语言理论与计算复杂性研究领域，RegexPSPACE数据集通过构建超过百万个正则表达式实例，为评估大语言模型在PSPACE完全问题上的推理能力提供了标准化测试平台。该数据集聚焦于正则表达式等价性判定与最小化这两个经典计算难题，通过双指数级空间搜索构建的标注数据能够系统性地检验模型在多项式空间约束下的逻辑推理极限。其精心设计的过滤机制确保了测试实例的复杂度梯度，使研究者能够量化分析模型在应对组合爆炸问题时的表现衰退规律。

解决学术问题

RegexPSPACE首次实证揭示了大型语言模型在空间计算约束下的理论能力与实践表现间的显著差距。该数据集通过PSPACE完全问题的结构化评估，解决了现有基准局限于NP类问题的缺陷，为计算语言学领域提供了衡量模型组合推理能力的新范式。其构建方法突破了传统标注过程中面临的计算不可行性障碍，通过深度受限的表达式枚举与等价类划分技术，实现了对模型空间探索能力的量化分析，推动了对于注意力机制计算边界的理论认知。

实际应用

在软件工程与网络安全领域，RegexPSPACE数据集支撑的正则表达式优化技术可直接应用于代码压缩与拒绝服务攻击防御。通过评估模型对复杂正则模式的简化能力，可指导开发更高效的文本处理引擎与漏洞检测系统。数据集构建过程中揭示的模型泛化特性，为工业级正则表达式库的智能优化提供了技术路径，特别是在日志分析、入侵检测等需要处理复杂模式匹配的实际场景中，该基准可作为评估推理模型实用性的重要指标。

数据集最近研究

最新研究方向

在形式语言理论与计算复杂性交叉领域，RegexPSPACE数据集标志着评估大型语言模型空间推理能力的重要突破。该数据集聚焦于PSPACE完全正则表达式问题，通过构建包含等价性判定和最小化任务的百万级标注实例，首次系统性地揭示了LLMs在多项式空间复杂度问题上的计算边界。当前前沿研究主要围绕模型在受限上下文窗口下的空间探索能力展开，通过双指数级搜索空间构建的基准测试表明，即使具备推理模块的大型模型在应对正则表达式最小化任务时仍普遍存在输出冗余、模式重复等系统性缺陷。这一研究方向与神经网络可解释性、计算语言学理论形成深度交叉，为理解Transformer架构在复杂搜索问题中的内在机制提供了新型实验范式，同时推动了基于形式语言理论的模型能力评估体系发展。

相关研究论文

• 通过

  韩国首尔延世大学计算机科学系 · 2025年