Type-Constrained Code Generation with Language Models

2025/04/12 by Niels Mündler, Jingxuan He, Hao Wang +3 · 17 voices · 21 citations
Computer Science · #Model-Driven Software Engineering Techniques #Logic, programming, and type systems #Software Testing and Debugging Techniques

paper · pdf · doi:10.1145/3729274

Abstract

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.

Citations

• Asleep at the Keyboard? Assessing the Security of GitHub Copilot's Code Contributions
• Program Synthesis with Large Language Models
• Language Models are Few-Shot Learners

Cited by

• Implementing Grassroots Logic Programs with Multiagent Transition Systems and AI (Full Version)
• Decode-Time Grammars: Constrained LLM Generation over a Refinement Order of Grammar Fragments
• Generative Compilation: On-the-Fly Compiler Feedback as AI Generates Code
• Cross-Dialect Generalization Without Retraining: Benchmarks and Evaluation of Schema-Derived Constrained Decoding for MLIR
• Moded Types for Grassroots Logic Programs, by AI, for AI (Full Version)
• VSA:Visual-Structural Alignment for UI-to-Code
• Modular Layout Synthesis (MLS): Front-end Code via Structure Normalization and Constrained Generation
• Agint: Agentic Graph Compilation for Software Engineering Agents
• Prompt Less, Smile More: MTP with Semantic Engineering in Lieu of Prompt Engineering
• Reducing Hallucinations in LLM-Generated Code via Semantic Triangulation
• Position: Vibe Coding Needs Vibe Reasoning: Improving Vibe Coding with Formal Verification
• AdapTrack: Constrained Decoding without Distorting LLM's Output Intent
• Learning to Guarantee Type Correctness in Code Generation through Type-Guided Program Synthesis
• Automated Discovery of Test Oracles for Database Management Systems Using LLMs
• Play by the Type Rules: Inferring Constraints for LLM Functions in Declarative Programs
• Specification-Guided Synthesis of Deadlock-Free Communication Protocol Refinements with Large Language Models
• LLM Agents for Generating Microservice-based Applications: how complex is your specification?
• REFINESTAT: Efficient Exploration for Probabilistic Program Synthesis
• ChopChop: a Programmable Framework for Semantically Constraining the Output of Language Models
• Correctness-Guaranteed Code Generation via Constrained Decoding
• Constrained Decoding of Diffusion LLMs with Context-Free Grammars

Discussions

• Type-constrained code generation with language models [hn, 257 points, 127 comments]
• "Type-Constrained Code Generation with Language Models" is a relatively new paper that addresses a common challenge with LLM-generated code. The researchers are from ETH Zurich and UC Berkeley. [bsky, 15 points, 1 comments]
• Des SLMs contraints par le typage (comme proposé dans cet article: arxiv.org/pdf/2504.09246) ça semble être une approche prometteuse! L'implem du papier semble nécessiter un entraînement / fine tuning [bsky, 2 points, 1 comments]
• Type-Constrained Code Generation with Language Models arxiv.org/pdf/2504.09246 [bsky, 0 points, 0 comments]
• Type-constrained code generation with language models https://arxiv.org/abs/2504.09246 (https://news.ycombinator.com/item?id=43978357) [bsky, 0 points, 0 comments]
• "Type-constrained code generation with language models" Using language models to write and fix code can make programming easier and better. Focusing on one programming language may be the smartest ide [bsky, 0 points, 0 comments]
• https://bsky.app/profile/hackernews.com.web.brid.gy/post/3lp4k353vrs32 [bsky, 0 points, 0 comments]
• Type-constrained code generation with language models [bsky, 0 points, 0 comments]
• Type-Constrained Code Generation with Language Models #HackerNews https://arxiv.org/abs/2504.09246 [bsky, 0 points, 0 comments]
• Type-constrained code generation with language models https://arxiv.org/abs/2504.09246 https://news.ycombinator.com/item?id=43978357 [bsky, 0 points, 0 comments]
• Type-constrained code generation with language models https://arxiv.org/abs/2504.09246 arxiv.org [bsky, 0 points, 0 comments]
• Type-constrained code generation with language models https://arxiv.org/abs/2504.09246 [bsky, 0 points, 0 comments]
• ⚡ Hackernews Top story: Type-constrained code generation with language models [bsky, 0 points, 0 comments]
• Type-constrained code generation with language models https://arxiv.org/abs/2504.09246 (http://news.ycombinator.com/item?id=43978357) [bsky, 0 points, 0 comments]
• Type-constrained code generation with language models https://arxiv.org/abs/2504.09246 (http://news.ycombinator.com/item?id=43978357) [bsky, 0 points, 0 comments]
• Type-constrained code generation with language models view on hacker news [bsky, 0 points, 0 comments]
• Type-constrained code generation with language models https://arxiv.org/abs/2504.09246 (https://news.ycombinator.com/item?id=43978357) [bsky, 0 points, 0 comments]

Related

• Automata-based constraints for language model decoding
• ChopChop: a Programmable Framework for Semantically Constraining the Output of Language Models
• Learning to Guarantee Type Correctness in Code Generation through Type-Guided Program Synthesis
• A Survey on Large Language Models for Code Generation
• Combining LLM Code Generation with Formal Specifications and Reactive Program Synthesis