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

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$\times$ (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.