# Constrained Decoding for Fill-in-the-Middle Code Language Models via Efficient Left and Right Quotienting of Context-Sensitive Grammars

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 27 references that are in the map.
- First posted on arXiv 28 Feb 2024.

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

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [The Stack: 3 TB of permissively licensed source code](https://mlsanity.com/paper/2211.15533/) (2022)
- [Efficient Training of Language Models to Fill in the Middle](https://mlsanity.com/paper/2207.14255/) (2022)
- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [Code Prediction by Feeding Trees to Transformers](https://mlsanity.com/paper/2003.13848/) (2020)
- [Pythia: AI-assisted Code Completion System](https://mlsanity.com/paper/1912.00742/) (2019)
- [Code Completion with Neural Attention and Pointer Networks](https://mlsanity.com/paper/1711.09573/) (2017)
- [Neural Program Generation Modulo Static Analysis](https://mlsanity.com/paper/2111.01633/) (2021)
- [Syntax-Aware On-the-Fly Code Completion](https://mlsanity.com/paper/2211.04673/) (2022)

## Built on by (most cited first, 8 of 8)

- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [CRANE: Reasoning with constrained LLM generation](https://mlsanity.com/paper/2502.09061/) (2025)
- [Type-Constrained Code Generation with Language Models](https://mlsanity.com/paper/2504.09246/) (2025)
- [Constrained Decoding of Diffusion LLMs with Context-Free Grammars](https://mlsanity.com/paper/2508.10111/) (2025)
- [An Empirical Analysis of Static Analysis Methods for Detection and Mitigation of Code Library Hallucinations](https://mlsanity.com/paper/2604.07755/) (2026)
- [OCELOT: Inference-Leakage Budgets for Privacy-Preserving LLM Agents](https://mlsanity.com/paper/2606.12341/) (2026)
- [Generative Compilation: On-the-Fly Compiler Feedback as AI Generates Code](https://mlsanity.com/paper/2607.13921/) (2026)
- [Specification-Guided Synthesis of Deadlock-Free Communication Protocol Refinements with Large Language Models](https://mlsanity.com/paper/2607.27964/) (2026)

## Abstract (arXiv)

Large Language Models are powerful tools for program synthesis and advanced auto-completion, but come with no guarantee that their output code is syntactically correct. This paper contributes an incremental parser that allows early rejection of syntactically incorrect code, as well as efficient detection of complete programs for fill-in-the-middle (FIM) tasks. We extend the Earley parsing algorithm to allow for left and right quotients of context-free grammars, and develop methods to handle quotienting of several context-sensitive features present in the grammars of many common programming languages. The result of these contributions is an efficient, general, and well-grounded method for left and right quotient parsing. To validate our theoretical contributions -- and the effectiveness of certain design decisions -- we evaluate our method on the particularly difficult case of FIM completion for Python 3, with syntax-correctness constraints. Our results demonstrate that constrained generation can significantly reduce the incidence of syntax errors in recommended code.