Is Exact Constrained Sampling Right for You?

Constrained sampling lets a language model (LM) produce outputs that satisfy a grammar or another hard constraint, and how it is done matters: masking invalid tokens one step at a time distorts the LM's distribution over valid outputs, which harms applications that need that distribution, such as program fuzzing and molecule generation. Recent work samples from the correct constrained distribution either approximately or exactly, and the exact methods—adaptive rejection sampling (ARS) and the recent Constrained Adaptive Rejection Sampling (CARS)—are preferable when their cost is affordable. But nothing tells a practitioner in advance whether it is, or which exact method to use. We analyze the cost of these methods exactly. Over a run, ARS pays one rejected LM call for every possible first mistake of the LM, while CARS pays at most one per prefix, and CARS is optimal among all strategies that learn only from their own draws. The speedup of CARS over ARS is bounded below by two masses read off the trie CARS builds: the light invalid mass, too unlikely for ARS to have drawn, and the unreachable mass, at prefixes too rare for CARS to have reached. Our analysis is practical: the measured costs fall inside the predicted range on every task, tight when the run has seen most of the ways the LM violates the constraint.