COMS 3997 · Neurosymbolic AI · Week 3

RobustFill

Neural Program Learning under Noisy I/O

Devlin, Uesato, Bhupatiraju, Singh, Mohamed, Kohli · ICML 2017

Input	Output
john Smith	Smith, Jhn
DOUG Q. Macklin	Macklin, Doug
Frank Lee (123)	LEe, Frank
Laura Jane Jones	Jones, Laura
Steve P. Green (9)	Green, Steve

Figure 1 of the paper: the user's outputs contain typos (“Jhn”, “LEe”). The last row should still come out right.

The problem

Two ways to learn string programs, each lacking

Rule-based (FlashFill)

Hand-crafted operator semantics, pruning and ranking. Accurate on clean examples.

But: “difficult to extend and fragile to noise”. Its efficiency rests on exact string matching.

Neural (before this paper)

Learned from data, so in principle extensible and tolerant of noise.

But: the best prior model (Parisotto et al., 2017) solved only 34% of real FlashFill tasks.

RobustFill · Devlin et al., ICML 2017

2

Where this comes from

From FlashFill to a neural FlashFill

2011

FlashFill

Version spaces over a string DSL (POPL)

2013

Flash Fill in Excel

Ships in Excel 2013: program synthesis behind a single keystroke

2015

FlashMeta / PROSE

The same idea for any DSL (Polozov and Gulwani, OOPSLA)

2017

RobustFill

A neural model on a FlashFill-style DSL, tolerating noisy examples (ICML). This paper.

RobustFill · Devlin et al., ICML 2017

3

The one idea to remember

Learn the search. Let execution check it.

A network trained on hundreds of millions of random programs proposes a beam of candidates. Running each one on the examples keeps only the consistent ones. Noise becomes something to train on, not something that empties the search.

Side by side

Same task, opposite machinery

	FlashFill (2011)	RobustFill (2017)
Search	Version-space algebra: every consistent program, as DAGs; intersect	Beam search from a learned model
Prior	Hand-written ranking (Occam's razor)	Learned from 256M random programs
Consistency	Guaranteed by construction	Checked by executing each candidate
Noise	Exact matching; one heuristic flags a single odd example as a likely typo	Trained on noisy examples; pick by edit distance
Engineering	Inverse semantics for every operator	A DSL interpreter plus a random program generator

RobustFill · Devlin et al., ICML 2017

5

This is the contrast to keep in mind for the rest of the talk. Both systems solve the same PBE problem over a similar DSL. FlashFill's guarantees come from exact reasoning, and so does its brittleness. We give up the guarantee that every consistent program was considered, but we get robustness and extensibility: to add an operator, you add it to the interpreter and the generator, and you don't write its inverse. FlashFill isn't defenceless against noise. Its Section 5.2 says that when the classifier fails, it drops a singleton partition, treats that example as a likely typo and asks the user (the "Kimberley" vs "Kimberly" example). That's a heuristic for one bad example, though, not robustness learned from data. Our noise handling is Section 7: train with synthetic character edits, and select the best program by character edit rate instead of exact match.

The language

A FlashFill-style DSL, with nesting and regex spans

p := Concat(e1, e2, e3, …)
e := f | n | n1(n2) | n(f) | ConstStr(c)
f := SubStr(k1, k2)
   | GetSpan(r1, i1, y1, r2, i2, y2)
n := GetToken(t, i) | ToCase(s)
   | Replace(δ1, δ2) | Trim()
   | GetUpto(r) | GetFrom(r)
   | GetFirst(t, i) | GetAll(t)

~30M

unique expressions e, concatenated into programs of any length

~20%

of test tasks need GetSpan, which grew the search space 10×

RobustFill · Devlin et al., ICML 2017 · Figure 2, Sections 3.2 and 5.1

6

Synthesis, with induction as the baseline

RobustFill writes programs, not answers

Synthesis: this is RobustFill (Sections 4, 5 and 7)

4 I/O examples

Neural net

A DSL program P

Interpreter runs P on new rows

For example, P = GetToken(Alpha, −1) | “, ” | ToCase(Proper, GetToken(Alpha, 1)). The net is probabilistic and proposes candidates; P is an ordinary deterministic program: same input, same output, every time. It can be checked against the examples, read and reused.

Induction: a baseline the paper also trains, for comparison only (Section 6)

4 I/O examples + a new input

Neural net

no program in between

The output string, char by char

Everything from here on (architecture, beam search, results, noise) is the synthesis model. Only slide 11 brings induction back, to ask whether writing a program is worth it.

RobustFill · Devlin et al., ICML 2017 · Sections 3.1 and 6

7

Students often mix these up, so say it plainly: RobustFill is a program synthesizer. The neural network is a proposal mechanism. Beam search over it yields candidate programs in the DSL, and each candidate is an ordinary deterministic program that a normal interpreter runs. That's how RobustFill checks candidates against the observed examples, and how the final answer can be read and reused. The randomness lives only in the proposer, never in the program. The example program is the one in Figure 1 of the paper. Induction is the road not taken. The same kind of network is trained to emit the output string directly, one character at a time, with the program left implicit in its weights. The paper builds it only to compare (Section 6): 81% for synthesis vs. 53% for induction on all-examples-correct, although induction gets partial credit more often. Evaluation for both: a test task shows 4 examples and holds out 6, and it counts only if all 6 held-out outputs are exactly right.

Architecture

Attention per example, pooled at every step

Output softmax → next program token

FC + MaxPool across examples

P1 · program

P2 · program

Pn · program

O1 · output

O2 · output

On · output

I1 · input

I2 · input

In · input

Weights shared across examples. The P layers' hidden states are max-pooled at every step.

Variant	What it adds
Basic Seq-to-Seq	LSTMs, no attention
Attention-A	O attends to I; P attends to O
Attention-B	P attends to O and I (double attention)
Attention-C	B, with bidirectional I and O encoders

RobustFill · Devlin et al., ICML 2017 · Section 4

8

Decoding

The network proposes, the interpreter disposes

Beam search: the k best programs

→

Run each on the 4 observed inputs

→

Keep the highest-scoring consistent one

DP-Beam

Each time an expression is completed, execute the partial program. If its output isn't a prefix of the target output, drop it from the beam. This works because the DSL is concatenative.

~0.3 s

per task on a Titan X GPU (Attention-C-DP, beam 100: 89%)

RobustFill · Devlin et al., ICML 2017 · Section 5

9

Results on FlashFillTest

Attention and pruning take neural synthesis from 34% to 92%

System	Beam 100	Beam 1000
Parisotto et al. (2017)	23%	34%
Basic Seq-to-Seq	51%	56%
Attention-C	83%	86%
Attention-C-DP	89%	92%

205 real tasks from Excel spreadsheets, supplied by the FlashFill and Parisotto authors.

Attention alone adds roughly 25 points over the basic model.

RobustFill · Devlin et al., ICML 2017 · Sections 3.3 and 5.1

10

Synthesis vs. induction

Which approach wins depends on the metric

81%

synthesis (Attention-A, beam 100). All or nothing: under 10% of tasks partly right.

53%

induction, same architecture. 33% of tasks partly right, since each output is decoded separately.

Fill a whole column: prefer synthesis. When it answers, every row is right.

Per-cell autocomplete: induction's partial credit counts for more.

RobustFill · Devlin et al., ICML 2017 · Section 6

11

Noisy examples

Equal on clean data; far apart once there are typos

92%

Excel FlashFill with no noise, matching our best model

80%

RobustFill with noise; about 2 points lost per noisy character

6%

Excel FlashFill with noise: “effectively broken” after 1–2 characters

Noise = random character insertions, deletions and substitutions in the observed examples. RobustFill trains on the same kind of noise and picks the program with the lowest edit distance to the examples.

RobustFill · Devlin et al., ICML 2017 · Section 1 and Section 7

12

This is the headline result. The 80% vs 6% comparison is from our contributions list in Section 1. Section 7 and Figure 8 show the curve: the neural models degrade by about 2 points absolute per noise character, while Excel FlashFill is "effectively broken" with just one or two characters of noise. That's expected, because its algorithm is built around exact string matching. Its only noise defence is a heuristic that flags one example it can't classify as a likely typo (FlashFill Section 5.2), and that doesn't cover typos scattered across several examples. Only two changes were needed: inject noise into the training data (this didn't hurt clean accuracy, footnote 9), and select P* by character edit rate instead of exact match. The Excel numbers come from a macro in Excel 2016. Be upfront about footnote 11: FlashFill was manually developed on this exact test set, so its clean 92% is on its home turf.

Champion · the case for a best paper award

Why this paper matters beyond its benchmark

Neural synthesis that works

92% on 205 real spreadsheet tasks, up from 34% for the best earlier neural model, and on par with FlashFill on clean data.

No hand-written inverses

To add an operator, add it to the interpreter and the random generator. Typos become something you train on: 80% vs 6% with noise.

What I'd build on it

The template of a neural proposer with a symbolic checker. Next week, DeepCoder uses a network to guide a symbolic search instead of replacing it.

Conceded up front: the training programs and the noise are synthetic

Both come from generators the authors wrote, and the noise at test time has the same form as in training. That doesn't sink it: the headline accuracy is measured on 205 real tasks, and the core claim, that a learned proposer checked by execution rivals a hand-built synthesizer, is tested there.

RobustFill · Devlin et al., ICML 2017

13

Critic · Reviewer 2, recommends reject

Claims the evidence does not yet support

Concern	An experiment that would test it
The noise is synthetic, uniform character edits, matched to training	Evaluate on real user typos, and on noise types the model never trained on.
FlashFill's noise defence is one heuristic for a single odd example	Compare against a version-space algebra with approximate matching, or leave-one-example-out voting.
Beam 1 is consistent only ~50% of the time, so search does much of the work	Give an enumerative synthesizer with DP pruning the same time budget, and compare.
Random programs on random ASCII strings	Test how accuracy changes as inputs drift from the generator's distribution.

The one experiment that would change my score: Test on real user typos against a FlashFill that also selects programs by edit distance, with an equal compute budget.

RobustFill · Devlin et al., ICML 2017

14

Discussion

What would we have to believe?

1

RobustFill still needs the DSL to generate its training data and to check its answers. Is it neural, or neurosymbolic?

2

Synthesis wins on all-or-nothing accuracy; induction earns partial credit. Which matches what users want?

3

Could one system have FlashFill's guarantees and RobustFill's tolerance for typos? What would it look like?