Pruning LLM Re-Ranking Along Containment Chains

When a query asks for everything a concept belongs to, the relevant answers form a chain. "Robin" is a bird, a vertebrate, an animal, an organism. A product query that matches a narrow category also matches every broader one above it. The same holds in taxonomy search, ontology lookup and category-level product retrieval. In each case, if one candidate document is relevant then everything that contains it is relevant too, and if one candidate is irrelevant then everything it contains is irrelevant. Today's large language model (LLM) re-rankers ignore this. They judge each candidate on its own, or sort candidates as if relevance were a single number, and they pay one expensive model call per candidate, or more.

We propose to exploit the one-way containment structure among candidates, computed offline and independent of any query, so that an LLM judge needs to answer only a few yes/no questions per query. Every other verdict follows by transitivity. On a chain of $H$ nested candidates this turns $H$ judgments into about $\log_2 H$, which is a binary search for the boundary between relevant and irrelevant. The claim is that on hierarchical retrieval this cuts LLM calls and FLOPs by a large factor at matched accuracy. As a side effect, a hierarchy-aware re-ranker can avoid undoing the broad-ancestor recall that recent first-stage retrievers have worked hard to recover.

Core Claim

Existing efficiency work on LLM re-ranking treats candidates as unstructured competitors. REALM models each candidate's relevance as a one-dimensional Gaussian and prunes candidates whose beliefs fall low after comparisons with a pivot document. It cuts LLM inferences by 23.4–84.4% on TREC DL, but its authors did not consider asymmetric or structured relevance. LLM Optimization Unlocks Real-Time Pairwise Reranking reaches a 166x speedup, but only by collapsing the task to finding the single best document. ASRank amortizes cost by generating one hypothetical answer per query and scoring candidates against it with a small model. The match it scores is flat and symmetric.

Our proposal differs from all three in where the savings come from. They come from a logical property of the target set rather than from a cheaper judge or a statistical belief. We call the relevant set $R$ upward-closed under the candidate order: if $d \in R$ and $d \preceq d'$ (read "$d'$ contains $d$"), then $d' \in R$. When $R$ has this property, a membership query at one node settles a whole ancestor set when the answer is yes, and a whole descendant set when the answer is no. The structure that supplies $\preceq$ is the object that the region-embedding literature already knows how to learn. TaxoBell and Insert or Attach learn box embeddings, which represent concepts as nested boxes so that containment is transitive and one-directional. Nobody has used that geometry to schedule re-ranker calls.

Research Program

The system has three parts. The first is an offline candidate order. We try three sources in increasing realism: a gold taxonomy, which gives an upper bound; box embeddings of documents trained in the style of TaxoBell on the corpus's own weak hierarchy signals; and a thresholded asymmetric score from the first-stage retriever. Because this order relates documents to documents, it is computed once and reused across all queries. That makes it amortized in the same spirit as ASRank's scent, but query-independent.

The second part is a directional pointwise judge. This is a frozen instruction-tuned model that is asked a single-token question in a fixed direction, such as "Is [query concept] a kind of / covered by [candidate]?". We read out the probability of "yes", following the pointwise yes/no scoring that Efficiency-Effectiveness Reranking FLOPs found to be the most FLOP-efficient LLM re-ranking style.

The third part, and the novelty, is the scheduler. The scheduler chooses which candidate to query next: the node whose answer resolves the most still-undecided candidates, which is the midpoint of an undecided chain segment. It then propagates confident answers along the order. Judge errors are the real risk, because one false "no" high in a chain wipes out its whole subtree. The scheduler therefore propagates a verdict only when the judge's probability exceeds a confidence margin. When the margin is not met, it re-queries a neighbouring node, and it keeps a soft belief per candidate in the style of REALM's Bayesian updates. The analysis will relate expected calls to judge error rate and chain structure. We expect roughly $B \log_2 H$ calls for $B$ boundary crossings and chain height $H$, because each chain needs one binary search. That cost grows as the confidence margin tightens.

We also run a diagnostic study on a question the file raises and nobody has answered. Hierarchical Retrieval: The Geometry and a Pretrain-Finetune Recipe shows that dual encoders lose distant ancestors, a failure the paper calls "lost-in-the-long-distance". Dual encoders are retrievers that embed the query and each document separately and compare the vectors. The paper recovers the lost ancestors with a pretrain-then-finetune recipe. We ask whether a standard flat LLM re-ranker placed after that retriever pushes broad ancestors back down in favour of lexically close near-matches. If it does, a structure-aware re-ranker matters for accuracy as well as cost.

Baselines

The naive reference is the hierarchy-aware first-stage retriever alone, with no re-ranking. We use You et al.'s 64-dimensional Euclidean dual encoder trained with their recipe on the WordNet noun hierarchy. They report overall recall rising from 71.4% to 92.3%, and recall on distance-8 ancestors rising from 19.4% to 75.7%. We rerun it on the same splits and use its top-$k$ list as the candidate pool for every re-ranker. Re-ranking must improve precision and F1 over the returned set without losing that recall.

The strongest accuracy competitor is exhaustive pointwise judging with the same directional prompt and the same judge model on every candidate. It gets exactly the judgments our method could get, just without skipping any. It is run with an identical model, prompt, precision and pool size. Beating it means matching its ancestor-set F1 within statistical noise while making substantially fewer calls. The goal is a several-fold reduction, measured as FLOPs through the E2R-FLOPs closed-form estimator and reported as ranking metric per PetaFLOP (RPP) and queries per PetaFLOP (QPP). For scale, that paper reports pointwise yes/no Flan-T5-large at RPP 72.67 and QPP 111 on DL19. There is no reported result on Lacuna for any LLM re-ranker on WordNet hierarchical retrieval, so we establish these numbers ourselves.

The strongest efficiency competitor is REALM, which prunes with scalar Gaussian beliefs and pivots. It is given the same judge, the same pool, and a tuning budget for its pruning threshold equal to what we give our confidence margin. REALM reports NDCG@10 gains of 0.7–11.9% and 23.4–84.4% fewer LLM calls on TREC DL, and has no reported result on Lacuna for hierarchical retrieval. We also include a listwise prompt instructed to respect category hierarchy, and the single-pass pairwise scheme of the real-time pairwise paper extended to return a full list.

Two ablations isolate the key ingredient. The first swaps the learned order for a random order with the same edge count, which tests whether the structure itself does the work. The second keeps the gold order but turns off the confidence margin, which tests how much error propagation costs.

Why not just…?

Why not just use the hierarchy-trained dual encoder and skip the LLM? You et al. already reach 92.3% overall recall on WordNet, so a re-ranker only earns its place if it sharpens precision within the retrieved set. The dual encoder has no token-level interaction between query and document (Lin et al.). Its recipe also needs labels for hierarchy distance that web corpora lack. The no-re-rank baseline measures this directly. If the LLM's F1 gain over it is negligible, we will report that the problem is solved upstream.

Why not just prompt the judge directionally and score every candidate? This is the most serious threat, since it may be exactly as accurate as our method. We do not argue otherwise. The contribution is the number of calls needed to reach that accuracy, and the exhaustive directional baseline is built to measure precisely that. If structured scheduling cannot cut FLOPs substantially at matched F1, for instance because judge noise forces so many re-queries that the savings vanish, the idea fails. The noise-injection experiment below will show where that break-even point lies.

Why not just let REALM's uncertainty-driven pruning handle it? REALM prunes one candidate at a time by belief. It cannot conclude that one negative verdict rules out a candidate's entire subtree. On deep chains we expect it to need close to linear calls where we need logarithmic ones. On flat pools with no order both methods should behave alike, and the TREC DL check tests that.

Why not just ask a large listwise LLM to respect hierarchies? Listwise prompting is the most expensive style per E2R-FLOPs, which reports Tourrank with Llama-3.1-8B as having one of the lowest RPP and QPP scores. It is also sensitive to the order candidates appear in. Probing work (Do Language Models Encode Semantic Relations?) finds uneven encoding of structured relations in LLMs. We include it as an accuracy reference point, not as a practical competitor.

Proposed Experiments

The primary benchmark is WordNet hierarchical retrieval under You et al.'s setup, with over 82,000 noun synsets. Here the query is a synset, the relevant set is its ancestors, and the target set is truly upward-closed. We report precision, recall and F1 broken down by ancestor distance, along with LLM calls, FLOPs, RPP and QPP. Synthetic trees of varying height and width from the same paper let us check the predicted scaling of call count with height against measured counts.

The secondary benchmark is ESCI (Shopping Queries Dataset), using You et al.'s split of Exact as short-distance and Substitute as long-distance. Here the order is only approximate, so this tests the learned box order under realistic noise. For reference, the cross-encoder reaches nDCG 0.852 there, against 0.563 for BM25. TREC DL19/20 serves as a no-harm check. With an empty or near-empty order the method should fall back to exhaustive pointwise judging, with NDCG equal to it and no extra cost.

Three results would be decisive. The first is the Gap-3 diagnostic: whether a flat pointwise or listwise re-ranker lowers distance-8 recall relative to the dual encoder's 75.7%. The second is the calls-versus-F1 curve against exhaustive directional judging and REALM, across chain heights. The third is a noise-injection study that flips a controlled fraction of judge answers, to locate the error rate at which confidence-gated propagation stops saving compute. If the random-order ablation matches the learned order, or savings vanish at realistic judge error rates, we will conclude that containment structure does not pay for itself in re-ranking.