- 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
- 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.
- Rich theoretical analyses. The paper carefully defines existing exact sampling approaches and introduces "envelopes."
- Experimental results. On BBH word sorting, MARS exceeds the SMC method across different ensemble settings (minimum, product, mixture, and maximum) in efficiency.
Critical weaknesses
- 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.
- 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.
- 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
- 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.
- 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?
- In the first paragraph in Section 2, what do and mean?
- 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
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.
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:
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, compared with −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× 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) for the target weight and Z for the sum of these weights. When expanding a prefix, let its old bound be b and the sum of the tighter child masses be b′. The descent survives with probability b′/b. Conditional on survival, a child of mass c is selected with probability c/b′. Their product is c/b. At terminal sequences we use the true target weight. These factors telescope: a descent starting with root mass Q returns w with probability ϕ(w)/Q. Conditioning on success gives ϕ(w)/Z. Tightened bounds remain valid after rejection, so the argument also applies to later descents, under the finite length bound and Z>0.
We will make this existing rejection step explicit in Algorithm 1 and clarify it in Section 3. Appendix A gives the proof;
returnProb_eqandsoundnessformalize the finite-state identities in Lean.3. What are Σ∗ and ε? Σ is the vocabulary without EOS. Σ∗ contains all finite strings over Σ, including the empty string ε. 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.