- Rating
- 1(−1)
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes prefix-balanced decoding, which coordinates samples within identical-prefix groups while preserving each sample’s next-token distribution conditional on the full observed batch history. It characterizes optimal prefix occupancy under this constraint and reports consistent but modest gains on finite intent decoders derived from three language models.
Critical strengths
-
The distinction between endpoint marginal validity and validity conditional on the observed batch is clearly formulated. Theorems 1–2 provide a useful characterization of all universal prefix-occupancy optimizers, going beyond the classical one-step balancing construction.
-
The finite-decoder experiments isolate the effect of sampling dependence by using identical model posteriors and exact static occupancy calculations. The paired uncertainty analysis and explicit discussion of the method’s limitations make the reported results reasonably convincing within this setting.
Critical weaknesses
-
The practical importance of the stronger conditional-validity requirement remains unclear. The endpoint lattice’s post-inspection TV discrepancy (0.00236) and target-calibration gap (0.00143) are both below the prespecified 0.01 materiality threshold, and the experiments do not show that these discrepancies cause a consequential downstream error (section 5.1, table 16).
-
The optimality guarantees concern individual prefixes and separable occupancy objectives; they do not cover arbitrary semantic sets of correct answers, and the restart theorem only establishes optimal continuation after a single selection at a common state. The canonical-label experiments closely match these assumptions, leaving the significance of the results for broader adaptive generation insufficiently established (proposition 2, theorem 5).
-
The roughly one-percentage-point gains are reported without measuring the cost of prefix grouping and synchronized decoding. Since the evaluation uses precomputed finite-label posteriors, it remains unclear whether these gains translate into a useful improvement at a fixed runtime budget.
The characterization is useful, but I am not convinced that its significance within the stated setting, together with the current empirical evidence, is sufficient for acceptance. I recommend weak rejection because the need for the stronger contract and its practical value remain insufficiently demonstrated, rather than because of an identified error in the main proofs.
Questions for authors
-
Can the authors show whether the measured conditional distortions change a downstream selection or budget-allocation decision? Given that the reported discrepancies are below the materiality threshold, a concrete decision-level effect would strengthen the motivation for the stricter contract.
-
Could the authors examine a small extension of the finite-decoder experiment in which several output strings count as successful, rather than a single canonical label? In light of Proposition 2, this would help determine whether the observed benefits survive a modest relaxation of the evaluation assumptions.
-
Could Full PBD, PBD4, IID, and the endpoint-lattice references be compared on the same 1,368-row integration subset, with paired utility differences? As appendix D.4 acknowledges, the reported primary PBD and lattice averages use different query populations and therefore do not establish a direct comparison.
-
What runtime overhead do prefix grouping and synchronization introduce relative to iid decoding? A comparison of IID, PBD4, and Full PBD under a matched time budget would help establish whether shallow coordination offers a useful practical tradeoff.
If the authors can satisfactorily address the above questions and clarify the practical cost-benefit tradeoff of the proposed method, I would be open to raising my rating.
6 comments
Weakness 2 and Question 2, multiple correct strings
Weakness 2 and Question 2: Do the benefits survive several successful strings?
Thank you for proposing this specific extension. Yes, full PBD improves the mean in all six tested model–dataset settings. We newly score the canonical phrase and two natural paraphrases per intent, including EOS, and evaluate success on their union. The study uses the same 7,610 distinct inputs across three fixed checkpoints: 3,080 BANKING77 and 4,530 primary CLINC queries per model, giving 22,830 model–query evaluations.
| Model | BANKING77 gain | CLINC gain |
|---|---|---|
| Phi-3.5-mini | +1.18 pp | +1.47 pp |
| Qwen2.5-3B | +1.09 pp | +1.11 pp |
| Qwen2.5-7B | +0.84 pp | +0.65 pp |
The equal-cell full-PBD minus IID gain is 1.06 percentage points, paired 95% interval [1.00, 1.11], and multiplicity-adjusted 98.33% interval [0.99, 1.13]. Absolute semantic hit is 69.67%/70.72%/70.73% for IID/PBD4/full PBD. Token-order and class-contiguous endpoint references attain 70.740%/70.742%, under their distinct contracts. PBD4 retains 99.3% of the full gain.
All methods use identical query identities and newly scored posteriors. The PBD calculation integrates joint sibling allocations for the correct-string union rather than adding singleton hit probabilities. Query resampling is stratified within intents and shared across models and methods, so repeated model evaluations do not become independent inputs.
The catalog was fixed before scoring. Canonical strings retain 99.4% of normalized mass, and the same-prompt canonical-only control gives a 1.06-point gain. The result therefore supports the modest relaxation you requested: the aggregate benefit survives several naturally scored successful strings, while Proposition 2's boundary for arbitrary semantic unions remains unchanged. Section 5.2 (p. 9) and Appendix F.2, Tables 20–21 (p. 28), report the complete comparison and control.
Weakness 2, continued: Does the restart theorem cover broader adaptive generation?
We appreciate this distinction. A related reviewer request motivated a repeated reward-guided pruning study, which also addresses this part of your concern. We evaluated 94,968 requests on GSM8K using a frozen, gold-free Qwen2.5-Math-PRM-7B controller, retaining four unfinished lanes at depth 64 and two at depth 192. Controller cost is included, and unpruned controls retain the verifier.
The primary timed full-PBD minus IID effect is −0.44 points, adjusted interval [−1.52, 0.66], so the study does not establish a utility ordering in this setting. Section 5.4 (p. 10) and Appendix F.4 (p. 30) report all fixed schedules and the matched-block configuration mixture. This supplies the broader controller evaluation rather than assuming its performance follows from Theorem 5, whose guarantee remains completion from the same once-selected state without further pruning.
Question 3 and Weakness 3 / Question 4, matched comparisons
Question 3: Can all five methods be compared on the identical 1,368-row subset?
Thank you for identifying the population mismatch. We now compare all five methods on exactly the same 1,368 model–query rows, representing 456 distinct queries from the canonical-label experiment. The settings are T=1, initial K=8, observation depth two, retained budget four, and the same target-free controller.
| Method | Target-free pass (%) |
|---|---|
| IID | 67.837 |
| PBD4 | 68.879 |
| Full PBD | 68.880 |
| Token-order endpoint lattice | 68.776 |
| Label-order endpoint lattice | 68.758 |
Full PBD exceeds the token-order lattice by 0.104 percentage points [0.009, 0.202] and the label-order lattice by 0.122 points [0.020, 0.225]. These post-hoc descriptive 95% intervals resample queries within intents, preserve pairing across models and methods, and condition on the stored boundary estimates.
Section 5.1 (p. 9) displays the common-population means; Appendix F.5, Tables 26–27 (p. 31), gives all paired utility differences. This resolves the denominator concern and provides the requested direct comparison. Its scope is a common-controller, common-budget comparison, rather than an equal-time result or causal attribution to distortion.
Weakness 3 and Question 4: What is the coordination cost at a matched time budget?
Thank you for asking for an actual runtime comparison rather than an operation count. We evaluated all 1,319 GSM8K test questions, four randomizations, Qwen2.5-7B-Instruct, K=8, and a 1,024-token cap. The 31,656 requests include fixed-K and genuine deadline-limited trials.
| Method | Fixed-K median latency | Success by the 9.31 s deadline |
|---|---|---|
| IID | 6.39 s | 96.38% |
| PBD4 | 6.40 s | 96.38% |
| Full PBD | 6.74 s | 96.10% |
PBD4's median is approximately 0.2% above IID, calculated before rounding, and both have the same observed deadline-success estimate. Their paired difference is 0.00 points, adjusted 98.33% interval [−0.53, 0.55]. The full-PBD timed difference is −0.28 points, nominal 95% interval [−0.70, 0.13]. These quantify the tradeoff directly; observed closeness does not establish superiority or formal equivalence.
The deadline was fixed from training-only timing. Methods share model/cache paths and instrumentation in matched execution blocks. An output must finish or reach the cap, satisfy the frozen final-line parser, and be available before the deadline. Randomizations are averaged within question before paired question-cluster resampling. The measurements cover complete-request cost, not isolated grouping or synchronization components.
Section 5.3 (pp. 9–10) and Appendix F.3, Tables 22–23 (p. 29), report these results. Combined with PBD4's 99.3% gain retention in the separate multi-phrase workload, they make the shallow-coordination case concrete. We respectfully ask you to reconsider your assessment in light of the positive semantic extension, corrected paired comparison, explicit decision example, and measured cost–benefit profile.
Thank you for your time and effort.
Weakness 1 and Question 1, decision consequences
Thank you for recognizing that Theorems 1–2 go beyond classical one-step balancing and that the controlled paired evaluation is informative. We answer Questions 1–4 in your order, naming the overlapping weaknesses explicitly. This comment addresses Q1; the next covers Q2 and the remainder of Weakness 2; the final comment covers Q3 and Q4.
Weakness 1 and Question 1: Do the measured conditional distortions change a decision?
Thank you for asking us to connect conditional fidelity to an actual decision. We have added a controlled equal-budget example in which the conditional interface changes the appropriate selection and its success probability. For the unchanged consumer, success increases from 1/4 under endpoint coupling to 1/3 under PBD.
Let P(A0,A1,B0,B1)=(1/4,1/2,1/16,3/16), with success {A0,B0}. Two lanes reveal their first tokens, and one is retained for its last token. The base selector prefers A, with success probability 1/3, to B, with probability 1/4. Every policy spends three transitions.
The endpoint lattice S and (S+1/2) mod 1, with S uniform, has the same observed-history probabilities as PBD: AA, AB, and BA occur with probabilities 1/2, 1/4, and 1/4. In mixed endpoint histories, the A lane's actual success probability is zero. The unchanged selector consequently achieves 1/4, whereas PBD preserves the retained A lane's conditional success probability of 1/3. A selector that explicitly recalibrates instead chooses B on mixed histories and achieves 3/8. The example therefore shows both the consequence of reusing the unchanged conditionals and the valid endpoint-aware alternative.
We distinguish this controlled mechanism from its prevalence in the measured population. The short-label mean TV is 0.00236, and the oracle-selected calibration gap is 0.00143; those measurements do not themselves isolate a consequential real-query decision change. The prespecified 0.01 criterion applies to mean TV, not to a separately specified calibration-gap criterion.
Section 2 (p. 3) now states the consumer, and Appendix F.1, Table 19 (p. 27), provides the calculation. Section 5.1 (p. 8) and Appendix D.4 (pp. 24–25) separate fidelity measurements from decision regret. Our Q3 reply adds the complementary real-query utility comparison under a common controller, without attributing its difference to distortion alone. Together, these additions make the motivation concrete while keeping the decision mechanism and empirical comparison distinct.