acceptodds
Withdrawn from ICLR 2027

Modular Adaptive Rejection Sampling

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Autoregressive language models are increasingly used in combination: one wants to intersect two models so that outputs are probable under both, take their union, sharpen a model, or contrast it against a weaker model. Existing approaches for sampling from such combinations are either efficient but not faithful to the distribution induced by the model combination, or faithful but not efficient, paying for every disagreement between the models at every sample. We present Modular Adaptive Rejection Sampling (\mars), an exact rejection sampling algorithm that supports complex combinations of distributions and that learns from its rejections. \mars generates a sample token by token, keeping for every prefix an upper bound on the total target weight of the sequences that start with that prefix and choosing each next token in proportion to these bounds. When \mars extends a prefix, the bounds of the prefix's possible extensions reveal how much the prefix's own bound overpromised; \mars rejects with exactly that probability and remembers the tighter bound, so the same rejection never happens again. Such bounds, which we call envelopes, are closed under intersection, union, sharpening, reweighting, and constraining, which yields an algebra of language models: any globally-normalized distribution built from these operations can be sampled exactly by the same algorithm. On three benchmarks, \mars uses up to fewer forward passes than sequential MC at the particle count prior work reports, while sampling exactly; against rejection sampling, \mars needs up to fewer descents per sample, and sometimes samples where rejection sampling times out at 400 attempts.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
exact sampling, rejection sampling, language model ensembles, constrained decoding

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_en9iOpenReview ↗
Rating
1
Confidence
2
Informativeness
2(+1)
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes a novel sampling method, MARS, for language model combination, including intersect, union, sharpen, reweight, and constrain, that offers exact distributions and practical sampling cost. To achieve this, they theoretically formulate existing rejection sampling (RS), in which the total target weight of all completions for a given prefix is computed. They introduce a computationally inexpensive upper bound, called “envelopes,” as an alternative to the total target weight in normal RS. They propose an efficient RS method, MARS, in which a computationally inexpensive upper bound is used instead of the exact total weight of all completions of a given prefix. A theoretical guarantee is provided to show that MARS can achieve exact sampling and monotonic improvement in acceptance probability. Furthermore, they generalize MARS to model combinations, including intersection, union, sharpening, reweighting, and constraints. Finally, empirical studies compare MARS against ordinary RS methods and sequential Monte Carlo (SMC), showing that, overall, MARS can achieve slightly faster sampling than ordinary RS while maintaining accuracy.

Critical strengths
  1. Clear motivation. The paper clearly states its goal of establishing the ideal sampler for combining multiple language models. The authors define it as exact and requiring few forward passes per sample.
  2. Rich theoretical analyses. The paper carefully defines existing exact sampling approaches and introduces "envelopes."
  3. Experimental results. On BBH word sorting, MARS exceeds the SMC method across different ensemble settings (minimum, product, mixture, and maximum) in efficiency.
Critical weaknesses
  1. Hard-to-follow writing style. There is some missing evidence or explanation to support the paper's approach. There are scattered instances where the logical progression makes abrupt leaps, making it likely that readers will struggle to understand the content.
  2. Missing clear definition. Some of the variables used in the theoretical analysis are either undefined or unclear. Since this paper features numerous complex notations, it is essential to present the theoretical analysis in a thorough and clear manner.
  3. Limited effectiveness. The accuracy results and the number of forward passes per sample in the evaluation showed no significant difference between MARS and the competing method (ordinary RS). In particular, there was no improvement whatsoever at the ensemble setting of "maximum."
Questions for authors
  1. The competing method for MARS is the existing RS approach, isn’t it? Why do you mention SMC in the Introduction and compare MARS with it in the experiment? If MARS is completely built on the RS approach, the context of SMC is unnecessary.
  2. Could you provide proof or any evidence for why choosing each next token in proportion to an upper bound on the target weight of the given prefix’s completions in the global distribution is valid, and why the upper bound is chosen?
  3. In the first paragraph in Section 2, what do Σ∗\Sigma^* and ϵ\epsilon mean?
  4. In Table 2, why does SMC exceed RS in accuracy? This result conflicts with your explanation: "Approximate methods like SMC become exact asymptotically, but their bias at any fixed budget is unknown."
2 comments

1. Why compare with SMC? The 2 baselines answer different questions. Cached RS isolates the benefit of learning from samples within exact rejection sampling. SMC measures the cost of an approximate alternative for the same globally normalized targets.

SMC particle sweep. SMC is asymptotically correct as the number of particles grows, but generally approximate at any fixed particle count. Its comparison with MARS therefore measures the cost of exact sampling relative to an approximate alternative, while cached RS isolates the benefit of adaptation within exact sampling. Preliminary experiments on BBH minimum, Spider geometric mean and JSON minimum cover all 12 planned instances and both seeds, with 20 requested draws per arm per instance–seed pair. Seconds per accepted sample, including timeout costs, are:

TargetMARSSMC1SMC2SMC5SMC10
BBH minimum3.292.443.817.1912.14
Spider geometric mean14.1914.3125.2055.9698.51
JSON minimum57.5250.91100.71185.64276.06

On JSON, SMC5 returned 455 of the 480 requested samples and SMC10 returned 431; all other entries in the table completed all 480 requests. SMC1 is fast, but on BBH its samples have lower target log weights than MARS: the mean difference is −5.49-5.49, compared with −0.23-0.23 between 2 independent MARS runs. On BBH, SMC differs from MARS in mean output length and target log weight at 1, 2 and 5 particles. 10 is the first tested particle count where neither difference is detected. At that setting, MARS is 3.7×3.7\times faster (3.29 vs. 12.14 seconds/sample). We only checked output length and target log weight; agreement on these averages does not prove that the sampled distributions are identical.

Cached RS already avoids repeated model evaluations. We will clarify the distinction between reductions in rejection attempts, model calls and wall time in the paper. The pilot covers both within-model and cross-model targets. In terms of wall time, the uncertainty intervals do not establish an advantage for either method, but the original ablation shows that learning from samples reduces descents from 4.57 to 1.58 per sample. Caching makes repeated descents cheap, so fewer descents need not translate into a wall-time speedup. The general response summarizes the timing and completion results.

2. Why do upper bounds give valid samples? Neither RS nor MARS needs the exact mass of every subtree. Selecting tokens in proportion to bounds is only part of MARS: the rejection step makes the output exact.

Write ϕ(w)\phi(w) for the target weight and ZZ for the sum of these weights. When expanding a prefix, let its old bound be bb and the sum of the tighter child masses be b′b'. The descent survives with probability b′/bb'/b. Conditional on survival, a child of mass cc is selected with probability c/b′c/b'. Their product is c/bc/b. At terminal sequences we use the true target weight. These factors telescope: a descent starting with root mass QQ returns ww with probability ϕ(w)/Q\phi(w)/Q. Conditioning on success gives ϕ(w)/Z\phi(w)/Z. Tightened bounds remain valid after rejection, so the argument also applies to later descents, under the finite length bound and Z>0Z>0.

We will make this existing rejection step explicit in Algorithm 1 and clarify it in Section 3. Appendix A gives the proof; returnProb_eq and soundness formalize the finite-state identities in Lean.

3. What are Σ∗\Sigma^* and ε\varepsilon? Σ\Sigma is the vocabulary without EOS. Σ∗\Sigma^* contains all finite strings over Σ\Sigma, including the empty string ε\varepsilon. We will define both in Section 2, move the operation table after the envelope definition, and use distinct notation for the constraint set and length bound.

4. Why can SMC have higher accuracy? Accuracy and fidelity measure different things. If the target assigns probability 0.6 to a correct answer, an exact sampler has expected accuracy 0.6. Always returning that answer scores 1 but changes the distribution. Higher task accuracy is therefore compatible with sampling bias, although an observed accuracy difference alone does not prove bias.

BBH maximum reports 41% for SMC and 36% for MARS. We will fix the sentence describing JSON maximum: MARS has higher accuracy than SMC (56% vs. 52%), as already reported in the table. We will also clarify the distinction between task accuracy and agreement with the target distribution.

Thank you for the detailed response and the additional experiments. My initial concerns have been addressed, and I acknowledge the theoretical contributions. However, I think that sufficient evidence has not yet been provided regarding the practical computational efficiency advantages of MARS (see below for details). Consequently, until these experimental concerns are resolved, it is difficult to significantly raise my assessment of the paper's overall validity. Therefore, while I am increasing the "informativeness" score from 1 to 2, I will keep the overall rating.


To elaborate, specifically, for the BBH minimum, the number of descent steps is reduced from 4.57 to 1.58 compared to standard RS. However, the number of forward passes shows only a marginal improvement (from 47.1 to 46.1), and no statistically significant advantage in wall-clock time has been demonstrated.

Reviewer_Fff9OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper proposes Modular Adaptive Rejection Sampling (MARS), an exact sampler for globally normalized combinations of autoregressive language models, such as products, minima, mixtures and generalized means, optionally with constraints or verifiers. MARS generalizes Constrained Adaptive Rejection Sampling (CARS, Parys et al., 2026). CARS tracks the probability mass that remains valid under a hard constraint. MARS instead stores, for each prefix, an upper bound ("envelope") on the target weight below it. When a prefix is expanded, the bound is tightened and the descent is rejected with probability equal to how much the old bound overpromised.

I see two main contributions:

  • An algebra of envelopes. A framework for deriving valid envelopes for combinations of models, closed under products, minima, mixtures, sharpening, reweighting and constraining. It is complemented by a lower bound showing that tempering and contrasting cannot be sampled efficiently by any exact method with next-token access.
  • Learning from rejections. A modification of rejection sampling that stores the tightened bounds, so a disagreement between models is paid for only once and the acceptance rate increases monotonically.

The experiments (BBH word sorting, Spider, JSON Schema) show that exact sampling with these envelopes needs 3.4–8× fewer forward passes than SMC at the particle count used in prior work. Compared with rejection sampling that shares the same prefix cache, MARS needs fewer descents per sample and avoids timeouts on hard instances.

Critical strengths

The algebra of envelopes is a clean and useful framework for reasoning about combinations of language models and for deriving exact samplers for them. The lower bound for tempering and contrasting is a nice complement that delimits what is possible. The theoretical claims come with proofs, many of them formalized in Lean. I did not check the proofs.

Exact sampling turns out to be competitive with, and often cheaper than, the approximate SMC baseline in forward passes. This is a useful empirical finding.

Learning from rejections is most valuable when the probability of a valid sample is very low. There, rejection sampling fails while MARS still returns samples.

Critical weaknesses

Presentation. The paper is very hard to read. The introduction does not clearly state the problem or why it matters. It would help to explain early, with a concrete example, why one wants outputs that are probable under both models, and why sampling from one model or locally renormalizing the product is not enough.

Section 2 introduces a large amount of notation and previews results (envelopes, terminal slack, Theorem A.7, Corollary A.8) whose meaning only becomes clear in Sections 3–4 or the appendix. I recommend the authors include more intuition and perhaps figures to explain how the algorithm works without relying so much on definitions and theorems.

Motivation and use cases. The paper would benefit from a concrete application in which exact sampling of a model combination is needed and the bias of approximate methods matters in practice. On the reported benchmarks, accuracy is similar across MARS, RS and SMC, and SMC is more accurate on the maximum.

Benefit of learning over rejection sampling. Learning is what distinguishes MARS from rejection sampling, but it reduces descents, not forward passes. With a shared prefix cache, MARS and RS use almost the same number of forward passes (1.00–1.07× on most rows, and RS uses fewer where it times out). The savings relative to SMC therefore seem to come from the envelope and the cache rather than from learning. Forward passes dominate the cost and cached descents are cheap, so outside the low-acceptance regime the practical gain of learning seems small.

Shared vocabulary. The method requires the combined models to share a tokenizer, which limits cross-model ensembles.

Questions for authors

My questions are about quantifying the benefit of MARS over RS.

  • What is the wall-time of MARS against RS with the same prefix cache?
  • How do timeout rates compare when the budget is matched in wall-clock time (including forward passes), rather than in descents?
1 comment

1. Wall time against cached RS. To partly answer the reviewer’s question, we ran a small pilot where we compare MARS and cached RS under identical time budgets on 2 within-model Qwen targets and a Qwen-7B/14B target. Both methods run in the same process on the same GPU. Sometimes MARS runs first; sometimes cached RS runs first. Each method starts with an empty cache and reuses it while trying to produce 5 samples. MARS/RS time ratios are 1.065, 1.079 and 0.999. 5-sample completion is 58/60 versus 58/60, 60/60 versus 60/60, and 32/40 versus 31/40. The cross-model completion difference is +2.5 percentage points. In this pilot, MARS and cached RS have similar observed wall times and completion rates. In terms of wall time, the uncertainty intervals do not establish an advantage for either method, but the original ablation shows that learning from samples reduces descents from 4.57 to 1.58 per sample. Caching makes repeated descents cheap, so fewer descents need not translate into a wall-time speedup.

2. Timeouts under equal wall-clock budgets. Completion outcomes coincide on both within-model targets. On the cross-model target, MARS completes 32/40 pairs versus 31/40 for cached RS: a +2.5 percentage-point difference. This does not resolve a completion advantage. Attempt-budget results are reported separately.

What learning from samples adds. In the original BBH minimum comparison, learning from samples reduces descents from 4.57 to 1.58, while calls fall from 47.1 to 46.1. Uncached RS takes 190.2 calls. We will clarify which gains come from caching and which from learning from samples. SMC also uses the envelope and cache. The general response reports the broader SMC particle sweep and explains the numerical correction used in the new experiments. We will put the framework for exact sampling of compositional targets first in the paper’s framing.

SMC particle sweep. Preliminary experiments on BBH minimum, Spider geometric mean and JSON minimum cover all 12 planned instances and both seeds, with 20 requested draws per arm per instance–seed pair. Seconds per accepted sample, including timeout costs, are:

TargetMARSSMC1SMC2SMC5SMC10
BBH minimum3.292.443.817.1912.14
Spider geometric mean14.1914.3125.2055.9698.51
JSON minimum57.5250.91100.71185.64276.06

On JSON, SMC5 returned 455 of the 480 requested samples and SMC10 returned 431; all other entries in the table completed all 480 requests. SMC1 is fast, but on BBH its samples have lower target log weights than MARS: the mean difference is −5.49-5.49, compared with −0.23-0.23 between 2 independent MARS runs. On BBH, SMC differs from MARS in mean output length and target log weight at 1, 2 and 5 particles. 10 is the first tested particle count where neither difference is detected. At that setting, MARS is 3.7×3.7\times faster (3.29 vs. 12.14 seconds/sample). We only checked output length and target log weight; agreement on these averages does not prove that the sampled distributions are identical.

Motivation and presentation. We will add a numerical example to Section 1: global normalization assigns a prefix probability 0.625, while local normalization gives 0.5 because it misses downstream disagreement. The goal is to preserve the specified ensemble distribution; the benchmarks do not establish a downstream accuracy benefit from exactness.

We will move the operation table after the envelope definition, make the rejection step explicit in Algorithm 1, and add a limitations section stating the shared-tokenizer restriction. Combining distinct Qwen models does not remove that limitation.

Reviewer_ozs2OpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents Modular Adaptive Rejection Sampling (MARS), an exact sampling framework for globally normalized combinations of autoregressive language models. Building on constrained adaptive rejection sampling, MARS introduces compositional envelopes that provide upper bounds on the target probability mass associated with each prefix. By maintaining a prefix trie and progressively refining these bounds, the framework leverages information from previous rejections to improve sampling efficiency while preserving distributional exactness. The method further develops an algebra of envelopes supporting intersection, union, sharpening, reweighting, and constraint operations. Experiments across three benchmarks demonstrate that MARS substantially reduces the number of sampling attempts compared with conventional rejection sampling.

Critical strengths
  • Clear problem formulation and compelling research motivation. The paper clearly distinguishes local and global normalization and highlights the trade-off between sampling exactness and computational efficiency, providing strong motivation for the proposed framework.
  • Strong theoretical foundations. The paper establishes rigorous guarantees for exact sampling, monotonically non-decreasing acceptance probabilities, and diminishing returns in rejection-mass reduction, alongside computational lower bounds that characterize the fundamental limitations of exact sampling.
Critical weaknesses
  • Limited practical efficiency gains over rejection sampling. Despite substantially reducing rejection attempts, MARS achieves only marginal forward-pass savings over cached RS (46.1 vs. 47.1 on BBH minimum), raising concerns about its practical computational efficiency.
  • Insufficient comparison with SMC under matched sampling fidelity. The paper lacks comprehensive comparisons with SMC under matched computational budgets and sampling fidelity, making it difficult to assess MARS's relative efficiency.
  • Incremental algorithmic novelty relative to CARS. MARS largely retains CARS's trie-based sampling and rejection-reuse mechanisms, with its primary extension being compositional envelopes. The paper should more clearly establish the algorithmic novelty beyond this generalization.
Questions for authors
  1. What practical efficiency gains does MARS provide over cached rejection sampling?
  2. How does MARS compare with SMC under matched sampling fidelity and computational budgets? Evaluating different particle counts across more benchmarks would provide stronger evidence for MARS's efficiency advantages.
  3. How well does MARS scale with larger vocabularies, longer sequences, and increasing sample counts?
2 comments

1. Gains over cached RS. The original BBH minimum ablation gives 190.2 / 47.1 / 46.1 model calls per sample for uncached RS / cached RS / MARS. Caching explains most of this reduction. Learning from samples reduces descents from 4.57 to 1.58; a cached descent can be cheap. We will clarify the distinction between rejection attempts and wall-time gains in the paper.

The general response summarizes the timing and completion pilot on Qwen-7B minimum, Qwen-7B geometric mean and Qwen-7B/14B minimum. In terms of wall time, the uncertainty intervals do not establish an advantage for either method, but the original ablation shows that learning from samples reduces descents from 4.57 to 1.58 per sample. Caching makes repeated descents cheap, so fewer descents need not translate into a wall-time speedup.

2. SMC particle count and fidelity. SMC is asymptotically correct as the number of particles grows, but generally approximate at any fixed particle count. Its comparison with MARS therefore measures the cost of exact sampling relative to an approximate alternative, while cached RS isolates the benefit of adaptation within exact sampling. Preliminary experiments on BBH minimum, Spider geometric mean and JSON minimum cover all 12 planned instances and both seeds, with 20 requested draws per arm per instance–seed pair. Seconds per accepted sample, including timeout costs, are:

TargetMARSSMC1SMC2SMC5SMC10
BBH minimum3.292.443.817.1912.14
Spider geometric mean14.1914.3125.2055.9698.51
JSON minimum57.5250.91100.71185.64276.06

On JSON, SMC5 returned 455 of the 480 requested samples and SMC10 returned 431; all other entries in the table completed all 480 requests. SMC1 is fast, but on BBH its samples have lower target log weights than MARS: the mean difference is −5.49-5.49, compared with −0.23-0.23 between 2 independent MARS runs. On BBH, SMC differs from MARS in mean output length and target log weight at 1, 2 and 5 particles. 10 is the first tested particle count where neither difference is detected. At that setting, MARS is 3.7×3.7\times faster (3.29 vs. 12.14 seconds/sample). We only checked output length and target log weight; agreement on these averages does not prove that the sampled distributions are identical.

3. Scaling. Dense-trie storage is O(VE)O(VE), with vocabulary size VV and EE expanded prefixes; an ancestor update costs O(Vd)O(Vd) host work at depth dd. These bounds do not determine how many model evaluations are needed. We have no controlled vocabulary-size study, and the evaluation caps outputs at 128 tokens.

Both MARS and cached RS reuse work across samples. The original 30-sample study does not show a growing model-call advantage for MARS. The corrected runtime's additional prefix storage is not covered by the old memory measurements; we will state this limit explicitly in the paper.

4. Novelty over CARS. The trie mechanics are inherited. CARS uses a model probability times a binary prefix-validity indicator; MARS supports quantitative bounds for soft combinations, with the required terminal rejection corrections. The contributions are the envelope abstraction and the exact sampler it induces, composition rules, the tempering/contrasting lower bound, and weighted diminishing-returns analysis. The finite-state sampling identities are formalized in Lean; the lower bound is proved on paper.

Reviewer_ozs2OpenReview ↗

Response for the Rebuttal

Thank you for the detailed response and additional experiments. Clarifying MARS's contributions relative to CARS and expanding the SMC comparisons have addressed several of my concerns. However, the modest wall-time speedups over cached rejection sampling and the lack of controlled scalability experiments remain open issues. Consequently, I will maintain my current score.

Comments on the paper

1 comment

MARS is a framework for exact sampling from globally normalized model combinations. Its main contribution is the envelope abstraction and its composition rules, together with the lower bound for tempering and contrasting. The trie mechanics and rejection build on CARS. We will revise the paper to make this distinction clearer.

What learning from samples adds. Cached RS already avoids repeated model evaluations. On the original BBH minimum experiment, uncached RS, cached RS and MARS take 190.2, 47.1 and 46.1 calls per sample. Learning from samples reduces descents from 4.57 to 1.58, but these are different measures of work. We will distinguish model calls, rejection attempts and wall time more clearly in the paper. SMC also uses the envelope and prefix cache; the RS cache ablation does not relate to the comparison with SMC.

Wall time and completion. To partly answer the reviewer’s question, we ran a small pilot where we compare MARS and cached RS under identical time budgets on 2 within-model Qwen targets and a Qwen-7B/14B target. Both methods run in the same process on the same GPU. Sometimes MARS runs first; sometimes cached RS runs first. Each method starts with an empty cache and reuses it while trying to produce 5 samples. MARS/RS time ratios are 1.065, 1.079 and 0.999. 5-sample completion is 58/60 versus 58/60, 60/60 versus 60/60, and 32/40 versus 31/40. The cross-model completion difference is +2.5 percentage points. In this pilot, MARS and cached RS have similar observed wall times and completion rates. In terms of wall time, the uncertainty intervals do not establish an advantage for either method, but the original ablation shows that learning from samples reduces descents from 4.57 to 1.58 per sample. Caching makes repeated descents cheap, so fewer descents need not translate into a wall-time speedup.

SMC particle sweep. SMC is asymptotically correct as the number of particles grows, but generally approximate at any fixed particle count. Its comparison with MARS therefore measures the cost of exact sampling relative to an approximate alternative, while cached RS isolates the benefit of adaptation within exact sampling. Preliminary experiments on BBH minimum, Spider geometric mean and JSON minimum cover all 12 planned instances and both seeds, with 20 requested draws per arm per instance–seed pair. Seconds per accepted sample, including timeout costs, are:

TargetMARSSMC1SMC2SMC5SMC10
BBH minimum3.292.443.817.1912.14
Spider geometric mean14.1914.3125.2055.9698.51
JSON minimum57.5250.91100.71185.64276.06

On JSON, SMC5 returned 455 of the 480 requested samples and SMC10 returned 431; all other entries in the table completed all 480 requests. SMC1 is fast, but on BBH its samples have lower target log weights than MARS: the mean difference is −5.49-5.49, compared with −0.23-0.23 between 2 independent MARS runs. On BBH, SMC differs from MARS in mean output length and target log weight at 1, 2 and 5 particles. 10 is the first tested particle count where neither difference is detected. At that setting, MARS is 3.7×3.7\times faster (3.29 vs. 12.14 seconds/sample). We only checked output length and target log weight; agreement on these averages does not prove that the sampled distributions are identical.

Numerical implementation. We corrected an inconsistency between historical-logit and causal-prefix scoring and added independent checks. The new sweep and timing runs use this corrected runtime. The original tables measure the earlier implementation; we will make this distinction explicit in the paper.

Presentation. We will add a numerical local/global example, define the missing notation, make the rejection step explicit, and state the tokenizer and memory limitations. We will fix the sentence describing JSON maximum: MARS has higher accuracy than SMC (56% vs. 52%), as already reported in the table.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.