Source-linked AI summary
Exploring Bottom-Up Clustering for Creating Semantic IDs
Leah Woldemariam, Sudhanshu Garg, Taha Belkhouja, Charles Kim-Yip, Ali Sahami
TL;DR
Semantic ID construction must reconcile unique item identification with preservation of semantic structure for downstream generative retrieval. The paper addresses this with bottom-up clustering that builds local groups first and then merges them into a hierarchy. The reported results show better clustering quality and next-item prediction performance than the RQ-VAE comparison.
Problem
Semantic ID construction must uniquely identify products while keeping semantically similar items near one another in the identifier hierarchy.
Method
The method builds Semantic IDs with bottom-up clustering, forming local groups first and progressively merging them into coarser hierarchical clusters.
Results
Bottom-up clustering achieves higher finest-level silhouette scores and higher Recall@10 and NDCG@10 than the comparison method.
Takeaways & Limitations
Preserving local relationships in pretrained embeddings improves the clustering quality and downstream utility of Semantic IDs.
Abstract
from arXiv · showhide
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 uses Semantic IDs to encode item meaning in sequential recommendation and search, but constructing them requires both unique item assignments and preservation of semantic proximity. The paper motivates bottom-up clustering as a way to address these challenges.
- Generative retrieval generates potential items sequentially from user information rather than matching user and item embeddings.
- Semantic IDs hierarchically encode coarse categorical information and progressively finer item distinctions, reducing search space at each decoding step.
- Codebook collapse and item collision can prevent Semantic IDs from being both well utilized and uniquely informative.
- Good Semantic IDs must uniquely identify each item while mapping semantically similar items to nearby identifiers.
- The proposed bottom-up approach assigns items to leaf nodes first to preserve embedding distance and local semantic structure while ensuring uniqueness.
2 Related Work
Prior work primarily uses residual quantization to construct hierarchical Semantic IDs, while addressing collision, codebook collapse, and utilization through deduplication, training changes, or regularization.
- Residual-quantized methods, especially RQ-VAE and R-KMeans, are popular because residual quantization enforces an item hierarchy.
- Semantic ID research identifies collision and codebook concentration as recurring problems that reduce uniqueness and codebook utilization.
- Prior solutions append unique identifiers, backpropagate through codebooks, introduce heuristics, or add dispersion terms to address these problems.
3 Methods
The method treats Semantic ID construction as constrained hierarchical clustering: items must remain uniquely identifiable while nearby embeddings retain nearby identifier structure. Bottom-up clustering first forms local groups, then merges weighted centroids into coarser levels.
- Overview: Item attributes are encoded into pretrained embeddings, which are represented as rows of an N × d matrix X for hierarchical clustering.
- Overview: The method frames Semantic ID assignment as preserving local embedding structure while uniquely distinguishing individual items.
- Bottom-Up Clustering: Bottom-up clustering groups nearby items at the lowest levels before progressively merging them into coarser clusters.
- Algorithm: Fine-level groups are split until each contains at most K items, then items receive unique within-cluster final codewords.
- Algorithm: The hierarchy is coarsened by repeatedly clustering weighted centroids, recomputing group centroids, and propagating labels to original products.
- New-Item Assignment: New items inherit the first L −1 codewords from a nearest neighbor and receive a unique final codeword within the selected cluster.
4 Experiments
The experiments evaluate codebook, clustering, and next-item prediction quality on Amazon Beauty, Sports & Outdoors, and a 5.8M-item dataset against RQ-VAE. Bottom-up clustering produces better finest-level clustering and downstream retrieval results, while category composition reflects differing cluster structures.
- Metrics: The evaluation measures SID collisions and utilization, silhouette and cosine clustering quality across tree depths, and Recall and NDCG for next-item prediction.
- Baselines: RQ-VAE is the primary baseline and constructs a fixed-size hierarchical codebook top-down through residual quantization.
- Datasets: The datasets include Amazon Product Reviews splits and a custom approximately 6 million-item collection represented using concatenated product text encoded by Qwen.
- Results: Bottom-up clustering achieves higher finest-granularity silhouette scores across datasets, with a particularly large gap on the larger and more diverse custom dataset.
- Results: Bottom-up clustering also achieves higher Recall@10 and NDCG@10 on next-item prediction than the comparison method.
- Conclusion: The results show that constructing Semantic IDs from local embedding relationships improves clustering quality and next-item prediction performance relative to a coarse-to-fine residual hierarchy.
A Appendix
Algorithm 1 constructs per-item labels through finest-level clustering followed by recursive merging of cluster representations. It assigns distinct within-cluster identifiers to guarantee item-level uniqueness and returns labels across hierarchy levels.
- Implementation: The appendix identifies the method as bottom-up hierarchical clustering and reports using 2000 and 64 clusters at levels L −1 and L −2 for the custom dataset.For the Amazon datasets, the implementation matches the RQ-VAE codebook size.
- Algorithm inputs and outputs: The procedure takes an embedding matrix, a decreasing coarsening schedule, and an optional cluster-size cap, then returns per-item labels at every hierarchy level.Each level assigns a label to every item, while the schedule controls progressively coarser clustering.
- Step 1: Finest clustering: Finest-level clustering partitions the embeddings, computes group centroids and item counts, and assigns each member a distinct running identifier.The distinct identifiers become the finest labels and provide uniqueness within each initial group.
- Step 2: Recursive Merging: Recursive merging repeatedly clusters the current representations at coarser levels and propagates the resulting labels back to the original items.The procedure returns the complete sequence of labels after the recursive merging loop.
- Step 1: Finest clustering: Groups exceeding the size cap are split, and the resulting labels are relabeled to dense identifiers before recursive merging begins.The cap limits group size, while dense relabeling standardizes the cluster labels.