PaperlayerView exact revision on arXiv

Source-linked AI summary

Synthesize, Execute and Debug: Learning to Repair for Neural Program Synthesis

Kavi Gupta, Peter Ebert Christensen, Xinyun Chen, Dawn Song

arXiv:2007.08095v2cs.LGcs.SEstat.ML

TL;DR

Complex program semantics make it difficult to synthesize programs consistent with input-output specifications. SED combines neural synthesis, execution, and iterative debugging to repair failing candidates, improving Karel synthesis and outperforming standard beam search in the reported setting.

  • Problem

    Complex program semantics, particularly in loop-containing programs, make it difficult to synthesize programs consistent with input-output specifications.

    Source: §1 · p. 1

  • Method

    SED generates candidate programs, executes them, and uses a neural debugger with execution traces to iteratively edit failing programs.

    Source: §1 · p. 2

  • Results

    On Karel, SED consistently improves its neural synthesizer and outperforms standard beam search when the synthesizer uses greedy decoding.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    SED shows that iterative repair can improve neural program synthesis without requiring the correct program to be generated in one shot.

    Source: Broader Impacts · p. 10

    The search terminates when all supplied examples pass, although this does not ensure semantic correctness on held-out cases.

    Source: §3.4 · p. 5

Abstract

from arXiv · show

The use of deep learning techniques has achieved significant progress for program synthesis from input-output examples. However, when the program semantics become more complex, it still remains a challenge to synthesize programs that are consistent with the specification. In this work, we propose SED, a neural program generation framework that incorporates synthesis, execution, and debugging stages. Instead of purely relying on the neural program synthesizer to generate the final program, SED first produces initial programs using the neural program synthesizer component, then utilizes a neural program debugger to iteratively repair the generated programs. The integration of the debugger component enables SED to modify the programs based on the execution results and specification, which resembles the coding process of human programmers. On Karel, a challenging input-output program synthesis benchmark, SED reduces the error rate of the neural program synthesizer itself by a considerable margin, and outperforms the standard beam search for decoding.

1 Introduction

Input-output program synthesis remains difficult when programs contain complex semantics such as loops. SED addresses this by combining neural synthesis with execution-guided iterative debugging, improving results on Karel.

1 Introduction

  • Input-output program synthesis seeks programs satisfying specifications, but loop-containing programs make partial execution results less informative.Existing systems generate programs from scratch, even when incorrect predictions could be repaired incrementally.Source: §1 · p. 1
  • The approach mirrors human debugging by repairing program fragments after observing incorrect outputs.Human programmers inspect written code and fix fragments that cause failures.Source: §1 · p. 2
  • SED first generates candidate programs, executes them against the specification, and iteratively edits the most promising failing candidate.The debugger uses both program tokens and execution traces, continuing until the specification is passed or the edit limit is reached.Source: §1 · p. 2
  • On Karel, SED consistently improves the neural synthesizer and outperforms standard beam search when the synthesizer uses greedy decoding.The benchmark includes programs with conditionals and loops.Source: §1 · p. 2

2 Problem Setup

The paper formulates synthesis as generating a DSL program consistent with input-output examples and repair as editing a buggy program under the same specification. Karel provides a loop- and conditional-containing test domain.

2 Problem Setup

  • The section introduces input-output synthesis and the program-repair problem handled by SED’s neural debugger.Both problems use the same input-output specification.Source: §2 · p. 2
  • Input-output synthesis generates a DSL program whose behavior matches the ground-truth program on valid inputs.Held-out examples are used to verify equivalence, although a small test set can make that verification imprecise.Source: §2 · p. 2
  • Program repair starts with a buggy program inconsistent with the specification and seeks edits that make it correct.The repair process may exploit the existing program rather than synthesizing a replacement from scratch.Source: §2 · p. 2
  • Karel describes a robot moving in a 2D grid and supports actions plus if, repeat, and while control flow constructs.These constructs make Karel a test bed for synthesis involving nontrivial program semantics.Source: §2 · p. 2

3 SED: Synthesize, Execute and Debug

SED combines a neural synthesizer with an execution-aware debugger that repairs failing candidates. Its training uses synthetic mutations and synthesizer errors, while best-first inference searches over repaired programs using specification satisfaction.

3 SED: Synthesize, Execute and Debug

  • SED produces candidate programs, executes them, and invokes debugging when they fail the specification.The framework then selects promising candidates and applies neural edits before final evaluation.Source: §3 · p. 2

3.1 Synthesizer

  • SED is compatible with encoder-decoder synthesizers that embed input-output pairs and decode program tokens.The framework is largely agnostic to the particular synthesizer, provided it has nontrivial prediction performance.Source: §3.1 · p. 3

3.2 Debugger

  • The debugger encodes input-output pairs, execution traces, and program tokens before an edit decoder generates repairs.TraceEmbed connects execution states with their corresponding I/O pairs, while ProgramEncoder jointly represents tokens and execution steps.Source: Figure 2 · p. 3, §3.2 · p. 4
  • The debugger supports KEEP, DELETE, INSERT[t], and REPLACE[t] operations, with INSERT repeatedly operating at the current input token.The total operation count is 2|V| + 2, and the other operations advance to the next program token.Source: Figure 1 · p. 3, §3.2 · p. 4
  • Execution traces are linked to program tokens through a bipartite graph, and related trace embeddings are averaged into token representations.A token is linked when it produces a state or initiates a loop or conditional whose body produces that state.Source: §3.2 · p. 4

3.3 Training

  • Two-stage training first learns repairs from synthetic AST mutations, then fine-tunes on incorrect programs produced by the neural synthesizer.Direct training on synthesizer errors is limited because a strong synthesizer produces relatively few wrong training examples.Source: §3.3 · p. 4

3.4 Inference Procedure

  • Best-first inference maintains a frontier of candidate programs, expands the highest-scoring unexpanded program, and stops when all input-output examples are satisfied.The search retains earlier candidates so it can avoid getting stuck when a later edit iteration is unpromising.Source: §3.4 · pp. 4–5
  • Greedy search instead selects the best current candidate at each edit iteration and stops after success or the maximum edit budget.The best-first alternative can fall back to outputs from earlier iterations.Source: §3.4 · p. 5

4 Evaluation

SED is evaluated for Karel synthesis and mutation-based repair using multiple synthesizers, debugger configurations, and search strategies. Across these evaluations, SED improves synthesis and repair, with execution traces, fine-tuning, and best-first search each affecting performance.

4.1 Evaluation Setup

  • The Karel benchmark contains 1,116,854 training samples, 2,500 validation examples, and 2,500 test examples, each specified by five input-output pairs plus one held-out pair.Generalization, which requires passing all six pairs, is the primary metric; exact match is also reported.Source: §4.1 · p. 5

4.2 Synthesizer Details

  • The experiments compare LGRL with beam size 32, greedy LGRL with beam size 1, and EGNPS with beam size 64 as candidate synthesizers.These synthesizer-only results form the first row of Table 1.Source: §4.2 · p. 6

4.3 Debugger Details

  • Debugger models use TraceEmbed or No TraceEmbed, are pretrained on synthetic 1–3-mutation programs, and use synthesizer-generated data for applicable fine-tuning.EGNPS debugging is fine-tuned with LGRL-generated data because executing all EGNPS beam programs is computationally expensive.Source: §4.3 · p. 6

4.4 Results

  • Models trained on 1–3 mutations repair around 70% of test programs with five mutations, while matching mutation distributions yield better performance.Figure 3 compares models trained on 1–3 versus 1–5 mutations across test mutation counts.Source: §4.4 · p. 6, Figure 3 · p. 6
  • TraceEmbed achieves the lowest repair error at each mutation count, although its larger models tend to overfit the training distribution.The overfitting tendency is attributed potentially to larger model sizes.Source: §4.4 · p. 6
  • SED consistently improves its underlying neural synthesizer on Karel, and with greedy LGRL decoding it outperforms standard beam search.With EGNPS, SED adds gains even though the synthesizer already uses execution information; an EGNPS ensemble improves from 8.32% to 7.78% generalization error with SED.Source: §4.4 · p. 7
  • SED repairs often move synthesizer predictions toward semantically correct programs requiring fewer edits than the ground truth, while remaining closer to the initial predictions.Without fine-tuning, SED also repairs semantic errors and edit distances beyond those represented by synthetic mutations.Source: §4.4 · p. 7, Figure 4 · p. 7
  • Fine-tuning improves results broadly, TraceEmbed generally helps most without fine-tuning, and matched-parameter controls show its gains are not explained by model size alone.The matched-size alternative reaches 15.88% generalization error without fine-tuning and 16.64% with fine-tuning, worse than smaller No TraceEmbed counterparts.Source: §4.4 · pp. 7–8, Figure 5 · p. 8

5 Related Work

SED builds on neural synthesis, execution-guided synthesis, and program-repair research by using execution results to repair synthesized programs. Its key distinction from prior Karel repair work is integrating debugging into synthesis, including programs far from the ground truth.

Program synthesis from input-output examples

  • SED extends execution-guided synthesis by using execution results to repair synthesized programs rather than only selecting among candidates.Prior work uses intermediate execution states to improve synthesis, while SED applies execution information to program repair.Source: §5 · p. 9

Generate-and-test techniques

  • Unlike symbolic generate-and-test methods, SED uses a neural design with simple heuristic search, while CEGIS methods typically require more complete formal specifications.The Karel setting provides only a few input-output examples as the specification.Source: §5 · p. 9

Program repair

  • SED incorporates neural program repair into synthesis, addressing relationships between programs and specifications that are typically complex.Its debugger differs from prior repair work focused mainly on syntactic correction or syntactically similar mutated programs.Source: §5 · p. 9
  • Unlike, SED improves synthesis results and can repair programs syntactically far from the ground truth by predicting alternative specification-satisfying programs.Prior work repairs programs created by randomly mutating ground-truth programs and does not study debugger-based synthesis improvement.Source: §5 · p. 9

6 Conclusion

SED connects program synthesis and repair through execution-guided iterative debugging. It outperforms beam search for greedy synthesis and improves synthesizers that already search or use execution information.

6 Conclusion

  • SED’s iterative repair outperforms beam search when the synthesizer uses greedy decoding.The framework also significantly boosts synthesizer-only performance when the synthesizer already searches or incorporates execution information.Source: §6 · p. 9
  • A two-stage training scheme alleviates program aliasing in supervised training and achieves strong generalization performance.The framework is presented as potentially extensible to broader specification-guided synthesis applications.Source: §6 · p. 9

Broader Impacts

SED addresses the need for precisely correct synthesized programs by allowing partial solutions to be corrected iteratively rather than requiring one-shot generation. The authors therefore view SED-like frameworks as applicable to a broad range of synthesis tasks.

Broader Impacts

  • SED allows partial solutions to be corrected through iterative improvement instead of requiring the solution to be generated correctly in one shot.The paper reports an overall performance improvement from this process.Source: Broader Impacts · p. 10
  • The authors believe SED-like frameworks could apply to a broad range of program synthesis tasks.Source: Broader Impacts · p. 10

A.1 LGRL Training

The experiments use LGRL and EGNPS synthesizers with specified training and inference configurations. LGRL is evaluated with greedy decoding and 32-beam search, while EGNPS uses 64-beam search.

A.1 LGRL Training

  • LGRL is trained for 50 epochs with minibatch SGD, batch size 128, gradient clipping, and a learning rate decayed by 50% every 105 steps.The reported initial learning rate is 1, and the model uses the Karel training dataset.Source: §A.1 · p. 12
  • LGRL-GD uses greedy decoding with B = 1, whereas LGRL uses beam search with B = 32.These configurations define the two LGRL synthesizers evaluated in the experiments.Source: §A.1 · p. 12

A.2 EGNPS Model

  • EGNPS is trained for 10 epochs with learning rate 5 × 10^-4 and batch size 16, then evaluated with beam size 64.The EGNPS training and inference settings are reported separately from the LGRL configurations.Source: §A.2 · p. 12

A.3 Debugger Training

The debugger training uses mutation-generated Karel programs and a staged optimization procedure with gradient control and later fine-tuning on incorrect examples.

A.3 Debugger Training

  • The debugger was trained for 50 epochs on Karel programs generated by random mutations sampled in proportion to mutation count.Source: §A.3 · p. 12
  • Training used minibatch SGD with batch size 64, gradient clipping at magnitude 1, and a learning rate of 1 decayed by 50% every 105 steps.Source: §A.3 · p. 12
  • Models were fine-tuned for 50 epochs on incorrect training examples with learning rate 10−4.Source: §A.3 · p. 12

A.4 TraceEmbed Architecture

TraceEmbed is a residual convolutional network that combines input, output, and trace grids while preserving spatial locality, producing a 256-dimensional program-token embedding.

A.4 TraceEmbed Architecture

  • TraceEmbed stacks input, output, and trace grids along the channel axis to preserve spatial locality while connecting features across grids.Source: §A.4 · p. 12
  • The network applies an initial convolution from 15 × 3 channels to 64, followed by three ResNet blocks using batch normalization, ReLU, convolution, and residual connections.Source: §A.4 · p. 12
  • A final fully connected layer flattens the grid into a 256-dimensional embedding matching the size of a program-token embedding.Source: §A.4 · p. 12

B More Descriptions of the Karel Domain

The Karel domain is defined by a grid-based DSL with movement, marker interaction, conditionals, and loops, while the accompanying algorithmic machinery uses greedy search and syntax-preserving program mutations.

B More Descriptions of the Karel Domain

C Full Greedy Algorithm

  • The full greedy decoding procedure is specified in Algorithm 2, with robot orientations including East and South shown in the accompanying material.Source: C Full Greedy Algorithm · pp. 12–13

D Mutations

  • Six mutation types—insert, delete, replace, wrap, unwrap, and replaceControl—modify program nodes while maintaining syntactic validity.Control constructs include if, ifelse, while, and repeat.Source: D Mutations · p. 13

Related papers

Loading 2007.08095v2…