2025-11-30T18:52:18.815530

SELF-REDRAFT: Eliciting Intrinsic Exploration-Exploitation Balance in Test-Time Scaling for Code Generation

Chen, Zheng, Huang et al.

Test-time scaling without interpreter feedback is essential for real-world code generation scenarios where test cases are not readily available. While existing paradigms often rely on either greedy exploitation (i.e., iterative refinement) or stochastic exploration (i.e., relying on sample-based voting or reranking mechanisms), the balance between these two dimensions remains underexplored. To investigate the LLM's intrinsic ability to balance exploitation and exploration, we introduce SELF-REDRAFT, a framework built upon Self-Refine that encourages the model to propose new drafts for solutions that are fundamentally flawed. Our results show that SELF-REDRAFT consistently achieves better performance than Self-Refine when converged under the same maximum number of iterations. Still, we observe that significant room for improvement remains, largely due to two core aspects of current self-redraft capabilities: constrained capacity for generating instructive feedback and fragile discriminative judgment. We also find that balancing strategies vary notably across different LLMs, reflecting distinct, model-specific behaviors. Overall, our study establishes a baseline for intrinsic exploration-exploitation balancing in test-time scaling and identifies feedback and discrimination as key areas with potential for future advances.

academic

SELF-REDRAFT: Eliciting Intrinsic Exploration-Exploitation Balance in Test-Time Scaling for Code Generation

基本信息

论文ID: 2511.02854
标题: SELF-REDRAFT: Eliciting Intrinsic Exploration-Exploitation Balance in Test-Time Scaling for Code Generation
作者: Yixiang Chen*, Tianshi Zheng*, Shijue Huang, Zhitao He, Yi R. (May) Fung (*Equal Contribution)
单位: Department of Computer Science and Engineering, HKUST
分类: cs.SE (Software Engineering), cs.AI (Artificial Intelligence)
提交时间: 2025年10月31日
论文链接: https://arxiv.org/abs/2511.02854v1

摘要

本文研究了在无解释器反馈的测试时扩展场景下，大语言模型（LLM）在代码生成任务中平衡探索（exploration）与利用（exploitation）的内在能力。现有方法要么依赖贪婪利用（迭代优化），要么依赖随机探索（基于采样的投票或重排序），但两者之间的平衡尚未得到充分研究。作者提出了SELF-REDRAFT框架，在Self-Refine基础上增加了对根本性错误解决方案进行重新起草的机制。实验表明，SELF-REDRAFT在相同迭代预算下持续优于Self-Refine，但仍存在显著改进空间，主要受限于两个核心能力：生成指导性反馈的能力不足和判别能力脆弱。研究还发现不同LLM的平衡策略存在显著差异，反映出模型特定的行为特征。

研究背景与动机

1. 要解决的问题

本文关注无执行反馈的测试时扩展（execution-free test-time scaling）场景下的代码生成问题。在实际应用中，测试用例往往不可用，因此需要LLM在没有程序执行反馈的情况下自主改进代码质量。

2. 问题的重要性

实际需求：现实场景中测试用例常常缺失，执行环境可能不可用
计算效率：测试时扩展是提升LLM性能的有效手段，但需要在有限计算预算下最大化性能
理论价值：探索-利用权衡是强化学习和搜索算法的核心问题，在代码生成领域的应用尚未充分研究

3. 现有方法的局限性

执行依赖型方法：需要测试用例和执行环境，在实际场景中受限
纯利用型方法（如Self-Refine）：仅进行迭代优化，容易陷入局部最优
纯探索型方法（如pass@k）：通过多次采样获取多样性，但缺乏针对性改进
平衡缺失：现有无执行反馈方法主要依赖利用，探索维度被忽视

4. 研究动机

作者旨在研究LLM在无执行反馈条件下平衡探索与利用的内在能力（intrinsic ability），识别当前模型的瓶颈，为未来改进指明方向。

核心贡献

提出SELF-REDRAFT框架：在Self-Refine基础上引入显式的探索选择，允许模型对根本性错误的解决方案进行重新起草（redraft），实现探索与利用的平衡
建立基准评估：在LiveCodeBench上对6个开源和专有LLM进行系统评估，证明SELF-REDRAFT在16次迭代后平均提升0.615%
识别核心瓶颈：通过深入分析揭示两个关键限制因素：
- 生成指导性反馈的能力不足（Insufficient Model Critique）
- 判别正确/错误代码的能力脆弱（Fragile Code Discrimination）
揭示模型特定行为：发现不同LLM的平衡策略存在显著差异，表明这一能力尚未成为通用能力，而是模型特定的涌现特性
量化改进空间：通过与pass@8上界对比，量化了当前方法与纯探索潜力之间的差距

方法详解

任务定义

输入：编程任务描述 $x$
输出：满足任务要求的代码解决方案 $\hat{y}$
目标：在无测试用例执行反馈的条件下，通过有限次迭代（测试时计算）最大化代码的功能正确性

模型架构

SELF-REDRAFT是一个迭代框架，包含三个主要步骤：

Step 0: 初始化

给定任务 $x$ 和生成提示 $p_{gen}$ ，模型生成初始解决方案： $y_0 \sim \pi(\cdot | p_{gen}, x)$

Step 1: 反馈生成（Feedback）

模型评估当前解决方案 $y_i$ ，使用反馈提示 $p_{fb}$ 生成反馈 $c_i$ ： $c_i \sim \pi(\cdot | p_{fb}, x, y_i)$

反馈包含两部分：

批评（critique）：分析代码问题并提供具体建议
行动建议（suggestion）：明确指示下一步操作，包括三种选择：
- PASS：代码正确，停止迭代
- REFINE：小幅改进，保持原有方法
- REDRAFT：根本性错误，需要新方法

Step 2: 再生成（Regeneration）

基于反馈和历史轨迹，模型生成新解决方案： $y_{i+1} \sim \pi(\cdot | p_{regen}, x, y_i, c_i, \ldots, y_0, c_0)$

根据反馈建议：

若为REDRAFT：生成全新解决方案（探索）
若为REFINE：在原方案基础上改进（利用）

迭代直到满足停止条件（达到最大迭代次数 $T$ 或模型输出PASS）。

技术创新点

1. 显式探索机制

与Self-Refine的核心区别：Self-Refine仅支持PASS和REFINE，纯粹是利用型方法。SELF-REDRAFT引入REDRAFT选项，允许模型识别根本性错误并重新起草解决方案。

设计合理性：

代码问题分为表层错误（如语法、边界条件）和方法论错误（如算法选择错误）
表层错误适合渐进式优化（refine），方法论错误需要重新思考（redraft）
通过让模型自主判断错误类型，实现探索-利用的动态平衡

2. 结构化反馈设计

使用XML标签强制模型生成结构化输出：

<critique>
详细的批评和分析
</critique>
<suggestion>
pass/refine/redraft
</suggestion>

这种设计便于：

信息提取和算法决策
后续实验分析
保证反馈的可操作性

3. 轨迹记忆机制

再生成时包含完整历史轨迹 $(y_0, c_0, \ldots, y_i, c_i)$ ，使模型能够：

避免重复错误
学习改进模式
在探索时仍保留有效信息

实验设置

数据集

LiveCodeBench（Jain et al., 2024）：

规模：1,055个编程问题
难度分级：easy、medium、hard三个级别
特点：
- 全面且无污染的评估基准
- 来自真实编程竞赛
- 持续更新，避免训练数据泄露

评价指标

Pass@k：功能正确性指标 $\text{pass@k} = \mathbb{E}_{\text{Problem}}\left[1 - \frac{\binom{n-c}{k}}{\binom{n}{k}}\right]$ 其中 $n$ 为生成样本数， $c$ 为正确样本数。本文使用 $n=16, k=8$ 。
Improvement Rate ( $r_{imp}$ )：初始错误解决方案被修正的比例
Regression Rate ( $r_{reg}$ )：初始正确解决方案被破坏的比例
Recall on Draft：辅助评估器正确识别"redraft"建议的召回率

对比方法

Self-Refine：纯利用型基线，仅支持迭代优化
Pass@8：纯探索型上界，通过独立采样获得

实现细节

模型配置（6个LLM）：

GPT-4.1 mini, GPT-4.1 nano（OpenAI）
Kimi K2（32B激活参数，1T总参数的MoE）
Llama 4 Maverick（17B激活参数，128专家MoE）
LongCat-Flash-Chat（MoE，擅长智能体任务）
Qwen3-Next-80B-A3B-Instruct

生成参数（遵循LiveCodeBench默认设置）：

Temperature: 0.2
Top-p: 0.95
Frequency penalty: 0
Presence penalty: 0

迭代设置：

最大迭代次数：16
使用相同初始解决方案集合确保公平比较
允许早停（模型输出PASS时）

实验结果

主要结果

整体性能（图2，表格完整结果见附录E）：

SELF-REDRAFT在16次迭代后平均比Self-Refine提升0.615%
改进在所有6个测试模型上一致出现
性能在16次迭代时趋于稳定

各模型表现（图8）：

不同模型的绝对性能差异显著
迭代曲线形态各异，反映不同的平衡策略
部分模型在早期迭代即达到峰值，后续出现波动

未开发的探索潜力

与pass@8上界对比（图3）：

Pass@8显著优于SELF-REDRAFT×16（17个解决方案）
关键发现：纯探索（8个独立样本）比当前探索-利用平衡更有效
差距示例：
- GPT-4.1 mini: SELF-REDRAFT 35.1% vs Pass@8 41.8%
- Qwen3-Next: SELF-REDRAFT 48.2% vs Pass@8 55.3%

解读：大量问题只需多样化采样即可找到正确解，但SELF-REDRAFT未能有效利用这一优势，说明当前探索机制效率低下。

反馈质量分析

盲评实验设计（第3.3节）：

从轨迹中采样（原解决方案，反馈，新解决方案）三元组
辅助评估器仅看解决方案对，判断是否发生方法论变化
对比评估器判断与原始反馈建议（refine vs redraft）
平衡采样：每组包含相等数量的"draft"和"refine"标签
最多1000个样本/生成器模型

Recall on Draft结果（图5）：

平均召回率：30-55%之间
正相关发现（图4）：Recall on Draft与SELF-REDRAFT的改进幅度呈正相关（相关系数约0.6-0.7）
跨评估器一致性（图7）：不同辅助模型的排名高度一致（Spearman ρ > 0.8）

核心结论：多数模型无法为方法论修正提供可操作的反馈，限制了有效探索。

判别能力分析

改进率与回归率对比（表1）：

模型	Self-Refine $r_{imp}$	SELF-REDRAFT $r_{imp}$	Self-Refine $r_{reg}$	SELF-REDRAFT $r_{reg}$
GPT-4.1 mini	3.29%	5.18% (+1.89)	1.11%	1.27% (+0.16)
GPT-4.1 nano	19.52%	23.02% (+3.50)	1.70%	2.33% (+0.63)
Kimi K2	9.89%	12.99% (+3.10)	1.57%	2.57% (+1.00)
Llama-4-Maverick	4.15%	6.74% (+2.59)	1.68%	3.78% (+2.10)
LongCat-Flash-Chat	18.68%	20.33% (+1.65)	2.69%	3.01% (+0.32)
Qwen3-Next	26.53%	29.34% (+2.81)	0.30%	0.60% (+0.30)

关键发现：

SELF-REDRAFT的改进率更高（修正更多错误）
但回归率也显著增加（破坏更多正确解）
回归率增幅在某些模型上很大（如Llama-4-Maverick +2.10%）

解读：重新起草是高风险操作。由于判别能力有限，模型常将正确解误判为错误并"改坏"，抵消了探索带来的收益。

跨模型行为差异

平衡策略差异（图6）：

蝴蝶图展示各模型在16次迭代中"refine" vs "redraft"建议的数量
巨大差异：
- 某些模型偏好"refine"（利用导向）
- 某些模型偏好"redraft"（探索导向）
- 无统一模式

含义：探索-利用平衡不是通用能力，而是模型特定的涌现特性，反映了：

预训练数据差异
模型架构影响
指令调优策略不同

案例分析

附录F完整案例：

任务：LeetCode风格的数组交换问题
原始解决方案：逻辑混乱，包含多个概念错误
反馈：详细指出5个具体问题，建议"redraft"
新解决方案：采用完全不同的动态规划方法，正确解决问题

观察：

当反馈质量高时，redraft能有效跳出错误方法
新方案展示了对问题的重新理解
但这种高质量反馈在实验中并非常态

结论与讨论

主要结论

SELF-REDRAFT有效但有限：在相同迭代预算下持续优于Self-Refine，但改进幅度有限（平均0.615%）
两大瓶颈：
- 反馈生成不足：模型难以识别方法论错误，无法提供有效的重起草指导
- 判别能力脆弱：误判导致有害的重起草，回归率上升抵消收益
模型特定性：平衡策略在不同LLM间差异巨大，非通用能力
巨大潜力：与pass@8上界的差距表明探索维度有大量未开发空间