Extreme multi-label classification means tagging an input, such as a product page, a legal document or a Wikipedia article, with a handful of labels drawn from hundreds of thousands or millions. Systems that work at this scale treat every label as an independent point in a vector space. As a result, they routinely predict a specific tag without its obvious parent, for example "laser printer toner" without "printer supplies". A different representation fixes this by construction. Each label becomes an axis-aligned box in $d$ dimensions, broad labels get big boxes, and a document "has" a label when the document's own box sits inside that label's box. This idea, box embeddings, has only been tried on label spaces of a few thousand. Its training loss also has a known weakness: when two boxes do not overlap, their overlap volume is zero and gradient descent has nothing to follow.
Object detection hit the same weakness and solved it in a different way. Generalized Intersection over Union (GIoU) adds a penalty based on the smallest box enclosing both the prediction and the target. Disjoint boxes are then pulled together using only min, max, subtraction and division. We propose to carry that idea into high-dimensional label boxes. Done naively, it fails, because volume ratios in hundreds of dimensions shrink exponentially. We therefore restate it as a per-axis, asymmetric "generalized containment" score. We then test whether box label heads trained this way, run on top of a standard candidate-retrieval stage, can reach extreme benchmarks. The test asks whether they keep the hierarchical consistency that point-vector models lack without losing precision on rare labels.
Core Claim
The claim has three parts.
First, the obvious transplant of GIoU into $d$-dimensional box embeddings will not work for $d$ in the hundreds. Box volume is a product of $d$ side lengths, so any ratio of volumes is a product of $d$ per-axis ratios. If each per-axis ratio is $r<1$, the total is $r^d$, which underflows. The enclosing-box penalty $|C\setminus(A\cup B)|/|C|$ then sits at essentially 1 for any imperfect pair, and its gradient flattens again.
Second, a per-axis restatement keeps what GIoU offers: a non-vanishing pull between disjoint boxes, scale invariance, and no transcendental functions. It also fits classification better than the symmetric original. For an input box $X$ and a label box $Y$, write $|X_k|$ and $|Y_k|$ for their side lengths on axis $k$. Write $i_k$ for the length of their overlap on that axis, which is zero when they are disjoint there. Write $c_k$ for the length of the smallest interval covering both. The generalized containment on axis $k$ is then
$$g_k(X,Y) = \frac{i_k}{|X_k|} - \frac{c_k - |Y_k|}{c_k}.$$
This quantity equals 1 exactly when $X$ lies inside $Y$ on that axis. It falls continuously toward $-1$ as the two intervals move apart. Unlike symmetric GIoU, it stays at 1 once $X$ is nested inside $Y$. In detection, nesting is a flaw, which is why Focal and efficient IOU loss for accurate bounding box regression added center and side-length terms. In classification it is what we want: a satisfied positive should stop pushing.
Third, these boxes are cheap to score only on a shortlist. Box comparisons are elementwise min and max operations, not matrix multiplications. They therefore cannot be scored against all $L$ labels as fast as a dense layer, and we do not try to. A standard extreme classifier proposes the top $K$ labels, and the box head rescores those $K$ at cost $O(dK)$.
The training loss for a positive pair $(x,y)$ is $\frac{1}{d}\sum_k (1-g_k)$. For a sampled hard negative $y'$, it is a hinge that is satisfied once some axis is separated:
$$\ell^-(x,y') = \max\Big(0,\ \min_k g_k(X,Y') - m\Big),$$
where $m$ is a margin. Positives need containment on every axis, while a negative only needs separation on one. Ranking uses $\frac{1}{d}\sum_k \min(g_k,1)$.
The novelty lies in three choices: replacing Gumbel and softplus smoothing with an enclosing-interval penalty, making that penalty per-axis and asymmetric so it survives high dimension, and bringing box label heads to $L\ge 10^5$ through shortlisting.
Relation to Prior Work
The closest work supplies the representation we reuse. Modeling Label Space Interactions in Multi-label Classification using Box Embeddings models inputs and labels as boxes and derives label probabilities from intersection volumes. It fixes disjoint gradients with the Gumbel box process from Smoothing the Geometry of Probabilistic Box Embeddings. That model beat vector, hyperbolic and earlier box baselines on 11 of 12 datasets in mean average precision, and it recovered hidden hierarchies with AUC ≥ 0.87. However, it was evaluated only on benchmarks with at most a few thousand labels, and it subsampled label-label edges. The smoothing paper itself shows how much the disjoint-gradient fix matters: on WordNet hypernymy, F1 rose from 0.5495 for the original boxes to 0.8800 with smoothing. We keep the representation and the motivation, but replace the smoothing mechanism and change the operating regime.
Generalized Intersection Over Union: A Metric and a Loss for Bounding Box Regression. supplies the enclosing-box idea. Its follow-ups constrain how we use it. Focal-EIOU documents GIoU's nested-box stall. Alpha-IoU (Alpha-IoU) shows that the shape of the overlap loss matters. None of these works leaves two to four dimensions, and none faces the exponential-volume problem that drives our per-axis design.
On the extreme-classification side, three works supply the scaling machinery and the baselines. AttentionXML uses shallow, wide label trees with beam search. DiSMEC uses pruned one-vs-rest linear models. HASTE uses GPU-aligned semi-structured sparse output layers. All three treat labels as independent points. We use them as shortlisters and do not compete with their retrieval stage.
Two methods enforce hierarchy explicitly. Coherent Hierarchical Multi-Label Classification Networks does so with a max-constraint over a known taxonomy. HECTOR decodes root-to-leaf paths with a sequence-to-sequence model. Both need the taxonomy, and HECTOR needs costly beam decoding. Our model needs neither at test time, so the honest comparison is on partially observed hierarchies.
Finally, Evaluating Extreme Hierarchical Multi-label Classification provides the Information Contrast Model, a hierarchy-aware evaluation metric. We use it for evaluation only.
Research Program
The work has four parts.
The first part is analysis. We will show formally and in simulation that volumetric GIoU, GIoU computed in log-volume, and our axis-wise score behave differently as $d$ grows from 2 to 512. We measure gradient norm and the fraction of disjoint pairs that receive useful signal. This mirrors the simulation methodology Focal-EIOU used in two dimensions.
The second part is the model. A text encoder produces an input box from a center vector and a softplus-parameterized width vector. Each label holds a $2d$-parameter box. A frozen shortlister supplies the top $K=100$ to $200$ candidates per input; we use AttentionXML's label tree where its released configuration exists and a HASTE-style sparse head on LF-Paper2Keywords. Negatives are the shortlisted non-gold labels. If the taxonomy is available, we add an optional label-label containment term on parent-child edges. We drop it in the taxonomy-free setting.
The third part is cost. We measure the box rescoring kernel against the dense rescoring cost. If memory for $2d$ parameters per label is binding at 3M labels, we test HASTE-style grouping of label boxes into shared-width tiles.
The fourth part asks whether the learned box volumes encode hierarchy at extreme scale. We score taxonomy recovery on Wiki-LSHTC-325K and EUR-Lex.
Baselines
The naive reference point is the shortlister alone: AttentionXML's own scores, with no rescoring. On Amazon-3M, AttentionXML reports P@1 of 50.86%, which is the strongest extreme-scale number in our file, and we will reproduce it before adding anything. The box head is only interesting if it at least matches this. Beating it means a statistically significant gain in P@1 or propensity-scored P@k, or matched precision with a large drop in the rate of child-without-parent constraint violations.
The second baseline isolates representation from loss. It is a point-vector rescoring head with the same $2d$ parameters per label, trained with binary cross-entropy on the same shortlist, with the same negatives and the same tuning budget. Without it, any gain could just come from a second stage with extra parameters.
The third baseline isolates our key ingredient. It is the Gumbel box head of the Multi-label Box Model, trained on the identical shortlist with the same dimension, optimizer and hyperparameter search budget. Our loss beats it if it matches or exceeds Gumbel boxes on P@k and constraint violations while training more stably across seeds and initializations. Wall-clock is reported, but we do not expect it to decide the comparison, since both heads only score $K$ labels. As a sanity check, we also run both box losses on the original MBM benchmarks: Enron, Imclef07a and the FUN/GO genomics sets. There the published result is wins on 11 of 12 datasets in mean average precision; per-dataset numbers are not in our file.
On hierarchical data, two explicit-taxonomy baselines apply. One is C-HMCNN's max-constraint applied over the point-vector head. The other is HECTOR on EUR-Lex, which reports a 12% P@1 margin over the next method for refinement from level 3. We will reproduce rather than quote absolute values, since none appear in our file. On LF-Paper2Keywords-8.6M we report HASTE's memory footprint (12.5 GiB versus 105.6 GiB dense) as the target any added head must not substantially inflate.
Why not just…?
Why not just use Gumbel box smoothing with the same shortlist? This is the real threat. On a shortlist of $K$ labels, the cost of softplus is modest, so our efficiency argument shrinks. The case for our loss must instead rest on how it optimizes. Its gradients are exact, it has no temperature to tune, it cannot exceed probability bounds (a problem the smoothing paper fixes with ad hoc rescaling), and nested positives behave in the way we want. The matched comparison and the seed-variance study settle this. If Gumbel boxes tie, we will report the contribution as the scaling and shortlisting recipe for box heads, not as a better loss.
Why not just add a max-constraint over a standard extreme classifier? When the full taxonomy is known, C-HMCNN-style post-processing guarantees coherence cheaply, and it may well match us on EUR-Lex. Its weakness is needing the full graph. We test this by hiding 25%, 50% and 100% of the hierarchy edges during training and at test time, and scoring violations against the full hidden taxonomy. Amazon-670K, which has no taxonomy, is the regime the max-constraint cannot enter.
Why not just use one-vs-rest linear models or a better sparse output layer? DiSMEC and HASTE are strong on precision. DiSMEC trains WikiLSHTC in 6 hours on 400 cores, and HASTE scales to 8.6M labels. But both score labels independently, and box embeddings were shown to cut constraint violations relative to point models. We include them as shortlisters and as point-vector references. If they match our violation rates as well as our precision, the box head has no purpose at scale, and we will say so.
Proposed Experiments
The first decisive check is the dimension sweep. If volumetric GIoU does not degrade with $d$ in practice, the axis-wise design is unnecessary and we will drop it.
The second is the main table. It covers EUR-Lex, Wiki-LSHTC-325K, Amazon-670K and Amazon-3M, and reports P@1/3/5, propensity-scored P@k, constraint-violation rate where a hierarchy exists, and ICM on the hierarchical sets. All heads share one shortlist, and each gets a fixed budget of 20 tuning trials.
The third is the hidden-edge experiment against C-HMCNN. The fourth is hierarchy recovery from box volumes on Wiki-LSHTC, measured against the AUC ≥ 0.87 that MBM reported at small scale; a large drop would mean containment geometry does not survive extreme label counts. The fifth is a tail-label breakdown by label frequency bucket, testing whether non-vanishing pulls on disjoint rare-label boxes help where point heads struggle.
We will report throughput and peak memory throughout, so that precision gains can be weighed against cost.
References
- Focal and Efficient IOU Loss for Accurate Bounding Box Regression
- Modeling Label Space Interactions in Multi-label Classification using Box Embeddings
- Smoothing the Geometry of Probabilistic Box Embeddings
- Generalized Intersection Over Union: A Metric and a Loss for Bounding Box Regression.
- $\alpha$-IoU: A Family of Power Intersection over Union Losses for Bounding Box Regression
- AttentionXML: Label Tree-based Attention-Aware Deep Model for High-Performance Extreme Multi-Label Text Classification
- DiSMEC: Distributed Sparse Machines for Extreme Multi-label Classification
- HASTE: Hardware-Aware Dynamic Sparse Training for Large Output Spaces
- Coherent Hierarchical Multi-Label Classification Networks
- Follow the Path: Hierarchy-Aware Extreme Multi-Label Completion for Semantic Text Tagging
- Evaluating Extreme Hierarchical Multi-label Classification