acceptodds
Under review as a conference paper at ICLR 2027

BeamStar : Rate-Distortion Optimal Beam Search on the Low-Surprise Viable Manifold

Abstract

Beam search is the standard decoding algorithm when exact, high-probability outputs matter, such as in machine translation, speech, code, and increasingly generative recommendation, where serving pipelines maintain large beam widths under strict latency budgets. Yet beam search is fundamentally wasteful: at every step most expanded hypotheses accumulate low cumulative log-probability and are eventually discarded, while still consuming GPU compute, KV-cache bandwidth, and synchronization overhead. We argue that this waste is structural. Good decoding trajectories concentrate on an exponentially small viable set of high-probability paths whose per-token surprise rate stays within of the model's capability frontier. We characterize this set (its cardinality, volume, and probability mass) and locate it among existing typicality notions: it is provably disjoint from the Shannon typical set for peaked models and coincides with the locally typical set along low-entropy corridors, making it the search-side counterpart of typicality-based sampling. We then frame adaptive beam pruning as an online rate-distortion problem: the retained beam count controls the information rate, and the pruning distortion is the KL divergence between the original and filtered decoding distributions, which admits a closed form under renormalization, namely the negative log of the retained probability mass, computable online at no extra cost. This exposes a practical control signal: at each step all beams are scored on the same cumulative-log-probability distribution, so its running maximum and spread alone suffice to place the pruning threshold. BeamStar prunes beams to track an online estimate of the capability frontier while accounting its distortion online; we prove the full-width beam output survives pruning with high probability, so returned quality is never silently degraded, and that the distortion budget bounds recall loss. On generative recommendation with OpenOneRec-1.7B and 8B-Pro, BeamStar speeds up decoding by 1.16–1.89 (cutting time per sample by 14–47%), the gain growing with beam width, while its global variant matches pass@1, pass@32, and recall@32 to within 0.5 points (effectively lossless), and it composes with standard serving optimizations.

Primary area:
foundation or frontier models, including LLMs
Keywords:
beam search, decoding, large language models, rate-distortion theory, inference efficiency, generative recommendation, typical set, information theory, adaptive computation, autoregressive models

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_zi9wOpenReview ↗
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).

1 comment
AuthorsOpenReview ↗

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:

  • calibrated fixed-gap baselines with the begin token supplied in every arm (Tables 4 and 16);
  • frozen transfer to wider beams;
  • a second recommender (T5 on Amazon Beauty);
  • the EDEN comparison you suggested;
  • batched-serving measurements;
  • a new online distortion-budget controller (Section 6.2, Table 2).

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.

  • Best output: the bound behaves as designed for its objective. Crediting the greedy incumbent, the best output is preserved in all but 2 of 997 analyzable requests.
  • List quality: the objectives differ. On 1,000 video requests, zero slack saves 46% of beam-forward work but lowers pass@32 by 8.1 points, because a bound that protects the single best output does not protect a useful 32-item list. Larger slack (0 / 0.5 / 2) recovers 73 / 85 / 118 successes against 142 at full width, at work 56 / 61 / 72 against 97.

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.

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

Paper Summary

In one sentence: BeamStar speeds up beam search by dropping, at each step, the candidates that score far below the best one. On two recommendation models it cuts decoding time by 14–47%, with almost no loss in quality.

Problem:

Some recommender systems use a language model to write out the ID of the item to recommend, one token at a time (generative recommendation). In the OpenOneRec models used here, each item ID has 5 tokens: a begin marker, three codes, and an end marker. To return a list of 32 items, the system runs beam search: at every step it extends each partial ID by one token and keeps only the 32 best results (beams). The 32 left after the last step are the list.

The problem is wasted work. Beam search always keeps exactly 32 beams, even when most of them are almost certainly useless, and every beam costs GPU time at every step. Running example:

  • Step 1: only one token (the begin marker) is allowed, but beam search still fills all 32 slots, so 31 are wasted (§F.2).
  • Step 2: say (made-up numbers) a few codes have probability 1/2, 1/4 and 1/8, and many have about 1/1024. The unlikely ones are 512 times less likely than the best, but they still take slots.

Goal:

Keep fewer beams, and so run faster, without lowering quality compared with full-width beam search. Quality is measured against the items users actually chose: pass@1 (is the top item correct?), pass@32 (is any of the 32 correct?) and recall@32 (what share of the correct items are in the list?).

Method:

After each normal beam-search step, BeamStar also drops the candidates that are much less likely than the best one, so it can keep fewer than 32 beams. On the paper's data it keeps about 20 of 32 on average. There are two versions: BSL decides what counts as "much less likely" from the current request alone, with nothing to tune, while BS decides from all requests seen so far, with one hand-tuned setting. The paper also gives a rate–distortion view and a survival theorem, but neither one sets the rule that is actually run.

Results:

  • BeamStar cuts the time per request by 14–47% across six settings (two models, two tasks, beam widths 32 to 512). The wider the beam, the bigger the saving.
  • BS gives almost the same quality as normal beam search: every score is within 0.5 points.
  • BSL keeps the top recommendation just as good, but the scores for the full 32-item list drop by up to about 5 points.

Difference between this paper and the closest baseline:

The closest baseline is score-gap pruning from "Beam Search Strategies for Neural Machine Translation" (Freitag & Al-Onaizan, 2017, arXiv:1702.01806). It already lets the number of beams change at each step, by dropping candidates that score more than a fixed amount below the best one, and it reports up to 43% faster decoding. BeamStar uses the same idea, but sets the amount from the spread of scores instead of fixing it. The paper cites this work but never compares against it, so it is unclear what BeamStar adds.

Critical strengths

Critical Strengths*

S1: The method is simple and gives real speedups (Table 1). It plugs into vLLM by replacing its beam-search loop, and it needs no extra model calls.

Why it matters: Wide beam search is a real cost when serving generative recommenders. A speedup that needs no training and, for BS, loses almost no quality is useful in practice.

Critical weaknesses

Critical Weaknesses*

W1: BeamStar is not compared with existing speedup methods, so we cannot tell what it adds.

At each step, BeamStar drops candidates that score more than some gap below the best one. That is score-gap pruning; BeamStar only changes how the gap is set. The paper says its rule differs because it divides scores by length, but here every item ID has the same length (footnote 1), so the two rules are the same. Missing baselines:

  • score-gap pruning (Freitag & Al-Onaizan, 2017) with a tuned fixed gap;
  • AtSpeed (Lin et al., 2025, arXiv:2410.05165): speculative decoding built for top-K beam search in generative recommendation;
  • NEZHA (Wang et al., 2025, arXiv:2511.18793): a built-in draft head plus a lookup of valid item IDs, aimed at wide beams over semantic IDs.

Why it matters: Without these, we cannot tell whether BeamStar is faster or better than the methods that already exist.

W2: The theory does not match the method that is run.

  • Theorem 1 needs a specific margin. BS uses a different one, with a factor tuned per task (2 or 2.2, E.4). BSL copies its shape but uses fixed constants. The paper also never checks how often the normal beam search output survives pruning.
  • The theorem holds "with probability 1 − δ", but beam search is deterministic (E.6). It is unclear what is random.
  • The "distortion" is only logged. It does not affect what gets pruned (E.4).
  • Props. 1–4 follow almost directly from the definitions. Prop. 4 (I ≤ H ≤ log|B|) is a textbook bound.

Why it matters: The theory is three of the paper's four listed contributions. If it neither sets nor guarantees the rule that is run, what is left is a simple pruning rule.

W3: The experiments are too narrow for the paper's broad claims.

The abstract frames beam search as a general problem (translation, speech, code, recommendation) and says BeamStar "composes with standard serving optimizations." But all speed and quality results come from one table (Table 1): two tasks from one benchmark (RecIF-Bench), one model family (OpenOneRec), and wide beams (128, 512) on only one model and task. Timing is at batch size 1 (E.5), so batched throughput is never measured; the paper leaves this to future work (H.4). Needed:

  • throughput under batched serving in vLLM, not only single-request latency;
  • a second generative recommender, e.g. on Amazon Beauty, Sports and Toys (used since TIGER, Rajput et al., NeurIPS 2023).

Why it matters: The speedup may come from this one model and benchmark, or vanish once requests are batched.

Questions for authors

Questions For Authors*

See weaknesses.

1 comment
AuthorsOpenReview ↗

Response to Reviewer wCHY

Thank you for a clear and demanding review. Your summary of the method is accurate, and your three weaknesses defined our revision plan. Shared numbers are in the Global Response.

W1. Comparison with score-gap pruning and other speedup methods.

We agree that at a fixed step, with equal lengths, the surprise-rate cap is a cumulative-score gap. Related Work and Section 5 now say so: our contribution is the analysis and the data-dependent margin, not a new ranking rule. We added calibrated fixed-gap baselines everywhere (Tables 4 and 16, Appendix G.9), with the begin token supplied to every arm:

  • Interactive, k=32: BS and a tuned gap show no significant difference at matched work or speed (BS's best case is +0.65 recall@32 points [−0.05, +1.35], with the sign flipping on calibration). Speedups are 1.13× (BS), 1.23× (BS_L) and 1.27× (gap).
  • Video, k=32: BS (γ=2.2) and gap (β=5) both reach 141/800 successes (full width: 142); the gap saves more work (6.3% vs. 0.7%).
  • Frozen transfer from interactive to video: at k=32, frozen BS (γ=2) stays near full width (−0.2 points [−0.6, +0.2]) while the frozen gap (β=3.5) loses 3.1 points, although BS also prunes less. At wider beams every rule loses list quality; at k=512, pass@32 drops by 8.3 / 2.9 / 1.2 points for BS / BS_L / gap.
  • Beauty (new model and dataset): at validation-matched work, BS (γ=2.4) gives 124 hits versus the gap's 111 on 1,600 fresh users (15 gains, 2 losses; corrected McNemar p=0.007). More aggressive pairs are mixed.

So we now state plainly that neither adaptive nor fixed margins dominate across settings. AtSpeed and NEZHA reduce the cost of each step with a trained draft model or head, while BeamStar is training-free and reduces the number of beams. The two are complementary; we discuss them in Related Work and do not claim a measured combination.

W2. Theory versus the method that is run. Each of your four points is now addressed:

  • Survival: from conditional theory to measurement. Eq. (16) now links the deployed global margin to Theorem 1: it inherits the guarantee whenever it covers the per-request difficulty gap plus the theorem's per-request bound. Whether γ=2 meets this depends on the reference increments' tail parameter σ, the margin constant ε̄ and the per-request gap, which we do not estimate. We therefore measure survival directly: no threshold rule loses the full-width best output in 995–997 analyzable requests (one-sided 95% upper bound ≈0.3%).
  • What is random: decoding is deterministic; the probability ranges over inputs and the trajectory population. This is now stated with Theorem 1.
  • Distortion now controls pruning. A new online budget controller keeps the smallest score-prefix meeting a mass allowance (Section 6.2, Table 2). Small budgets save about 5% of calls at unchanged pass@32, and larger budgets save about 30% at about −2.3 points. At matched work the deployed margin keeps more quality than mass control, which we report as a finding.
  • Props. 1–4: we agree they follow closely from the definitions. The contributions now say so and present them as characterizing the search region, not as new coding results. The title is now "Rate–Distortion Analysis".

W3. Broader experiments and batched serving.

  • Second recommender: a T5 model on Amazon Beauty (Appendix G.4), with results as in W1.

  • Batched serving, three measurements:

    • Same engine, pruning on vs. off, concurrency 16–256 (Appendix G.7): the throughput gain is 30% at concurrency 16 and shrinks to about 1% at 256, where the per-step token budget binds; pass@32 is 0.39 points lower.
    • Against stock vLLM across concurrency 1–256 (Appendix G.8): throughput is 10–32% higher, with pass@32 0.20–1.17 points lower.
    • Begin-appended control, beam 32, concurrency 16 (Appendix G.10): 1.126× throughput, SID hits 15/64 vs. 14/64.

    So pruning raises throughput at low and moderate load, and the gain mostly disappears near saturation. Appendix G.6 adds a scheduler trace showing that pruning reduces work rather than enlarging batches.

  • Claims scoped: the abstract and introduction now present translation, speech and code as motivation only, and we no longer claim composition with other serving optimizations.

Thank you; your review substantially improved the paper's honesty and its experiments.

Reviewer_bVJ6OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes BeamStar, an adaptive beam-pruning method based on a low-surprise "viable set." It develops a rate–distortion interpretation and a conditional survival guarantee. Hypotheses are retained according to an adaptive threshold using either local or pooled cross-request statistics. Experiments on generative recommendation report speedups over fixed-width beam search, with the global variant largely preserving quality and the local variant losing quality on list metrics.

Critical strengths

The method addresses a practical efficiency problem and requires no additional model forward passes. The reported speedups with little quality loss for the global variant are promising.

The distinction between low-surprise search and typical sampling provides useful motivation. The appendix also gives reasonably detailed implementation and evaluation protocols.

Critical weaknesses

The analysis proves optimality in retained beam count but only upper-bounds mutual information, which does not justify the stronger claim in Appendix C. Moreover, Appendix E.4 states that distortion is only logged, not used to control pruning. The connection between the adaptive score threshold and the claimed distortion-constrained optimum remains unclear.

It covers only short semantic-ID decoding in generative recommendation, with single-request timing and no adaptive pruning baseline. A matched-quality comparison with score-gap pruning is particularly important. The reported savings also partly arise at a fixed begin delimiter, raising the question of how much benefit remains when the baseline handles that delimiter directly.

The guarantees are not sufficiently connected to the implementation. The survival theorem relies on unvalidated assumptions, and the deployed margins are not shown to satisfy its requirements. The distortion ledger also normalizes against the candidate pool after top-k truncation, whereas the stated telescoping identity uses the mass before that truncation. Its reference distribution and claimed exactness need clarification.

Questions for authors

Could the authors provide the proposed surprise-gap histogram comparing ancestors of the final output with other candidates? The existing figures do not directly test this hypothesis.

How does BeamStar compare with score-gap pruning at matched quality, after both methods and the fixed-width baseline directly enforce the known begin delimiter?

How sensitive is the global variant to request order and changes in the request mix? Please clarify when its pooled statistics are initialized or reset.

3 comments
AuthorsOpenReview ↗

Response to Reviewer bVJ6

Thank you for a careful review and precise questions. Each one led to a new experiment or a correction; we answer them in order. Shared results are in the Global Response.

W1. Optimality claim and distortion that is only logged.

  • Optimality: 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 we no longer claim mutual-information optimality.
  • Distortion control: we added an online budget controller in which distortion sets the cutoff (Section 6.2, Table 2, Appendix G.12). Small budgets save about 5% of model calls with unchanged pass@32; larger budgets save about 30% at about −2.3 points. At matched work the deployed margin keeps more quality than mass control, which shows that lost mass alone is not a sufficient proxy for list quality.

W2. Score-gap baseline, begin delimiter, scope. See Q2 below for the full comparison. We also added a second recommender (T5 on Amazon Beauty, Appendix G.4) and batched-serving measurements (Appendices G.8 and G.10).

W3. Theory–implementation link and ledger reference.

  • Survival: from conditional theory to measurement. Eq. (16) now links the deployed global margin to Theorem 1: it inherits the guarantee whenever it covers the per-request difficulty gap plus the theorem's per-request bound. Whether γ=2 meets this depends on the reference increments' tail parameter σ, the margin constant ε̄ and the per-request gap, which we do not estimate. We therefore measure survival directly: no threshold rule loses the full-width best output in 995–997 analyzable requests (one-sided 95% upper bound ≈0.3%).
  • Ledger reference: you are right. Corollary 1's telescoping identity is stated for the pre-truncation reference, while the online ledger normalizes each step against the post-top-k candidate pool. The logged value is therefore the mass discarded from that pool, not from the full model. Section 5 and Remark 3 (Appendix H) now separate the two references and give a small example where they differ; every reported ledger value is labeled as within-pool.

Q1. Ancestor surprise-gap histogram. Added as Figure 8, with common bins and axes. Ancestors of returned outputs are clearly closer to the frontier than other candidates. Mean gaps (ancestors / others) at codes 2 and 3 are 2.69 / 3.57 and 3.48 / 6.84 nats for BS, and 2.21 / 3.94 and 2.89 / 8.20 for BS_L. Because ancestry is defined by later survival, we present this as descriptive support for Hypothesis 1, not a causal test.

Q2. Score-gap pruning with the begin delimiter enforced in all arms. With the begin token supplied in every arm, the fixed-width baseline also no longer spends a step on it.

  • Interactive speedups: 1.13× (BS), 1.23× (BS_L) and 1.27× (gap, β=3) against that baseline.
  • Interactive quality: at matched work or speed, BS and gap show no significant difference. BS's best case is +0.65 recall@32 points [−0.05, +1.35] at matched beams on evaluation, and the sign flips on calibration (Table 4, panel A3).
  • Video, k=32: BS (γ=2.2) and gap (β=5) reach the same 141/800 successes (full width: 142); gap saves somewhat more work.
  • Beauty: at matched validation work, BS gives 124 versus 111 hits on 1,600 fresh users (corrected McNemar p=0.007).

We report these as configuration-dependent results (Tables 4, 16; Appendix G.9). Table 1 is kept and labeled as the original generated-begin protocol.

Q3. Request order, mix and resets. The pooled statistics start empty in each serving process and accumulate without forgetting, as now stated in Appendix G.2, which also measures the sensitivity:

  • Request order: canonical, reversed and shuffled orders give 141 / 144 / 141 successes on the same 800 requests.
  • Warmup mix: a long versus a short warmup gives 36 versus 38 successes on the same 200 targets.

The effect is real but small at these sizes. We list a forgetting mechanism as future work.

Thank you again; we believe these additions answer each of your questions directly.

Thank you for the thorough revision, which addresses my concerns about the theoretical claims.

However, despite a positive result at one Beauty operating point, the matched comparisons show no consistent advantage over calibrated fixed-gap pruning. The distortion-budget controller also does not improve on the heuristic margin at matched work (Table 2).

The revisions improve the paper, but the remaining theoretical and empirical contribution is insufficient to change my assessment. I therefore maintain my rating.

Thank you for the follow-up. At matched work, pass@32 for the controller and the heuristic margin is statistically indistinguishable (32.3% vs 32.8%, a difference of 4 requests out of 800), and we do not claim an accuracy or latency gain. The difference is in distortion: at about 78 LLM calls per request, the controller loses 0.13 nats of log-mass per request versus 0.18 for the heuristic margin, and the budget is an explicit, auditable input (it holds on all 230,400 outputs). Small budgets also match full-width quality (33.3% vs 33.1%) with about 5% fewer calls.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.