Learning to Infer Program Sketches

Motivation and approach

• The approach addresses synthesis from both input-output examples and natural-language specifications, reflecting how programmers combine learned patterns with explicit reasoning.The motivating examples contrast familiar tasks, where recognition can provide most of the program, with unfamiliar tasks requiring reasoning about remaining code.Source: §1 · p. 1
• Previous sketch-based systems used fixed, hand-designed grammars that could not adapt sketch specificity to task difficulty.They could not learn to produce more detailed sketches for easy tasks or more general sketches for difficult ones.Source: §1 · p. 2
• The system dynamically combines neural pattern recognition with symbolic search, learning how much to rely on each component for a given programming task.Easy tasks can receive fuller sketches, while difficult tasks can leave more work to symbolic synthesis.Source: §1 · p. 2

Contributions

• The proposed system learns an intermediate sketch representation between a neural sketch generator and an enumerative symbolic synthesizer without explicit supervision.Its training objective teaches the network to find suitable sketches rather than relying on directly labeled intermediate representations.Source: §1 · p. 2
• The system is evaluated on list-processing and string-transformation programming-by-example domains and achieves state-of-the-art performance on the AlgoLisp English-to-code test dataset.The paper presents this evaluation as validation of its neuro-symbolic program synthesis system.Source: §1 · p. 2

Problem formulation

• Each specification Xi is assumed to be satisfied by an unknown true program Fi in a domain-specific language.For input-output specifications, the true program must satisfy every provided example.Source: §2 · p. 2
• The synthesis goal is to recover Fi from Xi and maximize the probability of solving each task within a threshold time t.The formulation explicitly treats solution speed as part of the objective.Source: §2 · p. 2
• Specifications may combine input-output examples with additional informal information such as natural-language instructions.The same probability-of-recovery objective applies when natural language is included in Xi.Source: §2 · p. 2

3.1. System Overview:

• A sketch is a valid program tree with arbitrary subtrees replaced by <HOLE>, allowing the system to learn where symbolic search is needed.The sketch generator proposes sketches from the specification, and the synthesizer fills holes through explicit symbolic search.Source: §3.1 · pp. 2–3
• The system extracts candidate sketches from the generator and gives them to a synthesizer that searches for full programs satisfying the specification.The synthesizer selects programs by symbolic search over the proposed sketches.Source: §3.1 · p. 3

3.2. Learning to Infer Sketches via Self-supervision

• Unlike fixed sketch systems, the approach learns how much detail to place in each sketch and therefore how much to rely on each component.The domain-general grammar also supports implementation across multiple programming domains with little overhead.Source: §3.1 · p. 3, §3.2 · p. 3
• Training rewards sketches from which the target program can be recovered quickly under a sampled evaluation budget.The objective maximizes the generator’s probability of sketches whose synthesis time is below the budget t.Source: §3.2 · p. 3
• The learned distribution contains concrete sketches for easy problems and more general sketches for difficult problems requiring greater symbolic search.Sampling budgets during training makes the system robust to varying enumeration limits and problem difficulty.Source: §3.2 · p. 3

4.1. Seq-to-Seq Neural Sketch Generator

• The neural generator is an attention-based sequence-to-sequence RNN, supplemented by a learned LSTM language model that reweights token probabilities.The generator encodes the specification and decodes program tokens while attending to it.Source: §4.1 · pp. 3–4

4. Our Implementation

• SKETCHADAPT combines a neural sketch generator with a symbolic synthesizer that fills sketch holes using guided enumeration.The model’s overview feeds specifications to the generator, then uses a recognizer-conditioned synthesizer to complete programs.Source: §4 · p. 3, Figure 1 · p. 4, §4.2 · p. 4

4.2. Synthesis via Enumeration

• The symbolic synthesizer uses a breadth-first probabilistic enumerator and a neural recognizer whose predicted production probabilities guide search.The enumerator operates over a strongly typed DSL and ranks candidate programs by their induced probability.Source: §4.2 · p. 4
• Pure synthesis enumerates roughly 3 × 10^3 programs per second, while list-processing enumeration exceeds 10^6 programs per second.Enumeration is fast for small programs but becomes impractical as program size grows because the search space is exponential.Source: §4.2 · p. 4
• SKETCHADAPT combines learned pattern guidance with enumeration, unlike prior systems whose division of labor is fixed.Neural methods explore fewer candidates at higher per-candidate cost, whereas enumeration efficiently handles portions that are difficult to recognize.Source: §4.2 · p. 4, Figure 1 · p. 4

4.3. Training

• Training uses sampled timeouts and a minimal qualifying sketch, maximizing the probability of the easiest sketch that solves each task within that timeout.An exponential timeout distribution supplies a range of sketch sizes during training.Source: §4.3 · pp. 4–5

List Processing

• With a beam size of 100, SKETCHADAPT reaches high accuracy on length-3 list programs with much less enumeration and remains comparable on length-4 programs while exceeding the generator-only RNN.Figure 2 varies enumeration budget for models trained on length-3 programs and evaluates generalization on length-4 programs.Source: Figure 2 · p. 6, §5.1 · p. 6

String Transformations

• SKETCHADAPT achieves higher accuracy than RobustFill on the string-editing tasks, despite RobustFill being developed specifically for string editing.The evaluation uses 48 SyGuS programs and 79 programs from Ellis et al. (2018), with training performed only on synthetic DSL samples.Source: Figure 3 · p. 6, §5.2 · p. 7

List Processing

• SKETCHADAPT is the only list-processing system reported to perform well on both familiar length-3 programs and out-of-sample length-4 programs.The generator-only RNN performs poorly on length-4 programs, while the synthesizer-only model needs a large enumeration budget and is slow on familiar programs.Source: §5.1 · pp. 6–7

String Transformations

• The larger string-editing DSL makes enumeration slower and less effective, preventing the synthesizer-only model from consistently generating sufficiently complex programs from scratch.This domain therefore tests whether learned sketches can reduce reliance on exhaustive search when the search space is large.Source: §5.2 · p. 7

AlgoLisp: Description to Programs

• On AlgoLisp, SKETCHADAPT and the generator-only RNN achieve near-perfect accuracy on the full dataset, while SKETCHADAPT significantly outperforms the RNN when training data is reduced.With beam size 10 and a 300-second timeout, the synthesizer-only model cannot achieve high performance; the reported results attribute stronger low-data generalization to symbolic search.Source: §5.3 · p. 8
• SKETCHADAPT shows strong generalization to unseen ‘even’ and ‘odd’ programs in the AlgoLisp evaluation.This evaluates models trained after excluding programs containing ‘odd’ and tests them on programs containing ‘odd’ and ‘even’.Source: §5.3 · p. 8

• Recent systems combine learned pattern recognition with explicit reasoning through program sketches, converting neural sketch predictions into full programs using symbolic synthesis.Source: §6 · p. 8

• SKETCHADAPT dynamically adapts sketch specificity, recognizing common motifs like pure RNNs while matching or exceeding symbolic synthesis generalization.Source: §7 · p. 8
• The authors hypothesize that learned integration of different computations may also benefit planning, rapid language learning, and sophisticated question answering.Source: §7 · p. 8

• The generator is an attention-based sequence-to-sequence model with a learned grammar mask that suppresses grammatically invalid program sequences.Source: A. Architecture Details · p. 11
• For AlgoLisp, the generator encodes natural-language descriptions rather than input-output examples, using an attention-based LSTM with grammar masking.Source: A. Architecture Details · p. 11
• HOLE is represented as an additional DSL token, and sampled sketches are converted into token sequences for the generator.Source: A. Architecture Details · p. 11
• The recognizer encodes each input-output example with an LSTM, averages the resulting vectors, and predicts production probabilities through an MLP.Source: A. Architecture Details · p. 11
• The recognizer differs from DeepCoder’s feedforward encoder but serves the same role of guiding symbolic enumerative search over programs.Source: A. Architecture Details · p. 11
• For AlgoLisp, the recognizer encodes the single natural-language specification, while examples remain available to the synthesizer for candidate verification.Source: A. Architecture Details · p. 11

• The models were implemented in PyTorch and trained with Adam at learning rate 0.001, using distinct embedding, hidden-size, and MLP configurations.Source: B. Experimental details · p. 11
• The benchmark programs come from Balog et al. (2016), were pruned for redundancy or invalid behavior, and converted into λ-calculus form.Source: §B.1 · p. 11
• Input-output examples were generated by sampling inputs and executing programs, with heuristic constraint propagation preventing invalid or out-of-range executions.Source: §B.1 · p. 11
• Sketch generators were pretrained on full programs for 10 epochs and then trained on the sketch objective for 10 more, while recognizers trained for 50 epochs.Source: §B.1 · p. 11
• Sketch Generator models had approximately 7 million parameters, compared with about 230,000 parameters for Recognizer models.Source: §B.1 · p. 11

B.2. String Transformations

• The string-transformation DSL extends Devlin et al. (2017) with constructs for lists and union types required by the strongly typed λ-calculus enumerator.Added tokens include concat list, concat1, expr n, and delimiter to regex.Source: §B.2 · p. 11
• The Generator and Recognizer networks were trained on 250,000 randomly sampled DSL programs, with batch size 50 for the sketch Generator.Source: §B.2 · p. 12
• Evaluation tasks were filtered to retain only cases whose reference programs satisfy the input-output specifications.The same filtering rule is stated for the test and development datasets.Source: §B.3 · p. 12
• AlgoLisp experiments used batch size 32 and trained until development loss stopped decreasing, with at least 1250 training iterations.Source: §B.3 · p. 12

Noisy Specifications

• The noisy-specification experiment injects insertion, deletion, or substitution errors and measures satisfying at least three of four test examples when one example is corrupted.The experiment is conducted in the string-editing domain, where user input can be noisy.Source: C. Additional Experimental Analysis · p. 12

IO-Only Ablation

• An IO-only Algolisp ablation conditions the Generator and Recognizer on input-output examples instead of natural-language descriptions.The supplied passage introduces Table 6 as reporting this ablation but does not provide its numerical outcomes.Source: C. Additional Experimental Analysis · p. 12

Evaluation Runtime

• SKETCHADAPT’s Algolisp solve times are not significantly slower than the RNN “Generator only” baseline despite combining neural beam search with enumerative search.The “Synthesizer only” baseline is faster because it solves only a small proportion of programs.Source: C. Additional Experimental Analysis · p. 12, Table 7 · p. 13

Breakdown of Results

• Across all domains, a large proportion of problems are solved by SKETCHADAPT but not by the strongest baseline, whereas far fewer are solved only by the baseline.Source: C. Additional Experimental Analysis · p. 12

Qualitative Examples

• Figures 5–7 provide examples of list-processing, text-editing, and AlgoLisp programs solved by SKETCHADAPT but not by the strongest baseline.The examples include learned sketches with instantiated holes for operations such as filtering, substring extraction, and maximum computation.Source: C. Additional Experimental Analysis · p. 12, Figure 5 · p. 14, Figure 6 · p. 15