- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The authors present adaptive beam pruning as an online rate-distortion problem, developing BeamStar to reduce the computational cost of full beam search while maintaining the same output with high probability.
Critical strengths
The paper tackles an important problem, reducing computational effort of beam search, and well cites existing literature on the subject. The theory provided is clear and defensible, although has several areas for improvement as detailed below.
Critical weaknesses
Experiments The experiments are the weakest part of the paper, and could do with substantial expansions. See the questions section below. With the additional page granted for final submission, Figure 2 and Figure 3 are worth summarising and including in the main body too.
Theory
-
Optimality: Equation 6 defines the capability frontier, then the local frontier is shown inline. The theoretical frontier is defined over the entire sequence space, while the estimated frontier depends on which trajectories the decoder actually explores. Discussions around which theoretical guarantees hold needs to be clearer, or analysis performed around the difficulty gap mentioned.
-
Proposition 4: Minimising beam width does not necessarily minimise mutual information. Can you please strengthen the connection and its use in Eq 14.
Smaller points
-
In the abstract: "within 0.5 points (effectively lossless)" -- Please remove the effectively lossless claim.
-
The opening sentence: "Autoregressive language models decode by searching an exponentially large sequence space, and". Many decoding methods dont search! e.g. greedy, top-k, min-p etc, none of these perform search. Please rephrase, e.g. to search-based decoding.
Overall, I believe my points are addressable and thus have recommended a weak acceptance but strongly believe all of the above should be integrated and made clearer before acceptance. The experimental analysis in particular.
Questions for authors
- EDEN is mentioned in the paper, but EDEN also performs pruning (see their Appendix C.2). How does BeamStar compare to this branch-and-bound style pruning?
Would expect to see comparative analysis in the experiments. As EDEN pruning "preserves optimality within the explored search space" (never eliminating potential best-scoring path), it would be good to see some tradeoff plots looking at the number of pruned trajectories in each case versus the probability of losing the best scoring output (e.g. under varying epsilon).
Response to Reviewer zi9w
Thank you for the encouraging assessment and for specific, actionable suggestions, especially the EDEN comparison. We addressed each point; shared results are in the Global Response.
Experiments. We substantially expanded them:
Section 6.2 now summarizes the per-position figures (now Figures 3–4): pruning concentrates at the first semantic code, most later candidates are retained, and frontier estimates vary across requests. Within the ten pages we prioritized the new comparison and budget-control results, so the figures themselves remain in Appendix F.
Theoretical versus explored frontier. Section 5 now states the direction explicitly. The estimate is a minimum over explored candidates, so it upper-bounds the true frontier. The cap can therefore be looser than the exact viable set: it is an estimate, not a membership certificate. We also state which results need the true frontier (Theorem 1, via its margin conditions) and how the difficulty gap enters the margin (Eq. 16).
Proposition 4 and Eq. 14. We agree. Section 5 and Appendix C now claim support-size optimality only: the score cap keeps the fewest beams for its distortion. Beam count upper-bounds the retained information rate, and minimizing the bound does not in general minimize mutual information. Eq. 14 is restated accordingly.
Smaller points. Both done: "effectively lossless" is removed, and the paper now opens with "Search-based decoding".
EDEN comparison and trade-off plot. We implemented EDEN's C.2 pruning component with a greedy incumbent and measured the trade-off you asked for. Figure 6 plots work saved against the rate of losing the full-width best output for every rule (BS, BS_L, two fixed gaps, EDEN), and Table 8 (Appendix G.3) varies EDEN's slack. Appendix G.11 gives the identity accounting, and Appendices G.4 and G.6 repeat the comparison on Beauty and on an interactive pilot.
This contrast helped us sharpen one of the paper's main findings: the top result is robust to pruning, while list recall at wide beams depends on lower-probability candidates.
Thank you again for the constructive review; it shaped the revised experiments directly.