Title: Constrained Adaptive Rejection Sampling

Abstract

As Language Models (LMs) are increasingly deployed in applications requiring generated outputs to adhere to rigorous semantic or syntactic rules, the challenge of constrained generation has gained prominence. Current methodologies exist on a spectrum: Greedy Constrained Decoding (GCD) methods guarantee validity during the decoding process but inadvertently distort the underlying LM distribution. Conversely, Rejection Sampling (RS) maintains distributional fidelity but incurs significant computational waste by discarding invalid outputs. Both approaches present significant drawbacks, particularly in fields like program fuzzing, where maintaining both sample validity and diversity is critical.

To address these limitations, we introduce Constrained Adaptive Rejection Sampling (CARS), a novel approach that enhances the sample efficiency of RS while strictly preserving distributional accuracy. CARS initiates with standard unconstrained LM sampling and employs an adaptive mechanism to eliminate constraint-violating continuations. This is achieved by recording invalid paths in a trie structure and subtracting their associated probability mass from subsequent sampling attempts. This adaptive pruning strategy ensures that prefixes already identified as invalid are never re-sampled, leading to monotonically increasing acceptance rates. Consequently, the final samples conform precisely to the constrained distribution.

Experimental evaluations across multiple domains, including molecular generation and program fuzzing, demonstrate that CARS consistently outperforms existing methods. It achieves superior efficiency, quantified by the number of LM forward passes required per valid sample, and generates higher sample diversity compared to both GCD and techniques that approximate the LM’s distribution.

Source: arXiv Generated at: 2026-06-04 00:00:00 UTC