ChopChop : a Programmable Framework for Semantically Constraining the Output of Language Models

Shaan Nagy, Timothy Zhou, Nadia Polikarpova, Loris D’Antoni · 2025

Read ChopChop : a Programmable Framework for Semantically Constraining the Output of Language Models by Shaan Nagy, Timothy Zhou, Nadia Polikarpova, Loris D’Antoni (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-00360.txt.

Introduction

Shaan Nagy, Timothy Zhou, Nadia Polikarpova, and Loris D'Antoni present ChopChop in 2025, a programmable framework that constrains language model output by semantic properties. Models can write code but cannot guarantee it is correct: outputs may break type safety, program invariants, or other semantic rules. Constrained decoding restricts generation to outputs that meet set properties.

Past methods handle only syntax, or encode semantics in brittle token-level ways. ChopChop builds constrained decoders by analyzing the space of programs a prefix could complete to. That analysis is framed as a realizability problem and solved by coinduction, which links token-level generation to program structure. Semantic guarantees could make generated code safer to deploy.

Catalog record

CREATORShaan Nagy, Timothy Zhou, Nadia Polikarpova, Loris D’Antoni
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE12 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-00360

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

ChopChop : a Programmable Framework for Semantically Constraining the Output of Language Models Shaan Nagy, Timothy Zhou, Nadia Polikarpova, Loris D’Antoni Abstract . Language models (LMs) can generate code, but cannot guarantee its correctness—producing outputs that often violate type safety, program invariants, or semantic equivalence. Constrained decoding offers a solution by restricting generation to programs that satisfy desired properties. Yet, existing methods are limited to shallow syntactic constraints or rely on brittle, ad hoc encodings of semantics over token sequences. We present ChopChop , the first programmable framework for semantic constrained decoding, enabling LMs to generate code that provably satisfies rich semantic properties. ChopChop connects token-level generation with reasoning over abstract program structures using a coinduction-based formalism and reduces constraint enforcement to a realizability problem over regular codata. We demonstrate ChopChop ’s generality through generation constrained by type safety and program equivalence, showing how formal methods can be seamlessly integrated into LM-driven code generation. ChopChop transforms semantic constrained decoding from a niche technique into a systematic, principled extension of LMs—improving success rates across models and tasks while maintaining practical decoding latency. 1. Introduction Language models (LMs) have fundamentally transformed how we interact with code—generating functions, completing boilerplate, and even suggesting entire programs. Yet, despite their success, LMs offer no guarantees of correctness: they produce code that looks plausible but often violates critical syntactic or semantic properties. Constrained decoding has emerged as a promising solution to this problem ( wang2023grammar ; willard2023efficient ; geng2024grammarconstrained ; monitors ; typespaper ) . In constrained decoding, a language model generates a sequence one token at a time, but the next token is chosen not only for its likelihood, but also based on whether extending the current output with that token could ultimately produce a program that satisfies a user-defined constraint. However, existing constrained decoding techniques are limited in scope. Early methods focus on shallow syntactic correctness—e.g., enforcing that outputs conform to a context-free grammar (CFG). More recent techniques attempt to enforce richer constraints like type safety ( typespaper ) or runtime properties ( monitors ) , but do so via ad hoc manipulations of token sequences. These approaches are brittle and operate solely on surface-level syntax, failing to leverage the abstract representations used by formal methods for reasoning about program semantics and ensuring deeper semantic correctness properties, such as program equivalence or adherence to complex invariants. In this paper, we ask: Can we design a principled, programmable framework for constrained decoding that enforces deep semantic properties—over programs, not just token sequences? Achieving this goal introduces two major challenges. (1) Bridging the syntax-semantics gap. Formal methods reason about semantic properties over abstract syntax trees (ASTs) or intermediate representations, while language models generate concrete syntax one token at a time. Enforcing semantic constraints during decoding thus requires translating between the evolving token prefix and the corresponding space of possible ASTs the prefix might generate. (2) Dealing with partial programs. Traditional program analyses operate on complete programs. But in constrained decoding, we must decide—incrementally, as each token is produced—whether a partial prefix could still yield a program that satisfies the desired constraint. Our approach. We present ChopChop , the first unified, programmable framework for semantic constrained decoding over abstract program representations. The key idea is to reduce constrained decoding to a familiar problem in program synthesis: realizability ( unrealizability2019 ; unrealizability2020 ) . At each decoding step, ChopChop constructs a symbolic representation of all ASTs consistent with the current prefix and asks whether any of them satisfy a user-defined semantic constraint. If so, decoding continues; otherwise, the token is rejected and an alternative is proposed. To apply ChopChop , users provide two inputs: ( i ) a parser from strings to ASTs, and ( ii ) a set of semantic pruners , functions that operate on a symbolic representation of sets of ASTs, and eliminate ASTs violating a constraint without enumerating the full set. Given these inputs, ChopChop incrementally enforces semantic constraints during decoding. As the LM emits tokens, ChopChop constructs a symbolic representation of all ASTs that are syntactically valid completions of the current prefix. This representation, implemented through regular coinduction , is pruned using the user-supplied semantic pruners (which are corecursive functions over said codata ). ChopChop then determines whether any ASTs remain in the pruned space. If the space is empty, the proposed token is rejected and an alternative is tried. This pipeline ensures that every accepted token keeps the generation process on track toward satisfying the semantic constraints—without ever needing to enumerate completions explicitly or modify the LM itself. Applications. We demonstrate the generality of ChopChop through two diverse applications: • Program Equivalence-Guided Decoding: We constrain a language model to generate programs equivalent, modulo term rewriting, to a reference program. Here, the semantic pruner uses e-graphs to efficiently reason about equivalence classes of ASTs. • Type-Safe Decoding: We constrain a language model to emit only well-typed programs in a subset of TypeScript. Here, the semantic pruner lifts type checking to operate over sets of abstract partial terms, and ChopChop ensures that type safety is maintained throughout the generation process. For these domains, ChopChop produces programs that satisfy given semantic constraints more often than both unconstrained language models and decoding algorithms that only constrain the program syntax. Through these applications, ChopChop establishes constrained decoding not as a task-specific patch, but as a programmable and semantically rich extension of LM generation—grounded in decades of insights from formal methods and synthesis. Contributions. • The first programmable framework for semantic constrained decoding , enabling LLMs to enforce deep semantic properties during program generation ( Section 2 ). • A formal connection between semantic constrained decoding and realizability in program synthesis, showing that enforcing semantic properties during generation reduces to checking whether the set of possible completions contains a valid program ( ). • A novel constrained decoding algorithm based on corecursion ; the algorithm incrementally builds a space of abstract program completions and interfaces this space with a user-given programmable corecursive semantic pruner ( ). • An implementation of our framework in a tool, ChopChop , and instantiate it in two challenging domains—equivalence-guided decoding and type-safe generation—demonstrating both generality and effectiveness ( ). • An evaluation of ChopChop on the two domains— ChopChop produces programs that satisfy given semantic constraints more often than existing approaches while incurring a small computational overhead ( ). discusses related work, and concludes. 2. Overview of ChopChop To motivate our approach, consider a simple but illustrative task: Generate a sum of odd integers whose total is even. For example, the expression is a valid solution: all summands are odd and the total is even. If we prompt a language model (LM) with this task, there is no guarantee it will succeed. It might produce a sum with even numbers (e.g., ), an odd total (e.g., ), or nonsensical output (e.g., banana ). ChopChop enables users to enforce such constraints (i.e., that the summands are odd and the sum is even) on the LM by providing two inputs: (1) A parser definition for translating strings generated by the language model to ASTs (see )—e.g., for translating the string to the AST ; (2) A set of semantic pruners , each representing a constraint

Read the complete text