RegexPSPACE

RegexPSPACE是第一个用于评估大型语言模型在PSPACE完全正则表达式问题上推理能力的基准。该基准基于两个PSPACE完全正则表达式问题：等价性决策和最小化，通过双指数空间探索和严格过滤过程，从超过一百万个初始实例中筛选出1,685个正则表达式问题。

RegexPSPACE is the first benchmark designed to evaluate the reasoning abilities of large language models on PSPACE-complete regular expression problems. It is based on two core PSPACE-complete tasks for regular expressions: equivalence decision and minimization, and 1,685 regular expression problem instances were filtered from over one million initial samples through doubly exponential space exploration and a strict filtering process.

原始信息汇总

RegexPSPACE 数据集概述

数据集基本信息

• 数据集名称: RegexPSPACE
• 核心目标: 评估大语言模型在PSPACE完全正则表达式问题上的推理能力
• 问题类型: PSPACE完全正则表达式问题
• 包含任务: 等价性决策(RegexEQ)和最小化(RegexMin)
• 数据规模: 1,685个正则表达式问题

数据集特点

• 首创性: 首个针对PSPACE完全正则表达式问题的基准测试
• 构建方法: 通过双指数空间探索和严格过滤流程，从超过百万初始实例中筛选
• 评估价值: 首次对大语言模型和大推理模型的空间计算限制进行实证研究

评估指标

• 最小化程度(Minimality)
• 等价性(Equivalence)
• 长度比率(Length Ratio)

数据集文件

• 主数据集: data/RegexPSPACE.jsonl
• 少样本示例: data/RegexPSPACE_fewshot.jsonl

相关资源

• 论文链接: https://arxiv.org/abs/2510.09227
• Hugging Face地址: https://huggingface.co/datasets/HDJin/RegexPSPACE

主要发现

• 任务难度差异: 模型在最小化任务上的表现明显差于等价性任务
• 模型规模依赖: 14-15B参数及以上模型普遍优于7-8B参数模型
• 常见失败模式: 重复标记序列生成、答案未在指定标记限制内完成

搜集汇总

数据集介绍

构建方式

在形式语言与自动机理论领域，RegexPSPACE基准的构建采用了双重指数空间探索方法。研究者从超过百万初始实例中，通过严谨的声学过滤流程，最终筛选出1,685个具有计算复杂性的正则表达式问题。该构建过程聚焦于PSPACE完全问题的两个核心维度：等价性判定与最小化问题，为评估大语言模型的空间推理能力奠定了理论基础。

特点

作为首个针对PSPACE完全正则表达式问题的评测基准，RegexPSPACE具备独特的理论价值。其创新性体现在多维量化评估体系，不仅涵盖基础准确率，更引入最小化度、等价性判定与长度比率等精细指标。该基准能系统揭示大语言模型在复杂推理任务中的典型失效模式，包括冗余生成、重复输出与提前终止等现象，为模型能力边界研究提供重要视角。

使用方法

基于Python生态的评估框架，研究者可通过四步流程开展实验：克隆代码库后配置虚拟环境，使用inference.py脚本执行零样本或五样本推理任务，最终通过evaluate.py脚本获取量化评估结果。该框架支持对等价性判定与最小化任务的双重测试，并可通过调整模型参数与样本数量实现不同场景下的性能验证。

背景与挑战

背景概述

在计算复杂性理论中，PSPACE完全问题代表了空间复杂度领域的核心挑战，其求解过程需要指数级内存资源。RegexPSPACE基准数据集由Hyundong Jin等研究人员于2025年10月创建，作为首个针对PSPACE完全正则表达式问题的评估框架。该数据集聚焦于正则表达式等价性判定（RegexEQ）与最小化（RegexMin）两大核心问题，通过双重指数空间探索与严谨过滤流程，从百万级初始实例中精炼出1,685个具有代表性的难题。这项开创性工作为揭示大语言模型在空间计算维度上的本质局限提供了实证基础，推动了复杂推理能力评估方法论的发展。

当前挑战

该数据集致力于攻克PSPACE完全问题领域的核心挑战，即验证大语言模型在处理需要指数级空间复杂度的正则表达式问题时的推理能力边界。在构建过程中，研究团队面临双重指数空间搜索带来的组合爆炸难题，需设计高效过滤机制从海量候选问题中筛选具有区分度的实例。同时需确保生成问题的计算复杂性严格符合PSPACE完全标准，并建立涵盖最小化程度、等价性判定与长度比率的多维度评估体系，以精确捕捉模型在复杂模式匹配任务中的典型失效模式，包括冗余生成、循环重复与提前终止等现象。

常用场景

经典使用场景

在形式语言与自动机理论领域，RegexPSPACE作为首个针对PSPACE完全正则表达式问题的基准测试集，主要用于评估大语言模型在复杂空间计算任务中的推理能力。该数据集通过正则表达式等价性判定和最小化两大核心任务，系统检验模型处理指数级空间复杂度问题的表现，为衡量模型高级推理机制提供了标准化实验环境。

解决学术问题

该数据集有效解决了当前大语言模型在计算复杂性理论评估中的空白，通过构建双重指数空间筛选的1685个挑战性问题，揭示了模型在空间复杂度推理中的固有局限。其设计的等价性、最小化与长度比等多维度量化指标，为分析模型在PSPACE完全问题上的失败模式提供了理论框架，推动了语言模型计算边界研究的发展。

衍生相关工作

基于该数据集的研究已催生多项重要工作，包括对14B参数量级以上模型空间推理能力的系统性比较分析，以及针对重复生成、提前终止等典型失败模式的归因研究。这些成果不仅深化了对大语言模型计算局限性的认知，更为构建下一代面向复杂问题求解的推理模型奠定了方法论基础。