CS Paper Radar

LEGIT: Live Eligibility Gating over Identifier Tries for Constrained Decoding of Heterogeneous Pages

Felix Fang, Zheng Liu, Robert Saliba

cs.IR cs.LGcs.PF ·submitted 2026-11-07 00:41 UTC · v1
hot direction

Abstract

A generative recommender names each candidate with a short token sequence, a Semantic ID, and recommends by generating those tokens. Some generative recommenders, including the Uber Eats search engine we are building, write a whole results page, stores with their menu items, in one decoding pass. Every Semantic ID on such a page must name a real store or item that is eligible for the search, such as a store that delivers to the user's location, and that is not already on the page. Each item must also belong to the store above it. A trie over the catalog keeps identifiers real, but eligibility and repetition change with every request and token, and the grammar-constrained decoder we tried could not enforce these changing rules exactly and quickly. We call this constraint LEGIT, for live eligibility gating over identifier tries. Numbering trie leaves depth first turns each rule into a range lookup over one store trie and one item trie, and every generated page passes an independent catalog check. On one NVIDIA B200 GPU with one or two requests per decode step, a direct implementation that walks the trie on the GPU makes each token about 5 times as slow as unconstrained decoding. Across 36 implementations, hardware counters and ablations are consistent with kernel launches and CPU-GPU waits as the source of this slowdown. Our fastest implementation walks the trie on the CPU while the GPU runs the model, needs no custom kernel, and cuts time per output token by 65.9 percent against the direct GPU implementation, to about 1.7 times the unconstrained cost. This implementation is also the fastest on a page layout that puts each item before its store.

Comment
22 pages, 11 figures, 18 tables. Under review

Closest papers

Nearest neighbours by meaning across the whole index.

From Interests to Semantic IDs: Retrieval-Grounded Credit Assignment for Generative Recommendation

cs.IR cs.AI ·2026-09-24 ·Mengdan Zhu, Yufan Zhao, Yao Zhao, Sophie Di, Tao Di +3 more
similarity 0.66
Abstract

Semantic IDs (SIDs) encode each catalog item as a short token sequence, enabling generative recommenders to predict the next item autoregressively. Reasoning-enhanced variants, an increasingly common extension, first generate a textual trace and then decode a next-item SID by beam search. Such recommenders are commonly trained with group-relative policy optimization under an exact-match SID reward, which is sparse in large catalogs. Two failure modes follow. When all rollouts in a group miss the target, the group yields zero advantage and no learning signal. Rollouts sharing the same SID reward receive identical advantages, however much their traces differ. In both cases the reward reflects only the decoded SID, never the reasoning that produced it. This creates a credit-assignment gap. We address this gap with retrieval-grounded query attribution. Each trace is structured into a history summary, a set of interest hypotheses, and a final SID. A frozen retriever executes every hypothesis as a catalog query, so that each hypothesis becomes independently verifiable rather than judged only through the final SID. A rollout is rewarded when any of its queries retrieves the target within the \mbox{top-$K$}, and per-query hit indicators localize that reward to individual hypotheses. Credit is thus assigned at the span level: only hypotheses that individually hit receive positive retrieval advantage, while the retrieval channel never updates the final SID span. Rollouts that share a SID reward can therefore receive different updates. Across experiments on three Amazon Reviews datasets, this yields consistent improvements in SID recommendation. On Video Games, an oracle analysis further reveals the potential of interest-conditioned SID decoding: selecting the target-relevant query among generated interests improves both recall and ranking.

0.11

Generative Retrieval under Real-Time Supply Constraints in Local Commerce

cs.IR ·2026-11-04 ·Shaopeng Liang, Biao Zhang, Hongzhen Ye, Zeyang Hou, Ma Jiang +6 more
hot direction similarity 0.64
Abstract · 11 pages, 3 figures, 6 tables, 2 algorithms. The first five authors contributed equally. Revised supply-stage discussion and filtering table…

Generative retrieval predicts semantic identifiers for candidate entities. In local retail and food delivery, candidates must also be serviceable for a particular user at a particular time. Location, weather, and traffic reshape merchant and product supply, so a catalog-valid identifier may be infeasible for the current request. Post-generation filtering removes such candidates only after beam capacity and inference computation have been spent. We study retrieval over an explicitly materialized, request-time supply snapshot, where short output sequences leave little opportunity to amortize online constraint preparation. Our RTP-LLM pipeline compiles eligible residual-quantization identifiers into a compressed sparse row prefix index, overlaps CPU compilation with model prefill, and shares the uploaded index across beams. Legal expansions retain original-model log probabilities, and constraint states follow selected beam parents. We formalize snapshot-relative identifier validity and distinguish it from entity-level eligibility and freshness. The implementation generates three-token merchant identifiers. Historical evidence covers T+1 daily-refresh catalog constraints and subsequent request-scoped serving evaluations. In one matched-beam daily-constraint case, filtered merchants decrease from 170 of 299 candidates to 29 of 299; residual distance filtering motivates request-specific constraints. A different-host comparison with 30,000 supplied entries reports a 0.6 ms service-side latency increment, while client measurements expose additional request costs. Captured requests from three geographic settings characterize behavior across supply sizes and output widths. These observations span development stages and measurement boundaries. They establish a practical implementation and identify bottlenecks, but do not establish compute savings at matched retrieval quality.

0.37

Evolving Semantic Indexes for Generative Retrieval

cs.AI cs.IRcs.LG ·2026-10-20 ·Jinming Nian, Jyun-Yu Jiang, Henry Tsai, Yi Fang, Zhirong Liang
similarity 0.63
Abstract

Generative retrieval (GR) casts search and recommendation as autoregressive generation of discrete semantic identifiers (SIDs). SID design largely determines GR quality, but its discrete, interdependent components (SID construction, collision handling, decoding, and training) cannot be optimized end-to-end with gradients and remain largely hand-designed. We introduce a framework that improves these components through LLM-driven evolutionary program search, to our knowledge the first application of this approach to GR. A locally served, open-weight 31B model mutates executable GR components, so no proprietary LLM API is used, and a 1M-parameter proxy decoder provides fast feedback in place of repeatedly training the 1B target generator. Across 21 SID programs on NQ320K, proxy and target Recall@100 show strong rank correlation (Spearman $ρ= 0.90$). Guided by this proxy, evolution improves the seed GR on NQ320K, MSMARCO300K, and a multilingual e-commerce dataset under a fixed training recipe. On NQ320K, jointly evolving SID construction and collision handling improves Recall@1 from 55.8% to 59.3% and Recall@100 from 85.8% to 90.6%. A component study shows that proxy reliability depends on what is evolved: improvements transfer reliably for the semantic index but not for the generator's training objective or the full pipeline. LLM-driven evolutionary search is thus a practical tool for GR design, provided proxy reliability is established for the chosen search space.

0.22

Separating Thinking from Spelling for Efficient Generative Recommendation

cs.IR ·2026-10-23 ·Danil Gusak, Anna Volodkevich, Ivan Oseledets, Evgeny Frolov
similarity 0.61
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

SPAR: Stepwise Personalized Autoregressive Recommendation with Prefix-Balanced Semantic IDs

cs.IR ·2026-10-20 ·Chunrui Zhang, Gaoyun Lin, Chang Zhou, Zheng Hu, Qiran Song +2 more
similarity 0.61
Abstract

Semantic ID (SID)-based generative recommendation retrieves items through successive token-level decisions, making personalization at each decoding step essential. However, existing methods insufficiently account for prefix-dependent user evidence and imbalanced historical interaction loads among candidate branches. This can cause irreversible branch-selection errors and favor popular paths. We propose SPAR, a generative recommendation framework that jointly improves stepwise personalization and SID construction. Its PATH Decoder retrieves prefix-relevant evidence from compressed long-term user memories and combines it with recent behavior, user profiles, and event context to guide each token decision. Its RQ-PIB module balances historical interaction loads among sibling branches under each parent prefix while preserving semantic structure. Experiments on large-scale Youku production data show an average relative HitRate improvement of 2.66% over the strongest baseline. SPAR also increases target-prefix retention by 5.79 percentage points and reduces the traffic-weighted largest child-branch share by 32.84% across SID levels. In a 7-day online A/B test, SPAR serves 10% of Youku's production traffic and improves average watch time per user by 3.95% and play conversion rate by 3.38%. These results demonstrate more reliable hierarchical decoding, balanced SID branches, and improved user engagement in industrial recommendation.

0.29

Query-Aware Source-Risk Triage for Retrieval-Augmented Generation

cs.AI ·2026-09-15 ·Kainan Zhou, Gangzhen Qian, Chuhong Xu, Lu Yi
published similarity 0.61
Abstract · 6 pages, 6 figures, 5 tables. Accepted at CAIT 2026

Retrieval-augmented generation (RAG) pipelines may omit a source's material relationship to the query. We study a pre-generation triage layer that treats this relationship as query dependent. The method routes canonical query families for enhanced review and assigns retrieved pages to pass, contextualize, exclude, or review. It combines a four-dimension page score, rank-discounted family aggregation, intent-preserving query mutations, and a family-held-out router. A single-coded pilot of 200 real URLs supplies provisional calibration anchors; a 20,000-row scenario with synthetic domain identifiers supports controlled workload analysis. An oracle page gate defines a risk-coverage target for a future learned classifier. The evaluation shows why page-level frequency cannot substitute for family-level exposure and quantifies how calibration changes scenario activation. Annotation reliability remains unmeasured, and synthetic rankings omit real retrieval dynamics. The result is an auditable triage method and validation plan, not an estimate of deployed review workload, live-Web prevalence, or downstream answer-quality gains.

0.26

Autoresearch for Marketplace Catalogs: From Legacy Forms to AI-Native Matching

cs.AI ·2026-08-31 ·Kartik Ravisankar, Hojat Abdolanezhad, Daniel Capo, Sang Su Lee, Shishir Dash +1 more
similarity 0.61
Abstract

Two-sided service marketplaces are moving from deterministic request-form intake to AI-native probabilistic matching, enabled by large language models (LLMs) that infer intent, preferences, and latent constraints from natural language. Relying on inferred intent rather than fixed-form fields forces these platforms to regenerate the provider-side preference taxonomy underwriting matching, search, and pricing: attributes interpretable to service providers while remaining a useful signal for marketplace decisions. We present an autoresearch loop that generates this taxonomy, one occupation at a time, and has been deployed in production at a major U.S. consumer services marketplace since April 2026, spanning 132 occupations. Instead of one global hierarchy, the loop treats each occupation as an independent generation problem and runs iterative propose-evaluate-keep refinement cycles. Each candidate tag set is scored by a recalibrated six-rubric LLM-as-judge framework, and a 7-critic panel of distinct personas contributes weighted penalties to an adjusted score, with no hard vetoes. A separate parity-mapping stage maps legacy request-form Q&A pairs back to the generated taxonomy, yielding both a coverage signal and an interface for human quality assurance; it does so by first inferring the provider attribute each legacy question was meant to measure, rather than translating questions to tags literally.

0.13

Do GEO Gains Survive the Live Web? Evaluating In-the-Wild Visibility Gains of Generative Engine Optimization via LIVE-GEO

cs.IR ·2026-10-31 ·Runze Kong, Haibo Jin, Xucheng Yu, Xiaoqi Wang, Huimin Zeng +1 more
benchmark similarity 0.60
Abstract · 12 pages, 5 figures, 8 tables

Generative engine optimization (GEO) rewrites web content so that LLM-based search systems, also termed generative engines (GEs), rank it higher in their answers and recommendations. However, existing GEO evaluations typically rely on directly supplied text or controlled retrieval pipelines, and whether GEO gains survive the live Web remains unclear, leaving a gap in understanding how GEO strategies affect the visibility of live webpages when accessed and ranked by GEs. To address this gap, we introduce LIVE-GEO, a benchmark for Live, In-the-wild Visibility Evaluation for GEO. LIVE-GEO publishes GEO-rewritten products as live webpages. We use LIVE-GEO to evaluate five existing GEO strategies (CORE, C-SEO, E-GEO, AgenticGEO, and Statistics Addition), applying them to the product descriptions and reviews of 80 fictional brands across 18 product families. We run experiments on three GEs (ChatGPT with GPT-6, Gemini 3.6 Thinking, and Grok in Expert mode), four direct-text API evaluators (GPT-4o, DeepSeek, Kimi, and Claude), and a direct-text local evaluator (Qwen2.5-3B-Instruct). With frozen $\pm0.2\%$ prices, most direct-text evaluators and GEs receiving product URLs give CORE the highest Top-1 rate, reaching 66.3%-76.3% on the GEs, yet other strategies vary in relative performance, and the GEs select the same top product for only 48.8%-66.3% of brands. We also find that ChatGPT is sensitive to the order of candidate URLs: CORE's Top-1 rate is 73.8% and 93.8% under two opposite fixed orders, and the randomized order used by LIVE-GEO yields 82.5%, between the two. In the numerical-faithfulness check, the JEV verifier agrees with the reference labels on 90.7% of 194 numerical benchmark cases and with human judgments on all 50 sampled descriptions, and it flags 86 of the 400 rewritten descriptions, including all 80 Statistics Addition descriptions.

0.48