Retrieve-and-Revise: Parallel Label-Set Refinement in a Compressed Space for Extreme Classification

Many prediction tasks ask a model to pick a small set of correct tags from a catalog of hundreds of thousands or millions, such as Wikipedia categories or Amazon product links. This is extreme multi-label classification. Two families of methods dominate. Discriminative methods score each label separately and take the top few, which is fast but treats labels as if they were chosen independently. Generative methods write the label set out one label at a time, which captures how labels depend on each other but is slow and forces an arbitrary order onto what is really an unordered set. We propose a third route. The model predicts a short continuous "query" vector for the whole label set. It uses that vector to retrieve a small pool of candidate labels from a nearest-neighbor index. It then revises both the vector and the chosen set in parallel over a few steps, so that each step can surface labels the first guess missed and drop redundant ones.

The bet is narrow and testable. Refining in a compressed space should reach correct labels, especially rare ones, that a one-shot shortlist never contained. Because each step only touches about a hundred retrieved labels rather than all $L$, the cost of a step does not grow with catalog size. If this holds, it gives a non-autoregressive generator (one that emits the whole output at once rather than token by token) that runs at the scales where autoregressive generators like XLGen become expensive and dense label heads hit memory limits.

Core Claim

A label set can be predicted by iterating in a low-dimensional query space, using retrieval feedback rather than full-catalog scoring at each step. On extreme benchmarks this should beat both one-shot embedding retrieval and shortlist-then-rerank pipelines at equal compute. The gain should come specifically from correct labels that enter the candidate pool only after refinement moves the query. The claim fails if a reranker given the same compute over a larger one-shot shortlist matches it.

What exists and where this sits

Three prior works shape this proposal, each in a different role.

A Study on the Autoregressive and non-Autoregressive Multi-label Learning motivates it. That paper builds a variational latent-variable model that predicts the set size up front and decodes all labels in parallel. It reports 64.63% versus 27.88% Precision@3 against a sequence-to-sequence model on Wiki10-31K. Its refinement, however, alternates between the latent vector and indicators over the full label space, so each step costs $O(L)$. It stops at 31K labels. It also concedes that autoregressive models keep an edge on Precision@1.

Iterative Refinement in the Continuous Space for Non-Autoregressive Neural Machine Translation supplies the method. It refines translations by walking an 8-dimensional latent with a learned score (gradient-predicting) network and decodes to tokens only once. It reports a 6.2x speedup for a 0.9 BLEU loss and less repetition than token-space refinement. That approach is "blind": the refiner never sees what the current latent decodes to. In a 31K-token vocabulary this is tolerable. In a multi-million-label catalog, a single final decode from an unguided latent is exactly the one-shot embedding retrieval we argue is insufficient. Our change is to give the refiner cheap, sublinear feedback by retrieving the top $m$ labels at each step.

The label-compression literature constrains the design. Scalable Label Distribution Learning for Multi-Label Classification and Delving Into Generalizable Label Distribution Learning map inputs to a fixed low-dimensional Gaussian label space and decouple training cost from label count. Their decode is static nearest-neighbor matching, evaluated only up to roughly a thousand labels. This is our zero-refinement ablation. The SLDL authors also report that asymmetric structure helps less on symmetric fine-grained data such as CUB, which warns against relying on asymmetric metrics as the source of gains.

Cluster-Guided Label Generation in Extreme Multi-Label Classification (XLGen) shows that generation helps tail labels at 500K scale. It is autoregressive, though, and depends on frequency ordering, which conflicts with the unordered-set argument of Barezi et al. We resolve that conflict by never ordering labels. Frequency information instead enters through a head-tail split of the candidate pool, borrowed from APLC-XLNet and HASTE.

Research Program

Each label $j$ gets an embedding $e_j \in \mathbb{R}^d$, with $d$ around 256. The embedding combines an encoding of the label's text with a learned residual, and all embeddings are stored in an approximate nearest-neighbor index. An input encoder produces a representation $h(x)$, an initial query $q_0$, and a predicted set size $\ell$.

The state at step $k$ is the query $q_k$ together with a candidate pool $P_k$. The pool is the union of the labels currently selected and the $m$ nearest labels to $q_k$, with $m \approx 100$. A small set transformer (non-causal attention over the pool's label embeddings, conditioned on $h(x)$) outputs two things: a keep score $s_j$ for every pool member, and a query update. The update is

$$q_{k+1} = q_k + g_\theta\big(h(x), q_k, \{e_j\}_{j \in P_k}\big).$$

Here $g_\theta$ is the refinement network and the bracketed term is the set of pool embeddings. After the update, the selected set becomes the top $\ell$ labels in the pool by $s_j$. Selected labels can be dropped at later steps, so the procedure revises a whole set rather than appending to a sequence. A step costs one index lookup plus attention over about $m+\ell$ vectors. Total cost is $K$ such steps, with $K$ between 2 and 6, and is independent of $L$ apart from the logarithmic cost of the index.

Training follows the denoising recipe of continuous-space refinement. We corrupt the true set by deleting labels and inserting distractors drawn from the same label clusters, a deliberately hard corruption, and form the corresponding pool. The network is trained to output keep scores matching the true set and a query move toward the region of embedding space holding the missing labels. Supervision for the move is a contrastive loss that pulls $q_{k+1}$ toward missing true labels and away from distractors.

Same-cluster distractors are the extreme-classification analogue of the "stuttering" failure in translation: a top-k list crowded with near-synonyms from one cluster. We therefore measure redundancy directly. Head labels are kept in a small dense head scored once, so the refiner spends its pool budget on the tail. No label order, distillation teacher, or full-catalog score appears anywhere in training or inference.

Baselines

The naive reference point is one-shot latent retrieval. We use the same encoder and label embeddings, predict $q_0$, and return the top $\ell$ nearest labels. This is the regime of SLDL's static decode (Scalable Label Distribution Learning), scaled up. It is exactly our method with $K=0$, so any gain over it is attributable to refinement.

The strongest discriminative competitor is a sparse one-vs-all head trained with HASTE. HASTE is the only method in the file reported at 8.6M labels, and it trains such heads in 12.5 GiB versus 105.6 GiB dense. We pair it with APLC-XLNet-style head-tail clustering on the mid-scale sets. Both use our encoder backbone and the same training-data passes. The file reports speed and memory for HASTE but no precision figure, and no reported result found on Lacuna for HASTE or APLC-XLNet Precision@k on Amazon-670K or Wiki-500K, so we reproduce both.

The strongest generative competitors are XLGen, run with its cluster guidance and frequency ordering on Wiki10-31K and Wiki-500K, and a reimplementation of the non-autoregressive latent-variable model. For the latter, the reported reference is Precision@3 of 64.63% on Wiki10-31K. Our reimplementation must reproduce that number before any comparison is treated as valid.

Beating the field means two things. First, higher Precision@k and propensity-scored precision (precision that up-weights rare labels) than the HASTE head at matched or lower per-query GPU latency. Second, higher tail precision than XLGen at several-fold lower latency.

Two ablations isolate the key ingredient. Blind refinement removes retrieval feedback, so the refiner sees only $h(x)$ and $q_k$, as in continuous-space NMT refinement. Frozen-pool refinement keeps the feedback but never re-queries the index, so the pool is fixed at step 0. Every method receives the same hyperparameter search budget in GPU-hours.

Why not just…?

Why not just retrieve a bigger shortlist once and rerank it with a set-aware model? This is the most serious threat. A one-shot shortlist of size $Km$ with the same set transformer as reranker costs about the same as $K$ refinement steps. The frozen-pool ablation and a matched-compute "rerank top-$Km$" baseline test it directly. The proposal survives only if refinement wins on tail labels and if those wins are explained by correct labels whose rank under $q_0$ lies beyond $Km$. If the matched-compute reranker ties, we will report that the benefit comes from set-aware reranking rather than query movement, and simplify the method accordingly.

Why not just use a sparse one-vs-all head, since HASTE already trains millions of labels on one GPU? It is cheap and strong, but it scores labels independently, so its top-k cannot coordinate a set. The file's evidence for coordination mattering is weak: Barezi et al. beat only SLEEC and FastXML, by 2–6%. We therefore treat this as open. The redundancy metric (fraction of top-$\ell$ labels from the dominant cluster) and full-set F1 will show whether independent scoring actually crowds sets, and on which benchmarks.

Why not just generate autoregressively, as XLGen does, which already helps tail labels? Latency grows with set length and depends on an imposed order. Barezi et al. also report sequence-to-sequence collapse at 31K labels. The caveat is that autoregressive decoding may keep its Precision@1 edge. We report Precision@1 separately and do not average it away. If we lose there, a hybrid that takes the top head label from the dense head is a cheap fix that we will test.

Decisive Experiments

The benchmarks are Wiki10-31K for comparability with prior non-autoregressive work, then Wiki-500K, Amazon-670K, and Amazon-3M. LF-Paper2Keywords-8.6M is used only to confirm that per-query latency stays flat as $L$ grows. Metrics are Precision@1/3/5, propensity-scored precision@k, nDCG@k, set-level F1 using the predicted $\ell$, the redundancy rate, and GPU milliseconds per query.

The single most important analysis is pool provenance. For every correct label in the final set, we record the step at which it first entered the pool and its rank under $q_0$. The core claim predicts that a substantial share of correct tail labels have $q_0$-rank beyond $Km$, and that blind refinement recovers few of them.

Two further checks round this out. Precision is plotted against $K$; it should rise and then saturate within a handful of steps, as in parallel refinement for translation. If it is flat from $K=0$, refinement is not doing work. Finally, a symmetric-relation control on a fine-grained subset tests whether gains disappear where label structure is weak, mirroring the CUB caveat from Delving Into Generalizable Label Distribution Learning.