PaperlayerView exact revision on arXiv

Source-linked AI summary

Synchromesh: Reliable code generation from pre-trained language models

Gabriel Poesia, Oleksandr Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, Sumit Gulwani

arXiv:2201.11227v1cs.LGcs.PL

TL;DR

Language models often produce code with conceptual or implementation errors, limiting reliable natural-language program synthesis. Synchromesh combines program-structure-based example retrieval with constrained decoding over frozen models, and improves validity and prediction accuracy across three domains while leaving conceptual errors possible.

  • Problem

    Language models can generate code unrelated to the requested intent or code that fails because of syntax, typing, or run-time errors.

  • Method

    Synchromesh uses Target Similarity Tuning to select structurally relevant examples and Constrained Semantic Decoding to enforce rich constraints during generation on a frozen language model.

  • Results

    Synchromesh significantly improves GPT-3 and Codex performance across SQL, Vega-Lite, and SMCalFlow by boosting prediction accuracy and output validity.

  • Takeaways & Limitations

    Constraint-aware decoding can prevent implementation errors by construction, while semantically tuned examples improve relevance and downstream performance across domains.

  • Takeaways & Limitations

    CSD cannot generally correct conceptual errors that remain after generation, even when it eliminates invalid syntax or types.

Abstract

from arXiv · show

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

1 INTRODUCTION

Synchromesh improves natural-language code generation by selecting semantically relevant examples and constraining decoding to prevent implementation errors. Across multiple programming languages and models, these components improve validity and prediction accuracy.

  • LLMs can generate code unrelated to the requested intent, producing conceptual errors even when prompted with natural-language descriptions.
  • 47% of failures in short Python programs from models with up to 137B parameters were syntax, typing, or run-time errors.
  • Target Similarity Tuning selects few-shot examples by similarity between the programs their utterances describe, rather than surface wording alone.
  • Completion engines support rich constraints, including syntax, scoping, and type-checking, while CSD aligns them with the language model’s token vocabulary.
  • Synchromesh was evaluated with GPT-3 and Codex on SQL, Vega-Lite, and SMCalFlow, where CSD and TST produced complementary gains in validity and prediction accuracy.
  • TST can retrieve examples containing the needed grouping-and-counting structure, enabling GPT-3 to adapt a correct SQL query despite different natural-language descriptions.

2 TARGET SIMILARITY TUNING

Target Similarity Tuning retrieves examples with program structures relevant to a natural-language query, addressing the mismatch between surface linguistic similarity and target-program similarity. It trains a sentence-similarity model using program-derived similarities and demonstrates this approach on SQL synthesis.

  • Surface-similar examples can miss the target query’s required program structure, such as grouping and counting.
  • TST fine-tunes a pretrained sentence-similarity model to predict similarity between target programs from their natural-language descriptions.
  • Program similarity is defined with tree edit distance over Abstract Syntax Trees.
  • TST-selected examples led GPT-3 to generate a correct SQL query that groups by City and sorts by each group’s record count.
  • The SQL example illustrates that structurally similar programs can be useful even when their natural-language descriptions differ drastically.

3 CONSTRAINED SEMANTIC DECODING

Constrained Semantic Decoding samples programs token by token while enforcing completion-engine constraints, combining syntactic and semantic validity checks with language-model generation. The procedure maintains valid partial programs, handles mismatched tokenizations, and guarantees satisfaction of enforced constraints in completed outputs.

  • Completion Engines: Completion engines return regular expressions describing tokens that can extend a partial program toward a complete correct program.This abstraction supports expressive constraints across SQL, Vega-Lite, and SMCalFlow, including domain-specific semantic restrictions.
  • The Constrained Semantic Decoding Algorithm: CSD prevents implementation errors by construction rather than repairing invalid programs after generation.Once generation completes, the program is guaranteed to satisfy all constraints enforced by its completion engine.
  • The Constrained Semantic Decoding Algorithm: In the SQL example, constraining the alias after “T1.” restricts generation to columns from the Flights table and fixes a prior implementation error.The resulting query is correct because the SQL completion engine applies the table-context constraint during generation.
  • Completion Engines: CSD combines context-free constraints for syntactic validity with context-sensitive constraints based on language semantics and user context.The context-free layer can be derived from target-language grammars and parser-generated partial ASTs; the context-sensitive layer is language-specific.
  • From Completion Engines to a Decision Procedure: The completion-engine decision procedure repeatedly matches maximal prefixes and uses completion strings to determine whether a partial output remains completable.Brzozowski derivatives efficiently answer whether a remainder can be completed against the relevant regular expression.
  • Constrained Semantic Decoding: CSD samples each next token from those that preserve membership in the prefix-closure of valid programs.For a partial output s, it computes valid model-vocabulary tokens t such that st remains completable to a valid program.
  • The Constrained Semantic Decoding Algorithm: CSD naturally handles arbitrary misalignment between language-model tokens and target-language tokens.A model token may span multiple completion points or fail to finish a target-language maximal match, without requiring completion engines to model that mismatch.
  • The Constrained Semantic Decoding Algorithm: CSD adds an average of 8% overhead to GPT-3 sampling in the reported implementation.The implementation uses Byte-Pair Encoding vocabulary structure and reused computation to reduce decoding overhead.

4 EXPERIMENTS

Synchromesh improves code-generation reliability across SQL, Vega-Lite, and SMCalFlow by combining semantically relevant example selection with constrained decoding. Gains include higher accuracy and validity, stronger performance on longer programs, and a narrower gap with supervised models, while conceptual errors can remain.

  • Experimental setup: The experiments use GPT-3 and Codex on SQL, Vega-Lite, and SMCalFlow, evaluating accuracy, edit distance, and valid outputs.SQL uses execution-match accuracy; Vega-Lite and SMCalFlow use exact-match accuracy, with validity requiring outputs to parse, type-check, and execute.
  • Results: Synchromesh improves top-1 accuracy over pre-trained LLMs across all three domains.The largest benefit occurs in SMCalFlow; equally sized GPT-3 and Codex models show nearly identical absolute gains on SQL and SMCalFlow.
  • Results: Validity improves substantially, including GPT-3 13B SQL validity rising from 43% to 72%.All Vega-Lite errors are eliminated for GPT-3 13B, while SMCalFlow models produce well-typed programs at least 97% of the time with Synchromesh.
  • Results: Synchromesh reduces prediction distance from ground truth across domains, with GPT-3 175B edit distance decreasing from 0.41 to 0.18.The authors distinguish this from merely preventing errors, which would not improve accuracy or average edit distance.
  • Results: TST and CSD provide complementary benefits: TST selects programs near the correct one, while CSD guides generation toward it.Ablation studies show their combination performs better than either component separately.
  • Results: Synchromesh is more beneficial for longer programs because accuracy decays more slowly and validity remains high as program length increases.Figure 4 analyzes SMCalFlow program lengths by percentile; the paper reports analogous SQL results in the Appendix.
  • Results: Synchromesh narrows, but does not eliminate, the gap between pre-trained and supervised models: SQL improves from 19% worse to 11% worse, and SMCalFlow from 27% worse to 9% worse.The supervised results are provided for context and are not directly comparable because those systems are trained or fine-tuned on each task.
  • Results: CSD outperforms generate-then-test: Codex needs three SQL samples to match Synchromesh at Valid@K = 85%, while Valid@5 remains below 93% in SMCalFlow and Vega-Lite.Synchromesh virtually eliminates errors with one sample in SMCalFlow and Vega-Lite, providing evidence for incremental validation.

5 RELATED WORK

Prior work adapts language models through prompting and constrained decoding, but existing approaches differ in their handling of semantic constraints, model adaptation, and target-language requirements.

  • Structured generation: Specialized AST-based training can mitigate syntactic errors but still lacks guarantees of accuracy or domain-specific semantic conformance.Such methods also require specialized architectures and decoding procedures for each target language.
  • Synchromesh: Synchromesh applies constraints at inference without specialized architectures or fine-tuning of the language model.This distinguishes it from approaches that rely on target-language-specific training or adapted models.
  • Constrained generation: Syntactic-constraint methods can require enumerating all valid programs and do not enforce semantic constraints.This limits their applicability when the valid-program space is large or domain semantics matter.
  • Prompting: Prompting methods select domain- and instance-specific examples to increase the likelihood of correct outputs.Few-shot augmentation uses sentence embeddings to retrieve examples, with later work fine-tuning embeddings on available training data.

6 CONCLUSION

Synchromesh combines inference-time constrained decoding and semantically targeted example selection to improve code-generation accuracy and validity across three real-world languages.

  • Conclusion: Synchromesh improves GPT-3 and Codex performance in SQL, Vega-Lite, and SMCalFlow by boosting prediction accuracy and output validity.The framework is designed for modular use by domain experts and integrates into decoding or inference APIs with minimal computational overhead.
  • Conclusion: Its completion-engine abstraction automatically derives an API from the target grammar and encodes rich semantic constraints.The studied completion engines cover SQL, Vega-Lite, and SMCalFlow, with constraints including names, aliases, types, and contextual rules.
  • Limitations: The studied domains are real-world but not Turing-complete, leaving extension to languages such as Python as future work.Such an extension would require integrating CSD with the target language’s parser or interpreter and identifying applicable constraint classes.
  • Conclusion: CSD samples complete programs by querying ValidPrefix, which tests whether partial outputs can be completed into valid programs.The procedure uses regular expressions over the target-language token set and model-token distributions.
  • Conclusion: CSD must align programming-language tokens with a separate model token vocabulary, including arbitrary mismatches caused by BPE tokenization.Greedy token matching and regular-expression derivatives support constraint checking for programming-language grammars.

C.3 SMCALFLOW

SMCalFlow is a rich calendar-oriented language whose completion engine enforces type correctness and supports modular, domain-specific safeguards against observed model failures.

  • SMCalFlow: SMCalFlow expresses calendar, weather, place, and people-related responses through scoped variables, generic types, polymorphic operators, and over 400 API functions.These constructs support complex actions and queries about calendar events.
  • Tokenization: Figure 7 illustrates token misalignment by contrasting Vega-Lite tokens with GPT-3’s BPE tokenization.The mismatch motivates alignment mechanisms in constrained decoding, although the figure itself concerns Vega-Lite rather than SMCalFlow.
  • Completion engine: The SMCalFlow completion engine enforces type-checking by construction while tracking function return types and variables declared inside let expressions.At a function argument position, only API functions with compatible return types remain valid candidates.
  • Heuristics: Heuristics based on utterance patterns address failures caused by blindly copying prompt examples without adaptation.For time expressions, the system maps utterances containing “a.m.” or “p.m.” to corresponding SMCalFlow Time constructors.
  • Domain knowledge: The completion-engine abstraction lets domain experts encode semantic knowledge and implement modular fixes for model failure modes.This extends beyond language semantics to predictable, domain-specific interventions.

E OPTIMIZATIONS TO CSD

CSD includes token-rejection and memoization optimizations, while the experimental setup also records dataset assumptions and examines accuracy and validity across SQL program lengths.

  • Token testing: Prefix-based rejection avoids testing BPE tokens whose prefixes are already inadmissible after a partial program.Rejected prefixes are stored in a Trie, and tokens are tested in increasing length order.
  • Assumption: SMCalFlow parameter and return types are inferred from type-annotated training programs because the public dataset lacks the API specification.This is an assumption underlying the completion engine’s type constraints.
  • Notation: The public SMCalFlow dataset uses LISP-like syntax, while the paper presents explanations in Python-like syntax for clarity.The notation is therefore explanatory rather than the dataset’s original surface syntax.
  • Evaluation: Figure 8 plots Codex accuracy and validity with and without Synchromesh against SQL ground-truth program-length percentiles.Error bands represent standard error, and lengths are rounded to the nearest 10% percentile.
  • Memoization: Memoizing completion points lets CSD begin checking from the longest known completion-point prefix of a new partial program.Completion points are maintained in a Trie for efficient lookup.

F CSD WITHOUT DIRECT ACCESS TO THE LANGUAGE MODEL

CSD can operate through the OpenAI API without direct access to GPT-3 or Codex. Synchromesh uses rejection-based sampling to constrain only tokens that violate the completion engine’s validity checks.

  • CSD remains applicable when the underlying language models are inaccessible, provided the API accepts logit biases.The authors used the public OpenAI API and relied on its ability to add a bias to token logits.
  • Rejection-based sampling first requests a complete program, then validates it token by token against the completion engine.When a violation is found, CSD determines valid next tokens and the system requests a single constrained token before continuing generation.
  • The implementation avoids making one API request for every token because that strategy is too slow.

G ANALYSIS OF ACCURACY AND VALIDITY BY LENGTH IN SQL

In SQL, validity gaps are largest for the longest queries, while CSD’s accuracy benefits peak around the 60% length percentile. The TST analysis fine-tunes sentence embeddings using program similarity derived from tree edit distance.

  • Analysis of accuracy and validity by length in SQL: The largest SQL validity gaps occur for the longest queries.
  • Analysis of accuracy and validity by length in SQL: CSD’s accuracy benefits are highest for queries around the 60% length percentile.
  • TST training procedure: TST fine-tunes a sentence embedding model to capture program similarity.
  • TST training procedure: For SQL and SMCalFlow, the authors computed normalized tree edit distances among 2,000 randomly selected examples and fine-tuned S-BERT for one epoch.They used cosine similarity loss with AdamW; no hyperparameter tuning was performed.
  • Additional examples: The detailed examples compare TST on top of Codex with CSD on top of Codex in SMCalFlow and Vega-Lite.

I.1 TST EXAMPLE IN SMCALFLOW

In SMCalFlow, surface-similar examples can produce API and time-structure errors, while TST retrieves an example with the required event structure and enables a reference-matching prediction.

  • Vanilla S-BERT retrieval: The surface-similar SMCalFlow example omits the explicit 6pm time and uses the nonexistent function “ThisSunday”.
  • Vanilla S-BERT retrieval: The prediction also specifies four event attributes without the required conjunction and uses location APIs incorrectly.The top example specified only three attributes, while “LocationWithNameLike” was unnecessary or inappropriate in this context.
  • TST retrieval: TST retrieves a less surface-similar example whose program has the necessary scheduling structure, including a weekday, time-of-day, duration, location, and attendee.
  • TST result: With TST, Codex correctly adapts Friday at 7:00 am to Sunday at 6pm and uses the CVS shopping center and Alex.The resulting prediction matches the reference program from the dataset.

I.2 CSD EXAMPLES IN VEGA-LITE

The Vega-Lite examples show CSD correcting invalid or impractical visualizations by enforcing dataset-aware feature choices and valid aggregation functions. These constraints preserve valid outputs while avoiding runtime warnings and exceptions.

  • Aggregation constraints: Codex alone uses “average” as a Vega-Lite aggregation, but the valid function is “mean”, so the response raises an exception.
  • Aggregation constraints: CSD constrains aggregation choices after the aggregate field, preventing “average” and forcing an existing function such as max, min, or mean.
  • Valid generation: The mean horsepower-over-time visualization is valid and matches the dataset ground truth.
  • Dataset-aware constraints: Codex colors a scatterplot by Model, producing 303 distinct legend values and a runtime warning about legend overflow.
  • Dataset-aware constraints: CSD inspects column cardinalities and restricts coloring or faceting to columns with fewer than 30 distinct values when necessary.In this example, the constrained generation selects Year instead of Model; the figure reports no runtime warning or error.
Loading 2201.11227v1…