B4: Towards Optimal Assessment of Plausible Code Solutions with
  Plausible Tests
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 B4 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.
66ed7bdb6babd2a705108320
Mouxiang Chen
admin_assigned
2024-09-20T15:23:23.634Z
66d58df54b87a685ccb8e4a0
/avatars/2566c20d79088ba761215b9a0197cb8e.svg
Mouxiang Chen
user
chenmouxiang
66ed7bdb6babd2a705108321
Zhongxin Liu
66ed7bdb6babd2a705108322
He Tao
66ed7bdb6babd2a705108323
Yusu Hong
admin_assigned
2024-09-20T15:26:59.773Z
66d6cffde75a7f30e6439eba
/avatars/f9e80ff9667995d21158247a314d2490.svg
YusuHong
user
YusuHong
66ed7bdb6babd2a705108324
David Lo
admin_assigned
2024-09-20T15:27:09.694Z
66a34bd87a0eac450c4428ee
/avatars/1eb652e1b5b9abd295fcf9e89259bd04.svg
David Lo
user
davidlo3917
66ed7bdb6babd2a705108325
Xin Xia
extracted_pending
2024-09-20T13:42:52.175Z
64472fd0d91be3130a37c97b
/avatars/ac4a3d6ad416dda4d93f48762a7ccbe3.svg
Xin Xia
user
xinxia86
66ed7bdb6babd2a705108326
Jianling Sun
B4: Towards Optimal Assessment of Plausible Code Solutions with
  Plausible Tests
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 B4 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.
The research defines an optimal code selection strategy using Bayesian posterior probability within an integer programming framework and proposes an efficient approximation to outperform heuristics in selecting code solutions with LLM-generated tests.
Bayesian framework posterior probability integer programming heuristic strategies prior knowledge large language models LLM-generated tests