# Synchromesh: Reliable code generation from pre-trained language models

arXiv: https://arxiv.org/abs/2201.11227 · HTML: https://mlsanity.com/paper/2201.11227/

## Key facts

- Cited by 156 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 30 references that are in the map.
- First posted on arXiv 26 Jan 2022.

## Builds on (most cited first, 20 of 20)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Pre-train, Prompt, and Predict: A Systematic Survey of Prompting Methods in Natural Language Processing](https://mlsanity.com/paper/2107.13586/) (2021)
- [Making Pre-trained Language Models Better Few-shot Learners](https://mlsanity.com/paper/2012.15723/) (2020)
- [What Makes Good In-Context Examples for GPT-3?](https://mlsanity.com/paper/2101.06804/) (2021)
- [Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task](https://mlsanity.com/paper/1809.08887/) (2018)
- [RAT-SQL: Relation-Aware Schema Encoding and Linking for Text-to-SQL Parsers](https://mlsanity.com/paper/1911.04942/) (2019)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [Constrained Language Models Yield Few-Shot Semantic Parsers](https://mlsanity.com/paper/2104.08768/) (2021)
- [Task-Oriented Dialogue as Dataflow Synthesis](https://mlsanity.com/paper/2009.11423/) (2020)
- [SmBoP: Semi-autoregressive Bottom-up Semantic Parsing](https://mlsanity.com/paper/2010.12412/) (2020)
- [Provable Limitations of Acquiring Meaning from Ungrounded Form: What Will Future Language Models Understand?](https://mlsanity.com/paper/2104.10809/) (2021)
- [In-IDE Code Generation from Natural Language: Promise and Challenges](https://mlsanity.com/paper/2101.11149/) (2021)
- [Collecting and Characterizing Natural Language Utterances for Specifying Data Visualizations](https://mlsanity.com/paper/2110.00680/) (2021)
- [Latent Attention For If-Then Program Synthesis](https://mlsanity.com/paper/1611.01867/) (2016)

## Built on by (most cited first, 30 of 156)

- [DS-1000: A Natural and Reliable Benchmark for Data Science Code Generation](https://mlsanity.com/paper/2211.11501/) (2022)
- [CodeRL: Mastering Code Generation through Pretrained Models and Deep Reinforcement Learning](https://mlsanity.com/paper/2207.01780/) (2022)
- [Retrieval-Augmented Generation for AI-Generated Content: A Survey](https://mlsanity.com/paper/2402.19473/) (2024)
- [Benchmarking and Defending Against Indirect Prompt Injection Attacks on Large Language Models](https://mlsanity.com/paper/2312.14197/) (2023)
- [Large Language Model Alignment: A Survey](https://mlsanity.com/paper/2309.15025/) (2023)
- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [Language Models of Code are Few-Shot Commonsense Learners](https://mlsanity.com/paper/2210.07128/) (2022)
- [Multi-lingual Evaluation of Code Generation Models](https://mlsanity.com/paper/2210.14868/) (2022)
- [Unified Demonstration Retriever for In-Context Learning](https://mlsanity.com/paper/2305.04320/) (2023)
- [Text and Patterns: For Effective Chain of Thought, It Takes Two to Tango](https://mlsanity.com/paper/2209.07686/) (2022)
- [Rephrase and Respond: Let Large Language Models Ask Better Questions for Themselves](https://mlsanity.com/paper/2311.04205/) (2023)
- [Prompting Is Programming: A Query Language for Large Language Models](https://mlsanity.com/paper/2212.06094/) (2022)
- [Learning Performance-Improving Code Edits](https://mlsanity.com/paper/2302.07867/) (2023)
- [SatLM: Satisfiability-Aided Language Models Using Declarative Prompting](https://mlsanity.com/paper/2305.09656/) (2023)
- [Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation](https://mlsanity.com/paper/2403.06988/) (2024)
- [Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programs](https://mlsanity.com/paper/2306.03081/) (2023)
- [AutomaTikZ: Text-Guided Synthesis of Scientific Vector Graphics with TikZ](https://mlsanity.com/paper/2310.00367/) (2023)
- [XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models](https://mlsanity.com/paper/2411.15100/) (2024)
- [JSONSchemaBench: A Rigorous Benchmark of Structured Outputs for Language Models](https://mlsanity.com/paper/2501.10868/) (2025)
- [In-context Learning with Retrieved Demonstrations for Language Models: A Survey](https://mlsanity.com/paper/2401.11624/) (2024)
- [Repair Is Nearly Generation: Multilingual Program Repair with LLMs](https://mlsanity.com/paper/2208.11640/) (2022)
- [Retrieval Augmented Generation (RAG) and Beyond: A Comprehensive Survey on How to Make your LLMs use External Data More Wisely](https://mlsanity.com/paper/2409.14924/) (2024)
- [Parsel: Algorithmic Reasoning with Language Models by Composing Decompositions](https://mlsanity.com/paper/2212.10561/) (2022)
- [Strategic Reasoning with Language Models](https://mlsanity.com/paper/2305.19165/) (2023)
- [Generating CAD Code with Vision-Language Models for 3D Designs](https://mlsanity.com/paper/2410.05340/) (2024)
- [GPT4AIGChip: Towards Next-Generation AI Accelerator Design Automation via Large Language Models](https://mlsanity.com/paper/2309.10730/) (2023)
- [Agents in Software Engineering: Survey, Landscape, and Vision](https://mlsanity.com/paper/2409.09030/) (2024)
- [TIARA: Multi-grained Retrieval for Robust Question Answering over Large Knowledge Bases](https://mlsanity.com/paper/2210.12925/) (2022)
- [How to Prompt LLMs for Text-to-SQL: A Study in Zero-shot, Single-domain, and Cross-domain Settings](https://mlsanity.com/paper/2305.11853/) (2023)
- [Grammar Prompting for Domain-Specific Language Generation with Large Language Models](https://mlsanity.com/paper/2305.19234/) (2023)

## Abstract (arXiv)

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.