Test-time Verification via Optimal Transport: Coverage, ROC, & Sub-optimality

📄 arXiv: 2510.18982v1 📥 PDF

作者: Arpan Mukherjee, Marcello Bullo, Debabrota Basu, Deniz Gündüz

分类: cs.AI

发布日期: 2025-10-21

💡 一句话要点

基于最优传输的测试时验证：揭示覆盖率、ROC与次优性之间的关系

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

关键词: 测试时验证 大型语言模型 最优传输 覆盖率 收敛域

📋 核心要点

  1. 现有测试时验证方法对验证器的作用和缺陷考虑不足，缺乏对生成器覆盖率、验证器ROC和采样算法次优性之间关系的统一量化。
  2. 论文将测试时验证建模为最优传输问题，以此来刻画覆盖率、ROC和次优性之间的相互作用，并分析了次优性-覆盖率曲线的不同状态。
  3. 实验结果表明，次优性-覆盖率曲线存在传输、策略改进和饱和三种状态，并验证了顺序采样和批量采样算法的计算复杂度对性能的影响。

📝 摘要（中文）

本文研究了大型语言模型（LLMs）测试时验证缩放中验证器的作用及其不完善性。验证的效果体现在三个量的相互作用中：(i)生成器的覆盖率，(ii)验证器的收敛域（ROC），以及(iii)采样算法的次优性。虽然最近的研究捕捉到了这些因素的子集，但缺乏一个统一的框架来量化它们相互作用的几何形状。本文将可验证的测试时缩放构建为一个传输问题，刻画了覆盖率、ROC和次优性之间的相互作用，并揭示了次优性-覆盖率曲线呈现三种状态：传输状态（次优性随覆盖率增加），策略改进状态（次优性可能随覆盖率降低，取决于验证器的ROC），以及饱和状态（次优性趋于稳定，不受覆盖率影响）。此外，本文提出并分析了两类采样算法——顺序采样和批量采样，并研究了它们的计算复杂度如何影响这些权衡。使用Qwen、Llama和Gemma模型的实验结果证实了理论发现。

🔬 方法详解

问题定义：现有的大型语言模型测试时验证方法，虽然通过验证机制提升了性能，但对验证器本身的作用及其局限性缺乏深入研究。具体来说，现有方法没有充分考虑生成器的覆盖率、验证器的收敛域（ROC）以及采样算法的次优性三者之间的复杂关系，导致无法有效指导验证器的设计和采样算法的选择。

核心思路：论文的核心思路是将可验证的测试时缩放问题建模为一个最优传输问题。通过这种建模方式，可以将生成器的覆盖率、验证器的ROC以及采样算法的次优性纳入一个统一的框架中进行分析，从而揭示它们之间的相互作用关系，并指导验证器的设计和采样算法的选择。最优传输理论提供了一种量化不同概率分布之间距离的有效方法，可以用来衡量生成器输出与理想输出之间的差异。

技术框架：该研究的技术框架主要包括以下几个部分：1) 将测试时验证过程形式化为一个最优传输问题；2) 分析覆盖率、ROC和次优性之间的关系，并推导出次优性-覆盖率曲线；3) 提出并分析顺序采样和批量采样两种采样算法；4) 通过实验验证理论分析结果。整体流程是从理论建模到算法设计，再到实验验证，形成一个完整的闭环。

关键创新：论文的关键创新在于将测试时验证问题建模为最优传输问题，并以此为基础分析了覆盖率、ROC和次优性之间的关系。这种建模方式提供了一个统一的框架，可以用来理解和优化测试时验证过程。此外，论文还提出了次优性-覆盖率曲线的概念，并揭示了其三种不同的状态，为验证器的设计和采样算法的选择提供了理论指导。

关键设计：论文的关键设计包括：1) 使用最优传输距离来衡量生成器输出与理想输出之间的差异；2) 定义了覆盖率、ROC和次优性等关键指标，并分析了它们之间的关系；3) 提出了顺序采样和批量采样两种采样算法，并分析了它们的计算复杂度；4) 通过实验验证了理论分析结果，并对不同模型的性能进行了比较。

🖼️ 关键图片

img_0

📊 实验亮点

实验结果表明，次优性-覆盖率曲线存在三种状态：传输状态、策略改进状态和饱和状态，验证了理论分析的正确性。此外，实验还比较了Qwen、Llama和Gemma等不同模型的性能，并分析了顺序采样和批量采样算法的优缺点。这些实验结果为实际应用中验证器的设计和采样算法的选择提供了重要参考。

🎯 应用场景

该研究成果可应用于提升大型语言模型在各种实际场景中的可靠性和性能，例如智能客服、机器翻译、文本生成等。通过优化验证器的设计和采样算法的选择，可以提高模型输出的质量和一致性，减少错误和偏差，从而增强用户体验和信任度。此外，该研究还可以为开发更高效、更可靠的AI系统提供理论指导。

📄 摘要（原文）

While test-time scaling with verification has shown promise in improving the performance of large language models (LLMs), the role of the verifier and its imperfections remain underexplored. The effect of verification manifests through interactions of three quantities: (i) the generator's coverage, (ii) the verifier's region of convergence (ROC), and (iii) the sampling algorithm's sub-optimality. Though recent studies capture subsets of these factors, a unified framework quantifying the geometry of their interplay is missing. We frame verifiable test-time scaling as a transport problem. This characterizes the interaction of coverage, ROC, and sub-optimality, and uncovers that the sub-optimality--coverage curve exhibits three regimes. A transport regime -- where sub-optimality increases with coverage, a policy improvement regime -- where sub-optimality may decrease with coverage, depending on the verifier's ROC, and a saturation regime -- where sub-optimality plateaus, unaffected by coverage. We further propose and analyze two classes of sampling algorithms -- sequential and batched, and examine how their computational complexities shape these trade-offs. Empirical results with Qwen, Llama, and Gemma models corroborate our theoretical findings.