Non-Programmers Can Label Programs Indirectly via Active Examples:
A Case Study with Text-to-SQL

For each utterance $u$, APEL solicits indirect annotations and produces a posterior probability distribution $p_{T}$ over programs. The maximum a posteriori (MAP) program is defined by $\hat{s}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\operatorname*{argmax}_{s}p_{T}(s)$.

Most simply, we could train a semantic parser on the inferred annotations $(u,\hat{s})$. Specifically, one option is to use these annotations to fine-tune the seed parser $p_{0}$. However, this may not be practical for a very large pretrained model such as Codex, in which case the annotations could be used to train a dedicated semantic parser from scratch.

In this paper, we evaluated APEL directly by asking whether its inferred annotations $(u,\hat{s})$ are accurate. We measured this by semantic equivalence $\llbracket\hat{s}\rrbracket=\llbracket s^{*}\rrbracket$ (see § 4.2) on a small test set of pairs $(u,s^{*})$ that were annotated by experts (using APEL). One could instead evaluate the actual impact of the inferred annotations on parsing performance, by training a semantic parser (e.g., fine-tuning the seed parser) on a large training set of APEL-labeled utterances, and evaluating that parser on the test set.

Rather than evaluating only the MAP annotation $\hat{s}$, we could have evaluated APEL’s entire distribution $p_{T}$ using the log-loss, $-\log p_{T}(s^{*}\mid u)$, averaged over the test set of $(u,s^{*})$ pairs. This is a more sensitive evaluation, though harder to interpret than exact-match accuracy.

But do we care whether the distribution $p_{T}$ is accurate beyond just its MAP annotation? Yes: one could train a parser $p$ by maximizing its expected log-likelihood

$\displaystyle\mathbb{E}_{s\sim p_{T}}[\log p(s\mid u)]$

(8)

summed over the APEL-annotated utterances $u$. In effect, this treats $p_{T}$ as giving a set of weighted “soft annotations” for $u$, not just the MAP annotation. It is equivalent to minimizing the Kullback-Leibler divergence $\mathrm{KL}(p_{T}\mid\mid p)$ (summed over $u$).

Once an improved parser has been trained on the inferred annotations—either the MAP annotations or the soft annotations—it can be used as an improved prior $p_{0}$ in the update rule 1. This can inform APEL in the selection of future questions.

Furthermore, although APEL’s past questions can no longer be changed, we can now reinterpret the annotators’ responses to those questions, by using equation 1 to recompute an improved posterior $p_{T}$ from the improved prior $p_{0}$. The improved soft annotations from these posteriors can be used to retrain the parser again. This procedure can be iterated to convergence to improve the parser.

This iterated procedure is a principled training method. If soft annotations are used for retraining via equation 8 at each iterations, then it is an instance of the Expectation-Maximization (EM) algorithm Dempster et al. (1977). (If MAP labels are used, it is an instance of the hard or “Viterbi” approximation to EM.) EM is guaranteed to converge to a new semantic parsing model $p_{0}$ that locally maximizes the conditional log-likelihood 6.4 of all of the observed data—in our case, the annotators’ responses $r_{t}$ for all $o$-selection questions on all utterances $u$. Thus, it is simply a log-likelihood training method where the observed data are not direct annotations $s$, but indirect annotations $r_{t}$. It marginalizes over the latent programs $s$.

The annotator model $p(r\mid a,s(i))$ can be jointly retrained with the semantic parser at each iteration of EM, to obtain a higher log-likelihood 6.4. Improving the annotator model in this way should result in more accurate distributions $p_{T}$ at the next iteration of EM, and thus a better semantic parser.

Specifically, when we retrain the parser via equation 8, we can also retrain the annotator model to maximize the expected log-likelihood

$\displaystyle\mathbb{E}_{s\sim p_{T}}[\sum_{t=1}^{T}\log p(r_{t}\mid a_{t},s(i_{t}))]$

(9)

summed over the APEL-annotated utterances $u$. This EM procedure will converge to a maximum of the incomplete-data log-likelihood as in § 6.4.

We could fit a richer model of annotator behavior than the relatively simple one in § 6.4. For example, we could estimate the error rates of individual annotators on different types of questions and program inputs. Intuitively, equation 9 means that we will tend to judge annotators as correct on examples where they agree with the consensus of $p_{T}$ and the other annotators.

Although equation 1 assumed that $p(r\mid s,u,a,i)=p(r\mid a,s(i))$, a rich model could drop this assumption.³³3This means using $p(r_{t}\mid s,u,a_{t},i_{t})$ in place of $p(r_{t}\mid a_{t},s(i_{t}))$ in equations 2, 3, 6.4 and 9. For example, the model might allow that the annotator is more likely to make an error when $u$ is difficult or $i$ is complex. As an annotator’s errors on a given utterance may be influenced by how they answered previous questions, a rich model could even take the form $p(r_{t}\mid s,u,a,i_{1},r_{1},\ldots,i_{t-1},r_{t-1},i_{t})$, where $i_{1},r_{1},\ldots,i_{t-1},r_{t-1}$ are the previous rounds of interaction with annotator $a$.

In our discussion of evaluation thus far, we have not given the semantic parser any partial credit. That is, given an utterance $u$, we have considered any answer other than the correct program $s$ to be equally wrong.

However, more generally, it may be tolerable to find a program whose outputs are correct—or at least close to correct—for most inputs. Let $\mathrm{loss}(\hat{o}\mid u,i,o^{*})$ denote the task-specific loss of predicting output $\hat{o}$ on input $i$ when the correct output is $o^{*}$. The loss of predicting program $\hat{s}$ when the correct program is $s^{*}$ is then

$\displaystyle\mathbb{E}_{i}[\mathrm{loss}(\hat{s}(i)\mid u,i,s^{*}(i))]$

(10)

where the expectation $\mathbb{E}_{i}$ is taken over some realistic distribution of inputs for utterance $u$. This loss function can be used in supervised evaluation.

Following standard Bayesian decision-theoretic methods, the semantic parser itself can aim to achieve low loss. No change to the training procedure is needed. Suppose we have trained a semantic parsing model $p(s\mid u)$ by EM as described above. We now need to extract decisions from this model. If the semantic parser is required to translate $u$ into a single program $\hat{s}$ that will be used for all inputs, then the best program to choose is the program that minimizes the Bayes risk

$\displaystyle R_{p}(\hat{s}\mid u)\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\mathbb{E}_{s\sim p}[\mathbb{E}_{i}[\mathrm{loss}(\hat{s}(i)\mid u,i,s(i))]]$

(11)

This $\hat{s}$ is not necessarily the MAP program. Once $\hat{s}$ is predicted, the output on any given input $i$ is $\hat{o}=\hat{s}(i)$.

In some applications, however, it may not be necessary to choose a single program to use for all inputs. Then the best output $\hat{o}$ to return for input $i$ is the output that minimizes the Bayes risk

$\displaystyle R_{p}(\hat{o}\mid u,i)$

$\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\mathbb{E}_{s\sim p(\cdot\mid u)}[\mathrm{loss}(\hat{o}\mid u,i,s(i))]$

(12)

In other words, $\hat{o}$ is now predicted from $i$ by a consensus of multiple programs.

A model of task loss as in Appendix A can be used to improve the selection of the next question $i_{t}$. Instead of maximizing the expected reduction in entropy (equation 4), we can maximize the expected reduction in the Bayes risk 11.

When $p$ is any distribution over programs $s$ for utterance $u$, define the minimum Bayes risk by

$\displaystyle\mathrm{MBR}(p)$

$\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\min_{\hat{s}}R_{p}(\hat{s}\mid u)$

(13)

At the start of round $t$, we can already achieve a Bayes risk of $\mathrm{MBR}(p_{t-1})$. Once we have the annotator’s response $r_{t}$ to question $i_{t}$, we will be able to update $p_{t-1}$ to $p_{t}$ and achieve a Bayes risk of $\mathrm{MBR}(p_{t})$, where $p_{t}$ depends on $i_{t}$ and $r_{t}$ via the update 2. Thus, the value of information from asking question $i_{t}$ is

$\displaystyle\mathrm{MBR}(p_{t-1})-\mathbb{E}_{r_{t}\sim p_{t-1}}[\mathrm{MBR}(p_{t})]$

(14)

This is essentially the same as the information gain 4, but with task loss replacing log-loss. It is again guaranteed to be $\geq 0$.

Our objective 5 tries to present the annotator $a_{t}$ with a “simple” input database $i_{t}$, as measured by the number of records $|i_{t}|$. However, $|i_{t}|$ is only a crude measure of the time or effort that the annotator must expend to answer the multiple-choice question derived from $i_{t}$. For example, annotators typically find it more difficult to perform arithmetic or to reason across multiple tables within $i_{t}$.

To predict the annotator’s effort on the input database $i_{t}$, we could attempt to simulate the annotator’s mental execution of the true program $s$ on $i_{t}$.⁴⁴4The same simulation could be also used to help model errors in the annotator’s response $r_{t}$ (Appendix A). As we do not know the true $s$, we would need to take the expectation of this effort over $s\sim p_{t-1}$. Mental operations such as adding 3-digit numbers or visually scanning the tables for a specific string could be then given appropriately high costs in the effort model.

In addition, perhaps a question that generates more multiple-choice options requires more effort. To capture this, the effort model could assign a cost not only to computing $s(i_{t})$ but also to finding that answer in the list of options. More generally, the model could attempt to capture mental strategies that do not fully compute $s(i_{t})$ but only do enough work to eliminate most of the options.

Finally, a question generally requires less human cognitive effort if it is related to a preceding question. Querying input database $i$ with utterance $u$ is easier for an annotator who has just queried the same $i$ with a different $u^{\prime}$, or queried a different $i^{\prime}$ with the same $u$.

How would we train the parameters of the effort model? We observe how quickly the annotator answered each $i_{t}$ with $r_{t}$. Taking this time as a proxy for effort, we can train the effort model to predict it from the true program $s$ (which the annotator is presumed to know) and $i_{t}$. If we do not know $s$, we can impute it from the observed responses—that is, evaluate the effort model’s log-likelihood in expectation under $s\sim p_{T}$, analogously to equations 8 and 9. In short, the effort model could be trained by EM, jointly with the other models.

The selection objective 5 manages the tradeoff between annotator effort and information gain by imposing a hard constraint on the annotator effort per $o$-selection question. We could improve this crude selection objective—especially given good models of annotator behavior and annotator effort—by selecting a question $i$ that achieves high “bang for the buck.” This score is given by the ratio of value of information (equation 4 or 14) to the expected effort of acquiring that information.

Both the numerator and denominator of this ratio depend on the specific annotator $a$ who is answering $i$, if the models have annotator-specific parameters. They also depend on the utterance $u$. Thus, the score is actually a property of the triple $(u,i,a)$.

At each step of APEL annotation, we would select a high-scoring triple—one in which we expect annotator $a$ to usefully evaluate utterance $u$’s desired behavior on input database $i$ with low effort. The annotator’s response $r$ then influences the scores of other triples involving $u$. We would stop annotation when no sufficiently high-scoring triple could be found.

In the same way, Bachrach et al. (2012) and Whitehill et al. (2009) model each individual annotator’s capability and each question’s difficulty, learning these parameters through agreement information. Yan et al. (2011) explore these ideas for active learning, similarly routing useful questions to competent annotators. Our experiment empirically finds that each annotator’s ability to answer questions and the difficulty of each domain varies wildly (Figure 10); therefore, future work is likely to benefit from actively selecting who to annotate which utterances.

The procedure described just above will switch freely among utterances and inputs, if it always selects the highest-scoring triple. However, recall that if a followup question on the same utterance or input is eventually to be asked at all, asking it immediately will incur less effort from the annotator. Thus, a good heuristic is to prioritize followup questions over non-followup questions, provided that they score highly enough that it is likely that they will eventually be asked.

More generally: Greedily choosing the highest-scoring question at each step is common in interactive protocols for information acquisition, such as adaptive quadrature or Bayesian optimization Schulz et al. (2018). However, this greedy procedure is in general suboptimal. One could do better at selecting the next question by planning ahead to subsequent questions Chen et al. (2015), though at a higher computational cost.

As shown in Figure 6a, unrestricted random cell values can confuse annotators who are unfamiliar with databases. Therefore, rather than synthesizing completely random values, we now always copy individual cell values from the sample databases (§ 4.1), optionally with minor perturbations such as $\pm 1$ for integer values.

A database record might also be confusing even if its individual cell values are not. For example, the annotator can be confused by counterfactual information where the U.S. is in Asia as shown in Figure (b). Therefore, we prefer to initialize $i^{0}$ with the existing database. The annotator can also be confused by uncommon patterns where two people have the same name but different IDs; therefore, if the existing sample database has unique values in a column, we prefer to enforce that $i$ also has unique values in that column.

Extremely small $i$ frequently leads to undefined denotations. For example, the maximum of zero elements is a special NULL value, meaning “undefined”; this confuses annotators without a computer science background (Figure 6d). Therefore, we always add a small probability mass ($\frac{1}{16}$) of RETURN NULL to the distribution $p$ and normalize the probabilities of the other candidates proportionally, in order to incentivize our algorithm to produce $i$ such that other SQL candidates will return non-NULL values.

Even if the returned value is well-defined, small $i$ can lead to confusion if some operators are not needed to answer the question. For example, in Figure 6e, asking the maximum over one element might appear confusing, as we do not need the max operator to obtain a correct denotation. Therefore, we always add into $p^{\prime}$ a small probability mass of “neighbor queries” Zhong et al. (2020) obtained by dropping aggregation operators and WHERE clauses from SQL candidates in $p^{\prime}$. This incentivizes our algorithm to produce $i$ such that the SQL candidates will meaningfully use their operators.

All the above tweaks make a tradeoff between the informative and the simplicity criteria in some way: we impose restrictions on $i$ or modify $p^{\prime}$ to decrease the annotator effort while sacrificing information gain we can potentially achieve. How do we decide when to apply certain tweaks?

In our paper, we always add small probabilities of neighbor queries and RETURN NULL to $p^{\prime}$ and use cell values from the existing database. We then consider 3 types of tweaks that we apply if possible: 1) $i_{0}$ satisfies the uniqueness constraint, 2) $i_{0}$ is initialized with an existing database, and 3) $|i|\leq 15$ rather than 30. We apply these tweaks if they do not prevent us from succeeding. We define in total $2^{3}=8$ different “configurations” $0\leq c<8$, each of which specifies what subset of tweaks to apply to the algorithm described in § 3. For example, $c=6=B110$ means we apply tweaks 1) and 2). We enumerate from $c=7$ to $0$ until the algorithm from § 3 returns a program input with $\mathrm{IG}(i)\neq 0$. In other words, we start by applying all the tweaks and drop the tweaks gradually until we obtain a $i$ with positive expected information gain.

Consider the utterance “What are the names of properties that are either houses or apartments with more than 1 room?” Should it be parsed as “(house) or (apartment and room > 1)”, or “(house or apartment) and room > 1”? Another example: “Count the number of friends Kyle has.” What to do when there are two students named Kyle?

It is hard for humans to do arithmetic mentally, e.g., find the average of eight 9-digit values. To avoid demanding such computations, APEL should improve the annotator effort model $|i|$ beyond counting the number of records (Appendix B).

Database schemas sometimes omit common-sense constraints. For example, according to common sense, “BIRTHDAY + AGE” should always yield the current year, so sorting by BIRTHDAY ascendingly is equivalent to sorting by AGE descendingly. However, APEL is able to find a database where these two strategies return different outputs.⁵⁵5Even though APEL derives its databases from the original Spider sample database, that sample database contains records that do not conform to this unstated constraint. Such a database is unnatural and confuses humans. A possible solution would be to induce such constraints from the sample database and/or the column names in the schema.

We vary the hyper-parameters in § 3 to test its robustness. Changing 5% to 20%, or decreasing the number of random re-runs, all leads to the same performance of 91%, and the average number of interaction rounds fluctuates by at most 0.05. Additionally, even after increasing the maximal allowed database size $R$ from 15 to 30, we still obtain an average size of 10, since we prefer smaller databases under the same information gain.

In this task, you will be asked to answer questions from several tables.

Here is the overall idea. You will be given a question on the top of the page, several tables on the left of the page, and you need to choose one of the options on the right, that corresponds to the correct answer. In this question, you are asked to “Show name, country, age for all singers ordered by age from the oldest to the youngest.” Therefore, we expect the correct option to list the information about Joe Sharp first, since he is older. We look at the options and B is correct. Notice that A is wrong because it does not list the information for all singers, and C is wrong because it lists the singers from the youngest to the oldest.

After you submit the answer, our system will ask you whether there is anything that appears ambiguous or confusing. We don’t need it for this question now.

Let’s go through some more examples.

In this question you are asked “How many singers do we have?” This is a tricky question. First notice that the tables have changed from before, so you need to re-read the table. Secondly, there are actually two singers, but they have the same name. You should consider them to be two different persons with the same name but different SSN, and hence choose B.

There is a time limit shown at the top of the page, and after 4 minutes the system will move on to the next question.

Takeaways:

• •

  Names are different from IDs. Two different people can have the same name.

• •

  There is a time limit of 4 minutes for each question.

In this question you are asked to find the song names of the singers above the average age. The average age is the mean of these 4 numbers, which is 34.5. The singers John and Rose have age above 34.5, so we can find their songs, which are sun and gentle man, which is D. Use a calculator if you need to!

Also, notice that there are other tables, but they are not relevant to the question. Feel free to ignore them. You can also choose to collapse them if that makes it easier, and you can click the button again to view it.

Takeaways:

• •

  Use a calculator if you need to.

• •

  Not every table is needed.

Here’s the same question and the same table. Let’s say somehow Sun and Gentleman is not one of the options, and then you should report that no answer is correct. Then we will ask you why you think no answer is correct. For example, you can write “gentleman and sun is correct. the average age is 34.5, John and Rose are above this age and have song gentleman and Sun”.

The system asks us why we didn’t choose A, we can answer “sun is by Rose, who is older than 34.5”. Please tell us enough information so that we can know why your choice is correct - for example if you just say “sun is also a correct answer”, it only describes the difference between the two options rather than explaining why it is correct. Giving us more information can help you win more bonus.

Takeaways:

• •

  Choose no option is correct and tell us why when you think no options are correct

• •

  Tell us why you didn’t choose an answer when we ask you to do so.

The question is “What are the full names of all players, sorted by birth date?” First, notice that there are a lot of answers in this case, and you need to scroll down to read through all of them. Secondly, there are a lot of ambiguities: for example, the question didn’t mention whether we should sort from youngest to oldest, or the reverse; secondly, the question does not mention whether the first and last name should be in the same column.  For these reasons, A, B are both correct. C, D are wrong because the question does not ask for birthday information; F is wrong because it only lists one player and G is wrong for including birthday information. Then we can write in the response: “ABE are all correct; not sure if we should sort them from the oldest to youngest or reverse; also not sure whether to put the first and last name into the same column.” But still, make your best guess, let’s say, A.

Then we click submit, and the system asks us why we didn’t choose C. We explain that “the question does not ask us for the birthday and it contains redundant information”.

Takeaways:

• •

  There can be a lot of options. Make sure to read through every of them

• •

  When the question is ambiguous and multiple answers are plausible, tell us why it is ambiguous and what are the plausible answers. But still, first make your best guess and submit.

The question is “Give the names of countries that are in Europe and have a population equal to 80000.” In this fictitious table, Brazil is in Europe and has a population of 80,000. Therefore, the correct answer is A, even though we know that Brazil is in fact in South America. However, it still cannot stop us from answering the question based on the table. Finally, there are many more countries in the world, beyond these three countries in the table, but we should pretend that there are only three countries in the world here.

Takeaways:

• •

  Try accepting the information from this table as much as possible and focus on the part useful for answering the question.

• •

  If something is not present in the tables, pretend that it does not exist.

Here are some more difficult tables.This is a database that contains information about battles and death. The overall description of the databases can be seen at the top of the page, which says: This database contains information about battles, death events, and ships. And then each table has its own description as well. For example, in the ship table, each row contains information about a ship, the 4th row means the ship D was lost in battle with ID 4, and you can look up information about battle 4 in the battle table. To make it convenient for you, whenever you move your cursor to a value, all the same values will be highlighted. Here we notice that according to the 5th row, Ship E was also lost in battle 4.

To view multiple tables at the same time, you can choose to zoom out, like this. Then you can zoom back in, like this. You can typically find this option in the Help panel of your browser. Again, if you think some tables are irrelevant, just collapse them like this.

You don’t have to study the tables in detail, since they will probably change for the next question.

Takeaways:

• •

  You don’t have to study the table content in great detail, since they will be changing.

• •

  Zoom-in/out if you need to. You can find them in the helper panel of your browser.

This question is “Show names, results and bulgarian commanders of the battles with no ships lost in the ’English Channel”.

The question asks for certain battles namely, those that did not lose ships in the English Channel [pause].  Let’s start by finding the battles that did lose ships in the English channel [pause]. Only Battle 5 did; it lost ship C there.  So the other battles, Battles 0 and 7, lost no ships there.  In fact, Battle 0 lost no ships at all, which is why it doesn’t show up in the second table. We find the names of Battle 0 and 7, along with their other information. Therefore, the answer is E. One very common mistake people make is that they ignored the word “no”, and they chose the battles that lost the ship. Be careful and pay close attention to every word!

Notice that there was originally the death table. We removed it from the display to make it easier for you.

The phrase ’Bulgarian commander’ might send you looking for a table that tells you each commander’s nationality. But actually, Bulgarian_commander is a column in the battles table. Presumably this table lists battles that Bulgaria fought. Each battle had two sides, and this column is naming the commander for the Bulgarian side. You don’t have to fully understand how the tables are set up, but you should figure out enough to answer the question.

Just to repeat, to make it easier for you to process this information, whenever your cursor moves to an ID or a piece of text, its counterpart in other tables will light up; whenever you click on a text, the counterpart in the answer will also be highlighted.

You can also choose to merge the tables. After you merge the table, there will still be two tables. Each of the rows in the battle table will still contain information about a battle, and each of the rows in the ship table will still contain information about a ship. However, the battle information where the ship is lost is merged into the ship table. Notice that battle 0 will not appear in the ship table, because no ship is lost in the battle, so be careful when you try to interpret the merged table. Click unmerge to recover to the original view.

Finally, if you forgot what each table means, you can always view them here.

Takeaways:

• •

  Pay close attention to how the question is being asked. They might lead to different options. Many mistakes people make are because they did not read the questions carefully.

• •

  Sometimes we choose not to show you certain tables and columns if we know for sure they are not needed.

• •

  Use the highlight functionality if that helps you to reason across tables.

• •

  Use the merge functionality if you need to. Each table will contain information about the same object/entity, but the information about its related objects will be pooled in.

The question is “List the name and date of the battle that has lost the ship named ‘Lettice’ and the ship named ’HMS Atalanta’.” Since there is no ship named “HMS atlanta”, there is no battle that lost both of these ships. So you should choose A, “no result found”.

Takeaways: Choose no_result_found if no answer satisfies the question.

To summarize, here are a couple of things you need to remember to answer the questions correctly:

• •

  Pay close attention to how the question is asked; most mistakes are made because of not reading the question carefully.

• •

  Accept the information in the table even if they are changing and might be different from the knowledge you have for the real world

• •

  IDs are different from names

• •

  Some questions might have a lot of options to choose from and you need to read through all of them.

To make it easier for you to answer the questions:

• •

  Use the highlight and merge operations when you need to

• •

  Use a calculator if you need to

• •

  Zoom out to fit the tables into the screen and prevent scrolling.

• •

  Not all table or column is needed to answer the questions

For freeform response:

• •

  Reporting ambiguities or tell us why the question is confusing only if you need to

• •

  Explaining why you did not choose another option when we ask you. Giving us more information can you help you win more bonus.

We used the dataset from Ye et al. (2020), which aims to synthesize a regular expression from a natural language description and a few strings that should be accepted and rejected by the regex. For example, an utterance $u$ could be

“This is a list of three comma separated strings, where each string must be formed by the substrings "cz" or "rzq" followed by one to four digits.”

and the corresponding program $s$ is

“concat ( concat ( or ( const(<cf>), const(<rzq>)),repeatrange(<num>, 1 ,4)),concat(<,> ,concat ( concat ( or ( const(<cf>), const(<rzq>)), repeatrange(<num>, 1, 4)), concat ( <,>, concat ( or (const(<cf>),const(<rzq>)), repeatrange(<num>, 1, 4))))))”.

The program $s$ maps from any input string $i$ to a boolean output of $1$ or $0$. Thus, an $o$-selection question simply asks whether the string $i$ should be accepted or rejected.

We used the development split to prompt GPT-4 (OpenAI, 2023) to create the seed semantic parser. We tested APEL on the test-inclusion split, where the utterances come from the same annotators who annotated the development split.

We prompted GPT-4 with few-shot demonstrations to create a seed semantic parser. We sampled 50 demonstrations from the development split to simulate a small “training set” of expert labels. For each utterance $u$ we sampled a candidate program from the seed semantic parser 50 times, where each time we randomly selected 20 demonstrations from the 50 dev split demonstrations as in-context demonstrations. We then automatically filtered out candidate programs that were syntatically invalid and merged semantically equivalent ones (semantic equivalence of regexps can be tested exactly). Finally, we define $p_{0}$ to be the empirical distribution of the top-10 equivalence classes. The top-1 accuracy (seed parser) is 64% and the top-10 accuracy (ceiling) is 77%.

We wish to choose among several candidate programs (or more precisely, equivalence classes). For each pair of candidate programs $s_{1}$ and $s_{2}$, we sample 200 program input strings $i$ such that $s_{1}(i)\neq s_{2}(i)$, using the efficient implementation from Ye et al. (2020). We then collect all such input strings across all pairs of candidate programs, find the ones with the highest information gain, and break ties by choosing the shortest one as a proxy for simplicity.

To evaluate whether the above procedure is effective in generating simple and informative program input, we consider a baseline that only generates an input string that would be accepted by the highest-ranking candidate regex, again using the implementation from Ye et al. (2020). Intuitively, this baseline tries to check the highest-ranking candidate program, by determining whether a string that it accepts should in fact be accepted. The response (if assumed to be correct) may eliminate some of the programs.

Our information gain method, by contrast, actively tries to distinguish among the candidates. It hopes to gain up to 1 bit of information about the correct candidate (this is the maximum information that can be derived from the annotator’s 1-bit response). An input string has IG $\approx 1$ bit if the candidates that would accept that string currently have about half of the probability mass. In that case, either response (1 or 0) will eliminate about half of the candidates (cf. Littlestone and Warmuth, 1994).

That said, any input string $i$ sampled by our procedure will distinguish between two of the candidate programs, and hence will have positive information gain. The annotator’s response $r$ (if assumed to be correct) will eliminate one of those two candidate programs, and perhaps others. Thus, it will take at most 9 rounds of oracle annotation for us to rule out 9 incorrect equivalence classes from our original 10 classes, thus achieving the candidate ceiling (§ 4.4), regardless of which sampled input string we select at each round.

After interacting with a simulated annotator for at most three rounds with an oracle annotator as in § 5, the APEL accuracy reaches the ceiling of 77% and outperforms the seed parser. In contrast, the baseline only achieves 68% accuracy after three rounds, thus illustrating the importance of optimizing information gain. Finally, APEL uses input strings with an average length of 5.3, while the baseline’s average is 11.6; this suggests that optimizing for simplicity is successful.