Will the dataset be released?

Yes! It’s included in the supplement.

How do you guarantee your base program/sample dataset has sufficient coverage to get a usable listener/speaker model?

We train the base models on randomly sampled program-specification pairs to initialize them as capable program synthesis models as described in section 3.2 of the paper and section 1 of the General Response.

Do you have a prior over which programs and samples may be more useful for training a model?

Yes, we use a prior over programs based on Ye et al. (2020) that is described in section 4.1 and appendix A of the paper.

What distribution do you use to sample the set of rows and columns to update for RSA?

We use the listener model to generate programs consistent with the prior example (“ab”, ✓) and the speaker model to generate examples consistent with the target program +b* as shown in Figure 1 of the paper. So, for the given example, in the second turn of the simulated interaction we may get a set of programs [a?b?, a+b+, a*b+c?] and examples [(“aab”, ✓), (“abb”, ✓), (“aa”, ✓), (“b”, ✗)], and use those to construct the consistency matrix over which we perform RSA inference.

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.

In section 1 of the General Response, we detail why the Literal model is not derivative of our pragmatic approach, and in itself a standard program synthesis baseline. In section 3 we describe some findings from running a symbolic regex-specific program synthesizer.

Ablations

There are no ablations on the number of samples needed to get good performance and other similar hyperparameters.

Figure 5 presents the performance of the model over rounds of training. Since each round corresponds to training on a new set of (in this case 1024) program-specification pairs, this is an ablation that looks at the number of samples (where each program-specification pair counts as a sample) required to get good performance. We find that model performance increases over rounds of training, highlighting the value of iterated training.

We have also added a comparison to one epoch of training on two different sets of program-specification pairs. One set of 5120 pairs is generated using the base speaker and listener models, corresponding to training on the same number of programs as the Pragmatic model, but in one round, effectively ablating the effect of iterated training. Training in a single round does not perform as well as training in multiple rounds of training.

We also compare to training on 400 pairs from the speaker in the 5th round of training, and find that this performs quite well, suggesting that a speaker in later rounds of training produces informative examples.

If you were referring to a different ablation, please let us know so we can clarify our method.

References

Xi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett. Benchmarking multimodal regex synthesis with complex structures. In Proceedings of the 58th Annual Meeting of the Association for Computa- tional Linguistics, pp. 6081–6094, Online, July 2020. Association for Computational Linguistics. doi: 10.18653/v1/2020.acl-main.541. URL https://aclanthology.org/2020.acl-main.541.

As mentioned above, the RSA framework assumes 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?

This is correct – it is not possible to model a uniform distribution over all consistent programs using the literal listener. We also added a prior term to the description of the L0 computation, thanks for pointing it out. This prior is implicitly modeled by the base model when it is trained. However, this non-uniform prior is used only when we sample from the base model. We follow prior work (Pu et al., 2020) and explicitly impose a uniform prior over the sampled programs (that we use to populate the consistency matrix we perform RSA inference over). We have amended the text of Section 3.2 to convey this more clearly.

The literal [speaker] $S_0$ is not defined in section 2. Only $L_0$ and $S_1$ are defined. Could the authors provide a definition?

We amended the paper to include the definition of $S_0$ analogous to $L_0$: $S_0(example|program) \propto M(example, program)P(example)$

Why didn't the authors include any baselines (neural or not) specific to the task of inferring regexs?

In section 3 of the General Response we describe some findings from running a symbolic regex-specific program synthesizer.

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.

Here is how we perform model selection. Given a model, we present the examples (a single string-label pair) from the validation set one example at a time, in sequence, and count the fraction of instances in which the model recovers the correct program. This fraction is used to score the models. This is similar to the replay setting which we use to evaluate GPT-3.5.

The authors state that "TOP-1@t measures whether the model's top-1 matches intended regular expression at any point at turn 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 , but the text is ambiguous.

Yes, this is a typo, thanks for pointing it out! We mean that for a turn t, the TOP-1@t metric measures the fraction of tasks solved after t turns are complete (that is, the user has provided t examples).

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.

The protocol is for both training and inference. We want the model to learn how to disambiguate between consistent programs, assuming that the base model is already effective at finding a consistent program. Note that the programs sampled are consistent with the given specification, but may be inconsistent with other examples sampled by the speaker that are not yet added to the specification, which builds a consistency matrix with both 1s and 0s.

I assume that the numbers reported in the tables refer to the fraction of instances in which an interaction was successful at time, 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.

We will amend the explanation of the method to make this clear.

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.

This is a typo, thanks for catching it!

From the intro: "A synthesizer trainer in the style of Devlin et al...." what does this mean? Could the authors be more explicit?

We elaborate on this in section 1 of the General Response. We have also updated section 3.2 to make this more clear.

Sampling from the consistency matrix

I couldn't understand the argument for sampling a subset of the consistency matrix in 3.3. If M is sparse, why does that allow us to sample a subset of the rows and columns? Wouldn't we mostly sample zeros?

We use M to refer to the entire consistency matrix with all programs and examples. So, sampling a set of columns at random would mean choosing a set of random programs, and sampling a set of rows would be choosing a set of examples at random. In the context of Figure 1 (where the target program is a+b*), an example of these samples may be [“p+q*”, “hg*”, “jk+”], and [(“xyz”, ✓), (“ij”, ✓), (“jld”, ✓)]. The part of the consistency matrix corresponding to these examples would be full of 0s. Instead, if we use the listener to generate programs consistent with the prior example (“ab”, ✓) and the speaker to generate examples consistent with the target program +b*, we may get a set of programs [a?b?, a+b+, a*b+c?] and examples [(“aab”, ✓), (“abb”, ✓), (“aa”, ✓), (“b”, ✗)], as shown in the figure. We can see again in the figure that this matrix is a lot less sparse than the case of choosing programs and examples to populate the matrix as discussed earlier.

Or is there a strategy for sampling (e.g., sampling dense areas) which is not mentioned?

The only strategy we use is filtering for consistency with the previous examples (for the listener) and the program (for the speaker). We do not use any other sampling strategies.

Conditioning on previous examples

I also don't understand exactly how the conditioning on previous examples are done when sampling in terms of the consistency matrix. Could you elaborate on that?

When generating examples at each turn, we resample the rows (programs) and columns (examples) based on the examples already added to the specification. This allows us to look at a relevant sample of the consistency matrix, as explained above. Referring to Figure 1 of the paper, we unroll an interaction between the speaker and listener models over a sequence of turns. In the first turn, there are no prior examples. The speaker generates examples only based on the target program (in this case a+b*), and the listener synthesizes programs that satisfy an empty specification. We then perform RSA inference and select an example to add to the specification. In the figure, this example is shown to be (“ab”, ✓). For the next turn, we use the specification built so far (now [(“ab”, ✓)]) as inputs to the speaker and listener models, and sample the next example as shown in the figure. This example is added to the specification, and the process is repeated.

1. Speaker generates high-quality examples in later rounds of training

In 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.

We have added a comparison to Figure 5 in the updated draft.

The ability to train on large amounts of synthetically generated data has been vital in making neural and neuro-symbolic program synthesis approaches (such as RobustFill, DeepCoder, etc.) work. Our work is in a similar spirit, and asks whether we can make such synthetically generated data more closely resemble the examples that a human user would provide while using the system.

Hence, our proposed approach can be used to generate a very large number of examples at a much lower cost than having users provide examples. So, even if each example produced by our method is of lower quality or utility than a human-provided example, the ability to scale our approach better than having users annotate data means that we can achieve comparable results at a lower cost, even if we use more examples overall.

We did run the experiment of finetuning the base model on 400 program-specification pairs from the speaker in the 5th round of training, and find that it performs quite close to the full pragmatic training, suggesting that these examples have comparable value to human-provided examples. Note that these 400 examples cannot be obtained without going through the other rounds of training too, and this experiment is meant to illustrate the utility of examples.

2. Base model performance plateaus during training

(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?

Figure 6 in the updated draft plots the validation metric (Top-1 success) on the validation set (40 program-specification pairs). We see that the base model has started to plateau in performance after 1 epoch of training (9375 steps). We have also updated Appendix B with this experiment.

3. Pretrained checkpoints help the base models

(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?

We also observe a substantial gain in sample-efficiency from using a pretrained model (as seen in the plot in Figure 6 of the updated draft). But, in general we agree with your statement that with the ability to generate unlimited synthetic data, we expect that we can start with a randomly initialized model and train until we are able to match the performance of starting with a pretrained model. However, since our goal here is to have a strong base synthesizer (while being agnostic to the specific type of base synthesizer), we opted to use a pretrained model in the interest of sample-efficiency.

4. Human vs automated evaluation

(3) Much of the evaluation is based off of human-interactions, which is present only in limited quantities. [...] would just need to label them.

Since the goal of building this kind of synthesizer is to better interpret human communication, the most faithful evaluation is to have humans interact with this kind of system. Having a model stand in for a human in evaluation might not be representative of the results of human interaction. With specific reference to an algorithm like the one you proposed, the choice of a random I/O example at the first turn is already a significant deviation from human behavior, since a human’s first example would also be chosen informatively. This would in turn influence every future turn of interaction too.

I appreciate the author's responses - I remain positive on the paper and I still supports its acceptance.

We did run the experiment of finetuning the base model on 400 program-specification pairs from the speaker in the 5th round of training, and find that it performs quite close to the full pragmatic training, suggesting that these examples have comparable value to human-provided examples. Note that these 400 examples cannot be obtained without going through the other rounds of training too, and this experiment is meant to illustrate the utility of examples.

Thank you for running this experiment -- I agree with your assessment, and to put it on my own words: this experiments shows that speaker model (once trained) is able to generate training pairs at a similar quality to humans (in terms of impact on training). This is a compelling point in favor of the method that I think should make its way into the discussion.

Since the goal of building this kind of synthesizer is to better interpret human communication, the most faithful evaluation is to have humans interact with this kind of system. Having a model stand in for a human in evaluation might not be representative of the results of human interaction. With specific reference to an algorithm like the one you proposed, the choice of a random I/O example at the first turn is already a significant deviation from human behavior, since a human’s first example would also be chosen informatively. This would in turn influence every future turn of interaction too.

Yes certainly there is no perfect replacement for human-studies, and any automatic metric that tries to capture human-interactions will have flaws, but I still maintain that trying to develop such metrics can be quite useful, for both this work and for future works that will try to improve within this design space. If the choice of the first random I/O has a massive impact on how many tries it takes to find the right expression, this is something that can be quantified with this metric (e.g. by choosing the I/O pair randomly, or having a human provide only the first I/O pair).

Figure 6 – not a major point, but I really think more epochs should be added to this plot, there is still very little evidence of plateauing, especially with how noisy top-1 is as a metric (as it doesn't take into account near misses).

Finally, I would once again encourage the authors to consider discussing the connections to the bootstrapped learning methods [1] and [2] -- these are useful ideological connections that future readers of the paper may benefit from.

Thank you for engaging without response!

We re-ran the literal listener training for additional epochs, and found that there is an improvement in performance as the base model is trained for longer. Since we train our models with linear learning rate decay, we tried two values for the maximum number of epochs — 3 and 20 (the model being trained for 20 epochs did not finish training in the course of author response, but we include partial results from it), and we show the validation performance in Figure 7. We see that the model trained for 3 epochs achieves higher performance. To ensure a fair comparison of our pragmatic training procedure against a stronger listener, we also present preliminary results training the pragmatic model starting with the new base model. Given time constraints, these experiments did not finish running, but preliminary evidence already shows that our pragmatic training procedure is able to significantly outperform the stronger base model even before convergence (Figures 8a,b). We this conclude that, irrespective of the base model, our approach is able to improve the performance of a synthesizer trained with uninformatively selected examples. Please refer to the PDF for these figures.

We have also added some discussion about other iterated bootstrap training to the paper to highlight these connections to the literature.