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 的更好的一次提交通过率。