R043 · AI-built software and its verification › Formal methods for AI-written code

Type-constrained decoding for code generation

Read the original

constrained-decodingformal-verificationai-built-softwareinference-cost

Mündler, He, Wang, Sen, Song and Vechev (ETH Zurich, UC Berkeley), arXiv 2504.09246, PLDI 2025; code at eth-sri/type-constrained-code-generation.

The type checker moves into the sampler, so most compile errors never get generated. The authors found syntax errors are only about 6% of compile failures in LLM TypeScript; 94% are type errors, which grammar-constrained decoding cannot catch because type systems are not context-free.

Mechanism. A prefix automaton answers one question per token: can this partial program still become a well-typed program? It tracks declared identifiers and expression types, and runs a reachability search over a type graph (operators, member access, calls) to see whether the needed type is still reachable. A token that fails is masked and resampled; 99.4% of steps need one sample. No extra LLM calls.

Results. Across Gemma 2 (2B to 27B), DeepSeek Coder 33B, CodeLlama 34B and Qwen2.5 32B on TypeScript HumanEval and MBPP: compile errors down 74.8% and 56.0% (syntax-only constraints: 9.0% and 4.8%). Functional correctness up 3.5% relative for synthesis, 5.0% for translation and 37% for repair of non-compiling code (Gemma 2 2B repair: 11.6 to 20.9). Median runtime up 39 to 52%.

Why it matters for efficiency. Every compile error an agent emits costs a tool call, a context append and a retry turn. Removing over half of them at decode time is a direct cut in agent loop length, and it is the same move Agent-C makes for tool policies.

Caveats. Needs full token distributions, so it does not work through closed APIs. Covers a core TypeScript subset; each language is substantial engineering. The search is sound but incomplete, so it can reject valid programs. Benchmarks are translated function-level tasks, not repositories.

Connections

See R043 on the knowledge map

Part of the Research notes on nowucca.com. Figures and claims are the source's own unless the summary says otherwise.