PaperlayerView exact revision on arXiv

Source-linked AI summary

Tree Navigation Without LLM Summaries: A Matched-Cost Study of Hierarchical Retrieval for Long-Document QA

Priyank Jayraj, Poonam Goyal, Navneet Goyal

arXiv:2610.06902v1cs.CLcs.IR

TL;DR

Flat retrieval can miss complementary evidence across long documents, and summary-tree retrieval combines navigation with generated summary content. NavTree uses a leaves-only tree without LLM indexing calls; it leads matched-cost hierarchical retrieval, ties the strongest flat baseline on QuALITY, and is the only hierarchical method to significantly beat a flat method on multi-hop QA.

  • Problem

    For long-document questions spanning multiple parts, flat top-k retrieval can cluster on one region and miss complementary evidence, while summary-tree retrieval combines navigation with generated summary content.

    Source: §1 · p. 1

  • Method

    NavTree builds a deterministic balanced segment tree and uses top retrieved leaves to guide a hybrid lexical-and-dense walk that emits only leaf chunks, with no LLM calls at indexing.

    Source: §1 · p. 2

  • Results

    NavTree leads the hierarchical class in 6 of 8 headline cells, ties the BM25 + SBERT hybrid at every QuALITY budget, and is the only hierarchical method to significantly beat a flat method on multi-hop QA.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The main benefit of summary trees in long-document QA can come from navigation rather than generated summary content, with token packing explaining NavTree’s multi-chunk advantage.

    Source: §7 · p. 9

    With BGE-large on QASPER@1024, hybrid-flat overtakes NavTree by +0.004, within the 0.026 CI half-width.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Retrieval-augmented generation grounds language models in external context, but for long documents flat top-$k$ retrieval can cluster on a single region and miss complementary evidence. RAPTOR-style summary trees address this by recursively clustering chunks and using a language model to summarize each cluster at indexing time, then ranking summary nodes alongside raw chunks at query time. We show the main benefit of summary trees in long-document QA can come from navigation rather than the generated summary content. We introduce NavTree, a leaves-only retriever that builds a deterministic balanced segment tree over chunks (zero language-model calls at indexing) and uses the tree purely as a navigation scaffold: a hybrid lexical-and-dense frontier walk, anchored on top retrieved leaves, descends from the root and emits only leaf chunks to the reader. On a matched-cost evaluation against flat retrievers and an extractive re-implementation of RAPTOR, NavTree is the strongest matched-cost hierarchical retriever in our evaluated grid and ties the strongest flat baseline. On long-document multi-hop QA, it is the only hierarchical method that significantly beats BM25 on a class-vs-class basis, corroborated by a reader-free retrieval-recall check. A matched-reader replication of the published abstractive RAPTOR variant, given strong cluster summaries, still loses to NavTree at every multi-chunk budget, at zero indexing cost. The ranking carries across stronger and open-weight readers, a stronger encoder, and a full factorial that isolates leaves-only emission as the structural lever.

1 Introduction

Flat retrieval can miss complementary evidence in long-document QA, while summary trees combine navigation with generated content. NavTree tests whether navigation alone can deliver the benefit, using a leaves-only tree and no LLM indexing calls.

Approach and comparison

  • NavTree uses a balanced segment tree, top-Kℓ leaf anchors, a hybrid BM25-and-dense frontier walk, and leaf-only output with flat tail-fill, avoiding LLM calls at indexing.The comparison uses a matched-cost extractive RAPTOR re-implementation rather than a cross-paper comparison with the original abstractive RAPTOR result.Source: §1 · p. 2

Main results

  • NavTree leads the hierarchical class in 6 of 8 headline cells, beats RAPTOR-Extractive by 4.4 and 5.4 points on QuALITY@1024 and @2000, and ties the strongest flat baseline at every QuALITY budget.The paired comparison with the BM25 + SBERT hybrid is not significant (p > 0.1).Source: §1 · p. 2
  • Across four multi-hop QA datasets, NavTree is the only hierarchical method that significantly beats a flat method, with +0.077/+0.069 F1 over BM25 on 2WikiMQA@1024/@2000.Reader-free recall is also highest on 2WikiMQA@2000 (94.9%) and MuSiQue@2000 (68.5%).Source: §1 · p. 2

Mechanism

  • Per-node summaries beat leaves on QuALITY (55.7% vs. 50.4%), but at multi-chunk budgets summary nodes can displace distinct-subtree leaves by repeating information from their best-leaf descendants.This token-packing effect is the proposed explanation for NavTree’s multi-chunk gains.Source: §1 · p. 2

Robustness

  • The ranking persists with gpt-4o, open-weight readers, and a stronger encoder; a 24-factorial isolates leaves-only emission as the structural lever and cross-encoder reranking as the dominant retrieval-side lever.The matched-reader RAPTOR replication also loses to NavTree at every multi-chunk budget.Source: §1 · p. 2

2 Related Work

Prior tree-style retrievers commonly include summary nodes in retrieved context, while related RAG work also changes retrieval units, budgets, and retrieval timing. NavTree’s architecture instead uses internal nodes for routing and returns leaf chunks.

Hierarchical retrieval

  • Related hierarchical retrievers, including RAPTOR and tree-style methods it inspired, include LLM- or rule-derived summary nodes in retrieved context.NavTree’s stated distinction is to use tree topology without retrieved summaries.Source: §2 · p. 2

Other RAG, budgets, and reranking

  • Other RAG work advances retrievers, readers, and orchestration, reorganizes retrieval units with HIPPORAG, GRAPHRAG, and LON-GRAG, or triggers retrieval dynamically.The passage characterizes these lines as largely orthogonal to leaves-only navigation.Source: §2 · p. 2
  • Budget-aware methods use redundancy-aware scoring or post-hoc compression, whereas NavTree narrows the search space before selecting content.Source: §2 · p. 2

NavTree architecture

  • Figure 1 separates offline tree construction from query-time navigation: internal nodes route the walk, and only selected raw leaf chunks reach the reader.A flat top-k tail-fill can supplement the selected leaves.Source: Figure 1 · p. 3

Other RAG, budgets, and reranking

  • Reader-focused work studies how readers use retrieved context; NavTree’s leaves-only design avoids paraphrased intermediate text.Source: §2 · p. 3

3 Method: NavTree

NavTree builds a deterministic segment tree over chunks, anchors navigation on retrieved leaves, and uses a hybrid frontier walk to select raw leaf chunks under a token budget.

3 Method: NavTree

  • NavTree combines a deterministic balanced segment tree, Steiner-active anchoring on FAISS top-k leaves, a hybrid frontier walk that returns only leaves, and flat top-k tail-fill.Source: §3 · p. 3

3.1 Segment tree construction

  • The balanced binary tree stores each raw chunk, its normalized SBERT embedding and token cost at leaves, plus deterministic concatenations of representative descendant sentences and their embeddings at internal nodes.The tree has 2n − 1 nodes and depth ⌈log2 n⌉; construction uses zero LLM calls.Source: §3.1 · p. 3

3.2 Steiner-active anchoring

  • Top-Kℓ leaf anchors define the Steiner-active mask as the union of root-to-anchor paths, pruning other nodes while guaranteeing each anchored leaf remains reachable.Source: §3.2 · pp. 3–4

3.3 Hybrid frontier walk + flat fill

  • The frontier walk mixes dense cosine and BM25 span scores, splits internal nodes without emitting them, then fills remaining budget from globally ranked unselected leaves.An optional cross-encoder rerank pools selected leaves and hybrid extras, then greedily packs them under the same budget.Source: §3.3 · p. 4, §3.2 · p. 4

4 Experimental Setup

The evaluation compares retrieval methods under shared chunking, embeddings, readers, prompts, and budgets. It includes a matched-cost extractive RAPTOR baseline, benchmarks, and per-cell statistical tests.

Datasets

  • The matched-cost grid covers QuALITY, QASPER, NarrativeQA-summary, and LongBench-SD; the multi-hop evaluation adds HotpotQA and 2WikiMQA.Sample sizes and dataset-specific task measures differ across benchmarks.Source: §4 · p. 4

Methods

  • Methods share 100-token sentence-aware chunking, an all-MiniLM-L6-v2 embedder, a gpt-4o-mini reader at T=0, a prompt template, and budgets of 256, 512, 1024, and 2000.RAPTOR-Extractive replaces RAPTOR’s GPT-3.5 cluster summaries with deterministic extractive summaries; the grid uses NavTree defaults Kℓ=10 and α=0.35.Source: §4 · p. 4

Baseline fairness

  • Two fairness checks show RAPTOR-Extractive summaries beat their best-leaf descendants on QuALITY (55.7% vs. 50.4%) and the baseline beats NavTree on QASPER at 256/512.Source: §4 · p. 5

Statistics

  • Per-cell bootstrap 95% confidence intervals use 10,000 resamples, and paired sign tests mark differences from parity at p < 0.01.Table 1 groups methods by flat versus hierarchical class; QuALITY and QASPER worst-case CI half-widths are ±2.0pp and ±0.026, respectively.Source: §4 · p. 5, Table 1 · p. 5

5 Results

NavTree leads the hierarchical class in the matched-cost headline grid and matches the strongest flat baseline on QuALITY. It also outperforms extractive RAPTOR in long-document tests, including multi-hop QA, while avoiding LLM-summary indexing costs.

5.1 Strongest matched-cost hierarchical retriever; at parity with flat

  • NavTree leads the hierarchical class in 6 of 8 headline cells and matches the BM25 + SBERT Hybrid on QuALITY at every budget.The QuALITY wins over RAPTOR-Extractive at 1024 and 2000 tokens are significant; the flat-baseline differences are within ±1.5 pp with p > 0.1.Source: §5.1 · p. 5

5.2 Matched-reader RAPTOR comparison and reader scaling

  • At budgets ≥512 tokens, NavTree beats both matched-reader abstractive RAPTOR variants; stronger gpt-4o summaries narrow but do not close the gap.At 1024 tokens, the gap versus abstractive RAPTOR with gpt-4o is +4.9 pp (HARD: +6.9 pp); at 2000 tokens it is +1.1 pp (HARD: +1.9 pp). At 256 tokens, that RAPTOR variant wins by +7.5 pp.Source: §5.2 · p. 5, Table 2 · p. 6

5.3 Long-document stress test: multi-hop and full-book QA

  • NavTree leads extractive RAPTOR on three of four long-document datasets at 2000 tokens, and is the only hierarchical method to significantly beat BM25 or SBERT on a multi-hop cell.On 2WikiMQA, it beats BM25 at 1024 and 2000 tokens and SBERT-flat at 512 tokens; MuSiQue methods cluster within 0.022 F1 at 2000 tokens.Source: §5.3 · p. 6, Table 3 · p. 6
  • Reader-free answer-presence recall ranks NavTree highest on 2WikiMQA and MuSiQue at 2000 tokens, corroborating that the retrieval-side win is not reader-driven.Figure 3 shows NavTree overtaking extractive RAPTOR by 2000 tokens on HotpotQA, 2WikiMQA, and full-book NarrativeQA, and by 1024 tokens on 2WikiMQA.Source: §5.3 · p. 6, Figure 3 · p. 7

5.1 Strongest matched-cost hierarchical retriever; at parity with flat

  • Figure 2 shows NavTree ahead of RAPTOR-Extractive on QuALITY at every budget and overtaking it on QASPER at budgets ≥1024 tokens.The headline grid focuses on QuALITY and QASPER; NarrativeQA-summary and LongBench-SD are omitted from the figure because they are uninformative retrieval discriminators at this budget grid.Source: §5.1 · p. 5, Figure 2 · p. 7

5.4 Indexing cost

  • NavTree and extractive RAPTOR require zero LLM calls for indexing, while original RAPTOR makes 682 summary calls on the 60-document slice.NavTree's embedding-only indexing takes 386 seconds versus 241 seconds for RAPTOR, but the reported abstractive-variant cost is much higher once LLM calls are counted.Source: §5.4 · p. 7

6 Analysis

The analysis finds that summaries can help when assessed individually, but leaves-only retrieval can use a multi-chunk budget more effectively by avoiding redundant summary content. Ablations and sweeps identify the settings and conditions that qualify this result.

6.1 Cosine-space view, downstream reality, and the real win mechanism

  • 76% of internal nodes have a negative cosine gap (mean −0.088), yet summaries reach 55.7% versus 50.4% for best leaves in a direct reader test.The cosine result measures query similarity, while the head-to-head measures reader outcomes; the per-node summary advantage does not settle which packed context works better.Source: §6.1 · p. 7
  • At 1024–2000 tokens, summaries often duplicate their best-leaf descendants and displace distinct-subtree evidence, so leaves-only packing wins.At 256–512 tokens, displacement is small and per-node summary usefulness dominates; NavTree loses on point estimates.Source: §6.1 · pp. 7–8

6.2 What knob matters: ablation and sweep

  • On QuALITY@2000, cross-encoder reranking is the dominant factorial lever (+1.26 pp), while Steiner versus anchor-free is roughly orthogonal (−0.11 pp).The ablation also reports Kℓ=10 over Kℓ=48 at −0.81 pp when CE is on; leaves-only emission, not the walk algorithm, drives class-vs-class wins.Source: §6.2 · p. 8
  • 72.5% is the QuALITY@1024 peak at α=0.35; the tuned default sits within 0.003 token F1 of the QASPER sweep peak.All six QASPER sweep settings are within 0.006 token F1, and Kℓ values 5–10 are equivalent within reader noise.Source: §6.2 · p. 8, Figure 4 · p. 9

6.3 Tight-budget CE rerank

  • At QASPER@256, cross-encoder reranking raises NavTree from 0.31 to 0.35 F1; its gains fall from +4.3 pp at 256 to +0.1 pp at 1024.UnifiedQA-base flattens all methods to within ∼1 pp, indicating retrieval differences depend on the reader's ability to exploit retrieved context.Source: §6.3 · pp. 8–9

7 Conclusion

The conclusion argues that summary trees can help long-document QA through navigation rather than generated summary content. Leaves-only navigation avoids summary redundancy at multi-chunk budgets and does not require the indexing-time LLM calls used to produce summaries.

7 Conclusion

  • Summary trees’ main benefit in long-document QA can come from navigation rather than generated summary content.The conclusion says matched-cost, matched-reader, multi-hop, and robustness results agree with this regime distinction.Source: §7 · p. 9
  • At multi-chunk budgets, a summary node may repeat evidence covered by its best-leaf descendant while displacing a distinct-subtree leaf.The conclusion describes per-node summaries as useful, but says the packing trade-off favors leaves-only navigation in this regime.Source: §7 · p. 9
  • Leaves-only navigation captures the tree’s routing benefit without summary displacement or the LLM calls used to produce summaries.Source: §7 · p. 9

Limitations

The evaluation has defined scope boundaries: a matched-reader replication does not use the deprecated GPT-4 checkpoint, and robustness checks cover particular datasets, encoders, and readers. The paper also leaves some retrieval-versus-reader mechanisms unresolved.

Limitations

  • The matched-reader replication does not directly use the deprecated GPT-4 checkpoint from Sarthi et al. (2024), so its published 82.6/76.2 result is orientation only.Source: Limitations · p. 9
  • The stronger-encoder check covers QuALITY@1024 and QASPER@1024; on QASPER, hybrid-flat overtakes NavTree by 0.004 F1 within the 0.026 CI half-width.The headline grid uses all-MiniLM-L6-v2.Source: Limitations · p. 9
  • Open-weight reader checks use 15–60-document subsets, and UnifiedQA-base flattens methods to within ∼1 pp.The paper notes that retrieval differences can vanish with a weak reader.Source: Limitations · p. 9
  • QuALITY@1024 re-runs show 0.76 pp and 0.87 pp standard deviations for NavTree and RAPTOR-Extractive; cells with |∆| < 0.9 pp should be read as ties.The reported 4.4 pp paired-test margin exceeds both re-run standard deviations.Source: Limitations · p. 9
  • All evaluated datasets are English text; non-English morphology and non-text modalities remain untested.Source: Limitations · p. 9
  • The paper leaves a decisive decomposition of subtree displacement, fixed-budget versus fixed-count regimes, and reader preferences for verbatim text versus paraphrase to future work.Source: Limitations · p. 9

Ethics statement

The ethics statement describes the use of public NLP datasets and standard open-source models, with API readers queried at temperature zero and no user-identifying data stored or released. The appendix also specifies the scope and shared conditions of the full matched-cost grid.

Ethics statement

  • The work uses publicly available NLP datasets and standard open-source models.Source: Ethics statement · p. 9
  • The API readers are queried at temperature 0, and the authors report aggregate metrics without storing or releasing user-identifying data.The statement says the method introduces no risks beyond those inherent to RAG and discloses AI assistance for code scaffolding and prose drafting.Source: Ethics statement · p. 10

A Full matched-cost grid and per-dataset detail

  • The full matched-cost grid uses gpt-4o-mini at T=0, identical 100-token sentence-aware chunking, all-MiniLM-L6-v2, and budgets of 256, 512, 1024, and 2000.It extends the headline grid with NarrativeQA-summary and LongBench-SD, described as structurally inconclusive retrieval discriminators at this budget grid.Source: A Full matched-cost grid and… · p. 11

B Matched-reader RAPTOR comparison: methodology

The matched-reader RAPTOR replication compares NavTree with extractive and abstractive variants while holding the reader and other retrieval paths constant. The section also tests component effects, parameter robustness, and paired method comparisons.

B Matched-reader RAPTOR comparison: methodology

  • At zero indexing cost, NavTree matches or beats abstractive RAPTOR under the same modern reader, with the residual @2000 accuracy gap always in NavTree’s favor on this slice.The million-document projection is ∼$60k for abstractive RAPTOR.Source: B Matched-reader RAPTOR comparison:… · pp. 11–12
  • In the 24 factorial, cross-encoder reranking adds 1.26 pp on average, while the leaves-only emission rule—not the walk algorithm—is identified as the structural lever.Steiner moves accuracy by only −0.11 pp on average; interactions are small, with the largest 2-way term at +0.56 pp.Source: B Matched-reader RAPTOR comparison:… · p. 12, Table 13 · p. 13
  • Across six QASPER@1024 parameter settings, token F1 falls within 0.006, and the QuALITY-tuned default sits 0.003 below the QASPER peak.The default is within the stated ±0.026 CI half-width and six-seed reader-noise bound.Source: B Matched-reader RAPTOR comparison:… · pp. 12–13
  • On 115 QuALITY question pairs, summaries score 55.7% versus 50.4% for the best leaf when each is supplied alone to the reader.The summary wins 16 of 26 disagreement cases; the result motivates the token-packing explanation for NavTree’s multi-chunk-budget wins.Source: B Matched-reader RAPTOR comparison:… · p. 13

D All paired sign tests, NavTree vs. every other method

  • The paired-sign-test table evaluates NavTree against other retrievers using per-question outcomes, with ties ignored; the accompanying claims include statistical ties on specified dataset-budget comparisons.The passage cites hybrid-flat as tied with NavTree on QuALITY at every budget and extractive RAPTOR as tied on QASPER at every budget.Source: D All paired sign tests, NavTree vs.… · p. 13

E Encoder sensitivity: BGE-large

The encoder and reader sensitivity analyses test whether NavTree’s ranking persists under stronger encoders, weaker readers, and open-weight readers. Reader-free QASPER evidence coverage provides a separate check on retrieval quality.

E Encoder sensitivity: BGE-large

  • With BGE-large on QuALITY@1024, NavTree leads extractive RAPTOR by 4.36 pp and ties hybrid-flat at 1560/2086 correct.The encoder upgrade is approximately symmetric across dense methods; BM25 is unchanged.Source: E Encoder sensitivity: BGE-large · pp. 13–14
  • With BGE-large on QASPER@1024, hybrid-flat overtakes NavTree by +0.004 F1 (0.397 vs. 0.393), within the 0.026 CI half-width.NavTree’s lead over extractive RAPTOR remains +0.015 F1; the grid does not distinguish hierarchy from strong-encoder hybrid-flat retrieval.Source: E Encoder sensitivity: BGE-large · p. 14

G Weak-reader sensitivity study

  • With UnifiedQA-base, retrieval methods show no consistent ordering, and QuALITY accuracy spread is ≤1.5 pp at every budget.The reader has a 512-token context window; the authors report retrieval gaps shrink when reader capacity is the bottleneck.Source: G Weak-reader sensitivity study · p. 15

H Open-weight reader replication: LLAMA-3.1-8B and QWEN-2.5-7B on local Ollama

  • Across two open-weight readers, NavTree leads or ties in 4/4 reader-dataset cells, and all 12 paired comparisons match directionally.The QWEN QASPER@1024 result ties hybrid-flat at 0.320 F1; only the NavTree–RAPTOR-Ext QWEN QASPER comparison reaches p < 0.05.Source: H Open-weight reader replication:… · p. 15

I.1 QASPER gold-evidence coverage

  • For QASPER reader-free recall at @1024, NavTree has the highest any@k (99.5%) and frac@k (93.9%), marginally above Hybrid-flat and SBERT-flat.At @2000, every method exceeds 96% frac; at @256, Hybrid-flat leads.Source: §I.1 · p. 16

I.2 Reader-free recall on multi-hop (HotpotQA / 2WikiMQA / MuSiQue): methodology

The reader-free multi-hop check measures whether retrieved contexts contain answer strings rather than relying on reader scores. NavTree has the strongest @2000 recall on 2WikiMQA and MuSiQue, but not on HotpotQA.

I.2 Reader-free recall on multi-hop (HotpotQA / 2WikiMQA / MuSiQue): methodology

  • Answer-presence@k tests whether the normalized gold answer string occurs in retrieved context, excluding yes/no or unanswerable items and strings shorter than three alphanumeric characters.The analysis covers 506 examples across three datasets.Source: §I.2 · p. 16
  • At @2000, NavTree has the highest reader-free recall on 2WikiMQA (94.9%) and MuSiQue (68.5%), while tying SBERT-flat’s lead on 2WikiMQA@1024 (83.7%).On HotpotQA, NavTree is competitive but never best; BM25 leads at budgets ≥1024 with 83.1%/92.5%.Source: §I.2 · p. 16
  • On MuSiQue@512, the reader-side deficit is described as a downstream-reader composition issue rather than a retrieval-quality gap.Reader-free recall is 27.4% for NavTree versus 31.0% for Hybrid-flat, within 4 pp.Source: §I.2 · p. 16

Related papers

Loading 2610.06902v1…