Many classification problems have labels arranged in a tree. A news story is labelled "Economics", then "Monetary Policy", then "Interest Rates". A common modern approach reads the document and then generates the label path one level at a time with a sequence-to-sequence model. This is appealing because each decision can condition on the ones before it. It also has a well-known flaw: one early mistake on a coarse category sends every later decision down the wrong branch. The best current systems avoid this flaw by giving up the tree. Some shuffle the label order during training. Others predict every level independently with separate output layers. Either way, the model loses the ability to reason about the path as a whole.
We propose to keep the tree and change how it is trained. The approach is early update training, a technique from structured prediction (predicting outputs with internal structure, such as parse trees or label paths). During training, the model runs the same beam search it will use at test time. A beam search keeps only the top $K$ partial answers at each step. The moment the correct partial answer falls out of the beam, search stops and the parameters are updated at exactly that point. The model is never trained on the corrupted states that follow a mistake it should have avoided. Label taxonomies suit this method unusually well. Their paths are short, so search inside training is cheap. The correct path is always reachable, which removes the premature, useless updates that limited earlier machine-translation uses of the method. The central question is sharp: is cascading error in hierarchical decoders a training problem or an architecture problem?
Core Claim
A label-by-level decoder for hierarchical text classification should satisfy three conditions. It should be trained with beam search in the loop. Its updates should be placed at the level where the correct partial label set first leaves the beam, or where the model's score most strongly prefers a wrong partial answer over the right one. It should be constrained so that it only emits children of labels it has already selected. Under these conditions, we claim the decoder will:
- match or beat decoupled architectures on Macro-F1, which is dominated by rare leaf classes;
- produce zero taxonomically invalid outputs;
- make fewer "cascade" errors, meaning leaf errors caused by a wrong ancestor.
There is a mechanism behind the claim for rare classes. Early update trains fine-grained decisions only on inputs where the coarse decision survived search. The deep levels therefore learn from the same distribution of states they will see at test time. Teacher forcing, by contrast, always feeds the gold parent to the model and never shows it the states its own mistakes produce.
The claim is falsifiable against one specific competitor, which we treat as the real opponent. That competitor predicts every node independently but decodes with an exact tree-consistency constraint and is trained with a global structured loss. If it matches the early-update decoder, then conditioning on earlier labels adds nothing once training is fixed, and the cascade was an architecture problem after all.
Where This Sits
Methods we reuse. Collins and Roark introduced the halt-and-update rule for beam-search parsing (Incremental Parsing with the Perceptron Algorithm). Daumé and Marcu generalized it to any search with a bounded queue (Learning as search optimization). Wiseman and Rush carried it into neural sequence-to-sequence models with margin losses and constrained decoding (Sequence-to-Sequence Learning as Beam-Search Optimization). Yu et al. argued that the first drop-off point is often a borderline miss. They proposed updating instead where the violation is largest, the "max-violation" update (Max-Violation Perceptron and Forced Decoding for Scalable MT Training). Andor et al. showed that globally normalized beam-search models avoid the label-bias weakness of locally normalized ones (Globally Normalized Transition-Based Neural Networks). We reuse their loss forms. All of this work operates on flat token sequences or syntactic derivations, not on label taxonomies.
The closest prior work. Two papers connect search-failure updates to hierarchy.
- Müller et al. prune a morphological tag lattice from coarse to fine and apply an early update whenever the gold tag sequence is pruned (Efficient Higher-Order CRFs for Morphological Tagging). This directly teaches coarse stages not to discard the right answer. It uses linear conditional random fields over fixed token positions, with first-failure updates only.
- Zhao et al. extend max-violation training to hierarchical translation grammars (Hierarchical MT Training using Max-Violation Perceptron). They found that half their training data was unusable under the simpler phrase-based model because the gold translation was unreachable.
We differ from both on three axes. The scorer is a neural pretrained encoder-decoder. The structure is a label taxonomy, where reachability is guaranteed by construction. The object of study is the level at which updates happen, relative to where the data is scarce.
Work that motivates the gap. IMAGE diagnoses cascading error in generative classification with BART, a pretrained encoder-decoder, and responds by shuffling label paths and augmenting rare classes (Well Begun Is Half Done). HiGen adds hierarchy-aware generation (HiGen). HYDRA removes the dependency entirely by giving each level its own output layer (HYDRA), and its authors concede that this does not guarantee consistent paths. None of these trains with search in the loop.
Work that constrains the design. The Wiseman and Rush result means we must budget for cross-entropy warm-up and a schedule that grows the beam during training. It also means we must measure overhead honestly, since they report roughly 3.3× slower training than teacher forcing.
Research Program
The decoder. The decoder reads a document with a pretrained encoder. It then emits labels level by level: all selected labels at depth 1, a separator, then all selected labels at depth 2, and so on. A mask permits only children of already-selected parents. This makes multi-path taxonomies, where one document carries several paths, a single constrained sequence.
The training search. A beam holds $K$ partial label sets. At the end of each level $\ell$ we check whether the gold prefix $y_{\le \ell}$ is still in the beam. The model's scores are unnormalized, as in beam-search optimization. The loss at a level is
$$ L_\ell = \Delta(\hat y^{K}_{\le \ell}, y_{\le \ell}) \,\big[\, 1 - s(y_{\le \ell}) + s(\hat y^{K}_{\le \ell}) \,\big]_+ , $$
where:
- $s(\cdot)$ is the model's summed score of a partial label set;
- $\hat y^{K}_{\le \ell}$ is the lowest-scoring member of the beam (the $K$-th best partial answer);
- $\Delta$ is a cost that grows with how wrong the competitor is, measured as the number of mismatched labels up to level $\ell$;
- $[\cdot]_+$ means $\max(0,\cdot)$.
Three placement rules. We compare three rules for where to apply the loss.
- First-failure. Apply $L_\ell$ at the first level where gold leaves the beam, then stop.
- Max-violation. Keep the gold prefix forced through all levels. Apply the loss only at the level with the largest violation.
- Search-optimization style. Apply the loss at every failing level, resetting the beam to gold after each.
The placement question has real content here, and it pulls in two directions. In taxonomies, data is abundant at the root and scarce at the leaves. First-failure concentrates updates on coarse levels whenever they fail. Max-violation may instead push updates toward the leaves, where scores are least reliable. Which of these helps Macro-F1 is an open empirical question. Depth-weighted margins are a natural extension, but we treat them as an ablation, not the contribution.
Instrumentation. Beyond Micro-F1 and Macro-F1, we report four diagnostics.
- The cascade rate: the fraction of wrong leaf predictions whose predicted ancestor was also wrong.
- Conditional leaf accuracy: accuracy at depth $\ell$ given that depth $\ell-1$ was correct.
- The invalid-path rate: the fraction of outputs containing a child without its parent.
- Training wall-clock time relative to teacher forcing.
These diagnostics say why a method wins, not just whether it does.
Baselines
Do-nothing reference. The same encoder-decoder, trained with teacher forcing and cross-entropy, decoded with the same constrained beam. This isolates the training change from the search change. Any improvement we report must exceed this model with the identical inference procedure and beam size.
IMAGE. The strongest existing generative method, which shuffles label paths and augments rare classes (Well Begun Is Half Done). It is the most direct competitor because it attacks the same cascade inside the same model family. It reports Micro-F1 87.69 and Macro-F1 70.77 on RCV1-V2. We will quote these published figures and also retrain it on our shared encoder with a matched hyperparameter budget. Beating it means higher Macro-F1 on RCV1-V2 with no loss of Micro-F1.
HYDRA. The strongest decoupled method, with separate output layers per level over a shared encoder (HYDRA). It reports Micro-F1 81.96 and Macro-F1 72.74 on NYT, and a +2.52 Macro-F1 gain over a flat RoBERTa classifier on RCV1-V2. We run it on the same encoder class with the same tuning budget. We report its invalid-path rate alongside F1, because a model that cannot guarantee valid paths does not compete on equal terms.
Consistent-flat model. We add this baseline ourselves because it is the real threat. It uses HYDRA-style independent per-node scores and decodes with an exact tree dynamic program. The program picks the highest-scoring label set in which every selected child has a selected parent. Because the constraint is closed under ancestors, this is solvable in linear time on a tree. The model is trained with a structured hinge loss under that exact decoder. Unlike HYDRA, it guarantees valid paths. It is globally trained with exact search, so it needs no search-failure heuristic. It differs from our model only in lacking conditioning on earlier decisions. Our model beats it only if it wins on Macro-F1 or conditional leaf accuracy at matched compute.
Scheduled sampling. The same encoder-decoder, trained by sometimes feeding its own predictions back in place of gold labels. This is the cheap way to expose a decoder to its own mistakes.
Ablations. Two ablations isolate the key ingredient.
- Placement. Compare first-failure, max-violation, and every-level updates with everything else fixed.
- Unconstrained training search. Keep constrained decoding at test time but let the training beam produce invalid paths. This tests whether the benefit comes from searching the taxonomy's actual state space.
All systems share the backbone, training data, number of passes, and hyperparameter trials. We additionally report a variant of each baseline given our method's extra wall-clock time as more training steps.
Why not just…?
Why not just use separate output layers per level, as HYDRA does? HYDRA shows this is fast and strong on rare classes. On paths, however, it trades validity for accuracy: its authors concede that children can be predicted without their parents. The fair version of this objection is the consistent-flat baseline above, and it is a genuine threat. If that baseline matches our decoder, the honest conclusion is that tree-structured decoding is unnecessary once decoding is consistent. We would report this as the main finding. The conditional-leaf-accuracy diagnostic will show whether any advantage of autoregression is real, or merely an artifact of consistency.
Why not just shuffle the label order, as IMAGE does? Shuffling removes the top-down order the cascade needs, but it also removes the ability to use the parent when predicting the child. That is exactly the dependency that should help rare leaves inherit evidence from well-trained parents. IMAGE's RCV1-V2 figures give the bar. The ablation separating "same decoder, teacher forcing" from "same decoder, early update" will show whether keeping the order with the right training beats discarding it.
Why not just use scheduled sampling? It exposes the model to its own predictions but still trains on every downstream step after a mistake. That is the noise early update was designed to remove. On flat translation, beam-search optimization reached 25.48 BLEU against 23.87 for standard baselines on IWSLT 2014 German-English (Sequence-to-Sequence Learning as Beam-Search Optimization). Whether that carries over to taxonomies, where sequences are much shorter, is exactly what our scheduled-sampling baseline tests.
Why not just widen the beam at test time? Beam aggregation shows that keeping more hypotheses at inference reduces cascades in multi-hop reasoning (BeamAggR). But a teacher-forced model's scores were never trained to rank the hypotheses a beam contains. We will sweep inference beam size for the do-nothing model. If a wide beam alone closes the gap, the training change is not justified.
Why not just stack classifiers on soft parent predictions? Stacked generalization, in which lower levels are trained on held-out predictions from higher levels, learns to correct parent mistakes in scene labelling (Stacked Hierarchical Labeling). It requires multiple training rounds over held-out folds, and it does not produce a discrete, valid path. We expect the consistent-flat baseline to dominate it and include stacking only if compute allows.
Proposed Experiments
Benchmarks. The main benchmarks are the multi-path taxonomies RCV1-V2 and NYT, where exact enumeration of label sets is impossible and search is genuinely approximate. BGC (4 levels) tests depth. ENZYME tests severe imbalance; for ENZYME, no absolute reported result was found on Lacuna, since HiGen reports only relative gains over plain BART. WOS serves as a control. Its single-path, two-level taxonomy of 141 classes permits exact scoring of every path. There we can train the same decoder with exact global normalization and measure how much the beam approximation costs. No reported WOS number for IMAGE or HYDRA was found on Lacuna, so all WOS comparisons use our reimplementations.
Decisive checks. Three results would settle the question.
- Early update must lower the cascade rate relative to the teacher-forced decoder at identical inference. If it does not, the proposed mechanism is wrong regardless of F1.
- Our decoder must beat the consistent-flat model on Macro-F1 on NYT or RCV1-V2 at matched compute. Otherwise the architectural claim fails.
- On WOS, beam-trained and exactly-trained decoders should be within noise of each other. This would show the search approximation is not the source of any gain.
Cost and placement. We report training slowdown against the roughly 3.3× reported for flat translation. We expect a smaller factor because taxonomy sequences are short, but this is a measurement, not an assumption. Per-depth F1 under each placement rule answers whether updates belong where the model first fails or where the leaves are thinnest.
References
- Incremental Parsing with the Perceptron Algorithm
- Learning as Search Optimization: Approximate Large Margin Methods for Structured Prediction
- Sequence-to-Sequence Learning as Beam-Search Optimization
- Max-Violation Perceptron and Forced Decoding for Scalable MT Training
- Globally Normalized Transition-Based Neural Networks
- Efficient Higher-Order CRFs for Morphological Tagging
- Hierarchical MT Training using Max-Violation Perceptron
- Well Begun Is Half Done: An Implicitly Augmented Generative Framework with Distribution Modification for Hierarchical Text Classification
- HiGen: Hierarchy-Aware Sequence Generation for Hierarchical Text Classification
- HYDRA: A Multi-Head Encoder-only Architecture for Hierarchical Text Classification
- BeamAggR: Beam Aggregation Reasoning over Multi-source Knowledge for Multi-hop Question Answering
- Stacked Hierarchical Labeling