Constrained Adaptive Rejection Sampling

• URL: http://arxiv.org/abs/2510.01902v1
• Date: Thu, 02 Oct 2025 11:17:26 GMT
• Title: Constrained Adaptive Rejection Sampling
• Authors: Paweł Parys, Sairam Vaidya, Taylor Berg-Kirkpatrick, Loris D'Antoni,
• Abstract summary: Language Models (LMs) are increasingly used in applications where generated outputs must satisfy strict semantic or syntactic constraints.<n>Existing approaches to constrained generation fall along a spectrum: greedy constrained decoding methods enforce validity during decoding but distort the LM's distribution.<n>We present Constrained Adaptive Rejection Sampling (CARS), an approach that strictly improves the sample-efficiency of RS without distributional distortion.
• Score: 27.579645342312674
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Language Models (LMs) are increasingly used in applications where generated outputs must satisfy strict semantic or syntactic constraints. Existing approaches to constrained generation fall along a spectrum: greedy constrained decoding methods enforce validity during decoding but distort the LM's distribution, while rejection sampling (RS) preserves fidelity but wastes computation by discarding invalid outputs. Both extremes are problematic in domains such as program fuzzing, where both validity and diversity of samples are essential. We present Constrained Adaptive Rejection Sampling (CARS), an approach that strictly improves the sample-efficiency of RS without distributional distortion. CARS begins with unconstrained LM sampling and adaptively rules out constraint-violating continuations by recording them in a trie and subtracting their probability mass from future draws. This adaptive pruning ensures that prefixes proven invalid are never revisited, acceptance rates improve monotonically, and the resulting samples exactly follow the constrained distribution. In experiments on a variety of domains -- e.g., program fuzzing and molecular generation -- CARS consistently achieves higher efficiency -- measured in the number of LM forward passes per valid sample -- while also producing stronger sample diversity than both GCD and methods that approximate the LM's distribution.

Related papers

• Corrected Samplers for Discrete Flow Models [36.348940136801296]
  A line of recent work has studied samplers for discrete diffusion models, such as tau-leaping and Euler solver.<n>We establish non-asymptotic discretization error bounds for those samplers without any restriction on transition rates and source distributions.<n>We rigorously show that the location-corrected sampler has a lower complexity than existing parallel samplers.
  arXiv  Detail & Related papers  (2026-01-30T03:53:22Z)
• Entropy-Aligned Decoding of LMs for Better Writing and Reasoning [21.971790771470324]
  Language models (LMs) are trained on billions of tokens in an attempt to recover the true language distribution.<n>Currently, vanilla random sampling from LMs yields low quality generations.<n>We introduce EPIC, a hyper- parameter-free decoding approach that incorporates the entropy of future trajectories into LM decoding.
  arXiv  Detail & Related papers  (2026-01-05T01:37:10Z)
• Chance-constrained Flow Matching for High-Fidelity Constraint-aware Generation [46.932479632530764]
  Chance-constrained Flow Matching integrates optimization into the sampling process, enabling effective enforcement of hard constraints.<n>Experiments show that CCFM outperforms current state-of-the-art constrained generative models in modeling complex physical systems.
  arXiv  Detail & Related papers  (2025-09-29T17:56:52Z)
• Flipping Against All Odds: Reducing LLM Coin Flip Bias via Verbalized Rejection Sampling [59.133428586090226]
  Large language models (LLMs) can often accurately describe probability distributions using natural language.<n>This mismatch limits their use in tasks requiring reliableity, such as Monte Carlo methods, agent-based simulations, and randomized decision-making.<n>We introduce Verbalized Rejection Sampling (VRS), a natural-language adaptation of classical rejection sampling.
  arXiv  Detail & Related papers  (2025-06-11T17:59:58Z)
• Towards Optimal Multi-draft Speculative Decoding [102.67837141152232]
  Multi-Draft Speculative Decoding (MDSD) is a recent approach where, when generating each token, a small draft model generates multiple drafts.<n>This paper discusses the dual of the optimal transport problem, providing a way to efficiently compute the optimal acceptance rate.
  arXiv  Detail & Related papers  (2025-02-26T03:22:44Z)
• Distributional Diffusion Models with Scoring Rules [83.38210785728994]
  Diffusion models generate high-quality synthetic data.<n> generating high-quality outputs requires many discretization steps.<n>We propose to accomplish sample generation by learning the posterior em distribution of clean data samples.
  arXiv  Detail & Related papers  (2025-02-04T16:59:03Z)
• Contrastive CFG: Improving CFG in Diffusion Models by Contrasting Positive and Negative Concepts [55.298031232672734]
  As-Free Guidance (CFG) has proven effective in conditional diffusion model sampling for improved condition alignment. We present a novel method to enhance negative CFG guidance using contrastive loss.
  arXiv  Detail & Related papers  (2024-11-26T03:29:27Z)
• REAL Sampling: Boosting Factuality and Diversity of Open-Ended Generation via Asymptotic Entropy [93.8400683020273]
  Decoding methods for large language models (LLMs) usually struggle with the tradeoff between ensuring factuality and maintaining diversity. We propose REAL sampling, a decoding method that improved factuality and diversity over nucleus sampling.
  arXiv  Detail & Related papers  (2024-06-11T21:44:49Z)
• Amortizing intractable inference in large language models [56.92471123778389]
  We use amortized Bayesian inference to sample from intractable posterior distributions. We empirically demonstrate that this distribution-matching paradigm of LLM fine-tuning can serve as an effective alternative to maximum-likelihood training. As an important application, we interpret chain-of-thought reasoning as a latent variable modeling problem.
  arXiv  Detail & Related papers  (2023-10-06T16:36:08Z)
• Conditional Sampling of Variational Autoencoders via Iterated Approximate Ancestral Sampling [7.357511266926065]
  Conditional sampling of variational autoencoders (VAEs) is needed in various applications, such as missing data imputation, but is computationally intractable. A principled choice forally exact conditional sampling is Metropolis-within-Gibbs (MWG)
  arXiv  Detail & Related papers  (2023-08-17T16:08:18Z)
• Selectively increasing the diversity of GAN-generated samples [8.980453507536017]
  We propose a novel method to selectively increase the diversity of GAN-generated samples. We show the superiority of our method in a synthetic benchmark as well as a real-life scenario simulating data from the Zero Degree Calorimeter of ALICE experiment in CERN.
  arXiv  Detail & Related papers  (2022-07-04T16:27:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.