PaperlayerView exact revision on arXiv

Source-linked AI summary

RobustFill: Neural Program Learning under Noisy I/O

Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, Pushmeet Kohli

arXiv:1703.07469v1cs.AI

TL;DR

The paper addresses how neural systems should learn programs or outputs from I/O examples in realistic string-transformation tasks. It develops an attentional-RNN-based synthesis system and directly compares synthesis, induction, and rule-based approaches. The synthesis model reaches 92% accuracy, remains robust to noisy examples, and the comparison shows that approach strengths depend on evaluation conditions.

  • Problem

    The work addresses limited direct evidence comparing neural program synthesis and induction on a large real-world task, alongside rule-based synthesis under noisy I/O examples.

  • Method

    The paper uses modified attentional RNNs to encode variable-sized I/O-example sets and generates either programs in a string-transformation DSL or output strings directly.

  • Results

    92% accuracy on a real-world FlashFill test set matches a hand-engineered system and exceeds the previous-best neural synthesis model by 58%.

  • Takeaways & Limitations

    Synthesis performs better on this task, while synthesis and induction each have strengths under different evaluation metrics and decoding constraints.

  • Takeaways & Limitations

    A richer DSL representation increased the search space by 10x, and hierarchical representation was not retained because its value did not justify computational cost.

Abstract

from arXiv · show

The problem of automatically generating a computer program from some specification has been studied since the early days of AI. Recently, two competing approaches for automatic program learning have received significant attention: (1) neural program synthesis, where a neural network is conditioned on input/output (I/O) examples and learns to generate a program, and (2) neural program induction, where a neural network generates new outputs directly using a latent program representation. Here, for the first time, we directly compare both approaches on a large-scale, real-world learning task. We additionally contrast to rule-based program synthesis, which uses hand-crafted semantics to guide the program generation. Our neural models use a modified attention RNN to allow encoding of variable-sized sets of I/O pairs. Our best synthesis model achieves 92% accuracy on a real-world test set, compared to the 34% accuracy of the previous best neural synthesis approach. The synthesis model also outperforms a comparable induction model on this task, but we more importantly demonstrate that the strength of each approach is highly dependent on the evaluation metric and end-user application. Finally, we show that we can train our neural models to remain very robust to the type of noise expected in real-world data (e.g., typos), while a highly-engineered rule-based system fails entirely.

1. Introduction

RobustFill examines neural program synthesis and induction for noisy, real-world string transformations, directly comparing them with rule-based synthesis. It introduces a neural architecture for variable-sized I/O example sets and reports stronger accuracy and noise robustness than prior statistical and hand-engineered approaches.

  • Program learning generates programs from specifications, but hand-engineered synthesis systems are difficult to extend and fragile to noise.
  • The paper directly contrasts neural program synthesis, which generates programs from I/O examples, with neural induction, which generates outputs using a latent program representation.
  • FlashFill-style string transformation lets users provide a few output examples while the system generates outputs for remaining input strings.
  • The models use modified attentional RNNs to encode variable-sized sets of I/O examples and generate either a DSL program or an output string.
  • 92% accuracy on 205 real-world FlashFill instances substantially exceeds the previous best statistical system’s 34% accuracy.
  • With noise, the model achieves 80% accuracy versus 6% for the comparable clean-data-performing system, while neural and induction approaches show different metric-dependent strengths.

2. Related Work

Related work spans neural induction, neural synthesis, and DSL-based rule-guided synthesis. RobustFill differs by learning an end-to-end synthesis algorithm rather than relying on hand-coded search guidance.

  • Neural Program Induction: Neural program induction uses latent memory or controller representations to generate outputs for algorithmic tasks.
  • Neural Program Synthesis: Neural program synthesis generates or searches for programs from examples, with RobustFill performing end-to-end synthesis unlike DeepCoder’s externally augmented search.
  • DSL-based synthesis: DSL-based synthesis exploits operator independence with divide-and-conquer search, hand-crafted pruning, and ranking heuristics.
  • DSL-based synthesis: RobustFill presents a neural architecture that automatically learns an efficient synthesis algorithm, unlike approaches requiring hand-coded textual features.

3. Problem Overview

The task asks a system to generalize string transformations from observed I/O examples to assessment inputs, either by synthesizing a program or directly inducing outputs. RobustFill uses a rich DSL and evaluates exact generalization on real-world FlashFill instances.

  • 3.1. Problem Formulation: Given observed I/O pairs and unpaired assessment inputs, the system must generate the corresponding assessment output strings.
  • 3.1. Problem Formulation: Each instance assumes at least one program correctly transforms all observed and assessment examples, although multiple valid programs may exist.
  • 3.1. Problem Formulation: Synthesis generates a DSL program token-by-token and can execute candidates on observed inputs to check consistency before searching further.
  • 3.1. Problem Formulation: Consistency on observed examples is necessary but does not guarantee generalization to new assessment examples.
  • 3.1. Problem Formulation: Induction generates assessment outputs character-by-character from observed examples and the assessment input, without explicitly using program P.
  • 3.1. Problem Formulation: Generalization accuracy requires every assessment output to be exactly correct; evaluation typically uses four observed and six assessment examples.
  • 3.2. The Domain Specific Language: The DSL represents string transformations through substring extraction, conversions, constants, nested expressions, and regex-based extraction.
  • 3.2. The Domain Specific Language: Approximately 30 million unique string expressions make pruning essential because black-box search must otherwise examine many candidates.

4. Program Synthesis Model Architecture

The model treats program synthesis as sequence-to-sequence generation, encoding I/O examples with recurrent networks and generating program tokens sequentially. Its architecture evolves from basic encoding toward attention, double attention, bidirectional processing, and late pooling for unordered variable-sized example sets.

  • Single-Example Representation: Program synthesis is formulated as sequence-to-sequence generation, with RNNs encoding observed I/O and another RNN generating the program token by token.The program is represented as a sequential output rather than a hierarchical RNN.
  • Single-Example Representation: The study explores four increasingly complex architectures: Basic Seq-to-Seq, Attention-A, Attention-B, and Attention-C.The variants progressively introduce attention, double attention, and bidirectional LSTMs.
  • Double Attention: Attention-A lets the output representation attend to the input, while Attention-B adds simultaneous attention to both output and input representations.In Attention-A, O attends to I and P attends to O; Attention-B gives P double attention to O and I.
  • Implementation: The implementation uses character-level I/O representations and source-code-order program tokens, with 95 printable ASCII tokens for strings and 430 program tokens.Training uses 512-unit recurrent and fully connected layers, 128-dimensional embeddings, SGD with gradient clipping, and 2 million minibatch updates.
  • Double Attention: Double attention computes attention over two vector sets using the previous recurrent state and current input, with the first attention influencing computation of the second.The paper specifies S, h_i−1, and x_i as the attended vectors, previous state, and current input; in the double-attention setup, S_A is O and S_B is I.
  • Multi-Example Pooling: Because test instances contain unordered, variable numbers of I/O examples, the model uses late pooling across example-specific hidden states at each timestep.Each example has separate I, O, and P layers with shared weights; pooled P states feed one output softmax layer.
  • Multi-Example Pooling: The pooling and output layers apply max pooling after a learned transformation, then softmax over the program vocabulary.The pooled representation is m_i, and y_i is the softmax output over v program tokens.

5. Program Synthesis Results

The synthesis results show that attention-based architectures and constrained decoding substantially improve generalization, with the best model reaching 92% accuracy. Generalization rises with more observed examples, while consistency and decoder behavior reveal remaining limitations.

  • Consistency vs. Generalization: Generalization accuracy requires a consistent program that produces exactly correct outputs for all six assessment examples.The reported percentage is the proportion of test instances meeting both conditions.
  • Architecture and Decoding: 25% absolute improvement separates all attentional variants from the basic seq-to-seq model.Attention-B and Attention-C add roughly 2–5% absolute accuracy, while DP-Beam adds roughly 5%.
  • Generalization Results: 92% accuracy is achieved by Attention-C-DP with Beam=1000 on the synthesis task.Attention-C-DP with Beam=100 reaches 89% accuracy at roughly 0.3 seconds per test instance.
  • Comparison to Past Work: The stronger accuracy improvement over prior statistical synthesis is attributed to late pooling, attention mechanisms, and a more expressive DSL.GetSpan() was required for approximately 20% of test instances, while the expanded DSL increased the search space tenfold.
  • Consistency vs. Generalization: Generalization accuracy increases as the number of observed I/O examples increases.Figure 5 reports results across beam sizes and numbers of observed examples using Attention-C.
  • Consistency vs. Generalization: Beam=1 produces consistent output for roughly 50% of instances, indicating that learned latent function semantics remain imperfect.Consistency stays relatively constant as the number of observed examples increases.

6. Program Induction Results

Program induction generates outputs directly rather than synthesizing an executable program, whereas synthesis generates a program and selects candidates using consistency. Under strict all-example accuracy, synthesis outperforms induction, while average-example accuracy favors induction relatively because outputs are decoded independently.

  • Model Differences: Induction generates each output string directly, while synthesis generates a program executed by the DSL to produce the output.Induction does not use the program P and instead predicts the output character-by-character.
  • Comparison of Induction and Synthesis Models: 53% induction accuracy compares with 81% for synthesis under strict all-example generalization accuracy.All six assessment examples must be exactly correct; synthesis uses Beam=100, while induction uses Beam=3.
  • Decoding and Consistency: Induction cannot improve through larger search because decoded candidates cannot be evaluated for consistency.Synthesis evaluates k-best program candidates one-by-one and selects the first consistent program.
  • Average-Example Accuracy: Average-example accuracy credits the proportion of assessment examples that are exactly correct across test instances.Unlike all-example accuracy, this metric gives partial credit when, for example, five of six assessment examples are correct.
  • Average-Example Accuracy: 33% of induction test instances are partially correct, compared with less than 10% for both synthesis conditions.Independent decoding gives induction a higher chance of getting some assessment examples correct, although synthesis still leads in absolute performance by 10%.
  • Metric Choice: The preferred metric depends on the downstream application: all-example accuracy suits complete spreadsheet columns, whereas average-example accuracy suits per-cell autocomplete.The paper states that neither metric should universally receive more credence.

7. Handling Noisy I/O Examples

The study evaluates robustness to noisy I/O examples by injecting simulated typos into FlashFill inputs and comparing neural models with Excel FlashFill. Neural models degrade gradually, whereas the rule-based system fails under minimal noise.

  • Noise was synthetically injected into observed input or output strings using random character insertions, deletions, and substitutions.Assessment examples remained clean so evaluation stayed possible.
  • Neural models degraded by approximately 2% absolute accuracy for each noise character introduced.
  • 92% accuracy: Excel FlashFill matched the best reported result without noise.FlashFill’s implementation was evaluated using Microsoft Excel 2016.
  • One or two noise characters effectively broke Excel FlashFill, whose algorithm relies critically on exact string matching.

8. Conclusions

The paper concludes that its neural synthesis model performs strongly on a real-world Programming By Example task and remains robust to moderate I/O noise. Comparing synthesis and induction shows that their relative strengths depend on the evaluation condition.

  • 92% accuracy: the neural synthesis model matched the hand-engineered system on a real-world Programming By Example task.
  • 58%: the neural synthesis model outperformed the previous-best neural synthesis model by this margin.
  • Neural models remained robust to moderate I/O noise, while the hand-engineered system failed under even small amounts of noise.
  • Synthesis performed better on this task, but induction had strength under evaluation conditions emphasizing the number of correct outputs.Synthesis had an advantage when all outputs needed to be correct.

Supplementary Material

The supplementary material specifies the DSL’s string-transformation semantics and explains how programs are represented and executed. Its operators extract, transform, combine, and compose substrings from an input string.

  • The DSL grammar defines the space of possible programs and supports straightforward program sampling.
  • The DSL maps an input string v to an output string produced by the Concat operator.
  • Concat combines the evaluated outputs of multiple expressions into one string.
  • Constants and nested function calls provide fixed strings and composition of transformations within the DSL.Nested calls are flattened into single tokens for selected nesting functions during implementation.
  • GetToken, GetFrom, GetUpto, GetSpan, GetFirst, and GetAll extract token, substring, span, or matched-string content from v.

B. Synthetic Evaluation Details

Synthetic experiments use programs sampled from the DSL, but the paper emphasizes real-world evaluation because synthetic difficulty depends on the generation procedure. Synthetic validation accuracy nevertheless tracks performance on the FlashFill dataset.

  • Synthetic results are largely omitted because generation procedures can make the dataset arbitrarily easy or difficult.The external real-world dataset is used to verify that learned semantics cover programs observed in real data.
  • Programs were randomly generated from the DSL with up to 10 expressions, with heuristics restricting inputs to those producing non-empty outputs.
  • Synthetic validation accuracy was generally consistent with FlashFill accuracy, with stronger synthetic models also performing better on real-world data.
  • Figure 10 reports model accuracy on the synthetically generated validation set.
  • Hand-selected FlashFill examples illustrate limitations involving underconstrained examples and irregular formatting that can prevent generalization.

D. Induction Network Architecture

The program induction architecture modifies synthesis Attention-A with double attention and an additional LSTM for encoding input examples. Figures illustrate the architecture, sampled examples, test predictions, and incorrect outputs.

  • Architecture: The induction network uses double attention to jointly attend to Ix and Oj, plus an LSTM to encode Ix.This architecture is described as a modification of synthesis Attention-A.
  • Architecture: Figure 11 depicts the induction network architecture, where dotted connections indicate that one variable attends to another.The figure provides the complete architectural diagram.
  • Training examples: Figure 12 shows randomly sampled training programs with corresponding input-output examples, including multiline examples split at spaces.
  • Test examples: Figure 13 presents FlashFill test examples with input strings, output strings, and execution results from predicted programs.Long strings are visually broken or hyphenated for readability, without changing the examples.
  • Prediction errors: Figure 14 shows incorrect FlashFill predictions, including inconsistent programs and consistent programs that fail to generalize.
Loading 1703.07469v1…