Source-linked AI summary
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation
Ziwen Zhao, Menglin Yang
TL;DR
Existing Tree-RAG systems struggle with cross-document multi-hop retrieval and questions spanning different granularities. Ψ-RAG introduces a distribution-adaptive hierarchical abstract tree index and a multi-granular agentic retriever, achieving a 25.9% generation gain over RAPTOR on token-level QA.
Problem
Existing retrieval systems use fixed-granularity chunks, while Tree-RAG indexes can remain structurally isolated for cross-document multi-hop questions.
Method
Ψ-RAG combines a hierarchical abstract tree built by iterative merging and collapse with an agentic retriever that performs multi-turn query-driven retrieval.
Results
25.9% generation gain over RAPTOR on token-level QA, alongside 23.7% average retrieval gains.
Takeaways & Limitations
Ψ-RAG extends Tree-RAG to corpus-level indexing and supports token-level QA, passage-level reasoning, and document-level summarization.
Takeaways & Limitations
The abstract tree index requires O(n^2 log n) computation and sorting and O(n^2) space for its similarity matrix.
Abstract
from arXiv · showhide
Retrieval-augmented generation (RAG) enhances large language models with external knowledge, and tree-based RAG organizes documents into hierarchical indexes to support queries at multiple granularities. However, existing Tree-RAG methods designed for single-document retrieval face critical challenges in scaling to cross-document multi-hop questions: (1) poor distribution adaptability, where $k$-means clustering introduces noise due to rigid distribution assumptions; (2) structural isolation, as tree indexes lack explicit cross-document connections; and (3) coarse abstraction, which obscures fine-grained details. To address these limitations, we propose $Ψ$-RAG, a tree-RAG framework with two key components. First, a hierarchical abstract tree index built through an iterative "merging and collapse" process that adapts to data distributions without a priori assumption. Second, a multi-granular retrieval agent that intelligently interacts with the knowledge base with reorganized queries and an agent-powered hybrid retriever. $Ψ$-RAG supports diverse tasks from token-level question answering to document-level summarization. On cross-document multi-hop QA benchmarks, it outperforms RAPTOR by 25.9% and HippoRAG 2 by 7.4% in average F1 score. Code is available at https://github.com/Newiz430/Psi-RAG.
1. Introduction
Ψ-RAG addresses Tree-RAG’s limitations in cross-document multi-hop retrieval with a hierarchical abstract tree index and a multi-granular agentic hybrid retriever. It generalizes Tree-RAG to corpus-level indexing while supporting tasks from token-level QA through document-level summarization.
- Motivation: Fixed-granularity chunking produces incomplete and inaccurate responses for higher-level questions.
- Limitations: Existing Tree-RAG methods mainly target single-hop retrieval on a single long document, limiting cross-document multi-hop retrieval.
- Method: Ψ-RAG combines a hierarchical abstract tree index with a multi-granular agentic retriever to address distribution adaptability, structural isolation, and abstraction-detail conflicts.The retriever can reorganize queries for additional document retrieval and supplement tree retrieval with fine-grained sparse retrieval.
- Results: 10× faster corpus-level tree construction than OpenIE-based Graph-RAG is achieved, alongside 23.7% average retrieval and 25.9% generation gains over RAPTOR on token-level QA.
- Scope and Contributions: Ψ-RAG supports token-level factual QA, passage-level causal reasoning, and document-level summarization.It is presented as the first Tree-RAG for cross-document multi-hop scenarios comparable to Graph-RAG and outperforms HippoRAG 2.
- Scope and Contributions: Ψ-RAG uses entirely open-source LLMs, replaceable components, and custom-corpus deployment without training or fine-tuning.
2. Preliminary
The preliminary section formalizes retrieval-augmented generation as an LLM paired with a retriever over indexed document chunks, then defines the tree structures used for organization and retrieval. It also distinguishes binary, multifurcating, and equi-depth trees.
- Retrieval-Augmented Generation: RAG maps a query to top-k relevant document chunks using a scoring function, while an index maps corpus chunks into a discrete retrieval space.The corpus contains n = |D| chunks, and the indexed set is D* = {u_i}^k_{i=1} ⊂ D.
- Tree Index: A tree index is a connected acyclic graph with finite nodes and edges, supporting parent, child, root, leaf-descendant, depth, and least-common-ancestor relations.Node depth is the path length to the root, with δ(root) = 0 and tree depth δ(T) defined as the maximum node depth.
- Tree Index: Trees are binary when each non-leaf has exactly two children, multifurcating when at least one node has more than two children, and equi-depth when all leaves share a root distance.These definitions distinguish branching structure from the depth property of the tree.
3. Ψ-RAG
Ψ-RAG builds an abstract tree through distribution-adaptive merging, collapse, rebalancing, and agent-generated abstractions. Its multi-granular retrieval combines iterative agentic reasoning with hybrid tree and sparse retrieval to address cross-document multi-hop and fine-grained searches.
- Abstract Tree Indexing: Ψ-RAG constructs abstract trees from document chunks and dense vectors through similarity ranking, iterative merging and collapse, and abstraction.Leaves retain original chunks, while upper nodes contain agent-generated abstracts.
- Abstract Tree Indexing: n −1 iterations connect all n nodes into one tree, after which excessive child counts are split and distributed evenly.Rebalancing limits overly long contexts for the abstraction agent.
- Multi-granular Agentic Retrieval: Existing tree retrieval can miss entities required for ordered causal reasoning because dense similarity emphasizes surface-related terms and tree structure isolates documents.Beam search is described as insufficient for ordered causality reasoning in multi-hop queries.
- Multi-granular Agentic Retrieval: The R&A agent uses multi-turn interactions to decide whether retrieved information suffices or whether another retrieval call is needed.Its action tag is either <answer> or <retrieve>.
- Multi-granular Agentic Retrieval: Agent-powered hybrid retrieval combines tree results with a BM25 sparse keyword index and reorganizes queries with enriched context.Query enrichment helps sparse retrieval add thematic keywords and helps tree retrieval locate relevant upper-level abstracts.
4. Distribution Adaptability of Tree-RAG
This section shows that k-means-type Tree-RAG favors uniformly sized clusters, while Ψ-RAG’s hierarchical construction avoids this uniform effect and preserves skewed corpus distributions. Theoretical results and visualizations show that Ψ-RAG produces fewer cross-cluster confusions than RAPTOR on skewed data.
- k-means-type Tree-RAG: k-means-type clustering favors uniformly sized clusters, even when the corpus distribution is skewed.The uniform effect arises because major-cluster objects can be assigned to minor clusters; soft k-means and GMM share this behavior.
- Ψ-RAG’s hierarchical index: Ψ-RAG prefers non-uniform leaf distributions rather than perfectly uniform subtree sizes.Theorem 4.3 shows that moving one leaf from one subtree to another lowers Dasgupta’s cost under a perfectly uniform distribution.
- Ψ-RAG’s hierarchical index: Ψ-RAG adaptively preserves skewed distributions and avoids the uniform effect when minor clusters differ substantially in size.Theorem 4.4 shows that moving a leaf into a minor subtree increases or preserves cost, with equality only when the source subtree has size ni + 1.
- Visualization study: On skewed datasets, RAPTOR frequently confuses major abstract nodes with minor ones, especially at higher tree layers.The visualization study constructs RAPTOR and Ψ-RAG indexes from skewed MultiHop-RAG category mixtures.
- Visualization study: Ψ-RAG assigns far fewer major abstract nodes to minor ones, producing a superior index structure on skewed data.The paper links RAPTOR’s confused abstracts to retrieval noise and provides a detailed case study in Appendix D.2.
5. Experiments
Experiments evaluate Ψ-RAG across token-level QA, narrative QA, and summarization using diverse cross-document benchmarks and retrieval, QA, and generation metrics. Ψ-RAG shows strong performance across tasks, with gains attributed to hierarchical indexing, agentic retrieval, and hybrid sparse-dense retrieval.
- Tasks and datasets: Evaluation covers single- and multi-hop QA, narrative QA, and summarization across benchmarks including NQ, PopQA, HotpotQA, 2Wiki, MuSiQue, MultiHop-RAG, NarrativeQA, ∞Bench, and QMSum.QA uses Recall@2, Recall@5, Exact Match, and F1; narrative QA and summarization use task-specific passage- and document-level metrics.
- QA results: Traditional retrievers perform competitively on single-hop factual QA, whereas IRCoT and HippoRAG 2 outperform BM25 + DPR on 3 out of 4 multi-hop datasets.The highest multi-hop F1 gains exceed 20%, underscoring the importance of modeling implicit entity relationships.
- QA results: On 5 out of 6 datasets, RAPTOR + Q3R underperforms DPR without a reranker, with degradations exceeding 25% in Recall@5 and 30% in F1 on PopQA.The results indicate that coarse-grained abstracts become a limitation as the tree index expands.
- QA results: 25.9% average F1 and 23.7% average Recall@5 gains over RAPTOR establish Ψ-RAG’s strong cross-document QA performance across abstraction types.Ψ-RAG surpasses RAPTOR by up to 54.78% in F1 on 2Wiki, HippoRAG 2 by 7.4% in average F1, and HippoRAG 2 + Q3R by 9.9%.
- Narrative QA and summarization: Ψ-RAG consistently outperforms all baselines on narrative QA and summarization, exceeding RAPTOR by 9.7% average F1 and GoR by 3.2% average ROUGE-L.BM25 and DPR perform worst in most passage- and document-level settings, while structured indexes provide higher-level information.
- Ablation study: The R&A agent improves multi-hop QA by ∼20% on average and single-hop NQ by 1.89% F1, while sparse retrieval adds +21.82% on PopQA and +41.21% on 2Wiki.These gains are associated with query reorganization and mitigation of coarse tree abstractions.
- Efficiency and limitations: 258 seconds indexes MuSiQue’s 1.3 million tokens, making Ψ-RAG 6.5× faster than RAPTOR, although AHC introduces O(n^2 log n) time and O(n^2) space complexity.The iterative merging and collapse process takes O(n^2) time, while top-down retrieval has O(log n) complexity.
6. Conclusion … B. Theoretical Proofs
Ψ-RAG is presented as a corpus-level hierarchical Tree-RAG framework for cross-document multihop questions, combining hierarchical abstract-tree indexing with multi-granular agentic retrieval. The appendix specifies its indexing and retrieval procedures, including tree construction, rebalancing, abstraction, and hybrid retrieval.
- 6. Conclusion: Ψ-RAG supports corpus-level indexing and cross-document multihop questions through hierarchical clustering-based indexing and a multi-granular agentic retriever.The framework targets poor distribution adaptability, structural isolation, and coarse abstraction in k-means-type tree indexes.
- A. Algorithms of Ψ-RAG: Abstract Tree Indexing builds a tree from a pairwise similarity matrix by processing similarities in descending order and merging nodes or roots according to their depths.The procedure initializes an empty tree and iterates through ranked similarity pairs.
- A. Algorithms of Ψ-RAG: The indexing algorithm rebalances overloaded nodes by splitting them, generates abstract text for every abstract node, and outputs the abstract tree.These operations occur after the similarity-driven tree construction loop.
- A. Algorithms of Ψ-RAG: Tree Retrieval traverses the index from the root across depth levels and applies top-k nearest-neighbor search to select candidate nodes.The procedure takes a query, tree index, retrieved-chunk count k, and maximum retrieval step imax as inputs.
- A. Algorithms of Ψ-RAG: Multi-granular Agentic Retrieval combines tree retrieval with sparse-index retrieval and uses an LLM agent to decide whether to answer or issue a reorganized retrieval query.The algorithm initializes results from both retrieval sources and repeats agentic steps until producing an answer.
B.1. Proof of Theorem 4.1
The proof establishes Theorem 4.1 by induction over the number of clusters, expressing the relevant objective through within-cluster pairwise distances. It concludes that k-means essentially maximizes L, with equal cluster sizes arising under an independence assumption.
- Inductive proof: The proof defines the sum of all pairwise distances among samples within k clusters as an intermediate quantity.This quantity is used to establish the theorem’s identity.
- Inductive proof: Mathematical induction verifies the relevant relation, beginning with the one-cluster base case and extending it from K−1 to K clusters.The induction step sums the corresponding expression over every cluster.
- Objective reformulation: The proof then rewrites L using the established relation between within-cluster and between-cluster pairwise distances.The supplied derivation explicitly invokes the established relation before rewriting L.
- Objective reformulation: Under independence of ninj and ∥µi −µj∥2, maximizing ninj yields equal cluster sizes, n1 = n2 = · · · = nk = n/k.This is a conditional consequence of the stated independence assumption.
- Conclusion: The theorem’s remark states that the k-means objective is essentially maximizing L.This conclusion summarizes the role of the preceding derivation.
B.2. Proof of Theorem 4.3
Theorem 4.3 is established by mapping binary AHC trees to equi-depth multifurcating trees through layer-wise collapsing and decomposing the resulting Dasgupta-cost changes. Under the theorem’s uniform-tree conditions, moving one leaf between subtrees lowers Ψ-RAG’s cost and reveals its preference for non-uniform leaf distributions.
- Tree correspondence: A surjection ψ maps every binary AHC tree to an equi-depth multifurcating tree through iterative node collapsing.Collapsing proceeds bottom-up by linking shallower subtrees to corresponding nodes in deeper subtrees until child-subtree depths are equal.
- Cost decomposition: The cost difference Δc = c(ψ(T_AHC)) − c(T_AHC) decomposes into layer-wise increments from leaf and abstract-node collapses, independently of collapse order within a layer.This follows from the connection lemma and Dasgupta-cost modularity, together with invariance to child ordering.
- Non-uniformity preference: For T = ψ(T_AHC) and T′ = ψ(T′_AHC), the tree-cost difference equals the difference in collapse increments: c(T′) − c(T) = Δc′ − Δc.The equality is obtained by decomposing ψ into successive leaf and abstract-node collapses and applying the corresponding increment formulas.
- Interpretation: Traditional AHC assigns equal Dasgupta costs to the two structures before collapse, whereas Ψ-RAG assigns lower cost to the non-uniform leaf distribution.Thus, Ψ-RAG’s collapsing process creates a non-uniformity preference even when pairwise leaf distances are unsorted.
B.3. Proof of Theorem 4.4 · C. Detailed Experimental Setup
Theorem 4.4 establishes that Ψ-RAG’s hierarchical cost and cost increment do not decrease when a leaf moves from a major to a minor subtree, supporting preservation of minor-class structure in skewed corpora. The proof analyzes equality and strict-increase conditions, while accompanying materials report dataset and abstract-tree-index statistics.
- B.3. Proof of Theorem 4.4: Theorem 4.4 considers a 3-layer equi-depth multifurcating tree with k ≥3 and a minor subtree Ti receiving one leaf from a major subtree Tj.The minor subtree satisfies 2 ≤ ni < nj for every j ≠ i.
- B.3. Proof of Theorem 4.4: c(T′) ≥ c(T), with equality if and only if nj = ni + 1.The theorem compares the hierarchical costs before and after moving one leaf into the minor subtree.
- B.3. Proof of Theorem 4.4: The cost increment satisfies Δc′ ≥ Δc, with equality if and only if nj = ni + 1.Here T = ψ(TAHC) and T′ = ψ(T′AHC), with Δc and Δc′ defined as in Theorem 4.3.
- B.3. Proof of Theorem 4.4: The proof attributes unchanged terms to a constant C that remains invariant under the structure change.This invariant appears in the cost comparison used for the theorem’s first part.
- B.3. Proof of Theorem 4.4: When nj = ni + 1, c(T′) − c(T) = 0; when nj = ni + x for x > 1, c(T′) > c(T).The proof derives strict cost growth when the donor subtree exceeds the minor subtree by more than one leaf.
- C. Detailed Experimental Setup: The detailed experimental setup includes dataset statistics and statistics of Ψ-RAG’s abstract tree indexes.These materials are identified as Table 9 and Table 10, respectively.
- B.3. Proof of Theorem 4.4: Theorem 4.4 concludes that Ψ-RAG incurs larger cost when assigning a major cluster node to a minor cluster.The proof’s equality and strict-inequality cases establish this conclusion.
- B.3. Proof of Theorem 4.4: Minor classes form minor subtrees under Ψ-RAG’s similarity ranking and iterative merging & collapse processes.The remark states that this tendency preserves minor-class sizes in skewed corpora.
C.1. Dataset and Index Statistics … D. Supplemental Experiments
The supplemental material specifies Ψ-RAG’s dataset splitting, abstract-tree behavior, configurations, retrieval settings, and LLM prompting procedures. It reports that corpus-level trees stabilize at 5–6 layers while using distribution-adaptive hierarchical abstraction.
- C.1. Dataset and Index Statistics: Documents are split into approximately 100-token chunks without mid-sentence cuts, except similarly sized paragraphs in five datasets that remain unsplit.The exceptions are NQ, PopQA, HotpotQA, 2Wiki, and MuSiQue.
- C.1. Dataset and Index Statistics: Corpus-level Ψ-RAG abstract trees stabilize at 5–6 layers, supporting hierarchy discovery without prior data-distribution assumptions.The tree statistics are provided for each dataset in Table 10.
- C.2. Configurations: Each abstract node allows a 100-token summative abstract, up to 20 keyword-abstract keywords, and 40 children before rebalancing splits excessive children in half.The keyword abstract ø is used in all non-comparative experiments unless otherwise stated.
- C.2. Configurations: QA retrieval integrates and reranks top-10 sparse and dense tree passages to a final top-5 at every retrieval step.Retrieved document chunks are maintained in a maximum-score list, with top-5 documents used for recall@k evaluation.
- C.2. Configurations: Experiments use up to three NVIDIA GeForce RTX 4090 GPUs, default Ollama and Hugging Face LLM settings, a 4096-token context window, temperature 0, and repetition penalty 1.3.The supplied passage also states that summarization response length depends on document size.
- C.3. Instruction Prompts: Summative-abstract prompts require direct, faithful summaries beginning with “Summary:” and covering key details and relationships without unnecessary additions.The prompt examples summarize multiple hotel-related documents and their relationships.
- C.3. Instruction Prompts: Keyword-abstract prompts generate ordered, comma-formatted key phrases covering paragraph information types, common themes, and distinguishing content.The example includes topics such as historic hotels, hotel companies, ownership history, locations, architecture, and founders.
- C.3. Instruction Prompts: The QA retrieval-and-answering agent is instructed to reason step by step after “Thought:” and conclude with a concise “Answer:”, while summarization prompts organize retrieved documents into a logically clear corpus summary.The QA prompt includes one-shot examples and a maximum thought length placeholder.
D.1. Case Study · D.2. Analyses on Hierarchical Abstract Tree · D.3. Analyses on Multi-granular Agentic Retriever
The analyses show how Ψ-RAG combines hierarchical abstraction with agentic hybrid retrieval to resolve multi-hop questions, while rebalancing and retrieval-iteration studies expose key performance and efficiency trade-offs. Case studies further illustrate distribution adaptability and the complementary roles of tree-based and sparse retrieval.
- D.1. Case Study: Ψ-RAG progressively refines retrieval from coarse thematic keywords to finer-grained chunks, identifying David Gest before answering with Liza Minnelli.The example requires up to three hops and demonstrates multi-granular agentic retrieval on the abstract tree.
- D.1. Case Study: The case study demonstrates that synergy between the hierarchical tree index and multi-granular hybrid retriever is central to Ψ-RAG’s effectiveness.The tree supports progressively refined semantic search, while sparse retrieval resolves specific factual links.
- D.1. Case Study: Structural isolation and coarse upper-layer abstractions can leave missing context and mislead retrieval toward irrelevant chunks.The agent therefore makes a second retrieval attempt, while sparse retrieval supplies straightforward keyword-based facts.
- D.2. Analyses on Hierarchical Abstract Tree: RAPTOR’s first-layer abstract nodes become dominated by the major class “Sports,” confusing retrieval for a minor-class question on skewed data.The comparison is used to demonstrate the impact of uniform effects and Ψ-RAG’s distribution adaptability.
- D.2. Analyses on Hierarchical Abstract Tree: Rebalancing without excessive splitting improves tree structure and performance, whereas repeated splitting can cause relevant nodes to be lost.The maximum number of children per abstract node is constrained to keep total abstract length within the abstraction agent’s context window.
- D.3. Analyses on Multi-granular Agentic Retriever: The first extra retrieval attempt provides the greatest performance gain on multi-hop datasets, while later attempts yield minimal or negative improvement.Each attempt adds relatively constant time overhead, making the retrieval budget an efficiency-performance trade-off.
- D.3. Analyses on Multi-granular Agentic Retriever: Longer retrieval chains can introduce unnecessary noise, so the number of iterative retrieval attempts should be balanced against cost across application scenarios.The analysis emphasizes that additional retrieval calls are not uniformly beneficial.
D.4. Failure Analysis · E. Real-World Extensions
Ψ-RAG failure analysis distinguishes incorrect answers from retrieval failures and shows that retrieval quality degrades with index scale and query complexity. False answers generally exceed retrieval failures, with manual analysis attributing errors mainly to incomplete retrieval, reasoning mistakes, hallucination, and granularity mismatch.
- D.4. Failure Analysis: Ψ-RAG measures False Rate for incorrect answers and Not Mentioned Rate for retrieval failures.An incorrect answer shares no overlapping tokens with the ground truth.
- D.4. Failure Analysis: Index scale is a primary retrieval-failure factor, with ∞-LongBook showing a significantly higher Not Mentioned Rate than NarrativeQA.NarrativeQA’s index is only 30% the size on average, while larger search spaces produce coarser, noisier upper-level abstracts.
- D.4. Failure Analysis: Query complexity also affects retrieval, as MuSiQue’s 4-hop questions have higher Not Mentioned Rates than datasets with fewer hops.The passage specifically contrasts MuSiQue with HotpotQA and 2W datasets.
- D.4. Failure Analysis: The False Rate consistently exceeds the Not Mentioned Rate on most datasets, excluding MultiHop-RAG with unanswerable negative samples.This indicates that incorrect answers are not explained solely by retrieval failures.
- D.4. Failure Analysis: 29 cases in a 50-case MuSiQue analysis involved LLM misguidance or guesses caused by incomplete retrieval.The analysis used L3-70B failure cases.
- D.4. Failure Analysis: The remaining analyzed causes were logical errors in agentic reasoning (8 cases), hallucination (6 cases), and answer–ground-truth granularity mismatch (7 cases).Together, these categories account for the manually analyzed failure cases not attributed to incomplete retrieval.
E.1. Approximate Nearest Neighbor Search for Efficient Indexing … G. Discussion and Future Work
The paper extends Ψ-RAG for large-scale indexing, practical hop-adaptive retrieval, and broader RAG settings, while discussing incremental updates and future efficiency improvements. Its extensions reduce indexing costs, and its discussion identifies update mechanisms, insertion limitations, and further research directions.
- E.1. Approximate Nearest Neighbor Search for Efficient Indexing: O(n^2/b) indexing time and O(n^2/b^2) space result from recursively bucketing balanced corpora before building and merging per-bucket trees.Bucketing uses fast recursive spherical k-means and assumes b ≪ n balanced buckets.
- E.1. Approximate Nearest Neighbor Search for Efficient Indexing: O(kn log kn) similarity-ranking time and O(kn) space result from ranking top-k HNSW neighbor pairs instead of all chunk pairs.An HNSW graph is built over all chunk embeddings before tree construction.
- E.1. Approximate Nearest Neighbor Search for Efficient Indexing: Less than 1.5 GB of storage lets HNSW generate sorted document pairs for 50M-token corpora, while combined bucketing uses MB-level memory and under 1% of original time.The evaluation uses Wiki18-6M and Wiki18-50M subsets.
- E.2. Query Hop Discriminator: A lightweight 2-layer MLP predicts each query’s hop count before retrieval and selects the maximum retrieval time for the R&A agent.It is trained on questions with 1 to 4 hops for settings without a known maximum hop count.
- F. Related Work: RAG-related approaches include sparse retrieval, agentic RAG, graph-RAG, and tree-RAG, differing in keyword matching, recursive reasoning, relational traversal, and hierarchical indexing.The related-work discussion contrasts these retrieval and indexing paradigms.
- G. Discussion and Future Work: New chunks can be inserted by matching each node to its most similar leaf, updating keyword abstracts upstream, and regenerating summative abstractions.The local pairwise-similarity construction avoids re-clustering the entire corpus.
- G. Discussion and Future Work: Subtree insertion is recommended when new contents differ substantially, while more efficient abstraction schemes and specialized agents remain future work.Repeated isolated insertions under one parent may amplify semantic or granularity biases.