Generating Pragmatic Examples to Train Neural Program Synthesizers
Authors: Saujas Vaduguru
Daniel Fried
Yewen Pu
Venue: ICLR 2024 poster (2024)
Keywords: program synthesis
pragmatics
self-play
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
TL;DR: Pragmatic program synthesis in a realistic program space without human supervision in training

Abstract: Programming-by-example is the task of synthesizing a program that is consistent with a set of user-provided input-output examples. 
As examples are often an under-specification of one's intent, a good synthesizer must choose the intended program from the many that are consistent with the given set of examples. Prior work frames program synthesis as a cooperative game between a listener (that synthesizes programs) and a speaker (a user choosing examples), and shows that models of computational pragmatic inference are effective in choosing the user intended programs. However, these models require counterfactual reasoning over a large set of programs and examples, which is infeasible in realistic program spaces. In this paper, we propose PraX, a novel way to amortize this search with neural networks. We sample pairs of programs and examples via self-play between listener and speaker models, and use pragmatic inference to choose informative training examples from this sample. We then use the informative dataset to train models to improve the synthesizer's ability to disambiguate user-provided examples _without human supervision_. We validate PraX on the challenging task of synthesizing regular expressions from example strings, and find that our method (1) outperforms models trained without choosing pragmatic examples by 23% (a 51% relative increase) (2) matches the performance of supervised learning on a dataset of pragmatic examples provided by humans, despite using no human data in training.

Published as a conference paper at ICLR 2024
GENERATING PRAGMATIC EXAMPLES TO TRAIN NEURAL PROGRAM S SYNTHESIZERS
Saujas Vaduguru Carnegie Mellon University svadugurêcs. cmu.edu
Daniel Fried Carnegie Mellon University dfriedθcs. cmu.
Yewen Pu Autodesk Research
y peeen.pp@uuoooeskcco
ABSTRACT
the task of synthesizing a program that consis- tent with set of user- eser-provided input-output examples. As examples often under-specifiiation of one's intent, a good synthesizer must choose the intended program from the many that are consistent with the given set of examples. Prior work frames program synthesis as cooperative game between a listener (that synthesizes programs) and a speaker (a user choosing examples), and shows that models of computational pragmatic inference are effective in choosing the user intended programs. However, these models require counterfactual reasoning over a large set of programs and examples, which is infeasible in realistic program spaces. In this paper. we propose PRAX, a novel way to amortize this search with neural networks. We sample pairs of programs and examples via self-play between listener and speaker models, and use pragmatic inference to choose infor- mative training examples from this sample. We then use the informative dataset to train models to improve the synthesizer's 's ability to disambiguate user-provided examples without human supervision. We validate PRAX on the challenging task of synthesizing regular expressions from example strings, and find that our method (1) outperforms models trained without choosing pragmatic examples by 23% (a 51% relative increase) (2) matches the performance of supervised learning on a dataset of pragmatic examples provided by humans, despite using human data in training.
gerramminn--y-examipie
INTRODUCTION
In program synthesis specifically programming-by example-PPBE) user describes a target program using input-output examples (i.e. test cases) and the synthesizer finds a program that is consistent with these input-output examples. In PBE, the users directly express the semantics of the intended program (what should do) without having to understand the syntax of the program (what it should look like). Such systems have found real-wordf
in variety of scenarios such as spreadsheet formulas (Chen et al. 2021 Gulwani 2011) and data wrangling (Feng et al.) 2018).
An important aspect of inferring programs from examples is dealing with ambiguity. Given set of examples, there can be many spurious programs consistent with the set, and picking out the right one the user has in mind is a long-standing challenge. For example, when describing the regular expression a+b*[] [1] an informative user might provide the example (ab, v) indicating that the string ab matches the target regular expression. However, to the program synthesizer, both atb* and a*b+c? would be among many acceptable answers based on this example.
Pu al. (2020) resolves this ambiguity by framing program synthesis as a coorporative communica- tive game: the user chooses an informative set of examples to convey the program to the synthesizer, and the synthesizer chooses program under the assumption that these examples were chosen infor- matively. Models of pragmatic inference, specifically, the Rational Speech Acts (RSA) framework (Frnkk & Goodman 2012) can then be used to build program synthesizer that can resolve ambi- guity via recursive Bayesian inference. The RSA framework allows the synthesizer to reason about
I1 or more as followed by 0 or more bs ?c? means optionally having at the end.

---

Published as a conference paper at ICLR 2024
Generate dataset D, informative spediiicatins for programs
Update speaker and listener models using Dr
add example SPEC
Speaker, ?b
Listener, .8
De PROGRAM SPEC
Speaker .+3 Ab
SPEC [(ab./9]
>laab, +
[aa, v/
Listener, A
*labó, M
Speaker,_ 20
Rational Speech Acts
P;:
>>aa,
Ustener +41
PROGRAM
latbA
18
Repest rounds 0, 1,...
Dr (PRROGRAM sibe, SPEC [[ab, Valaa 2 -1))
PRAX iteratively generates datasets containing increasingly informative program spec- ifications (lists examples consistent with the program), and updates models on the generated datasets. ! We use Speaker model - that generates example consistent with target PRO- GRAM- - to propose a set candidate specifications. Using the Rational Speech Acts model of pragmatic reasoning (red box; described in in Figure 2 we choose the example that is most infor- mative to a Listener model that synthesizes programs consistent with a given specification. manner, incrementally build the list of examples SPEC for the PROGRAM. We repeat this for different programs to create a dataset of informative PROGRAM-SPEC pairs. ? We use the dataset update the Speaker and Listener models. We train the speaker generate the selected pragmatic examples, and the listener to synthesize the target program given the generated examples.
Figure 1:
this
what program user intended, given that they chose that particular set of examples rather than a different one. For example, the synthesizer could reason that user that wanted to describe axb+c? would have chosen an example containing the character C. However, this approach requires the syn- thesizer perform expensive counterfactual inference over the space of all programs and examples to resolve ambiguity, making it difficult to scale to realistic programming domains.
To scale to realistic program spaces, modern approaches of PBE systems have relied on training neural networks to efficiently search through large program spaces for consistent programs given examples (Balog et al. 2017: Devlin et al. 2017). In this paper, we explore whether we can use sim- ulated reasoning in communication games using the RSA framework as way to generate training data consisting of pragmatic examples. The generated data is then used to train neural networks to enable scaleable pragmatic program synthesis. We dub this approach PRAX. We hypothesize that since the RSA framework computationally models how a human chooses examples to communicate program, end users would succeed more often when communicating with neural synthesizer trained on pragmatic data (our work) as compared to a neural synthesizer trained on non-pragmatic data (Balog al. 2017 Devlin et al. 2017).
An overview of PRAX is shown in Figure We start with a neural literal listener - a synthesizer trained in the style of Devlin al. (2017) and neural literal speaker that generates examples consistent with a given program. We generate a sequence of pragmatic examples incrementally to obtain training pair (program, am, examples). This pair then added to an aggregate training set, which is used to finetune both the speaker model making it more likely to generate pragmatic examples and the listener model making it more likely recover the intended program given pragmatic examples.
We validate the effectiveness of PRAX on the well-studied PBE task of inferring regular expressions from a set of examples. Each example is pair (string, bool), indicating whether particular string matches the regex. To compare our training algorithm to standard supervised learning from human- annotated data, we collect novel dataset of human annotations, consisting of (program am, examples) where the examples were given by person for total of 440 regular expressions. We find that with only a small number (40) of human annotations used only for model selection able to outperform a system that is fine-tuned using 400 annotated regexes from this dataset. We conduct human evaluation of PRAX by giving user target regex communicate interactively to
method is
2

---

Published as a conference paper at ICLR 2024
a+b+
a7b7
arbs
arbrcc
Leg
a+bb
o7b7
arbe
arbicc
S
arbce
97b7
arbe
arbic7
V
(aab, v/>
(aad, v/ (abe, v/
(abà V)
(abb, v
(aa,
(aa, V)
(aa, v/
1b,
(6, X)
(b,
Normalize rows
Normalize colurns
Figure An illustration of how the Rational Speech Acts framework is used to select an informative example for a given program. We start with the matrix corresponding to the consistency relation between the sample programs and examples shown Figure [ We obtain a literal listener distribution Lo over programs for each example by normalizing the rows of this matrix. Since the M matrix is binary, each row in Lo a uniform distribution over consistent programs the sample any of the consistent programs is equally likely be the intended program. We then obtain a pragmatic speaker distribution S1 by normalizing the columns of the Ly matrix: modeling the probability an informative speaker might have for choosing each example when communicating program to a literal listener. RSA outputs the highest-probabilig example S (e.g., (aa, v)) in the column corresponding to the target program (e.g., a+b*).
the synthesizer using examples, and find that the informative examples generated by our procedure substantially improve the performance of regular expression synthesizer, with improvements of 22.8% absolute (51,4% relative) in accuracy (11 participants, 340 regexes total). PRAX, despite not using providdd data during training, matches the performance of of model fine-tuned on large dataset of human-write written pragmatic examples. Our code and data are available at hhtps: 7/gi 7/github. www.cooo/asaaaaaaa
BACKGROUND
Programming-by-Eae Ex-mmll In this paper, we tackle the task finding program E P. where P is space of possible programs. As a specification of intent, a user provides sequence of input- output examples E E+ where E' X y the space of all possible input-output pairs that programs in P operate over. For example, P may be space of regular expression programs, X' the space of all strings the alphabet that the regular expressions are defined over, and E (v.x) where output / indicates whether the input string matches the regular expression. For simplicity of explanation, this section we consider cases where the specification consists single example, deferring the cases of multiple examples the next section.
The semantics of programs are captured by the consistency relation M between and
M (program, example) example (z, v) E X V, program(z) yy
program is consistent with an example iff executing the program on the input produces the tended output. We can view M as consistency matrix where each row corresponds to example, each column corresponds to a program, and an element example and 0 otherwise (Figures and 2 left).
the program consistent with the
Literal model of program synthesis A minimal requirement program synthesizer is that finds any program that is consistent with the given specification. We refer to such synthesizer as the literal listener Lo, which naively assigns equal probability to any consistent program.
Lo (epprogrameexampeee e program) P(program)
((example,
This literal listener distribution given by normalizing the rows of the consistency matrix to produce uniform probability distributions (Lo in Figure 2) However, this literal listener cannot resolve
Here the notation X indicates sequence of elements belonging to X

---

Published as a conference paper at ICLR 2024
ambiguity when interacting with users, it places equal probability on all consistent programs. A literal speaker one that generates any consistent examples for given program defined analogously as (example program) x M (example, program P(examplee))
Pragmatic model of program synthesis When interacting with a synthesizer, users choose exam- ples that are informative those that distinguish the program they desire from others. For example, given the specification ((ab, v),, user is likely wants the regular expression a+b+ than a+b+c?, since they probably would have included the character if they wanted the latter expression.
To leverage the informativity of examples,Puus et (020) use the Rational Speech Acts (RSA: Frank & Goodman 2012) framework to derive a pragmatic program synthesizer that resolves ambiguity by modeling how people choose examples informatively. First, they construct a pragmatic speaker S that chooses an example in proportion to the likelihood that it would make the literal listener infer the intended program:
S1 (eaxmpllelppogrrmm x Loroogrrm example))P(exampe)
(2)
Using a uniform prior P(example), the S1 distribution is given by normalizing the columns of the Lo matrix (S, in Figure 2) As we can see, given a program S₁ selects an example in propor- tion to the likelihood of La recovering the program given the example, choosing examples that are informative the listener
Finally, a pragmatic listener (program synthesizer) I is built on top of St:
Li (program) (xammlle)) x Si (example) P(progra))
(3)
using a prior P(program) over programs. This listener resolves ambiguity by choosing that program that an informative speaker (modeled by Sj) would have described using the chosen example.
Pu al. 2020) demonstrated that building a pragmatic synthesizer L in this way allows for users to cammunicate the target program to the synthesizer using fewer examples without training model on human- produced examples or explicitly defining a prior over the space of programs. However, in realistic domains, enumerating large numbers of programs and examples is intractable, preventing the application of this framework to a broader range of tasks.
METHOD
In this section, we describe the iterative process by which we bootstrap pragmatic neural program synthesizer by generating informative specifications, without human supervision (Figure I]. The full algorithm is detailed in Appendix C
3.1 SPEAKER AND LISTENER MODELS
We build on past work that uses neural models specification-condiiione proposal distri- butions over programs (Balog et al., 2017: Devlin et al.] 2017). Our listener (synthesizer) models represent distributions over programs Lo(programje (emmpeerraexxmmlees). Our speaker (specifica- tion generation) models generate the sequence of examples in specification autoregressively: S& ceneample//pograaae examples ) While all our listener and speaker models share the same architecture and initialization, we vary their training data, as described below.
3.2 TRAINING BASE MODELS
As a foundation for our approach, we train base listener and speaker models to approximate literal speakers and listeners So and La (Equation (T). Since we cannot enumerate the consistency matrix completely and normalize rows, we obtain these approximate models by training on data obtained by randomly sampling an input from the space of inputs X, and executing the program on the input
*For a sequence of examples, Pu 2020 propose factoring the pragmatic speaker distribution autore- gressively as S, (examples) 'ee train the speaker to predict the input-output pair to encourage the model to capture aspects of the domain semantics
= I
S₁ (example papxample/progrran. |program, examples.,)
4

---

Published as a conference paper at ICLR 2024
to obtain the output (e.g., by checking if an sampled example string is matched by sampled regular expression). This lets us generate as many samples from M as we can, which we can use to train base listener to approximate Lo (Equation ( and a base listener to approximate an analogous So. using standard maximum likelihood training. This is essentially the method proposed by Devlin et al. (2017). We denote the resulting base listener model La, and the hase speaker model S and use these as the initial models in our iterative model bootstrapping procedure.
3.3 GENERATING INFORMATIVE EXAMPLES
The crux of our algorithm is using the existing S₂ and Le to approximate S1, which can then be used generate training data improve S& and Le over rounds of training. At each round r of our approach, we use the current speaker and listener models, together with the RSA procedure, to create a dataset of informative examples specifying programs (① of Figure 1.. We incrementally generate examples to create specification. Given a partial specification of examples examples we sam- ple a set of additional candidate examples: S,. (example |program, am, examples Similarly, we sample a set of alternative programs: Lg, (program (eprrrggram/e/apllleee (::) from the partial specification [
We can then compute the sampled consistency matrix over the generated examples and programs, and use RSA inference as shown in Figure 2 proximate S1 distribution!" This example is added to the partial specification, and repeat until a maximum number of examples are reached [ The completed program-specification pair is then added dataset D, of examples from that round of training. This process amounts choosing an example proposed by the current speaker model that minimizes ambiguity among programs that the current listener infers be likely. The full algorithm for incrementally generating sequence of examples is presented in Algorithm] 2 (Appendix
to to choose the highest scoring example from the ap-
3.4 MODEL UPDATES
We use the dataset D, to update both the speaker and listener models as sketched in part @ of Fig- ure D Juiig standard maximum likelihood training. In each round r we further fine-tung tune the speaker and listener models on the generated data to obtain the updated parameters f,+1 and Ør+1- The full algorithm to iteratively generate examples and update the model presented in Algorithm [ (Ap- pendix To select the model that works best with that maximizes a model selection metric computed over a small set of programs paired with human- provided examples Note Note that this validation set is never used to update the model parameters, and only is used to choose a model.
examples, we choose the model
4 EXPERIMENTS
4.1 REGULAR EXPRESSIONS
We validate the training algorithm we propose on the task of synthesizing regular expressions ('regexes') ) formally defined in Section We use the regular expression domain language presented by Ye et al. (2020). In addition to defining a regular expression specification language, they also define sampling distribution over the space of regular expressions that we use sample programs for training and evaluating our model. This distribution uses templates that generalize types of regular expressions that people ask about on fora such as StackOverflow. Further details are provided in Appendix(A A
'W follow prior work (Pu et al. 2020) and impose uniform, rather than learned, prior over this sample. "Ideally, one could perform exact inference to draw samples from S, directly. As stated earlier, this is intractable. Therefore, we first sample subset of the and columns in the consistency matrix, then perform the RSA inference over this much smaller denser sampled matrix. However, consistency matrix A sparse (mostly 0s) - most programs are inconsistent with any non-trivial set of examples allowing for reasoning about sample of the matrix.
SSince the models are used only generate the programs and utterances that are used create the lexicon, we can draw examples from other sources, including models other than So, (example, Iprogran examples.,) and Lo, (programi examples.))
This amounts performing early stopping on the validation metric.
5

---

Published as a conference paper at ICLR 2024
4.2 MODELS FOR COMPARISON
Base models We use ByTS-small models (Xue et al. 2022) as the backbone for all speaker and listener models. To obtain the base speaker Sa, and listener Lo models that approximate the literal speaker and listener respectively, we use a set of 300,000 randomly-generated program-specificatii pairs (with varying numbers of examples in each specification) and finetune the pretrained ByTS checkpoint. Full details of training are provided in Appendix The Le, model acts as the LITERAL model in our experiments.
PRAX We start with the base models Sa, and Leo and use the iterative data generation and fine- tuning algorithm to obtain a sequence of synthesis models L,g, for rounds r = 0. O..... Rmax. We use the Top- I metric evaluated small validation set to choose the best model which we refer to as the PRAX model.
Finetuning on human-provide specifications We obtain an HFT model by fine-tuning Ló curated high-quality human-provided specifications (Section 4.5). This model allows us to compare how well our approach of using model generated informative examples compares with sourcing more expensive human annotations.
GPT-3.5 We evaluate GPT-3.5 by using the program-specificen
pairs we obtain as users interact with the other three models, and revealing each specification to the GPT-3.5 model in the order the user provided them, one example
time. We stop when the model guesses the correct regular expression, when all the examples are presented. We can think of this as form of interaction where the human docsn't 't observe the outputs this model while giving examples. Further details of how the model is prompted are in Appendix F
Inference Crucial to our approach is the ability to generate programs from examples, and vice versa. To generate programs from specification (sequence of examples from either self-play or human), we present to the listener, and sample 500 programs using top-p sampling (Holizman al. 2020) with p = 0.9. We then deduplicate the set of sampled programs, and filter out programs inconsistent with the given specification. We can then sort the remaining programs by their score under the model obtain a ranked list of consistent programs. Similarly, to generate specifications from program, we sample 500 examples using top-p sampling with p 1 and check that the examples are consistent with the program.
4.3 PROCEDURE
We evaluate the model the basis of successful communications on 11 human participants. A sampled regex p is given to a human participant, whom describes it using a sequence of examples, providing example in each turn for upto maximum of 10 turns. The synthesizer takes the examples provided and generates a ranked list of inferred programs, of which the top-1 regex p' shown the participant. The communication is successful when p p', which point the interaction ends 1o A total three synthesizers were considered - the LITERAL model, the human fine-tuned HFT model, and the PRAX model. The identity of the models referred the users only as differently colored robots. The study yielded communication history over a total of 340 regexes (109 the LITERAL model, 113 to the HFT model, and 118 to the PRAX model) Further details about how the user study is conducted are provided in Appendix E
4.4 MEASUREMENT
We consider the following metrics. TOP- @t measures whether the model's top-1 matches intended regular expression at any point turn i of the interaction. We can also consider the average value of Top-1 by aggregating across the turns t E (1,..., 10). Averaging across turns rewards models that pass success criteria given fewer turns model that can infer the target regex at turn 4 on average
1eWe used the greenery Python library identify regex matches in terms of semantic similarity, and just surface form match.
lI small bug caused us to collect few extra interactions for some of the models, which does not change the measurements on the models' relative performances

---

Published as a conference paper at ICLR 2024
Model
ToP-1 TOP-1@110 (SE)
Top-10@10 (SE)
EDIT DISTANCE @10 (SE)
LITERAL
0.434 (0.04)
0.522 (0.47)
0.513 (0.04))
GPT-3.5
0.074 (0.044)
0.189 (002))
0.082 (0.015)
HFT
0.587 (0.047)
0.623 (0.47)
0.614 (0.947)
PRAX
0.661 (0.043)
0.703 (0.02))
0.694 (0.042)
Table 1: Success metrics at the end of 10 turns of interaction with each model, with standard emrors computed using bootstrap sampling. indicates that the results are in replay.
Model
ToP-1 (SB)
ToP-10 10 (SB)
EDIT DISTANCE S 1
LITERAL
0.233 (0.028)
0.333 (0.04)
0,296 (0031)
GPT-3.5
0.048 (0.010)
0.122 (0.014)
0.056 (0.11)
HFT
0.349 (0.032)
0.424 (0.035)
0,390 (0.034)
PRAX
0.373 (0.028)
0.430 (0.030)
0.432 (0.031)
Table 2: Average success metric over 10 turns. We see that the PRAX training method we propose on par with HFT, and outperforms other baselines significantly for all success criteria. indicatess that the results are in replay.
better than model that can only infer the target at turn 10. We use ToP-1 over a validation set as the model selection criterion for our proposed method. Top- 10-t and ToP- 10 are similarly 1@t measures whether the model's highest scoring prediction any of the turns to f is at most 1 token edit from the intended program, and EDIT DISTANCE S is the average of this value over E fI....,10},
defined. EDIT DISTANCE
4.5 HUMAN-PROVIDED SPECIFICATIONS
alternative to generating informative examples using the method we propose is have human annotators provide examples. We collect new dataset of high-quality program-specificttoo pairs.
Procedure We present a participant with sampled regular expression, and instruct them to pro- vide examples that they might use to illustrate the regular expression to another person. Participants are asked to provide at least 5-7 examples. We verify whether the examples are informative by checking whether different annotator is able to identify the program which the given set of exam- ples describes. Further details about the data collection process are presented in Appendix D
Usage of data We collect total of 440 program-speciffcation pairs. We sample small subset of 40 pairs that received "correct" verifications as a validation set for model selection. We use the other 400 pairs as training set to finetune the La, models on human-provided informative examples, obtaining HFT (see Appendix (B).
4.6 RESULTS
the rate of success for different models at the end of 10 turns of interaction. We see that training on informatively examples results in large gains in performance. Both the PRAX and HFT models significantly outperform the literal model for all three criteria of success. Looking at the aggregate success rate across turns Table reveals that it not just that the PRAX synthesizer eventually catches up to the HFT model, but also performs on par with it over the course of the interaction. Figure shows the progression of each metric over the course interaction. In contrast, that GPT-3.5 performs worse than the literal model. One reason for this could be that the distribution of regular expressions that the GPT-3.5 encounters in its training data could be quite different, leading worse performance. In conclusion, the experiments validate hypothesis that humans communicate more effectively with the model trained on informative examples (the PRAX and HFT models) than with model trained randomly chosen examples (the LITERAL model).

---

Published as a conference paper at ICLR 2024
0.8
Nodal
0.8
Model
0.8
Model
Edit Distance 18tt
Lieral
Frak
0.6
0.6
0.0
Top 1081
Top: 10:0
0.4
0.4
0.4
0.2
022
0.2
0.0
10 0.0
15
0.0
(a)
(b)
(c)
Figure 3: Performance of various models function of turns, measured in ( Top- 1 @t.
TOP-1@U and (c) EDIT DISTANCE I 1@t. Lines show averages, and bands are standard errors. Our model PRAX, trained entirely from self-play and RSA inference without using human numan-provided data performs better than the non pragmatamaicc LITERAL model across all turns and metrics, and matches the performance of HFT tuned human- provided examples.
Target program
Examples
LITERAL
PRAX
AAAAAAAAAAAAAAA V
4A2.)
4A(1,)
4A(2.)
4AA /
All V
B6 V
(A-2X1,2502,4)
[A-Z3(1))(224)
BBW
AAAAAAAAA
d
Figure 4: Example specifications for two programs provided during the user study, along with the highest ranked guess from the LITERAL and the PRAX models.
Examples of synthesized programs Figure shows examples of guesses by the LITERAL and PRAX models given the same sequence of examples. In the first case, we see that the PRAX model is able to infer that if user wanted regular expression that accepted 4A, they would have specified that, and instead correctly guesses that the user wanted at least two A the string. The second example also shows how the LITERAL model synthesizes regular expression that is correct, but is too specific, while the PRAX model recovers the correct generalization.
5 ANALYSIS OF TRAINING
Figure shows the progression of the ToP-1 metric over the course of different rounds of training. We see that as we train the model for more rounds, the performance of the model generally increases, and then tapers off. This shows that as the model is trained for more rounds, it gets increasingly pragmatic. Since the model we choose for the user study is trained for 5 rounds, on 1024 5120 programs, also compare to training the model for only single round the same number of programs. replay study (similar how we evaluated GPT-3.5; Figure we find that iteratively generating data and updating the model performs better. We also that finetuning the base model on 400 examples (to match the HFT setting) from a later round training also results in a strong model, suggesting that the speaker is trained more, generates examples that useful to finetune a listener model.
6 RELATED WORK
Neural network models of pragmatic reasoning Prior work has applied the the RSA pragmatic reasoning framework to improve neural models at inference time for tasks including image caption- ing (Andreas & Klein| 2016 vision-and -anguage navigation (Fried et al. 2018b), and machine translation Goodman 2019), RSA is used inference time to re-rank multiple outputs from the neural models.
al. 2018), instruction generation (Fried et al. 201 8a),
&
8

---

Published as a conference paper at ICLR 2024
0.275
0.250
0.200
Methos
0.150
0.125
Lsermmut
Vail darion
Round
Figure 5: TOP-1 metric over the course of rounds of training the PRAX model. We report the metric on the validaton set as well evaluating all interactions from the user study in the replay setting (similar to how we evaluated GPT-3.5). We compare the accuracy over rounds of training to generating specifications and updating the models only once, amounting to single round of We also compare to fine-tuning the base
the procedure with more programs -PRAX-single-ooudde model on 400 pairs (same number HFT) generated by the speaker in the 5th round of training (PRAX-HFT-matcl) to assess the quality of our speaker-generatee examples.
PRAX has two advantages over these works: (1) it requires no human- -ronn-pr data during training; (2) it uses RSA at training time via data generation, amortizing expensive RSA computaion.
Other approaches have used pragmatically motivated training procedures. The closest works to ours White al. 2020) and Lazaridou al.) (2020), who use reinforcement learning approaches to fine-tune a speaker model using reward from a fixed listener model. Monroe & Potts (2015) and McDowell & Goodman (2019) backpropagate through the RSA procedure training time to reason counterfactually about pragmatically produced utterances from humans. Again, PRAX is unique in that it does not require human-provided training data.
Finally, Andreas & Klein (0166) find that amortizing pragmatic reasoning during training does not perform as well explicit pragmatic reasoning during inference in the domain of image captioning. We demonstrate that amortization is in fact effective for the domain programming- by-example.
Pragmatic reasoning for program synthesis Similar to our work, Vaithilingam et al. (0033) conduct study of how users interact with an exact RSA pragmatic regular expression synthesizer over toy domain of 1000 regexes total over strings of only Os and 1s. Pu et al. (2023) propose way to make pragmatic PBE more efficient by inferring global ranking function, but still relies on the expensive exact RSA during training. Our approach is different in that by using neural models for speakers and listeners at training time, we are able to scale to realistic regex domain. Pertseva et al. also present approach version space baaser-bbased approach to regular expression synthesis from examples by explicitly modeling the probability of examples describing programs (as in our speaker models), but they work with only positive examples (a subset of example space with examples that have the output v, excluding those with the output X). Ferreira et al. (2021) present an SMT-based method that reasons about distinguishing inputs synthesize regular expressions. We discuss connections to iterated bootstrapped training for program synthesis in Appendix
7 CONCLUSION
We present PRAX, a novel algorithm that bootstraps pragmatic program synthesizers by (1) gen- erating datasets using self-play between speaker (program -> examples) and a listener model (examples + programs), and (2) training on the generated data. Crucial to our approach is the use of pragmatic inference to make the generated data more informative. PRAX produces pragmatic program synthesizers with minimal supervision: in a challenging regular expression domain, match- ing the performance synthesizers fine-tuned on numan-produee human-pra -povidee data during training. Future work might explore scaling pragmatic program syn- thesis to open-ended Python code generation, and application to multimodal specifications - e.g. with natural language and examples (Ye et al. 2020).
examples, despite not using any

---

Published as a conference paper at ICLR 2024
ETHICS STATEMENT
Our dataset collection process and user study constitute human subjects research. Our studies were deemed exempt from full IRB review by our institution. All participation was voluntary. Participants signed an online consent form, and were compensated fairly for their time.
ACKNOWLEDGEMENTS
The authors would like to thank Xi Ye for help with sampling regular expression programs, Eric Lu and Kevin Ellis for initial discussions, Priyan Vaithilingam for inputs the interface and user study, Kira Jones for help with compensating participants, Catherine Copetas for help with advertising, Alex Xie and Simran Khanuja for help with testing the user study interface, and Vijay Viswanathan, Jared Fernandez, Zhiruo Wang, Harshita Diddee, and Lindia Tjuatja for feedback on drafts. SV was supported by gift from Autodesk Research.
REFERENCES
Jacob Andreas and Dan Klein. Reasoning about pragmatics with neural listeners and speakers. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 1173-1182, Austin, Texas, November 2016. Association for Computational Linguistics. doi:
10.186533v1/DDI-11122 URL/https://allantoolgy 1ttp:/aanthooooooor//0----111111 org/D16-1125
Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. In International Conference Learning Representa-
tions, 2017. URL
Xinyun Chen, Petros Maniatis, Rishabh Singh, Charles Sutton, Hanjun Dai, Max Lin, and Denny Zhou. Spreadsheetcodeer: Formula prediction from semi-structured context. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 1661-1672. PMLR, 18-24 Jul 2021.
mlr, wtwppede.srss....esee.ee....esee
www.ppressssvve h1tp://119//cc/12/ html
Reuben Cohn-Gordon and Noah Goodman. Lost in machine translation: method to reduce mean- ing loss. In Proceedings of the 2019 Conference of the North American Chapter of the Associa- tion for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pp. 437-441, Minneapolis, Minnesota, June 2019. Association for Computational Lin- guistics. doi: 10.18653/v1/N11-1100 1042. URL / .wr.ea..rgg/M... woo.oogg///NN/N
Reuben Cohn-Gordon, Noah Goodman, and Christopher Potts. Pragmatically informative image captioning with character-level inference. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technolo- gies, Volume (Short Papers), pp. 439-443 New Orleans, Louisiana, June 2015 8. Association for org/
Computational Linguistics. doi: 10. 10.18653/v1/N18-- 2070. URL https::/accaathhtt
N18-2070
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel rahman Mohamed, and Pushmeet Kohli. RobustFill: Neural program learning under noisy I/O. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 990-998. PMLR, 06-11 Aug 2017. URL httpp:://proceedeiiie
mlr. prwss/ press/vT0/dee wwt./vvwinl............ htmll
Kevin Ellis, Catherine Wong. Maxwell Nye, Mathias Sablé-Meyer, Lucas Morales, Luke Hewitt, Lue Cary, Armando Solar-Lezama, and Joshua B. Tenenbaum. Dreamcoder: Bootstrapping in-
ductive program synthesis with wake-sleep library learning, In Proceedings of the 42nd ACM SIG-
PLAN International Conference on Programming Language Design and Implementation, PLDI 2021, pp. 835-850 New York. NY. USA, 2021. Association for Computing Machinery. ISBN 978 1550833912. doi: 10. 11.111/54554433445500000 URL TtLhhttps: //ooi. orooorg///11 1145/3448888. 3454088
10

---

Published as a conference paper at ICLR 2024
Yu Feng, Ruben Martins, Osbert Bastani, and Isil Dillig. Program synthesis using conflict-driven learning. ACM SIGPLAN Notices, 53(4):420-433 2018.
Margarida Ferreira, Miguel Terra-Neves, Miguel Ventura, Inês Lynce, and Ruben Martins. Forest: An interactive multi-tree synthesizer for regular expressions. In Jan Friso Groote and Kim Guld- strand Larsen (eds.). Tools and Algorithms for the Construction and Analysis of Systems, pp. 152-169, Cham, 2021. Springer International Publishing. ISBN 978- 778-3-030-72016-2.
Michael C. Frank and Noah D. Goodman. Predicting pragmatic reasoning in language games. Sci- ence, 336(6084))998 998, 2012. doi: 10.1 10.112//cceecc... wwt.siiiinee..188..... 1218633. URL https: http:::/wwwwwscineee
brg//doi/abs/1..11220 https//000.11////ceencnc 1218633
Daniel Fried, Jacob Andreas, and Dan Klein. Unified pragmatic models for generating and following instructions. In Proceedings of the 2018 Conference of the North American Chapter of the Asso- ciation for Computational Linguistics: Human Language Technologies, Volume (Long Papers), pp. 1951-1963, New Orleans, Louisiana, June 201 8a. Association for Computational Linguistics. wttpaaanooooooooog//111111111111
doi: 10. 10.18653/v1/N18. 177.
Daniel Fried, Ronghang Hu, Volkan Cirik, Anna Rohrbach, Jacob Andreas, Louis-Phillppe Morency, Taylor Berg- Kirkpatrick, Kate Saenko, Dan Klein, and Trevor Darrell. Speaker-follower models for rision-and-language navigation. In S. Bengio, H. Wallach, H. Larochelle, K. Grau- man, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Sys- tems, volume 31. Curran Associates, Inc., 2018b. URL httpps://ppoceeddinggg/ www.wing...eniiiinnoommm cc/ 68 http:///0000c005033336663353-330
paper files/ / (ataperr2018/f1le///
pdf
Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Program- ming Languages, POPL '11, pp. 317-330, New York, NY, USA, 2011. Association for Com- puting Machinery. ISBN 9781450304900.
doi: 141144//922388811266222 URL https:
//doi.org/10. 011111111//19888 1494
Luke Hewitt Tuan Anh Le, and Joshua Tenenbaum. Learning to learn generative programs with memoised wake-sleep. In Jonas Peters and David Sontag (eds.). Proceedings of the 36th Con- ference on Uncertainty in Artificial Intelligence (UAI), volume 124 of Proceedings of Machine Learning Research, pp. 1278-1287. PMLR, 03-06 Aug 2020. URL httpss:/pproceedings. tt20a. html]
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. In International Conference on Learning Representations, 2020. URL |htpp:: //openreview. http:/iwwwwwweeeeeeeeeeeeeeeeeee wwwp:/eee/fooumiiieeeeeo Forr/orrrrrrrrrryrrrr
Angelkki Lazaridou, Anna Potapenko, and Olivier Tieleman. Multi-agent communication meets natural language: Synergies between functional and structural language learning. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 7663-7674, Online, July 2020. Association for Computational Linguistics. doi: 00..6653/1/2220..o main. 685. WtRL/htts:::/eee httptpp::/aaaaaahollogyyo httpa//aaaaatttoaooo////////.... acl-main. 685
Bill McDowell and Noah Goodman. Learning from omission. In Proceedings of the 57th An- nual Meeting of the Association for Computational Linguistics. pp. 619-628. Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10.18653/v1/P19. 1059. URL
bttps::/aac.anthooogy.....gg/
Will Monroe and Christopher Potts. Learning in the rational speech acts model. In 20 th Amsterdam Colloquium, 2015.
Elizaveta Pertseva, Mark Barbone, Joey Rudek, and Nadia Polikarpova. Regex+: Synthesizing regular expressions from positive examples. 11TH Workshop on Synthesis. URL https://par. nsf. nsff.ov/bbb11o/1133674
Yewen Pu, Kevin Ellis, Marta Kryven, Josh Tenenbaum, and Armando Solar-Lezama. Program synthesis with pragmatic communication. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 13249- 13259. Curran Associates, Inc., 2020. URL https::::: U wewpeeeeddiinnsneeeissee.eeee cc/ cttppprrrccpppprrrpcppppp paper files/

---

Published as a conference paper at ICLR 2024
Yewen Pu, Saujas Vaduguru, Priyan Vaithilingam, Elena Glassman, and Daniel Fried. Amortizing pragmatic program synthesis with rankings, 2023.
Priyan Vaithilingam, Yewen Pu, and Elena L. Glassman. The usability of pragmatic communication in regular expression synthesis, 2023.
Julia White, Jesse Mu, and Noah D Goodman. Learning refer informatively by amortizing prag- matic reasoning. In CogSci, 2020.
Linting Xue, Aditya Barua, Noah Constant, Rami AI-Rfou, Sharan Narang, Mihir Kale, Adam Roberts, and Colin Raffel. ByT5: Towards token-free future with pre-trained byte-to-byte models. Transactions of the Association for Computational Linguistics, 10:291-306, 2022. doi: 1.11162/aclaa0004600 URL httpp:://aclaan htttps://aclanthoooggyy. 1tt.:/...rrr2222..a111111111
Xi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett. Benchmarking multimodal regex synthesis with complex structures. In Proceedings of the 58th Anmual Meeting of the Association for Computa- tional Linguistics, pp. 6081 1-944, Online, July 2020. Association for Computational Linguistics. doi: 10. 00.18653/v1/0022..ee maa.: 541. URLL/htp:://aacaattoollyyr/////p acl-mmacllna 541.
A PROGRAM SAMPLING
We sample programs from the CONCATENATION and SEPARATION templates from Ye et al. (2020) since the INTERSECTION template is not supported by popular regular expression libraries like Python's 's standard re module. We sample programs with maximum concatentation depth of 3, and sample programs from the CONCATENATION and SEPARATION templates in 5:1 ratio using the sampling tools provided by Ye al 2020).
Despite controlling the complexity of programs during sampling, many sampled regular expressions are quite long and difficult for a human to reason about easily. To make the task easier for annotators and user study participants, we use the number of tokens the regular expression program as proxy for complexity, and cut off programs that are shown to humans at a maximum length of 30 tokens.
B TRAINING BASE MODELS
We use ByT5 pretrained models (Xue et al. 2022 as the backbone to build all our speaker and listener models. We sample programs described in Appendix A and generate uninformatively chosen examples for the programs. We then train the models on a sequence-to-sequene task. The input to the listener to the speaker is a program followed by a linearized sequence of prior examples, and the output is the next example in the sequence.
linearized sequence of examples, and the output is the program. The input
We generate random examples by first choosing whether the example is positive or negative exam- ples with equal probability. the example is positive, we use the rstr Python package to sample strings that match the target regular expression. If the example is negative, we use the same package to sample string from the regular expression * and check that doesn't 't match the target program.
We train the base models on 100,000 programs. For each program, we randomly sample 3 specifi- cations. The length of each specification is chosen to be an integer between 0 and 15, uniformly at random. The models are trained for epoch, using the AdamW optimizer with learning rate of 5 x 10 with the learning rate warmed up over the first 10% of training steps, and then decayed linearly. The batch size is set to 32.
Additionally, we found that training the base model (that we dub LO) for epochs achieved higher performance. To ensure fair comparison, we trained from the higher performing base model (that we dub L0+) using our PRAX algorithm. We see Figure 7 that we get significant improvements over the based literal model even when continuing from an improved base model.
We also compare to training the base model from a mandoml--niiallzee checkpoint Figure 6 and find that training from the pretrained checkpoint is far more sample-efficient.
12

---

Published as a conference paper at ICLR 2024
0.14
0.10
0.00
method pretrained
0.04
0.00
10000
steps
Figure 6: Comparing validation performance of base model trained from pretrained checkpoint to one trained from a randomly initialized checkpoint, One epoch of training is 9375 steps.
round
0.275
0.3
L0+
Top-18r
0.225
0.2
0.200
base LG Lt=
0.1
0.150
0.0
0.125
Round 10
(a) TOP-1 over turns
ToP-1 over rounds of training
Figure 7: Comparison between the LO model from the original experiments and the L0+ model trained for longer. Round corresponds to the LITERAL model.
13

---

Published as a conference paper at ICLR 2024
C PRAGMATIC MODEL TRAINING
Algorithm Outer training loop
1: procedure TRAINING(Le,, Sd.: H. V, METRIC)
2: Input: Base listener model Lo.
3: Input: Base speaker model $0
4: Input: Set of hypotheses H
5: Input: Validation pairs V
6: Input: Validation metric METRIC
7: Output: Trained listener model Lø
8: for 0 to Rmax do
9:
Sample set of & hypotheses H H
10:
D, < {(h, C.N,GNRATTRRRAAAATTSSCCCCCCTOOO I H}
11:
Lo TRAINLISTENER Lo,: U/-0 D2)
S < TRAINSPEAKER(S 1/ Dj)
13:
H. < H H
14: end for
15:
return arg max, METRIC(LO,
end procedure
Finally, we finetune the the base models we train by iteratively using the speaker and listener models generate data, and finetuning the generated data using the algorithm shown above.
To generate the candidates at a particular round r, we use both the base models and the models from round Sampling from multiple models with different biases help draw more diverse sample of programs and examples, and get a better approximation of the consistency matrix to perform RSA reasoning over. We draw 250 samples from each of the models we are sampling the base listener, the listener from round the base speaker, and the speaker from round r.
As we the algorithm, we update the models by training from the initial parameters (of the base speaker or listener model) on all the datasets generated up to and including that round. We train for for Rmar
rounds with k 1024 programs per round, generating specifications with up to Nutterances 10 examples. We choose the model trained for rounds based on the ToP-1 metric on the validation set 40 examples. At each round we update the models using the AdamW optimizer for I epoch, using learning rate of 5 x 10-5, The batch size is set to 32.
D DATASET COLLECTION
We recruited 18 computer science graduate students. The data collection task proceeded in two phases specification creation and specification verification. Some participants did the both tasks, while some only did the verification task. Participants who did both tasks spent approximately hours on the task and were compensated with $45, while those who did the verification task spent approximately 2 hours and were compensated with $30. Participants were allowed to perform the task online at location of their choice, and were allowed to perform the task across multiple sittings.
Each participant was given a short tutorial on the syntax and semantics of regular expressions, and small quiz where they had enter three positive and three negative examples for given regular expression to proceed to the rest of the study. Participants were then told about communication game, and to provide examples that they would use if they were asking another person to write the online forum like StackOverflow.
regular expression for them
they might
Participants then went to the annotation screen for the specification creation task (if they took part, if not they proceeded directly to the next stage), where they were shown regular expression and asked to enter examples consistent with it, the interface shown in Figure g Consistency was automatically checked, participants could not enter inconsistent examples. A minimum number of examples between 5 and 7 was randomly picked for each instance (to allow the participants from simply providing the same minimum number for each program), but no limit the number of
14

---

Published as a conference paper at ICLR 2024
Algorithm 2 Approximate RSA inference
1: procedure CENNEATTERRAGMMAATSSSCCCCCCACCTT Sp
2: Input: Listener model Lg
3: Input: Speaker model So
4: Input: Target program h
5: Output: Specification
6:
[-[]
7:
for 1 to Nexamples do
8:
Sample examples from So conditioned on and filter for consistency with h. h,
9:
E f- SATEXAMMPECCANDDDATESS
10:
Sample programs from Le conditioned and filter for consistency with + GETDISTRACTORSI(L: for in D (h) do for e in do
11:
12:
13:
14:
D Populate consistency matrix with whether p is consistent with Mle, p] - 1p -ee
15:
16:
end for end for
17:
Compute the literal listener distribution over the sample M of the consistency matrix for in D U {h} do
19:
for in do
21:
Literaa pe, Σ, Meel
Mic.p
22:
end for end for & Populate consistency matrix with whether is consistent with e for p in D (h) do for e in E do Sesale,p] &
23:
24:
25:
26:
Leumale
Ene Liven ee 5
28:
end for end for e" + arg max, Sksale, h]] s s [e*]
29:
30:
32:
end for
return s end procedure
34:
Regular expressions from examples
User: dev
Regei cheatsheet
You are now the describer
Here, you are presented with rogular expression. You need to provide set examples that desenbee this regular expression to guessor. exsmppes.
Regex: k(2,
Enter example
Add
WZZZZ
KZ
Figure 8: Interface for providing examples for regular expression
15

---

Published as a conference paper at ICLR 2024
Regular expressions from examples
Reger cheatsheot
You are now the guesser
You are given iit of ecae provided descrier You are sito siven optors reguiar expressions. You nead chosse whic regular expresión best 1ts
trying
katt about.
4kvm-pp
W=44mm3
Ser-Sert
700-9)0,2000
[8 0112, a112
Figure 9: Interface for verifying a specification written by another human
examples was placed. Participants created specifications for 40 programs before proceeding the verification task.
For the verification task, participants are shown specification and regular expressions, of which the target regular expression (that the specification was written for) is one, as shown in Figure 9 The others are distractors. To ensure the distractors are not too easy to distinguish from the target, we sample distractors using the LITERAL. model. Of the 4 distractors, we attempt to find 2 which are consistent a subset of the specification, and 2 which are inconsistent with the specification. Since providing the entire specification might lead to too few consistent programs remaining, or distractors that are too hard to tell apart from the target, we use only the first example of the specification as input to the LITERAL model to generate distractors. Depending whether they did the specification creation task, participants verify 40-90 specifications.
The dataset contains 440 examples in total. Of these, 423 have 2 verifications and 17 have one verification. the 440, 352 (80%) have two verifications that recover the target. 406 (92%) of the 440 have least one verification recovering the target. We use 40 of the programs with two verifications recovering the target as the validation set.
E
USER STUDY
To conduct the user study, we recruited 11 computer science graduate students. Participants spent approximately 1.5 hours the task and were compensated with $25, Participants were allowed to perform the task online at a location of their choice, and were allowed to perform the task across multiple sittings. Figure 10 shows the UI.
Each participant was given a short tutorial on the syntax and semantics of regular expressions, and small quiz where they had enter three positive and three negative examples for given regular expression to proceed to the rest of the study. Participants were then told about communication game, and informed that they would be playing the role of the speaker in the game and describing a target program. Each participant interacted with the three models in order - PRAX, LITERAL, and HFT and cycled through the list in order, but first model they encountered was chosen randomly. Each model was assigned color, and the participants were told the color of the model they were interacting with, but not given any other details about it. Participants provided examples one at a time, and observed the synthesizer's 's highest ranked guess every step. If the guess matched the target program, the interaction ended. Participants were given the option to move to the next task after providing 10 examples. Each participant completed 31 instances they provided examples for
16

---

Published as a conference paper at ICLR 2024
Regular expressions examples:
User: dev
Regex cheatshect
You are now the describer
Her,, presente with repression. You need interact with and cummanicate the regular wepresior, Alter each refening
example is provided, system playing game is completed when the systent's guess matches the regular expression were given, when 10 ecamples have bren proviced. the failed
of quesser guess regular expression might
system producas the system, and the system falls to guess the regular expression after 10 exampies, you can submit the asamples you provided and move on the next taak.
guass,
provide
which might
You are now interacting with the red robot.
Regex: u{2, J (U]A) ?N.a), [a-z] {3, 4}
System's guess:
Figure 10: Screenshot of the user study UI with an example interaction
31 different programs, with one of the interactions from one of the particpicipants being excluded due to error.
F PROMPTING AN LLM
We prompt the gpt-3. 3pt-3.5-tuue S-turbo-insstruct variant of GPT-3.5. We provide examples of 5 program- specification pairs in the context of a code snippet, followed by a set of examples. We sample 10 generations with temperature
0.7 and 0.9. We sample for maximum of 64 tokens, or stop tokens that indicate that the regular expression is complete are sampled.
We rank the generated completions using the sum of token log probabilities, and choose the highest scoring program consistent with the given answer as the top-1 guess, and other consistent programs the top-10 guesses to calculate the ToP-1 and TOP-10 metries.
G SPEAKER QUALITY
One measure of the speaker's quality is the loss evaluated in examples provided by humans. Evalu- ating loss allows us to see if human provided examples are more likely under model's 's distribution, without penalizing the model for the exact example not appearing in set of examples decoded from the model (since there are many possible examples that are consistent with a program, and multiple possible informative examples too). We see in Figure [I that even without being trained on any human- examples, the speaker loss on numan-provice validation examples reduces.
H CONNECTIONS TO ITERATED BOOTSTRAPPED TRAINING
Methods such as DreamCoder (Ellis et al. 202T and Memoized Wake Sleep (Hewitt et al., 2020) use iterated bootstrap training to build a hierarchy of abstractions solve tasks more effectively over iterations of training. At each iteration of training, they create tasks by sampling program from a changing library of abstractions, and executing the program on fixed distribution inputs to train synthesizer to work with updated abstractions.
Our method on the other hand is aimed at allowing synthesizer to reason about how examples are chosen to demonstrate programs from fixed library. We change the distribution of examples being drawn from a trained speaker model over the course of iterated bootstrapped training towards more informative examples.
17

---

Published as a conference paper at ICLR 2024
Speaker validation loss
2.3
2.2
2.1
Logg
2.0
1.9
1.8
0
2
4
6
8
10
Round
Figure 11: Speaker loss on the validation set computed over rounds of training
18


Reviews:
[{"review_id": "9QlIbtTa5u", "reviewer": "Reviewer_Dg1v", "summary": "This paper focuses on program synthesis by example for regexes. It aims to learn a program synthesis model that reasons pragmatically. As many possible programs can meet ambiguous input example specifications, counterfactual thinking should be usefully employed to differentiate among the many valid hypotheses. Other works have investigated this possibility, most under the rational speak acts (RSA) framework, but this kind of reasoning is intractable to do exactly for non-trivial domains. The paper suggests a bootstrapped learning approach to overcome this limitation, by jointly learning a speaker model (which suggests pragmatic examples given an input program) and a listener model (which suggests a likely program, given a list of assumed pragmatic examples). Over multiple rounds, these networks are trained on one another’s predictions, chosen according to an RSA methodology, made tractable by restricting the hypothesis space according to the programs sampled from the model. Experiments with human-trials demonstrate that listener models trained in this framework perform better than comparison approaches.", "questions": "(1) The proposed system effectively improves the listener model by finding “better” synthetic training I/O examples, where better means there is a pragmatic connection between the examples and the target program. However, it’s unclear if this improvement changes the upper-bound of the listener model performance, or if it just helps the listener model reach a good performance with less training iterations. Training the base model for 300k programs, for a single epoch, it's not clear whether the model has started to plateau in performance. It would be helpful to provide evidence that the base model has saturated, by e.g. plotting validation performance over pretraining iterations. What would this plot look like?\n\n(2) It’s also not clear to me why starting from a pretrained model like ByT5 would be necessary or helpful. The programs come from a constrained DSL, where unlimited synthetic data can be sampled, so it should be possible to train the base models from scratch. It would be good to include an ablation on how starting with or without pretraining affects the proposed method. What is the justification for starting with a pretrained model?\n\n(3) Much of the evaluation is based off of human-interactions, which is present only in limited quantities. Are there any metrics which could be evaluated without human interactions? For instance, what about the following set-up:\n\n1. Pick a target regular expression and a single I/O example at random\n2. The listener samples a target expression given the current specification\n3. With respect to (2), the speaker samples an example, which is annotated as consistent/inconsistent by an oracle\n4. Repeat steps 2 and 3 until the listener samples the *correct* target expression\n\nThe metric would then be the number of example generations needed for the listener to predict the correct regular expression, where the idea would be that as the speaker is better at producing \"pragmatic\" examples it should require less steps versus a baseline that for instance randomly sampled an example. Beyond serving an evaluation set-up that requires no human-data, this kind of framework could conceivably even be useful for “real-world” applications: e.g. this could reduce the burden on an end-user, who instead of having to think up new examples as input, would just need to label them.\n\n## Minor:\n\n(4) Is the hypotheses set in Appendix D randomly sampled programs from the DSL? Please make this clear. More generally, some of the terminology used in the pseudo-code could be more directly mapped back to concepts in the main paper, or given a more detailed treatment in the supplemental text. \n\nThere is a typo in the figure 3 caption: metrix", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I enjoyed this paper and I would support its acceptance into the conference proceedings. \n\nThe proposed approach is sensible and well-explained. The methodology appears quite general, and should be able to be used broadly as it requires no human GT data during training. In fact, the human GT data that is used in validation seems like it could be removed, as based on the trend in figure 5 it doesn’t appear as though the method is overfitting in any sense over bootstrapping rounds.\n\nThe experimental design and presentation is sound and convincing for the regexes inference domain. The paper mainly validates the proposed system with human-trials, which makes sense as its hard otherwise to source ‘pragmatic’ examples, and it confirms the system would actually be easier to work with for an end-user", "weaknesses": "While a lot of effort has gone into validating the system is working for this particular regex domain, the paper does not explore other problem settings to any degree. I don’t think this is a major limitation, but it is probably holding the paper’s rating back slightly. The impressive results on one-domain are likely of interest to a subset of the ICLR community, but showing that this methodology can generalize effectively across domains would broaden this interest. As a note, I don’t even think these other domains would need to be *more difficult* than regexes (e.g. like python code generation mentioned in the conclusion), but could even be other domains of similar complexity. \n\nIn some ways the comparison against HFT is a bit unfair, as the proposed method has effectively unlimited training data (although only a set amount of bootstrapping rounds are employed), whereas HFT is fine-tuned with a fixed amount of human-feedback. To get a “fairer” upper-bound of how “good” the pragmatic examples produced by the system are with respect to the human provided exemplars, it might be good to include an additional condition where the listener model is fine-tuned on a fixed amount of data (i.e. the same amount as used in HFT) where the I/O examples are produced by the final speaker model. \n\nMinor:  \n\nThere is a connection to be made between the proposed method and bootstrapped “wake-sleep” approaches for program synthesis [1,2]. Both learn “generative” and “inference” models that learn on one another’s outputs. The modeling set-ups are different, as these wake-sleep approaches move towards a target distribution, whereas the proposed method optimizes for synthetic training data that matches a prior desiderata (pragmatic I/O examples), but these ideas are close enough that they should be discussed within the related work section. \n\n[1] DreamCoder: growing generalizable, interpretable knowledge with wake–sleep Bayesian program learning\n[2] Learning to learn generative programs with Memoised Wake-Sleep", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "A0bw3CnzUe", "reviewer": "Reviewer_Lieb", "summary": "The paper scales pragmatic inference for program synthesis to realistic problem\nsizes using neural networks. The authors introduce a listener and a speaker\nneural model and train these iteratively. The models are used to generate\ndatasets containing increasingly informative program specifications, and they\nthemselves are trained further on these datasets in each iteration. To build the\ndataset, the models suggest candidate specifications, and the specifications to\nbe included are chosen from these using pragmatic inference (the Rational Speech\nActs framework).\n\nThe method is evaluated on the task of inferring regular expressions from a set\nof examples in a human interaction study with 11 participants and outperforms a\nbase literal model, a human finetuned model, and GPT-3.5.", "questions": "I couldn't understand the argument for sampling a subset of the consistency\nmatrix $M$ in 3.3. If $M$ is sparse, why does that allow us to sample a subset\nof the rows and columns? Wouldn't we mostly sample zeros? Or is there a strategy\nfor sampling (e.g., sampling dense areas) which is not mentioned?\n\nI also don't understand exactly how the conditioning on previous examples are\ndone when sampling in terms of the consistency matrix. Could you elaborate on\nthat?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Scaling up pragmatic inference for realistic program synthesis could open up\npromising future research.\n\nThe paper is clearly written with illustrative figures. I found the explanation\nof the pragmatic model of program synthesis really good and easy to follow.\n\nThe paper includes a real-world study of program synthesis with 11 human\nparticipants.", "weaknesses": "I believe the main weakness of the paper is that the presented method is not\ncompared to any existing neural program synthesis system (like DeepCoder,\nPCCoder, DreamCoder, CrossBeam, LambdaBeam, etc.). I think this would be\nimportant as the main thesis of the paper is scaling up pragmatic inference to\nthe level of these systems. It would also be good to include a domain for\nsynthesizing programs that's more general and widespread in the literature than\nregexes.\n\nI think that Section 4.6 about the human annotated dataset should be earlier as\nit's already referred to earlier.\n\nSome typos:\n- Introduction: \"an user\", \"coorporative\", \"human ... atempt to communicate\",\n  \"of of\"\n- page 3 top line \"an sampled example\"\n- 4.3 Measurement: \"top-1 matches THE intended regular expression\"\n- 4.7 Results: \"informatively\", \"4\" should be \"Figure 3\"\n- 6 Related work: \"datas\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UwFy6kIB9L", "reviewer": "Reviewer_h5RG", "summary": "In this paper, the authors propose a method for program synthesis (specifically the programming-by-examples variety of it) framed as a two-player game. A _speaker_ model $S$ is charged with generating informative examples, which a _listener_ model $L$ uses to generate programs; within this setup, a given set of examples can be consistent with multiple programs. The authors get around this difficulty by devising an approximation of a pre-existing Bayesian scheme, dubbed RSA. Using LLMs as speaker and listener models, and by performing RSA only on a partial consistency matrix $M$ of programs/examples pairs sampled from them (instead of the full matrix which is prescribed by exact RSA), the authors make it possible to select the examples which are most informative for a given program, resolving the aforementioned ambiguity. These examples are then added to the dataset of (example, program) pairs and used to train the speaker and listener in an Expert Iteration fashion. \nThe authors demonstrate that their proposed method, trained using only synthetic data and their ExpIt-like procedure, performs better than a set of baselines, including a model trained on high quality data sourced from human annotators, and GPT 3.5.", "questions": "- As mentioned above, the RSA framework assumes $L_0$ to assign equal probability to all consistent programs, which is not going to be the case once it is approximated with a Neural Net. Could the authors comment on this?\n- The literal listener $S_0$ is not defined in section 2. Only $L_0$ and $S_1$ are defined. Could the authors provide a definition?\n- Why didn't the authors include any baselines (neural or not) specific to the task of inferring regexs?\n- Some details of the evaluation protocol are a bit obscure. First of all, how do the authors compute their top-1 metric on the validation dataset, when doing model selection? They only provide a definition of the metric as part of the final human trial, so it's not clear how the model would be prompted when computing it at the model selection stage.\n- The authors state that \"TOP-1@$t$ measures whether the model's top-1 matches intended regular expression at any point at turn $t$ of the interaction\". Is it at any point, or a turn $t$? Since the interaction ends after a match is achieved, it can only be at turn $t$, but the text is ambiguous.\n- The authors detail their inference procedure in section 4.4. Therein they state that programs inconsistent with a given example are filtered out. Shouldn't they be left in in order to build the consistency matrix $M$? Does this paragraph only detail the inference protocol for the evaluation phase, or also for the training phase? This is not clear.\n- I assume that the numbers reported in the tables refer to the _fraction_ of instances in which an interaction was successful at time $t$, so it's technically incorrect that the metrics measure \"whether\" something happens. They actually measure \"how often\" it happens over a set of interactions. It would be helpful to the reader to amend this somewhat inaccurate language.\n- From section 4.7: \"4 shows the progression of...\" 4 what? I assume that this actually refers to figure 3 and this is a typo.\n- From the intro: \"A synthesizer trainer in the style of Devlin et al....\" what does this mean? Could the authors be more explicit?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- While RSA is not novel in itself, the paper is anyway quite novel in making it applicable to a large-scale program synthesis task, and in using LLMs to model speaker and listener.\n- The paper is accessible and written well, though it does contain a very large number of details and some typos.\n- The authors set up a comprehensive experimental pipeline inclusive of humans in the loop. Most papers on code synthesis do not actually test their methods \"in the wild\", while this paper does.\n- The proposed method does beat the considered baselines by a good margin.", "weaknesses": "- It appears that one assumption of RSA is that given a certain example, the literal listener $L_0$ should assign equal probability to all programs consistent with it. This is unlikely to be the case once $L_0$ is a neural net, unless this has been perfectly trained.\n- Synthetic data needs to be available to pre-train the literal speaker and listener models. These might not be available when considering more rich \"programming\" languages than regexs.\n- Both the training and evaluation protocols are quite complex, meaning that multiple reads of the paper  are necessary to get all of the details.\n- The set of baselines considered is somewhat narrow, and does not include any previous efforts on the particular task considered (i.e. inferring regular expressions). The authors compare only against effectively an ablation of their own method (LITERAL), their method but trained on a set of human-annotated data (HFT), and a generalist LLM (GTP 3.5).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uRk01htinO", "reviewer": "Reviewer_3Xjo", "summary": "The authors present a framework built on the Rational Speech Acts model that iteratively tunes a listener and speaker model to generate programs fitting a spec. This framework can essentially be viewed as a bootstrapping method to build a dataset and listener and speaker models in a more efficient way than blindly sampling programs. Experiments on a regex dataset show that this framework outperforms naively training a single L/S model pair with a moderately sized dataset as well as prompting a LLM. This framework also outperforms using a human dataset instead of a listener.", "questions": "- Will the dataset be released?\n- How do you guarantee your base program/sample dataset has sufficient coverage to get a usable listener/speaker model? Do you have a prior over which programs and samples may be more useful for training a model?\n- What distribution do you use to sample the set of rows and columns to update for RSA?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The presented method outperforms the literal and GPT baselines. It also outperforms HFT which suggests that the iterative listener training makes a difference.\n- The method outperforms a small human labeled dataset, which suggests that it may be better to use this method if one does not have access to lots of human annotations.\n- The method converges at a comprable rate to the literal and HFT methods, so the bootstrapping method appears to work.", "weaknesses": "- The method is only tested on a regex dataset. This ignores programs that cannot be written as regexes and more complicated programs.\n- This paper only compares the pragmatic framework against the literal and HFT baselines, which are derivatives of the pragmatic framework. While there is a comparison against GPT3.5, I would have liked to see other program synthesis baselines that do similar things for a more thorough comparison.\n- There are no ablations on the number of samples needed to get good performance and other similar hyperparameters.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)