Large language models (LLMs) excel at implementing code from functionality
descriptions, but struggle with algorithmic problems that require not only
implementation but also identification of the suitable algorithm. Moreover,
LLM-generated programs lack guaranteed correctness and require human
verification. To address these challenges, we propose ALGO, a framework that
synthesizes Algorithmic programs with LLM-Generated Oracles to guide the
creation and verify their correctness. ALGO first generates a probably correct
but possibly slow reference oracle by prompting an LLM to exhaustively
enumerate all the combinations of relevant variables. This oracle is then
utilized to guide an arbitrary search strategy in exploring the algorithm space
and to verify the algorithms synthesized. Our study shows that the
LLM-generated oracles are correct for 88% of the cases. With the oracles as
verifiers, ALGO can be integrated with any existing code generation model in a
model-agnostic manner to enhance its performance. Experiments show that when
equipped with ALGO, we achieve an 8x better one-submission pass rate over the
Codex model and a 2.6x better one-submission pass rate over CodeT, the current
state-of-the-art model on CodeContests. We can also get 1.3x better pass rate
over the ChatGPT Code Interpreter on unseen problems.

提出了一种名为 ALGO 的框架，该框架使用 LLM 生成的神谕来引导算法程序的创建和验证。实验表明，与 Codex 和 CodeT 等现有领先模型相比，在处理未知问题时，使用 ALGO 可获得 8x 和 2.6x 的更好的一次提交通过率。

使用生成的 Oracle 验证器合成算法程序

ALGO: Synthesizing Algorithmic Programs with Generated Oracle Verifiers

A code generation model generates code by taking a prompt from a code
comment, existing code, or a combination of both. Although code generation
models (e.g., GitHub Copilot) are increasingly being adopted in practice, it is
unclear whether they can successfully be used for unit test generation without
fine-tuning. To fill this gap, we investigated how well three generative models
(CodeGen, Codex, and GPT-3.5) can generate test cases. We used two benchmarks
(HumanEval and Evosuite SF110) to investigate the context generation's effect
in the unit test generation process. We evaluated the models based on
compilation rates, test correctness, coverage, and test smells. We found that
the Codex model achieved above 80% coverage for the HumanEval dataset, but no
model had more than 2% coverage for the EvoSuite SF110 benchmark. The generated
tests also suffered from test smells, such as Duplicated Asserts and Empty
Tests.

该研究探讨了三种代码生成模型（CodeGen、Codex 和 GPT-3.5）在单元测试生成中的效果，发现 Codex 模型在 HumanEval 数据集中可以达到 80% 以上的覆盖率，但在 EvoSuite SF110 基准测试中，没有模型的覆盖率超过 2% 且生成的测试代码存在多种测试异味问题。