Revocable Beams: Letting Deeper Levels Overturn Early Commitments in Hierarchical Decoding

Many models now produce structured outputs one level at a time. A recommender writes an item's identifier as a coarse cluster code followed by finer codes. A text classifier writes a path through a label taxonomy. Beam search is the usual decoding method here: it keeps the $k$ best partial outputs at each step and discards the rest. Its failure mode in these hierarchies is stark. In generative recommendation, between 91.9% and 96.6% of retrieval failures happen in the first two decoding steps, because the correct coarse prefix falls out of the beam and its whole subtree becomes unreachable (TAAL). Beam search never revisits a discarded prefix, even when later steps make it obvious that the surviving prefixes are wrong.

We propose to give beam search a way to change its mind. A small head on the decoder, which we call the revocation head, reads the model's state one level after a commitment and predicts whether the parent prefix was a wrong turn. When it fires, the hypothesis's beam slot is handed back to the best previously pruned sibling at the shallower level, and the total compute budget stays fixed. The head is trained the way stacked hierarchical labeling trains its child classifiers (Stacked Hierarchical Labeling), on realistic upstream mistakes. Here those mistakes are the actual beam-search errors that cross-fitted copies of the decoder make on held-out data, not random corruption. The bet is that deeper levels carry evidence about whether shallower choices were right, and that this evidence can be learned and used during search rather than after it.

Core Claim

Under a matched budget of decoder forward passes, a learned revocation signal will recover a substantial fraction of correct coarse prefixes that standard beam search prunes. It will do so in two very different hierarchical regimes:

  • Top-down semantic-ID recommendation. Here the failure is the early-pruning cliff.
  • Bottom-up (child-to-parent) hierarchical text classification. Here the failure is that a wrong leaf contaminates every ancestor generated after it (RADAr).

The claim is specific about the training signal. The gain should come from training on the decoder's own out-of-fold beam errors. It should not come merely from widening early beams, from untrained confidence signals, or from generic prefix noise. If depth-dependent beam widths at equal compute match the method, the claim fails.

Relation to Prior Work

Four papers motivate the problem, and none of them revoke a commitment once it is made.

  • TAAL measures the early-pruning cliff on hierarchical semantic identifiers. It attacks the cliff before search, by training the first two levels toward a soft, mode-covering target, and after search, with PMI re-ranking (dividing a candidate's probability by its prefix's marginal frequency). Its own ablations show the re-ranking alone helps little, because pruned subtrees cannot be re-ranked. Our method acts inside search and is complementary: it can sit on top of a TAAL-trained model.
  • BeamAggR keeps top-$k$ answers at every node of a question tree so that a rank-1 mistake can be outvoted higher up. Its beams are static and it never reopens a dropped candidate.
  • Gambit prunes and re-branches whole reasoning traces using a hidden-state probe. Its thoughts are flat, its probe judges the current trace rather than an ancestor decision, and the paper notes that a mis-scored early step is lost for good.
  • Flow-of-Options lets a downstream option survive a bad upstream pairing through a max-update rule. It depends on executing code for scores, which our setting lacks.

Two papers supply method. Stacked Hierarchical Labeling gives the out-of-fold training recipe: child classifiers learn to distrust parent outputs because they are trained on held-out parent mistakes. Its pipeline is feed-forward, however, and parents are never revised. We move this recipe into an autoregressive beam and add revision. RADAr gives a strong bottom-up decoder for hierarchical text classification and an honest open problem: an error at the first, leaf-level step propagates into all of its ancestors.

Two papers constrain the design.

  • Revisiting HTC shows that flat BCE classifiers, which predict every label independently, are hard to beat on shallow benchmarks such as Web of Science. So we must evaluate on deep taxonomies and with hierarchical metrics, or we risk measuring nothing.
  • When are likely answers right? finds that sequence probability and correctness often diverge. This is why we expect a trained correctness-oriented signal to add information beyond cumulative log-probability. It is also why we test an untrained confidence signal as a control.

Research Program

Building the training data. We split the training set into $F$ folds and train $F$ copies of the hierarchical decoder, each on all folds but one. Each copy runs beam search at the deployment beam width on its held-out fold. We log every hypothesis state at every level and label it by whether its prefix up to the previous level is on the gold path. The resulting states have exactly the error distribution the deployed decoder will produce. That distribution is concentrated at levels one and two for semantic identifiers and at the leaf step for bottom-up classification.

The revocation head. The head $r_\theta(x, y_{\le l+1})$ is a small network on the final decoder state after emitting level $l+1$. It outputs the probability that $y_{\le l}$ is off the gold path, given input $x$. It is trained with cross-entropy on the logged states, with the base decoder frozen.

Search with revocation. Beam search ranks hypotheses by

$$s(y_{\le l+1}) = \sum_{j \le l+1} \log P(y_j \mid y_{<j}, x) + \lambda \log\big(1 - r_\theta(x, y_{\le l+1})\big),$$

where $\lambda$ is tuned on validation data. The search also keeps a small reserve buffer of the best $m$ pruned prefixes per level, together with their cached key-value states. When a hypothesis's revocation probability exceeds a threshold $\tau$, its slot goes to the best reserve prefix at the shallowest flagged level, and that prefix is re-expanded. Every re-expansion is charged against a fixed budget of decoder forward passes, so revocation competes for the same compute as standard search.

Analysis. We will measure per-level gold-prefix survival and the recovery rate, defined as the fraction of gold prefixes pruned by standard beam search that revocation restores. We will also measure how well the head's predictions are calibrated by level.

Baselines

Standard beam search. The do-nothing reference is plain beam search with uniform width on the same trained decoder. Beam widths are $B \in \{5, 10, 20\}$, as in TAAL's pressure regime. Greedy decoding is reported as a floor.

Strongest recommendation competitor: TAAL. This is TAAL on Amazon Beauty, Amazon Instruments, and Yelp, which reports relative NDCG@10 gains of 39.5%, 6.7%, and 28.6% over its baseline. The file gives no absolute NDCG@10 values, so we will reproduce TAAL with its T5 backbone and leave-one-out protocol. We will then run revocation both against TAAL and on top of TAAL. Beating it means higher NDCG@10 and Recall@10 at equal forward passes, averaged over five seeds, since TAAL reports a single seed.

Strongest classification competitor: RADAr. This is RADAr, which matches HBGL's Micro-F1 of 87.23 on RCV1-V2. On the deep Hierarchical WikiVitals taxonomy, the strongest reported number in the file is 90.97% hF1 AUC for logit-adjusted conditional softmax (Revisiting HTC). The flat BCE baseline in the same paper scores 89.23%. We retrain RADAr in both label orderings on RCV1-V2, NYT, and Hierarchical WikiVitals, and add beam search and revocation under the same budget. Beating the baseline means exceeding the reproduced RADAr Micro-F1 and the 90.97% hF1 AUC on Hierarchical WikiVitals. Every comparison uses the same encoder and the same hyperparameter-search budget.

Allocation control. A depth-scheduled beam spends the same total forward passes as revocation but distributes them as wider beams at the fragile levels. Its per-level widths are tuned on validation data with the same search budget we give $\lambda$ and $\tau$.

Ablations. Four ablations isolate the key ingredient:

  • an untrained revocation signal, using the entropy or maximum probability at level $l+1$;
  • a head trained on randomly corrupted prefixes instead of out-of-fold beam errors;
  • the trained head used only as a re-ranking term, with no reserve re-expansion;
  • the trained head used only for re-expansion, with no score term.

Why not just…?

Why not just widen the beam at the first two levels? This is the most serious threat. If the gold prefix is usually ranked just outside the beam, a wider early beam captures it more cheaply than any learned signal. The depth-scheduled control at matched compute tests this directly. TAAL's observation that gains concentrate at narrow beams suggests the gold prefix is often ranked far below the cutoff under a popularity-collapsed model. That would favor a signal that uses deeper evidence. We will report the distribution of gold-prefix ranks so readers can see which regime holds. If the scheduled beam matches revocation, we will report that as the finding.

Why not just use the model's own confidence at the next level as the revocation signal? An untrained entropy signal costs nothing and may capture much of the effect. But sequence probability is a poor proxy for correctness (When are likely answers right?), and a model collapsed onto popular prefixes can be confidently wrong beneath them. The entropy ablation measures how much the trained head adds. If the head adds little, the method simplifies to confidence-triggered backtracking, which would still be a useful result.

Why not just train with scheduled sampling or random prefix noise? Generic corruption teaches robustness to errors the deployed decoder does not actually make. Stacked labeling's argument is that the noise must match the test-time error distribution (Stacked Hierarchical Labeling). The random-corruption ablation tests whether this matters in autoregressive decoding.

Why not just re-rank the final beam with a verifier or PMI? A re-ranker cannot restore a subtree that was already pruned, and TAAL's ablation found PMI calibration alone gives only minor gains. The re-ranking-only ablation quantifies how much of our effect requires re-expansion.

Why not just use a flat classifier for hierarchical text classification? On shallow taxonomies this may tie, as Revisiting HTC found on Web of Science. That is why the decisive classification tests use NYT and Hierarchical WikiVitals, where flat BCE trails conditional modeling.

Proposed Experiments and Decisive Checks

Recovery on semantic-ID recommendation. On Amazon Beauty, Instruments, and Yelp, we first reproduce the early-pruning cliff. We then report gold-prefix survival at levels one and two, the recovery rate, NDCG@10, and Recall@10, all at matched forward passes. The decisive check has two parts:

  • revocation must beat the depth-scheduled beam at equal compute, both with and without TAAL training;
  • recovered items must come mostly from gold prefixes ranked well outside the beam, not just past the cutoff.

Bottom-up classification. On RCV1-V2, NYT, and Hierarchical WikiVitals, we test whether a revocation head reading the parent-level state can overturn a wrong leaf. We measure Micro-F1, hF1 AUC, and the fraction of leaf errors corrected. The decisive check is that leaf-error correction rises with taxonomy depth, which is where RADAr's exposure-bias problem bites hardest.

Necessity of out-of-fold errors. Across both regimes, the head trained on random corruption must underperform the head trained on out-of-fold beam errors. If it does not, the stacked-generalization component is unnecessary.

Cost. We report wall-clock overhead of the reserve buffer, its memory footprint, and results with five seeds and confidence intervals.