# NGAME: Negative Mining-aware Mini-batching for Extreme Classification

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 78 references that are in the map.
- First posted on arXiv 10 Jul 2022.

## Builds on (most cited first, 30 of 33)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Momentum Contrast for Unsupervised Visual Representation Learning](https://mlsanity.com/paper/1911.05722/) (2019)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [FaceNet: A Unified Embedding for Face Recognition and Clustering](https://mlsanity.com/paper/1503.03832/) (2015)
- [Bag of Tricks for Efficient Text Classification](https://mlsanity.com/paper/1607.01759/) (2016)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval](https://mlsanity.com/paper/2007.00808/) (2020)
- [RocketQA: An Optimized Training Approach to Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2010.08191/) (2020)
- [Efficiently Teaching an Effective Dense Retriever with Balanced Topic Aware Sampling](https://mlsanity.com/paper/2104.06967/) (2021)
- [Sparse, Dense, and Attentional Representations for Text Retrieval](https://mlsanity.com/paper/2005.00181/) (2020)
- [Smart Mining for Deep Metric Learning](https://mlsanity.com/paper/1704.01285/) (2017)
- [DiSMEC - Distributed Sparse Machines for Extreme Multi-label Classification](https://mlsanity.com/paper/1609.02521/) (2016)
- [Fast Multi-Resolution Transformer Fine-tuning for Extreme Multi-label Text Classification](https://mlsanity.com/paper/2110.00685/) (2021)
- [Bonsai -- Diverse and Shallow Trees for Extreme Multi-label Classification](https://mlsanity.com/paper/1904.08249/) (2019)
- [LightXML: Transformer with Dynamic Negative Sampling for High-Performance Extreme Multi-label Text Classification](https://mlsanity.com/paper/2101.03305/) (2021)
- [A no-regret generalization of hierarchical softmax to extreme multi-label classification](https://mlsanity.com/paper/1810.11671/) (2018)
- [Ordered SGD: A New Stochastic Optimization Framework for Empirical Risk Minimization](https://mlsanity.com/paper/1907.04371/) (2019)
- [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)
- [Extreme Classification in Log Memory using Count-Min Sketch: A Case Study of Amazon Search with 50M Products](https://mlsanity.com/paper/1910.13830/) (2019)
- [DECAF: Deep Extreme Classification with Label Features](https://mlsanity.com/paper/2108.00368/) (2021)
- [Stochastic Negative Mining for Learning with Large Output Spaces](https://mlsanity.com/paper/1810.07076/) (2018)
- [Extreme Multi-Label Legal Text Classification: A case study in EU Legislation](https://mlsanity.com/paper/1905.10892/) (2019)
- [Pretrained Generalized Autoregressive Model with Adaptive Probabilistic Label Clusters for Extreme Multi-label Text Classification](https://mlsanity.com/paper/2007.02439/) (2020)
- [Deep Extreme Multi-label Learning](https://mlsanity.com/paper/1704.03718/) (2017)
- [Large-Scale Training System for 100-Million Classification at Alibaba](https://mlsanity.com/paper/2102.06025/) (2021)

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

- [Large Language Models as Annotators: Enhancing Generalization of NLP Models at Minimal Cost](https://mlsanity.com/paper/2306.15766/) (2023)
- [Breaking the Batch Barrier (B3) of Contrastive Learning via Smart Batch Mining](https://mlsanity.com/paper/2505.11293/) (2025)
- [ELIAS: End-to-End Learning to Index and Search in Large Output Spaces](https://mlsanity.com/paper/2210.08410/) (2022)
- [A Survey on Extreme Multi-label Learning](https://mlsanity.com/paper/2210.03968/) (2022)
- [Dual-Encoders for Extreme Multi-Label Classification](https://mlsanity.com/paper/2310.10636/) (2023)
- [Unified Generative & Dense Retrieval for Query Rewriting in Sponsored Search](https://mlsanity.com/paper/2209.05861/) (2022)
- [Graphite: A Graph-based Extreme Multi-Label Short Text Classifier for Keyphrase Recommendation](https://mlsanity.com/paper/2407.20462/) (2024)
- [ICXML: An In-Context Learning Framework for Zero-Shot Extreme Multi-Label Classification](https://mlsanity.com/paper/2311.09649/) (2023)
- [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)
- [Learning label-label correlations in Extreme Multi-label Classification via Label Features](https://mlsanity.com/paper/2405.04545/) (2024)
- [GraphEx: A Graph-based Extraction Method for Advertiser Keyphrase Recommendation](https://mlsanity.com/paper/2409.03140/) (2024)
- [Navigating Extremes: Dynamic Sparsity in Large Output Spaces](https://mlsanity.com/paper/2411.03171/) (2024)
- [Your Pretrained Model Tells the Difficulty Itself: A Self-Adaptive Curriculum Learning Paradigm for Natural Language Understanding](https://mlsanity.com/paper/2507.09758/) (2025)
- [Large Language Model as a Teacher for Zero-shot Tagging at Extreme Scales](https://mlsanity.com/paper/2406.09288/) (2024)
- [Improving Retrieval in Sponsored Search by Leveraging Query Context Signals](https://mlsanity.com/paper/2407.14346/) (2024)
- [Prototypical Extreme Multi-label Classification with a Dynamic Margin Loss](https://mlsanity.com/paper/2410.20401/) (2024)
- [Labels in Extremes: How Well Calibrated are Extreme Multi-label Classifiers?](https://mlsanity.com/paper/2411.04276/) (2024)
- [LLMDistill4Ads: Using Cross-Encoders to Distill from LLM Signals for Advertiser Keyphrase Recommendations at eBay](https://mlsanity.com/paper/2508.03628/) (2025)
- [Graph Regularized Encoder Training for Extreme Classification](https://mlsanity.com/paper/2402.18434/) (2024)
- [UniDEC : Unified Dual Encoder and Classifier Training for Extreme Multi-Label Classification](https://mlsanity.com/paper/2405.03714/) (2024)
- [Multi-label Learning with Random Circular Vectors](https://mlsanity.com/paper/2407.05656/) (2024)
- [BroadGen: A Framework for Generating Effective and Efficient Advertiser Broad Match Keyphrase Recommendations](https://mlsanity.com/paper/2505.19164/) (2025)
- [A Geometry-Aware Efficient Algorithm for Compositional Entropic Risk Minimization](https://mlsanity.com/paper/2602.02877/) (2026)
- [HASTE: Hardware-Aware Dynamic Sparse Training for Large Output Spaces](https://mlsanity.com/paper/2606.01117/) (2026)
- [XLDA: Linear Discriminant Analysis for Scaling Continual Learning to Extreme Classification at the Edge](https://mlsanity.com/paper/2307.11317/) (2023)
- [On the Necessity of World Knowledge for Mitigating Missing Labels in Extreme Classification](https://mlsanity.com/paper/2408.09585/) (2024)
- [ASTRA: Accurate and Scalable ANNS-based Training of Extreme Classifiers](https://mlsanity.com/paper/2409.20156/) (2024)
- [Fine-grained auxiliary learning for real-world product recommendation](https://mlsanity.com/paper/2510.04551/) (2025)
- [Next-Gen Sponsored Search: Crafting the Perfect Query with Inventory-Aware RAG (InvAwr-RAG) Based GenAI](https://mlsanity.com/paper/2607.03880/) (2026)

## Abstract (arXiv)

Extreme Classification (XC) seeks to tag data points with the most relevant subset of labels from an extremely large label set. Performing deep XC with dense, learnt representations for data points and labels has attracted much attention due to its superiority over earlier XC methods that used sparse, hand-crafted features. Negative mining techniques have emerged as a critical component of all deep XC methods that allow them to scale to millions of labels. However, despite recent advances, training deep XC models with large encoder architectures such as transformers remains challenging. This paper identifies that memory overheads of popular negative mining techniques often force mini-batch sizes to remain small and slow training down. In response, this paper introduces NGAME, a light-weight mini-batch creation technique that offers provably accurate in-batch negative samples. This allows training with larger mini-batches offering significantly faster convergence and higher accuracies than existing negative sampling techniques. NGAME was found to be up to 16% more accurate than state-of-the-art methods on a wide array of benchmark datasets for extreme classification, as well as 3% more accurate at retrieving search engine queries in response to a user webpage visit to show personalized ads. In live A/B tests on a popular search engine, NGAME yielded up to 23% gains in click-through-rates.