# SPoC: Search-based Pseudocode to Code

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

## Key facts

- Cited by 176 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2019.

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

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [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)
- [CodeXGLUE: A Machine Learning Benchmark Dataset for Code Understanding and Generation](https://mlsanity.com/paper/2102.04664/) (2021)
- [InCoder: A Generative Model for Code Infilling and Synthesis](https://mlsanity.com/paper/2204.05999/) (2022)
- [CodeGeeX: A Pre-Trained Model for Code Generation with Multilingual Benchmarking on HumanEval-X](https://mlsanity.com/paper/2303.17568/) (2023)
- [VerilogEval: Evaluating Large Language Models for Verilog Code Generation](https://mlsanity.com/paper/2309.07544/) (2023)
- [Spider 2.0: Evaluating Language Models on Real-World Enterprise Text-to-SQL Workflows](https://mlsanity.com/paper/2411.07763/) (2024)
- [Is Self-Repair a Silver Bullet for Code Generation?](https://mlsanity.com/paper/2306.09896/) (2023)
- [Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Models](https://mlsanity.com/paper/2208.06677/) (2022)
- [SantaCoder: don't reach for the stars!](https://mlsanity.com/paper/2301.03988/) (2023)
- [Multi-lingual Evaluation of Code Generation Models](https://mlsanity.com/paper/2210.14868/) (2022)
- [MultiPL-E: A Scalable and Extensible Approach to Benchmarking Neural Code Generation](https://mlsanity.com/paper/2208.08227/) (2022)
- [FollowBench: A Multi-level Fine-grained Constraints Following Benchmark for Large Language Models](https://mlsanity.com/paper/2310.20410/) (2023)
- [A Survey of Text Watermarking in the Era of Large Language Models](https://mlsanity.com/paper/2312.07913/) (2023)
- [Self-Edit: Fault-Aware Code Editor for Code Generation](https://mlsanity.com/paper/2305.04087/) (2023)
- [Large Language Models as Analogical Reasoners](https://mlsanity.com/paper/2310.01714/) (2023)
- [Execution-based Code Generation using Deep Reinforcement Learning](https://mlsanity.com/paper/2301.13816/) (2023)
- [Productivity Assessment of Neural Code Completion](https://mlsanity.com/paper/2205.06537/) (2022)
- [The Robots are Here: Navigating the Generative AI Revolution in Computing Education](https://mlsanity.com/paper/2310.00658/) (2023)
- [Don't Overthink it. Preferring Shorter Thinking Chains for Improved LLM Reasoning](https://mlsanity.com/paper/2505.17813/) (2025)
- [AnalogCoder: Analog Circuit Design via Training-Free Code Generation](https://mlsanity.com/paper/2405.14918/) (2024)
- [Leveraging Automated Unit Tests for Unsupervised Code Translation](https://mlsanity.com/paper/2110.06773/) (2021)
- [Improving Code Generation by Training with Natural Language Feedback](https://mlsanity.com/paper/2303.16749/) (2023)
- [Reuse, Don't Retrain: A Recipe for Continued Pretraining of Language Models](https://mlsanity.com/paper/2407.07263/) (2024)

## Abstract (arXiv)

We consider the task of mapping pseudocode to long programs that are functionally correct. Given test cases as a mechanism to validate programs, we search over the space of possible translations of the pseudocode to find a program that passes the validation. However, without proper credit assignment to localize the sources of program failures, it is difficult to guide search toward more promising programs. We propose to perform credit assignment based on signals from compilation errors, which constitute 88.7% of program failures. Concretely, we treat the translation of each pseudocode line as a discrete portion of the program, and whenever a synthesized program fails to compile, an error localization method tries to identify the portion of the program responsible for the failure. We then focus search over alternative translations of the pseudocode for those portions. For evaluation, we collected the SPoC dataset (Search-based Pseudocode to Code) containing 18,356 programs with human-authored pseudocode and test cases. Under a budget of 100 program compilations, performing search improves the synthesis success rate over using the top-one translation of the pseudocode from 25.6% to 44.7%.