DuET: Dual Execution for Test Output Prediction with Generated Code and Pseudocode

1. 研究背景与问题定义 (Problem)

核心任务：测试输出预测 (Test Output Prediction)
在代码生成任务中，测试用例（Test Cases）对于评估和筛选模型生成的代码至关重要。测试用例生成包含两个阶段：输入生成（Input Generation）和输出预测（Output Prediction）。

• 定义：给定问题描述（Problem Description）和测试输入（Test Input），预测程序的正确输出。
• 挑战：这是一个需要精确程序推理（Program Reasoning）的困难任务。尽管大语言模型（LLM）取得了进展，但直接进行推理往往不够可靠。

现有方法的局限性

• 直接代码执行 (Direct Code Execution, e.g., TestChain)：
  • 方法：先生成可执行代码，然后直接运行代码获取输出。
  • 缺陷：对实现错误 (Implementation Errors) 极其敏感。即使模型掌握了正确的逻辑（伪代码层面正确），微小的语法错误、边界条件遗漏或索引错误（Off-by-one）也会导致代码执行失败或产生错误输出。
• 纯 LLM 推理：
  • 缺陷：容易受到执行幻觉 (Execution Hallucination) 的影响。LLM 在模拟复杂逻辑（如深层嵌套循环）时，可能会产生看似合理但实际错误的中间推理步骤，导致最终预测偏差。

核心痛点：如何在代码生成的筛选阶段，获得既准确又鲁棒的测试输出预测，以有效过滤候选代码？

---

2. 方法论：DUET 框架 (Methodology)

作者提出了 DUET (Dual Execution) 框架，旨在结合“直接代码执行”和"LLM 基于伪代码的执行”两者的优势，通过功能多数投票 (Functional Majority Voting) 机制进行融合。

2.1 核心组件

1. 基于 LLM 的伪代码执行 (LLM-based Pseudocode Execution)

   • 原理：不生成可执行代码，而是生成高层抽象的伪代码 (Pseudocode)，然后利用 LLM 的推理能力模拟伪代码的执行过程。
   • 优势：规避了低层实现细节（如语法错误、变量命名错误），专注于算法意图（Algorithmic Intent）。对于存在实现错误的场景，该方法更鲁棒。
   • 劣势：在推理链过长或逻辑极其复杂时，LLM 容易产生幻觉。

2. 直接代码执行 (Direct Code Execution)

   • 原理：生成可执行代码并直接运行。
   • 优势：具有确定性（Deterministic），只要代码正确，结果必然准确。对于逻辑简单但推理步骤多的任务，比 LLM 模拟更可靠。
   • 劣势：一旦代码生成有误（即使逻辑正确），执行即失败。

2.2 双执行融合策略 (Dual Execution Strategy)

DUET 并行执行上述两条路径：

• 路径 A：生成伪代码 $\rightarrow$ LLM 模拟执行 $\rightarrow$ 输出预测。
• 路径 B：生成伪代码 $\rightarrow$ 翻译为代码 $\rightarrow$ 直接执行 $\rightarrow$ 输出预测。

路径加权功能多数投票 (Path-Weighted Functional Majority Voting)
为了整合两条路径的结果，DUET 采用了一种改进的多数投票机制：

• 基础投票：统计所有路径产生的输出结果，出现频率最高的结果作为候选。
• 路径置信度加权：如果某条路径（如直接执行路径）内部的所有样本都达成一致（Unanimous Agreement），则赋予该路径更高的投票权重 ($w_{high}$)，否则使用基础权重 ($w_{base}$)。
• 互补性：
  • 当代码存在实现错误时，伪代码路径通常能提供正确逻辑。
  • 当推理链过长导致 LLM 幻觉时，直接代码执行路径能提供准确结果。
  • 两者结合覆盖了单一方法的失败模式。

---

3. 关键贡献 (Key Contributions)

1. 首创基于 LLM 的伪代码执行用于测试输出预测：
   • 提出将伪代码作为中间表示，利用 LLM 推理模拟执行，成功将“逻辑正确性”与“实现错误”解耦。
2. 提出 DUET 双路径框架：
   • 设计了一个新颖的框架，通过功能多数投票结合直接执行和伪代码执行，利用两者的互补优势克服各自的局限性。
3. 揭示并解决“零优势问题” (Zero-Advantage Problem)：
   • 在端到端代码生成中，发现仅依赖直接代码执行（如 TestChain）进行候选筛选时，如果生成的代码本身有缺陷，预测的输出也是错的，导致筛选信号失效（即“零优势”）。DUET 通过引入解耦的伪代码路径，解决了这一问题。
4. SOTA 性能表现：
   • 在多个基准测试中取得了最先进的性能。

---

4. 实验结果 (Results)

实验主要在 LiveCodeBench、BigCodeBench-Hard、DevEval 和 HumanEval(+) 等基准上进行。

4.1 测试输出预测 (Test Output Prediction)

• LiveCodeBench (Main Leaderboard)：
  • DUET 在 Pass@1 指标上达到了 81.1%。
  • 相比之前的 SOTA (GPT-4-Turbo + FMV) 提升了 6.9 个百分点。
  • 相比仅使用直接代码执行的 TestChain 提升了 5.6 个百分点。
• 不同模型表现：在 Llama-3.1-8B/70B、Mistral-Large 等不同大小的模型上，DUET 均显著优于基线方法，证明了其通用性。

4.2 端到端代码生成 (End-to-End Code Generation)

• 筛选效果：将 DUET 应用于代码生成后的候选筛选阶段（Filtering Candidates）。
  • 在 LiveCodeBench-Easy 上，DUET 将 Llama-3.1-8B 的 Pass@1 提升了 3.2 个百分点。
  • 对比 TestChain：使用 TestChain 进行筛选反而导致性能下降（-5.6 pp），验证了“零优势问题”的存在；而 DUET 有效避免了此问题。
• 其他基准：在 BigCodeBench-Hard、DevEval 和 HumanEval(+) 上，DUET 均取得了最佳或次优的 Pass@1 成绩。

4.3 深入分析 (Analysis)

• 代码正确性敏感度：当生成的代码正确时，直接执行表现最好；当代码错误时，伪代码执行表现更好。DUET 能自适应地利用两者。
• 执行轨迹长度 (Trace Length)：
  • 短轨迹（<100 步）：伪代码执行往往更优。
  • 长轨迹：直接执行更可靠，因为 LLM 的多步推理容易出错。
  • DUET 通过结合两者，在不同长度下均保持高性能。
• 领域适应性：在涉及复杂工具调用（如 BigCodeBench-Hard）和仓库级代码生成（DevEval）中，DUET 依然保持领先。

---

5. 意义与总结 (Significance)

• 理论意义：
  • 重新定义了测试输出预测的范式，证明了**中间表示（伪代码）**在提升 LLM 推理鲁棒性方面的关键作用。
  • 揭示了代码生成筛选中“零优势问题”的机制，为未来的代码生成优化提供了新的视角。
• 实践价值：
  • 无需训练：DUET 是一个即插即用的推理框架，不需要对基础模型进行微调，即可显著提升现有 LLM 的代码生成和评估能力。
  • 高可靠性：通过双路径互补，大幅降低了因代码实现错误或推理幻觉导致的误判，使得自动化代码评估和筛选更加可信。
  • 成本效益：虽然增加了计算开销（需运行两次路径），但通过并行处理和投票机制，其带来的性能提升远超成本，特别是在高价值代码生成场景中。

总结：DUET 通过巧妙地结合“代码执行的确定性”与“伪代码推理的抽象性”，解决了当前 LLM 在测试输出预测中的核心痛点，为构建更可靠的自动化代码生成与评估系统提供了新的 SOTA 方案。