# ALGO: Synthesizing Algorithmic Programs with LLM-Generated Oracle Verifiers

arXiv: https://arxiv.org/abs/2305.14591 · HTML: https://mlsanity.com/paper/2305.14591/

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 37 references that are in the map.
- First posted on arXiv 24 May 2023.

## Builds on (most cited first, 25 of 25)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Teaching Large Language Models to Self-Debug](https://mlsanity.com/paper/2304.05128/) (2023)
- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis](https://mlsanity.com/paper/2203.13474/) (2022)
- [Large Language Models Can Self-Improve](https://mlsanity.com/paper/2210.11610/) (2022)
- [InCoder: A Generative Model for Code Infilling and Synthesis](https://mlsanity.com/paper/2204.05999/) (2022)
- [CodeT: Code Generation with Generated Tests](https://mlsanity.com/paper/2207.10397/) (2022)
- [Generating Sequences by Learning to Self-Correct](https://mlsanity.com/paper/2211.00053/) (2022)
- [Reward Design with Language Models](https://mlsanity.com/paper/2303.00001/) (2023)
- [LEVER: Learning to Verify Language-to-Code Generation with Execution](https://mlsanity.com/paper/2302.08468/) (2023)
- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [SPoC: Search-based Pseudocode to Code](https://mlsanity.com/paper/1906.04908/) (2019)
- [Natural Language to Code Translation with Execution](https://mlsanity.com/paper/2204.11454/) (2022)
- [Reading Between the Lines: Modeling User Behavior and Costs in AI-Assisted Programming](https://mlsanity.com/paper/2210.14306/) (2022)
- [Coder Reviewer Reranking for Code Generation](https://mlsanity.com/paper/2211.16490/) (2022)
- [TOGA: A Neural Method for Test Oracle Generation](https://mlsanity.com/paper/2109.09262/) (2021)
- [Fault-Aware Neural Code Rankers](https://mlsanity.com/paper/2206.03865/) (2022)
- [A Theory of Formal Synthesis via Inductive Learning](https://mlsanity.com/paper/1505.03953/) (2015)
- [Type-Directed Synthesis of Visualizations from Natural Language Queries](https://mlsanity.com/paper/2209.01081/) (2022)
- [ObSynth: An Interactive Synthesis System for Generating Object Models from Natural Language Specifications](https://mlsanity.com/paper/2210.11468/) (2022)

## Built on by (most cited first, 30 of 41)

- [Large Language Models for Software Engineering: A Systematic Literature Review](https://mlsanity.com/paper/2308.10620/) (2023)
- [CRUXEval: A Benchmark for Code Reasoning, Understanding and Execution](https://mlsanity.com/paper/2401.03065/) (2024)
- [Automatically Correcting Large Language Models: Surveying the landscape of diverse self-correction strategies](https://mlsanity.com/paper/2308.03188/) (2023)
- [R2E-Gym: Procedural Environments and Hybrid Verifiers for Scaling Open-Weights SWE Agents](https://mlsanity.com/paper/2504.07164/) (2025)
- [Debug like a Human: A Large Language Model Debugger via Verifying Runtime Execution Step-by-step](https://mlsanity.com/paper/2402.16906/) (2024)
- [ACECODER: Acing Coder RL via Automated Test-Case Synthesis](https://mlsanity.com/paper/2502.01718/) (2025)
- [Phenomenal Yet Puzzling: Testing Inductive Reasoning Capabilities of Language Models with Hypothesis Refinement](https://mlsanity.com/paper/2310.08559/) (2023)
- [From LLMs to LLM-based Agents for Software Engineering: A Survey of Current, Challenges and Future](https://mlsanity.com/paper/2408.02479/) (2024)
- [LLM-based Agents Suffer from Hallucinations: A Survey of Taxonomy, Methods, and Directions](https://mlsanity.com/paper/2509.18970/) (2025)
- [Confidence Matters: Revisiting Intrinsic Self-Correction Capabilities of Large Language Models](https://mlsanity.com/paper/2402.12563/) (2024)
- [Enhancing Large Language Models in Coding Through Multi-Perspective Self-Consistency](https://mlsanity.com/paper/2309.17272/) (2023)
- [LongCodeZip: Compress Long Context for Code Language Models](https://mlsanity.com/paper/2510.00446/) (2025)
- [Automated Proof Generation for Rust Code via Self-Evolution](https://mlsanity.com/paper/2410.15756/) (2024)
- [EffiLearner: Enhancing Efficiency of Generated Code via Self-Optimization](https://mlsanity.com/paper/2405.15189/) (2024)
- [LLM-Assisted Code Cleaning For Training Accurate Code Generators](https://mlsanity.com/paper/2311.14904/) (2023)
- [Competition-Level Problems are Effective LLM Evaluators](https://mlsanity.com/paper/2312.02143/) (2023)
- [Zero-Shot Detection of Machine-Generated Codes](https://mlsanity.com/paper/2310.05103/) (2023)
- [EVOR: Evolving Retrieval for Code Generation](https://mlsanity.com/paper/2402.12317/) (2024)
- [SWE-Synth: Synthesizing Verifiable Bug-Fix Data to Enable Large Language Models in Resolving Real-World Bugs](https://mlsanity.com/paper/2504.14757/) (2025)
- [The Counterfeit Conundrum: Can Code Language Models Grasp the Nuances of Their Incorrect Generations?](https://mlsanity.com/paper/2402.19475/) (2024)
- [Scaling LLM Inference with Optimized Sample Compute Allocation](https://mlsanity.com/paper/2410.22480/) (2024)
- [Measuring the Influence of Incorrect Code on Test Generation](https://mlsanity.com/paper/2409.09464/) (2024)
- [AutoCode: LLMs as Problem Setters for Competitive Programming](https://mlsanity.com/paper/2510.12803/) (2025)
- [Scattered Forest Search: Smarter Code Space Exploration with LLMs](https://mlsanity.com/paper/2411.05010/) (2024)
- [Can LLMs Generate High-Quality Test Cases for Algorithm Problems? TestCase-Eval: A Systematic Evaluation of Fault Coverage and Exposure](https://mlsanity.com/paper/2506.12278/) (2025)
- [Scaling Test-Time Compute to Achieve IOI Gold Medal with Open-Weight Models](https://mlsanity.com/paper/2510.14232/) (2025)
- [Top Pass: Improve Code Generation by Pass@k-Maximized Code Ranking](https://mlsanity.com/paper/2408.05715/) (2024)
- [Scoring Verifiers: Evaluating Synthetic Verification for Code and Reasoning](https://mlsanity.com/paper/2502.13820/) (2025)
- [ArchCode: Incorporating Software Requirements in Code Generation with Large Language Models](https://mlsanity.com/paper/2408.00994/) (2024)
- [Can Vision-Language Models Handle Long-Context Code? An Empirical Study on Visual Compression](https://mlsanity.com/paper/2602.00746/) (2026)

## Abstract (arXiv)

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 generation and verify their correctness. ALGO first generates a 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 synthesized algorithms. 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. The problem set we used for testing, the prompts we used, the verifier and solution programs, and the test cases generated by ALGO are available at https://github.com/zkx06111/ALGO.