PaperlayerView exact revision on arXiv

Source-linked AI summary

PRQ-KMeans: Projection Residual Quantization for Semantic ID Tokenization

Yunxiao Luo, Siyuan Wang, Ben Chen, Chenyi Lei

arXiv:2608.24207v1cs.LG

TL;DR

Residual-quantization tokenizers can waste capacity on global commonality, ignore graded centroid similarity, and pass selected-direction variation to later levels. PRQ-KMeans addresses these issues with post-hoc global removal, Top-k centroid refinement, and projection residuals, achieving the best overall downstream retrieval performance across the evaluated datasets, including substantial industrial gains.

  • Problem

    Residual-quantization tokenizers may waste first-level capacity on global commonality, discard graded nearby-codeword similarity, and leave selected-codeword variation in later residuals.

  • Method

    PRQ-KMeans is a post-hoc hierarchical SID tokenizer that removes the global-mean component, refines centroids with Top-k similarity-weighted updates, and uses projection residuals.

  • Results

    PRQ-KMeans achieves the best overall downstream retrieval performance on the industrial dataset and four public benchmarks; on the industrial dataset, it improves Order HitRate and MRR over RQ-KMeans by 7.4% and 11.8%.

  • Takeaways & Limitations

    The results support explicitly controlling what is passed between successive SID levels in hierarchical tokenization.

  • Takeaways & Limitations

    The method is developed in the post-hoc setting, where residual construction is not constrained by additive input reconstruction.

Abstract

from arXiv · show

Semantic identifiers (SIDs) represent entities as hierarchical token sequences for generative retrieval and recommendation. Residual-quantization tokenizers construct these sequences by selecting a codeword at each level and passing a residual to the next. We view this process as progressive commonality removal: each token captures a component shared within its group, while later tokens should model the remaining differences. This view reveals three limitations: a corpus-wide shared component can consume first-level capacity, hard assignment ignores graded similarities to nearby codewords, and full-codeword subtraction can leave variation along the selected-codeword direction in the next residual. We therefore develop our solution in the post-hoc setting, where residual construction is not constrained by input reconstruction. Specifically, we propose PRQ-KMeans, which removes the global-mean component, refines centroids with Top-k similarity-weighted updates, and replaces full-codeword subtraction with a projection residual that removes each representation's selected-centroid component. Experiments on a large-scale industrial search dataset and four public recommendation benchmarks show that PRQ-KMeans achieves the strongest overall performance among the evaluated tokenizers, including gains of up to 7.4% in HitRate and 11.8% in MRR on the industrial dataset.

1 Introduction

Hierarchical SID construction can be viewed as progressive commonality removal, but existing residual-quantization tokenizers face global, assignment, and residual-construction challenges. PRQ-KMeans addresses these challenges in the post-hoc setting with global removal, Top-k refinement, and projection residuals.

  • Hierarchical SIDs use coarse-to-fine token sequences, with shared early tokens and later tokens distinguishing entities under the same prefix.
  • Residual quantization selects a codeword at each level, subtracts it, and passes the residual to the next level.
  • Progressive commonality removal treats each selected codeword as within-group commonality and the residual as the remaining differences for later tokens.
  • Three challenges are identified: global commonality can consume first-level capacity, hard assignment discards graded nearby-codeword similarity, and full subtraction can leave selected-direction carryover.
  • Post-hoc tokenizers permit residuals to preserve only differences needed by later SID levels because reconstruction does not constrain the codeword sum.
  • PRQ-KMeans removes the global-mean component, refines centroids using Top-k similarity-weighted updates, and uses projection residuals for selected-centroid removal.

2 Related Work

Semantic identifiers support generative retrieval and recommendation through hierarchical or signal-enriched token sequences. Residual-quantization methods include autoencoder-based and post-hoc approaches, alongside alternative parallel code-generation methods.

  • Semantic IDs replace atomic entity identifiers with short discrete sequences for generative retrieval and recommendation.
  • Hierarchical SID methods organize identifiers across levels, while related approaches incorporate semantic, lexical, or relevance signals into identifier construction.
  • Residual-quantization methods include autoencoder-based RQ-VAE and R3-VAE, plus post-hoc QARM, OneRec, and RQ-GMM variants.
  • Beyond residual quantization, parallel methods generate multiple codes from separate vector subspaces or token branches.

3 Preliminaries and Motivation

RQ-KMeans recursively assigns centroids and subtracts them to form hierarchical SID residuals, but full subtraction can leave selected-direction carryover. Industrial measurements show this carryover and associate its reduction with broader next-level prefix utilization.

  • 3.1 RQ-KMeans for Hierarchical SIDs: RQ-KMeans fits one K-Means codebook per level, assigns each representation to a centroid, emits the assignment as a token, and passes a residual onward.
  • 3.1 RQ-KMeans for Hierarchical SIDs: The standard residual subtracts the selected centroid from the current representation, with an optional normalized in-place update before the next level.
  • 3.2 Residual Carryover after Centroid Subtraction: Because representations assigned to one centroid can contain different directional coefficients, full subtraction leaves residual carryover when the shared centroid coefficient differs from an instance’s coefficient.
  • 3.3 Empirical Motivation: The industrial three-level tokenizer uses codebook sizes 1024, 512, and 128 to measure carryover and its effect on the following SID level.
  • 3.3 Empirical Motivation: 9.89%, 10.17%, and 7.44% are the mean carryover ratios at L1, L2, and L3, respectively; the 7.07% isotropic-direction reference contextualizes these values.
  • 3.3 Empirical Motivation: 47.88% to 48.46%: L2 prefix utilization increases as retained L1 carryover decreases from η = 1 to η = 0.

4 Methodology

PRQ-KMeans learns hierarchical SID codebooks sequentially, combining global-component removal, Top-k soft refinement, hard cosine assignment, and projection residuals. The projection update removes the selected-centroid component before the next level while preserving the closest orthogonal residual.

  • Overview: At each level, Top-k soft refinement fits the current codebook, hard cosine assignment emits a token, and the residual proceeds to the next level.
  • Projection Residual Construction: The projection residual is chosen as the smallest-change vector orthogonal to the selected centroid.
  • Projection Residual Construction: Unlike RQ-KMeans, the projection residual contains no remaining component along the selected centroid.
  • Projection Residual Construction: Cosine similarity is used for both Top-k soft refinement and hard assignment because centroid magnitude does not affect the removed component.
  • Overview: PRQ-KMeans removes the global component before fitting the first codebook, then reuses the learned mean during SID encoding.
  • Top-k Soft Centroid Refinement: Top-k refinement updates each centroid from representations for which it is a nearby candidate, while hard assignment is used afterward for token emission.
  • SID Encoding: The residual is normalized and used to fit the next codebook, repeating the hierarchy level by level.

5 Experiments

Experiments evaluate PRQ-KMeans across industrial search and four public recommendation benchmarks, comparing codebook quality, retrieval performance, ablations, hyperparameters, embeddings, and qualitative centroid structure. PRQ-KMeans achieves the strongest reported overall results among evaluated tokenizers, with gains in both codebook utilization and downstream retrieval.

  • Industrial benchmark: 7.4% and 11.8% are PRQ-KMeans’s Order HitRate and MRR improvements over RQ-KMeans on the industrial dataset.Click HitRate and MRR also improve by 6.4% and 8.9%, respectively.
  • Public benchmarks: PRQ-KMeans obtains the best or tied-best value on all eight metrics across four public benchmarks and exceeds RQ-KMeans in every comparison.On LastFM, Recall increases from 0.0115 to 0.0179 and NDCG from 0.0042 to 0.0076 relative to RQ-KMeans.
  • Ablation study: The complete PRQ-KMeans model achieves the best result on every industrial ablation metric and the best or tied-best result on all eight public metrics.The ablations remove global component removal, replace soft refinement with hard updates, or replace projection residualization with full-centroid subtraction.
  • Hyperparameter sensitivity: For hyperparameters, k = 2 and k = 5 outperform k = 1 and k = 10, while β = 15–25 remains comparable and β = 10 performs worse.The reported pattern suggests a trade-off between sharing near cluster boundaries and preserving locality.
  • Embedding robustness: With aligned Qwen3 representations replacing BGE representations, PRQ-KMeans achieves the highest HitRate and MRR on both Order and Click.The codebook sizes, alignment procedure, and downstream protocol remain unchanged.

6 Conclusion

PRQ-KMeans frames hierarchical SID construction as progressive commonality removal and explicitly controls the information passed between token levels. Its complete design combines global-component removal, Top-k soft refinement, and projection residuals, with theory characterizing residual carryover and projection-residual properties.

  • Conclusion: PRQ-KMeans is a post-hoc hierarchical SID tokenizer based on progressive commonality removal.It removes the global component before the first level, refines codebooks with Top-k soft weights, and removes the selected-centroid component through projection before the next codebook.
  • Conclusion: The method addresses three tokenization challenges by controlling shared components, graded centroid similarity, and selected-centroid carryover.These design choices correspond to the paper’s progressive-commonality-removal view and its identified challenges.
  • Conclusion: Theoretical analysis derives representation-level carryover within clusters and proves geometric properties of the projection residual.The carryover analysis includes arithmetic-mean centroids and explains when carryover vanishes.
  • Conclusion: Carryover under an arithmetic-mean centroid equals the within-cluster variance of representations’ coefficients along the centroid direction.It becomes zero only when all assigned representations have the same coefficient along that direction; non-mean centroids add an offset term.

A.2 Proof of Proposition 1

The proposition establishes that the projection residual is orthogonal to the selected centroid and uniquely minimizes Euclidean change among all orthogonal alternatives. The algorithm then fits global and levelwise parameters before freezing them to encode hierarchical SIDs.

  • A.2 Proof of Proposition 1: The projection residual removes the selected-centroid component while enforcing orthogonality to that centroid.The proof uses direct expansion to establish exact orthogonality, with normalization preserving it when the residual is nonzero.
  • A.2 Proof of Proposition 1: The projection residual is the unique feasible vector with minimum Euclidean change from the original representation.The feasible set is the closed subspace of vectors orthogonal to the centroid, and the squared-distance decomposition has equality only at the projection residual.
  • Algorithm 1: Algorithm 1 fits the global mean and levelwise codebooks from input embeddings, then freezes them during hierarchical SID encoding.The procedure generates one hierarchical SID for each embedding using the learned parameters.
  • Algorithm 1: The fitting procedure includes global component removal and Top-k soft centroid refinement before SID encoding.The algorithm samples initial centroids and repeats soft refinement for the prescribed number of iterations.
  • Algorithm 1: The encoding stage stores the sequence of tokens produced across all SID levels for each input embedding.The listed procedure returns the global mean and levelwise codebooks after encoding.

C.1 Public Benchmark Setup

The public evaluation uses a common GenRec/TIGER pipeline across four recommendation datasets, with all tokenizers operating on fixed Sentence-T5 representations and identical SID codebook sizes. Performance is measured using item-level Recall and NDCG under shared downstream model settings.

  • C.1 Public Benchmark Setup: The public benchmarks are Sports, Toys, Clothing, and LastFM within the GenRec data-processing and TIGER encoder–decoder pipeline.Tokenizers fit 768-dimensional Sentence-T5-Base item representations and produce three-level SIDs with 256-256-256 codebooks.
  • C.1 Public Benchmark Setup: PRQ-KMeans uses neighborhood size k = 2 and concentration β = 15 in the public evaluation.These settings are applied to the three-level, 256-256-256 SID configuration.
  • C.1 Public Benchmark Setup: All SIDs are evaluated with the same TIGER encoder–decoder and shared training, validation-checkpoint, and beam-decoding settings.The model has four encoder layers, four decoder layers, dimension 128, feed-forward dimension 1024, six attention heads, and beam size 30.
  • C.1 Public Benchmark Setup: The public results use item-level Recall and NDCG.Training uses at most 200 epochs with learning rate 10^-4, zero weight decay, batch size 256, inference batch size 96, and patience 10.

C.2 Industrial Benchmark Setup

The industrial evaluation follows the OneSearch framework on large-scale multimodal query–item representations, comparing three- and five-level SID configurations under shared downstream training. It evaluates Click and Order behavior with beam-expanded item rankings and reports identifier-structure metrics alongside tokenizer comparisons.

  • C.2 Industrial Benchmark Setup: The industrial fitting corpus contains 16,843,945 representations from 7,797,542 items and 9,046,403 training-query records.The 128-dimensional representations encode query text, item titles, prices, keywords, and OCR-derived text using a distilled BGE encoder.
  • C.2 Industrial Benchmark Setup: The industrial study uses three-level 1024-512-128 and five-level 1024-512-128-64-64 SID configurations.PRQ-KMeans uses k = 5 and β = 15, while all tokenizers share BART-Base and the same three downstream training stages.
  • C.2 Industrial Benchmark Setup: Click and Order test sets each contain 30,000 query–item pairs constructed from search logs.Beam search returns 128 SIDs; mapped items are ranked using availability and a composite historical-behavior score before retaining the top five per SID.
  • C.2 Industrial Benchmark Setup: The comparisons include RQ-VAE, R3-VAE, RQ-KMeans, RQ-GMM, PQ-KMeans, and OPQ-KMeans in public and three-level industrial settings.The five-level comparison additionally includes RQ-OPQ, ResKmeansFSQ, and PRQ-OPQ variants.
  • C.2 Industrial Benchmark Setup: Each tokenizer follows its prescribed fitting or training schedule, with PRQ-KMeans using 25 soft centroid-refinement iterations.Other schedules include 20 epochs for the VAE baselines, 25 clustering iterations for RQ-KMeans and PQ-KMeans, and up to 30 EM iterations for RQ-GMM.
  • C.2 Industrial Benchmark Setup: The study reports independent-code ratio, cumulative prefix utilization, and used-prefix Gini for SID-structure analysis.Unused prefixes are excluded from Gini, and lower Gini indicates a more even distribution among occupied prefixes.
  • C.2 Industrial Benchmark Setup: Tokenizer fitting and codebook analyses use a CPU server, while downstream generative-retrieval training and evaluation use eight NVIDIA H800 GPUs.The CPU server has two 96-core AMD EPYC 9654 processors and 2.2 TB RAM; the GPU server has 80 GB HBM3 per GPU.
  • C.2 Industrial Benchmark Setup: The industrial analysis proceeds from carryover measurement and controlled-update details to ablations, sensitivity results, and qualitative case studies.This ordering defines the reported experimental analysis sequence.

D.1 Residual Carryover Analysis

The analysis interprets residual carryover geometrically: after normalization, it is the absolute cosine with the selected centroid, with 7.07% as the isotropic d = 128 reference scale. A controlled update changes only the original carryover term before normalization while keeping the L1 codebook and assignments fixed.

  • After L2 normalization, carryover equals the absolute cosine between the next-level representation and its selected centroid.
  • 7.07% is the expected absolute cosine for two independent isotropic unit directions at d = 128.This provides a dimensional reference for Figure 2(a).
  • The controlled update scales only the original carryover term before normalization, while keeping the L1 codebook and assignments fixed.L2 is refitted for every value of η.

D.3 Public-Benchmark Hyperparameter Sensitivity

On four public benchmarks, k = 2 is consistently best or tied-best for Recall and NDCG, while the preferred concentration parameter varies by dataset. Additional qualitative analyses show PRQ-KMeans separating collision-group items and producing broader, contextually related prefix neighborhoods.

  • Hyperparameter sensitivity: k = 2 gives the best or tied-best Recall and NDCG on all four public benchmarks, with larger k providing no consistent gain.The evaluated neighborhood sizes are k ∈ {1, 2, 5, 10} at β = 15.
  • Hyperparameter sensitivity: β = 15 performs best on Sports, Clothing, and LastFM, whereas β = 10 performs best on Toys.The preferred concentration therefore varies across datasets.
  • Hierarchical SID organization: In a 12-item Kitty-themed collision group, PRQ-KMeans keeps one level-1 prefix, separates items into two level-2 prefixes, and produces three full SIDs.The three full SIDs contain four items each, and Table A2 summarizes their associated keywords.
  • Hierarchical SID organization: For the query “hotel,” the PRQ-KMeans prefix contains 100 items and 29 level-3 branches, versus 22 items and 14 branches for RQ-KMeans.The PRQ-KMeans neighborhood includes hotel-related contexts such as entrances, bathrooms, corridors, and commercial installations.
Loading 2608.24207v1…