Research map / Probabilistic and scientific modeling / Variational and generative sampling
Controllable Generation via Locally Constrained Resampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Locally Constrained Resampling (Gen-C), which builds a local factorized pseudolikelihood around an LLM sample, conditions it exactly on a logical constraint via constraint circuits, and corrects bias with importance-weighted resampling to guarantee constraint satisfaction.
Problem
Autoregressive models struggle to generate outputs that satisfy logical constraints; greedy token-masking methods are myopic and do not sample from the correctly conditioned distribution.
Approach
Treat an LLM sample as inducing a local factorized (contextualized pseudolikelihood) distribution that can be exactly conditioned on a constraint compiled into a constraint circuit; sample from this conditional, reweight by importance weights against the LLM, and resample, yielding constraint-satisfying samples close to the conditional LLM distribution.
Key results
- On Warcraft shortest path, the method raises exact-match accuracy from 69.10% (oversampling) to 78.13% with 100% consistency.
- On Sudoku, Llama3-8B with the method reaches 100% exact accuracy versus 44.90% for GPT-4o mini and 26.20% for Gemini 1.5 Flash.
- On RealToxicityPrompts with Llama3-8B, the method lowers toxic-prompt expected max toxicity from 0.43 to 0.37 and toxicity probability from 38.30% to 28.00%, matching word banning perplexity (14.50).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply LCR instead of oversampling | CNN-LSTM · Warcraft | Exact accuracy: 69.10% -> 78.13% | Helped |
| Apply LCR to constrain generated paths | CNN-LSTM · Warcraft | Consistent accuracy: 76.60 -> 100% | Helped |
| Apply LCR with Sudoku constraints | Llama3-8B · Sudoku | Exact accuracy: 44.90% -> 100% | Helped |
| Apply LCR with Sudoku constraints | Llama3-8B · Sudoku | Consistent accuracy: 44.90% -> 100% | Helped |
| Ban listed toxic expressions with LCR | Llama3-8B · RealToxicityPrompts Toxic | Expected maximum toxicity: 0.43 -> 0.37 | Helped |
| Ban listed toxic expressions with LCR | Llama3-8B · RealToxicityPrompts Toxic | Toxicity probability: 38.30% -> 28.00% | Helped |
| Ban listed toxic expressions with LCR | Llama3-8B · RealToxicityPrompts Full | Expected maximum toxicity: 0.25 -> 0.23 | Helped |
| Ban listed toxic expressions with LCR | Llama3-8B · RealToxicityPrompts Full | Toxicity probability: 14.26% -> 11.04% | Helped |
| Ban listed toxic expressions with LCR | Llama3-8B · RealToxicityPrompts Nontoxic | Expected maximum toxicity: 0.20 -> 0.19 | Helped |
| Ban listed toxic expressions with LCR | Llama3-8B · RealToxicityPrompts Nontoxic | Toxicity probability: 7.60% -> 6.35% | Helped |
| Ban listed toxic expressions with LCR | Llama3-8B · RealToxicityPrompts | PPL: 14.45 -> 14.50 | Hurt |
Limitations
- Detoxification uses top-k approximation of the pseudolikelihood due to compute limits
- Sampling guarantees hold only in the limit of large sample size for resampling-based correctness of distribution
- Evaluated only on relatively small or simple constraints (word bans, Sudoku uniqueness, path validity)
Experimental setup
Datasets: Warcraft shortest path dataset Sudoku 10K puzzles RealToxicityPrompts LDNOOBW bad words list
Benchmarks: Warcraft shortest path Sudoku RealToxicityPrompts
Metrics: exact match accuracy consistency expected maximum toxicity toxicity probability perplexity
Baselines: Word Banning Gemini 1.5 Flash GPT-4o mini CNN-LSTM oversampling
Builds on: Outlines NeuroLogic Decoding ASAp PICARD sentential decision diagrams
Closest papers by meaning
- Constrained Discrete Diffusion (NeurIPS 2025 · similarity 0.89)
- Guaranteed Generation from Large Language Models (ICLR 2025 · similarity 0.88)
- Constrained Sampling for Language Models Should Be Easy: An MCMC Perspective (NeurIPS 2025 · similarity 0.87)
- Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata (NeurIPS 2026 · similarity 0.87)
- Beyond Autoregression: Fast LLMs via Self-Distillation Through Time (ICLR 2025 · similarity 0.87)
- Breaking AR’s Sampling Bottleneck: Provable Acceleration via Diffusion Language Models (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.