Coarse-to-Fine Label Attention for Long-Document Extreme Classification

Some classification problems have hundreds of thousands of possible labels, and most of those labels are rare. Two examples are assigning diagnosis codes to a hospital discharge note and tagging a Wikipedia article. For a rare label, the evidence is often a single sentence buried deep in a long document. The methods that read documents at the level of individual words for each label work well on rare labels. Label-wise attention is one such method: every label gets its own query vector, which searches the document's tokens for supporting evidence. The problem is cost. It grows with the number of labels times the document length, so it has never run on large label sets. The methods that do scale to millions of labels take a different route. They compress the document into one pooled vector, usually after cutting it to 512 tokens because standard Transformer attention costs grow with the square of the length. They then search a label tree or a sparse output layer. That route discards exactly the buried evidence that rare labels need.

We propose to keep label-wise attention but spend it only where it is needed. A sub-quadratic encoder, meaning one whose cost grows roughly linearly with length, reads the full document into token states. A label tree is then searched coarse to fine. At every level, only the few label clusters still in the search beam send queries into the token states. Per-label evidence gathering becomes affordable because its cost depends on the beam size and the tree depth, not on the total number of labels. The central bet goes beyond saving compute. We claim that token-level probing at the coarse levels of the tree is what keeps rare labels from being pruned early. Pooled-vector tree search loses exactly those labels.

Core Claim

Existing large-output systems search their label trees with a single document vector. We claim that, on long documents with long-tailed labels, replacing that vector with cluster-specific attention over full-length token states will raise the shortlist recall of rare labels. Better shortlist recall is the quantity that bounds final rare-label accuracy. This should hold without sacrificing head-label precision and at a cost that grows with beam size rather than label count.

Concretely, let $n$ be the document length, $d$ the hidden width, $L$ the number of labels, $b$ the beam width, $c$ the tree branching factor and $D$ the tree depth. Full label-wise attention costs $O(L\,n\,d)$. Our search costs

$$ O(D\, b\, c\, n\, d), $$

because at each of $D$ levels only the $b\,c$ children of the surviving clusters issue queries. With $L=10^6$, $c=32$, $b=10$ and $D\approx 4$, the saving is more than three orders of magnitude.

Relation to Prior Work

Two papers motivate the approach by showing both the value and the cost of per-label evidence. ZAGCNN combines label-wise attention with a graph network over the ICD-9 diagnosis ontology. It reports relative Recall@10 gains of 4.8% on few-shot labels and 19% on zero-shot labels on MIMIC-III, but it evaluates every label against every token. INTR gives each class its own decoder query over image patches and states outright that this cannot scale to thousands of classes. We keep their mechanism but never evaluate more than $b\,c$ queries at once.

Three papers supply the scaling machinery. None of them lets labels read tokens. XR-Transformer fine-tunes a Transformer recursively along a hierarchical label tree and reaches 54.2% Precision@1 on Amazon-3M in 29.3 hours. It still truncates input and patches the lost context with TF-IDF features, which are bag-of-words term-frequency vectors. We reuse its tree and its coarse-to-fine training schedule but replace the pooled vector with cluster queries. HASTE makes a semi-structured sparse output layer run efficiently on GPUs at 8.6M labels, using a dense head and a sparse tail. It assumes a fixed input embedding, so it is a strong competitor for the output side but ignores the sequence entirely. DEPL generates keyword "pseudo-descriptions" for rare labels and retrieves labels with a dual BERT encoder. We borrow those descriptions to initialize leaf queries for labels without natural-language names.

On the encoder side, Monarch Mixer matches BERT on GLUE with 9.1× higher throughput at 4K tokens using dense matrix-multiply primitives. Protein-Mamba shows that state-space models, which carry a compressed running summary of the sequence in linear time, work on long biological sequences. These papers supply the encoder. The file also constrains the choice. State-space models are known to lose precise recall of isolated facts compared with full attention. That is exactly our use case, so the encoder choice is an experimental variable rather than an assumption.

Research Program

The system has three parts. The first is the encoder. We will use a bidirectional Monarch Mixer as the primary encoder, with a bidirectional Mamba-style state-space encoder as a second option. Either one produces token states for documents of 4K to 8K tokens.

The second part is the label tree, built by balanced clustering of label embeddings as in XR-Transformer. Each internal node owns a small set of query vectors, around four prototypes per cluster, so that a cluster can attend to evidence for any of its heterogeneous members. Each leaf query is initialized from the label's text or its DEPL-style pseudo-description. It is then parameterized as its parent's query plus a residual. Rare leaves therefore default to their ancestors, the same parameter borrowing ZAGCNN obtains from its ontology graph.

The third part is scoring. At each level, the surviving children attend to the token states. Each score combines the attended evidence with the pooled document vector. The top $b$ clusters survive to the next level.

Training follows XR-Transformer's recursive schedule. At each level we train on the true clusters plus hard negatives drawn from the current beam. We add one extra term for rare labels. It penalizes cases where a rare label's ancestor falls just outside the beam, which directly targets early pruning.

Two analyses accompany the system. The first measures shortlist recall broken down by label frequency at every tree level. The second tests whether attention for correctly retrieved rare labels lands on the tokens that human annotators or the label description would point to. This is an interpretability check in the spirit of INTR's attribution maps.

Baselines

The naive reference point is a truncated 512-token BERT encoder with a flat one-versus-all output layer, or with the XR-Transformer tree where the flat layer cannot fit in memory. This shows how much any long-context or label-attention machinery is worth.

The strongest existing method for scaling with documents is XR-Transformer with its TF-IDF hybrid features. Those features are a real, cheap way to recover truncated context. On Amazon-3M the file reports 54.2% Precision@1 for it (XR-Transformer). For the output side, the strongest method is HASTE. We will feed it the same long-context pooled embedding our encoder produces. That isolates whether a better sparse output layer on a pooled vector matches token-level cluster attention.

For rare labels, DEPL is the reference. The file reports 6.87 macro-F1 on Wiki10-31K labels with 1 to 9 training examples, against 0.9 for X-Transformer (DEPL). On MIMIC-III, ZAGCNN runs at full label-wise attention. The file gives only relative improvements for it, so no absolute MIMIC-III number was found on Lacuna, and we will rerun it ourselves on the frequent-plus-few-shot code subset where it fits in memory.

The key ablation keeps everything in our system except the cluster queries. The tree is instead searched with the pooled long-context vector. This is "our encoder plus XR-Transformer." Any gain beyond it belongs to token-level probing.

All systems will share training data, the same tree where applicable, one GPU-hour budget per dataset, and an equal hyperparameter search. We will count beating the baselines as meeting two conditions. The first is a statistically significant gain in rare-bucket shortlist recall and rare-label macro-F1 over both the pooled-vector ablation and DEPL. The second is head Precision@1 within one point of the best baseline.

Why not just…?

Why not just truncate to 512 tokens and rely on TF-IDF features, as XR-Transformer does? This is a real threat. A rare code's key sentence often contains a distinctive term that TF-IDF captures anywhere in the document. The pooled-vector ablation with XR-Transformer's hybrid features, run on MIMIC-III where notes run into thousands of tokens, settles it. If TF-IDF recovers rare-label recall as well as token attention does, the long-context half of the claim fails and we will report that.

Why not just split the document into 512-token chunks, encode each with BERT, and max-pool? Chunking avoids the quadratic cost without a new encoder, as Chunked TabPFN does for tables. It is plausible that chunked BERT token states work as well as Monarch Mixer or Mamba states. We therefore treat the encoder as swappable. Cluster queries will be run over chunked-BERT token states as well. If chunking matches the sub-quadratic encoders, the contribution narrows honestly to the label-attention search, with the encoder chosen purely on throughput.

Why not just shortlist with the pooled vector and then rerank the top few hundred labels with label-wise attention? This is cheaper and simpler. However, reranking cannot recover labels the shortlist already dropped, and our hypothesis is that pooled shortlists drop rare labels disproportionately. The per-level, per-frequency-bucket shortlist recall measurement tests this directly. If pooled shortlists already contain rare labels at high recall, the simpler reranker is sufficient, and we will adopt it.

Why not just reweight the loss toward rare labels? Reweighting cannot create evidence the model never reads. FishNet argues this ceiling, and AnnoDPO found plain supervised losses lagging on rare Gene Ontology terms. We will still include class-balanced reweighting on every baseline so that the gain cannot be attributed to loss weighting.

Proposed Experiments

MIMIC-III is the primary testbed. It combines long notes, thousands of codes and an ontology, and it is where buried evidence matters most. Wiki10-31K provides long documents with a severe tail and a published rare-label reference.

Amazon-670K and Amazon-3M serve only as a scaling check. Their texts are short, so we expect no accuracy gain there. The question is whether the $O(D\,b\,c\,n\,d)$ cost holds at millions of labels, measured in wall-clock time and peak memory against XR-Transformer and HASTE.

We will report Precision@1/3/5, macro-F1 by frequency bucket (0, 1–5, 1–9, and head), and shortlist recall per tree level. We will also report the Information Contrast Model score from Evaluating Extreme Hierarchical Multi-label Classification, which penalizes the "safe" predictions of frequent codes that flat F1 rewards.

The decisive check is a single plot on MIMIC-III and Wiki10-31K. It shows rare-label recall of the beam at each tree level for cluster queries versus pooled vectors, at matched beam width. If cluster queries do not keep noticeably more rare-label ancestors alive at levels one and two, the mechanism is wrong regardless of final scores.

A second check sweeps document length (512, 2K, 4K, 8K tokens) across the encoder choices. It tests whether rare-label gains grow with length, and whether a state-space encoder's compressed memory loses isolated evidence that Monarch Mixer or chunked BERT retain.