Paper deep dive
Exploring Bottom-Up Clustering for Creating Semantic IDs
Leah Woldemariam, Sudhanshu Garg, Taha Belkhouja, Charles Kim-Yip, Ali Sahami
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 9/14/2026, 5:03:39 AM
Summary
This paper proposes a bottom-up clustering algorithm for generating Semantic IDs (SIDs) for generative retrieval systems. Unlike traditional top-down methods like RQ-VAE that often suffer from codebook collapse and item collisions, the proposed method preserves local structure in the embedding space by clustering items at the finest level first and merging them upwards. This ensures unique identifiers for each item while maintaining semantic proximity, leading to improved clustering quality and downstream retrieval performance on datasets like Amazon Product Reviews.
Entities (9)
Relation Signals (8)
Leah Woldemariam → affiliatedwith → Cornell University
confidence 95% · Leah Woldemariam Affiliation: Department of Electrical and Computer Engineering Affiliation: Cornell Tech, Cornell University
Sudhanshu Garg → affiliatedwith → PayPal
confidence 95% · Sudhanshu Garg Affiliation: PayPal
Bottom-Up Clustering → usedfor → Semantic IDs
confidence 95% · In this work, we present an algorithm for generating Semantic IDs... Key to our work is the use of bottom-up clustering
RQ-VAE → comparedwith → Bottom-Up Clustering
confidence 92% · We compare our algorithm to the above baselines... RQ-VAE... as our primary baseline.
Bottom-Up Clustering → evaluatedon → Amazon Product Reviews
confidence 90% · We compare our algorithm to the above baselines with the Amazon Product Reviews dataset
Bottom-Up Clustering → improves → clustering quality
confidence 90% · improving the clustering quality of the resulting Semantic IDs
Bottom-Up Clustering → mitigates → Item Collision
confidence 85% · ensures the identifiers are both unique... collisions occur when a single SID maps to multiple items
Bottom-Up Clustering → mitigates → codebook collapse
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:The success of generative retrieval has largely been attributed to the use of Semantic IDs, which improve over arbitrary item-level identifiers such as hashes by capturing the semantics of items. The main challenges faced when constructing Semantic IDs, however, is in mapping each identifier to a unique product and capturing information valuable to downstream tasks. Past works have appended additional codewords to de-duplicate item identifiers and utilized residual quantization to create hierarchical clusters. In this work, we present an algorithm for generating Semantic IDs that ensure the identifiers are both unique and preserve the structure of the original embedding. Key to our work is the use of bottom-up clustering to preserve local structure in the embedding space, improving the clustering quality of the resulting Semantic IDs and their utility for downstream generative retrieval.
Tags
Links
- Source: https://arxiv.org/abs/2609.08310v1
- Canonical: https://arxiv.org/abs/2609.08310v1
Trouble viewing inline? Open PDF directly →
Full Text
22,861 characters extracted from source content.
Expand or collapse full text
Exploring Bottom-Up Clustering for Creating Semantic IDs Leah Woldemariam Affiliation: Department of Electrical and Computer Engineering Affiliation: Cornell Tech, Cornell University Affiliation: New York, NY, USA Email: lsw85@cornell.edu Sudhanshu Garg Affiliation: PayPal Affiliation: San Jose, California, USA Email: sudgarg@paypal.com Taha Belkhouja Affiliation: PayPal Affiliation: San Jose, California, USA Email: tbelkhouja@paypal.com Charles Kim-Yip Affiliation: PayPal Affiliation: San Jose, California, USA Email: cyip@paypal.com Ali Sahami Affiliation: PayPal Affiliation: San Jose, California, USA Email: asahamishirazi@paypal.com Abstract The success of generative retrieval has largely been attributed to the use of Semantic IDs, which improve over arbitrary item-level identifiers such as hashes by capturing the semantics of items. The main challenges faced when constructing Semantic IDs, however, is in mapping each identifier to a unique product and capturing information valuable to downstream tasks. Past works have appended additional codewords to de-duplicate item identifiers and utilized residual quantization to create hierarchical clusters. In this work, we present an algorithm for generating Semantic IDs that ensure the identifiers are both unique and preserve the structure of the original embedding. Key to our work is the use of bottom-up clustering to preserve local structure in the embedding space, improving the clustering quality of the resulting Semantic IDs and their utility for downstream generative retrieval. 1 Introduction Generative retrieval has been established as a method for creating recommendation systems that provides better generalization performance on new items Rajput et al. (2023). Instead of matching user and item embeddings, generative retrieval takes user information as input and generates potential items by treating retrieval as a sequential task. User information might include previous item interactions or text queries for the task of search. Its main advantage includes avoiding the error propagation due to multi-stage filtering, as well avoiding popularity bias and cold-start issues Lin et al. (2025b); Rajput et al. (2023). Since items in these sequential models must be quantized, a recent line of research has been directed towards approaches to creating these quantized identifiers. Using item semantics to create these identifiers has shown to be the main facilitator in providing better item generalization Rajput et al. (2023). Identifiers that encode item semantics, called Semantic IDs (SIDs), are usually a short sequence of integers built in a hierarchical fashion so that top-level codewords represent coarse, categorical information, and lower level codewords increase precision in identifying an item. The item hierarchy allows for a smaller search space at each decoding step Tay et al. (2022) and allows for a clear method for recommending diverse items Rajput et al. (2023). Among methods used for generating Semantic IDs, Residual-Quantized Variational Autoencoders (RQ-VAEs) and Residual K-Means (R-KMeans) stand out as the most popular due to the use of residual quantization for enforcing the item hierarchy. The primary issues surrounding the creation of Semantic IDs include codebook collapse and item collision. Codebook collapse occurs when only a few codewords within a codebook at any given level in a hierarchy contain the vast majority of items, under-utilizing the entire codebook space, while collisions occur when a single SID maps to multiple items Lin et al. (2025a). Together, these issues can prevent semantically distinct items from being assigned unique and informative identifiers. Arbitrary assignment methods such as hashing or plain enumeration satisfy the property of uniqueness, but they fail to encode semantic relationships between items. Generating good SIDs therefore requires balancing two objectives: assigning each item a unique identifier while ensuring that semantically similar items are mapped to nearby Semantic IDs. In this work, we propose an approach to creating Semantic IDs that both satisfies uniqueness and preserves distance in the embedding space. Using bottom-up rather than top-down clustering, we assign items to leaf nodes first, this ensures that each item corresponds to a single leaf node (uniqueness) and similar items in the embeddings space are inherently assigned nearby SIDs. The motivation behind the use of a bottom-up clustering is to preserve this local structure throughout the SID hierarchy: two items with similar embeddings will more likely share the same (L−1)(L-1)-th codeword when there are L codewords, thereby preserving fine-grained semantic relationships that can be exploited by downstream models. In contrast to conventional methods, which often introduce uniqueness through an ad hoc deduplication step and prioritize global structure during quantization, our approach preserves local neighborhoods by deisgn. By jointly preserving uniqueness and local embedding structure, our approach provides a more faithful discrete interface between pretrained item representations and downstream retrieval decisions, directly addressing the broader question of how pretrained representations can be made more actionable for downstream tasks. 2 Related Work Semantic IDs. Most work on SIDs use Residual Quantization, with an earlier model using Vector Quantization alone is one exception Van Den Oord et al. (2017). Ju et al. (2025) find that RK-Means can out-perform RQ-VAE, noting the added complexity does not necessarily lead to a significant increase in performance. Finally, Liu et al. (2025) finds that the structure of SIDs themselves may limit the scaling of GR models, and that combining SID embeddings with collaborative filtering does not improve scaling. Xu et al. (2026) introduces orthogonal regularization for multi-modal embeddings in order to ensure the weights learned by each expert do not learn redundant information. Collision and Codebook Utilization. Many works cite that the primary issue in creating SIDS through the RQ-VAE is the high collision rate and low codebook utilization Kuai et al. (2024). Kuai et al. (2024) finds that not only can codebooks heavily concentrate products into a small number of codes, but that this phenomenon may be isolated into specific levels. Lin et al. (2025a) similarly note that one pitfall of the Semantic IDs is the lack of uniqueness of the Semantic IDs, which they solve by concatenating the Semantic ID with unique identifiers from the item’s embedding. At Snap, Ju et al. (2026) finds the codebook collapse and collision are primary issues in creating SIDs, and mitigate these issues by backpropagating through the codebook and by introducing heuristics, respectively. Alternatively, semantics is usually measured and improved by categorical/tag information Penha (2025). Liu et al. (2026) adds terms to the loss function that maximize dispersion and improves codebook utilization efficiency. 3 Methods Overview. As in Algorithm 1 presented in the Appendix, the set of items set can be represented as an N×dN× d matrix X. Each xi∈ℝdx_i ^d represents a number of text item attributes used as input together into a pre-trained transformer to create an embedding. Denote the set of labels for each item i at level ℓ as g(ℓ)g^( ), and (gi(1),…,gi(L))(g_i^(1),…,g_i^(L)) represents the Semantic ID for item i. Unlike arbitrary IDs, learned SIDs often struggle to guarantee uniqueness. At the same time, products that are similar to each other should be assigned nearby SIDs in the identifier hierarchy. This is one of the key properties a SID should have and is critical for mitigating the cold-start problem, as it allows unseen or sparsely observed items to share identifier structure with semantically related products. Thus, mapping these embeddings to discrete identifiers can be viewed as a constrained hierarchical clustering problem: the resulting identifiers should uniquely distinguish individual items while preserving the local structure of the original embedding space. We seek to hierarchically assign items their identifiers through bottom-up clustering, i.e., by first clustering items and successively merging them at each level in the hierarchy. By using bottom-up clustering, we preserve local structure within the embedding space and its fine-grained item relationships. In particular, nearby items are grouped together at the lowest levels of the hierarchy before these local groups are progressively merged into coarser clusters. This is in contrast to top-down approaches, which first capture global information in the embedding space and subsequently partition it into increasingly fine-grained regions, potentially losing local relationships introduced at deeper levels of the hierarchy. By preserving these local relationships, our approach aims to retain the information in pretrained item representations that is most useful for downstream retrieval decisions, providing a more actionable interface between latent representations and generative models. Figure 1: (a) A diagram depicting bottom-up clustering, with each node representing the embedding of an item. In the leftmost panel are the unclustered items, and in the middle panel is the initial clusters (green). The rightmost panel shows the final hierarchical clustering with the top-level groups in purple. (b) Example of a sample items assigned SIDs using the bottom-up approach. Algorithm. We construct a hierarchical, bottom-up clustering of the product embeddings X∈ℝN×dX ^N× d as described in Algorithm 1. The procedure begins at the finest level by clustering the raw embeddings, streamed in chunks, to partition N products into k0k_0 fine-grained groups. To ensure that the final codebook uniquely identifies each item, groups containing more than K items are further split until every sub-cluster contains at most K items. We enumerate each item within these fine clusters and assign its index as the L-th codeword, ensuring every product has a unique within-cluster identifier. For each of the initial groups, we compute a weighted centroid using its member count, yielding a compact set of k1k_1 representative points that summarizes the full dataset. We then coarsen the hierarchy upward by iteratively merging these centroids. At each level, we cluster the current set of centroids using standard Agglomerative Clustering, using each centroid’s member count as a sample weight so that the merge respects the true population mass. After each merge, we recompute the centroids and weights for the newly formed groups, and propagate the new labels back down to every original product. Repeating this produces a sequence of increasingly coarse cluster assignments. Each cluster at every level is enumerated 1,…,kℓ1,…,k_ as the standard format of SIDs. Note that kℓk_ need not be the same at each level. Merging clusters at g(ℓ)g^( ) creates the ℓ−1 -1 codewords, thereby creating clusters by moving up the tree. See Algorithm 1 for a more detailed description. New items are assigned SIDs according to their nearest neighbors. A new item inherits the first L−1L-1 codewords of its nearest neighbor, with a unique L-th codeword assigned within the selected cluster. When a cluster exceeds a predefined threshold, it can be further split into sub-clusters. Cluster assignment may also use multiple nearest neighbors for greater robustness. Importantly, this procedure allows the SID hierarchy learned from pretrained item representations to generalize to previously unseen items without reconstructing the identifier space. By transferring local structure to new items, the resulting SIDs make pretrained representations directly actionable for downstream retrieval under cold-start settings. 4 Experiments Metrics. We evaluate our approach with a number of metrics to measure codebook quality and clustering quality, and additionally evaluate our method over a next-product prediction task to assess the downstream utility of the resulting Semantic IDs. To measure codebok quality, we measure the average number of items assigned to each SID, which captures the extent to which multiple items share the same identifier and provides an indication of identifier collisions and codebook utilization. To measure clustering quality, we evaluate silhouette score and cosine similarity; we measure these metrics at each depth of the tree created by the SIDs, i.e. for clusters created by the first codebook, second codebook, and so on, while emphasizing the values at the final clusters. These metrics characterize how well the SID hierarchy preserves the structure of the pretrained embedding space. When a dataset has categorical labels for each item, we additionally measure the average number of categories among items within a codeword, where fewer categories indicate greater semantic coherence within the resulting clusters. As in Rajput et al. (2023), recall and NDCG is reported for item prediction tasks. These downstream metrics allow us to evaluate whether improvements in the structure of the Semantic IDs translate into better retrieval decisions, connecting representation quality to downstream actionability. Baselines. We compare against an RQ-VAE, the a widely used method for constructing SIDs, as our primary baseline. The RQ-VAE constructs codebooks in a top-down, hierarchical fashion starting with a fixed codebook size L. Datasets. We compare our algorithm to the above baselines with the Amazon Product Reviews dataset, a collection of product reviews for items Ni et al. (2019). We evaluate over the Beauty and Sports & Outdoors splits. We additionally compare our algorithm gainst the same baselines on a custom dataset containing approximately 6 million items, each with titles, model-generated captions of corresponding images, categorical information, and brand information. For each product, we concatenate the available textual information and encode it using a Qwen model to obtain the pretrained item embedding from which its SID is constructed. Custom Dataset Beauty Sports & Outdoors Metric RQ-VAE Bottom-Up RQ-VAE Bottom-Up RQ-VAE Bottom-Up Codebook Quality Avg. Rows per ID 1.63 1 1.35 1 1.49 1 Clustering Quality Avg. Silhouette Score 0.00 0.29 −-0.07 0.07 0.02 0.07 Cosine Similarity 0.80 0.82 0.76 0.80 0.88 0.79 Next Product Prediction Recall@10 0.020 0.036 0.0509 0.0567 0.0328 0.0327 NDCG@10 0.001 0.002 0.0255 0.0296 0.0169 0.0166 Other Avg. Unique Categories 1.06 14.30 1.16 3.75 1.21 4.54 Table 1: Comparison of RQ-VAE and Bottom-Up clustering methods across the 5.8M Item dataset and Amazon Beauty datasets. Cluster-based metrics are reported at the final depth of the tree. RQ-VAE & Next Product Prediction Model Implementation. We first perform a hyper-parameter search on the batch size, learning rate, weight decay, codebook mode, codebook size, number of codebooks, and VAE hidden dimensions to compare our approach against the best possible RQ-VAE. The RQ-VAE used in these experiments has a codebook size of 256 for 3 codebooks. An extra codeword was appended to the RQ-VAE generated SIDs so that each item corresponding to a single SID, following the style of Rajput et al. (2023); Ju et al. (2025). Results. Table 1 reports the metrics for the finest-grained groups. For the bottom-up approach, this is evaluated at level L−1L-1, corresponding to clusters defined by the tuples (g(1),…,g(L−1))(g^(1),…,g^(L-1)), since the L-th level always maps to unique items. The bottom-up approach achieves higher silhouette scores across all datasets at the finest granularity, indicating that its finest-level clusters are more compact and better separated in the pretrained embedding space. The gap is particularly large on the custom dataset, which contains substantially more items and greater product diversity than the Amazon Reviews Beauty dataset. This suggests that preserving local structure may become increasingly important as the item space grows more heterogeneous. The bottom-up approach also achieves higher Recall@10 and NDCG@10 on the downstream next-item prediction task, showing that improved SID structure translates to better downstream retrieval. The bottom-up approach also yields a higher average number of unique categories within each cluster, which is expected because the optimal RQ-VAE configuration uses a codebook size substantially larger than the number of clusters at each level in the bottom-up hierarchy. Unlike RQ-VAE, which learns a residual hierarchy from coarse to fine, our bottom-up method constructs the SID hierarchy directly from local relationships in the pretrained embedding space. We show that this structure-preserving approach leads to better clustering quality as well as improved performance on the downstream task of next-item prediction. More broadly, these results suggest that the way pretrained representations are converted into discrete abstractions materially affects their downstream utility: preserving tak-relevant local structure can make those representations more actionable for downstream decision-making. References [1] C. M. Ju, L. Collins, L. Neves, B. Kumar, L. Y. Wang, T. Zhao, and N. Shah (2025) Generative recommendation with semantic ids: a practitioner’s handbook. In Proceedings of the 34th ACM International Conference on Information and Knowledge Management, p. 6420–6425. Cited by: §2, §4. [2] C. M. Ju, T. Zhao, L. Neves, L. Collins, B. Kumar, J. Ren, L. Zhang, W. Zhuo, V. Zhang, X. Bai, et al. (2026) Semantic ids for recommender systems at snapchat: use cases, technical challenges, and design choices. arXiv preprint arXiv:2604.03949. Cited by: §2. [3] Z. Kuai, Z. Chen, H. Wang, M. Li, D. Miao, W. Binbin, X. Chen, L. Kuang, Y. Han, J. Wang, et al. (2024) Breaking the hourglass phenomenon of residual quantization: enhancing the upper bound of generative retrieval. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing: Industry Track, p. 677–685. Cited by: §2. [4] G. Lin, Z. Hua, T. Feng, S. Yang, B. Long, and J. You (2025) Unified semantic and id representation learning for deep recommenders. arXiv preprint arXiv:2502.16474. Cited by: §1, §2. [5] S. Lin, C. Gao, J. Chen, S. Zhou, B. Hu, Y. Feng, C. Chen, and C. Wang (2025) How do recommendation models amplify popularity bias? an analysis from the spectral perspective. In Proceedings of the Eighteenth ACM International Conference on Web Search and Data Mining, p. 659–668. Cited by: §1. [6] J. Liu, L. Collins, J. Tang, T. Zhao, N. Shah, and C. M. Ju (2025) Understanding generative recommendation with semantic ids from a model-scaling view. arXiv preprint arXiv:2509.25522. Cited by: §2. [7] X. Liu, F. Zhang, Y. Wu, X. Jia, Z. Xia, F. Zhuang, Z. Zhang, F. Jiang, and W. Lin (2026) CAT-id2: category-tree integrated document identifier learning for generative retrieval in e-commerce. In Proceedings of the Nineteenth ACM International Conference on Web Search and Data Mining, p. 426–435. Cited by: §2. [8] J. Ni, J. Li, and J. McAuley (2019) Justifying recommendations using distantly-labeled reviews and fine-grained aspects. In Proceedings of the 2019 conference on empirical methods in natural language processing and the 9th international joint conference on natural language processing (EMNLP-IJCNLP), p. 188–197. Cited by: §4. [9] e. al. Penha (2025) Semantic ids for generative search and recommendation. External Links: Link Cited by: §2. [10] S. Rajput, N. Mehta, A. Singh, R. Hulikal Keshavan, T. Vu, L. Heldt, L. Hong, Y. Tay, V. Tran, J. Samost, et al. (2023) Recommender systems with generative retrieval. Advances in Neural Information Processing Systems 36, p. 10299–10315. Cited by: §1, §1, §4, §4. [11] Y. Tay, V. Tran, M. Dehghani, J. Ni, D. Bahri, H. Mehta, Z. Qin, K. Hui, Z. Zhao, J. Gupta, et al. (2022) Transformer memory as a differentiable search index. Advances in neural information processing systems 35, p. 21831–21843. Cited by: §1. [12] A. Van Den Oord O. Vinyals et al. (2017) Neural discrete representation learning. Advances in neural information processing systems 30. Cited by: §2. [13] Y. Xu, M. Zhang, C. Li, Z. Liao, H. Xing, H. Deng, J. Hu, Y. Zhang, X. Zeng, and J. Zhang (2026) Mmq: multimodal mixture-of-quantization tokenization for semantic id generation and user behavioral adaptation. In Proceedings of the Nineteenth ACM International Conference on Web Search and Data Mining, p. 788–797. Cited by: §2. Appendix A Appendix Below is the algorithm describing our bottom-up approach. In our experiments, the bottom-up clustering approach used 2000 and 64 clusters at level L−1L-1 and L−2L-2, respectively for the custom dataset and otherwise matches the codebook size used by the RQ-VAE for the Amazon datasets. Algorithm 1 Bottom-Up Hierarchical Clustering 1: Embedding matrix X∈ℝN×dX ^N× d; strictly decreasing coarsening schedule K=[k1,k2,…,kL]K=[k_1,k_2,…,k_L]; optional per-cluster size cap cmaxc_ . 2: Per-item level labels g(0),g(1),…,g(L)\g^(0),g^(1),…,g^(L)\, each g(ℓ)∈0,1,…Ng^( )∈\0,1,…\^N giving every item i a label at level ℓ ; tuple (gi(1),gi(2),…,gi(L))(g^(1)_i,g^(2)_i,…,g^(L)_i) is unique per item. 3: 4: Step 1: Finest clustering 5: g(L−1)←MiniBatchKMeans(X,k1)g^(L-1)← MiniBatchKMeans(X,\,k_1) ⊳ returns a label gi(L−1)∈0,…,k1−1g^(L-1)_i∈\0,…,k_1-1\ for every item i 6: (C,w)←GroupCentroids(X,g(L−1))(C,w)← GroupCentroids(X,\,g^(L-1)) ⊳ C∈ℝkℓ×dC ^k_ × d centroids; w: its item count ⊳ a maps cluster labels at ℓ+1 +1 to labels at level ℓ 7: for all groups s in g(L−1)g^(L-1) do 8: assign the members of s distinct ids 0,1,2,…0,1,2,… (running count within s) as their label g(L)g^(L) 9: end for 10: g(L)←g^(L)← these per-item ids ⊳ (uniqueness) 11: Step 2: Recursive Merging 12: for ℓ=L−2 =L-2 to 11 do 13: g(ℓ)←MiniBatchKMeans(C,kℓ,sample_weight=w,parent=g(ℓ+1))g^( )← MiniBatchKMeans (C,\,k_ ,\,sample\_weight=w,\ parent=g^( +1) ) 14: 15: if cmax≠∅c_ ≠ then g(ℓ)←EnforceMaxClusterSize(X,g(ℓ),cmax)g^( )← EnforceMaxClusterSize (X,\,g^( ),\,c_ ) ⊳ splits any level-ℓ group with more than cmaxc_ items 16: end if 17: relabel g(ℓ)g^( ) to dense ids 0,…,nℓ−1\0,…,n_ -1\ 18: (C,w)←GroupCentroids(X,g(ℓ))(C,w)← GroupCentroids(X,\,g^( )) 19: end for 20: return (g(1),g(1),…,g(L))(g^(1),g^(1),…,g^(L))