Source-linked AI summary
SPoC: Search-based Pseudocode to Code
Sumith Kulal, Panupong Pasupat, Kartik Chandra, Mina Lee, Oded Padon, Alex Aiken, Percy Liang
TL;DR
Synthesizing long, functionally correct programs from pseudocode is difficult because search needs credit assignment when candidate programs fail. SPoC searches alternative line-level translations and uses compilation-error localization to focus that search, achieving 44.7% success under 100 compilations versus 24.6% for the top-one translation.
Problem
Mapping pseudocode to functionally correct long programs requires guiding search beyond sparse whole-program success signals, especially because compilation errors make up 88.7% of failures.
Method
The method treats each pseudocode-line translation as a discrete program portion and localizes compilation failures to focus search on alternative translations for responsible portions.
Results
44.7% success is achieved under 100 synthesis trials, compared with 24.6% for the top-one translation.
Takeaways & Limitations
Search with error localization improves synthesis success under a limited compilation budget, while prefix-based pruning is more effective under larger budgets.
Takeaways & Limitations
Incorrect error localization can cause catastrophic search failure, whereas best-first search can still find a correct program.
Abstract
from arXiv · showhide
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%.
1 Introduction
SPoC synthesizes functionally correct long programs by searching over pseudocode translations and using compilation errors to guide credit assignment. It introduces the SPoC dataset and reports substantially higher success under a fixed compilation budget.
- 1 Introduction: The framework maps natural-language pseudocode and test cases to functionally correct programs with non-trivial intermediate computation.Test cases provide semantic specification, while pseudocode guides intermediate computations.
- 1 Introduction: Search selects alternative translations for individual pseudocode lines instead of relying only on the top-one translation.Each pseudocode line is treated as a discrete program portion.
- 1 Introduction: 88.7% of search failures are compilation errors, motivating error localization that redirects search toward translations of offending portions.The method identifies the responsible portion and focuses subsequent search there.
- 1 Introduction: Two localization methods are proposed: a multiclass classifier that down-weights an offending line and prefix-based pruning that blacklists a guaranteed-erroneous prefix.The classifier also uses the error message and pseudocode; prefix pruning uses additional compilations.
- 1 Introduction: 44.7% success is achieved with 100 synthesis trials, compared with 24.6% for the top-one translation.The multiclass model reduces trials in 15.5% of programs, while prefix pruning performs better under larger budgets.
2 Problem statement
The task takes pseudocode lines, indentation, and public input-output tests, then synthesizes an equally line-structured program. A candidate is accepted only after compilation and successful execution on public and hidden tests.
- 2 Problem statement: The system receives L pseudocode lines with indentation levels and k public input-output test cases.Each test case pairs an input string with its expected output string.
- 2 Problem statement: It synthesizes a program consisting of L code lines corresponding to the pseudocode lines.The program is evaluated against public and additional hidden test cases.
- 2 Problem statement: At training time, examples contain pseudocode, a gold program, and both public and hidden test cases.
- 2 Problem statement: At test time, only pseudocode, public tests, and a computation budget are available, with one compiler-and-execution call per synthesis trial.The final program is validated on both public and hidden tests.
3 Dataset
SPoC was created to combine human-authored pseudocode at consistent granularity with functional test-case validation for non-trivial competitive-programming solutions. It contains 18,356 programs across 677 problems with problem- and worker-held-out test sets.
- 3 Dataset: Existing language-to-code datasets often lack functional validation and therefore rely on syntactic proxy metrics.These proxies include exact match, BLEU, and tree node F1.
- 3 Dataset: NAPS provides pseudocode and test cases, but its synthetic and human-authored descriptions differ in information content and granularity.Its pseudocode-to-code length ratios are 1:1.82 for synthetic data and 1:3.26 for human-authored data.
- 3 Dataset: SPoC pairs competitive-programming programs with human-authored pseudocode, public tests, and hidden tests at consistent annotation granularity.The dataset was created because no existing resource combined these properties.
- 3 Dataset: The collection scrapes accepted C++ solutions and filters constructs that are difficult to annotate consistently.
- 3 Dataset: Programs are decomposed into code lines, with single-statement blocks grouped with preceding control statements for higher-level descriptions.For example, a one-line input loop can receive a higher-level description.
- 3 Dataset: 59 crowdworkers annotated the code, after qualification screening based on manually inspected initial annotations.
- 3 Dataset: The dataset contains 18,356 programs from 677 problems, averaging 14.7 lines per program, with splits held out by problem and worker.The problem split holds out 158 problems; the worker split holds out 7 workers.
4 Base approach
The base approach translates each pseudocode line into ranked candidate code lines, then uses best-first search over candidate combinations. Programs are tested until one compiles and passes public tests or the budget is exhausted.
- 4 Base approach: A translation model generates M candidate code lines for each pseudocode line, producing ranked candidates with probabilities.The model uses an LSTM encoder-decoder with copying and coverage; experiments set M = 100.
- 4 Base approach: Best-first search forms programs by selecting one candidate from each line’s candidate list.
- 4 Base approach: In the illustrated example, best-first search succeeds in four compiler calls, while error localization down-weights c21 and succeeds earlier.The satisfying program is (c11, c22, c32).
- 4 Base approach: The search initially tests the top-one translation and orders candidate combinations by the product of their line-level probabilities.
- 4 Base approach: After a failed compilation, runtime execution, or public-test mismatch, the algorithm inserts unexplored one-line alternatives into the search heap.Search stops on a program passing all public tests or when the computation budget is used.
5 Error localization
The paper treats compilation outcomes as a sparse search signal and uses error localization to identify code portions responsible for failures. It introduces multiclass classification and prefix-based pruning to guide subsequent candidate selection.
- Motivation: 88.7% of best-first-search failures are compilation errors, motivating compilation-based credit assignment instead of relying only on pass/fail outcomes.The compiler provides error messages and line numbers, but reported locations can be noisy.
- Error localization: Error localization uses pseudocode, synthesized code, and the first compiler error to infer offending lines or abstain.Detected lines can trigger down-weighting or blacklisting of their translation candidates.
- Multiclass classification: Multiclass classification predicts one offending line with a neural model using pseudocode, code, error-message, and positional representations.It returns the highest-probability line only when its probability exceeds β_mul = 0.95.
- Multiclass classification: The classifier reduces the current candidate probability for the predicted line, rebuilds the search heap, and skips previously explored programs.The candidate probability is multiplied by α < 1.
- Prefix-based pruning: Prefix-based pruning uses additional compiler calls to find an offending code prefix, addressing uncertain line predictions and context-dependent errors.It tests selected offsets to limit budget use and abstains when no offending prefix is found.
6 Experiments
The experiments evaluate functional correctness, search efficiency, and error-localization strategies for pseudocode-to-code synthesis. Search performance depends on both candidate translation quality and how compilation failures are localized.
- Evaluation: Success rate at B measures the fraction of examples producing an accepted program within B synthesis trials.Each trial permits one compiler call and execution on public tests; final programs are checked on public and hidden tests.
- Translation accuracy: 84–87% line-level functional accuracy does not translate into reliable program-level synthesis.Only 18.2% of TESTP and 32.0% of TESTW programs have every top candidate correct, while combined top candidates succeed on 17.8% and 30.7%.
- Oracle success rate: 44.8% of TESTP and 28.6% of TESTW programs contain a line lacking any correct candidate among the top M = 100.The corresponding infinite-budget oracle success rates are 55.2% on TESTP and 71.4% on TESTW, assuming incorrect candidates cannot combine into correct behavior.
- Synthesis results: Multiclass localization improves success rates most up to approximately B = 1500, whereas prefix-based pruning performs better at higher budgets.Prefix-based pruning uses extra compilations, so it performs worse under tighter budgets.
- Synthesis results: Prefix-based pruning slightly increases compilation costs on easier examples but provides larger benefits on difficult programs.Its verified error-prefix decisions make the benefit outweigh the cost for harder programs.
- Error analysis: Prefix-based pruning reduced one example’s search from 1511 to 413 trials by detecting incorrect candidates associated with pseudocode line 9.A contrasting example shows multiclass localization incorrectly selecting line 3 and causing failure, while best-first search finds a correct program in 80 iterations.
7 Related work and discussion
The paper situates its approach among program synthesis, semantic parsing, and automated program-repair work on error localization. Its error-localization model extends compiler-informed approaches by incorporating pseudocode when selecting offending lines.
- Program synthesis: Program synthesis commonly uses constraint satisfaction, while brute-force enumeration remains effective for some problems but struggles as search spaces grow.
- Semantic parsing: Semantic parsing traditionally maps natural-language questions to executable database queries, with related work also handling sequences of utterances.
- Error localization: Automated program-repair research has localized syntax errors, defined semantic errors, and compiler-indicated error locations.
- Error localization: The multiclass model should select the pseudocode-consistent offending line when multiple code lines could fix a compilation error.