Fast Controlled Generation from Language Models with Adaptive Weighted
  Rejection Sampling
The dominant approach to generating from language models subject to some
constraint is locally constrained decoding (LCD), incrementally sampling tokens
at each time step such that the constraint is never violated. Typically, this
is achieved through token masking: looping over the vocabulary and excluding
non-conforming tokens. There are two important problems with this approach. (i)
Evaluating the constraint on every token can be prohibitively expensive -- LM
vocabularies often exceed 100,000 tokens. (ii) LCD can distort the global
distribution over strings, sampling tokens based only on local information,
even if they lead down dead-end paths. This work introduces a new algorithm
that addresses both these problems. First, to avoid evaluating a constraint on
the full vocabulary at each step of generation, we propose an adaptive
rejection sampling algorithm that typically requires orders of magnitude fewer
constraint evaluations. Second, we show how this algorithm can be extended to
produce low-variance, unbiased estimates of importance weights at a very small
additional cost -- estimates that can be soundly used within previously
proposed sequential Monte Carlo algorithms to correct for the myopic behavior
of local constraint enforcement. Through extensive empirical evaluation in
text-to-SQL, molecular synthesis, goal inference, pattern matching, and JSON
domains, we show that our approach is superior to state-of-the-art baselines,
supporting a broader class of constraints and improving both runtime and
performance. Additional theoretical and empirical analyses show that our
method's runtime efficiency is driven by its dynamic use of computation,
scaling with the divergence between the unconstrained and constrained LM, and
as a consequence, runtime improvements are greater for better models.
67f80f73cce5a0f258129554
Benjamin Lipkin
extracted_confirmed
2025-04-10T18:46:57.881Z
613a6efea488863c1920731e
https://cdn-avatars.huggingface.co/v1/production/uploads/1664283416127-613a6efea488863c1920731e.jpeg
Ben Lipkin
user
benlipkin
67f80f73cce5a0f258129555
Benjamin LeBrun
claimed_verified
2025-04-11T07:25:51.744Z
613a6efea488863c1920731e
https://cdn-avatars.huggingface.co/v1/production/uploads/1664283416127-613a6efea488863c1920731e.jpeg
Ben Lipkin
user
benlipkin
67f80f73cce5a0f258129556
Jacob Hoover Vigly
67f80f73cce5a0f258129557
João Loula
extracted_pending
2025-04-10T18:35:33.249Z
655c76dcf37a7d0b09348813
/avatars/6fed15a38652dcc62f9022c5ff905cf2.svg
João Loula
user
jloula
67f80f73cce5a0f258129558
David R. MacIver
67f80f73cce5a0f258129559
Li Du
67f80f73cce5a0f25812955a
Jason Eisner
67f80f73cce5a0f25812955b
Ryan Cotterell
67f80f73cce5a0f25812955c
Vikash Mansinghka
67f80f73cce5a0f25812955d
Timothy J. O'Donnell
extracted_confirmed
2025-04-10T18:36:14.652Z
632b7bed6110e37dba3f5793
/avatars/564d7b53f14f9dfc54aefc5dafb7f8a8.svg
Tim O'Donnell
user
todonnell
67f80f73cce5a0f25812955e
Alexander K. Lew
extracted_pending
2025-04-10T18:35:33.249Z
673cc08370644bb836283fec
/avatars/b8c7f1a10ddf76dcd06398c59f553b61.svg
Alexander Lew
user
alexanderlew
67f80f73cce5a0f25812955f
Tim Vieira
Fast Controlled Generation from Language Models with Adaptive Weighted
  Rejection Sampling
The dominant approach to generating from language models subject to some
constraint is locally constrained decoding (LCD), incrementally sampling tokens
at each time step such that the constraint is never violated. Typically, this
is achieved through token masking: looping over the vocabulary and excluding
non-conforming tokens. There are two important problems with this approach. (i)
Evaluating the constraint on every token can be prohibitively expensive -- LM
vocabularies often exceed 100,000 tokens. (ii) LCD can distort the global
distribution over strings, sampling tokens based only on local information,
even if they lead down dead-end paths. This work introduces a new algorithm
that addresses both these problems. First, to avoid evaluating a constraint on
the full vocabulary at each step of generation, we propose an adaptive
rejection sampling algorithm that typically requires orders of magnitude fewer
constraint evaluations. Second, we show how this algorithm can be extended to
produce low-variance, unbiased estimates of importance weights at a very small
additional cost -- estimates that can be soundly used within previously
proposed sequential Monte Carlo algorithms to correct for the myopic behavior
of local constraint enforcement. Through extensive empirical evaluation in
text-to-SQL, molecular synthesis, goal inference, pattern matching, and JSON
domains, we show that our approach is superior to state-of-the-art baselines,
supporting a broader class of constraints and improving both runtime and
performance. Additional theoretical and empirical analyses show that our
method's runtime efficiency is driven by its dynamic use of computation,
scaling with the divergence between the unconstrained and constrained LM, and
as a consequence, runtime improvements are greater for better models.
The paper proposes an adaptive rejection sampling algorithm to improve runtime and performance of constrained generation from language models by reducing constraint evaluations and variance in importance weights.
locally constrained decoding token masking adaptive rejection sampling sequential Monte Carlo algorithms text-to-SQL molecular synthesis goal inference pattern matching JSON domains importance weights unconstrained and constrained LM