PaperlayerView exact revision on arXiv

Source-linked AI summary

Generating Long Semantic IDs in Parallel for Recommendation

Yupeng Hou, Jiacheng Li, Ashley Shin, Jinsung Jeon, Abhishek Santhanam, Wei Shao, Kaveh Hassani, Ning Yao, Julian McAuley

arXiv:2506.05781v1cs.IR

TL;DR

Generative semantic ID recommenders face inefficient multi-step inference, which limits the length and expressiveness of item IDs. RPG uses unordered long IDs with parallel multi-token prediction and graph-constrained decoding; it achieves the best overall performance among compared baselines while improving efficiency.

  • Problem

    Generative semantic ID recommenders rely on costly multi-step decoding, restricting semantic IDs to short sequences despite richer item semantics.

  • Method

    RPG tokenizes items into unordered IDs of up to 64 tokens, trains independent token prediction with a multi-token objective, and uses graph-constrained decoding.

  • Results

    RPG ranks first in 11 of 12 metrics and outperforms the strongest baseline by an average of 12.6% on NDCG@10.

  • Takeaways & Limitations

    Parallel generation enables RPG to use long, expressive semantic IDs while maintaining inference efficiency.

  • Takeaways & Limitations

    The claim that long semantic IDs are more expressive than short ones is treated as an assumption and examined with alternative semantic encoders and lengths.

Abstract

from arXiv · show

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 Introduction

Existing semantic ID-based generative recommenders improve scalability but incur costly multi-step inference, restricting semantic IDs to short sequences. RPG addresses this trade-off by generating long unordered IDs in parallel and guiding decoding with a graph.

  • Semantic IDs replace unique item IDs with shared discrete-token sequences, reducing the need for item-scale embedding tables.Retrieval-based semantic ID models can still require runtime memory proportional to the number of items.
  • Autoregressive generative recommenders require repeated sequence-model forwarding and beam search during multi-step decoding.TIGER generates semantic IDs token by token while maintaining multiple candidate prefixes.
  • 4-token semantic IDs simplify decoding but may not capture rich item semantics, whereas 32-token IDs are impractical for generative beam search.This creates a tension between semantic expressiveness and inference latency.
  • RPG predicts all tokens of the next unordered semantic ID in parallel, making decoding a single step independent of ID length.The framework uses multi-token prediction to train independent token predictions and explicitly incorporate sub-item semantics.
  • RPG uses graph-guided decoding to connect similar semantic IDs and iteratively retain higher-scoring candidates for top-K recommendation.The graph addresses the sparse decoding space created by removing sequential dependencies between tokens.
  • RPG’s inference runtime memory and time complexities are independent of the number of candidate items while supporting expressive long semantic IDs.Experiments across public benchmarks report the best overall performance among compared baselines and greater efficiency than existing generative methods.

2 Method

RPG represents items with unordered semantic IDs of up to 64 tokens and predicts all tokens in parallel using a multi-token prediction objective. It then accelerates inference through cached logits and graph-constrained propagation over valid, similar semantic IDs.

  • Long Semantic ID Construction: RPG uses optimized product quantization to create unordered semantic IDs with up to 64 tokens per item.Each token comes from a different codebook, supporting long representations without sequential dependencies.
  • Long Semantic ID Construction: Item representations aggregate token embeddings for each semantic ID into a single vector before sequence modeling.Mean or max pooling avoids directly concatenating potentially 64 token embeddings into the input sequence.
  • Multi-token Prediction Objective: The multi-token prediction objective factorizes the next semantic ID probability into independent per-position token probabilities.Separate projection heads map the sequence representation to the token space of each codebook.
  • Multi-token Prediction Objective: MTP optimizes target semantic IDs in token space rather than target items in item space, directly incorporating semantic tokens into learning.This differs from item-based cross-entropy while retaining the semantic-token target structure of generative recommendation.
  • Efficient Logit Calculation: Cached token logits reduce candidate scoring complexity from O(Nmd) to O(Mmd+Nm), with the cached approach independent of the number of candidate items in its cache construction.The method first caches sequence-to-token dot products, then scores each candidate semantic ID by looking up its token logits.
  • Graph-Constrained Decoding: Graph-constrained decoding links similar valid semantic IDs and iteratively propagates from an initial beam, retaining candidates with higher prediction scores.Similarity edges are sparsified to the top k per node; decoding examines at most O(bk) nodes per step and has time complexity O(Mmd+bqkm), independent of item count.
  • Inference Efficiency: RPG reduces sequence encoder forward passes from approximately O(bm) to O(1) per input instance compared with TIGER.Parallel token generation makes the number of encoder passes independent of semantic ID length while graph propagation guides valid-ID search.

3 Experiments

The experiments evaluate RPG and multiple item ID-based and semantic ID-based baselines on four Amazon Reviews categories using standard sequential recommendation protocols and metrics.

  • Datasets: Experiments cover Sports, Beauty, Toys, and CDs from the Amazon Reviews dataset, with CDs included as a larger dataset.CDs has approximately four times more interactions than Sports.
  • Data protocol: Users’ historical reviews are chronologically ordered, with leave-last-out evaluation reserving the final item for testing and the penultimate item for validation.Earlier reviews appear first in each input interaction sequence.
  • Baselines: RPG is compared with item ID-based and semantic ID-based recommendation baselines, including Caser, GRU4Rec, HGN, BERT4Rec, SASRec, FDSA, S3-Rec, VQRec, TIGER, RecJPQ, and HSTU.The baselines use convolutional, recurrent, Transformer, feature-processing, quantization, and autoregressive approaches.
  • Evaluation: Performance is evaluated with Recall@K and NDCD@K for K∈{5, 10}, using the best validation checkpoint for test evaluation.The evaluation follows Rajput et al.
  • Implementation: Implemented models are trained for up to 150 steps with batch size 256, tuned learning rates, and early stopping based on validation performance.RPG uses a two-layer Transformer decoder with a parameter count comparable to TIGER and tunes temperature and semantic ID length.

3.2 Overall Performance

RPG achieves the strongest overall recommendation performance while supporting long semantic IDs and efficient inference. Its results also show that semantic tokenization, digit-specific projection heads, and graph-constrained decoding are important design choices.

  • Overall results: RPG ranks first in 11 of 12 metrics and outperforms the strongest baseline by an average of 12.6% on NDCG@10.Across the evaluated datasets, semantic ID-based methods generally outperform traditional item ID-based approaches.
  • Overall results: RPG generates semantic-ID tokens in parallel, enabling semantic IDs with up to 64 digits per item.This design lets RPG use long and expressive semantic IDs while retaining efficient inference.
  • Efficiency analysis: RPG and TIGER maintain constant memory usage and inference time as the item pool expands, unlike SASRec and VQRec.The efficiency analysis varies the Sports item pool from 2 × 10^4 to 50 × 10^4 items and measures runtime memory and clock time.
  • Efficiency analysis: RPG reduces runtime memory consumption by nearly 25× and achieves an inference speedup of almost 15× compared to TIGER.These results preserve generative models’ inference-cost independence from item-pool size while improving efficiency over the generative baseline.
  • Ablation analysis: Replacing OPQ with random tokens or RQ-based semantic IDs reduces performance, especially when tokens have no semantic meaning.The ablation indicates that the multi-token prediction loss benefits from semantics embedded in long semantic IDs.
  • Ablation analysis: Removing the projection head or sharing one across all digits lowers performance, while beam search struggles with OPQ-based IDs lacking sequential dependencies.The results support digit-specific semantic spaces for decoding and the use of RPG’s alternative inference design.

3.5 Further Analysis

Further analysis examines how semantic ID length, encoder strength, cold-start behavior, and decoding hyperparameters affect RPG. Longer IDs improve expressiveness and performance, while modest decoding settings can preserve efficiency.

  • Semantic ID Length: Semantic ID length improves performance generally, with optimal lengths of 16 for Sports, 32 for Beauty, 16 for Toys, and 64 for CDs.Smaller datasets may converge earlier, whereas the largest dataset benefits most from length 64.
  • Expressive Ability: Longer RPG semantic IDs outperform four-digit IDs even with sentence-t5-base, and stronger encoders further improve performance.The comparison evaluates whether long semantic IDs provide expressive capacity beyond encoder quality.
  • Cold-Start Analysis: RPG achieves the best overall cold-start recommendation performance across item-frequency groups.The groups are defined by training occurrences: [0, 5], [6] [10], [11] [15], and [16] [20].
  • Hyperparameter Analysis: Beam sizes above 10 do not significantly improve NDCG@10, suggesting that a relatively small beam is generally sufficient for efficiency.The passage qualifies this recommendation by requiring the beam size to exceed K in the top-K metric.
  • Hyperparameter Analysis: NDCG@10 rises as graph edges per node increase and stabilizes beyond k=100, while iteration benefits saturate after q=2.The graph-decoding analysis varies edge count and propagation iterations independently.

4 Related Work

Related work covers sequential recommendation and semantic ID-based recommendation, including retrieval and generative paradigms. Semantic IDs discretize item features while retaining semantic information for recommendation.

  • Sequential Recommendation: Sequential recommendation models user behavior with methods including Markov Chains, RNNs, CNNs, and Transformers.Semantic IDs have also been used to convert modality features into discrete tokens for sequential recommendation.
  • Semantic ID-Based Recommendation: Semantic IDs are discrete token sequences that jointly index items while retaining some semantics.They can encode text, images, and collaborative signals using quantization, clustering, or joint recommendation-model training.
  • Semantic ID-Based Recommendation: Semantic ID recommendation began primarily with retrieval models and later expanded to generative recommendation.Retrieval methods embed semantic IDs and retrieve those closest to a user representation, while generative models emerged with advances in generative retrieval.

5 Conclusion

RPG predicts semantic ID digits in parallel rather than autoregressively, combining long unordered IDs, multi-token prediction, and graph-constrained decoding. Experiments report strong effectiveness and efficiency.

  • 5 Conclusion: RPG predicts each semantic ID digit in parallel, enabling unordered, long, and expressive semantic IDs.Removing sequential dependence makes ID length independent of the number of decoding steps.
  • 5 Conclusion: RPG uses multi-token prediction to integrate semantics into training and graph-constrained decoding to refine semantic IDs during inference.The graph connects semantically similar IDs and iteratively propagates the maintained beam.
  • 5 Conclusion: RPG is reported to be effective and efficient in memory consumption and inference speed.The paper identifies alignment with LLMs as future work for long semantic IDs.

A Notations

This section summarizes the paper’s notation conventions.

  • A Notations: Table 5 summarizes the notation used throughout the paper.

B Additional Implementation Details

Experiments used a single NVIDIA RTX 3090 GPU, with training and hyperparameter tuning costs varying by dataset scale.

  • All experiments ran on a single NVIDIA RTX 3090 GPU with 24GB of memory.
  • Moderate-scale dataset training took less than 2 GPU hours per fixed hyperparameter setting.
  • The 45-setting hyperparameter sweep required under 90 GPU hours per moderate-scale dataset.
  • Large-scale CD training took under 8 hours per run and about 180 GPU hours across reported checkpoints.

C Additional Discussion

Long semantic IDs degrade TIGER’s performance and inference speed, whereas RPG benefits from longer IDs and outperforms TIGER at each model’s optimal length. RPG uses more total storage but accesses only a small subset during inference.

  • RPG handles long semantic IDs efficiently and benefits from increased ID length in performance.
  • At their optimal semantic ID lengths, RPG consistently outperformed TIGER across all datasets while achieving better inference efficiency.
  • RPG consumes more total storage but typically accesses only 10-25% of items during inference.
Loading 2506.05781v1…