TL;DR
PRQ-KMeans introduces a novel post-hoc hierarchical tokenizer for generating Semantic IDs (SIDs) used in generative retrieval and recommendation systems. By replacing standard full-vector centroid subtraction with an orthogonal projection residual, it completely eliminates "residual carryover" across hierarchy levels. This simple geometric fix, combined with global component removal and soft centroid refinement, leads to significantly better codebook utilization and state-of-the-art retrieval performance.
What Problem Does This Paper Address?
Generative retrieval and recommendation models represent items or documents using Semantic IDs (SIDs)—hierarchical sequences of discrete tokens (e.g., mapping a specific shoe to a category sequence like [Sports -> Running -> Nike]). Standard tokenizers typically use a framework called residual quantization (like RQ-KMeans) to build these hierarchies level-by-level: they pick a cluster centroid for the current token, subtract it from the item's vector representation, and pass the remaining "residual" vector to the next level to determine the next token.
The authors identify three major flaws in how standard tokenizers handle this process:
- Global Background Noise: A corpus-wide shared component often dominates the initial embeddings, wasting the capacity of the first-level codebook on background noise rather than meaningful distinctions between items.
- Hard Assignment Boundaries: Standard K-Means updates only the single closest centroid during training, completely ignoring graded similarities to nearby clusters.
- Residual Carryover: Geometrically, subtracting a full centroid vector from an item embedding does not perfectly remove that cluster's directional component for every individual item. This leaves a "carryover" component along the selected centroid's direction, forcing subsequent levels to waste capacity re-learning information from previous levels.
Methods
PRQ-KMeans addresses these challenges through three sequential operations that enforce progressive commonality removal from a global to local scale:
- Global Component Removal: Before any quantization happens, the model computes the global mean of all input embeddings and removes each item's projection onto this mean, stripping away corpus-wide background noise.
- Top-$k$ Soft Centroid Refinement: During codebook fitting, item embeddings contribute to the updates of their top-$k$ nearest centroids in proportion to their cosine similarity, smoothing out cluster boundaries and improving centroid estimation.
- Projection Residual: Instead of subtracting the full centroid vector ($r - c$), PRQ-KMeans projects the current residual onto the selected centroid and subtracts only that projection component. This guarantees that the next-level residual is strictly orthogonal to the selected centroid, completely eliminating residual carryover.
Datasets
The authors evaluated their approach across both large-scale industrial and public benchmarks:
- Industrial Dataset (KuaiSearch): A massive e-commerce search dataset from Kuaishou containing ~7.8 million items and 9.0 million training-query records. Evaluation was performed on separate, real-world
OrderandClicktest sets. - Public Benchmarks: Four widely used recommendation datasets from the Amazon review corpus (Sports, Toys, Clothing) and LastFM.
Key Insights and Ideas
- The Orthogonality Guarantee: Traditional residual quantization assumes subtraction removes a feature. However, because items within a cluster vary, full subtraction leaves a positive or negative "shadow" (carryover) along that feature's axis. Forcing strict orthogonality via projection ensures later codebooks focus entirely on new orthogonal variations.
- Wasted Capacity Quantified: The authors empirically show that standard RQ-KMeans residuals have a carryover ratio higher than random chance (9.89% at the first level). By artificially tuning and reducing this carryover, they demonstrate that prefix utilization at the next level increases monotonically—proving that carryover actively harms hierarchy efficiency.
- Post-Hoc Freedom: Variational Autoencoder (VAE)-based tokenizers are constrained by the need to additively reconstruct the original input vector. Post-hoc tokenizers (which operate on frozen, pre-trained embeddings) do not have to reconstruct the input, giving them the freedom to discard components entirely through projection.
Key Results
Industrial Search Performance
PRQ-KMeans achieved substantial improvements over standard RQ-KMeans and generative baselines:
- Order HitRate@50 increased by 7.4% (from 0.2913 to 0.3128).
- Order MRR@50 (Mean Reciprocal Rank) improved by 11.8% (from 0.0644 to 0.0720).
Codebook Quality
The geometric modifications led to a much more balanced and highly utilized codebook hierarchy. Level 2 prefix utilization rose from 47.88% to 57.78%, and the Gini index dropped significantly, indicating that items were distributed much more evenly across available semantic paths rather than clustering into a few overcrowded slots.
Public Benchmarks
PRQ-KMeans achieved the best or tied-best results across all eight evaluation metrics across the four public datasets. The gains were particularly pronounced on the LastFM dataset, where Recall@20 shot up from 0.0115 to 0.0179.
Limitations and Future Work
- Post-Hoc Dependency: PRQ-KMeans is strictly a post-hoc tokenizer. It relies entirely on the quality of pre-computed, frozen embeddings and cannot learn representations end-to-end with the retrieval model.
- Hyperparameter Sensitivity: The optimal neighborhood size ($k$) and softmax concentration ($\beta$) depend heavily on the dataset scale. For instance, the massive industrial dataset required $k=5$, while the smaller public benchmarks performed best with $k=2$.
- Future Directions: The authors suggest that exploring how to integrate projection residuals into end-to-end learnable VAE frameworks or alternative non-additive reconstruction paradigms remains an open and promising challenge.
Summary updated