一句话：提出贝叶斯框架下用似真测试选择最佳代码解的最优策略及其可计算近似 B4。
在代码生成中，从多个生成解中选出最佳解十分关键，但可靠测试往往缺失或昂贵。论文研究当代码解与测试都只是似真而非可靠时，如何最优地选择最佳解。作者证明在贝叶斯框架下，最优策略可基于解与测试间通过状态的后验概率定义，并将最佳解识别形式化为整数规划问题；随后提出高效近似该不可计算最优策略的方法，其误差由先验知识正确性界定，并引入针对代码生成任务的有效先验。理论与实证表明现有启发式策略存在局限；B4 在用 LLM 生成测试评估 LLM 生成代码时显著优于启发式，最困难场景下相对最强启发式提升最高 50%，相对随机选择提升 246%。
Selecting the best code solution from multiple generated ones is an essential task in code generation, which can be achieved by using some reliable validators (e.g., developer-written test cases) for assistance. Since reliable test cases are not always available and can be expensive to build in practice, researchers propose to automatically generate test cases to assess code solutions. However, when both code solutions and test cases are plausible and not reliable, selecting the best solution becomes challenging. Although some heuristic strategies have been proposed to tackle this problem, they lack a strong theoretical guarantee and it is still an open question whether an optimal selection strategy exists. Our work contributes in two ways. First, we show that within a Bayesian framework, the optimal selection strategy can be defined based on the posterior probability of the observed passing states between solutions and tests. The problem of identifying the best solution is then framed as an integer programming problem. Second, we propose an efficient approach for approximating this optimal (yet uncomputable) strategy, where the approximation error is bounded by the correctness of prior knowledge. We then incorporate effective prior knowledge to tailor code generation tasks. Both theoretical and empirical studies confirm that existing heuristics are limited in selecting the best solutions with plausible test cases. Our proposed approximated optimal strategy ℬ4 significantly surpasses existing heuristics in selecting code solutions generated by large language models (LLMs) with LLM-generated tests, achieving a relative performance improvement by up to 50% over the strongest heuristic and 246% over the random selection in the most challenging scenarios. Our code is publicly available at https://github.com/ZJU-CTAG/B4.
@inproceedings{paperbot8390,
title = {B4: Towards Optimal Assessment of Plausible Code Solutions with Plausible Tests},
author = {Mouxiang Chen and Zhongxin Liu and He Tao and Yusu Hong and David Lo and Xin Xia and Jianling Sun},
booktitle = {ASE},
year = {2024},
doi = {10.1145/3691620.3695536}
}