# Extreme Classification in Log Memory using Count-Min Sketch: A Case Study of Amazon Search with 50M Products

arXiv: https://arxiv.org/abs/1910.13830 · HTML: https://mlsanity.com/paper/1910.13830/

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- Placed in MoE large language models, one of 12 directions in Mixture-of-experts.
- First posted on arXiv 28 Oct 2019.

## Placed in

- Mixture-of-experts / [MoE large language models](https://mlsanity.com/moe/moe-large-language-models/)

## Built on by (most cited first, 30 of 36)

- [ML-Decoder: Scalable and Versatile Classification Head](https://mlsanity.com/paper/2111.12933/) (2021)
- [Fast Multi-Resolution Transformer Fine-tuning for Extreme Multi-label Text Classification](https://mlsanity.com/paper/2110.00685/) (2021)
- [ECLARE: Extreme Classification with Label Graph Correlations](https://mlsanity.com/paper/2108.00261/) (2021)
- [DeepXML: A Deep Extreme Multi-Label Learning Framework Applied to Short Text Documents](https://mlsanity.com/paper/2111.06685/) (2021)
- [DECAF: Deep Extreme Classification with Label Features](https://mlsanity.com/paper/2108.00368/) (2021)
- [NGAME: Negative Mining-aware Mini-batching for Extreme Classification](https://mlsanity.com/paper/2207.04452/) (2022)
- [Learning with Holographic Reduced Representations](https://mlsanity.com/paper/2109.02157/) (2021)
- [Extreme Zero-Shot Learning for Extreme Text Classification](https://mlsanity.com/paper/2112.08652/) (2021)
- [On Missing Labels, Long-tails and Propensities in Extreme Multi-label Classification](https://mlsanity.com/paper/2207.13186/) (2022)
- [Large-Scale Training System for 100-Million Classification at Alibaba](https://mlsanity.com/paper/2102.06025/) (2021)
- [Metadata-Induced Contrastive Learning for Zero-Shot Multi-Label Text Classification](https://mlsanity.com/paper/2202.05932/) (2022)
- [Propensity-scored Probabilistic Label Trees](https://mlsanity.com/paper/2110.10803/) (2021)
- [Label Disentanglement in Partition-based Extreme Multilabel Classification](https://mlsanity.com/paper/2106.12751/) (2021)
- [A Survey on Extreme Multi-label Learning](https://mlsanity.com/paper/2210.03968/) (2022)
- [PINA: Leveraging Side Information in eXtreme Multi-label Classification via Predicted Instance Neighborhood Aggregation](https://mlsanity.com/paper/2305.12349/) (2023)
- [Dual-Encoders for Extreme Multi-Label Classification](https://mlsanity.com/paper/2310.10636/) (2023)
- [SemSup-XC: Semantic Supervision for Zero and Few-shot Extreme Classification](https://mlsanity.com/paper/2301.11309/) (2023)
- [Towards Memory-Efficient Training for Extremely Large Output Spaces -- Learning with 500k Labels on a Single Commodity GPU](https://mlsanity.com/paper/2306.03725/) (2023)
- [Generalized test utilities for long-tail performance in extreme multi-label classification](https://mlsanity.com/paper/2311.05081/) (2023)
- [Speeding-up One-vs-All Training for Extreme Classification via Smart Initialization](https://mlsanity.com/paper/2109.13122/) (2021)
- [MatchXML: An Efficient Text-label Matching Framework for Extreme Multi-label Text Classification](https://mlsanity.com/paper/2308.13139/) (2023)
- [Multi-modal Extreme Classification](https://mlsanity.com/paper/2309.04961/) (2023)
- [Navigating Extremes: Dynamic Sparsity in Large Output Spaces](https://mlsanity.com/paper/2411.03171/) (2024)
- [Federated Multiple Label Hashing (FedMLH): Communication Efficient Federated Learning on Extreme Classification Tasks](https://mlsanity.com/paper/2110.12292/) (2021)
- [Adversarial Examples for Extreme Multilabel Text Classification](https://mlsanity.com/paper/2112.07512/) (2021)
- [On Riemannian Approach for Constrained Optimization Model in Extreme Classification Problems](https://mlsanity.com/paper/2109.15021/) (2021)
- [Graph Regularized Encoder Training for Extreme Classification](https://mlsanity.com/paper/2402.18434/) (2024)
- [IRLI: Iterative Re-partitioning for Learning to Index](https://mlsanity.com/paper/2103.09944/) (2021)
- [CARLS: Cross-platform Asynchronous Representation Learning System](https://mlsanity.com/paper/2105.12849/) (2021)
- [Physics-Guided Problem Decomposition for Scaling Deep Learning of High-dimensional Eigen-Solvers: The Case of Schr"odinger's Equation](https://mlsanity.com/paper/2202.05994/) (2022)

## Abstract (arXiv)

In the last decade, it has been shown that many hard AI tasks, especially in NLP, can be naturally modeled as extreme classification problems leading to improved precision. However, such models are prohibitively expensive to train due to the memory blow-up in the last layer. For example, a reasonable softmax layer for the dataset of interest in this paper can easily reach well beyond 100 billion parameters (>400 GB memory). To alleviate this problem, we present Merged-Average Classifiers via Hashing (MACH), a generic K-classification algorithm where memory provably scales at O(logK) without any strong assumption on the classes. MACH is subtly a count-min sketch structure in disguise, which uses universal hashing to reduce classification with a large number of classes to few embarrassingly parallel and independent classification tasks with a small (constant) number of classes. MACH naturally provides a technique for zero communication model parallelism. We experiment with 6 datasets; some multiclass and some multilabel, and show consistent improvement over respective state-of-the-art baselines. In particular, we train an end-to-end deep classifier on a private product search dataset sampled from Amazon Search Engine with 70 million queries and 49.46 million products. MACH outperforms, by a significant margin,the state-of-the-art extreme classification models deployed on commercial search engines: Parabel and dense embedding models. Our largest model has 6.4 billion parameters and trains in less than 35 hours on a single p3.16x machine. Our training times are 7-10x faster, and our memory footprints are 2-4x smaller than the best baselines. This training time is also significantly lower than the one reported by Google's mixture of experts (MoE) language model on a comparable model size and hardware.