🤖 machine learning

PRQ-KMeans: Projection Residual Quantization for Semantic ID Tokenization

This paper introduces PRQ-KMeans, a post-hoc semantic ID tokenization method that improves upon traditional residual quantization by removing global mean components, refining centroids with similarity-weighted updates, and employing projection residuals to achieve superior performance in generative retrieval and recommendation tasks.

Original authors: Yunxiao Luo, Siyuan Wang, Ben Chen, Chenyi Lei

Published 2026-08-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yunxiao Luo, Siyuan Wang, Ben Chen, Chenyi Lei

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast digital libraries of the internet, where billions of products, articles, and videos compete for attention, computers need a way to organize information that goes beyond simple labels. Traditional systems often rely on unique codes for every single item, much like a library card catalog where each book has a distinct number. However, modern artificial intelligence is learning to understand the meaning behind these items, grouping them by what they are rather than just what they are called. This approach, known as generative retrieval, allows machines to predict and find relevant content by generating short sequences of words or tokens that describe an item's essence. To make this work efficiently, researchers have developed methods to break down complex data into hierarchical layers, where the first few tokens describe a broad category and later tokens narrow down to specific details. The challenge lies in how to strip away the shared, common features of a group of items at each step so that the remaining information is purely what makes the next level of detail unique. If the system fails to remove these common features cleanly, it wastes its capacity repeating information it has already learned, leaving less room to distinguish between the items that matter most.

A team of researchers at Kuaishou Technology has tackled this specific problem with a new method called PRQ-KMeans. Their work focuses on the mechanics of how these hierarchical codes are built, identifying a subtle flaw in how previous systems handled the transition from one level of detail to the next. In the standard approach, when a computer selects a representative "center" for a group of similar items, it simply subtracts that center from the item's data to create a leftover piece, or residual, to be analyzed further. The researchers discovered that this simple subtraction often leaves behind a faint echo of the original center, a leftover component that travels with the data to the next level. This echo is problematic because it causes the next layer of the system to waste time re-analyzing differences that have already been accounted for, effectively blurring the distinction between items that should be clearly separated.

To solve this, the team introduced a process of "progressive commonality removal," which acts like a more precise filter. Instead of just subtracting a standard average, their method first removes a global background component that is shared across the entire dataset, ensuring the system starts with a clean slate. Then, as it builds each layer of the hierarchy, it uses a technique called projection to strip away the specific influence of the chosen center. Imagine a vector of data as a line pointing in a specific direction; the researchers' method ensures that the leftover data sent to the next level is perfectly perpendicular to the direction of the center it just passed through. This guarantees that no part of the previous decision leaks into the next stage, forcing the system to focus entirely on the new, unique differences that define the finer details. They also refined how the system groups items by allowing data points to influence not just their closest neighbor, but a small circle of nearby candidates, creating a more accurate map of the data landscape before making a final decision.

The results of applying this method were measured against existing systems using a massive dataset from an industrial e-commerce search engine containing millions of items and queries. The new approach demonstrated a clear advantage in how well it organized the data and how effectively it helped the search engine find the right products. On this industrial dataset, the new method improved the system's ability to hit the correct item in the top fifty results by 7.4 percent and improved the ranking of the correct item by 11.8 percent compared to the previous best method. These gains were not limited to just one type of data; the researchers also tested the method on four public recommendation benchmarks covering sports, toys, clothing, and music. In every case, the new method performed as well as or better than the leading alternatives, proving that the technique works across different types of content.

Beyond the numbers, the researchers visualized how the system's internal maps changed with their new method. In the older systems, the layers of organization tended to crowd together, with later layers clustering tightly in the center because they were still carrying the "echo" of earlier decisions. With the new projection method, the layers spread out more evenly, utilizing the full space available to distinguish between items. This structural improvement meant that the system could assign more unique codes to different products, reducing the number of times unrelated items were forced to share the same identifier. By carefully controlling exactly what information is passed from one level of analysis to the next, the researchers showed that it is possible to build a more efficient and accurate system for finding things in a digital world, turning a subtle mathematical correction into a significant practical gain for how we search and discover content online.

Technical Summary: PRQ-KMeans

Problem Statement
Semantic Identifiers (SIDs) represent entities as hierarchical token sequences for generative retrieval and recommendation. A common approach to constructing these identifiers is Residual Quantization (RQ), where a codeword is selected at each level to represent a component of the entity, and the residual (the difference between the representation and the codeword) is passed to the next level.

The authors identify three specific limitations in standard RQ tokenizers (such as RQ-KMeans and RQ-VAE) that hinder the efficiency of hierarchical SID construction:

Global Component Dominance: A component shared across the entire corpus (global mean) can dominate the initial representations. In standard RQ, the first codebook must expend capacity modeling this global background rather than distinguishing coarse differences between entities.
Hard Assignment Limitations: Standard K-Means uses hard assignment, where a representation updates only its single nearest centroid. This ignores graded similarities to nearby codewords, discarding useful information near cluster boundaries.
Residual Carryover: Standard RQ subtracts the full centroid vector from the representation. However, if an individual representation contains a different magnitude of the centroid's directional component than the centroid itself, the subtraction leaves a "residual carryover" (positive or negative) along the selected centroid's direction. This forces subsequent codebooks to revisit variation already represented by the current token, reducing the utilization of later SID levels.

Methodology: PRQ-KMeans
The paper proposes PRQ-KMeans (Projection Residual Quantization K-Means), a post-hoc hierarchical SID tokenizer designed to address these limitations through "progressive commonality removal." Unlike VAE-based methods constrained by additive reconstruction, PRQ-KMeans operates on existing embeddings without requiring the codewords to reconstruct the input, allowing the residual to preserve only the necessary differences for future levels.

The method consists of three core mechanisms:

Global Component Removal: Before fitting the first codebook, PRQ-KMeans projects each input embedding onto the global mean of the corpus and subtracts this component. This prevents the global background from consuming the capacity of the first-level codebook.
Top-k Soft Centroid Refinement: During the fitting of each codebook, the algorithm employs a soft refinement step. Instead of updating only the nearest centroid, it identifies the Top- $k$ nearest centroids based on cosine similarity. It then updates these centroids using weights proportional to the similarity scores (via a softmax with concentration parameter $\beta$ ). This allows representations near cluster boundaries to contribute to multiple nearby centroids, improving centroid estimation.
Projection Residual Construction: After hard assignment selects a centroid, PRQ-KMeans does not subtract the full centroid vector. Instead, it calculates the projection residual. It removes only the component of the representation that lies along the direction of the selected centroid, ensuring the resulting residual is strictly orthogonal to that centroid. This eliminates the "residual carryover" issue, ensuring that the next level receives a representation free of the variation already captured by the current token.

Key Contributions

Conceptual Framework: The authors introduce the view of hierarchical SID construction as "progressive commonality removal," identifying that residual construction determines what information is passed between levels. They explicitly characterize "residual carryover" as a source of inefficiency in standard RQ.
Algorithmic Innovation: They propose PRQ-KMeans, which integrates global component removal, Top-k soft centroid refinement, and projection-based residual construction.
Empirical Validation: The method is evaluated on a large-scale industrial e-commerce search dataset and four public recommendation benchmarks (Amazon Sports, Toys, Clothing, and LastFM).

Experimental Results

Industrial Dataset: PRQ-KMeans achieved the strongest overall performance among evaluated tokenizers. Compared to the strong baseline RQ-KMeans, it improved HitRate by 7.4% and MRR by 11.8% on the Order task, and 6.4% and 8.9% on the Click task. It also demonstrated superior codebook quality, with higher prefix utilization and lower Gini coefficients (indicating better distribution of tokens).
Public Benchmarks: PRQ-KMeans achieved the best or tied-best performance across all eight metrics (Recall and NDCG) on the four public datasets, consistently outperforming RQ-KMeans and other baselines like RQ-VAE and RQ-GMM.
Ablation Studies: Removing any of the three components (Global removal, Soft refinement, or Projection) resulted in performance degradation, confirming that all three mechanisms contribute to the method's effectiveness.
Robustness: The method maintained its superiority when tested with different input embeddings (Qwen3 vs. BGE), demonstrating robustness to embedding variations.

Significance and Claims
The paper claims that PRQ-KMeans demonstrates the effectiveness of explicitly controlling the information passed between successive SID levels. By removing the global mean and ensuring residuals are orthogonal to selected centroids, the method allows later levels of the hierarchy to utilize a broader set of prefixes and distinguish entities more effectively. The authors conclude that their approach provides a stronger foundation for generative retrieval and recommendation by optimizing the tokenization process itself, rather than relying solely on the downstream model to learn from suboptimal identifiers. The results suggest that modeling and removing "residual carryover" is a critical, previously underexplored factor in hierarchical quantization.

Technical Summary: PRQ-KMeans

More like this