Easy-First Decoding Across Taxonomic Depth

Many classification problems come with a label tree. A news story is "Economics" and then "Monetary Policy"; a butterfly is a family, then a genus, then a species. Most systems walk this tree in one fixed direction. They either go top-down, choosing the coarse class and then refining it, or bottom-up, finding the fine pieces first and composing them. In both cases an early mistake becomes a constraint that later stages cannot undo. Yet which level is easiest depends on the input. A photo may show unmistakable species markings while its sub-family is visually ambiguous. A document may name a very specific topic while its top-level category is borderline.

This note proposes a decoder that resolves the taxonomy in whatever order the model is most certain about, one decision at a time. A committed decision is pushed through the tree: accepting a label accepts its ancestors, and rejecting a label rejects its descendants. The committed labels are also fed back into the input representation before the next, harder decision is made. The strategy comes from easy-first dependency parsing, which attaches the most confident word pairs first and lets those attachments enrich the context for the rest. We move it from word order in a sentence to depth in a fixed label hierarchy. We then measure directly whether it reduces the rate at which an error at one level causes an error at another.

Core Claim

In hierarchical classification, cascading errors come from two separate things. One is committing in a fixed order. The other is conditioning later decisions on earlier ones. Removing only the first is cheap: exact scoring of every valid path does that in one pass. Our claim is that the extra value of easy-first decoding comes from the second, done in a certainty-chosen order. When the model conditions its representation on its most confident partial labeling, and trains on the states it will actually reach, it should beat both fixed-order conditional decoders and one-pass consistent models. It should also show a lower cross-level error propagation rate. If the gains disappear once exact path scoring or order-free iterative refinement is added to a flat model, the claim is false. The experiments are built to detect that outcome.

Where This Sits

The mechanism comes from the easy-first parsing line. An Efficient Algorithm for Easy-First Non-Directional Dependency Parsing makes the most confident attachment first and updates the head's features so that harder attachments see richer context. Easy-First Dependency Parsing with Hierarchical Tree LSTMs makes those updates neural, using recursive subtree encoders. It trains with a dynamic oracle, meaning the model is supervised on the best next action even after it has already made mistakes, and it reports 92.6% UAS and 90.2% LAS on the Penn Treebank. Learning What's Easy: Fully Differentiable Neural Easy-First Taggers replaces the hard choice of "what to decide next" with a constrained softmax over a running sketch of predictions. It also documents a cost: running one step per position is slow. All three work over horizontal sequences. We reuse their order-by-confidence rule, their state update and their dynamic-oracle training, and apply them to vertical label trees, which these papers never address.

The motivating evidence comes from hierarchical classification. In Hierarchical Entity Typing via Multi-level Learning to Rank, child types are scored only if the parent is accepted, so parent recall caps leaf accuracy. In A Neural Layered Model for Nested Named Entity Recognition, a missed inner entity blocks the outer one, and the authors say so explicitly. These are the two fixed directions we want to replace.

The closest existing bridge is Well Begun Is Half Done (IMAGE). It sees top-down propagation in generative hierarchical text classifiers and breaks it by randomly shuffling target label order during training. IMAGE's order is random and fixed at training time. Ours is chosen at inference time, per input, by calibrated certainty, and it is trained on the model's own trajectories.

Two further lines constrain the design. Coherent Hierarchical Multi-Label Classification Networks guarantees that a parent is scored at least as high as its children through a max-over-children module, in a single pass. Hierarchical Image Classification using Entailment Cone Embeddings gets the same consistency by summing child probabilities into parents. Both show that consistency by itself is cheap, which is why we do not claim it as our contribution. HYDRA shows that a flat encoder with one classification head per level matches complex structured models. That sets a high bar for any structured decoder.

Research Program

The model has three parts: an encoder, a decision state and a scorer.

The encoder is RoBERTa-base for text and a ResNet-style network for images. The decision state records every taxonomy node as accepted, rejected or open. At each step the scorer assigns every open node a probability of being positive, using the encoder output cross-attended to embeddings of the currently committed labels.

The "ease" of a node $v$ is its calibrated margin $e_v = |2\,\sigma(z_v / T_{d(v)}) - 1|$. Here $z_v$ is the node's logit, $\sigma$ is the logistic function, and $T_{d(v)}$ is a temperature fitted on development data separately for each depth $d(v)$. The per-depth temperature is not decoration. Coarse classes are data-rich and fine classes are long-tailed, so raw confidences are skewed by depth. Without correction the "easy" node would almost always be the root, and the decoder would silently collapse to top-down.

The decoder commits the open node with the largest $e_v$ and closes the tree around it: ancestors of an accepted node become accepted, and descendants of a rejected node become rejected. It then re-encodes and repeats until no node is open. Because one commitment usually resolves a whole chain, the number of steps is far smaller than the number of labels. We also test committing the top $m$ nodes per step, and report wall-clock latency against one-pass baselines, since the tagger paper shows latency is a real cost of easy-first decoding.

Training follows the dynamic-oracle recipe. The model rolls out its own easy-first trajectory, with some probability of keeping its own mistakes. At each visited state it is supervised with the correct labels of all open nodes that are still consistent with the committed state. This teaches it to recover from a wrong early commitment instead of amplifying it. We also build a fully differentiable variant with the constrained softmax from the easy-first tagging work, and compare it against the hard version.

The analysis part adapts the Error Propagation Rate from ReCAPA from time steps to tree depth. We define

$$\mathrm{EPR}(k \to j) = P(\text{error at level } j \mid \text{error at level } k) - P(\text{error at level } j),$$

computed on test instances. This is the excess failure probability at level $j$ caused by an error at level $k$, measured both downward ($j>k$) and upward ($j<k$). A model that truly isolates errors should drive EPR toward zero while keeping aggregate F1. We also log, per instance, the depth of the first committed decision. This shows whether the model actually departs from top-down order, and where.

Baselines

The naive reference is a flat multi-head classifier in the style of HYDRA. It uses the same encoder, one sigmoid head per level and independent thresholds. It shows what the encoder alone achieves, with no hierarchy-aware inference. HYDRA reports Micro-F1 81.96 and Macro-F1 72.74 on NYT. We will reproduce it on our encoder rather than rely on that number.

The strongest published competitor on this exact question is IMAGE, because it targets top-down propagation in hierarchical text classification head-on. It reports Micro-F1 87.69 and Macro-F1 70.77 on RCV1-V2. We found no reported result on Lacuna for IMAGE on WOS or BGC. We will run IMAGE's released recipe with the same backbone and the same number of hyperparameter trials as our model. Beating it means higher Macro-F1 on RCV1-V2 over at least three seeds, with a margin beyond seed variance, together with lower downward EPR. Macro-F1 is the metric most sensitive to rare leaves.

The consistency baseline adds the max-constraint module and its loss from C-HMCNN on top of the same encoder. That paper reports rank-based wins across 20 datasets. We found no reported result on Lacuna for C-HMCNN on RCV1-V2, NYT, WOS or BGC. For ETHEC, the relevant reference numbers come from the entailment-cone paper. The flat baseline reaches a species-level F1 of 0.4578 and the hyperbolic cone model 0.5977. The marginalization classifier reaches the best mean F1 of 0.9223, and it is the one we treat as the bar.

The fixed-order conditional decoder uses our exact architecture, but forces the commitment order to be top-down or bottom-up. Three ablations isolate the key ingredient. The first uses random order. The second commits in easy-first order but never feeds committed labels back, so there is order but no conditioning. The third drops the dynamic oracle and trains only on gold states. All models share data splits, encoder, training epochs and a matched hyperparameter search budget.

Why not just…?

Why not just add a max-constraint module and stop? It guarantees consistency in one pass, but its outputs are only as good as the base network's features. It cannot re-read the input in light of a confident decision elsewhere in the tree. If our model's gains match those of C-HMCNN on the same encoder, conditioning adds nothing, and we will say so. The EPR comparison separates the two: consistency modules make predictions coherent, but they do not necessarily make errors less correlated across levels.

Why not just score every valid path exactly on top of a flat classifier? This is the most serious threat. With a few hundred labels, summing per-level log-probabilities over all root-to-leaf paths is cheap, and it already removes any fixed commitment order. We include it as a baseline. If it matches our model, the easy-first benefit in this setting is just "avoid greedy top-down," and the representation feedback earns nothing. The no-feedback ablation, which commits in easy-first order without re-encoding, should behave like path scoring. The full model has to beat both for the claim to stand.

Why not just refine all levels in parallel for a few rounds, with no ordering? Iterative refinement conditioned on the previous round's soft predictions might capture the same benefit without choosing an order. We found no paper in the file testing this for hierarchical classification, so we build it ourselves with the same number of refinement steps as our average trajectory length. If it ties with easy-first, the contribution is iteration, not order, and the proposal narrows to that finding.

Why not just shuffle label order during training, as IMAGE does? Shuffling teaches the decoder not to lean on parent prefixes, but at inference it still commits to some order that is unrelated to the input. Our random-order ablation, trained with the same shuffling, measures what certainty-driven order adds beyond it.

Proposed Experiments

Text experiments use RCV1-V2 (4 levels, 103 labels), NYT (8 levels, 166 labels), WOS (2 levels) and BGC (4 levels). They report Micro-F1, Macro-F1, per-depth F1, downward and upward EPR, and latency. The image experiment uses ETHEC (4 levels, strongly long-tailed), reporting species-level F1 and mean F1 against the numbers above.

WOS is a built-in control. With only two levels there is little room for order to matter, so gains there should be small. Large gains on WOS would suggest the improvement comes from something other than ordering.

The decisive check is a stratified analysis. We split test instances by whether an oracle, meaning the best-calibrated flat model, finds the most confident decision at the root or deeper. The prediction is that easy-first gains, and the drop in EPR, are concentrated in the "deeper" stratum, especially on NYT and ETHEC, where depth and long tails are largest. A second check is the distribution of first-commitment depths. If the calibrated model starts at the root almost always, the method reduces to top-down, and any improvement must then come from dynamic-oracle training, which the gold-state ablation isolates.

We will accept the proposal's central claim only if three things hold together: the full model beats path scoring and parallel refinement on Macro-F1, it lowers cross-level EPR, and its gains appear where the easiest decision is not at the top.