CS Paper Radar

Where Beam Search Loses Top-Ranked Items:First-Step Coverage in Generative Recommendation

Heng Yao, Hanwei Zhu

cs.IR ·submitted 2026-10-31 16:09 UTC · v1
hot direction

Abstract

Generative recommendation can reproduce a wider beam's ranked output with roughly half the prefix-capacity budget by reallocating retention capacity across semantic-ID positions. We identify a \emph{first-step coverage bottleneck}: across six full-test settings of the TIGER generative recommender spanning three domains and two identifier constructions, every pruned exact top-10 path is first lost at the initial decoding step. An exact-catalog reference isolates search losses and guides a controlled budget intervention. Moving width to the first step raises Search Recall@10 by 0.96--10.90 percentage points at Beam-50's unchanged budget. Across all 77,373 test users with residual-quantized variational autoencoder (RQ-VAE) tokenization, the reallocated schedule reproduces Beam-100's ordered top-10 at nominal budgets of 151 rather than 301, without retraining or changing identifiers or scores. Matched-output timing saves 6.35--6.39\% of decoder latency; profiling identifies the execution costs that limit the translation from reduced search work to runtime savings. Larger-candidate experiments reveal how output size changes retention requirements. These findings make budget placement an actionable serving decision: locate ranking loss, redirect search capacity, and preserve downstream inputs before increasing uniform beam width.

Comment
5 pages, 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Separating Thinking from Spelling for Efficient Generative Recommendation

cs.IR ·2026-10-23 ·Danil Gusak, Anna Volodkevich, Ivan Oseledets, Evgeny Frolov
similarity 0.71
Abstract

Generative recommenders retrieve items by writing their semantic IDs (SIDs) code by code under trie-constrained beam search, an approach now deployed on large web platforms. Standard autoregressive interfaces pay for the SID length K twice: a history of T items enters the backbone as TK code tokens, and every beam-search step runs through the backbone, so returning B candidates costs O(BK) backbone decode tokens per user. The second cost often dominates, and it grows with the backbone, the SID depth and the candidate budget. We introduce Deco (decoding from concepts), which separates reading the history from writing the identifier. The backbone reads each history item as one fused token and condenses the history once into a compact next-item concept; a light KV-cached decoder conditioned on the concept and the generated prefix runs the entire beam search, while the identifiers, the trie and the autoregressive factorization stay unchanged. The decoder approaches full-backbone accuracy with cross-entropy alone, and distillation improves it further. On seven datasets from e-commerce, movies and music streaming, Deco achieves comparable or better accuracy than both a standard generative recommender and the full-backbone teacher with fused inputs, while delivering 3.2-8.6$\times$ their throughput under a 50 ms p95 latency budget in a production-style serving pipeline. Delegating beam search makes larger candidate pools and models practical: Deco generates 1000 candidates faster than its teacher generates 100, and with a 1.5B-parameter LLM backbone, it matches the 69M-parameter teacher's throughput while achieving higher accuracy.

0.19

Beyond Semantic IDs: Finite-Beam Reachability and Continuous-Query Generation in Generative Recommendation

cs.AI ·2026-10-09 ·Yu Sun, Renkai Xiang, Zuodong Xiang, Junwei Zhou, Yike Zhang +4 more
similarity 0.70
Abstract

Generative recommendation (GR) of social media platforms commonly retrieves items by autoregressively decoding discrete Semantic IDs (SIDs) with finite-width beam search. This work examines how this output interface constrains whether held-out targets enter finite returned lists, while distinguishing catalog-wide scoreability from empirical top-K support. We introduce two continuous-query paradigms: CQG-Single generates one retrieval query in a single pass, and CQG-AR autoregressively generates continuous residual updates, retaining step-wise decoding while removing the SID item-token vocabulary, code lookup, and discrete beam expansion. These designs thereby eliminate the SID-specific reachability constraint induced by finite-beam decoding and avoid the technical challenge of aligning a discrete SID vocabulary with the pretrained backbone's vector space. Both methods make every encoded item directly scoreable through dense or approximate-nearest-neighbor retrieval. Under a unified protocol with valid-prefix constrained decoding, CQG-Single exceeds the TIGER-style baseline in all seven runs while using 55.3% as many trainable parameters. CQG-AR remains comparable on ML-1M and is numerically stronger on Beauty and Sports datasets. A controlled depth ablation further shows that additional continuous refinement does not monotonically improve shallow accuracy. These findings motivate decoupling output representation, autoregressive modeling, and retrieval budget when evaluating generative recommendation systems.

0.38

From Item Scores to Semantic Tokens: Test-Time Collaborative Adaptation for Generative Recommendation

cs.IR ·2026-10-23 ·Xiongfeng Shan, Xing Tang, Hanchong Chen, Fuyuan Lyu, Lingjie Li +3 more
similarity 0.69
Abstract

Generative recommenders using semantic identifiers predict items through successive token decisions, but beam search may irreversibly prune promising item paths. This limitation is particularly consequential when a few recent interactions signal an emerging interest while earlier behavior favors established preferences. Yet an independently trained discriminative recommender may rank the same items highly from the same interaction history. Such complementary scores are available at test time, offering a way to adapt a frozen generator without retraining either model. The challenge is to use these scores before pruning: combining completed recommendation lists cannot alter earlier beam decisions, while scores over complete items cannot directly inform choices among semantic prefixes shared by multiple items. We propose \textbf{T}est-Time \textbf{C}ollaborative \textbf{B}eam \textbf{S}earch \textbf{A}daptation (\textbf{TCBSA}), a training-free method that incorporates collaborative information into semantic decoding. TCBSA transforms discriminative score margins into potentials over shared semantic edges and uses a confidence gate to regulate their contributions to cumulative path scores before beam selection. We establish a sufficient condition for target prefix survival under global beam competition and bound score perturbations under low discriminative confidence. Full-catalog experiments show consistent improvements over strong baselines across datasets and different generative and discriminative recommenders. Analyses of emerging interests and decoding behavior demonstrate gains in recommendation accuracy and target path survival, while targeted interventions support the contribution of shared prefix corrections. TCBSA also offers a favorable balance between recommendation accuracy and inference latency compared with simply widening the native beam.

0.17

Keeping the Index Open: The Recommendation-Side Cost of Shared Search and Recommendation

cs.IR cs.LG ·2026-08-25 ·Theodore Rogers, Joe Standerfer, Dmitrii Timoshenko, Haoxue Li, Zuhaib Akhtar +1 more
similarity 0.68
Abstract

A shared search-and-recommendation index must score new items from features alone because search has no exploration slot. In a public log covering both surfaces over one catalog, $38.6\%$ of held-out query-search impressions show an item never previously shown or visited. For user-cold engagements, the feature-based tower serves this demand without measurable loss against $99$ sampled negatives ($0.9595$ Recall@20 versus $0.9510$ warm). A lexical baseline reaches similar parity, while a full-catalog check remains statistically undecided. Dual-encoder retrieval therefore keeps the index \emph{open} to new items, unlike an ID-softmax recommender that requires retraining. We price this openness on recommendation against six sequential baselines, each retrained and tuned through five rounds on corrected targets. A float32 timestamp bug had reordered leave-one-out targets for $19.7\%$ of users. On MovieLens-1M, warm accuracy trails the strongest retrained baseline by $5.2\%$ Recall@20 and $11.4\%$ NDCG@20. On MIND, the gap narrows to $0.8$--$3.6\%$ relative to the five strongest baselines, though the model ranks sixth of seven. Under strict zero-leakage cold-start evaluation, the content tower achieves $0.172 \pm 0.006$ Recall@20, $1.4\times$ the strongest retrained dedicated method ($0.124 \pm 0.007$) and $3\times$ a training-free floor, without cold-specific training. Exact full-softmax training raises Recall@20 by $54\%$ on MIND-small and $6.9\%$ on MovieLens-1M over sampled InfoNCE, but recomputes the full catalog each step and exhausts accelerator memory at $240$K items. Approximate nearest-neighbor search explains none of the remaining gap, serving cost does not regress against ID-softmax retrieval, and a history-window sweep explains half the post-recipe remainder. Exact-quality training at catalog scale remains the open problem.

0.23

Personalized LLM Recommendation with Semantic IDs: Autoregressive Beam Search vs. Multi-Token Prediction

cs.IR cs.AIcs.CLcs.LG ·2026-10-11 ·Sejoon Oh, Fernando Amat Gil, Evan Smothers, Dan Iter, Mark Thornburg +9 more
published similarity 0.67
Abstract · Accepted to NeurIPS 2026 PALM Workshop

Large-scale personalization is shifting from embedding-table retrieval to LLM-based recommenders that generate the Semantic ID (SID) of the item to recommend, where each SID is a short sequence of discrete hierarchical content codes. A single instruction-tuned model can then unify retrieval, content understanding, and language, and recommend brand-new titles from their content alone using SID; then, how should the model generate the SID? Traditionally, models rely on a single language modeling head that generates tokens autoregressively, typically using constrained beam search. In contrast, an emerging body of work explores multi-token prediction (MTP), where dedicated heads predict all tokens in parallel, substantially reducing the decoding latency associated with beam search. We report an industry-scale, apples-to-apples comparison of these two generation paradigms: single-head autoregressive decoding vs. MTP. We introduce a new auxiliary ranking loss, defined over the joint SID score, to train the MTP objective. We evaluate the SID training objectives on both quality and training/inference cost, inside a multi-task LLM that jointly does personalized retrieval, content question-answering (QA), and instruction following over a large streaming-media catalog. Our experiments show single-head beam search consistently beats MTP on most product-critical metrics: ranking and content QA, and trains at roughly 2.6x lower dollar cost on Qwen3-8B scale; MTP wins only on raw inference throughput. Around this finding, we detail an efficient training and inference stack and report end-to-end gains over the previous non-SID baseline equipped with an auxiliary ranking head: +77% item cold-start ranking, +22% content-QA accuracy, +2.8x faster training, with language metric regression traced to SID vocabulary expansion. We address the language regression by reinforcement learning post training.

0.26

Better Rankers, Worse Retrievers: The Hidden Cost of RL Post-Training in Generative Recommendation

cs.IR cs.AI ·2026-11-17 ·Yuheng Chen, Fan Zhang, Yixuan Xu, Chao Yang, Yang Xiang +1 more
similarity 0.66
Abstract

Generative recommenders decode the semantic ID of a user's next item with a language model, and post-training them with reinforcement learning (RL) after supervised fine-tuning (SFT) has become standard practice. The gains are mostly reported on the first ten results, yet in deployment such models hand hundreds of candidates to a downstream ranker or reward model. We show that RL post-training has a hidden cost: it improves accuracy at the top of the list (hit@K for small K) but, on all five datasets we study, lowers the recall of the candidate list (hit@K for K in the hundreds). The model becomes a better ranker and a worse retriever. Controlled experiments trace the loss to the negative advantages that RL assigns to the candidates it samples, the rollout. The root cause is that only one next item is logged per user, so RL treats every other candidate as wrong. Yet these candidates are the model's most plausible alternatives, and often the next items of other users with similar histories. Penalising them pushes down exactly what similar users choose next, and these items drop out of those users' candidate lists. This diagnosis points directly to a remedy: out-of-rollout anchoring, a single additional loss term that preserves the SFT model's ordering of the items outside the rollout. It keeps the gain at the top and restores recall to the SFT level on all five datasets, and it is effective under other RL configurations as well. To our knowledge, this is the first systematic study of this recall loss: we measure it, identify its cause, and show that, once the cause is known, a simple remedy suffices.

0.18

Generative Recommenders Forget the Long Tail: Restoring Memorization in Retrieval and Ranking

cs.IR ·2026-10-21 ·Xu Huang, Jiancan Wu, Hongzheng Qin, Jiawei Feng, Can Ye +3 more
similarity 0.66
Abstract

Generative recommenders replace the retrieve-then-rank cascade with a single model: beam search over semantic item identifiers performs retrieval, and the same likelihood performs ranking. We show that this shared score makes them forget long-tail items twice. In retrieval, beam search keeps identifier prefixes by the probability mass of their subtrees, so tail items are pruned early, and a wider beam admits few more of them. In ranking, the likelihood places tail items below head items even when they are admitted, so expanding retrieval alone brings little or no gain. Both failures reflect missing item-level memorization (i.e., direct recall of which items co-occur), which collaborative filtering provides and shared-prefix generation lacks. To this end, we propose CAPE (Co-occurrence-Aware Pool Expansion), a training-free plug-in that restores memorization at both stages: (i) a memorization channel retrieves co-occurrence-supported tail items outside the beam and scores them with the frozen generator, and (ii) memorization-calibrated ranking fuses the generator likelihood with co-occurrence evidence while keeping the generator's first item. Experiments with two generative backbones on product and music domains show that CAPE significantly improves long-tail accuracy over the backbones and over re-ranking baselines that share its candidates, preserves or improves overall accuracy, and adds a small fraction of the latency.

0.21

History-Conditioned Joint-Prefix Alignment for Generative Recommendation

cs.IR cs.AI ·2026-08-29 ·Hongliang Sun, Lianjie Li, Bolin Zhang, Dianbo Sui, Dianhui Chu +1 more
similarity 0.66
Abstract

Generative recommendation retrieves items by autoregressively generating semantic identifiers, but beam search may discard a target before its complete identifier is generated. Our preliminary analysis across three benchmarks shows that most missed targets are pruned within the first two decoding steps, highlighting the importance of early prefix retention. However, retaining a target's first-token branch alone is insufficient if its continuation is pruned at the next step: aligning only the first-token distribution improves first-token survival but yields little gain in complete-path retention. This observation motivates joint supervision of early branches and their continuations. We propose Prefix Alignment with Temporal History (PATH), which aggregates transition statistics from the training corpus over recent interactions with exponential decay to construct history-conditioned two-token prefix targets. PATH aligns the model's joint predictions with these targets through forward KL divergence, using a chain-rule decomposition that enables unbiased Monte Carlo estimation. At inference time, PATH reuses the transition statistics for pointwise mutual information (PMI) calibration, reranking completed candidates relative to global prefix frequency. Experiments on Beauty, Instruments, and Yelp demonstrate the effectiveness of PATH, showing consistent improvements in recommendation performance and higher full-SID survival rates.

0.42