Non-Programmers Can Label Programs Indirectly via Active Examples: A Case Study with Text-to-SQL
Authors: Ruiqi Zhong
Charlie Victor Snell
Dan Klein
Jason Eisner
Venue: EMNLP 2023 Main (2023)
Keywords: Semantic Parsing; Annotation; Code generation
TL;DR: We introduce APEL, a semantic parsing annotation framework that lets non-programmers indirectly select the correct program by asking them which output would be appropriate for a carefully selected input.

Abstract: Can non-programmers annotate natural language utterances with complex programs that represent their meaning?  We introduce APEL, a framework in which non-programmers select among candidate programs generated by a seed semantic parser (e.g., Codex).  Since they cannot understand the candidate programs, we ask them to select indirectly by examining the programs' input-ouput examples. For each utterance, APEL actively searches for a simple input on which the candidate programs tend to produce different outputs. It then asks the non-programmers only to choose the appropriate output, thus allowing us to infer which program is correct and could be used to fine-tune the parser. As a first case study, we recruited human non-programmers to use APEL to re-annotate SPIDER, a text-to-SQL dataset. Our approach achieved the same annotation accuracy as the original expert annotators (75%) and exposed many subtle errors in the original annotations.

Non-Programmers Can Label Programs Indirectly via Active Examples:
A Case Study with Text-to-SQL
Ruiqi Zhong"! Charlie Snell Dan Klein' Jason Eisner²
University of California, Berkeley" Microsoft Semantic Machines
{ruiqi-zhong, csnel122, (lein](berkeley) edu
wwweeiieeiiiooooooooee com com
Abstract
How old is the youngest person from section P?
Can con-programmers annotate natural lan- guage utterances with complex programs that represent their meaning? We introduce APEL, a framework in which non- programmers se- among candidate programs generated by seed semantic parser (e.g.. Codex). Since they cannot understand the candidate programs, we ask them to select indirectly by examining programs' input-ouput examples. For each ut- terance, APEL actively searches for simple input which the candidate programs tend to produce different outputs. It then asks the non- programmers only to choose the appropriate output, thus allowing gram is correct and could be used to fine-tune the parser. As a case study, we recruited human proggrrrrrmmess to APEL re-annotate SPIDER, a text-to-SQL. dataset. Our approach achieved the same annotation accuracy as the original expert annotators (75%) and exposed many subtle errors the original annotations.
Generate prior over
candidate list of programs using Codex with lew-shot
SELECT MIN (Age)
from People
SELECT MIN (Age)
People
NHERE Section
Synthesize program input
Name Age
Section
Eren 26
P
infer which pro-
i=
Mikasa
23
P
Reiner 19
M
Ask the annotator which output is correct based on u and
Reweight
sx(i)
x Annotator
safi j= 23
response
1 Introduction
Semantic parsing often aims map a natural lan- guage utterance to a program, which can exe- cuted on an input (Kushman and Barzilay, 2013). For example, for the utterance "How old is the youngest person," we can map to the SQL program SELECT MIN(AGE) FROM PEOPLE, execute it on an input database, and return the output answer. Lan- guage models like Codex often achieve substantial few-shot performance (Chen et al., 2021a). How- ever, user-facing applications often involve novel phrases or domain-specific values unseen during pre-training or generic instruction-tuning, so the model still needs more labels for training. Since hiring programming experts to label training data is costly, ask pro-programmers to label them?
Figure I: The outline of APEL. The orange background indicates what the annotators can see they only need select which output (19 23) is correct by read- ing the question and the database i. We downweight program candidates that are inconsistent with the anno- tators' response. Figure 3 illustrates our criteria for i.
ments, prompting it with few demonstrations that solicited from expert programmers. We now want to label additional training data. To construct the correct program for new utterance, APEL uses the seed parser to generate a list of candidate pro- grams with prior probabilities (Figure top), and then asks non-programmer annotators to indicate which candidate is correct.
We introduce APEL, framework that indirectly labels programs with pro-progrrmmmr responses on carefully constructed input-output examples. APEL must be seeded with a moderately good se- mantic parser: we use Codex for this our experi-
However, we cannot ask the annotators select the correct program directly, since even expert pro- grammers might find this challenging (Figure 2). Instead, APEL obtains information indirectly by asking questions about how the program should be-

---

Utterance a: Find the first name students who have both cat and dog pets.
SELSCT MEE (Ago)
Erom People
Name
Age
Section
Ro SELSCT MEE (Age) from People WHERE Section "p"
Eren
Mikasa
23
P
2015 bane pet. Asi E2 on "i.etuud e t2.ereid
pacc 12 c.Jpacid 12.petid pettope
Name Age Section
Armin
19
Sy
SHEERSBCO
Annie
18
ERot ptudent AS K.1.
GEEACE
Mikasa 23
P
Million Rows Omitted m
10upprtio wenser tl.petagee
Not N1(Ex)= =
Not Simple! sx(ia) = 18
Informative!
S2(8x) = 23 v
S2(in) = 19 /
reor Stusees
NEEER Seain
FRME student 1d
.015 heu pot 15 72 be viuuuu Micoteid
Figure Informativity and simplicity guide our search for useful input. is not informative since knowing the correct output does not tell us which program is correct. vi not simple since the input is too large for humans to find the correct output. Figure I shows an ideal input.
52
2013 20ta oR ipenidd portid
"cac EMER05R07
SELACT ri. sttlt
student As 0023
23. 23.potid 12.petid KIEDE 13.pettype Mog')
Figure 2: APEL needs to obtain information about whether 81 or 82 is correct; it is hard even for experts to directly select the correct one by eyeballing. The error of 81 is subtle: it finds the first names of the students who have dogs and the first names of the students who sets of first names.
2018) development set ($6). According to new carefully constructed gold standard, we achieve the same accuracy the original SPIDER annotation performed by database experts (75%) and also sub- stantially outperforms the top-1 accuracy of Codex (59%). APEL also exposes subtle errors made by previous experts, which we analyze in $6.6.
have cats, and intersects these APEL can reveal this error by asking about a tiny stu- dent database in which Alice Jones owns dog while Alice Smi th owns cat. As student named Alice owns both, the annotator will select an output o that does not include Alice, implying that $1 is incorrect.
APEL is a preliminary step towards enabling non-programmers to label utterances with arbitrar- ily complex programs. Applying it new seman- tic parsing tasks still faces some bottlenecks: it quires a seed semantic parser with reasonable top-k accuracy and an efficient procedure to find simple and informative program inputs ($7). However, these bottlenecks might be alleviated by future ad- vances in semantic parsing and program synthesis. With these advances, we hope APEL can facilitate non-po cun-prorrammerss to label programs in a broader range of applications in the future.
have. We synthesize a program input, execute the candidate programs on it to obtain list of outputs, and ask the annotators which output is correct given the utterance and the input. We could eliminate the programs that returned other outputs, but annota- may make mistakes, so instead downweight them via Bayes' Theorem (Figure bottom). To pin down the correct program, we iteratively reduce the entropy of the distribution over candidates by repeating the process with more synthesized inputs.
To reduce annotators' workload, we propose an algorithm to search for program input that max- imizes the expected information gain of the anno- tator's answer ($3), subject the constraint that the input is simple enough for the annotator to reason about the correct output easily (Figure 3). Since our method resembles the programming by example (PBE) framework (Lavrac and Dzeroski, 1994) and learns an underlying program by actively choosing which examples should be labeled, we call our framework APEL-Active Programming by Examples using prior derived from natural Language utterance.
Framework
APEL aims to enable humans to indirectly annotate natural language utterances with programs. Here we use text-to-SQL case study.
2.1 Outline of APEL
Let u be a given utterance and e known database schema, which specifies the table names, column names, and the constraints on value types, unique- ness, and foreign keys. We want to synthesize SQL program s that captures the meaning of and works properly for any database with schema Figure illustrates our pipeline. We first feed e and u to a seed semantic parser (e.g. Codex with
Non-Programmer Annotator Study, As a case study, we use APEL to label SQL programs. We built an annotation GUT based on APEL and re- cruited Il non programmerss to label a random sub- set of 240 utterances from the SPIDER (Yu et al.,
'The corrected unnotations and our code for searching for informative and simple databases are on our githuh: https: //github. cwt.b/.cooaaiaaaaeeeo//ee coom/ruqiiizee aeriiizhong/aee Chhong/EMLPP22 EENLL23-APPE P2P-APEL.

---

prompt) to generate prior distribution p over list of SQL programs s. We then 1) synthesize an input database i, 2) execute the list of programs on i to obtain a list of program outputs o, and 3) display u, i, and the outputs to an annotator a. The annotator generates response indicating which output they think is correct. We will then raise the posterior probabilities of the candidates such that s(i) r, i.e. returns r when executing on i. Since ask the annotator select the correct output of program given an input, we call our questions "o-selection questions."
is both informative and simple. Informative. Our belief as we enter round is Pt-1- Once we observe the annotator's response Tt, we will be able to update it to Pt- This will achieve an information gain of H(p 1) H(p:), where the Shannon entropy H of a distribution over programs characterizes its remaining uncertainty about which program is conrect.
choice However, Pt will depend not only of question in but also on the annotator's response r (equation (2)). We do not know r, yet, but our current belief is that it will be distributed as
To formalize, the posterior distribution over the program 8, once we observe the response r, is
Pt-1(Te) = Pt-((()) p(r: ar, s(t))
(3)
So our expected Information Gain from asking i, (1)) H(pt-1) ( (4)
p(s| u, i, x p(s u, a. a) p(r s, a. p(s u) p(r a, si))
(I)
where p(s u.) was the prior from the seed parser. Here p(r a, s(i)) models annotator behavior: the probability that annotator would have responded with if
where the expectation is taken under distribution (3). This is high if the candidates that are most plausible under pt-1 tend to return different out- puts (it) and hence different annotator responses Tt, making тe informative about s. By contrast, i in Figure 3 left would yield an uninformative response (IG = 0).
correct implementation of u and therefore (i) were the correct output. To the extent that annotators are accurate, this Bayesian update increases the probability of the correct program.
We can ask more o-selection questions to obtain further information about the correct candidate and improve the posterior. If desired, different rounds may use different annotators. For each u, we define
Simple. We would like to avoid presenting the annotator with complex inputs such as the large database in in Figure 3 right. The correct response might be informative, but determining it would quire too much human effort. We crudely model the effort required for is the number of records |ée].
(s( def p(s u. 01, fi,,,,,
r() x (0-1(6) at, s(:))
The next section proposes a heuristic to synthe- size a simple informative database in given schema sample database with schema and distribu- tion pt-1 over SQL programs.
to be the posterior after > 0 questions, with Po p(s u) being the prior. Letting T denote our total number of questions about u, our final posterior is pr.
3 Optimizing the Input Database
Evaluation. We output as our annotation the most probable SQL candidate & according to Pr, and compare it to a gold standard. To show that our framework is useful, &, needs to be correct more often than šo. the most probable SQL candidate according to the seed semantic parser p(s u). Relation to Weakly Supervised Learning. Ap- pendix A explains how the "soft annotations" pro-
We attempt to maximize the expected information gain IG over all databases that conform to the given schema e and have at most R total records, where R = 30 in our case study. Formally, we search for
= argmax argmaxIIGp.-1 IGpp,((pp) (4r). sdl/SR
(5)
vided by the full distribution pr could be used to retrain the semantic parser p(s u). These im- proved models would turn improve the estimate pr (i.c., an EM algorithm).
When multiple databases have the same IG, we break ties by favoring the smallest database. Since t and p are fixed during the optimization process, will write IG(i) instead of IG (ix) for short. Our method can be summarized as "fuzz-then- drop." Fuzzing (Miller et al., 1990) is an estab- lished practice in software testing, where an algo- rithm generates a large number of random program
2.2 Criteria for Synthesized Inputs
To generate an o-selection question on round t, APEL needs to synthesize an input database 4 that

---

inputs to search for an input that satisfies a property or reveals bug. In our casc, we want search for an input database that maximizes the information gain. Therefore, we first perform fuzzing by ran- domly generating a large number of large datahases as in Zhong et al. (2020) see Appendix C for fur- ther details-and keep the database x that maxi- mizes the expected information gain IG)) We then drop records from 10 satisfy the simplicity criterion for L iterations.
SQL dataset with 1034 utterance-SQL pairs dis- tributed under the CC BY-SA 4.0 License. The development set divided into 20 domains, each with a distinct database schema c, a collection of utterance-SQL (u, 8) pairs, and a sample database. We split the 1034 (u, pairs equally into vali- dation split and an evaluation splif. We used the validation split to tune our annotator interface ($6), develop our fuzz-then-drop algorithm ($3), and prompt Codex ($4.2) create seed parser. We used the evaluation split evaluate APEL with simulated annotators ($5), and from these drew a random subset of 240 utterances balanced across domains to conduct our human evaluation ($6).
For each iteration e of dropping records, we ran- domly drop 5% of the records from i' to obtain z4+1 If this results in a less informative database, i.e., IG(;++)) < (t").. we are willing to retry up to 20 times in hopes of randomly finding an j that is at least as informative as if; if we fail in all 20 tries, we keep the best of the 20 despite the decrease in IG. Of the databases smaller than R that we encountered during the iterations, let i be the one with the highest IG: def
To make our evaluation more reliable, we 1) corrected the sample database to conform to the schema c and updated the test suite correspond- ingly (Appendix D), and 2) established a new gold standard by correcting errors in 61 out of these 240 SQL annotations ($6.2). The corresponding author of SPIDER endorses our corrections (T. Yu, p.c.).
argmax IG(1)
(6)
4.2 Obtaining the SQL Program Prior po
Since our procedure is randomized, we repeat it 3 times, and let i* be the i with the largest IG(i), breaking ties as before in favor of smaller i. Finally, we simplify i" by dropping tables and columns that were not mentioned by any SQL candidates in p.
We generated prior over SQL program candidates using the Codex (Chen et al., 2021b) language model with few-shot prompting. Given an utter- ance u with a schema c, we created the prompt (Ap- pendix E.1) by concatenating a linearization of e with eight distinct (ug, sk) pairs from the validation split associated with the same schema c, and finally the utterance itself. Some (ux, sk)) pairs were chosen randomly while others were chosen because ug has the highest TF-IDF similarity to We ran- domly sampled 200 prompts for by choosing dif- ferent (ug, 8k) pairs, and for each prompt, we asked Codex to generate 20 completions (SQL programs) and filtered out non-exccutable candidates. To pre- vent surface form competition (Holtzman et al., 2021), we then merged approximately semantically equivalent candidates by finding sets of candidates that return exactly the same outputs on IK random databases, using the implementation from Zhong et al. (2020). We define Po be the empirical distri- bution in our sample of the 16 semantic equivalence classes that were most frequent the sample. Thus, each & in $2 represents an approximate equivalence class rather than a single program.
Our procedure of dropping records from a large informative database is heavily inspired by Miao et al. (2019), which, given a database i such that (1) * (i), provably finds the smallest subset of records in i such that programs 81 and 82 return different outputs. However, their algorithm works only for restricted family of SQL programs and cannot be adapted to optimize information gain. Our procedure does not provide any provable opti- mality guarantee, but more flexible and practical.
In practice, simply applying the above proce- dure can generate unnatural databases and lead to vacuous SQL execution, confusing the annotators. In Appendix C, we illustrate several typical confu- sions (Figure 6) and explain how we fix them.
4 Experimental Setup
We describe the dataset used benchmark APEL ($4.1), how we obtained the prior over SQL candi- dates ($4.2), and our evaluation metrics ($4.4).
Treating the original SPIDER annotation the ground truth, the top-1 accuracy of po on the en- tire development set is 72% and the top- 16 accu- racy is 94%. These numbers are not comparable
4.1 Dataset
We benchmarked APEL on the development set of SPIDER (Yu et al., 2018), an English text-to-

---

prior works, which usually evaluate on unseen database domains in a zero-shot manner (harder than our setting) but do not predict string literals and DISTINCT keywords, which we need for execu- tion. Appendix E.2 includes more details on top-k accuracy (sometimes also referred to as pass @ass@AA k)). Note that the seed parser could be further im- proved, e.g. with better models (OpenAl, 2023) or prompts (Zhou et al., 2023). However, these improvements are complementary to APEL, whose goal is to improve over the seed parser with non- programmer responses. We design our evaluation metrics based on this goal in the next section.
easy
med
hard
extra
all
Ceiling
0.98
0.96
0.98
0.81
0.94
Codex
0.87
0.80
0.56
0.45
0.72
OrigDB
0.98
0.90
0.83
0.66
0.86
APEL 0.93
0.95
0.97
0.75
0.91
Table The description of the metrics can be seen $4.4. APEL means using databases generated using the method descrihed in $3 while Orig directly uses the sample database from SPIDER. APEL significantly outperforms both Codex and OrigDB with p-value x 10-$, indicating that both APEL and our database generation algorithm are effective.
4.3 Separation of Annotators
marked APEL the entire evaluation split by sim- ulating oracle annotator who always responds correctly by choosing the output of the correct SQL program and assuming that the SQL, annotation provided by SPIDER always correct. Addition- ally, to evaluate our database generation algorithm in $3, we compared to OrigDB, an ablated variant of APEL that directly uses the sample database from the original SPIDER dataset. Table I reports the candidate ceiling, the Codex accuracy, and the accuracy for both OrigDB and APEL.
When optimizing the next input i to show to a given annotator a ($3), we measured its IG by condition- ing on the previous responses from only. That is, we treated each annotator as if they were the first an- notator. (Indeed, all annotators for u the same first question.) This approach reduced the amount of information about u that our total questions could extract, but it also reduced the variance of our experiment by running multiple independent (but shorter) annotation sessions on u. To compute the final py for u, we still aggregated the responses from all annotators using the Bayesian formula (2).
With rounds of intcractions, APEL accuracy (91 1%) substantially improves on the Codex ac- curacy (72%), validating the effectiveness of our framework; we achieved this by interacting with oracle annotator for 1.8 rounds average. Compared to OrigDB (86%), which uses the sam- ple databases from the original SPIDER dataset interact for round, APEL's database generation method leads to higher accuracy since it allows multiple rounds and optimizes for information gain. Furthermore, averaged across all utterances, the databases generated by APEL contained altogether 10 records across all rounds-whereas the OrigDB databases contained on average 33,295 records and would be impractical to present to human anno- tators. These results highlight the need for the databases be both simple and informative.?
4.4 Evaluation Metrics
We report the following statistics to evaluate APEL:
Codex accuracy: how often is the argmax of Po correct? This baseline reflects the top-1 accuracy of the seed semantic parser.
APEL. accuracy: how often & (the argmax of pr) correct? This reflects the improvement due to our APEL annotators.
candidate ceiling: how often does the sup- port of po contain correct program? This reflects how much APEL is bottlenecked by the seed semantic parser, whose top 16 candi- dates form our candidate list.
If APEL is effective, we should see that the APEL accuracy is higher than the Codex accuracy. Since SPIDER categorizes its utterances by diffi- culty (casy/medium/harr///
Appendix H provides further information on the database sizes, the number of interaction rounds, and the robustness of our database generation method under different hyper-parameter choices.
we report the ac- curacy for each difficulty level. Next we evaluate APEL with both simulated and human annotators.
6 Human Evaluation
5 Automated Simulation Evaluation
We evaluate the effectiveness of APEL with real human annotators. We built an interface designed
To automatically test the effectiveness of APEL without additional human annotations, we bench-
AAPEL achieves % accuracy with I round of interaction.

---

6.2 Gold Standard Annotation
To establish clean gold standard, two of the au- thors annotated all 240 utterances using our own APEL system. Whenever our two responses to a APEL question were different, we reached a con- sensus through discussion.
We closely examined the o-selection questions where our consensus response did not match the output of the SQL. program provided by SPIDER, and corrected SPIDER'S program if we felt that our response was strictly better. To avoid biasing against the original annotations, we stuck to the original ones whenever there were ambiguitics, and we double-checked each corrected annotation by additionally writing down reasons why we felt it was better. As mentioned in $4.1, we ultimately corrected 61 out of the 240 SQL annotations. $6.6 analyzes these corrections in greater detail.
Figure screenshot our annotation interface ($6. I). Appendix J and Figure 11 include more details.
to be user-friendly ($6.1) and used ourselves to establish gold annotations for 240 utterances ($6.2).
We then recruited 11 con-programmer subjects to annotate the same utterances ($6.3), aggregated their responses by learning model of annotator be- havior ($6.4), and benchmarked their performance with the newly established gold standard ($6.5).
6.3 Non-Programmer Annotation
We analyze errors by SPIDER expert annotators in $6.6, qualitative feedback from our subjects in $6.7, and errors made by our subjects in Appendix F.
Annotation Unit. We split the 240 utterances into
8 units. Each unit contained 30 utterances across 4-5 database domains and proved to take 1-2 hours to annotate with our interface. For the annotator behavior model p(r a, s()) in equation (1), we assumed that every annotator would respond cor- rectly with 0.7 probability and would otherwise select a response uniformly at random.
6.1 Annotation Interface
Figure 4 shows an example o-selection question in our interface, which displays the utterance on the top, the database on the left, and up to M 6 distinct outputs
Recruiting Non-Programmers. As annotators. we recruited 11 university students who 1) were not pursuing/had not received Computer Science degree and 2) had prior experience with SQL. Bach annotator could annotate any number of units (from 1 to 8) as they wished, but had to annotate them fully. For each unit we rewarded them with 515 as a base payment and $5 ($10) bonus if their response agreed with our corrected gold standard > 85% (95%) of the time. We received 20 units of annotation in total, and hence each utterance was examined by 2.5 annotators average. We asked each of them 1.84 questions about the utterance and the databases that we presented contain only 8.05 records on average. We visualize the distribution of the number of questions for each utterance and the database sizes for each question in Figure 5. Participation Procedure. We asked each anno- tator 1) sign consent form participate in the study, watch a 12-minute video tutorial that contains our annotation instructions and explains the basics of foreign and primary keys, and 3) complete the annotation task. The tutorial can be
the right in random order, followed by "none of the above" option; generally, an output may be a string, a number, or a table. The annotator can also use an open-ended response field to optionally report that the question is ambiguous or confusing; we did not use these open-ended responses during data collection, but future work could potentially condition them in equation (2) (along with the multiple-choice responses).
To reduce the annotators' cognitive load, when the mouse pointer is over cell, our interface high- lights that cell along with all other cells of i and of the outputs that have the same value. Appendix J describes more features of our interface.
We asked each annotator up to consecutive questions for each utterance u, stopping the inter- action after
2 questions if some candidate
already has p. (s) > 0.9, or our heuristic ($3) fails to find an appropriate database for the next question.

---

Evaluating Annotators
easy
med
hard
extra
all
Ceiling
0.91
0.91
0.92
0.69
0.88
Fraction ucsoanccs
Freection of interactions
SPIDER
0.93
0.78
0.63
0.50
0.75
Codex 0.78
0.65
0.43
0.36
0.59
APEL
0.83
0.80
0.73
0.47
0.75
Table 2: Similar to Table except that we now use the gold standard from $6.2 and also report the annotation accuracy of the original SPIDER dataset. APEL signifi- cantly outperforms Codex (p-value 10-3).
Rumber
Database
Figure 5: The distribution database sizes (left) and number questions (right) for the human evaluation.
As Appendix A explains, one way to maximize equation (7) is use EM algorithm that alter- nates between imputing the unknown for each utterance (using pr) and re-estimating the anno- tator error model based on these imputed "gold" answers. Appendix also discusses how the anno- tator error model could be enriched.
seen at https: https:/yooutt.bb//HLLLL www-Mee/MM2M11111111 and an example unit of the annotation task can be tried http://35. 225. 26. 420000000000000000000 10m00044______..111_________
6.4
Learning an Annotator Behavior Model
After collecting the annotations, used them to improve $6.3's naive model of annotator behavior p(r a, s()) by learning parameters on for each annotator a and 3g for each SPIDER domain For a given a and d, the chance that the annotator answers at random is no longer fixed at 0.3, but is modeled as (aa + 5a b), where is the logistic function and b is a bias term. Larger aa and Sa predict higher error rates.
6.5 Results
We present the results in Table 2. APEL (75%) is effective, since it significantly outperforms Codex (59%) with p-value 10 under one-sided paired t-test. APEL leads the highest improve- ment for utterances for medium hard difficulty levels, implying that APEL most effective when the utterances are hard enough so that there is still room for improvement, but not too hard to con- fuse the non prn-progrrmmer annotators. Additionally, APEL with non- con-prorraamerss is on par with pre- vious database experts without the help of seed parser. We next analyze the errors made by previ- ous database experts.
We maximize the incomplete data log- likelihood
L, logp(r1......................... ... .T 11. ii))
T
= log Σ (s) II p(re at, s(t))
(7)
summed over utterances u. Since we explicitly model the annotator behavior, L, sensitive to domain d of u and the annotator a who answered the question about ig- Just as in other adaptive crowdsourcing research, we do not assume access to the gold value of Our behavior model will predict lower annotation tend agree with other annotators and with Codex.
6.6 Subtle Errors by Database Experts
APEL helped us identify annotation mistakes in the original SPIDER dataset ($6.2). We categorize and present them below to demonstrate where APEL is most helpful. The corresponding author of SPIDER agrees with analyses (T. Yu, p.c.).
rate for those who
Interpreting Database Schema Properly. Sup- pose each row contains information about an orchestra, including the year the orchestra was founded and its associated recording company. For an utterance "Which recording company was founded the earliest?", the correct annotation under this schema should be "Not enough information to tell". Neither SPIDER nor APEL currently supports this annotation option, though our human anno- tator reported this issue their open-ended feed- back. SPIDER annotates this utterance incorrectly as SELECT company from TABLE WHERE YEAR
Overall, our annotators chose the correct option 72% of the time. To evaluate our unsupervised annotator model, we compared its predicted proba- bility of a correct response on each utterance to the 0/1 indicator of whether the annotator did select the correct option. See Appendix I for visualization. Our model achieves an AUC ROC score of 0.68 and MSE error of 0.185. For comparison, a simple supervised model that always predicted the true overall probability of 72% would achieve an MSE error of 0.20.

---

(SELECT MYARYEAR) from TABLE), which looks plausibly correct but actually finds the recording company of the parliest-founder orchestra.
Difficulty: While most questions are straight- forward, some require onerous computations (e.g., requires adding 170115 and 50456). Even though we set up a time limit for each question, these questions consumed a lot of mental energy. Future work could include an option for the users to skim through all the questions and solve the easier ones first. Vagueness: Some utterances were inherently vague. Consider the utterance "Count the num- ber of friends Kyle has." what to do when there are two students named Kyle? Without external affirmation that these questions were indeed vague, some subjects wasted too much time guessing how to interpret them. Future work could elicit confidence ratings, rather than choosing discrete option.
Handling All Allowed Values. The annotated SQL should behave appropriately on all plausible cell values. For example, when we are asked about the maximum value in column that allows NULL cells, prefer SQL. that skips any NULL cells and returns the maximum of the actual values. As another example, if the utterance is "How many countries have a republic government povernmentform..""" the "Republic" will ignore any countries with the government form "Federal Republic"; the correct annotation should be WHERE GOVERNMENT LIKE "XRepublicx". INNER JOIN vs. LEFT JOIN. Suppose the utterance is "List singer names and number of concerts for each singer." and the database contains table of singers and a table with records (s, c) if singer performed in concert c. The SPIDER annotation is incorrect because it uses INNER JOIN, which fails to return singers with count O. Ties for Extremals. For the utterance "Who is the youngest person?". the SPIDER annotation is SELECT NAME FROM PEOPLE ORDER BY AGE LIMIT 1. As APEL discovers, case ties, humans prefer SQL that will return all of the people who have the smallest age, rather than just the first one.
clause WHERE GOVERNMENT
Related Work and Future Directions
Our framework can potentially generalize from text-to-SQL to other semantic parsing tasks. The SQL program 8 can generalize to other types of executable semantic parses, the input database i can generalize to any well-typed input, and the database query result = s(i) can generalize to the intended effect of on i. Applying APEL to new task would require with high top-k accuracy, and an algorithm find simple informative program input i. These problems are related to semanntc parsing and pro- gramming by example, respectively. We now dis- cuss how those two lines of research benefit from APEL and also how they could make APEL more powerful in the future.
seed semantic parser
Remark. Since most of the text-to-SQL models had low performance 3 years ago, Yu et al. (2018) favored short and plausible SQL annotations to make learning easier. These annotation conven- tions were shared between training and test sets to form a coherent structured prediction task (in- ternal validity). Now that structured prediction is working well enough that the predictions could be used real-world settings, we should turn to as- suring that the SQL annotations actually have the desired effects (external validity). APEL can help in establishing the new gold standard ($6.2).
Semantic Parsing. Semantic parsers have im- proved significantly over the past decades (Zettle- moyer and Collins, 2007; Scholak et al., 2021a). Recent pretrained models can perform the task without task-specific architectures (Scholak et al., 202 even in zero/few-shot manner (Shin et al., 2021; Rajkumar et al., 2022).
6.7 Qualitative Feedback
However, collecting semantic parsing datasets is still challenging since it requires experts. Wang et al. (2015) addresses this by synthetically generat- ing logical forms, using templates to explain them in natural language, and asking crowdworkers to paraphrase them. Still, the paraphrases usu- ally restricted in linguistic diversity (Larson et al., 2020). Another line of research (Yao al., 2020; Elgohary et al., 2020; Mo et al., 2022) tries to learn from user interaction based on the surface form
We informally interviewed some of our subjects to obtain feedback about APEL. Here is some ex- ample feedback that indicates future room for im- provement:
Boredom: Some subjects complained that the annotation process was boring and they would not want do it second time. Future work can design better UIs and interactions to make the annotation more engaging.

---

information, e.g., whether a program refers spe- cific fields. However, their assumption that non- expert annotator can recognize the true program via paraphrases is unrealistic when programs have complex semantics. In contrast, APEL allows non- programmers to indirectly label text-to-SQL data via input-output examples.
evaluate the program ouipuls (Chen al., 2023). Prompting large language models to evaluate their own outputs is a widespread idea. Schick et al. (2023) rerank ad hoc programs generated by a lan- guage model based on whether their outputs in- crease the probability of observed text. Bai et al. (2022) automatically critiques model-generated outputs and refines them for future training.
Applying APEL to other programming lan- guages requires a seed semantic parser with high top-k accuracy. Such requirement is more likely be fulfilled in the future, at least for program- ming languages that are well-represented in lan- guage model training data, as language model capa- bility is expected to improve (Ganguli et al., 2022). Additionally, the seed parser can be improved with better prompting techniques (Trummer, 2022; Wei et al., 2022; Wang et al., 2023; Zhou et al., 2023), which are complementary to contribution and would make APEL stronger.
To apply APEL to other programming languages. we need efficient methods to synthesize simple and informative program inputs. Such methods already exist for less expressive languages such as regular expressions or restricted SQL (Miao et al., 2019). Appendix M describes an additional case study where used APEL (with simulated annotators) to label utterances with regular expressions. To extend APEL to more complicated programs, we can potentially use language models to generate test inputs (Schäfer et al., 2023) and train them to search for more informative inputs with self- supervision (Haluptzok et al., 2023).
Programming by Example. PBE has been ap- plied to synthesize regular expressions (Gulwani, 101 tensor manipulation (Shi al., 2020), data analysis (Bavishi et al., 2019), and visualization (Wang et al., 2021) programs, etc. Some other recent works such as Ye et al. (2020); Baik et al. (2020) also try to combine semantic parsing with PBE. However, both of them require the users to provide the input-output examples, which can be time-consuming to write.
Scalable Oversight. As AT systems become more capable of generating candidate responses, an emerging line of research supervises AI systems by providing preferences over Al-generated candi- dates rather than providing human demonstrations (Askell et al., 2021; Ouyang et al., 2022). There- fore, to supervise Al to perform more complex tasks, it becomes increasingly important deter- mine human preferences over model outputs that are expensive verify (Amodei et al., 2016; Bow- man et al., 2022), such as full-book summaries or natural language descriptions of distributional properties (Wu et al., 2021; Zhong et al., 2022). Our work presents strategy to re- re-weight complex outputs from an Al system (namely, programs) by asking simple informative questions of annotators who do not have understand the outputs directly.
To reduce the users' workload, we provide the input part of the input-output examples, and fo- cus on only those inputs whose outputs will ac- tually help identify the desired concept. This is a case of active learning, which is broadly used in other applications such as learning real-valued functions, sequence classification, and visual ques- tion answering (Schulz et al., 2018; Ein-Dor et al., 2020; Karamcheti et al., 2021). In APEL, for each utterance, we maintain prior over the function (program) space and learn the desired function by querying it on a sequence of carefully chosen in- puts. Similar to our work, Pasupat and Liang (2016) asked non programmers o-selection questions by synthesizing table inputs, but they did not optimize for question simplicity and focused on simpler single-table setting. Concurrent to work, Lahiri al. (2022) applied a similar framework label Python functions; unlike them, we validated APEL. with human annotators.
8 Conclusion
We proposed APEL, enabling non-programmers to indirectly label SQL programs via oututt examples. With advances in semantic parsing and PBE, future work could potentially extend APEL to other applications. We hope non-programmers can label more complex programs in the future, hence decreasing the costs of supervising increasingly ca- pable AI systems that can take complicated actions by generating and executing code.
To reduce the effort required from humans, fu- ture work can also use large language models to

---

Acknowledgements
References
The first author is funded by NSF-Simons Theo- rinet Grant (NSF Award #2031985), Our human interaction study was approved by UC Berkeley's Institutional Review Board, and our survey and interface did not collect any personal identifiable information. We thank members of the Berkeley NLP group and Jacob Steinhardt's group, and the anonymous reviewers for their feedback on our paper draft.
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. 2016. Concrete problems Al safety. arXiv preprint arXiv:1606.0655..
Jacob Andreas, John Bufe, David Burkett, Charles Chen, Josh Clausman, Jean Crawford, Kate Crim, Jordan DeLoach, Leah Domnr, Jason Eisner, Hao Fang, Alan Guo, David Hall, Kristin Hayes, Kellie Hill, Diana Ho, Wendy Iwaszuk, Smriti Jha, Dan Klein, Jayant Krishnamurthy. Theo Lanman, Percy Liang, Christopher H. Lin, Ilya Lintsbakh, Andy Mc- Govern, Aleksandr Nisnevich, Adam Pauls, Dmitrij Petters, Brent Read, Dan Roth, Subhro Roy, Jesse Rusak, Beth Short, Div Slomin, Ben Snyder, Stephon Striplin, Yu Su, Zachary Tellman, Sam Thomson, An- drei Vorobev, Izabela Witoszko, Jason Wolfe, Abby Wray, Yuchen Zhang. and Alexander Zotov. 2020. Task-oriented dialogue dataflow synthesis. Trans- actions of the Association for Computational Linguis- tics, 8:556-577
Limitations
APEL is only a preliminary step towards allow- ing non-programmers to label utterances with pro- grams. We are not close to enabling expert-level labeling for arbitrary programming languages. We only experimented with English utterances, SQL programs, and university students; generalizing this to more natural languages, programming lan- guages, and annotator populations requires more future work.
Amanda Askell, Yuntao Bai, Anna Chen, Dawn Drain, Deep Ganguli, Tom Henighan, Andy Jones, Nicholas Joseph, Ben Mann, Nova DasSarma, et al. 2021. A general language assistant as a laboratory for align- ment. arXiv preprint 1
Our current implementation is limited text- to-SQL and regular expressions. As mentioned at the end of the last section, applying APEL to other semantic parsing tasks requires effective algorithms to find simple but informative program inputs and a strong seed semantic parser. While we believe that these assumptions are likely to hold in the future, they might not hold currently. We also assumed that we have access to a pool of unlabeled utterances begin with, while in practice we might not have access to utterances from real users. More future directions are discussed in Appendices B and I. As APEL only considers the function (i.e., input- output mapping) computed by a program, it is only able to annotate an utterance with a semantic equiv- alence class of correct programs. Other factors such efficiency readability might be needed choose among the programs in that class.
Yoram Bachrach, Thore Graepel. Thomas P. Minka, and Jo W. Guiver. 2012. How to grade test without knowing the answers-a Bayesian graphical model for adaptive crowdsourcing and aptitude testing. In ICMI..
Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, et al. 2022. Constitutional Al: Harmlessness from AI feedback. arXiv preprint arXiv:2212.08077.
Christopher Baik, Zhongjun Jin, Michael J. Cafarella, and H. V. Jagadish. 2020. Constructing expressive relational queries with dual--peccffication synthesis. In CIDR.
Rohan Bavishi, Caroline Lemieux, Roy Fox, Koushik Sen, and Ion Stoica. 2019. AutoPandas: Neural- backed generators for program synthesis. Pro- ceedings of the ACM Programming Languages, 3(OPSLLA)11277
Even though we have shown that APEL has higher accuracy than the seed parser, we have not empirically validated that the seed parser is im- proved by fine-tuning on the programs selected by APEL, nor did we study whether such im- provements are in fact cheaper to attain with non- programmers than with expert annotators.
Samuel R Bowman, Jeeyoon Hyun, Ethan Perez, Edwin Chen, Craig Pettit, Scott Heiner, Kamile Lukosuite, Amanda Askell, Andy Jones, Anna Chen, et al. 2022. Measuring progress on scalable oversight for large language models. arXiv preprint arXiv:2211.035..
Finally, no semantic parser should be used to synthesize SQL queries or other semantic forms for high-stakes scenarios without careful analysis of errors and the downstream harms that they might cause.
Anthony Chen, Pallavi Gudipati. Shayne Longpre, Xiao Ling, and Sameer Singh. 202 la. Evaluating entity disambiguation and the role of popularity in retrieval- based NLP. In Proceedings of the 59th Annual Meet- ing of the Association for Computational Linguistics

---

and the 11th International Joint Conference on Natu- val Language Processing (Volume I: Long Papers), pages 4472-4485 Online. Association for Computa- tional Linguisties.
Conference on Fairness, Accountabilityy and Trans- parency, pages 1747-1764.
Sumit Gulwani. 2011. Automating string processing in spreadsheets using input-output examples. ACM Sigplan Notices, 46(1):317-330.
Bei Chen, Fengji Zhang, Anh Nguyen, Daoguang Zan, Zeqi Lin, GuanG Lou, and Weizhu Chen. 2023. Codet: Code generation with generated tests. In The Eleventh International Conference on Learning Representations.
Patrick Haluptzok, Matthew Bowers, and Adam Tauman Kalai. 2023. Language models can teach themselves to program better. In The Eleventh International Conference on Learning Representations.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. b02 Evaluating large lan- guage models trained on code. arXiv preprint arXiv:2107.0337.
Ari Holtzman, Peter West, Vered Shwartz. Yejin Choi, and Luke Zettlemoyer. 2021. Surface form com- petition: Why the highest probability answer isn't always right. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Process- ing. pages 7038-7051, Online and Punta Cana, Do- minican Republic. Association for Computational Linguisties.
Xinyun Chen, Linyuan Gong, Alvin Cheung, and Dawn Song. 202lc. PlotCoder: Hierarchical decoding for synthesizing visualization code in programmatic con- text. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 1 11th International Joint Conference on Natu- ral Language Processing (Volume I: Long Papers), pages 2169-2181, Online. Association for Computa- tional Linguistics.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray. Alec Radford, Jeffrey Wu, and Dario Amodei. 2020. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836.
Xinyun Chen, Chang Liu, and Dawn Song. 2018. Exxcuttionguuide neural program synthesis. In Inter- national Conference on Learning Representations.
Siddharth Karamcheti, Ranjay Krishna, Li Fei-Fei, and Christopher Manning. 2021. Mind your outliers! in- vestigating the negative impact of outliers on active learning for visual question answering. In Proceed- ings of the 59th Annual Meeting of the Association for Computational Linguistics and the I 11th International Joint Conference on Natural Language Processing (Volume I: Long Papers). pages 7265-7281, Online. Association for Computational Linguistics.
Yuxin Chen, Shervin Javdani, Amin Karbasi, J. Andrew Bagnell, Siddhartha Srinivasa, and Andreas Krause. 2015. Submodular surrogates for value of informa- tion. In Proceedings of AAAL.
Shumo Chu, Chenglong Wang, Konstantin Weitz, and Alvin Cheung. 2017. Cosette: An automated prover for SQL. In CIDR.
Nate Kushman and Regina Barzilay, 2013. Using se- mantic unification to generate regular expressions from natural language. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 826-836, Atlanta, Georgia. Association for Computational Linguistics.
A. P. Dempster. N. M. Laird, and D. B. Rubin. 1977. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Soci- ety, 39(1):1221.
Liat Ein-Dor, Alon Halfon, Ariel Gera, Eyal Shnarch, Lena Dankin, Leshem Choshen, Marina Danilevsky, Ranit Aharonov, Yoay Katz, and Noam Slonim. 2020. Active Learning for BERT: An Empirical Study. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP), pages 7949-7962, Online. Association for Computa- tional Linguistics.
Shuvendu K Lahiri, Aaditya Naik, Georgios Sakkas. Piali Choudhury, Curtis von Veh, Madanlal Musu- vathi, Jeevana Priya Inala, Chenglong Wang, and Jianfeng Gao. 2022. Interactive code generation via test-driven user-intent formalization. arXiv preprint arXiv:2008.0590
Stefan Larson, Anthony Zheng, Anish Mahendran, Rishi Tekriwal, Adrian Cheung, Eric Guidan, Kevin Leach, and Jonathan K. Kummerfeld. 2020. Iterative feature mining for constraint- based data collection to increase data diversity and model robustness. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). pages 8097-8106, Online, Association for Computa- tional Linguistics.
Ahmed Elgohary. Saghar Hosseini, and Ahmed Hassan Awadallah. 2020. Speak to your parser: Interactive text-to-SQL with natural language feedback. In An- nual Meeting of the Association for Computational Linguistics.
Deep Ganguli, Danny Hernandez, Liane Lovitt, Amanda Askell, Yuntao Bai, Anna Chen, Tom Con- erly, Nova Dassarma, Dawn Drain, Nelson Elhage, al. 2022. Predictability and surprise large gen- erative models. In Proceedings of the 2022 ACM
Nada Lavrac and Saso Dzeroski. 1994. Inductive logic programming. In WLP, pages 146-160. Springer.

---

N. Littlestone and M.K. Warmuth. 1994. The weighted majority algorithm. Information and Computation, 108(2):212-261.
pages 9895-9901, Online and Punta Cana, Domini- can Republic. Association for Computational Lin- guistics.
Zhengjie Miao, Sudeepa Roy, and Jun Yang. 2019, Ex-
Eric Schulz, Maarten Speekenbrink, and Andreas Krause. 2018. A tutorial on Gaussian process regres- sion: Modelling, exploring, and exploiting functions. Journal of Mathematical Psychology. 85:1-16.
plaining wrong queries using small examples. In Proceedings of the 2019 International Conference on Management of Data, pages 503-520.
Barton P. Miller, Louis Fredriksen, and Bryan So. 1990.
Max Schäfer, Sarah Nadi, Aryaz Eghbali, and Frank Tip. 2023. Adaptive test generation using a large language model.
An empirical study of the reliability UNIX utilities. Communications of the ACM, 33(12):32-44.
Lingbo Mo, Ashley Lewis, Huan Sun, and Michael White. 2022. Towards transparent interactive seman- tic parsing via step-by-step correction. In Findings of the Association for Computational Linguisties: ACL 2022, pages 322-342, Dublin, Ireland. Association for Computational Linguistics.
Semantic Machines, Jacob Andreas, John Bufe, David Burkett, Charles Chen, Josh Clausman, Jean Craw- ford, Kate Crim, Jordan DeLoach, Leah Dornrr, Ja- son Eisner, Hao Fang. Alan Guo, David Hall, Kristin Hayes, Kellie Hill, Diana Ho, Wendy Iwaszuk, Sm- riti Jha, Dan Klein, Jayant Krishnamurthy, Theo Lan- man, Percy Liang, Christopher H. Lin, Ilya Lints- bakh, Andy McGovem, Aleksandr Nisnevich, Adam Pauls, Dmitrij Petters, Brent Read, Dan Roth, Subhro Roy, Jesse Rusak, Beth Short, Div Slomin, Ben Sny- der, Stephon Striplin, Yu Su, Zachary Tellman, Sam Thomson, Andrei Vorobev, Izabela Witoszko, Jason Wolfe, Abby Wray, Yuchen Zhang, and Alexander Zotov. 2020. Task-oriented dialogue as dataflow syn- thesis. Transactions of the Association for Compula- rional Linguistics, 8:556-571.
OpenAI. 2023. GPT-4 technical report. arXiv.
Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida. Carroll L.. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray. al. 2022. Training language models to follow instructions with human feedback. arXiv preprint arXiv:2203.02155.
Panupong Pasupat and Percy Liang. 2016. Inferring log- ical forms from denotations. In Proceedings of the 54th Annual Meeting of the Association for Compu- tational Linguistics (Volume 1: Long Papers), pages 23-32, Berlin, Germany, Association for Computa- tional Linguistics.
Kensen Shi, David Bieber, and Rishabh Singh. 2020. TF-Coder: Program synthesis for tensor manipula- tions. arXiv preprint arXiv:2003.0004
Richard Shin, Christopher Lin, Sam Thomson, Charles Chen, Subhro Roy, Emmanouil Antonios Platanios, Adam Pauls, Dan Klein, Jason Eisner, and Benjamin Van Durme. 2021. Constrained language models yield few-shot semantic parsers. In Proceedings of the 2021 Conference on Empirical Methods in Natu- ral Language Processing, pages 7699-7715, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gul- wani. 2022. Synchromesh: Reliable code generation from pre-trained language models. In International Conference Learning Representations.
Nitarshan Rajkumar, Raymond Li, and Dzmitry Bah- danau. 2022. Evaluating the text-to-SQU capa- bilities of large language models. arXiv preprint arXiv:2204.00498.
Immanuel Trummer. 2022. CodexDB: Synthesizing code for query processing from natural language in- structions using GPT-3 Codex. Proceedings of the VLDB Endowment, 15(11):2921-22
Timo Schick, Jane Dwivedi- Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. 2023. Toolformer: Language models can teach themselves to use tools. arXiv preprint arXiv:2302.0477 2302..476..
Bailin Wang, Richard Shin, Xiaodong Liu, Oleksandr Polozov, and Matthew Richardson. 2020. RAT-SQL: Relation-aware schema encoding and linking for text- to-SQL parsers. In Proceedings of the 58th Annual Meeting of the Association for Computational Lin- guistics, pages 7567-7578, Online. Association for Computational Linguistics.
Torsten Scholak, Raymond Li, Dzmitry Bahdanau, Harm de Vries, and Chris Pal. 2021a. DuoRAT: To- wards simpler SQLL models. In Proceedings of the 2021 Conference of the North American Chap- ter of the Association for Computational Linguistics: Human Language Technologies. pages 1313-1321, Online. Association for Computational Linguistics.
Chenglong Wang, Yu Feng, Rastislav Bodik, Isil Dil- lig. Alvin Cheung, and Amy J. Ko. 2021. Falx: Synthesis-powered visualization authoring. In Pro- ceedings of the 202/ CHI Conference on Human Factors in Computing Systems, pages 1-15.
Torsten Scholak, Nathan Schucher, and Dzmitry Bah- danau. Ib. PICARD: Parsing incrementally for constrained regr-seeees decoding from language models. Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing,
Sida I. Wang. Samuel Ginn, Percy Liang, and Christo- pher D. Manning. 2017. Naturalizing a programming

---

language via interactive learning. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 929-938, Vancouver, Canada. Association for Computational Linguistics.
Conference on Empirical Methods in Natural Lan- guage Processing, pages 3911-3921, Brussels, Bel- gium. Association for Computational Linguistics.
Luke Zettlemoyer and Michael Collins. 2007. Online learning of relaxed CCG grammars for parsing logical form. In Proceedings of the 2007 Joint Con- ference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning TEMNLP-CoNLLE pages 678-687, Prague, Czech Republic, Association for Computational Lin- guistics.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery. and Denny Zhou. 2023. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations.
Yushi Wang. Jonathan Berant, and Percy Liang. 2015. Building a semantic parser overnight. In Proceedings of the 53rd Annual Meeting of the Association for Computationall Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 1332-1344 1342, Beijing, China. Association for Computational Linguistics.
Ruiqi Zhong, Charlie Snell, Dan Klein, and Jacob Steinhardt. 2022. Describing differences between text distributions with natural language. In Inter- national Conference on Machine Learning, pages 27099-27116, PMLR.
Ruiqi Zhong, Tao Yu, and Dan Klein. 2020. Semantic evaluation for text-to- SOL with distilled test suites. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 396-411, Online. Association for Computa- tional Linguisties.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. 2022. Chain-of siiin-of-thee of-thought prompting elicits rea- soning in large language models. Advances in Neural Information Processing Systems,
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang. Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V Le, and Ed H. Chi. 2023. Least-to-man most prompting enables com- plex reasoning in large language models. In The Eleventh International Conference Learning Rep- resentations.
Jacob Whitehill, Ting-fan Wu, Jacob Bergsma, Javier Movellan, and Paul Ruvolo. 2009. Whose vote should count more: Optimal integration of lahels from labelers of unknown expertise. In Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc.
Jeff Wu, Long Ouyang, Daniel M. Ziegler, Nisan Sti- ennon, Ryan Lowe, Jan Leike, and Paul Christiano. 2021. Recursively summarizing books with human feedback. arXiv preprint arXiv:21099 10862.
Yan, Romer Rosales, Glenn Fung, and Jennifer G. Dy. 2011. Active learning from crowds. In Proceed- ings of the 28th International Conference Interna- tional Conference on Muchine Learning, ICML'I 1,, page 161-1168, Madison, WI, USA. Omnipress.
Ziyu Yao, Yiqi Tang, Wen-tau Yih, Huan Sun, and Yu Su. 2020. An imitation game for learning se- mantic parsers from user interaction. Proceed- ings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages Online. Association for Computational Linguistics.
Xi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett. 2020. Benchmarking multimodal regex synthesis with complex structures. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 6081-6094, Online. Association for Computational Linguistics.
Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga. Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingn- ing Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev. 2018. Spider: A large-scale human-labeled dataset for complex and cross-domain semantic pars- ing and text-to-SQL task, In Proceedings of the 2018

---

Supplementary Material
summed over the APEL-annotated utterances u. In effeet, this treats pr as giving a set of weighted "soft annotations" for u, not just the MAP annota- tion. It is equivalent to minimizing the Kullback- Leibler divergence KT(pr p) (summed over u).
A Training on APEL Annotations
As APEL is an annotation method, its ultimate goal is to convert unlabeled utterances into "su- pervised" training examples (u, 8) for a semantic parser. In this appendix, we discuss how these training examples would be constructed and used. (In the main paper, we used "example" to refer to examples of the form o), used for programming by example ($2). In this appendix, however, use "example" to refer to examples of the form (), used as training examples for semantic parser.)
Iterative Retraining Once improved parser has been trained the inferred annotations either the MAP annotations or the soft annotations can be used as an improved prior po the update rule (1). This can inform APEL 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 (I) to recompute an improved poste- rior Pr from the improved prior Po- 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.
Training on MAP Annotations For each utter- ance APEL solicits indirect annotations and pro- duces posterior probability distribution pr over programs. The maximum a posteriori (MAP) pro- gram is defined by 8 argmax, (s))..
Most simply, we could train semantic parser the inferred annotations (u, 8). Specifically, one option is to these annotations to fine-tune the seed parser Po- However, this may not be practical for very large pretrained model such as Codex, in which case the annotations could be used to train a dedicated semantic parser from scratch.
This iterated procedure is a principled training method. If soft annotations are used for retrain- ing via equation (8) at each iterations, then it is an instance of the Expectation Expectation-Maximizatio gorithm (Dempster et al., 1977). (If MAP labels are used, is an instance of the hard "Viterbi" ap- proximation EM.) EM is guaranteed to converge to a new semantic parsing model Po that locally maximizes the conditional log- likeliiel (7) all of the observed data in our case, the annotators' responses тr for all o-selection questions on all utterances Thus, it is simply a log-likelihood training method where the observed data are not direct annotations s, but indirect annotations rú. It marginalizes over the latent programs
(EM) al-
Downstream Evaluation In this paper, eval- uated APEL directly by asking whether its inferred annotations (u, 8) are accurate. We measured this by semantic equivalence [$] = [[s*] (see $4.2) on a small test set pairs (u, that were annotated by experts (using APEL). One could instead evalu- ate the actual impact of the inferred annotations on parsing performance, by training semantic parser (e.g., fine-tuning the seed parser) on a large training set of APEL-labeled utterances, and evaluating that parser the test set.
Richer Model of Annotator Behavior The an- notator model p(r a, s(i) can be jointly retrained with the semantic parser at each iteration of EM, to obtain higher log-likelihood (7). Improving the annotator model in this way should result in more accurate distributions pr at the next iteration of EM, and thus better semantic parser. Specifically, when we retrain the parser via equa- tion (8), we can also retrain the annotator model to maximize the expected tog-likelihood
Beyond MAP Rather than evaluating only the MAP annotation 8, we could have evaluated APEL's entire distribution pr using the log-loss, Ps u). averaged over the test set of (u, s*) pairs. This is more sensitive evaluation, though harder to interpret than exact-match accuracy.
But do we care whether the distribution pr is accurate beyond just its MAP annotation? Yes: one could train a parser by maximizing its expected log-likelihood
T
Egpr
log p(rz | ar, s(i)))
(9)
summed over the APEL-annotated utterances u. This EM procedure will converge to maximum of the incomplete-dat log- likelihooo as in $6.4.
Exppy [ogp(s u]]

---

We could fit richer model of annotator behavior than the relatively simple one in $6.4. For example, we could estimate the error rates of individual anno- tators 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 pr and the other annotators.
risk
(p u) del L, (8()) u, 1, s())]]
(11)
This & is not necessarily the MAP program. Once is predicted, the output on any given input i is 8())
In some applications, however, it may not be necessary choose single program use for all inputs. Then the best output return for input the output that minimizes the Bayes risk
Although equation (1) assumed that p(r 8, u, a, = p(r a, s()),, rich model could drop this assumption. For example, the model might allow that the annotator is more likely to make error when is difficult or i is com- plex. As annotator's errors ance may be influenced by how they answered previous questions, a rich model could even take the form p(ra 8, u. 0, à1, Ti...... 4-11 Tt-1, it), where i1, -,,..., i1-1, 72-1 are the previous rounds
(p (Ō u. Es-p(-l)) [loss(ō i, s())] (12)
given utter-
In other words, â is now predicted from i by a consensus of multiple programs.
B Extensions to APEL Annotation
of interaction with annotator a.
The following natural extensions could be explored in future work.
Evaluating with Task Loss In our discussion of evaluation thus far, we have not given the semantic parser any partial credit. That is, given an utterance we have considered any answer other than the correct program s to be equally wrong.
Selecting Questions with Task Loss A model of task loss as in Appendix A can be used im- prove the selection of the next question ig. Instead of maximizing the expected reduction in entropy (equation (4)), we can maximize the expected re- duction in the Bayes risk (11).
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 lōss(ō) i, o") denote the task-specific loss of predicting output on input i when the correct output is o*.
When p is any distribution over programs for utterance u, define the minimum Bayes risk by
MBR(p) min Rp
(13)
The loss of predicting program when the correct program is s* is then
At the start of round t, can already achieve Bayes risk of MBR(pt-1). Once have the annotator's s response rr to question it we will be able to update Pt-1 to Pt and achieve Bayes risk of (BR(pt). where pt depends on é and r; via the update (2). Thus, the value of information from asking question i, is
E2 [loss($8() (8(1) u, i, (t))
(10)
where the expectation E, is taken over some realis- tic distribution of inputs for utterance u. This loss function can be used in supervised evaluation.
Decoding with Task Loss Following standard Bayesian decision-thewd theoretic methods, the semantic parser itself can aim to achieve low loss. No change the training procedure is needed. Suppose we have trained a semantic parsing model p(s u) by EM as described above. We now need to extract decisions from this model. the semantic parser is required to translate into a single program & that will be used for all inputs, then the best program to choose is the program that minimizes the Bayes
MBR(P-11- (MB. [BR(P:))
(14)
This is essentially the same as the information gain (4), but with task loss replacing log-loss. It is again guaranteed to be 2 0.
Richer Model of Annotator Effort Our objec- tive (5) trics to present the annotator a, with "sim- ple" input database i, as measured by the number of records |åg]. However, [ is only crude mea- sure of the time or effort that the annotator must expend to answer the multiple-choice question de- rived from it For example, annotators typically
'This means using p(ra | as, is) in place of p(rx ae, a(f)) in equations (2), (3), (7) and (9).

---

find it more difficult perform arithmetic or to reason across multiple tables within it.
swering 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).
To predict the annotator's effort on the input database i,, we could attempt to simulate the anno- tator's mental execution of the true program on iq. As we do not know the true s, we would need to take the expectation of this effort over 8 Pt-1- Mental operations such adding 3-digit numbers visually scanning the tables for specific string could be then given appropriately high costs in the effort model.
At each step of APEL annotation, we would select a high-scoring triple-one in which we ex- pect annotator to usefully evaluate utterance u's desired behavior on input database with low ef- fort. 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 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(t)) but also to finding that answer in the list of options. More generally, the model could attempt capture mental strategies that do not fully compute s(t)) but only do enough work to eliminate most of the options.
In the same way, Bachrach et al. (2012) and Whitchill et al. (2009) model each individual an- notator's capability and each question's is difficulty, learning these parameters through agreement infor- mation. Yan et al. (201 explore these ideas for active learning. similarly routing useful questions to competent annotators. Our experiment empiri- cally 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 annotate which utterances.
Finally, a question generally requires less human cognitive effort if it is related to a preceding ques- tion. Querying input database i with utterance is easier for an annotator who has just queried the same with different u', or queried different i' with the same u.
Mon-Myopic Selection Policy The procedure de- scribed just above will switch freely among utter- ances and inputs, if it always selects the highest- scoring triple. However, recall that a followup question on the same utterance or input is eventu- ally to be asked at all, asking it immediately will incur less effort from the annotator. Thus, good heuristic is to prioritize followup questions over non-followup questions, provided that they score highly enough that it is likely that they will eventu- ally be asked.
How would we train the parameters of the effort model? We observe how quickly the annotator an- swered each 4 with ry. 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 ig. If we do not know we impute it from the observed responses thhpt is, evaluate the effort model's log-likelihood in expec- tation under s ~ Pr, analogously to equations (8) and (9), In short, the effort model could be trained by EM, jointly with the other models.
More generally: Greedily choosing the highest- scoring question at each step is common in inter- active protocols for information acquisition, such as adaptive quadrature or Bayesian optimization (Schulz et al., 2018). However, this greedy proce- dure is in general suboptimal. One could do better at selecting the next question by planning ahead subsequent questions (Chen et al., 2015), though at a higher computational cost.
Choosing Who Should Annotate What The se- lection objective (5) manages the tradeoff between annotator effort and information gain by impos- ing a hard constraint on the annotator effort per o-selection question. We could improve this crude selection objective given good models of annotator behavior and annotator effort-by by se- lecting question i that achieves high "bang for the buck." This score is given by the ratio of value of information (equation (4) (14)) the expected effort of acquiring that information.
Again, we leave all these refinements to future work.
Both the numerator and denominator of this ra- tio depend on the specific annotator a who an-
C Other Synthesis Constraints
This appendix gives further details about our method of database construction ($3). Overall, we
'The same simulation could be also used to help model errors in the annotutor's response r. (Appendix A).

---

follow the recipe of Zhong al. (2020) to gener- ate large informative databases that conform a given schema c. We draw upon the existing sample database with this schema (provided by the SPI- DER dataset in our experiments) to obtain plausible cell values. Following Zhong et al., we first synthe- size cell values for all the "parent" columns (i.e., the columns that are being referenced by child column in foreign key relation), and then popu- late child columns with random elements from the parent columns.
gorithm to produce such that the SQL candidates will meaningfully use their operators.
Managing Tradeoffs between two Criteria All the above tweaks make a tradeoff between the in- formative and the simplicity criteria in some way: we impose restrictions on or modify p' to decrease the annotator effort while sacrificing information gain can potentially achieve. How do decide when to apply certain tweaks?
In our paper, we always add small probabilities of neighbor queries and RETURN NULL to p' and use cell values from the existing database. We then consider 3 types of tweaks that we apply if possible: 1) in satisfies the uniqueness constraint, 2) in is initialized with an existing database, and 3) | < 15 rather than 30. We apply these tweaks if they do not prevent from succeeding. We define in total 2
Naturalness of i As shown in Figure 6a, unre- stricted random cell values confuse annota- 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 1 for integer values.
different "ccofigurations" S c 8, each of which specifies what subset of tweaks to apply to the algorithm described $3. For example, c = B110 means we apply tweaks 1) and 2). We enumerate from = to 0 until the algorithm from $3 returns program input with IG(i) * 0. In other words, we start by applying all the tweaks and drop the tweaks gradually until we obtain a with positive expected information gain.
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.
Asia as shown in Figure (b). Therefore, we prefer to initialize 1 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 column, prefer to enforce that i also has unique values that column.
D Fixing SPIDER Databases
We found several issues with the SPIDER databases and fixed them as follows:
Non- vac-oucuous Execution Extremely small i fre- quently leads to undefined denotations. For exam- ple, the maximum of zero elements is special NULL value, meaning "undefined"; this confuses annotators without a computer science background (Figure 6d). Therefore, we always add a small probability mass ( of RETURN NULL to the dis- tribution and normalize the probabilities of the other candidates proportionally, in order to incen- tivize our algorithm to produce such that other SQL. candidates will return non-NULL values.
Some SPIDER databases do not conform to the foreign key constraint, i.e. some of the child columns contain values not in the parent columns they are referring to. We enforce the foreign key constraint by dropping the illegal records.
In some domains, we identify missing foreign key constraints and add them.
The voter_1 domain does not contain an ap- propriate foreign key design. Since fixing it would require an effort of re-annotating all 15 associated SQLs, we chose to exclude this domain from our evaluation.
Even if the returned value is well-defined, small i can lead to confusion some operators are not needed to answer the question. For example, in Figure 6e, asking the maximum over one element might appear confusing, operator obtain correct denotation. Therefore, we always add into p' a small probability mass of "neighbor queries" (Zhong al., 2020) obtained by dropping aggregation operators and WHERE clauses from SQL candidates in p/. This incentivizes our al-
do not need the max
Some Date typed columns are string-valued and use English words to represent values, result, dec1, 2021,
e.g. nov1, 2021. which is chronologically later, will be con- sidered smaller alphabetically. We fix this

---

Name
Age
Section
k
easy
medium
hard
extra
all
Unnatural
(a)
asdg
102
0.87
0.80
0.56
0.45
0.72
values
gwerty
200
pejgen
2
0.94
0.89
0.74
0.63
0.84
0.96
0.93
0.87
0.70
0.89
Country
Continent
0.97
0.95
0.95
0.78
0.92
Counterfactual
(b)
U.S.
Asia
content
16
0.98
0.96
0.98
0.81
0.94
Canada
Africa
32
0.98
0.96
0.98
0.85
0.95
ID
Name
Age
Table 3: The top-k accuracy for the SQL candidates generated by Codex on SPIDER (Yu al., 2018), calcu- lated on each split.
Uncommon
(c)
Eren
pattern
Fren
23
Utterance: How old youngest person from section A?
been selected. Finally we append the natural lan- guage utterance to be annotated, and ask Codex to continue generating text after this prompt, which generates candidate SQL program corresponding to An example prompt can be seen in Figure 7. As mentioned in $4.2, we sampled 200 different prompts, which varied in their selected examples, and for each prompt we sampled 20 candidates from Codex with temperature=1.. and top_p=0..95.
Name
Age
Section
Vacuous answer
(d)
NULL
Reiner
26
Name
Age
Section
Vacuous
(e)
Fren
26
operator
Figure 6: Examples unnatural databases (top) and vacuous execution (bottom), which motivates several tweaks in Appendix C. In (a) the individual cell val- ues are unnatural. In (b) the records contradict world knowledge. In (c) the database contains persons with the same name, which is atypical (but possible). In (d) denotation the utterance undefined, since cannot take the maximum of zero elements. In (e) we do not need the max operator to obtain the correct denotation, since there is only one person in section A.
E.2
Top-k Accuracy
As mentioned in $4.2, we defined Po as distribu- tion over the top-k approximate equivalence classes of the 4000 sampled programs, where = 16. Ta- ble 3 reports the candidate ceilings ($4.4) for vari- ous other values of k, and Figure graphs these top-k accuracy curves.
by canonicalizing date representations into a yyyy-mm-dd format.
Errors in Non-Programmer Responses
Ambiguous Utterances. Consider the utterance "What are the names of properties that are either houses or apartments with more than room?" Should it be parsed as "(house) or (apartment and room > 1)", or "(house or apartment) and room > !P Another example: "Count the number of friends Kyle has." What to do when there are two students named Kyle?
We accordingly update the suite of test cases from Zhong et al. (2020) that we use to check whether two SQL forms equivalent (see $4.2), that they conform the new database schema.
E Generating SQL Candidates
E.1 Prompting Codex
As sketched in $4.2, we obtain SQL program can- didates through few-shot prompting, where the database schema is followed by or 8 (with 50% probability) pairs of natural language utterances with their corresponding SQL queries from the SPI- DER development set from the subset of utterance- SQL pairs associated with the same database schema. To select each in-context example, with probability 50% we choose the examples most sim- ilar to the utterance u that we want annotate based on TF-IDF similarity, and with probability 50% we choose a random example that has not yet
Heavy Computation. 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 Constraints with Common Sense. 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

---

CREATE TABLE Highschooler(
ID int primary key, name text, grade int)
CREATE TABLE Friend( student id int, friend_ia id int, primary key (student id, friend_id) foreign key(student id) references Highschooler((D) (ID) ON DELETE CASCADE, foreign key (friend_id) id) references Highschooler(ID) DELETE CASCADE
[Other table schema omitted]
Write query that answers "Count the number of high schoolers."
SELECT count(*) (*) FROM Highschooler
Write a query that answers "What are the names of high schoolers who have 3 or more friends?"
SELECT name PROM Friend AS Tl JOIN Highschooler AS T2 ON Tl.student id rid GROUP Ti.student_ HAVING count(*)
[6 More examples omitted]
Write query that answers "Find the average grade of all students who have some friends." [Models' Completion]
Figure 7: example prompt we use the Codex API. We obtain SQL program candidates through 4/8-shot prompting, where the database schema (orange) is followed by 4/8 pairs of natural language utterance and their corresponding SQL queries from the SPIDER development set, randomly sampled from the subset of queries associated with the same database schema. Finally concatenate the target natural language utterance u to annotated, and ask Codex to complete the prompt, which results in candidate SQL program corresponding
equivalent to sorting by AGE descendingly. How- ever, APEL is able to find a database where these two strategies return different outputs.? Such a database is unnatural and confuses humans. A pos- sible solution would be to induce such constraints from the sample database and/or the column names in the schema.
SQL Candidates Top-k Acc
0.95
Accuracy
0.80
G Computation
We did not compute the runtime in controlled environment, so the statistics in this section are our best estimate.
easy medium
0.60
extra
Finding a single informative small database can take up to several minutes. The simulation evalua- tion on the evaluation split in $5 (524 utterances) takes around 240 CPU hours in total.
1
2
8
16
32
k
Figure 8: The top-k accuracy for the candidate SQL. pro- grams generated by Codex, after filtering and merging candidates. On each difficulty split plot the curve of top-k accuracy (y-axis) and & (x-axis, log-scaled). The numbers be in Appendix Table 3.
For the human evaluation in $6 (240 utterances), we must pre-compute the databases for each terance, order support real-time interaction. Since we may ask the annotator up to ques- tions about the utterance, the choice of database
'Even though APEL derives its databases from the origi- nal SPIDER sample database, that sample database contains records that do not conform to this unstated constraint.

---

performance of 91%, and the average number of interaction rounds fluctuates by at most 0.05. Addi- tionally, even after increasing the maximal allowed database size R from 15 to 30, we still obtain an av- erage size of 10, since we prefer smaller databases under the same information gain.
|W| Across Interaction Rounds
# Interaction Rounds
Across Utterances
200
# Utterances
223
# Rounds
100
If
Total # Relations in Database
Rounds per Utterance
I Human Annotation
Figure 9: The interaction statistics using the SPIDER annotation simulate an ideal annotator. Left: the distribution of the size of the database across each round of interaction. Right: the distribution of the number of rounds across difference utterance.
We provide breakdown statistics on the annotation accuracy of different sources based on difficulty in Table 5.
More analysis on the annotator behavior model can be found in Figure 10.
easy
med
hard
extra
all
J Interface
Candidate
0.98
0.96
0.98
0.81
0.94
Codex
0.87
0.80
0.56
0.45
0.72
See Figure 11 for a detailed screenshot of our in- terface. We implemented the front-end of our terface with Angular and the back-end was built with flask and Redis. Users are presented with a sequence of 40 distinct questions, and each ques- tion may have multiple rounds. For each round, the user is given 4 minute time-limit before the inter- face automatically transitions to the next question. Before being asked questions on new database, the user is presented with page displaying all the tables in the database alongside descriptions we wrote for each table (see Figure Figure 12 for an ex- ample screenshot). When answering questions, the user is given link back to this page for reference.
OurDB 0.93
0.95
0.97
0.75
0.91
OrigDB 0.98
0,90
0.83
0.66
0.86
Table 4: The accuracy ceilings on each difficultyy split. "med" stands for medium difficulty. Candidate means the candidate ceiling. OurDB means the accuracy ceil- ing achieved by querying an oracle annotator with most 3 small informative databases we synthesize. OrigDB means the accuracy ceiling by querying with the databases released by the SPIDER dataset.
4 is conditioned on 0-2 previous questions and responses (11,71...., 1, 1). We pre-compute the database in for each of these possible histories that we may encounter. 6 This takes around 100 CPU hours in total (for the 240 utterances).
The user either select one of the multiple choice questions presented or select "No Answer is Correct", and depending on their selection the user is presented with a differing set of followup questions. Regardless of their selection, we always ask the user two optional followups: "if you think the question is ambiguous, tell us why." and "if the question looks confusing, tell us why." In addition to these optional questions, sometimes ask quired followup questions. Specifically, if the user on their final round and selects an answer which does not agree with the SPIDER annotation, we ask them why they did not seleet the correct an- swer according to spider. Or if the user selects "No Answer is Correct", we ask "What is the answer you have in mind and why?" We use the users' answers to these followups to collect information on the users' reasoning in answering questions and to determine issues with the SPIDER dataset.
H Simulated Interaction Statistics
The breakdown statistics of candidate and inter- action ceiling (see $4.4) can be seen in Table 4, and the distribution database sizes and number of rounds of interaction can be seen in Figure 9.
Robustness Towards Hyper-Parameetrr Choices. We vary the bustness. Changing 5% 20%, or decreasing the number of random re-runs, all leads to the same
in $3 to test its ro-
'Except that we set a timenut of 40 minutes per utterance. the the 240 utterances, utterances timed out before computing all of the databases in the response tree. (These primarily came from one domain where SPIDER'S 's sample database was very large.) If during the interaction with an annotator, we needed a database it that we had not precomputed, we aborted the interaction early (we considered this as a failure to find an appropriate database, in the terms of 12. However, this rarely happened, since at each node of the response tree, we considered the most probable responses first.
We implemented a number of features in our in- terface to minimize the annotator effort. One of the largest challenges in this task is answering ques-

---

True Annotator Response Accuracy
Across Different Domains
True Annotator Response Accuracy
Across Different Annotators
1.0
1.0
0.8
0.8
0.6
0.4
0.2
0.2
0.0
0.0
0.4 0.6
0.0
0.2
Predicted Annotator Response Accuracy
Predicted Annotator Response Accuracy
Figure 10: For each domain (left) and annotator (right), we use our annotator behavior model to predict the annotation accuracy (z-value) without using gold annotation and compare it with true annotation accuracy (y-value) using the gold annotation. The outlier at the bottom of the left figure corresponds to domain that only contains six utterances, where 4 were used for training and used for held-out evaluation.
easy
medium
hard
extra
all
Candidate Ceiling
0.91
0.91
0.92
0.69
0.88
SPIDER
0.93
0.78
0.63
0.50
0.75
Codex
0.78
0.65
0.43
0.36
0.59
APEL
0.75
0.71
0.65
0.49
0.67
APEL
0.83
0.80
0.73
0.47
0.75
Table 5: I-best accuracy of various SQL prediction methods, broken down by the difficulty level of the utterance (as categorized by SPIDER). Codex returns the most probable SQL according to Po- APEL does the same, after eliminating SQLs that are inconsistent with the responses of single randomly chosen annotator. APEL m is our full method, which returns the SQL with the highest posterior probability after we fit our model of annotator enror.
tions across several foreign keys. We implement two distinct mechanisms make this easier for users. First, we highlight all table values or foreign keys matching the value the mouse is currently hov- cring over. Second, we give the user the option to merge all foreign keys into single table by press- ing "merge" button. We allow the users to choose when merge because there is trade-off; while merged mode can make reasoning about foreign keys easier, it also can significantly increase the width of the tables visible to the user.
asked "Show name, country, age for all singers ordered by age from the oldest 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 ambigu- ous or confusing. We don't 't need it for this question now.
Sometimes there are tables presented to the user that are not necessary for answering the question, we give users the option to collapse tables to simplify their display.
Page 3
Let's go through more examples.
Page 4 In this question you are asked "How many singers do we have?" This is 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.
K Video Transcript
Page In this task, you will be asked to answer questions from several tables.
Page 2
Here the overall idea. You will be given question on the top of the page, several tables on the left of the page, and you need choose one the options on the right, that corresponds to the correct answer. In this question, you are
There is a time limit shown at the top of the page, and after 4 minutes the system will move on to the

---

professionals
4) click to merge foreign keys.
below average?
1) 1)40:0 time limit.
chanes Foom df option
2) foreign key value highlight on hover.
PAOTSSIAALL DV
3) click to collapse table.
Tiln
5) Select option B and answer follow up questions.
Select "No Answer is Correct" and answer follow up questions.
Question:
Queatior:
What are the first name and last same of the professionals who have done treatment with cast below average?
Whut ars the first sams and lust nume of the profossioaal who have does treatreant with cost below everrge?
why dite's yne sdler
Matrend hou
Coodee
Figure 11: A detailed screenshot of our interface, and the logical flow of follow up questions.

---

to redd trough the cortert you abary nite back 5030 dem toa taoads
Detabase: dog, Jennels
This aua derabaee about dige, breads, their oarneng then alto matton about the (rnciccal treatmeet informaion andite profecdones who tranted thent.
treatment_ L_tneennttttpppe types
Each row containe inforration about inottnen tyoe For ee marple, EXAM the coce for Phylical commiation
CODE
TREATMENT TYPE DESERIPTION
Prysicsi Hear ration
Vacoiration
WAL
Take for Welk
breeds
contane nonretttonn obout breed dog.
Messо,
BBK
Esk PM
BLL
Bullioo
Figure 12: An example database description page presented users before they start answering questions for that database.
next question.
Page 8 Here's the same question and the same table. Let's say somehow Sun and Gentleman is one of the options, and then you should report that no answer is correct. Then we will ask you why you think no answer 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".
Page Takeaways:
Names are different from IDs. Two different people can have the same name.
There is time limit of 4 minutes for each question.
The system asks why we didn't choose A, can answer "sun is by Rose, who older than 34.5". Please tell us enough information so that we can know why your choice correct for example you just say "sun is also 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.
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 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 you need to!
Page 6
Page 9
Takeaways:
Also, notice that there other tables, but they are not relevant the question. Feel free to ignore them. You can also choose collapse them if that makes it easier, and you can click the button again to view it.
Choose no option is correct and tell us why when you think no options are correct
Tell us why you didn't 't choose an answer when we ask you to do so.
Page Takeaways:
The question is "What are the full names of all players, sorted by birth date?" First, notice that there are a lot answers in this case, and you need to seroll down to read through all of them.
Page 10
Use calculator if you need to.
Not every table is needed.

---

Secondly, there are lot of ambiguities: for ex- ample, 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 the same col- umn. 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 re- sponse: "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.
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 value, all the same values will be highlighted. Here we notice that according 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.
Then we click submit, and the system asks us why we didn't t choose C. We explain that "the ques- tion does not ask us for the birthday and it contains redundant information".
You don't 't have study the tables in detail, since they will probably change for the next question.
Page 11
Takeaways:
Page 15
Takeaways:
There can be a lot of options. Make sure to read through every of them
You don't have to study the table content in great detail, since they will be changing.
When the question is ambiguous and multiple answers are plausible, tell us why it is ambigu- ous and what are the plausible answers. But still, first make your best guess and submit.
Zoom-in/out you need to. You can find them the helper panel of your browser.
Page 16
This question is "Show names, results and bulgarian commanders of the battles with no ships lost in the 'English Channel".
The question "Give the names of coun- tries that are in Europe and have a population equal to 80000." In this fictitious table, Brazil is in Eu- rope and has 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 coun- tries in the world, beyond these three countries in the table, but we should pretend that there are only three countries in the world here.
Page 12
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 the English channel [pause]. Only Battle 5 did; it lost ship C there. So the other bat- tles, Battles O 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 O and 7, along with their other informa- tion. 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!
Page 13 Takeaways:
Try accepting the information from this table as much as possible and focus on the part useful for answering the question.
Notice that there was originally the death table. We removed it from the display to make it easier for you.
If something is not present in the tables, pre- tend that it does not exist.
The phrase 'Bulgarian commander' might send you looking for a table that tells you each commander's nationality. But actually, Bulgar- commanddd is a column in the battles table. Presumably this table lists battles that Bulgaria fought. Each battle had two sides, and this column
Page 14 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

---

is naming the commander for the Bulgarian side. You don't have fully understand how the tables are set up. but you should figure out enough to answer the question.
Pay close attention 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 changing and might be different from the knowledge you have for the real world
Just to repeat, to make easier for you to process this information, whenever your cursor moves to an ID or piece of text, its counterpart in other tables will light up; whenever you click 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 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 lost in the battle, be careful when you try to interpret the merged table. Click unmerge to recover to the original view.
text, the
IDs are different from names
Some questions might have lot of options choose from and you need to read through all of them.
To make it casier for you to answer the questions:
Page 21
Use the highlight and merge operations when need to
Use a calculator you need to
Zoom out to fit the tables into the screen and prevent scrolling.
Finally, if you forgot what each table means, you can always view them here.
Not all table or column is needed to answer the questions
Page 17
Takeaways:
Pay close attention to how the question is be-
Page 22
For freeform response:
ing asked. They might lead to different op- tions. Many mistakes people make are be- cause they did not read the questions carefully.
Reporting ambiguities or tell us why the ques- tion is confusing only if you need to
Explaining why you did not choose another option when we ask you. Giving us more in- formation can you help you win more bonus.
Sometimes we choose not to show you certain tables and columns if we know for sure they not needed.
L Beyond Text-to-SQL
Use the highlight functionality if that helps you to reason across tables.
Our framework can be generalized to other seman- tic parsing applications more broadly, where
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.
be generalized other types of executable semantic parses, such tensor manipulation commands, visualization programs (Chen et al., 2021c), or dataflow graphs (Semantic Machines et al., 2020);
the SQL program
Page 18 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 battle that lost both these ships. So you should choose A, "no result found".
the database schema can be generalized to in- clude any context that affects the mapping of u to 8, e.g., the conversational history preced- ing u, and the input type required by program s;
Page 19
Takeaways: Choose result_fourr if answer satisfics the question.
the input database can be generalized any well-typed input if is function, be the program state (e.g., mapping from variable names to their values) if is a step in a procedural program;
Page 20 To summarize, here are a couple of things you need to remember to answer the ques- tions correctly:

---

the database query result s()) can be generalized to the intended effect of given i, which includes not only an answer or a table, but also an output images, side effects such as file updates (e.g., updates to a database or a document), or robotic actions.
lined in Appendices A-B. It would also be desir- able refine and speed up our heuristics for the challenging problem of finding simple inputs that distinguish among SQL queries. Finally, we look forward to future work that extends APEL to other semantic parsing applications.
Applying APEL to a new type of semantic parsing application, rather than utterance-to-SQL, would require the following components:
M Simulation Experiments on Regex
We include an additional experiment on regular expressions to help the readers understand how to apply APEL to semantic parsing tasks other than SQL..
A seed semantic parser that is likely to generate a short list of candidates that contain the correct program. This requirement is not hard to satisfy in many applications, given that large language models achieve often achieve high top-k accuracy generating simple Python snippets (Chen et al., 2021a). JSON data (Poesia al., 2022). Lispress (Shin et al., 2021) and SQL programs (Scholak et al., 2021b; Rajkumar et al., 2022) with only a few training examples and are likely to continue improving (Kaplan et al., 2020). For example, we achieved 95% top-32 accuracy on SPIDER with- out any task-specific engineering beyond few-shot prompting (e.g., specialized architectures (Wang al., 2020), decoding constraints (Scholak al.. 2021b). etc).
Dataset. We used the dataset from Ye et al. (2020), which aims synthesize a regular expres- sion from a natural language description and few strings that should be accepted and rejected by the regex. For example, an utterance u could be
"This is list of three comma sepa- rated 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 const(<cf>)
(
An algorithm to find an simple informative pro- gram input i that satisfies c. Our method $3 generates random databases by using an existing sample database as a reference and greedily drops rows optimize the objective in equation (5). Fu- ture methods could potentially speed up the op- timization process with learned neural network (Chen et al., 2018) or a constraint solver (Chu et al., 2017).
const (erzaa)),,epeaatrraaa
1 (
concat(s) concat concat
or const repeatrange 1, 4)), concat ( <,>, concat or (const(<cf>) const(<rzqp)) repeatrange (<num>, 1, 4))))))>
const(<cf>>,
The program s maps from any input string i to boolean output of or O. Thus, an o-selection question simply asks whether the string i should be accepted rejected.
A graphical interface that enables the annota- tors to easily inspect the input i and choose the correct output o, where o can be generalized from database tables, strings, or numbers to calen- dar events (Andreas et al., 2020), voxel structures (Wang et al., 2017), etc. Careful interface design ($6.1) can significantly reduce the effort required from the annotators.
We used the development split to prompt GPT-4 (OpenAI, 2023) 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.
In summary, APEL is general framework for clarifying the semantics of natural language utter- ances. It elicits information from humans about how the semantic forms should behave when exe- cuted on particular inputs.
Seed Semantic Parser. We prompted GPT-4 with few-shot demonstrations to create a seed mantic parser. We sampled 50 demonstrations from the development split to simulate small "training set" of expert labels. For each utterance u we sam- pled a candidate program from the seed semantic parser 50 times, where each time we randomly
In this paper we demonstrated the value APEL on a text-to-SQL. task. Some future work is out-

---

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 semanti- cally equivalent ones (semantic equivalence reg- exps can be tested exactly). Finally, we define Po to be the empirical distribution of the top-10 10 equiv- alence classes. The top-1 accuracy (seed parser) is 64% and the top-10 accuracy (ceiling) is 77%.
input string we select at each round.
Results. After interacting with a simulated an- notator 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 1 11.6; this suggests that optimizing for simplicity is successful.
Simple and Informative Program Input. We wish choose among several candidate programs (or more precisely, equivalence classes). For each pair of candidate programs 81 and $2, we sample 200 program input strings such that (1) * 82 (1). 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 proxy for simplicity.
To evaluate whether the above procedure is effec- tive in generating simple and informative program input, we consider baseline that only generates an input string that would be accepted by the highest- ranking candidate regex, again using the imple- mentation from Ye et al. (2020). Intuitively, this baseline tries to check the highest-ranking candi- date program, by determining whether 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, ac- tively tries to distinguish among the candidates. hopes to gain up bit of information about the correct candidate (this is the maximum informa- tion that can be derived from the annotator's 1-bit response). An input string has IG ss 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 climinate about half of the candidates (ef. Littlestone and Warmuth, 1994).
That said, any input string i sampled by our pro- cedure will distinguish between two of the can- didate programs, and hence will have positive in- formation gain. The annotator's response (if as- sumed to be correct) will eliminate one of those candidate programs, and perhaps others. Thus, it will take at most 9 rounds of oracle annotation for rule out 9 incorrect equivalence classes from our original 10 classes, thus achieving the can- didate ceiling ($4.4), regardless of which sampled


Reviews:
[{"review_id": "CpQS4mXdsU", "reviewer": "Reviewer_Vovf", "summary": "", "questions": "* Please see the second bullet point in the above section \n* L297+ \"We randomly sampled 200 prompts for u by choosing different (uk , sk )\". Does this mean there are 200 in-context examples for each test utterance? If so, why choose such a large number?\n* Why feeding the original Spider database in oracle setting (Table 1)? \n     * The paper mentioned that \"Our method also generates much simpler databases than the sample databases, which contain on average 33,295 records and prevent the human annotators from selecting the correct output effectively\" but isn't this the **oracle** setting where the correct response is **always** selected (L350-L352)? How is a human annotator related here?\n     * \"our database generation method leads to higher accuracy since it optimizes information gain\" -- my question is that since the original DBs are way larger, won't they cover more possible data combinations and serves as a superset of the synthetic databases?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for appreciating our framework and the problem we proposed! \n\nAs you have mentioned, our core contribution is a framework that pieces multiple components together (e.g., semantic parser, database generator) to indirectly elicit program labels. We consider **recent advancements on semantic parsers to be complementary** to our contribution and will improve APEL.\n\nRe: soundness, **our submission does NOT claim that the specific system we built is the current SOTA**. Our user study was run in 2021 right after codex-001 was released, a year earlier than [1, 2]; therefore, the exact system we built is unlikely to be SOTA after two years, as do most other ML systems.\n\nRe: excitement, **our conceptual takeaways will likely have lasting value**, even though our current system is not SOTA. As AI will support humans on more difficult tasks, supervising them is challenging for humans because direct labeling is difficult. Our paper is a first step tackling this general problem.\n\n> “Lacks comparisons with approaches such as self-consistency [1] and CodeT [2]”\n\n[1,2] are semantic parsing methods that are complementary to our contribution. We focused on the following question: given a seed semantic parser, such as [1, 2], how to use human non-experts to continue improving it. Nevertheless, thanks for bringing up [1, 2] and our updated related work will include them.\n\n> Why few-shot learning on SPIDER instead of 0-shot? Does APEL also need database values? Is that a limitation of APEL?\n\nThe mathematical framework of APEL **requires neither few-shot learning nor the database values**. The specific system we built in 2021 did require few-shot examples to achieve reasonable top-k accuracy since it was based on Codex-001, and it did require values from the SPIDER dataset to generate realistic-looking data. However, future work can use semantic parsers with stronger 0-shot performance and database values generated by language models [3].\n\n> Clarification: L297+ 200 in-context examples for each test utterance?\n\nWe retrieved in-context examples from a pool of ~25 examples (50% of the dev set per database), and created 200 prompts by selecting random selections and permutations of 4 or 8 of them to denoise (E.1). Future developers using APEL can start with a stronger semantic parser that does not require significant prompt-engineering effort.\n\n> Clarification: “We require the model to predict DISTINCT keywords and string literals.” Wouldn’t the execution only need the synthetic databases?\n\nL317 points out that the previous evaluation [4] does not require the SQL to be complete (e.g., predict the string literals). However, our paper does require the SQL to be complete to determine the correct semantics, so we reported a stricter evaluation metric.\n\n> Clarification: Why is the human annotator mentioned (L350-L352) if  the correct response is always selected?\n\nIndeed, Section 5 used a simulated perfect annotator instead of human annotators. L350 was a side comment which emphasizes that such a simulation assumption is unrealistic for humans using the baseline – large databases from SPIDER.\n\n> Clarification: Larger databases always have high information gain?\n\nConsider a Table with two columns (student_name, pet_name) where each row means that student_name owns pet_name. Consider two utterances U1,U2 and databases D1, D2\n\nU1: “Find the set of all students” → SELECT DISTINCT STUDENT_NAME FROM TABLE\n\nU2: “Find the set of all students with at most 1 pet” → SELECT STUDENT_NAME FROM TABLE GROUP BY STUDENT_NAME HAVING COUNT(PET_NAME) <= 1;\n\n(D1)\n\n| student_name | pet_name |\n| ----------- | ----------- |\n| Alice | Dog |\n|Alice | Cat |\n\n(D2)\n\n| student_name | pet_name |\n| ----------- | ----------- |\n| Alice | Dog |\n\nD1 is larger than D2; however, U1 and U2 have the same correct answer on (D1) but not on D2.\n\n> Clarification: Why feed the original Spider database in oracle setting (Table 1)?\n\nEven a perfect annotator might not achieve 100% SQL annotation accuracy, since the generated databases might fail to make two candidates return different results. Table 1 compares the database generated by our method to the SPIDER’s database to show that it is effective to optimize databases for simplicity and information gain.\n\n[1] Self-Consistency Improves Chain Of Thought Reasoning In Language Models\n\n[2] Codet: Code Generation With Generated Tests\n\n[3] Language Models are Realistic Tabular Data Generators\n\n[4] Semantic Evaluation for Text-to-SQL with Distilled Test Suites", "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": "* The setting of utilizing labels from non-experts is interesting. To my best knowledge, it is not well studied in the literature as well.\n* The idea of asking annotators to select the correct *program execution* is intuitive and neat. \n* The proposed APEL framework is well-motivated and mathematically sound", "reasons_to_reject": "* The experiment lacks comparisons with existing approaches. For instance, existing works such as self-consistency [1] and CodeT [2] use execution consistency to select the correct programs. In APEL case, the synthetic program input $i_t$ can be treated as inputs in each round. How does APEL compare to such methods which do not require annotators in the loop?\n* The non-standard split of the SPIDER dataset is not well explained and indicates the limitation of applying APEL to zero-shot settings. As mentioned in L315-L320 \"These numbers are not comparable to prior works, which usually evaluate on unseen database domains in a zero-shot manner (harder than our setting) but do not require predicting string literals and DISTINCT keywords, which we need for execution.\" I am wondering (1) how much information APEL needs from the database, only the schemas or the data as well? (2) wouldn't the execution only need the synthetic databases?\n\n[1] Self-Consistency Improves Chain Of Thought Reasoning In Language Models\n\n[2] Codet: Code Generation With Generated Tests", "questions_to_authors": "* Please see the second bullet point in the above section \n* L297+ \"We randomly sampled 200 prompts for u by choosing different (uk , sk )\". Does this mean there are 200 in-context examples for each test utterance? If so, why choose such a large number?\n* Why feeding the original Spider database in oracle setting (Table 1)? \n     * The paper mentioned that \"Our method also generates much simpler databases than the sample databases, which contain on average 33,295 records and prevent the human annotators from selecting the correct output effectively\" but isn't this the **oracle** setting where the correct response is **always** selected (L350-L352)? How is a human annotator related here?\n     * \"our database generation method leads to higher accuracy since it optimizes information gain\" -- my question is that since the original DBs are way larger, won't they cover more possible data combinations and serves as a superset of the synthetic databases?", "paper_topic_and_main_contributions": "* This work studies a new scenario of improving semantic parsing with labels from *non-expert* programmers. They use text-to-SQL as an example for the study. \n\n* This work proposes APEL framework which leverages the annotation on *program executions* which does not require the annotators to understand the SQL. It has the following steps: 1. generate the seed programs 2. generate synthetic databases that could maximize the information gain for selecting the candidate programs 3. update the posterior probability of the candidate programs. Repeat 2, 3.", "excitement": 5, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8VAP2dvexo", "reviewer": "Reviewer_EWXL", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": 5, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for reading our paper comprehensively and appreciating our contribution.\n\n> The errors in Section 6.6 were found by experts. How does it contribute to the presentation of APEL, and how repeatable it is?\n\nRe: why we presented it. Since Table 2 claimed that the previous annotator accuracy is only 75%, it might be useful for the readers to qualitatively understand what annotation errors were present.\n\nRe: how repeatable it is with non-experts. All mistakes presented in Section 6.2 were actually also uncovered by non-experts, since the mistakes in the program became obvious when APEL presents an input-output example. Nevertheless, experts were required to categorize and present them. We will make this clearer in the updated version.\n\nFinally, APEL might be useful not only for non-programmers but also for programmers, as debugging might be easier with simple input-output examples. Future work can more systematically study how APEL could help experts find subtle bugs.\n\n> Only one (small) dataset with 240 utterances is investigated\n\nOur results achieved both a substantial effect size (59%->75%) and a significant p-value of. < 0.001 (Table 2), so we believe our conclusion is sound. We did not have enough resources to collect large-scale high-quality human annotations. \n\nIn addition to human evaluation, Section 5 ran larger scale evaluation on 520 utterances in the development set with simulated human annotators and Appendix M evaluated on 630 utterances for regex expression. In both cases, the APEL accuracy significantly outperforms Codex’s Pass@1 with simple inputs, indicating the robustness of our conclusion.\n\n> Tradeoffs between the costs of human annotation in APEL vs. the amount of additional data we can collect.\n\nThanks for bringing this up! Our paper did not study the exact economic benefit of APEL in a deployment environment. However, it provides an alternative, which collects semantic parsing data with non-experts, who might be cheaper and require less time to train in practice. We will acknowledge this limitation in our updated version, and look forward to future work that uses APEL-related methods for realistic downstream applications.", "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": "* The paper is well-written with key ideas presented up front, claims are not overstated\n* An ablation on the quality of database selection (as compared to SPIDER’s original database) is conducted that helps validate the effectiveness of the approach\n* Extensive analysis is provided on the case study performed on the SPIDER development data\n* The paper provides extremely thorough implementation details \n* There is clear discussion of annotator demographics and compensation.\n* The limitations are clearly stated – a reasonably good seed parser is needed as well as an efficient procedure to find simple/informative program inputs.", "reasons_to_reject": "* The comparison between Codex P1 accuracy and APEL (which uses human annotators based on a seed parses from Codex) makes sense if we interpret Codex P1 as a competing semantic parse collection strategy. However, in a practical setting we need to trade off the costs of human annotation through APEL vs. the additional volume data that could be collected by Codex by training semantic parsers with the resulting data and applying it to new domains. This is touched on briefly in the limitations and the Appendix.\n* It's unclear how repeatable the process of uncovering subtle errors with APEL is (Section 6.6), as these were uncovered by experts (two authors) – this is a nice result, but what makes this specific to the APEL approach is a bit unclear from the main body of the paper.\n* Only one (small) dataset with 240 utterances is investigated (worth noting that the Appendix shows how the approach can be extended to other applications)", "questions_to_authors": "", "paper_topic_and_main_contributions": "The authors propose a semantic parsing (program) annotation approach that can be carried out by non-programmers, offering a potentially scalable way to collect difficult annotations for tasks that typically require expert annotation. The key insight of their proposed approach, APEL, is to find a simple synthetic program input database that leads to different outputs on candidate programs being evaluated for a given utterance. Non-programmer annotators can then select the program that leads to the correct answer without reading the program itself. The process is repeated iteratively. In a case study on SPIDER development data, the resulting system reaches the same accuracy (75%) as that of database experts.\n\nThe authors formalize the APEL approach to select a candidate program input (i.e. database) as maximizing the expected information gain at each step, i.e. inputs that lead to different results between candidates, given a constraint of containing at most 30 records (to reduce annotator burden). Their approach relies on a high-quality seed parser (in their case, Codex with few-shot prompting). In addition to the case study with human annotators, the authors validated their approach using a simulation-based approach.", "excitement": 4, "reproducibility": 5, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "* 050 - then -> to\n* 329 - how often are any of the top 16 candidates correct\n* Missing reference (??) in footnote on page 13"}, "extra_text": {}}, {"review_id": "zxMjZ7LIN2", "reviewer": "Reviewer_uyi9", "summary": "", "questions": "- Were there any qualitative methods or results used in the human subject study? Structured interviews? Post-surveys? etc.\n    - The rebuttal addresses these questions.  As for my comment about low participant pool size, I would reiterate that this is, in general, a small size.  One best paper at NAACL (which is not HCI, incidentally) is not convincing given other studies which much larger participant pools in the HCI, AI, and SE communities.  There is perhaps some subtlety relating to the degree to which each participant is involved.  For example, smaller participant pools might be acceptable for studies with a more ethnographic approach.   Regardless, I don't think this is a dealbreaker for this submission. \n- Can you describe in more detail how APEL could generalize to non-SQL settings?  In broad strokes, I can understand how you could generate candidate programs and inputs, but for a non-programmer participant, how would something like APEL show, say, C/C++ programs?  What level of abstraction would be considered? Single function? A few lines of code? A whole compilation unit?\n    - The authors clarified scope in their rebuttal.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 5, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Any qualitative interviews?\n\nThanks for this very insightful comment. We did not have a formal interview process in our experimental design, and retrospectively it was indeed a missed opportunity. \n\nHowever, we did talk to many of our subjects after the study, and we can discuss them in the updated version. Some example insights include:\n- Some subjects complained that the annotation process was boring and they would not want to do it a second time. Future work can design better UIs and interactions to make the annotation more engaging. \n- While most questions are straightforward, some examples are particularly hard (e.g., requires adding several 10-digit numbers). Though we set up a time limit for each question, these questions consumed a lot of mental energy. Future work could include an option for the users to skim through all the questions and solve the easier ones first.\n- Some utterances were inherently vague. Without external affirmation that these questions were indeed vague, some subjects wasted too much time trying to guess how to interpret the question. Future work could include an entry for the subjects to indicate their confidence, rather than choosing a discrete option. \n\n> The result is found in a small subject pool. Is this a coincidence? \n\nAs acknowledged in your review, we conducted a statistical significance test. We found both a substantial effect size (59%->75%) and a significant p-value of < 1e-3 (Table 2), so it is unlikely to be just a coincidence.\n\nIn addition to human evaluation, we corroborated our finding with a larger set of utterances with simulation. Section 5 ran larger scale evaluation on 520 utterances in the development set with simulated human annotators and Appendix M evaluated on 630 utterances for regex expression. In both cases, the APEL accuracy significantly outperforms Codex’s Pass@1, indicating the robustness of our conclusion.\n\nFinally, we would like to note that 11 subjects are not particularly small within the HCI literature; for comparison, the NAACL 2022 best paper [1] only involved 9 subjects. \n\n> How does APEL generalize to non-SQL settings?\n\nEmpirically, we provided additional experiments on Regex in Appendix M, and a concurrent work [2] used a similar framework to synthesize python snippets (evaluated with simulated humans). We believe that it is also conceptually straightforward to synthesize function snippets in some other languages, such as pandas, pytorch, numpy, matplotlib: in these languages, the inputs and outputs are intuitive to understand, and prior works have studied programming by example in these domains (L603). We agree with you that it is still challenging to extend APEL to any programming language for any programming context (e.g. an entire compilation unit), but we do not make such an unwarranted claim either (see below). \n\n> Possible Overclaiming about generalizability to other languages?\n\nOur submission does not try to claim that “APEL can enable non-programmers to program for any application”. To prevent potential misinterpretation, our submission has explicitly restricted the scope by putting the phrase “a case study in Text-to-SQL” in the title, emphasizing the limitation at the end of the intro (089), and discussing future work in Section 7, the Limitation section, and Appendix Section I. **If specific sentences seem misleading/overclaiming, feel free to point them out so that we can update them for our next version.**\n\nWe absolutely agree that in order to label more complicated languages (e.g., C++) in more complex scenarios (e.g., entire compilation unit), “significant investment of research effort into understanding the best way to present inputs and candidate programs.”, as we have also pointed out at the end of our intro (L089) “APEL is a preliminary step towards enabling non-programmers to label arbitrarily complex programs.” To inform future work, we made our best effort to concretize how APEL should be applied to other programming languages by providing an additional experiment in Regex in Appendix M and discussing other languages in Section 7. \n\nWhile APEL itself is unlikely to be the ultimate solution, the following contributions from APEL will likely endure:\n- We designed an evaluation protocol by comparing machine-assisted non-expert annotations with expert annotations.\n- We proposed to label indirectly when direct labeling is challenging.\n- We used execution results to help non-programmers supervise semantic parsers,  connecting the paradigm of semantic parsing and programming by example. \n- We optimized the questions for the annotators to maximize information gain while keeping it simple.\n\nWe look forward to future work that revises and extends our framework to more complex programming tasks. \n\n\n[1] Automatic Correction of Human Translations\n\n[2]  Interactive Code Generation via Test-Driven User-Intent Formalization\n\n[3] DS-1000: A Natural and Reliable Benchmark for Data Science Code Generation", "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": "- Timely and relevant topic -- software engineers may increasingly depend on automation to produce candidate programs (e.g., through Codex / Copilot-like technologies).   Thus, is it important to understand how people can help guide automated program synthesis techniques as described in this paper. \n- Well executed evaluation.  The authors show a significant increase in accurately labeling natural language queries with SQL programs with respect to reasonable baselines. \n- highly intuitive technique based on reasonable insights about active learning and human-in-the-loop labeling.\n- Well-written and well-organized manuscript with a reproducible protocol.", "reasons_to_reject": "- Very small human subject pool for this type of work.  While the authors report statistical significance, I am a bit skeptical about possible coincidences of performance achieved.  \n- No qualitative methods used in human subject study.  There is a missed opportunity to learn more from the non-programmer participants about their approach to labeling. \n- possible overclaiming about the paper's generalizability to new languages.  In this setting, Text-to-SQL involves a fairly direct path for executing candidate seed programs to generate outputs.  It is less clear how (1) intuitive inputs for non-programmers would be selected in non-SQL settings, and (2) how candidate programs would be executed to provide useful outputs for non-programmers to assess each candidate.  The authors discuss programming by example in the related work, but I am skeptical that this technique could extend to new programming languages without a significant investment of research effort into understanding the best way to present inputs and candidate programs.", "questions_to_authors": "- Were there any qualitative methods or results used in the human subject study? Structured interviews? Post-surveys? etc.\n    - The rebuttal addresses these questions.  As for my comment about low participant pool size, I would reiterate that this is, in general, a small size.  One best paper at NAACL (which is not HCI, incidentally) is not convincing given other studies which much larger participant pools in the HCI, AI, and SE communities.  There is perhaps some subtlety relating to the degree to which each participant is involved.  For example, smaller participant pools might be acceptable for studies with a more ethnographic approach.   Regardless, I don't think this is a dealbreaker for this submission. \n- Can you describe in more detail how APEL could generalize to non-SQL settings?  In broad strokes, I can understand how you could generate candidate programs and inputs, but for a non-programmer participant, how would something like APEL show, say, C/C++ programs?  What level of abstraction would be considered? Single function? A few lines of code? A whole compilation unit?\n    - The authors clarified scope in their rebuttal.", "paper_topic_and_main_contributions": "This paper presents an approach to annotating natural language descriptions with SQL queries using non-programmers.  The authors suggest that, rather than synthesizing programs from whole cloth, non-programmers can be shown example candidate programs as well as input/output pairs capturing program behavior to determine the correct candidate program to use.   The technique involves generating seed programs from given natural language queries.  The seed programs represent (potentially incorrect or incomplete) queries that are then fed to non-programmers.  In addition, seed input data is produced via fuzzing, and the non-programmer helps determine which seed program is correct by considering the natural language query, input, and corresponding output. \n\nThe authors demonstrate the viability of their approach using a human study of 11 non-programmers.  The authors show the protocol used and share training materials.   They report their approach can help label natural language queries with SQL queries as accurately as existing techniques requiring programming expertise.", "excitement": 4, "reproducibility": 5, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "N/A", "Typos_Grammar_Style_and_Presentation_Improvements": "This is a well-written manuscript."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a method for annotating (and improving) semantic parsing with labels from non-programmers, using text-to-SQL. They enable these non-expert annotations by having annotators judge program execution, rather than programs directly. They introduce the APEL framework, which searches for synthetic inputs that lead to different outputs on candidate programs, and then elicit correctness judgments that can be used to fine-tune parsers. They find in a case study that their method can reach the same annotation accuracy as annotations using experts.

The reviewers are in agreement that the paper is well-written, with an interesting, intuitive, and novel framework and methodology. The reviewers also express that the paper features clear presentation of implementation details, extensive analyses, and sensible validation of the approach. Some questions and concerns were raised, but were largely addressed in discussion. Overall I judge that this is a strong submission and a worthy contribution to the conference.
Decision: Accept-Main