title: Fast Controlled Generation from Language Models with Adaptive Weighted
    Rejection Sampling
summary: 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.
paper_authors._id: 67f80f73cce5a0f258129554
paper_authors.name: Benjamin Lipkin
paper_authors.status: extracted_confirmed
paper_authors.statusLastChangedAt: 2025-04-10T18:46:57.881Z
paper_authors._id: 613a6efea488863c1920731e
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/1664283416127-613a6efea488863c1920731e.jpeg
paper_authors.fullname: Ben Lipkin
paper_authors.type: user
paper_authors.user: benlipkin
paper_authors._id: 67f80f73cce5a0f258129555
paper_authors.name: Benjamin LeBrun
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2025-04-11T07:25:51.744Z
paper_authors._id: 613a6efea488863c1920731e
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/1664283416127-613a6efea488863c1920731e.jpeg
paper_authors.fullname: Ben Lipkin
paper_authors.type: user
paper_authors.user: benlipkin
paper_authors._id: 67f80f73cce5a0f258129556
paper_authors.name: Jacob Hoover Vigly
paper_authors._id: 67f80f73cce5a0f258129557
paper_authors.name: João Loula
paper_authors.status: extracted_pending
paper_authors.statusLastChangedAt: 2025-04-10T18:35:33.249Z
paper_authors._id: 655c76dcf37a7d0b09348813
paper_authors.avatarUrl: /avatars/6fed15a38652dcc62f9022c5ff905cf2.svg
paper_authors.fullname: João Loula
paper_authors.type: user
paper_authors.user: jloula
paper_authors._id: 67f80f73cce5a0f258129558
paper_authors.name: David R. MacIver
paper_authors._id: 67f80f73cce5a0f258129559
paper_authors.name: Li Du
paper_authors._id: 67f80f73cce5a0f25812955a
paper_authors.name: Jason Eisner
paper_authors._id: 67f80f73cce5a0f25812955b
paper_authors.name: Ryan Cotterell
paper_authors._id: 67f80f73cce5a0f25812955c
paper_authors.name: Vikash Mansinghka
paper_authors._id: 67f80f73cce5a0f25812955d
paper_authors.name: Timothy J. O'Donnell
paper_authors.status: extracted_confirmed
paper_authors.statusLastChangedAt: 2025-04-10T18:36:14.652Z
paper_authors._id: 632b7bed6110e37dba3f5793
paper_authors.avatarUrl: /avatars/564d7b53f14f9dfc54aefc5dafb7f8a8.svg
paper_authors.fullname: Tim O'Donnell
paper_authors.type: user
paper_authors.user: todonnell
paper_authors._id: 67f80f73cce5a0f25812955e
paper_authors.name: Alexander K. Lew
paper_authors.status: extracted_pending
paper_authors.statusLastChangedAt: 2025-04-10T18:35:33.249Z
paper_authors._id: 673cc08370644bb836283fec
paper_authors.avatarUrl: /avatars/b8c7f1a10ddf76dcd06398c59f553b61.svg
paper_authors.fullname: Alexander Lew
paper_authors.type: user
paper_authors.user: alexanderlew
paper_authors._id: 67f80f73cce5a0f25812955f
paper_authors.name: Tim Vieira
paper_title: Fast Controlled Generation from Language Models with Adaptive Weighted
    Rejection Sampling
paper_summary: 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.
paper_ai_summary: 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.
paper_ai_keywords: 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