Sub-linear Scaling for Extreme Multi-label Classification

This direction is merged into another direction: label space scalability (extreme multi-label scalability). Its last version stays readable and citable here.

Version 1 of 183 papers86 conceptsfrozen 2026-10-04

In traditional machine learning, we often treat classification as a "flat" problem: given an input, the model calculates a score for every possible category and picks the winner. This "one-vs-all" approach works perfectly when you have ten categories (like MNIST digits) or even a thousand (like ImageNet).

However, as we move toward human-level scales—categorizing every medical condition in a clinical note, every product on Amazon, or every tag on Wikipedia—the number of labels ($L$) grows to hundreds of thousands or even millions. At this scale, flat classification hits a linear bottleneck: the time and memory required to train and run the model grow proportionally with $L$. As Gregory Griffin and Pietro Perona point out in Learning and using taxonomies for fast visual categorization, evaluating every class for every input becomes prohibitively slow, preventing real-time recognition.

The research direction of Extreme Multi-label Classification (XMC) seeks to break this linear dependency, moving toward sub-linear or even logarithmic scaling ($O(\log L)$).

The Geometry of Labels: Trees and Taxonomies

The most intuitive way to bypass the linear scan is to organize labels into a hierarchy. Instead of asking "Is this a Golden Retriever?", "Is this a Poodle?", and "Is this a Beagle?", a hierarchical model asks "Is this an animal?", then "Is this a dog?", and finally narrows down the breed.

Yitao Zhang demonstrated this in A Hierarchical Approach to Encoding Medical Concepts for Clinical Notes, showing that leveraging the inherent structure of medical taxonomies (like ICD-9) allows systems to handle rare conditions without a massive computational hit. When a natural taxonomy doesn't exist, researchers like Paul Mineiro and Nikos Karampatziakis use spectral clustering to automatically build trees that group labels based on their confusion matrices, effectively "routing" inputs to a small subset of candidate labels A Hierarchical Spectral Method for Extreme Classification.

Dimensionality Reduction via Compressed Sensing

Another way to think about extreme classification is through the lens of sparsity. In a dataset with a million labels, any single image or document will only ever have a few relevant tags. This sparsity allows us to use techniques from signal processing.

In Multi-Label Prediction via Compressed Sensing, Daniel Hsu and John Langford proposed projecting high-dimensional label vectors into a much lower-dimensional latent space. Instead of predicting $L$ labels, the model predicts a small number of "compressed" features. These features can then be decoded back into the original label space. This reduces the number of required predictors from linear to logarithmic, providing a theoretical path to handle massive label sets with minimal memory.

Similarly, Jason Weston and Samy Bengio introduced WSABIE Large scale image annotation: learning to rank with joint word-image embeddings, which maps both images and labels into a shared low-dimensional embedding space. Finding the right label then becomes a "nearest neighbor" search rather than an exhaustive classification task.

The Specialization Paradox

A recurring tension in this field is the trade-off between label-specific features and scalability.

Intuitively, a model should look for different features to identify a "Cat" (whiskers, ears) than it does for "Politics" (keywords like 'election' or 'senate'). Algorithms like REEL Multi-Label Learning with Regularization Enriched Label-Specific Features and LIMIC Label Specific Multi-Semantics Metric Learning for Multi-Label Classification generate custom feature sets or distance metrics for every individual label.

While Min-Ling Zhang and Jun-Xiang Mao show that this specialization significantly boosts accuracy, it re-introduces the linear bottleneck. If every label requires its own unique transformation or attention block (as in ESA-Net), the system once again becomes computationally prohibitive at extreme scales.

Scaling to 100 Million Labels

The current frontier involves combining these insights—embeddings, hierarchies, and efficient optimization—to handle industrial-scale problems. Kunal Dahiya and colleagues developed SiameseXML SiameseXML: Siamese Networks meet Extreme Classifiers with 100M Labels, which uses Siamese networks to ingest label metadata (like text descriptions). By using a multi-stage pipeline that first narrows down the label space and then applies high-precision classifiers, they demonstrate that it is possible to provide accurate, real-time tagging even when the "menu" of possible labels is 100 million items long.

Papers in this version

Showing 60 of 83 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sub_linear_scaling_for_extreme_multi_lab_8d61ee5c,
  title = {Sub-linear Scaling for Extreme Multi-label Classification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sub-linear-scaling-for-extreme-multi-label-classification/rdr_8d61ee5c20cd44aba847603a7cfb13e2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_sub_linear_scaling_for_extreme_multi_lab_8d61ee5c_v1,
  title = {Sub-linear Scaling for Extreme Multi-label Classification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sub-linear-scaling-for-extreme-multi-label-classification/rdr_8d61ee5c20cd44aba847603a7cfb13e2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}