Semantic ID-based recommendation models tokenize each item into a small number of discrete tokens that preserve specific semantics, leading to better performance, scalability, and memory efficiency. While recent models adopt a generative approach, they often suffer from inefficient inference due to the reliance on resource-intensive beam search and multiple forward passes through the neural sequence model. As a result, the length of semantic IDs is typically restricted (e.g., to just 4 tokens), limiting their expressiveness. To address these challenges, we propose RPG, a lightweight framework for semantic ID-based recommendation. The key idea is to produce unordered, long semantic IDs, allowing the model to predict all tokens in parallel. We train the model to predict each token independently using a multi-token prediction loss, directly integrating semantics into the learning objective. During inference, we construct a graph connecting similar semantic IDs and guide decoding to avoid generating invalid IDs. Experiments show that scaling up semantic ID length to 64 enables RPG to outperform generative baselines by an average of 12.6% on the NDCG@10, while also improving inference efficiency. Code is available at: https://github.com/facebookresearch/RPG_KDD2025.

1. Bibliographic Information

• Title: Generating Long Semantic IDs in Parallel for Recommendation
• Authors: Yupeng Hou, Jiacheng Li, Ashley Shin, Jinsung Jeon, Abhishek Santhanam, Wei Shao, Kaveh Hassani, Ning Yao, and Julian McAuley.
• Affiliations: The authors are from the University of California, San Diego, and Meta AI. This collaboration between a top academic institution and a leading industrial research lab suggests a blend of rigorous research and practical application.
• Journal/Conference: Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD '25). KDD is a premier, top-tier international conference in the field of data mining and knowledge discovery, making this a high-impact publication venue.
• Publication Year: 2025
• Abstract: The paper addresses a key limitation in semantic ID-based recommendation systems: the inefficiency of generative models. These models typically generate item IDs token-by-token (autoregressively), which is slow and limits the length and expressiveness of the semantic IDs. The authors propose RPG (Recommendation with Parallel semantic ID Generation), a framework that generates all tokens of a long, unordered semantic ID in parallel. RPG is trained with a multi-token prediction loss and uses a novel graph-constrained decoding method during inference to efficiently find valid and relevant items. Experiments show that by enabling longer semantic IDs (up to 64 tokens), RPG outperforms generative baselines by 12.6% on NDCG@10 while being significantly more efficient.
• Original Source Link: /files/papers/68f277d0b34112def177fd80/paper.pdf. This appears to be a link to a locally hosted PDF file from a paper collection, indicating it is likely a formally published conference paper.

2. Executive Summary

• Background & Motivation (Why):

  • Core Problem: Modern recommendation systems are increasingly using semantic IDs—short sequences of tokens that represent an item's meaning—instead of unique numerical IDs. Generative models that create these semantic IDs token-by-token are powerful but suffer from major inference latency. This is because they rely on slow, autoregressive decoding with techniques like beam search, requiring multiple forward passes through a large neural network for a single recommendation.
  • The Gap: This inefficiency forces existing models like TIGER to use very short semantic IDs (e.g., 4 tokens). Short IDs have limited expressiveness; they cannot capture the rich, nuanced features of complex items, thus capping the potential recommendation quality.
  • The Innovation: The paper's core idea is to break the sequential dependency. Instead of generating tokens one by one, RPG generates all tokens of a semantic ID in parallel in a single step. This decouples inference time from ID length, allowing the use of long, expressive semantic IDs (e.g., 64 tokens) without a performance penalty.

• Main Contributions / Findings (What):

  1. RPG Framework: A novel and lightweight framework for recommendation that generates long, unordered semantic IDs in parallel.
  2. Multi-Token Prediction (MTP) Objective: A training objective that teaches the model to predict all tokens of a target item's semantic ID independently and simultaneously, directly embedding sub-item semantics into the learning process.
  3. Graph-Constrained Decoding: An efficient inference algorithm that addresses the challenge of finding valid IDs in a massive search space. It builds a graph of similar items and uses iterative propagation to discover high-quality recommendations, avoiding the pitfalls of naive enumeration or beam search.
  4. State-of-the-Art Performance and Efficiency: RPG is shown to outperform existing generative baselines in recommendation accuracy (by an average of 12.6% on NDCG@10) while being drastically more efficient, reducing runtime memory by up to 25x and inference time by up to 15x.

3. Prerequisite Knowledge & Related Work

• Foundational Concepts:

  • Sequential Recommendation: The task of predicting the next item a user will interact with, given their chronological history of past interactions (e.g., clicks, purchases). Models like SASRec and BERT4Rec are classic examples.
  • Semantic ID: An alternative to representing items with a single, meaningless ID (e.g., $item_12345$). A semantic ID is a sequence of discrete tokens (e.g., $[token_5, token_23, token_55]$) learned from an item's content (text, image). These tokens are shared across items and capture specific semantic facets.
  • Vector Quantization (VQ): A data compression technique that maps continuous vectors (like item feature embeddings) to a finite set of discrete "codebook" vectors. Each item is represented by the index of the closest codebook vector.
  • Product Quantization (PQ): An extension of VQ for high-dimensional vectors. The vector is split into several lower-dimensional sub-vectors, and VQ is applied to each sub-vector independently. The final representation is a concatenation of the codebook indices. This is key to RPG, as the independence of sub-vectors allows for unordered, parallel prediction. The paper uses Optimized Product Quantization (OPQ), which adds a rotation to better balance variance across sub-vectors before quantization.
  • Residual Quantization (RQ): A different VQ technique where quantization is performed sequentially. The vector is first quantized, then the error (residual) from this first step is quantized, and so on. This creates an ordered dependency between tokens, making it suitable for autoregressive models like TIGER but unsuitable for parallel generation.
  • Autoregressive Generation: A generative process where a sequence is produced one element at a time, with each new element conditioned on the previously generated ones. This is common in Large Language Models (LLMs) and generative recommenders like TIGER. It is powerful but inherently sequential and slow.
  • Beam Search: A heuristic search algorithm used during decoding in sequence-generation models. Instead of greedily picking the single best token at each step, it keeps track of the $b$ most probable partial sequences (the "beam") and extends them, pruning the less likely ones. It improves quality over greedy search but increases computational cost.
  • Transformer: A neural network architecture based on self-attention mechanisms, which has become the standard for processing sequential data in NLP and recommendation.

• Previous Works & Differentiation:

  • Retrieval-based Semantic ID Models (e.g., VQ-Rec): These models learn vector representations for semantic IDs and then perform a nearest neighbor search against the entire item catalog to find recommendations.
    • Limitation: Their memory and time complexity scale with the number of items, making them difficult to deploy in systems with massive catalogs.
  • Generative Semantic ID Models (e.g., TIGER, HSTU): These models treat recommendation as a sequence generation task, autoregressively generating the next item's semantic ID token by token.
    • Advantage: Their inference cost is independent of the item catalog size.
    • Limitation: The autoregressive process combined with beam search is very slow, which forces the use of very short semantic IDs (e.g., 4 tokens), limiting their expressiveness.
  • RPG's Differentiation: RPG combines the best of both worlds. Like generative models, its inference cost is independent of the item catalog size. However, by generating tokens in parallel, it avoids the high latency of autoregressive models. This enables the use of long semantic IDs, which the paper shows are more expressive and lead to better performance, a capability previously impractical for generative approaches.

4. Methodology (Core Technology & Implementation)

The RPG framework is composed of three main stages: item representation using long semantic IDs, training via a parallel prediction objective, and inference using graph-constrained decoding.

该图像是论文中图1的示意图，展示了RPG框架的整体流程。左侧描述了训练阶段多token并行预测的结构，右侧展示了推理阶段基于图约束的解码过程，通过图传播避免生成无效ID，实现长语义ID高效生成。

As shown in Figure 1, the training process (left) learns to predict all tokens of an item's semantic ID in parallel. The inference process (right) uses a pre-built graph to efficiently search for the best recommendations.

4.1 Long Semantic ID-based Item Representation (Section 2.1)

1. Semantic ID Construction: Instead of the Residual Quantization (RQ) used by autoregressive models, RPG uses Optimized Product Quantization (OPQ).

   • An item's high-dimensional feature vector (e.g., from a text encoder) is split into $m$ sub-vectors.
   • Each sub-vector is quantized independently, producing a token $c_j$ from a corresponding codebook $C^{(j)}$.
   • The final semantic ID is an unordered tuple of $m$ tokens: $(c_1, c_2, \ldots, c_m)$. The lack of order is critical, as it removes the sequential dependencies that necessitate autoregressive generation. This allows for much longer IDs, with $m$ up to 64.

2. Semantic ID Embedding Aggregation:

   • To feed the item history into the Transformer, each item's semantic ID is converted back into a single vector.
   • Each token $c_j$ in an item's ID is looked up in its corresponding embedding table $E_j$ to get a token embedding $e_{j, c_j}$.
   • These $m$ token embeddings are aggregated (e.g., via mean pooling) into a single item representation $v_i$. $$v_i = \operatorname{Aggr}(e_{1, c_1}, \dots, e_{m, c_m})$$
   • This aggregation step keeps the input sequence length manageable, avoiding efficiency issues that would arise from concatenating all 64 tokens for every item in the history.

4.2 Learning to Generate Semantic IDs in Parallel (Section 2.2)

The core of RPG's training is the Multi-token Prediction (MTP) objective, which trains the model to predict all $m$ tokens of the next item's semantic ID at once.

1. Model Architecture: A Transformer decoder takes the sequence of aggregated item representations $\{v_1, \ldots, v_{t-1}\}$ as input and produces a final sequence representation $s$.

2. MTP Loss: The model predicts the probability of the target item's semantic ID $(c_{t,1}, \ldots, c_{t,m})$ given the history $s$. Due to the independent nature of OPQ tokens, this joint probability is factorized into the product of individual token probabilities: $$\mathbb{P}(c_{t,1}, \ldots, c_{t,m} | s) \approx \prod_{j=1}^{m} \mathbb{P}^{(j)}(c_{t,j} | s)$$ The training loss is the negative log-likelihood of this probability, which simplifies to a sum of standard cross-entropy losses, one for each of the $m$ digits: $$\mathcal { L } = - \sum _ { j = 1 } ^ { m } \log \mathbb { P } ^ { ( j ) } ( c _ { t , j } | s ) = - \sum _ { j = 1 } ^ { m } \log \frac { \exp ( e _ { c _ { t , j } } ^ { \top } \cdot \mathrm { g } _ { j } ( s ) / \tau ) } { \sum _ { c \in C ^ { ( j ) } } \exp ( e _ { c } ^ { \top } \cdot \mathrm { g } _ { j } ( s ) / \tau ) }$$

   • $\mathcal{L}$: The total MTP loss for one prediction.
   • $m$: The length of the semantic ID.
   • $c_{t,j}$: The ground-truth token for the $j$-th digit of the target item.
   • $s$: The user history representation from the Transformer.
   • $g_j(\cdot)$: A dedicated projection head (e.g., an MLP) that maps the general history representation $s$ into a specialized space for predicting the $j$-th token. This is crucial for capturing the distinct semantics of each digit.
   • $e_c$: The embedding for a token $c$.
   • $C^{(j)}$: The codebook of possible tokens for the $j$-th digit.
   • $\tau$: A temperature hyperparameter to control the sharpness of the probability distribution.

3. Efficient Logit Calculation: During inference, the score (logit) for a candidate item with ID $(c_1, \ldots, c_m)$ is the sum of the log-probabilities of its constituent tokens: $$\text{score} = \sum_{j=1}^{m} \log p_{c_j}^{(j)}$$ To compute this efficiently for many candidates, the model first pre-computes the probability distributions $p^{(j)}$ for all $m$ codebooks given the history $s$. This takes $O(Mmd)$ time, where $M$ is the codebook size and $d$ is the embedding dimension. Then, scoring each candidate item only requires $m$ lookups and additions.

4.3 Next Semantic ID Decoding with Graph Constraints (Section 2.3)

A major challenge with parallel generation is the massive search space ($M^m$ possible combinations), where most combinations do not correspond to any real item. The paper proposes a clever graph-based decoding method to navigate this space efficiently.

• Key Observation: Because the final score is a sum of token logits, two semantic IDs that differ in only a few tokens will have very similar scores. This relationship is shown empirically in Figure 2.

  该图像是一个图表，展示了两个语义ID之间不同数字的数量与它们预测的logits绝对差值的关系。随着不同数字数量增加，模型预测的logits差异也逐渐加大。

This plot confirms that as the number of differing digits between two semantic IDs increases, the difference in their predicted scores also tends to increase, justifying the local search approach.

• Decoding Process:

  1. Build Graph (Offline): Before inference, a graph is constructed where each node is a valid semantic ID (an actual item). An edge connects two nodes if their semantic IDs are "similar" (e.g., measured by the dot product of their aggregated embeddings). The graph is sparsified by keeping only the top-$k$ nearest neighbors for each node.
  2. Sample Initial Beam (Online): For a given user history, the process starts by randomly sampling a small set of $b$ valid semantic IDs from the item pool. This set is called the "beam".
  3. Iterative Graph Propagation (Online): This process is repeated for $q$ steps:
     • Propagate: The beam is expanded by adding all neighbors of the current $b$ items from the pre-computed graph, creating a candidate set of up to $b \times k$ semantic IDs.
     • Keep the Best: The score for each candidate ID is calculated using the efficient logit calculation method. The $b$ candidates with the highest scores are kept as the new beam.
  4. Final Recommendations: After $q$ iterations, the semantic IDs in the final beam are returned as the top-$K$ recommendations.

• Complexity: The time complexity is approximately $O(Mmd + bqkm)$, which is independent of the total number of items $N$. This makes RPG highly scalable.

5. Experimental Setup

• Datasets: The experiments use four public datasets from Amazon Reviews, which are standard benchmarks in sequential recommendation. Sports, Beauty, and Toys are moderately sized, while CDs is larger, allowing for scalability assessment.

  (Manual transcription of Table 1)

  Datasets	#Users	#Items	#Interactions	Avg. t
  Sports	18,357	35,598	260,739	8.32
  Beauty	22,363	12,101	176,139	8.87
  Toys	19,412	11,924	148,185	8.63
  CDs	75,258	64,443	1,022,334	14.58

• Evaluation Metrics:

  • Recall@K (R@K):

    1. Conceptual Definition: Measures the hit rate. It is the proportion of cases where the ground-truth next item is found within the top-$K$ recommended items. A value of 1 means a perfect score.
    2. Mathematical Formula: $$\text{Recall}@K = \frac{1}{|\mathcal{U}|} \sum_{u \in \mathcal{U}} \mathbb{I}(g_u \in P_{u,K})$$
    3. Symbol Explanation:
       • $\mathcal{U}$ is the set of users in the test set.
       • $g_u$ is the ground-truth next item for user $u$.
       • $P_{u,K}$ is the set of top-$K$ items recommended to user $u$.
       • $\mathbb{I}(\cdot)$ is the indicator function, which is 1 if the condition is true and 0 otherwise.

  • Normalized Discounted Cumulative Gain@K (NDCG@K):

    1. Conceptual Definition: Measures the quality of the ranking. It rewards models for placing relevant items higher up in the recommendation list. It is a more fine-grained metric than Recall.
    2. Mathematical Formula: $$\text{NDCG}@K = \frac{1}{|\mathcal{U}|} \sum_{u \in \mathcal{U}} \frac{\text{DCG}_u@K}{\text{IDCG}_u@K} \quad \text{where} \quad \text{DCG}_u@K = \sum_{i=1}^K \frac{rel_i}{\log_2(i+1)}$$
    3. Symbol Explanation:
       • $rel_i$ is the relevance of the item at rank $i$. In this setting, it is 1 if the item is the ground-truth item and 0 otherwise.
       • $\log_2(i+1)$ is the discount factor, which penalizes items at lower ranks.
       • IDCG@K (Ideal DCG) is the DCG score of a perfect ranking, used for normalization. For leave-one-out evaluation, IDCG@K is 1 if $K \ge 1$.

• Baselines:

  • Item ID-based: Caser, GRU4Rec, HGN, BERT4Rec, SASRec, FDSA, S3-Rec. These models use traditional unique item IDs.
  • Semantic ID-based: VQ-Rec (retrieval-based), TIGER (autoregressive generative), RecJPQ (retrieval-based), HSTU (autoregressive generative). These serve as the most direct competitors.

6. Results & Analysis

6.1 Core Results

(Manual transcription of Table 2)

• Key Findings: RPG consistently achieves the best or near-best performance across all datasets and metrics. It significantly outperforms the strongest semantic ID-based baseline, TIGER, especially on the NDCG metric, which measures ranking quality. For example, on the Beauty dataset, RPG achieves an NDCG@10 of 0.0464, compared to TIGER's 0.0384—a 20% relative improvement. The paper's claim of a 12.6% average improvement on NDCG@10 is well-supported. This demonstrates that the expressive power of long semantic IDs translates directly into better recommendation quality.

6.2 Inference Efficiency Analysis

![Figure 3: Comparison of runtime memory consumption and inference time w.r.t. the item pool size on the "Sports" dataset.](/files/papers/68f277d0b34112def177fd80/images/3.jpg)
*该图像是图表，展示了在“Sports”数据集上，随着物品池大小（以$\times10^4$计，取对数）变化时，不同模型的运行时内存消耗和推理时间的对比。左图为内存使用量，右图为推理时间。RPG模型在内存和时间上均表现出明显优势。*

• Analysis: This figure is the most striking demonstration of RPG's practical advantage.
  • Memory (a) and Time (b): The costs for retrieval-based models (SASRec, VQ-Rec) grow as the item pool size increases, because they must score every item. In contrast, the costs for generative models (TIGER, RPG) remain flat, as their computation is independent of the item pool size.
  • RPG vs. TIGER: While both are scalable, RPG is in a different league of efficiency. It uses drastically less memory and time than TIGER. This is because TIGER must perform multiple forward passes for its autoregressive beam search, while RPG performs only one. This result validates RPG's core design for efficiency.

6.3 Ablation Study

(Manual transcription of Table 3)

• Analysis:
  • Semantic ID: Replacing OPQ with random tokens causes a massive performance drop, confirming the MTP loss effectively learns from the semantics in the tokens. Using RQ instead of OPQ also degrades performance, suggesting that unordered OPQ tokens are a better fit for the parallel generation paradigm.
  • Projection Heads: Removing the projection heads or using a single shared one hurts performance, confirming the importance of having separate, specialized heads to map the user history to the distinct semantic space of each token digit.
  • Inference Method: This is the most critical ablation. Applying beam search completely fails (0.0000 NDCG), proving it is fundamentally incompatible with unordered, parallel token generation. Removing the graph constraints also leads to a severe performance drop, highlighting that the graph is essential for guiding the search toward valid and relevant semantic IDs.

6.4 Further Analysis

• Scalability of Semantic ID Lengths (Figure 4):

  该图像是包含四个子图的图表，展示了RPG模型在不同语义ID长度（以对数刻度表示）的情况下，针对四个领域（Sports, Beauty, Toys, CDs）的NDCG@10性能表现随长度变化的趋势。

  This plot shows that performance generally improves as the semantic ID length increases from 4 to 16, 32, or even 64. On the largest dataset, CDs, the best performance is achieved with the longest ID (64 tokens). This directly supports the central hypothesis that longer, more expressive IDs lead to better recommendations.

• Expressive Ability Analysis (Table 4): (Manual transcription of Table 4)

  Model	PLM	#digits	Sports	Beauty	Toys	CDs
  TIGER	sentence-t5-base	4	0.0225	0.0384	0.0432	0.0411
  	text-emb-3-large	4	0.0243	0.0411	0.0390	0.0409
  RPG	sentence-t5-base	4	0.0152	0.0292	0.0330	0.0186
  	text-emb-3-large	4	0.0117	0.0235	0.0275	0.0175
  	sentence-t5-base	16 ~ 64	0.0238	0.0429	0.0460	0.0380
  	text-emb-3-large	16 ~ 64	0.0263	0.0464	0.0490	0.0415

  This analysis shows that TIGER, with its short 4-digit ID, does not consistently benefit from a more powerful semantic encoder. In contrast, RPG with long IDs (16-64 digits) sees a significant performance boost when using the stronger text-emb-3-large encoder. This indicates that long semantic IDs are more expressive and have a higher capacity to leverage richer semantic information.

• Cold-Start Recommendation (Figure 5):

  该图像是图表，展示了“Sports”数据集中基于冷启动频次分组的推荐系统在NDCG@10指标上的表现比较。四个分组按测试项在训练集中出现次数划分，横轴为出现区间，纵轴为NDCG@10值，比较了SASRec、VQ-Rec、TIGER和RPG四种方法。

  RPG demonstrates superior performance across all item popularity groups, including the very infrequent items ([0, 5] appearances). This suggests that by learning from sub-item token semantics, the model generalizes better to items it has rarely or never seen, a key advantage for cold-start scenarios.

• Hyperparameter Analysis (Figure 6):

  该图像是论文中图6的图表，展示了模型推理阶段超参数对NDCG@10的影响。图中分别分析了beam size（b）、边的数量（k）和步骤数（q）三个超参数的变化趋势及其对性能的影响。

  This analysis provides practical guidance for deploying RPG.

  • Beam Size (b): A small beam size (e.g., 10) is sufficient.
  • #Edges (k): Performance improves with more neighbors up to around $k=100$, after which returns diminish.
  • #Steps (q): The search converges very quickly, with performance saturating after just 2-3 propagation steps. This further confirms the efficiency of the graph-constrained decoding method.

7. Conclusion & Reflections

• Conclusion Summary: The paper successfully introduces RPG, a novel framework that resolves the critical efficiency-expressiveness trade-off in generative recommendation. By replacing slow autoregressive generation with parallel prediction, RPG enables the use of long, expressive semantic IDs. This is made possible by the MTP training objective and a highly efficient graph-constrained decoding algorithm. The result is a model that is not only more accurate than previous state-of-the-art generative models but also orders of magnitude faster and more memory-efficient.

• Limitations & Future Work: The authors identify aligning RPG with Large Language Models (LLMs) as a promising direction for future work. This could potentially create an efficient LLM-based recommender that leverages the power of long semantic IDs. A limitation not explicitly mentioned might be the offline cost of building the similarity graph, which could be substantial for extremely large and frequently updated item catalogs. The performance is also dependent on the quality of the initial item features and the semantic encoder used.

• Personal Insights & Critique:

  • Novelty: The shift from an autoregressive to a parallel generation paradigm for semantic IDs is a significant and clever conceptual leap. It elegantly sidesteps the primary bottleneck of prior generative models. The graph-constrained decoding is a well-designed solution to the practical problem of searching an exponentially large but sparse space of token combinations.
  • Impact: RPG has the potential to become a new standard for building scalable and high-performance recommendation systems. Its efficiency makes it highly attractive for industrial applications with massive item catalogs and strict latency requirements.
  • Critique and Open Questions:
    • The initial beam is sampled randomly. Could a "smarter" initialization, perhaps based on a simple retrieval model, accelerate convergence or improve final performance?
    • The graph similarity is based on aggregated embeddings. Would a more sophisticated similarity metric that directly considers token overlap lead to a better-structured graph?
    • How would the framework perform in domains where item semantics are less prominent (e.g., movie recommendations based purely on collaborative filtering signals)? The reliance on rich content features might be a boundary condition. Overall, this is a strong paper presenting a well-motivated, technically sound, and empirically validated solution to a significant problem in the field of recommender systems.