title: B4: Towards Optimal Assessment of Plausible Code Solutions with
    Plausible Tests
summary: 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.
paper_authors._id: 66ed7bdb6babd2a705108320
paper_authors.name: Mouxiang Chen
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2024-09-20T15:23:23.634Z
paper_authors._id: 66d58df54b87a685ccb8e4a0
paper_authors.avatarUrl: /avatars/2566c20d79088ba761215b9a0197cb8e.svg
paper_authors.fullname: Mouxiang Chen
paper_authors.type: user
paper_authors.user: chenmouxiang
paper_authors._id: 66ed7bdb6babd2a705108321
paper_authors.name: Zhongxin Liu
paper_authors._id: 66ed7bdb6babd2a705108322
paper_authors.name: He Tao
paper_authors._id: 66ed7bdb6babd2a705108323
paper_authors.name: Yusu Hong
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2024-09-20T15:26:59.773Z
paper_authors._id: 66d6cffde75a7f30e6439eba
paper_authors.avatarUrl: /avatars/f9e80ff9667995d21158247a314d2490.svg
paper_authors.fullname: YusuHong
paper_authors.type: user
paper_authors.user: YusuHong
paper_authors._id: 66ed7bdb6babd2a705108324
paper_authors.name: David Lo
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2024-09-20T15:27:09.694Z
paper_authors._id: 66a34bd87a0eac450c4428ee
paper_authors.avatarUrl: /avatars/1eb652e1b5b9abd295fcf9e89259bd04.svg
paper_authors.fullname: David Lo
paper_authors.type: user
paper_authors.user: davidlo3917
paper_authors._id: 66ed7bdb6babd2a705108325
paper_authors.name: Xin Xia
paper_authors.status: extracted_pending
paper_authors.statusLastChangedAt: 2024-09-20T13:42:52.175Z
paper_authors._id: 64472fd0d91be3130a37c97b
paper_authors.avatarUrl: /avatars/ac4a3d6ad416dda4d93f48762a7ccbe3.svg
paper_authors.fullname: Xin Xia
paper_authors.type: user
paper_authors.user: xinxia86
paper_authors._id: 66ed7bdb6babd2a705108326
paper_authors.name: Jianling Sun
paper_title: B4: Towards Optimal Assessment of Plausible Code Solutions with
    Plausible Tests
paper_summary: 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.
paper_ai_summary: 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.
paper_ai_keywords: Bayesian framework posterior probability integer programming heuristic strategies prior knowledge large language models LLM-generated tests