# Generalized test utilities for long-tail performance in extreme multi-label classification

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 52 references that are in the map.
- First posted on arXiv 9 Nov 2023.

## Builds on (most cited first, 21 of 21)

- [AttentionXML: Label Tree-based Attention-Aware Deep Model for High-Performance Extreme Multi-Label Text Classification](https://mlsanity.com/paper/1811.01727/) (2018)
- [Inferring Networks of Substitutable and Complementary Products](https://mlsanity.com/paper/1506.08839/) (2015)
- [Unbiased Recommender Learning from Missing-Not-At-Random Implicit Feedback](https://mlsanity.com/paper/1909.03601/) (2019)
- [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)
- [ECLARE: Extreme Classification with Label Graph Correlations](https://mlsanity.com/paper/2108.00261/) (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)
- [Learning Optimal Tree Models Under Beam Search](https://mlsanity.com/paper/2006.15408/) (2020)
- [Pretrained Generalized Autoregressive Model with Adaptive Probabilistic Label Clusters for Extreme Multi-label Text Classification](https://mlsanity.com/paper/2007.02439/) (2020)
- [On Missing Labels, Long-tails and Propensities in Extreme Multi-label Classification](https://mlsanity.com/paper/2207.13186/) (2022)
- [Surrogate regret bounds for generalized classification performance metrics](https://mlsanity.com/paper/1504.07272/) (2015)
- [Probabilistic Label Trees for Extreme Multi-label Classification](https://mlsanity.com/paper/2009.11218/) (2020)
- [Consistent Multiclass Algorithms for Complex Metrics and Constraints](https://mlsanity.com/paper/2210.09695/) (2022)
- [CascadeXML: Rethinking Transformers for End-to-end Multi-resolution Training in Extreme Multi-label Classification](https://mlsanity.com/paper/2211.00640/) (2022)
- [Conditional Probability Tree Estimation Analysis and Algorithms](https://mlsanity.com/paper/1408.2031/) (2014)
- [Propensity-scored Probabilistic Label Trees](https://mlsanity.com/paper/2110.10803/) (2021)
- [PINA: Leveraging Side Information in eXtreme Multi-label Classification via Predicted Instance Neighborhood Aggregation](https://mlsanity.com/paper/2305.12349/) (2023)
- [Long-tailed Extreme Multi-label Text Classification with Generated Pseudo Label Descriptions](https://mlsanity.com/paper/2204.00958/) (2022)

## Built on by (most cited first, 6 of 6)

- [Consistent algorithms for multi-label classification with macro-at-k metrics](https://mlsanity.com/paper/2401.16594/) (2024)
- [Curiosity Meets Cooperation: A Game-Theoretic Approach to Long-Tail Multi-Label Learning](https://mlsanity.com/paper/2510.17520/) (2025)
- [Navigating Extremes: Dynamic Sparsity in Large Output Spaces](https://mlsanity.com/paper/2411.03171/) (2024)
- [A General Online Algorithm for Optimizing Complex Performance Metrics](https://mlsanity.com/paper/2406.14743/) (2024)
- [HASTE: Hardware-Aware Dynamic Sparse Training for Large Output Spaces](https://mlsanity.com/paper/2606.01117/) (2026)
- [Exploring Imbalanced Annotations for Effective In-Context Learning](https://mlsanity.com/paper/2502.04037/) (2025)

## Abstract (arXiv)

Extreme multi-label classification (XMLC) is the task of selecting a small subset of relevant labels from a very large set of possible labels. As such, it is characterized by long-tail labels, i.e., most labels have very few positive instances. With standard performance measures such as precision@k, a classifier can ignore tail labels and still report good performance. However, it is often argued that correct predictions in the tail are more "interesting" or "rewarding," but the community has not yet settled on a metric capturing this intuitive concept. The existing propensity-scored metrics fall short on this goal by confounding the problems of long-tail and missing labels. In this paper, we analyze generalized metrics budgeted "at k" as an alternative solution. To tackle the challenging problem of optimizing these metrics, we formulate it in the expected test utility (ETU) framework, which aims to optimize the expected performance on a fixed test set. We derive optimal prediction rules and construct computationally efficient approximations with provable regret guarantees and robustness against model misspecification. Our algorithm, based on block coordinate ascent, scales effortlessly to XMLC problems and obtains promising results in terms of long-tail performance.