# Type-Constrained Code Generation with Language Models

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 65 references that are in the map.
- First posted on arXiv 12 Apr 2025.

## Builds on (most cited first, 30 of 35)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Gemma 2: Improving Open Language Models at a Practical Size](https://mlsanity.com/paper/2408.00118/) (2024)
- [DeepSeek-Coder: When the Large Language Model Meets Programming -- The Rise of Code Intelligence](https://mlsanity.com/paper/2401.14196/) (2024)
- [A Survey on Large Language Models for Code Generation](https://mlsanity.com/paper/2406.00515/) (2024)
- [StarCoder 2 and The Stack v2: The Next Generation](https://mlsanity.com/paper/2402.19173/) (2024)
- [Asleep at the Keyboard? Assessing the Security of GitHub Copilot's Code Contributions](https://mlsanity.com/paper/2108.09293/) (2021)
- [A Survey of Hallucination in Large Foundation Models](https://mlsanity.com/paper/2309.05922/) (2023)
- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [SWT-Bench: Testing and Validating Real-World Bug-Fixes with Code Agents](https://mlsanity.com/paper/2406.12952/) (2024)
- [Prompting Is Programming: A Query Language for Large Language Models](https://mlsanity.com/paper/2212.06094/) (2022)
- [Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation](https://mlsanity.com/paper/2403.06988/) (2024)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [Bugs in Large Language Models Generated Code: An Empirical Study](https://mlsanity.com/paper/2403.08937/) (2024)
- [Copiloting the Copilots: Fusing Large Language Models with Completion Engines for Automated Program Repair](https://mlsanity.com/paper/2309.00608/) (2023)
- [What's Wrong with Your Code Generated by Large Language Models? An Extensive Study](https://mlsanity.com/paper/2407.06153/) (2024)
- [How Can Self-Attention Networks Recognize Dyck-n Languages?](https://mlsanity.com/paper/2010.04303/) (2020)
- [Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages](https://mlsanity.com/paper/2310.13897/) (2023)
- [A Systematic Literature Review on Large Language Models for Automated Program Repair](https://mlsanity.com/paper/2405.01466/) (2024)
- [Measuring The Impact Of Programming Language Distribution](https://mlsanity.com/paper/2302.01973/) (2023)
- [Exploring Parameter-Efficient Fine-Tuning Techniques for Code Generation with Large Language Models](https://mlsanity.com/paper/2308.10462/) (2023)
- [CoTran: An LLM-based Code Translator using Reinforcement Learning with Feedback from Compiler and Symbolic Execution](https://mlsanity.com/paper/2306.06755/) (2023)
- [Code Less, Align More: Efficient LLM Fine-tuning for Code Generation with Data Pruning](https://mlsanity.com/paper/2407.05040/) (2024)
- [Syzygy: Dual Code-Test C to (safe) Rust Translation using LLMs and Dynamic Analysis](https://mlsanity.com/paper/2412.14234/) (2024)

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

- [Unveiling the Potential of Diffusion Large Language Model in Controllable Generation](https://mlsanity.com/paper/2507.04504/) (2025)
- [Constrained Decoding of Diffusion LLMs with Context-Free Grammars](https://mlsanity.com/paper/2508.10111/) (2025)
- [Towards Formal Verification of LLM-Generated Code from Natural Language Prompts](https://mlsanity.com/paper/2507.13290/) (2025)
- [SEVerA: Verified Synthesis of Self-Evolving Agents](https://mlsanity.com/paper/2603.25111/) (2026)
- [Correctness-Guaranteed Code Generation via Constrained Decoding](https://mlsanity.com/paper/2508.15866/) (2025)
- [Beyond the Prompt: An Empirical Study of Cursor Rules](https://mlsanity.com/paper/2512.18925/) (2025)
- [RefineStat: Efficient Exploration for Probabilistic Program Synthesis](https://mlsanity.com/paper/2509.01082/) (2025)
- [Agint: Agentic Graph Compilation for Software Engineering Agents](https://mlsanity.com/paper/2511.19635/) (2025)
- [Verifier-Guided Code Translation via Meta-Step Decoding](https://mlsanity.com/paper/2605.17626/) (2026)
- [Implementing Grassroots Logic Programs with Multiagent Transition Systems and AI (Full Version)](https://mlsanity.com/paper/2602.06934/) (2026)
- [Constrained Code Generation with Discrete Diffusion](https://mlsanity.com/paper/2605.16829/) (2026)
- [The Alignment Problem in Constrained Code Generation](https://mlsanity.com/paper/2606.21619/) (2026)
- [Large Databases Need Small, Open-Weight Language Models](https://mlsanity.com/paper/2606.31808/) (2026)
- [Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance](https://mlsanity.com/paper/2608.28229/) (2026)
- [LLM Agents for Generating Microservice-based Applications: how complex is your specification?](https://mlsanity.com/paper/2508.20119/) (2025)
- [Play by the Type Rules: Inferring Constraints for LLM Functions in Declarative Programs](https://mlsanity.com/paper/2509.20208/) (2025)
- [Learning to Guarantee Type Correctness in Code Generation through Type-Guided Program Synthesis](https://mlsanity.com/paper/2510.10216/) (2025)
- [Position: Vibe Coding Needs Vibe Reasoning: Improving Vibe Coding with Formal Verification](https://mlsanity.com/paper/2511.00202/) (2025)
- [Prompt Less, Smile More: MTP with Semantic Engineering in Lieu of Prompt Engineering](https://mlsanity.com/paper/2511.19427/) (2025)
- [The New Compiler Stack: A Survey on the Synergy of LLMs and Compilers](https://mlsanity.com/paper/2601.02045/) (2026)
- [Hydra: Efficient, Correct Code Generation via Checkpoint-and-Rollback Support](https://mlsanity.com/paper/2605.15238/) (2026)
- [Learning the Error Patterns of Language Models](https://mlsanity.com/paper/2605.28328/) (2026)
- [Accelerating Constrained Decoding with Token Space Compression](https://mlsanity.com/paper/2605.29986/) (2026)
- [Projectional Decoding: Towards Semantic-Aware LLM Generation](https://mlsanity.com/paper/2605.30054/) (2026)
- [Dynamic Infilling Anchors for Format-Constrained Generation in Diffusion Large Language Models](https://mlsanity.com/paper/2606.04535/) (2026)
- [TypeProbe: Recovering Type Representations from Hidden States of Pre-trained Code Models](https://mlsanity.com/paper/2607.08339/) (2026)
- [Generative Compilation: On-the-Fly Compiler Feedback as AI Generates Code](https://mlsanity.com/paper/2607.13921/) (2026)
- [Cross-Dialect Generalization Without Retraining: Benchmarks and Evaluation of Schema-Derived Constrained Decoding for MLIR](https://mlsanity.com/paper/2607.18254/) (2026)
- [Decode-Time Grammars: Constrained LLM Generation over a Refinement Order of Grammar Fragments](https://mlsanity.com/paper/2607.18357/) (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 (LLMs) have achieved notable success in code generation. However, they still frequently produce uncompilable output because their next-token inference procedure does not model formal aspects of code. Although constrained decoding is a promising approach to alleviate this issue, it has only been applied to handle either domain-specific languages or syntactic features of general-purpose programming languages. However, LLMs frequently generate code with typing errors, which are beyond the domain of syntax and generally hard to adequately constrain. To address this challenge, we introduce a type-constrained decoding approach that leverages type systems to guide code generation. For this purpose, we develop novel prefix automata and a search over inhabitable types, forming a sound approach to enforce well-typedness on LLM-generated code. We formalize our approach on a foundational simply-typed language and extend it to TypeScript to demonstrate practicality. Our evaluation on the HumanEval and MBPP datasets shows that our approach reduces compilation errors by more than half and significantly increases functional correctness in code synthesis, translation, and repair tasks across LLMs of various sizes and model families, including state-of-the-art open-weight models with more than 30B parameters. The results demonstrate the generality and effectiveness of our approach in constraining LLM code generation with formal rules of type systems.