Synchromesh: Reliable Code Generation from Pre-trained Language Models
Authors: Gabriel Poesia
Alex Polozov
Vu Le
Ashish Tiwari
Gustavo Soares
Christopher Meek
Sumit Gulwani
Venue: ICLR 2022 Poster (2022)
Keywords: program synthesis
language models
code generation

Abstract: Large pre-trained language models have been used to generate code, providing a flexible interface for synthesizing programs from natural language specifications. However, they often violate syntactic and semantic rules of their output language, limiting their practical usability. In this paper, we propose Synchromesh: a framework for substantially improving the reliability of pre-trained models for code generation. Synchromesh comprises two components. First, it retrieves few-shot examples from a training bank using Target Similarity Tuning (TST), a novel method for semantic example selection. TST learns to recognize utterances that describe similar target programs despite of differences in surface natural language features. Then, Synchromesh feeds the examples to a pre-trained language model and samples programs using Constrained Semantic Decoding (CSD): a general framework for constraining the output to a set of valid programs in the target language. CSD leverages constraints on partial outputs to sample complete correct programs, and needs neither re-training nor fine-tuning of the language model. We evaluate our methods by synthesizing code from natural language descriptions using GPT-3 and Codex in three real-world languages: SQL queries, Vega-Lite visualizations and SMCalFlow programs. These domains showcase rich constraints that CSD is able to enforce, including syntax, scoping and typing rules. Across all languages, we observe complementary gains from CSD and TST in prediction accuracy and in effectively preventing parsing, type and run-time errors.

Published as a conference paper at ICLR 2022
SYNCHROMESH: RELIABLE CODE GENERATION FROM LANGUAGE MODELS
Gabriel Poesia*t Stanford University goesia@@stanfoddeed
Oleksandr Polozov*
X, the moonshot factory pol owwv@googleeee.ooooooooooooooo e com
Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, Sumit Gulwani
Microsoft Research, Redmond
{levu, astiwar, gustavo. soares, meek, www.tgggmmicrossft.cco
ABSTRACT
Large pre-trained language models have been used to generate code, providing a flexible interface for synthesizing programs from natural language specifications. However, they often violate syntactic and semantic rules of their output language, limiting their practical usability. In this paper, we propose SYNCHROMESH: a framework for substantially improving the reliability of pre-trained models for code generation. SYNCHROMESH comprises two components. First, it retrieves few-shot examples from a training bank using Target Similarity Tuning (TST), a novel method for semantic example selection. TST learns to recognize utter- ances that describe similar target programs despite differences in surface natural language features. Then, SYNCHROMESH feeds the examples to pre-trained lan- guage model and samples programs using Constrained Semantic Decoding (CSD): a general framework for constraining the output to a set of valid programs in the target language. CSD leverages constraints on partial outputs to sample complete correct programs, and needs neither re- re-training nor fine-tuning of the language model. We evaluate our methods by synthesizing code from natural language descriptions using GPT-3 and Codex in three real-world languages: SQL queries, Vega-Lite visualizations and SMCalFlow programs. These domains showcase rich constraints that CSD is able to enforce, including syntax, scope, typing rules, and contextual logic. We observe substantial complementary gains from CSD and TST in prediction accuracy and in effectively preventing run-time errors.
INTRODUCTION
Large language models (LLMs) trained on massive corpora of unsupervised data have been shown to perform a wide range of tasks, including natural language generation, semantic parsing and sen- timent analysis (Brown et al. 2020 Devlin et al. 2019; Raffel et al.) 2020). This can achieved without task-specific training. but rather by adapting the model to each task at test-time using tex- tual prompts, which can contain examples and natural language descriptions.
many cases, this methodology was shown to provide good performance, reducing the need to annotate large datasets for each task of interest (Brown et al. 2020 Shin et al. (02I).
An important application of LLMs is in synthesizing programs from natural language descriptions (Austin et al. [021]] Chen et al.) 202T). But this task still challenging for LLMs.. First, they commit conceptual errors, generating code that misses the intent behind the given description. For example, when asked to reverse an array, the model might generate code that simply swaps the first and last elements. Indeed, users of current natural language-to-code systems report that models often produce code that is unrelated to their query (u et al. 2021).
* "Equal contribution.
1 Work done during an internship at Microsoft with the PROSE team. Work done while Microsoft Research (oo) ozovêmi crosoft.com

---

Published as a conference paper at ICLR 2022
Question: Which has the high number of ceparting lights!
TST
Synchromesh
CSD Program generation
Language
selection
Prompt
Exampla
Retum techniiian...
FROM city Airports
tron FROM "echntctor
GROUP COUNTIY) DESC LIMIT
CE Constraint Validation
ON Seanceltrport stack GROUP BY clty BESC LIMIT
Exsmple
examples
Figure 1: Overview of the SYNCHROMESH framework. Given the user's query, high-relevance examples are first retrieved with Target Similarity Tuning (TST). Then, a program is incrementally sampled via Constrained Semantic Decoding (CSD), which queries completion engine (CE) to enforce constraints during code generation without re-training or fine-tuning the language model.
Even when they capture the right intent, LLMs can still make implementation errors: the generated code can fail to execute. For reversing array, model might generate loop with the correct structure but with an off-by-one error, causing a runtime exception. These errors are common even with very large models. For example, [Austin al. (202T) tested models with up 137B parameters on generating short Python programs from natural language. Still, 47% the failures were due to syntax, typing or run-time errors (as opposed to running but producing incorrect output). This is in line with theoretical results in Merrill et al. (2021) showing that programming language semantics cannot be fully inferred from ungrounded data. Together, both observations suggest that simply scaling up LLMs might be ineffective to obtain reliable performance, especially for longer programs.
In this paper, we address both conceptual and implementation errors with SYNCHROMESH, frame- work for reliable code generation from pre-trained models. Since LLMs are highly sensitive to which few-shot examples are given their prompt, we propose Target Similarity Tuning (TST): method for dynamically selecting semantically relevant examples for a given description. TST mit- igates conceptual errors by learning to select examples with similar intent, even when their natural language descriptions seem unrelated in form. Given relevant examples, with Constrained Semantic Decoding (CSD), a novel method for enforcing rich syntactic and seman- tic constraints during code generation top of frozen language model. Rich manguage-spectine constraints, ranging from syntax validity to scoping and type-checking. can be implemented under the simple abstraction of completion engines (CE). CSD aligns these constraints with the language model's 's token vocabulary by leveraging Brzozowski language derivatives (Brzozowski 1964). This guarantees that all sampled programs satisfies the implemented constraints, preventing whole classes of implementation errors by construction. The pipeline is illustrated in Figure
then generate programs
We demonstrate the generality of SYNCHROMESII in three real-world languages: SQL (database queries), Vega-Lite (data visualization) and SMCalFlow (calendar applications). In experiments with GPT-3 and Codex, we observe that SYNCHROMESH can eliminate whole classes of errors that make outputs from unconstrained models either fail to execute produce trivial results (e.g., empty charts). Furthermore, eliminating invalid programs consistently improves prediction accuracy. In summary, we make the following contributions:
We propose Target Similarity Tuning for selecting few-shot examples based on the similar- ity of the programs they describe, improving relevance and downstream performance.
We introduce completion engines as an abstraction that can implement rich classes of se- mantic program constraints, as we demonstrate SQL, Vega-Lite and SMCalFlow.
We introduce a general, constraint-on -bbserrnn-observing decoding algorithm, which aligns program- ming language constraints with the language model's 's token vocabulary.
We evaluate our method in three natural language-to-cool tasks. CSD and TST both show strong complementary gains in output validity and prediction accuracy across domains.
TARGET SIMILARITY TUNING
In this section, we first overview the challenge posed by conceptual errors in programs synthesized by LLMss. We then introduce TST, which improves performance through more relevant example
2

---

Published as a conference paper at ICLR 2022
Question:
Prompt
"Whith dity has the highest number of diraprts?
b
Viich Nighest slevatior?'
SELECT city FRM Alrgetts
GPT-3
casee as Flevatice aest 1007
Dangle N7:
columm "NunderOfSsiport table "Arports"
S-BERT
2 Prompt
S-BERT
kamplt 21:
"hetarr with tachelctane."
SELECT Techntctes
GPT-3
M0LECT Clia PREN Air pnrs
SKUPP BY City
PRDE COUNTCY) DESC LIKIT
Figure 2: Example of Target Similarity Tuning improving example selection for synthesizing a SQL query. In (a), the prompt example missed the key query structure (grouping and counting). With this example, GPT-3 generates invalid query (b). With TST, we retrieve relevant example which GPT-3 successfully adapts to answer the user's question (c).
selection. Throughout, we will use a real example of synthesizing SQL database query to answer a question posed in natural language.
Suppose data analyst has relational database of airports and wants answer the following ques- tion: "Which city has the highest number of airports?" One procedure for turning this description into SQL query is to an LLM such GPT-3 (Brown al. 2020) Codex (Chen al. 2021). To prompt the model for the task at hand, we would feed it with a natural language description of the task and selection of input-output examples.
Given the analyst's question, how do we select the most relevant examples from a training pool? Liu al.] (2021a) proposed retrieve examples with similar natural language descriptions
ing a pre-trained paraphrase detection model. Figure 2h shows the most similar example from the Spider natural language-to-SQL dataset (Yu al. 2018 according Sentence-BERT (Reimers & Gurevych 2019). The query "Which city has the highest elevation?" is similar on surface level: also asks "Which city has the highest D?" This training query asks about "elevation", a property that is readily available as column in the Airports table. Figure ( shows GPT-3's output when given this and few other examples. The model attempts to mimic the top example, referring to nonexistent column "NumberOfAArpooe based on description similarity and not SQL query similarity. example had simplistic structure that was significantly different from the structure of the desired SQL query, and this contributed to the failure at Point (b) in Figure 2
The issue is that we picked the example in the prompt
fact, the SQL query in the chosen
We want retrieve examples that have relevant program structures for the test query. We do using our fine-tuning scheme called Target Similarity Tuning (TST). Formally, suppose D a dataset of programs and associated utterances, with D; (p:, uz). Let S(Pa, Pb) E [0, 1] denote normalized similarity metric between programs. So is a pre-trained similarity model for natural language predict the similarity between target programs given by
sentences, TST consists in fine-tuning S from their descriptions, Precisely, we minimize the mean-squared error loss:
LTST (0) = Es,j-D [Sa [u:, u,) S(tr,
We define S uusing the classical tree edit distance algorithm from Zhang & Shasha 1989) to compare Abstract Syntax Trees (ASTs). Figure 2 shows GPT-3's output when given examples selected with TST. Now, the output query is correct: it performs a "group by" on the "City" column, and sorts by the count of records in each group. This structure TST, corresponding to "Return the team with the most technicians". Even if the analyst's question and this utterance are drastically different in natural language, they share similarity in the SQL query that they describe. The TST objective is able to properly capture this fact. As our experiments show in Section 4. TST significantly boosts the performance of both GPT-3 and Codex.
already present in the top example selected by
CONSTRAINED SEMANTIC DECODING
We now present Constrained Semantic Decoding (CSD) as approach eliminate implementation errors from code generated by LLMs. We first illustrate CSD with an example, and then formalize it using the abstraction of CEs.
3

---

Published as a conference paper at ICLR 2022
Question:
Prompt
SELECT city AltrectCaaa 4.12.50urocsi/pp
which the Highest number of deperting Rights?"
CRCUP BY city
Thetur the tear with the trchridams"
ORDER BY COUNT(-) DESC LIKET
"AapoitCodd""
S-BERT
SELECT ceah
FROM Techvican
SELECT city
ORDER CouNTey pesc
CSD
Flights 2001 pirports 72
dwwoeeGddeaurrrtrrrr... T7.MMrportceee
LIMIT1
Thkwingpet
ORDER COUNT(C)) BSSC LIKIT
SQL Completion
Figure 3: Example on CSD generating a SQL query. Given the prompt, GPT-3 makes mistake (a) when generating the JOIN condition. CSD is able to prevent this error by (b) keeping track of table aliases and constraining the model to respect the database schema.
The example in Figure 2 showed that TST can help LLMs generate the correct program. In gen- eral, however, TST only helps LLMs by guiding toward the correct structure, but the model still needs to fill all the specific implementation details correctly. Figure 3 shows case where the model cannot simply adapt one example from the prompt. Here, the user's query is "Which city has the highest number of departing flights?" This query is similar the previous one in fact, TST retrieves the same top-1 example as before. But now the correct SQL query needs to join the "Airports" and "Flights" tables. GPT-3 generates the join condition Flights.Airportt Airports. Srrports.Souree..r Swwrcuuururrrrrt but this condition has a subtle error: the column names of the two tables are swapped. Thus, this query fails to execute. In general, unconstrained language models often make such implementation errors: using undeclared variables, losing track of nesting levels when producing complex expressions, or calling functions using arguments of the wrong type. Even the smallest of such emrors prevents generated code from executing.
CSD prevents implementation errors by construction (as opposed to repairing after-the- fact). Imag- ine we have access an oracle, which call CE, that take partial program and return all tokens that can extend that partial program toward a complete correct program. When the LLM is generating the program token by token, CSD ensures that the next token sampled from the set returned by the CE.
In Figure after generating "T1 inside the "on" clause, our SQL CE resolves the alias and constrains the model to output one of the colurns from the "Flights" table. This fixes the error seen previously during generation and produces the correct SQL query.
3.1 COMPLETION ENGINES
We now formally define CEs. Let Σ be base alphabet, and ΣL E' be the (potentially infinite) set of tokens of the target language. Our goal is to sample programs from a language C Mj set of tokens. We use
the set of valid programs. A CE Cr. is partial function from Σÿ, regular expression over Σ to represent a set of tokens. The strings in the domain of Cr are called completion points, and CE satisfies the following axioms: (Al) The empty string and every p E L must be completion points. For every E L, Cp(p) = r'8', where r'S' is the regular expression that matches the stop token. (A2) If 29, is completion point and t fully matches C2 (s), then their concatenation st must also be completion point. (A3) The CE is exhaustive; that is. if is completion point and s tty, where to is a token, then should be completion point and Cz()) should match ln. Furthermore, we assume that CEs are only called after maximal matches. For example, if partial program ends an identifier, the CE can assume that the identifier is complete.
Our CEs are implemented in two layers: a context-free layer, which enforces syntactic validity, and a context-sensitive layer, which encodes semantic constraints that depend on language semantics and the user's context (e.g.. the database). Below, we describe an automatic method for construct- ing context- ffree CEs directly from the target language's grammar. The context-sensitivy layer of an engine is specific to the target language. Table I provides an overview of several constraints imple- mented by our CEs for SQL, Vega-Lite and SMCalFlow, three rich languages with different syntactic and semantic structures. A detailed description of the three CEs be found in Appendix
4

---

Published as a conference paper at ICLR 2022
Language
Constraint
Example of partial program
Valid/hnvaidd
Examples
SQL
valid identifier must follow after AS,
SELECT Name, Role FROM User AS
V
TI
2 x
Column names must come from schema, even behind aliases.
SELECT U. Name FROM User AS WHERE U.
Name
DoB v
Birthday
Vega-Lite
Data fields must be used with compatible types.
["x": {"field": "Category", "cype":
"nomi nal v
"temporal "
Do not facet on field with too many distinct values (breaks rendering).
(rcolum":(("fielll""
"Category" "ZipCode" x
SMCalFlow
Type-check parameters of all API functions.
(Yield (FLaccHlasFaature (x
Takeout V
IsWindy List. Aisty x yx
Track declared variables and their types.
(1et 85)
(Yield (inCelsius
Table 1: Examples of constraints implemented in our CEs for SQL,, Vega-Lite and SMCalFlow. Given a partial program, CEs return regular expression that matches the valid tokens that can follow. Here, we show positive and negative token examples for each such regular expression. This abstraction allows domain experts to encode wide range of expressive code generation constraints.
Deriving completions from grammars Computer language parsers are often automatically gen- erated from a grammar. The grammar contains enough information derive the context-free layer of CEs. To facilitate this process, we created a library that extends any parser generated by ANTLR (Parr& & Fisher 201T), a popular LL(") top-down parser generator, to provide token-level completions. Namely, we (i) let the LATLR-geenraan (ii) retrieve its state the Augmented Transition Network (ATN) at the last program token, (iii) tra- verse the ATN from that state to enumerate all possible next token productions. This process yields (a) a list of productions and token types { that are allowed to follow and (b) a partial AST Tp. Each CE takes { and T, as input to generate semantic context-sensitive constraints.
parser process the given program prefix p,
3.2 FROM COMPLETION ENGINES TO DECISION PROCEDURE
We use CEs to guide sampling from LLM. A key component of our algorithm for constrained sampling is a decision procedure for membership in prefix-closure of the set of all valid programs. The prefix-closure I. of language I. contains all programs in L well as all of their prefixes. Intuitively. L contains all partial programs that can be completed to a valid program. Given CE build a decision procedure for L given a string s, does belong to L
Ct. our first goal
We answer if E L by repeatedly calling Ct on certain prefixes p of s and matching the regular expression (p(p) with suffixes of We start with p being the empty string. We find the maximal prefix of that matches the regular expression (p) and remove it from s and add it to p. and repeat until the match fails. There are two cases: either s is empty now, which means the input string was completion point and hence it is in L,, or now is the remainder left after removing the largest prefix that was a completion point. For the second case, we must check: does there exist completion string such that sc fully matches the regular expression Cz(p)?
This question can be efficiently answered by Brzozowski derivatives (Brzozowski 1964). Formally, the derivative of a formal language S with respect to a string is another formal language u -S {v uv E 5}. In other words, it is precisely the set of strings that can complete u to some string in S. If - 5 0, then string in S starts with Brzozowski derivatives efficient to compute for our regular languages (or regular expressions defining them) we describe a simple linear-time algorithm in the Appendix. Given the derivative of (p), answering whether can be completed to
5

---

Published as a conference paper at ICLR 2022
belong to (p) reduces to performing a simple regular expression match. This operation answers the case when the remainder is non-empty and completes our decision procedure for L
3.3 THE CONSTRAINED SEMANTIC DECODING ALGORITIM
Using the decision procedure for L", we can now describe the Constrained Semantic Decoding algorithm. Suppose E Le is the language model's output so far (we start with e). If EM is the model's vocabulary, we can compute the set of valid next tokens (*) = {l EMr 8t E [.9 by using decision procedure for each token in the vocabulary ΣM. In other words, we maintain the invariant that the model's current partial output s is in L and make progress by using the model to sample from Vis (s), instead of the unconstrained EM. Once have a complete program, we guaranteed that it will satisfy all constraints enforced by the CE.
One subtlety to note is that language models and programming languages have drastically different tokenizations; i... C,. and LLM work with different tokens. For instance, a long string literal is a single SQL token, but might span multiple tokens for the language model. Similarly, single token from the language model's vocabulary might close multiple parentheses at once. In general, token boundaries between the two can be arbitrarily misaligned. Each decision of whether st belongs to L can potentially cross multiple completion points, or might not even finish a maximal match to the previous completion point (see the Appendix for an example prediction in Vega-Lite where this happens multiple times). Nevertheless, our CSD algorithm described here naturally handles this alignment problem. Hence, in SYNCIROMESI, CEs do not need to be aware of this issue - they can be fully implemented in terms of the target language's ' tokens [
Our implementation applies substantial optimizations that leverage the structure of Byte-Pair Encod- ing vocabularies (namely, that many tokens are prefixes of longer tokens) and reuse computation. We detail these optimizations in Appendix E In our experiments with GPT-3, CSD adds an average of 8% overhead to the sampling procedure relatively small impact to trade for output correctness.
4 EXPERIMENTS
We evaluate SYNCHROMESH in three tasks of synthesizing code from natural language descriptions. For SQL, we use the Spider dataset (Yu et al.) 2018). For Vega-Lite, we use the NLV Corpus (Srinivasan et al. 2.21). For SMCalFlow, we use the dataset that introduced the language (Andreas) et 2020).. In NLV. which has visualizations over 3 different datasets, we alternate using each dataset as a test-set by only using training examples from the other two datasets. In Spider and SMCalFlow, we use the training/validation set split given in each dataset.
Example selection model To select examples, we use Sentence- Centence-BERT (Reimers & Gurevych, 2019) to fetch the 5 closest examples by cosine similarity. When using TST, we fine-tuned the model with the TST objective in both the Spider and SMCalFlow training sets. The NLV corpus is smaller and does not provide clear train-test split fairly evaluate TST. Holding out one dataset and fine-tuning on the remaining two yields S SYNCHROMESH accuracies of over 90%. However, we attribute that performance to the fact that NLV has only 10 distinct visualizations and the same participants labeled all three datasets. For that reason, we omit Vega-Lite from the TST experiments.
Language models We used the two largest models from the GPT-3 family (Brown et al. 2020 with 13B and 175B parameters), as well the largest Codex model (Chen al. 2021). Codex shares the same architecture with 175B GPT-3, but its training set contained a larger portion of source code in variety of languages. Our only access the models was through the public OpenAl HTTP API, which allowed us to apply constraints by adding bias to logits. We describe the necessary adaptations of CSD to this setting in Appendix F
Metrics For Vega-Lite and SMCalFlow, we report the exact-match accuracy between predictions and ground-truth (field order is disregarded in Vega-Lite). In SQL, we instead measure execution
CCS aligns the LLM's stream of vocabulary subb))toeens to the CE's stream of valid program completion points, akin to clutch that dynamically aligns the speeds of differently-sized gears in manual transmission. Such mechanism known as synchromesh (Jewkes et al. 1969), which gives the name our whole framework.

---

Published as a conference paper at ICLR 2022
SQL Valid
Vega-Lite
SMCalFlow
Model
Exec
Dist.
Acc.
Valid
Dist.
Acc.
Valid
Dist.
Andreas ct al. 2020)
72% (S)
Srinivasan al.
202
64% (8)
Rubin Berant
202
(1%
Scholak et al.
2021
(9%
98%
GPT-3
16%
43%
14%
55%
0.51
38%
76%
0.43
CSD
20%
66%
0.44
17%
100%
0.48
40%
95%
0.40
TST
14%
48%
0.42
60%
88%
0.22
CSD + TST
19%
72%
0.43
63%
98%
0.17
GPT-3 175B
28%
49%
0.36
20%
67%
0.36
44%
77%
0,41
CSD
35%
73%
0.36
25%
100%
0.32
45%
97%
0.37
TST
31%
56%
0.35
60%
88%
0.24
4 CSD TST
37%
76%
0.34
66%
97%
0.18
Codex 175B +4 CSD
56%
73%
0.25
39%
87%
0.24
45%
79%
0.37
61%
85%
0..3
40%
99%
0.23
46%
97%
0.33
TST
60%
81%
0.23
63%
90%
0.21
*+ CSD + TST
64%
85%
0.23
63%
99%
0.19
Table Results of each language model on all domains with and without CSD and TST. For SQL, run the resulting query and report Execution Match accuracy (Exec.). For Vega-Lite and SM- CalFlow, we instead report Exact Match accuracy (Acc.). Edit Distance (Dist.) measures average relative edit distance between the prediction and the ground truth. We also report the fraction of Valid model outputs (those that parse, type-check and execute). For context only, we show recent results from supervised models (trained on the datasets we use) marked with (5).
accuracy, comparing query results instead. For more fine-graines signal, additionally mea- sure the edit distance between the predicted and ground-truth ASTs using the normalized tree edit distance (Zhang & Shasha 1989).
4.1 RESULTS
Table F summarrze our main results evaluating SYNCHROMESH. Key observations are:
SYNCHROMES!I improves reliability on top of all pre-trained LLMs. First, it improves top-1 accu- racy (exact or execution- -eauurrn-) over any pre-trained LLM in all domains. SMCalFlow benefits the most, likely because this domain -ppecffc language is absent the LLM pre-training corpus. For SQL and SMCalFlow, the absolute gain is almost the same for equally-sized GPT-3 and Codex.
Second, SYNCHROMESH dramatically improves validity. In SQL, eliminates execution errors from 29% of the queries generated by GPT-3 13B (as validity improves from 43% to 72%). Even Codex benefits, with 12% more queries executing successfully after SYNCHROMESH augmenta- tion. In Vega-Lite and SMCalFlow, SYNCHROMESHI improves reliability even more substantially. GPT-3 13B only produces valid charts for 55% of the queries in NLV; all errors are eliminated with SYNCHROMESH. This is nearly paralleled in SMCalFlow, in which all models produce well-typed programs 97% the time or more with SYNCHROMESH.
SYNCHROMESH brings the output closer to ground truth. Error prevention alone is trivial (e.g.. with a constant emror error-free prediction), but not while simultaneously improving accuracy or edit distance the ground-truth, as SYNCHROMESH does. Again, we observe improvements in all domains and the most SMCalFlow. For GPT-3 175B, the average edit distance is reduced from 0.41 to 0.18.
TST and CSD bring complementary benefits. Our ablation studies reported in Table show that their combination performs better than either one separately. TST helps L.MMs generate programs in the "vicinity" of the correct one, and CSD helps by "guiding" the models toward the correct
SYNCHROMESH adds more value for longer programs. Program synthesis is hardest when the target program is complex. Does SYNCHROMESH improve synthesis of longer programs, are its benefits

---

Published as a conference paper at ICLR 2022
Vallek (N)
SMCCa Tow
Codex Codex Synchromesh
Codex
Codex Synchromesh
length (percentile)
is
length (percentiie)
Number of samples
(a)
(c)
Figure 4: (a) Accuracy and (b) validity of Codex predictions with and without S SYNCHROMESH on SMCalFlow as function of the ground-truth program length. We map program lengths to percentiles, and round to the closest multiple of 10%. Error bands correspond to standard error. (c) Evaluation of the "generate- ggenerate-then-test approach with Codex. showing the probability of at least one prediction being a valid program (Valid@ K) for up to samples.
"For each origin,
"nark' ("tope": "acatlerplat", "aaceding' thats Offiald:: "helght" "tspel: "cuentitativv" "tape":
thart top. gURrIROOS Die neceeer hooeas
acceleration by weight scatterplot"
GPT-3 C5o
("tupe": "potee"),
Pralents intuelst "eligh"" "type" "ountitotive"
Codex
Concepnuot ermer aboutche mastine of "for sadr
? ""eal"": Accelaration "type" "guntitaaiiv""))
Groundenth: (harkkt ("type"s "point"), "enceding"
Collass' ("ruelat: "origle", "tpe": "scminal" ).
"weight" "yyee" quantssattiv
("eeld" "Accaleracten", "spe": quantstattve')
Figure 5: Illustration of implementation and conceptual errors in Vega-Lite. CSD can avoid gener- ating the invalid Vega-Lite mark type "scatterplot", though conceptual errors can still remain.
coming from fixes to small programs? Figure 4 a) shows accuracies and (b) validity for SMCalFlow broken down by the length of the ground truth program (we show results for SQL in the Appendix). Here, program lengths are shown as their percentile. With SYNCHROMESH, we see that accuracy decays at a slower pace, and validity remains high throughout, when compared to Codex alone. This indicates that SYNCHROMESH improves the ability of base models to generate longer programs.
LLMs augmented with SYNCHROMESH approach but underperform supervised models. For context, we include statc-of-the-ar results at the time of writing for each task in Table 2 We note that these methods fine-tune or train the underlying language-to-conl -o-dee model on each task, thus are not directly Codex
comparable to LLMs with SYNCHROMESH. That said, we observe that base substantially underperform supervised models (19% worse for SQL; 27% worse for SMCalFlow), and SYNCHROMESII helps narrow that gap (now 11% worse for SQL; 9% worse for SMCalFlow).
SYNCHROMESH outperforms "generate-then-tes" CSD enforces program constraints during gen- eration. Instead, prior work has leveraged
mennerate-then-esge approach: take multiple samples and filter out those that produce errors or violate constraints (Chen et al. (02T). Fi) evaluates this approach with Codex, the highest performing base LLM. We sample from Codex with a temper- ature 7 = 0.7 to obtain diverse but high-quality samples. We then compute the "Valid K" metric by using the "Pass @ K" estimator from Chen et al. (2021) calculate the probability of at least one valid sample among K, with K < 5. In SQL, Codex needs 3 samples to match SYNCHROMESH (Valid @ K 85%). In SMCalFlow and Vega-Lite, SYNCHROMESH is able to virtually eliminate errors with sample, while "Valid for Codex is still below 93%. This provides evidence that even the best LLMs benefit from incremental validation, especially in less popular languages.
4.2 DISCUSSION
In our experiments, SYNCHROMESH was able to improve accuracies and program validity across all languages due to better examples to use as reference (TST) and preventing errors during generation (CSD). Yet, this approach has important limitation. While TST can reduce conceptual errors, and CSD can guarantee that certain implementation errors never occur (e.g., type errors in SMCalFlow, or undefined column references in Vega-Lite SQL), TST cannot guarantee climination of concep- tual errors. When those occur, CSD is usually insufficient to correct the prediction. Figure [ shows example in Vega-Lite from the "Cars" dataset in NLV. Here, the user asks for scatter plot
8

---

Published as a conference paper at ICLR 2022
for each origin, indicating faceting (multiple charts). GPT-3 alone produces invalid Vega-Lite chart type, "scatterplot". CSD can eliminate this error, guiding GPT-3 to generate "point" instead. However, conceptual error remains: instead of faceting, the model colors points by their origin. Codex produces the correct Vega-L.te mark type, but still makes the same conceptual mistake.
Nonetheless, we argue that improving validity is especially important for user-facing applications. Users of language-to-code systems might need to rephrase their request or to edit the system's out- put. But outputs that fail to even execute undermine user experience: fixing an automatically gener- ated program can be more cumbersome than writing it in the first place. In LLM-driven systems like Github Copilot, implementation errors can remain unnoticed and introduce bugs or vulnerabilities.
5 RELATED WORK
Program synthesis is a long-standing AI challenge with the goal of generating computer programs
from higher-level specification (Gulwani et al.] 2017). In particular, synthesis from natural lan- guage descriptions has gained recent attention (Liu et al. [016)] Yaghmazadeh et al., (207)). thanks to advances in natural language processing models such as Transformers ( (Vaswani et al. 2017). Typically, LLMS such GPT-3 (Brown et al. 2020) and Codex (Chen al. (02T) output
constrained sequence of tokens, and still often make conceptual or implementation errors in gener- ated programs (Austin et al. 2021). Specialized training, c.g. to output an AST (Wang et al. 2020) Yin & Neubig 2017), can mitigate syntactic errors, but still does not guarantee accuracy or confor- mance to domain-specific semantic constraints. Moreover, requires a specialized architecture and a decoding procedure for each target language. Instead, SYNCHROMESH applies such constraints at inference, neither using specialized architectures nor fine-tuning the LLM.
The general idea of constraining LLMs when generating programs has been explored in recent work. Shin et al. (202T) applied syntactic constraints for semantic parsing. However, their method requires enumerating all valid programs for determining valid next tokens for the LLM, and does not enforce semantic constraints. In concurrent work, Scholak et al. (202T) applied similar semantic constraints to synthesizing SQL queries. The authors substantially improve the performance of an already fine- tuned model by leveraging an incremental parser. We see CSD as a generalization of these efforts, as our completion engines can apply context-sensitive constraints by dynamically constructing regular expressions. Aligning these constraints with the underlying model vocabulary does not require fine- tuning: S SYNCHROMESH only trains the much smaller target similarity model (Section
Since the emergence of LLMs, researchers have developed numerous techniques to adapt them to new domains (Liu et al. 2021b). Many focus on prompting, i.c. generating domain- and instance- specific input to an LLM to increase the likelihood of correctness. In few-shot prompt augmentation, Gao et al. (2020) use pre-trained sentence embeddings to select the closest prompt examples to the given input instance. Liu et al. (2021a) further fine-tune sentence embeddings on the available training set of input utterances. TST in SYNCHROMESH takes this approach step further, and fine- tunes the embedding models based on oulpul similarity. It optimizes the amount of relevant output bits in the prompt, thereby reinforcing the necessary hints for the LLM.
6 CONCLUSION
SYNCHRRMMESII augments program synthesis with pre-trained LLMs prevent conceptual and im- plementation errors during generation. We designed SYNCHROMESH to be easily usable with mini- mal NLP or LLM knowledge expected from a domain expert. As such, it (a) automatically generates the completion engine API from the language grammar, (b) does not require fine-tuning the LLM, drastically reducing the data/compute budget, and (c) integrates into the decoding loop or inference API with minimal overhead. Our method significantly improves performance of both GPT-3 and Codex in three languages, both by boosting accuracy and consistently improving output validity.
While real-world and well-established, the domains we study are still not Turing-complett We envision extending SYNCHROMESH to a Turing-complete language like Python can vastly increase reliability of LLM- systems like Github Copilot. This requires further extension of CSD to integrate with the parser/interpreter of the target language, and to study applicable classes of con- straints. The TST technique, however, can be used in any M-bseb language-to-code system.

---

Published as a conference paper at ICLR 2022
REFERENCES
Jacob Andreas, John Bufe, David Burkett, Charles Chen, Josh Clausman, Jean Crawford, Kate Crim, Jordan DeLoach, Leah Dorner, Jason Eisner, al. Task-oriented dialogue dataflow synthesis. Transactions of the Association for Computational Linguistics, 8:556-571, 2020.
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, and Charles Sutton. Program synthesis with large language models, 2021.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. 14 2020.
Janusz A Brzozowski. Derivatives regular expressions. Journal of the ACM (JACM), 11(4):
481-494, 1964.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde, Jared Kaplan, Harri Ed- wards, Yura Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107, 03374, 2021.
Jacob Devlin, Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pp. 4171-4186, 2019.
Tianyu Gao, Adam Fisch, and Danqi Chen. Making pre-trained language models better few-shot learners. arXiv preprint arXiv:2012.15723, 2020.
Sumit Gulwani, Oleksandr Polozov, Rishabh Singh, et al. Program synthesis. Foundations and Trends@ in Programming Languages, 4(1-2):1-119, 2017.
John Jewkes, David Sawers, and Richard Stillerman. Automatic Transmissions, pp. 231- 233. Palgrave Macmillan UK, London, 1969. ISBN 978-1-349-00015-99 doi: 1001007/ 978-1 1--449-00015-9.11
Chang Liu, Xinyun Chen, Eui Chul Shin, Mingcheng Chen, and Dawn Song. Latent attention for ih-then program synthesis. Advances in Neural Information Processing Systems, 29:4574-4582. 4582, 2016.
Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen. What makes good in in-context examples for gpt-3? arXiv preprint arXiv:2101.06004, 2021a.
Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pre- train, prompt, and predict: A systematic survey of prompting methods in natural language pro- cessing, 2021b.
William Merrill, Yoav Goldberg, Roy Schwartz, and Noah A. Smith. Provable limitations of acquir- ing meaning from ungrounded form: What will future language models understand?. 2021.
Terence Parr and Kathleen Fisher. LI (*) the foundation of the antir parser generator. ACM Sigplan Notices, 46(6):425-436, 2011.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21:1-67, 2020.
Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert- networks. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 11 2019. URL https://arxii
org/abs/ 1908. 10084
Ohad Rubin and Jonathan Berant. Smbop: Semm-autoregressive bottom-up semantic parsing. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Com- putational Linguistics: Human Language Technologies, pp. 311-324, 2021.
10

---

Published as a conference paper at ICLR 2022
Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. Picard: Parsing incrementally for strained auto-regressive decoding from language models. arXiv preprint arXiw:2109.05009 2021.
Richard Shin, Christopher H Lin, Sam Thomson, Charles Chen, Subhro Roy, Emmanouil Antonios Platanios, Adam Pauls, Dan Klein, Jason Eisner, and Benjamin Van Durme. Constrained language models yield few-shot semantic parsers. arXiv preprint arXiv:2104.08668, 2021.
Arjun Srinivasan, Nikhila Nyapathy, Bongshin Lee, Steven M Drucker, and John Stasko. Collecting and characterizing natural language utterances for specifying data visualizations. In Proceedings of the 2021 CHI Conference Human Factors in Computing Systems, pp. 1-10, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Bailin Wang, Richard Shin, Xiaodong Liu, Oleksandr Polozov, and Matthew Richardson. 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 Linguistics, pp. 7567-7578, 2020.
Parsers.
Frank Xu, Bogdan Vasileseu, and Graham Neubig. In-ide code generation from natural language: Promise and challenges. arXiv preprint arXiv:2101. 2021.
Navid Yaghmazadeh, Yuepeng Wang, Isil Dillig, and Thomas Dillig, Sqlizer: query synthesis from natural language. Proceedings of the ACM on Programming Languages, 1(00PSLA):-26, 2017.
Pengcheng Yin and Graham Neubig. A syntactic neural model for general-purpose code generation. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 440-450, 2017.
Tao Yu, Rui Zhang, Kai Yang. Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, et al. Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-sql task. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 3911-3921, 2018.
Kaizhong Zhang and Dennis Shasha. Simple fast algorithms for the editing distance between trees and related problems. SIAM journal on computing, 1866):2245-2222 1989.

---

Published as a conference paper at ICLR 2022
Algorithm 1:
CSD(M, Em)
Algorithm 2: ValidPrefix(s)
Input : LLM--based token generator,
Input : string 8
Input- : Its token set ΣM
Output: True iff E L f- neal prefer <- n";
Output: String generated by M, constrained by Cr.
nerl_loken "M,
while neal + do
while nexl_loken + "$" do
p + p. nert-prefer;
valid_tokene + {t E EM ValidPrefix(st))
nerl-prefit
next next_token + Sample(M(s) valid :tokens;; next_token;
regez CL(p):
next next-prefia t- startswith(s, regen);
end
end
return S;
return (s - reger + ()):
Figure 6: ValidPrefiz(s) determines is in the prefix-closure L" given completion engine Cr. for L. CSD(M, Σxr returns a string generated by the model M ensuring that the string's underlying token sequence consistent with completion engine CL.
A CONSTRAINED SEMANTIC DECODING ALGORITHM
In Section 3.3 we described the Constrained Semantic Decoding algorithm in the text. We provide the same algorithm pseudo-code in Algorithms and 2 in F below. ValidPref ix is our decision procedure for L", while CSD samples complete program from the model M by making calls to ValidPrefix. We use 8 t to denote concatenation of and t. and s-1 t to denote the string obtained by removing the prefix from /. The utility function startswith(s, r) returns the maximal prefix that matches the regular expression r, and returns if there is no such match. The function Sample Dist, S) returns token from the S of tokens sampled from the distribution Dist restricted to S. The CSD procedure uses the model AM on the partial program to generate distribution on the next token, but constrains belong the of valid _tokens determined by the completion engine CL.
B COMPUTING BRZOZOWSKI DERIVATIVES
Regular expression derivatives can be expensive to compute in general. The main challenge is that Klenee stars fork the decision procedure: the algorithm must decide to repeat or skip the pattern in- side star. However, in this work, all our regular expressions come from grammars of programming languages. These languages have one important feature in common: tokens are defined by greedy matching rules. This means that Klenee stars consume many characters possible, and do not backtrack if a tokenization error occurs (the error simply propagates). Under the assumption that Klenee stars have greedy semanties, derivatives can be computed in linear time, The algorithm for computing derivatives of regular expression can be worked out by looking at all constructors of regular expressions. Table this computation for regular expressions of base alphabet Σ.
C COMPLETION ENGINES
Here, we describe our completion engines for SQL, Vega-Lite and SMCalFlow in more detail.
C.I SQL
SQL database queries are executed the context of a particular database containing set of tables. Each table has schema, which specifies named columns, their data types and constraints such as foreign keys. We refer to Yu et al. (2018) for more detailed description of the SQL language.
Our CE for SQL enforces that only columns that exist in the tables in the database are used. The main challenge is that queries often specify aliases. Thus, during parsing, we construct a symbol table mapping aliases to the tables they refer to. We enforce that tables that already have an alias should only be referred to by their alias, not in their unqualified form. Since aliases can be referred to in the SELECT clause before being defined in the FROM clause, also keep track of undefined
12

---

Published as a conference paper at ICLR 2022
Constructor
Description
Derivative w.r.t d' E 5
Ø
Empty regular expression (matches string).
Matches only the empty string.
Matches a single character
cfc otherwise.
Rí R2
Concatenation of two regular ex- pressions R1 and R2
If the derivative of Ri w.r.t d' is not ø, then it's the concatenation of that with R2- Otherwise, if R1 matches then it is sim- ply the derivative of R2 w.r.t. d. If not, then the result is Ø.
R2
Union of two regular expressions R1 and R₂
Union of the derivatives of R2 and Rg w.r.t. d (if one becomes Ø, simply return the other).
R*
Klenee star any number of repeti- tions of
If the derivative of R w.r.. i not Ø, then return the concatenation of that derivative with Rs. Otherwise, return
Table 3: Computing Brzozowski derivatives for each constructor of regular expressions under the assumption that Klenee stars are greedy. The resulting algorithm runs linear-time on the size of the regular expression.
aliases to enforce that they will be assigned table later. Moreover, condition in the WHERE clause might involve nested query, which in its turn might redefine or create new aliases. As a result, our symbol table keeps stack of scopes properly resolve aliases in nested contexts.
We constrain numeric literals to either come from set of common numbers (including 0 and 1) or from the user's natural language question. This prevents the model from copying arbitrary numbers from the few-shot examples in the prompt. Finally, since SQL is case- insennsens,, our CE returns case-insensitive regular expressions for keywords, table and column names.
C.2 VEGA-LITE
Vega-Lite is a declarative language for specifying data visualizations given data frame table where rows represent data points and columns represent attributes of various data types. syntax is subset of JSON. Therefore, Vega-Lite grammar accepts JSON objects that follow subset of the Vega-Lite schema.
As in SQL, we the user's data frame to constrain valid field names. Additionally, in Vega-Lite, one must also specify a Vega-Lite type that is used to interpret the field values. We inspect the run- time values in the data frame to determine compatible Vega-Lite types. For example, string column typically used as a categorical value inmiinal, in Vega-Lite). However, if entries have ISO- e if its values can be parsed
formatted timestamps, it can be used temporal, or quantitat as numbers. Since ISON objects are unordered, it must handle two valid output orders: the model might output the field name first (we thus later constrain the type) or the data type first (we then constrain the field name to compatible columns). Because Vega-Lite's behavior is to silently ignore invalid data points, associating a column with an incompatible type simply produces an empty chart. Our constraint completely prevents this class of emror..
We forbid repeated fields and limit the length of free-form string literals to 30 characters, which prevents the common failure mode of language models to enter repetition loops. Similarly, we only allow an aggregation one of the X-Y axes, but not both, since that collapses the chart to a single data point and is another common failure case. Finally, splitting into multiple charts) based on a column with too many (> 50) distinct values: that typically crashes the Vega- rendering engine since it allocates overly large output image. In summary, our constraints guarantee conformance to the Vega- specification and additionally avoid common mistakes that cause crashes degenerate outputs.
prevent the model from faceting (i.e.,
13

---

remove the time Published as a conference paper at ICLR 2022
Byte-Pair Encoding token boundaries (model's ouptut)
ma type : "point" } "encoding" [Xx" (ffeld""
"INDB Rating
Vega-Lite tokens
(aligned with completion points)
Illustration of the token misalignment problem in Vega-Lite. Colors denote Vega-Lite tokens, which match how the completion engine works (and what are its completion points). Vertical lines denote how GPT-3 tokenizes this program.
Figure 7:
C.3 SMCALFLOW
SMCalFlow programs express responses to queries about calendar events, weather, places, and people (Andreas et al. 2020). It a rich language with scoped variable declarations, generic types, polymorphic operators and large API of over 400 functions, which can be composed express complex actions like "cancel any meetings on the same day of my next doctor's appointment", or answer queries such "will it be raining during my next walking meeting with Frank?"
Our CE enforces that programs type-check by construction. An example is given in Figure | At the current point inference. the model is producing an argument to size. Since this function takes list, its argument must be the return value of function with return type List<T>. Among all functions and methods in the SMCalFlow API, only 14 return lists, which severely limits the valid options for the callee. Similarly, we keep track of declared variables inside let expressions, together with their types (inferred from their initialization expression), and use that data structure to limit options whenever token of type ident tetoniffees fier is syntactically allowed to follow.
Finally, we implemented heuristics based on user utterance patterns that avoid common failure cases observed in GPT-3. These tend to happen when the model blindly copies portions of the examples in the prompt without adaptation. For instance, whenever the utterance contains exactly one of "a.m." or "p.m", this is usually represented in SMCalFlow by call a corresponding SMCalFlow function that constructs a T Time object (e.g., NumberAM (5) ). However, if the examples retrieved for the prompt tend to only have times in the opposite half of the day, GPT-3 might call the wrong function, and translate the time sub-expression in "Schedule it for 5pm" into NumberAM (5). To avoid this, if we detect exactly one of "a.m." or "p.m." in the utterance, construction functions associated with the opposite pattern from the candidates. We do the same filtering with days of the week and months, which are also constructed by specific functions.
In all domains, the CE abstraction allows us to easily encode domain knowledge in a modular fash- ion. Besides constraints coming from the language's semantics, it further allows domain experts to analyze failure modes of the language model and to implement fixes them in modular and predictable manner.
D THE TOKEN MISALIGNMENT CHALLENGE
The main challenge of CSD is in aligning constraints expressed in terms of programming language tokens with the model's output, which happens in another token vocabulary (typically constructed with Pyir-Pair Encoding). Figure 7 shows illustration of this challenge in Vega-Lite. Arbitrary mismatches can occur: the first BPE token includes the first Vega-Lite token and the first character of the second. In the middle of the example, the "encodine ng token in Vega-Lite spans 4 BPE tokens, with misaligned boundaries at the beginning and end. Nonetheless, this issue is seamlessly handled by the CSD algorithm.
Since the public SMCalFlow dataset does programs in the training set to infer parameter and return types. In the public dataset, SMCalFlow programs given in LISP-like syntax. For clarity, we mimic the original paper and Python-like syntax our explanations.
with the API specification, we the type-annotated
14

---

Published as a conference paper at ICLR 2022
05
56 Exact Match
56 Valid
Modd
Wodd
Codex
Codex
Codex Synchromesh
Codex Synchromess
Target program length (percentile)
Target program length (percentile)
(a)
(b)
Figure 8: (a) Accuracy and (b) validity of Codex predictions with and without SYNCHROMESH on SQL as function of the ground-truth program length. We map program lengths to percentiles, and round to the closest multiple of 10%. Error bands correspond standard error.
E OPTIMIZATIONS TO CSD
The algorithm described in Section 3.3 tests each token from the language model's 's vocabulary indi- vidually. However, many BPE tokens prefixes of oen another, which lets us apply significant optimization. If 4 is prefix of l2 and I is inadmissible after a partial program p. then l2 is also inadmissible. Thus, Before we test token against the completion engine, we check whether one of its prefixes was already rejected. If so, we can safely skip that token.
test tokens by order of length, and keep rejected tokens in Trie structure.
Another optimization consists in memoizing the enumerated completion points. When testing new partial program p. instead of starting from the empty string, we can start from the longest known completion point that is prefix of This, again, can be efficiently done by keeping completion points in a Trie.
F CSD WITHOUT DIRECT ACCESS TO THE LANGUAGE MODEL
We used the public OpenAl API to access GPT-3 and Codex. Therefore, we did not have direct access to the underlying language models. Even so, CSD still be applied provided can pass a bias to added to the logits, which is available in the OpenAI API.
request each token is too slow. Instead, apply "rejection" "bbsced based sampling, as follows. First, we request complete program from the model. Then, we iterate token- by-token, validating it with the CSD algorithm against the completion engine. If we find violation, we (a) use CSD to determine all valid next tokens, (b) make a request asking from just a single token, applying a logit bias constrain it to the valid tokens, and then (c) continue generation after appending the new token. Most (90%+) trajectories end after at most 3 corrections to the model. In degenerate cases, we might need to correct the model after almost every token. our experiments, we capped CSD to apply at most 15 corrections, to control the time a request with CSD takes. This only happened in less than 55 of the cases, and could be completely avoided if we had direct access to the model (in which case CSD is efficient enough to be applied at every token).
However, making
G ANALYSIS OF ACCURACY AND VALIDITY BY LENGTH IN SQL
Figure shows the equivalent of Figure 4 for the SQL domain. We notice that the largest gaps in validity happen for the longest queries, and the benefits in accuracy are highest for queries around the 60% length percentile.
15

---

Published as a conference paper at ICLR 2022
H TST FINE-TUNING DETAILS
In Section 2 we described TST, which fine-tunes a sentence embedding model to attempt to capture program similarity. Here, give more details
training procedure.
First, for both SQL and SMCalFlow, we selected a random set of 2000 examples, and computed the normalized one epoch using the cosine similarity loss. We used the AdamW optimizer with a learning rate of x 10 5 the default parameters in the S-BERT library We did not perform any hyperparameter tuning. Training took around hours on single GPU.
edit distance between all pairs of examples. We then fine-tuned S-BERT for
1 COMMENTED EXAMPLES OF TST AND CSD
Here, we provide three more detailed examples. The first examples shows the benefit of using TST on top of Codex. The remaining show value of CSD on top of Codex. Since the examples in Sections 2 and used SQL, we now give examples in SMCalFlow and Vega-Lite for diversity.
I.1 TST EXAMPLE IN SMCALFLOW
Query: "Hi, I need to meet with Alex on this Sunday at 6pm at the CVS shopping center for an hour." This query asks the system to create event. Without TST, the top example (similar to the query) returned by vanilla S-BERT from the training set is:
User utterance: Hi, I need to meet with Alex tomorzow afternoon for an hour.
SMCalFlow:
(Yield
ArreateCommiLEveettWWrraa (Crettebrrfligghhbeeeekaaepeep
(& (Event.start. (DateTimeConstraiit (Afternoon) (Tomorrow) )
(Event (Event.durate .duration_ (?= (toHours 1))))
attendees_? (Event.attendest (Execute (refer (exteensionConstraint
(Event.c
[RecipientVit:Nammlliie (EnptystructConstraalle (PersonNeme.apple "Alex"))))))11>>"
This example also involves creating an event, and also with person named "Alex". However, the time structure of this example, "Tomorrow afternoon", is not trivial to translate to "this Sunday 6pm", because these two specifications require different APIs from SMCalFlow. Given this and more examples, Codex generates:
(Yield (CreateComitEVvee:Waaprrer (Greaterrafliightteeeetvaaggggg (& (6 (Bvent.duration_? (?= (toHours 1)))
(DatefineConstraint (Afternoon) (ThisSunday) )
(Event.location.
(?= (LocattjonWiihhaaeel... (EmptystructCConsrraii)
diocatiioNNme..aggii "CvS shopping center"))))
(Event..tttendees_. (AttendeeLi stwaeeeecstssssssseeeeeeeaeeeeee
(Execute (refer (extennsionConstraain
[BeeipplentWitnNaeLLLiee (EiptySttruct
(PersonName "Alex")
16

---

Published as a conference paper at ICLR 2022
This prediction, while seeming reasonable at surface level, violates the SMCalFlow APIs in mul- tiple places. First, the function "ThisSunday" does not exist. The parameter 6pm was lost this prediction, since the examples had explicit time in it and Codex could not identify where to put it. Besides that, the model trying to specify four attributes of the created event: start time, duration, location and attendees, but it would need more conjunction (call to "&") do so. This eroor likely came from the fact that the top example only specified three attributes. The calls to the loca- tion APIs also incorrect "Location WithNameLiie exists (and is present in other examples in the prompt), but is not really needed or appropriate in this context.
However, if use TST pick the examples for the prompt, Codex is able to solve the problem. With TST, the top retrieved example is:
User utterance: Schedule hours on Friday at 7:00 am for Meeting with Kayla at the Sear's Tower.
SMCalFlow:
(Yield (CresteCommiiEEventttaperr
(& (a
(Event.starts (?= (DatetttTieeiithheeaaallll
(NextDOW (Friday))
(NumberAM 7L)))
(Event (Event.duration duration_? (?= (toHours ))
ddvent.location
(?= (Locat.oonkeepprasee....) "SearV's Tower")
(Execute (refer (extensionConstrains.
(RecipientWithhaaeeiii (Emptystrrnccoonsraaile (PersonName apply "kayle")))))1111)
Note that the utterance, from the perspective of its natural language structure, is less similar to the user's request than the previous example. However, describes query with the exact necessary structure: it schedules something for the next Friday (trivial to modify to Sunday) at certain time of the day ("NumberAM" can be simply rewritten to "NumberPM", which Codex does correctly). The location attribute, which Codex had previously tried to adapt from a less related example, is now also specified here. With this example, Codex able to make correct adaptation. It predicts:
(Yield (CreatecoomttEEeentWaapper (Creatterrefiigghhhtttttttttgggp (& (s (6 sEvent.start_? (?= (DateatiineviithDeaaallss
(NextDOw (Sunday))
(NumberPM 6L)
(Event Esvent.duration_? (?= (toHours 1)))
(Event.locationn]
(?= (ww.aatiinneypprrseeccooo
"CVS shopping center")))
IEvent.attteddess..
PAteendelisttisseccipintt
(Execute (refer (extensionConstraaint
[KecipiientWittMMMMll..ee (Emptystrruttoostraains
(PersonName apply "Alex"))))111111"
This matches the reference program from the dataset.
17

---

Published as a conference paper at ICLR 2022
1.2 CSD EXAMPLES IN VEGA-LITE
Query: "average horsepower over years, colored by origin" This query does not specify chart type, but one could infer that line chart is likely more appropriate since it showing quantity over time. The dataset under consideration contains car models with their year of manufacture, horsepower, number of cylinders and many other attribute. Thus, obtain the "average horsepower" in given year, we need an aggregation in Vega-Lite. Codex alone predicts:
("mark"; ("type": "line" },
"encoding";
("x": ("field"; "Year", "type": "temporal", "timeUnit": "yearmonth" } "y": ("field"; "Horsepower", "type": "quantitatives
"aggregate": "average" }
"coler": ("field"; "Origin", "type": "nominal"
All the right components of the query are there. However, even though the query asks for the "average horsepower", the aggregation function in Vega-Lite is called "mean". Specifying an invalid aggregation function makes Vega-Lite raise an exception. Thus, an actual user wouldn't it see any plot from this response.
CSD prevents Codex from generating "average" after it outputs the field name "aggregate", forcing it choose one of the existing aggregation functions (max, min, mean, etc). Constrained by CSD, Codex generates:
("mark": ("type": "line" }
"encoding";
("x": ("field"; "Year", "type": "temporal",
"timeUnit": "yearmonth" "y": ("field": "Horsepower", "type": "quantitative", "aggregate": "mean" } "color": ("field": "Origin", "type": "nominal"
This is not only valid but also matches the ground-truth from the dataset.
"Create a scatterplot of acceleration vs horsepower by model" This utterance asks for a chart that relates each car's accelcration and horsepower. Codex generates:
("mark": ("type": "point" )
"encoding":
("x": ("field": "Horsepower", "type": "quantitative" } "y": ("field"; "Acceleration", "type": "quantitative" ,, "color": ("field": "Model", "type": "nominal" } }}}
The produced plot, shown in Figure in principle correct, and answers the user's question. The "by model" in the query might sound if the user wants specialized plots by model. Codex realizes this interpretation by coloring each point differently by the car's model. But in this dataset, each row represents different car with distinct model. Thus, there 303 unique values of the "Model" column, and Vega-Lite raises run-time warning saying that the legend has overflowed for having too many values, so some values (the majority, in this case) were omitted. When the model decides to facet column with too many values, the Vega-Lite run-time often runs out of memory for allocating an overly large image.
CSD avoids these errors by looking at the user's dataset and determining which columns can be used for coloring or faceting, based on how many distinct values they have. none are available, then CSD doesn't 't let the model use these features. In this example, CSD forces Codex to choose one of the columns with less than 30 distinct values. Between those, Codex generates "Year". The resulting plot is shown in Figure (right). While in this example the "Year" column the user's s request, the application of this constraint here steers Codex to avoid a run-time warning emro. The ground-truth visualization for this description does not have any color specification,
not mentioned in
18

---

Published as a conference paper at ICLR 2022
Model
ar broughan
28
anc arc.aaaassdoo
concard
Accdees
concard at
1000
concard de
grandin
aichoree
vrchoree spartbouu
25
nutader
motador rse
100
150
300
gazer
Hersegower
gazer
20
0 72
MTC
spint ot
Acceleration
73
100
15
108
(000
5000
0000
wadi (tieor)
wudi fox
bme 2002
78
bre X00
buick century
buick century X50
buck eantury lniied
buidk century special
buik century toad
100
150
200
.I7 entree
Horsepower
Figure 9: Benefit of CSD: The left plot is generated by Codex without CSD, but it has overflowing legend and it also raises a warning about missing values. Using CSD, we generate the plot on right that generates runtime warning error.
neither prediction counts exact match. Nevertheless, from the point of view of the user's experience, CSD can be helpful even when cannot completely fix the prediction.
19


Reviews:
[{"review_id": "qThFVj8IwpG", "reviewer": "Reviewer_ZrJp", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Although TST works well empirically, I still cannot get the intuition behind it. The similarity score of two questions (u_i, u_j) indicates the relevance of two (p_i, u_i) in many cases. It would be great if the authors can provide more examples as the one shown in Fig 2 (I suspect the example is not that common). On the other hand, p_i and p_j could be equivalent even if their tree edit distance is large. The authors are encouraged to provide some analysis in that case.\n\n2. The results without TST in Table 2 are reported by selecting examples via the vanilla S-BERT without fine-tuned with the TST objective  (v.s. Random selection)? \n\n3. On the paragraph of “Example selection model”, it would be helpful if the authors elaborate more on fine-tuning S-BERT with the TST objective in Spider and SMCalFlow. \n\n4. Results show that the proposed method still underperforms supervised methods, while both TST and supervised methods use the full training set. Given the large size of GPT-3/CodeX, it would be better if the authors further discuss the practical merits of their approach. \n\n5. The proposed CSD method could be applied to the decoding part of supervised methods. It would be interesting to see how much gain CSD will bring to the supervised methods.\n\n6. Maybe I missed the number in the paper, but I wonder how many constraints did you implement in CEs for the three programs? How hard was it to collect them?\n\n7. It is a bit weird to only show integer results in Table 2 (at least keep one decimal place). \n\n8. It’s a bit surprising to see that TST also largely helps generate valid model outputs according to Table 2. Could you please explain a bit more about it?\n\n9. The result of GPT-3 13B + TST performs worse than GPT-3 13B  (14% v.s. 16%), which contradicts all the other results in Table 2. Why? Or a typo?\n\n10. Based on the results in Table 2, Vaga-Lite has relatively simple program grammar. Can you know why GPT-3/CodeX still performs very low on the task? Questions are ambiguous?\n\n11. In Algorithm 1, is the Sample() function adjusted by other advanced sampling variants (e.g., temperature sampling/top-k/top-p)? How do these sampling variants influence the performance? Are the improvements caused by the sampling variants orthogonal to CSD?\n\n\n", "summary_of_the_paper": "This paper presents a framework for more reliable code generation via in-context learning of GPT-3/CodeX. The paper is motivated by the finding that GPT-3/CodeX often generate programs with syntactic and semantic errors. To resolve this problem, the authors propose 1) Target Similarity Tuning (TST) for retrieving 5 relevant examples based on program similarity and 2) Constrained Semantic Decoding (CSD) for constraining the code generation output to a set of valid programs. The authors evaluate their proposed methods on three different code synthesising tasks (Spider, Vega-Lite, and SMCalFlow). Strong complementary gains on these tasks demonstrate the effectiveness and generalizability of the proposed framework on several tasks with different target programs (SQL, Vega-lite, and SMCalFlow). \n", "summary_of_the_review": "Although most of the high-level motivations and ideas of the paper have been studied in example/prompt selection and constraint-based decoding (e.g., PICAD), the authors are able to refine them and generalize them to more diverse domains and tasks by using GPT-3/CodeX without fine-tuning with a relatively small overhead to the output process. \n\nAlso, results show that the proposed method still underperforms supervised methods, while both TST and supervised methods use the full training set. Given the large size of GPT-3/CodeX, it would be better if the authors further discuss the practical merits of their approach (compared to few-shot learning with median-size language models has more meaningful practical benefits at this time if they are able to achieve competitive performance by fine-tuning <300-shot (a small number) examples.). \n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "kCdXG_A3CtF", "reviewer": "Reviewer_vLDx", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The two contributions of the paper are quite different and have different qualities. What is nice about the paper is that it shows that the two ideas may complement each-other.\n\nWhere the paper falls short is providing understandable limitations of these ideas. I do not agree they are universally good and some of the evaluation results look confusing and difficult to parse and understand. From the evaluation, it is not clear when the two ideas are tested separately and which improvement can be attributed to the specific idea. The output model also does not reach the accuracy level of prior state-of-the-art works, often by a lot. This usually wouldn’t be an issue if the training was really few-shot, but the TST idea removes this as it fine-tunes a transformer model.\n\nTST\n===\nThe main idea of TST is that instead of purely textual similarity input/output examples for the few-shot learning, the fine-tuned model would provide target query similarity metrics to the input. The choice of \"normalized similarity metric between programs\" to be AST edit distance is not clear. Also, there seems to be something different happening than what the explanation in the paper gives. We see cases of programs with low textual similarity, but high AST similarity that the model learns to return. However, this means this model learns how to approximately synthesize programs from the inputs. The paper does not discuss what capacity/complexity this pretrained model would need, but I assume the needs may be similar to the works that do program synthesis without pretrained language models (they outperform this work, this is for similar accuracy).\nminor questions: Why was AST distance chosen here. Why would it do better than pure text distance on the program text?\n\nCSD\n===\nThe idea to check if a sequence could potentially complete during decoding is also not new. It was already done before, for example by Karaivanov et al., Onward 2014 paper Phrase-Based Statistical Translation of Programming Languages. However, CSD here claims to enforce syntax, scope, typing rules, and contextual logic. This is an interesting claim, but this means that quite complex logic in the decoder. First, it is not clear this logic would expand to other languages with more complex syntax. Probably what the authors implement does not do precise enforcement, because this would be too complex, but instead efficiently cuts-off many search branches that would not lead to correct solutions. This is probably a nice contribution, but is not discussed in the text of the paper. It is also not clear which of syntax, scoping, type enforcement or other semantic rules contribute to the increased precision.\n\nThe main baseline to compare to here would be generate-then-check. In such a setting, one can use an unmodified parser, type checker and validator that can probably enforce more properties than the checker during decoding. Given the results shown in the paper, it is not clear why CSD would be of any significant advantage. There is also something unclear about the comparison to generate-then-check - is it compared to the full Synchromesh or only to the CSD part of it? Also, I would expect to see generate-then-check in the main evaluation table.\n", "summary_of_the_paper": "The paper considers the problem of text to code translation, usually done in state-of-the-art models using a natural language input fed into a transformer model together with other similar input/output examples as a few-shot learning and code being directly output by the model.\n\nThe paper proposes two enhancements of this process.\n\n* The first one called Target Similarity Tuning (TST) is a way to pick input/output examples similar to the input text. Previous works use a pretrained models for natural language similarity (Sentence-BERT is compared in the paper) that determine what examples to include in the few-shot prompt and the TST proposes to also fine-tune this model on code examples such that some semantic similarity in encoded - for example using the same structure of the queries [think of SQL queries to synthesize].\n* The other improvement called Constrained Semantic Decoding (CSD) proposes to alter the decoder of the transformer model and to make it avoid generating programs that are impossible to complete to syntactically or semantically correct ones.\n", "summary_of_the_review": "Overall, the paper gives some interesting ideas, but it does not demonstrate these ideas lead to actual wins and doesn’t discuss its limitations. Combining the two contributions TST and CSD does not lead to state-of-the-art results, while removing some of the advantages of few-shot learning. I believe this work is not generally flawed, but in this state is below the bar of ICLR.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Gcce-Sg8YdU", "reviewer": "Reviewer_ML5m", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "To the best of my knowledge, the ideas presented by the paper are novel and interesting. Although the two sources of improvements (better example selection and constraint validation) have already been explored by prior works, the proposed methods can address some of the major limitations of prior methods intuitively: TST further incorporates the similarity of programs instead of only considering language similarity, and CSD is more efficient and effective empirically. Both methods bring significant empirical gains to the reliability of code generation. The methods are also relatively easy to implement/reproduce and drop in existing pipelines. \n\nI have several minor concerns:\n1. Does CSD also bring significant benefits to more widely used languages like python or C++? Intuitively, the language model probably has a better model of these languages due to more training data, such that CSD is not that needed or only marginally more beneficial than generate-then-test. It would be beneficial to provide extra experiments on these languages.\n2. Similarly, more general-purpose languages also have more diverse ways of achieving the same effect. Then “the similarity between target programs” that TST is trying to predict seems less well defined. \n3. The context-sensitive layer of CSD seems highly language-dependent and not scalable to more general cases. Yet I imagine this is perhaps more important to validness than the context-free layer. It would be interesting to see how relatively important these two layers are over the existing datasets as well as more expressive languages. \n", "summary_of_the_paper": "This paper aims to improve the reliability of LLM based code generation via two aspects: select better prompting examples based on program similarity and constrain LLM to only generate valid programs incrementally. The authors provide extensive experiments and ablations to demonstrate the improvement of accuracy and validness.", "summary_of_the_review": "Overall, the methods proposed by this paper are novel and address major drawbacks of previous methods, leading to significant improvement of code generation performance across three real-world languages. The methods are also relatively straightforward to reproduce and built upon by future works.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "7qr_vS4U2nX", "reviewer": "Reviewer_vKkK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nIt is good to see a new code generation approach that considers both syntactic and semantic rules of the output language. Such an approach could prevent implementation errors in the generated programs. The proposed approach is evaluated on three languages (SQL, Vega-Lite, and SMCalFlow). The paper is generally well written.\n \nTo select examples, the authors fetch the 5 closest examples from a training set by cosine similarity. How is the training set constructed? What if there is no similar example in the training set? That is, the returned 5 closest examples all have low similarity to the question. \n\nHow many few-shot examples are selected? Are the few-shot examples the same as the 5 closest examples?\n\nThe proposed approach utilizes pre-trained models for code generation. Actually, a traditional approach (such as the one that is based on code template/pattern analysis) could also work here. Especially, considering the proposed approach also utilizes modules such as similar example retrieval and constraint analysis. Can you simply use a non-DL method to generate code based on the similar examples you retrieved, instead of using a pre-trained model? What are the benefits of using a pre-trained model here?  \n \nThis paper claims to improve the reliability of pre-trained models for code generation. However, it only investigates three domain-specific languages SQL, Vega-Lite, and SMCalFlow, which all lead to relatively simple programs. It is not clear if the proposed approach can be applied to other commonly-used, general-purpose programming languages such as Java, Python, and C/C++, which all have more complex syntactical structures.  \n\nActually, there are already some work that consider constraints in generating more complex Java and Python programs:\nLyu et al., Embedding API dependency graph for neural code generation. https://arxiv.org/abs/2103.15361, 2021.\nFor program synthesis, there are also some related work that are based on input and output examples:\nZaremba et al., Learning simple algorithms from examples. arXiv preprint arXiv:1511.072\nShu et al., Neural Programming by Example, Proc. AAAI 2017, Feb 2017.\n", "summary_of_the_paper": "This paper proposes SYNCHROMESH, a framework for improving the reliability of pre-trained models for code generation. SYNCHROMESH first retrieves few-shot examples from a training set using Target Similarity Tuning. It then feeds the examples to a pre-trained language model and samples programs using Constrained Semantic Decoding, which can constraint the output to a set of valid programs in the target language. The authors evaluate the proposed approach by synthesizing code from natural language descriptions using GPT-3 and Codex in three real-world languages: SQL queries, Vega-Lite visualizations and SMCalFlow programs. The experimental results look promising. \n", "summary_of_the_review": "Pros:\n\n. A new approach to code generation using pre-trained models.\n\n. Evaluated on three languages (SQL, Vega-Lite, and SMCalFlow)\n\nCons:\n\n. It is unclear if the proposed approach can be applied to other general-purpose programming languages such as Java, Python.\n\n. Some technical details are missing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper gives a new method for code generation from natural language queries using pretrained models. The approach follows two steps: (1) given a query, it selects a set of similar training examples using a method called Target Similarity Tuning, and (2) it then uses a method called Constrained Semantic Decoding (built on top a frozen language model) to adapt these examples into syntactically/semantically correct code.

The reviewers found the paper interesting. There were some concerns about the method's scope and its relationship to prior work but these were mostly addressed during the author response period. Given this, I am delighted to recommend acceptance. Please incorporate the feedback in the reviews (in particular, the review by vLDx) in the final version of the paper.
Decision: Accept (Poster)