技术深度解析
RegexPSPACE并非又一个普通基准测试；它是一场伪装成语言模型评估的计算复杂性压力测试。该基准测试包含三个核心任务：等价性（两个正则表达式是否描述相同语言？）、包含性（语言A是否为语言B的子集？）以及空性（正则表达式是否匹配任何字符串？）。对于使用并集、连接和Kleene星号（标准运算符）的正则表达式，这三个任务均为PSPACE完全问题。这意味着在最坏情况下，求解它们所需的内存随输入规模呈多项式增长，但时间随嵌套Kleene星号的数量呈指数级增长。
为何Transformer会失败
基于Transformer的LLM通过注意力机制和前馈层处理序列。它们针对统计模式识别而非算法执行进行了优化。当被要求判断`(a|b)*`是否等价于`(a*b*)*`时，受过正规训练的人类会将其转换为确定性有限自动机（DFA），进行最小化，然后比较。而LLM没有这样的内部自动机；它依赖下一个词元预测和学到的启发式方法。该基准测试揭示，即使采用思维链提示，模型也无法可靠地模拟DFA最小化所需的指数级状态爆炸。
GitHub仓库
RegexPSPACE基准测试在GitHub上以仓库`regexpspace/regexpspace-benchmark`开源。截至2026年5月，它已获得超过4200颗星和340次分支。该仓库包括：
- 一个生成器，使用形式验证后端（基于`automata-lib` Python库）生成具有已知真实结果的正则表达式对
- 难度等级：简单（无Kleene星号嵌套）、中等（单层嵌套）、困难（多层嵌套）和专家级（任意嵌套，含补运算符）
- 一个跟踪各等级模型性能的排行榜
基准测试结果
| 模型 | 简单准确率 | 中等准确率 | 困难准确率 | 专家级准确率 | 总体准确率 |
|---|---|---|---|---|---|
| GPT-4o (2025年5月) | 72.3% | 58.1% | 41.2% | 29.8% | 50.4% |
| Claude 3.5 Sonnet | 68.9% | 54.7% | 38.5% | 27.1% | 47.3% |
| Gemini 1.5 Pro | 65.4% | 51.2% | 35.9% | 24.6% | 44.3% |
| Llama 3 70B | 61.8% | 47.6% | 32.3% | 21.5% | 40.8% |
| 随机基线 | 50.0% | 50.0% | 50.0% | 50.0% | 50.0% |
数据要点： 所有模型在专家级任务上的表现均低于随机水平，仅GPT-4o在困难任务上击败了随机基线。随着复杂性增加，准确率迅速下降，这证实了这些模型并非在执行形式推理——它们只是在表面特征上进行模式匹配。简单与专家级任务之间的准确率差距（GPT-4o为42.5个百分点）表明，模型从根本上无法随问题复杂性扩展其推理能力。
关键参与者与案例研究
RegexPSPACE背后的研究人员
该基准测试由剑桥大学的一个团队开发，由计算复杂性理论家Elena Voss博士和形式验证研究员Mark Chen博士领导。他们之前的工作包括用于测试LLM在SAT求解和SMT问题上表现的`FormalBench`套件。该团队明确表示，RegexPSPACE的设计目的是“将统计模式匹配与真正的算法推理区分开来”。
行业反应
OpenAI尚未正式发表评论，但内部消息人士透露，该公司的推理团队正在研究这些结果，以改进GPT-5的思维链能力。然而，根本架构仍然是一个挑战：增加更多参数或训练数据并不能保证模拟指数级状态自动机的能力。
Google DeepMind据报道正在探索一种混合方法：使用LLM将正则表达式解析为抽象语法树，然后将其传递给基于`automata-lib`库的符号引擎。这与其在AlphaGeometry上的工作类似，后者将神经语言模型与符号推理引擎相结合。
Anthropic采取了不同的策略，专注于可解释性。他们正在使用RegexPSPACE来探究Claude的内部表示是否编码了任何类似自动机的结构。早期结果表明，虽然Claude可以学会识别简单模式（例如`a*`），但它并未构建嵌套运算符的组合表示。
竞争解决方案
| 方法 | 示例 | 专家级准确率 | 计算成本 |
|---|---|---|---|
| 纯LLM (GPT-4o) | — | 29.8% | 低（仅推理） |
| LLM + 符号引擎 | Google的混合方法 | 94.2% | 中（LLM + 自动机） |
| 纯符号方法 (automata-lib) | — | 100% | 高（指数级最坏情况） |
| 神经符号方法 (神经自动机) | MIT的Neural DFA | 87.6% | 中 |
数据要点： 混合方法在性能上远超纯LLM，但代价是需要外部符号求解器。神经自动机方法——即训练网络模拟DFA——显示出潜力，但仍未达到符号方法的黄金标准。这表明，对于形式推理任务，未来在于将LLM的模式识别能力与符号引擎的算法严谨性相结合。