TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability

📄 arXiv: 2608.09538v1 📥 PDF

作者: Vincent Cohen-Addad, Dimitris Paparas, Ernest van Wijland, Max Springer, Julien Canitrot-Paradis, Honghao Lin, David Woodruff, Adarsh Kumarappan, Rajesh Jayaram, Rudrajit Das, Lalit Jain, Ola Svensson, Silvio Lattanzi, Mislav Balunovic, Theophane Weber, Vahab Mirrokni

分类: cs.CL, cs.AI

发布日期: 2026-08-10

💡 一句话要点

提出TCS-Bench以评估生成AI在理论计算机科学研究中的能力

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 生成AI 理论计算机科学 证明生成 基准评估 大型语言模型 自动化定理证明 验证机制

📋 核心要点

  1. 现有的生成AI在理论计算机科学领域的证明生成能力有限，缺乏系统的评估基准。
  2. 论文提出了TCS-Bench基准，专注于从顶级会议中提取定理证明任务，以评估LLMs的证明生成能力。
  3. 实验结果显示，最先进的模型在TCS-Bench上表现良好，验证者的准确率超过90%，表明该基准的有效性。

📝 摘要（中文）

我们介绍了TCS-Bench，这是一个用于评估大型语言模型（LLMs）在研究级理论计算机科学（TCS）证明生成能力的基准。TCS-Bench包含来自顶级理论计算机科学会议（STOC、FOCS和SODA）发表的论文中的定理证明任务。每个任务提供必要的上下文，以推导出目标结果的自包含证明。我们在该基准上评估了最先进的模型，并通过验证代理验证生成证明的正确性，进一步将验证者与人类专家的证明判断进行基准测试。我们的参考验证者在专家标记集上达到了超过90%的准确率。

🔬 方法详解

问题定义：论文旨在解决现有生成AI在理论计算机科学领域证明生成能力不足的问题。现有方法缺乏系统的评估标准，导致难以比较不同模型的性能。

核心思路：论文的核心思路是构建TCS-Bench基准，通过提供来自顶级会议的定理证明任务，来系统性地评估大型语言模型的证明生成能力。这种设计使得模型在特定的学术背景下进行评估，确保生成的证明具有学术价值。

技术框架：整体架构包括任务选择、模型评估和证明验证三个主要模块。首先，从STOC、FOCS和SODA等会议中提取定理证明任务；其次，使用最先进的LLMs生成证明；最后，通过验证代理对生成的证明进行正确性验证，并与人类专家的判断进行比较。

关键创新：最重要的技术创新点在于构建了一个专门针对理论计算机科学的证明生成基准TCS-Bench，填补了现有评估工具的空白。与现有方法相比，TCS-Bench提供了更具针对性的任务和验证机制。

关键设计：在设计中，论文设置了明确的任务上下文，以确保生成的证明是自包含的。同时，验证代理的设计也经过优化，以提高其在专家标记集上的准确性，达到90%以上。该设计确保了生成证明的质量和可靠性。

🖼️ 关键图片

img_0
img_1
img_2

📊 实验亮点

实验结果表明，最先进的模型在TCS-Bench基准上表现优异，验证者在专家标记集上的准确率超过90%。这一结果不仅验证了TCS-Bench的有效性，也为未来的研究提供了可靠的评估标准。

🎯 应用场景

该研究的潜在应用领域包括教育、自动化定理证明、以及生成AI在科学研究中的应用。通过提供一个标准化的评估工具，TCS-Bench可以帮助研究人员更好地理解和改进生成AI在理论计算机科学中的应用，推动相关领域的进步。

📄 摘要（原文）

We introduce TCS-Bench, a benchmark for evaluating Large Language Models (LLMs) on research-level Theoretical Computer Science (TCS) proof generation. TCS-Bench consists of theorem-proving tasks from papers published at top theoretical computer science venues (STOC, FOCS, and SODA). Each task provides the necessary context to derive a self-contained proof for a target result. We evaluate state-of-the-art models on this benchmark. We verify the correctness of generated proofs via a verification agent, and further benchmark the verifier against human-expert proof judgements on a set of target statements and generated proofs pairs. Our reference verifier achieves over 90% accuracy on the expert labeled set.