Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation Ziwen Zhao 1 Menglin Yang 1 (a)
Singledocument document Passage-level retrieval Single online indexing / long context
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 crossdocument multi-hop QA benchmarks, it outperforms RAPTOR by 25.9% and HippoRAG 2 by 7.4% in average F1 score1 .
Single-document query search
Augmented context
Online
Crossdocument retrieval Multi-document corpus
Cross-document query search
Corpus-level offline indexing
Offline
(b) Single-document
Cross-document
Augmented context
Online
(c)
Indexing time vs. multi-hop F1 𝚿-RAG
Question answering F1 (%)
arXiv:2605.00529v1 [cs.LG] 1 May 2026
Abstract
𝚿-RAG: Indexing time ↓ Multi-hop F1 ↑
HippoRAG 2 GraphRAG
Graph-RAG: Indexing time ↑ Multi-hop F1 ↑
RAPTOR
Ψ-RAG
Traditional Tree-RAG: Indexing time ↓ Multi-hop F1 ↓
Figure 1. (a) Two RAG application scenarios: single-document and cross-document retrieval. (b) Multi-hop QA performance w.r.t. the number of documents in the tree index. (c) Ψ-RAG has both efficient indexing and accurate multi-hop retrieval compared to structured RAG baselines, using 2Wiki as an example.
question answering (QA) to document-level summarization, RAG frameworks must leverage the semantic hierarchy within corpora (Sarthi et al., 2024; Chen et al., 2024). Traditional retrieval systems (Robertson et al., 2009; Karpukhin et al., 2020) slice documents into short, independent chunks; this fixed retrieval granularity leads to incomplete and inaccurate responses for higher-level questions (Nair et al., 2023; Liu et al., 2021; Sarthi et al., 2024; Wang et al., 2025).
1. Introduction Retrieval-augmented generation (RAG) (Lewis et al., 2020) enhances large language models (LLMs) with reliable references from external knowledge bases. To effectively address multi-granular user queries from token-level factual
Structured RAG achieves multi-granularity by organizing documents relationally with knowledge graph indexes (Edge et al., 2024; Jiménez Gutiérrez et al., 2024; 2025) or hierarchically with tree indexes (Liu et al., 2021; Jin et al., 2025b; Sarthi et al., 2024). Its utility is demonstrated in two key scenarios, as in Figure 1(a): (1) single-document retrieval, to process user requests in diverse granularity within a single user-uploaded document (Jin et al., 2025a; Li et al., 2025b; Zhang et al., 2025a); (2) cross-document retrieval, to process user requests by building a large index from an entire
1
The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China. Correspondence to: Menglin Yang <[email protected]>. Proceedings of the 43 rd International Conference on Machine Learning, Seoul, South Korea. PMLR 306, 2026. Copyright 2026 by the author(s). 1 Code is available at https://github.com/ Newiz430/Psi-RAG.
1
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation Table 1. Comparison of RAG frameworks. “?” indicates limited support by specific methods. Task type Traditional RAG Graph-RAG Tree-RAG Ψ-RAG (Ours)
Singledocument
Crossdocument
Tokenlevel
Passagelevel
Documentlevel
✓ ✓ ✓ ✓
p ✓ p ✓
✓ ✓ ? ✓
? ✓ ✓ ✓
p ? ✓ ✓
document retrieval with a reorganized query when needed. This empowers the tree retriever with better causal understanding of user query. (3) To resolve the conflict between coarse abstraction and detailed factual retrieval, a multigranular hybrid retrieval framework is employed, where an agent-powered sparse retriever supplements the hierarchical tree retrieval with fine-grained information, yielding significant performance gains. Our proposed framework possesses numerous advantages:
(domain-specific) corpus and retrieving across multiple documents, challenging the multi-hop retrieval and reasoning capabilities of RAG frameworks (Trivedi et al., 2023; Tang & Yang, 2024).
• Ψ-RAG generalizes Tree-RAG from passage-level to corpus-level indexing. As shown in Figure 1(c), Ψ-RAG builds a corpus-level tree 10× faster than OpenIE-based Graph-RAG. Under this setting, Ψ-RAG achieves average gains of 23.7% in retrieval and 25.9% in generation over RAPTOR on token-level QA.
Our work focuses on Tree-RAG (Liu et al., 2021; Jin et al., 2025b; Sarthi et al., 2024; Tao et al., 2025; Rezazadeh et al., 2025), which organizes documents into a tree-structured index. It explicitly defines different information granularities, enabling superior retrieval performance, especially for summative tasks (Sarthi et al., 2024; Xiao et al., 2025). See Appendix F for more related works. However, existing Tree-RAG methods mainly target single-hop retrieval on a single long document, while cross-document and multihop retrieval remain underexplored. For example, representative k-means-type cluster trees like RAPTOR (Sarthi et al., 2024) achieve high retrieval performance only with small-scale, passage-level indexes. As shown in Figure 1(b), RAPTOR’s retrieval accuracy drops significantly when the search space expands to corpus-level with millions of tokens. We identify three key limitations: (1) Poor distribution adaptability: k-means-type clustering implicitly relies on spherical data distributions (Sarthi et al., 2024), which introduces noisy documents to the retriever for corpora with a skewed distribution. (2) Structural isolation: unlike Graph-RAG which dynamically hops between documents based on pairwise relationships, leaf nodes in a tree index lack explicit connections. This prevents the retriever from capturing implicit causal dependencies in multi-hop questions. (3) Coarse abstraction: the coarse-grained abstracts act like a mosaic, obscuring token-level details at the very beginning of retrieval, as dense vector matching struggles to precisely associate a specific entity in the user query with abstract concepts on top of the tree.
• Ψ-RAG extends Tree-RAG to complex multi-hop scenarios. To our knowledge, Ψ-RAG is the first Tree-RAG for cross-document multi-hop scenarios comparable to Graph-RAG, exhibiting great application potential. As in Figure 1(c), Ψ-RAG is both efficient and powerful, outperforming cutting-edge Graph-RAG frameworks like HippoRAG 2 (Jiménez Gutiérrez et al., 2025). • As in Table 1, Ψ-RAG is an all-in-one Tree-RAG framework supporting tasks across various granularities: token-level factual QA, passage-level causal reasoning, and document-level summarization. • Ψ-RAG is built entirely with open-source LLMs. Its components are flexibly replaceable. Ψ-RAG can be applied to custom corpora without any training or finetuning, demonstrating strong generalizability.
2. Preliminary Retrieval-Augmented Generation. Given a user query q, an LLM f (q; I) generates a corresponding response a, where I is the system instruction for a specific task. For a reasoning model, a = R ∪ y, where R is the Chain-ofThought (Wei et al., 2022) reasoning text and y is the final answer. An LLM equipped with RAG can be defined as f · r, where the retriever r(q; I) maps q to top-k relevant document chunks D∗ = {ui }ki=1 ⊂ D using a scoring function s(q, u). The external corpus D contains n = |D| chunks in total. The index I : D → T maps each chunk in D to a discrete index space T for better retrieval.
This work aims to address the limitations of Tree-RAG on cross-document and multi-hop retrieval. We present Ψ-RAG, a versatile and effective Tree-RAG framework, comprising a hierarchical abstract tree index and a multigranular agentic retriever. (1) To address poor distribution adaptability, we build an abstract tree index via a hierarchical clustering-inspired “merging and collapse” process, which iteratively links similar chunks to existing or newly generated upper-level nodes in the tree. (2) To tackle structural isolation, a retrieval and answering agent reasons through the user query, during which it calls for additional
Tree Index. We overload the symbol T to denote a tree. Formally, a tree T = (V, E) is a connected acyclic graph |V| with a finite node set V = {vi }i=1 and an edge set E ⊂ V × V. The root node for a node u is denoted as root(u). The set of children of u is c(u) = {v|u → v ∈ E}. Let ℓ(u) be the set of all leaf nodes reachable from u. The depth of a node δ(·) is defined as the length of the path to the root, 2
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation Abstract Tree Indexing
1
(1 , 3) (2 , 3) (4 , 5) (3 ,4)
encoder
2
similarity ranking
Beyoncé's music is generally R&B ... Beyoncénames Michael Jackson as her musical influence...
3 Michael Jackson: The Life of an Icon is a documentary film...
4 5
merging & collapse
The music of The Lord of the Rings film series was composed...
r a1
1 2 3 4 5
document chunks
abstract tree
a1
keyword abstract
Summary: Introduction of Beyoncé's stylistic range and her inspiration Michael Jackson...
a1 R&B, film music,
a2
Summary: Elements in adapted action films such as The Lord of the Rings and The Avengers...
a2 Action films, film
r
r
Summary: Documents cover various entertainment topics including music, films, and comics...
a2
Thanos appears in various Marvel films...
Multi-granular Agentic Retrieval
summative abstract
token-level question answering
document-level summarization
The film name about that pop star who influenced Beyoncé?
musical career, singer childhood, Beyoncé, Michael Jackson, The Life of an Icon...
adaptation, film music, release date, Marvel Universe, The Lord of the Rings, Thanos...
Summarize the contents of film music.
Film about MJ? ①
②
R&A Agent
multi-granular hybrid index
Entertainment industry, artistic forms, music stars, film actors, artistic career, Beyoncé, ...
R&A Agent
multi-granular hybrid index "The Lord of the Rings is deemed as one of the greatest film music achievements..."
"Michael Jackson: The Life of an Icon."
encoder
Figure 2. Overview of Ψ-RAG. In Abstract Tree Indexing, a hierarchical abstract tree is built by ranking pairwise chunk similarities and applying an iterative “merging and collapse” process. Then, an abstraction agent generates a summative or keyword abstract for each abstract node. In Multi-granular Agentic Retrieval, a retrieval and answering (R&A) agent dynamically interacts with a multi-granular knowledge base organized by both the tree index and a sparse keyword index. By adjusting the retrieval iterations and the utilization of the sparse index, Ψ-RAG adapts to diverse user requests from token-level question answering to document-level summarization. Merging
with δ(root) = 0. TheMerging tree depth is δ(T ) = maxu∈T δ(u). similar We chunk denote pairs the parent (ancestor) of leaf u at a distance k as pk1(u),2 where p0 (u) = u and root(u) = pδ(u) (u). The 3 (LCA) 4 1 2 least3common ancestor of1 two nodes is defined as 4 3 4 2 𝛿 2 =𝛿 4 the deepest node that is an ancestor to both:
1
2
𝑝 4
max
δ(a)
δ(u) 𝑝k 4 (v)}δ(v) a∈{pk (u)}k=1 ∩{p k=1
2
1
2
3
4
5
𝛿 3 >𝛿 5
3. Ψ-RAG
6
1
2
𝑐 𝑝2 3
4
← 𝑐 𝑝2 3
5
3
2
3
4
𝑟 5
𝑝 3
5
6
1
2
3
4
4
5
6
𝛿 3 >𝛿 5
𝛿 2 =𝛿 4
(1)
𝑝2 3
𝑝 4
1
2
3
4
1
2
𝑝 3
3
4
5
6
𝑐 𝑝 4
←𝑐 𝑝 4
∪ 6
new abstract node
2
3
𝑝2 3
4 1
1
A tree1 is2binary nodes have 3 4 (or5 bifurcating) 6 1 2 if 3all 4its non-leaf 5 6 exactly two children. A tree is 𝑐 𝑝multifurcating 4 ← 𝑐 𝑝 4 ∪ 6 if all non-leaf nodes have at least twoNode children at least one node has Abstract Collapseand 𝑝 3 𝑝 3 more than two children. A tree is equi-depth if every leaf is 𝑟 5 𝑝 3 𝑟 5 𝑝 3 equidistant from the root. 2
3
𝑝 4
Leaf Node Collapse
LCA(u, v) = arg
Abstract Node Collapse
Leaf Node Collapse
similar chunk pairs
1
2
3
𝑐 𝑝2 3
𝑟 5
4
5
← 𝑐 𝑝2 3
6 ∪ 𝑟 5
new edge
Figure 3. Illustration of abstract tree building steps: merging, leaf node collapse, and abstract node collapse. Yellow arrows indicate the current chunk pair to be processed.
6
∪ 𝑟 5
As illustrated in Figure 2, Ψ-RAG follows the two-phase paradigm of existing structured RAG: indexing and retrieval. This section formally presents its two core components: Abstract Tree Indexing and Multi-granular Agentic Retrieval.
similar pair of document chunks (u, v), the tree is built iteratively: if neither u nor v has a parent, they are linked under a newly created abstract node a: c(a) = {u, v}. This is called a merging. If one node u is already linked to an abstract node p(u), the isolated node v is also linked under p(u): c(p(u)) ← c(p(u)) ∪ {v}. This is called a leaf node collapse. If both u and v are already linked to abstract nodes and their roots differ, then:
3.1. Abstract Tree Indexing Ψ-RAG constructs a tree index from a long document or a document collection, which we term an abstract tree. The leaves consist of the original document chunks D and their encoded dense vectors. Upper-level nodes are called abstract nodes, each containing an abstract of its children generated by an abstraction agent. The abstract tree is constructed via a “similarity ranking → iterative merging and collapse → abstraction” pipeline.
• If δ(u) = δ(v), their roots are merged under a new abstract node a: c(a) = {root(u), root(v)}, making root(u) = root(v) = a. • If δ(u) > δ(v), root(v) is linked onto the path of u: c(pδ(v)+1 (u)) ← c(pδ(v)+1 (u)) ∪ {root(v)}
Similarity ranking. First, all document chunks are encoded into fixed-length dense vectors e(D) ∈ R|D|×de using a pretrained language encoder. A symmetric similarity matrix S ∈ R|D|×|D| = e(D)e(D)⊤ is then constructed. These chunk pairs are finally sorted in descending order based on their similarity scores.
(2)
This results in δ(u) = δ(v). The case for δ(u) < δ(v) is analogous. This is called an abstract node collapse. Figure 3 illustrates these tree-building steps. The iteration runs for exactly n − 1 steps, which is the minimum number of connections required to link all n nodes into a single tree. Subsequently, the abstract tree is rebalanced by splitting
Iterative merging and collapse. Beginning from the most 3
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation
nodes with an excessive number of children and distributing the children evenly between two new nodes. This avoids overly long contexts for the abstraction agent. A detailed algorithm is provided in Appendix A.
until the action tag becomes <answer> or the number of retrieval steps reaches a threshold imax . The user instruction I continuously reminds the agent of the remaining retrieval attempts. If the information remains insufficient after exhausting all attempts, the R&A agent returns “Not mentioned”.
Abstraction. This step employs an abstraction agent to generate and encode an abstract for each abstract node. We consider two abstraction types. (1) Summative abstract: paragraphs of summary text (Sarthi et al., 2024; Edge et al., 2024) that capture coherent logic and key entity relationships. (2) Keyword abstract: keywords of different types distilled from the document chunks, with high information density but weak logical correlations. Phrases are encouraged over single words to preserve the entity co-occurrence.
Agent-powered Hybrid Retrieval. In a corpus-level search space, the coarse-grained upper-level abstracts make even simple factual searches challenging for Tree-RAG. To better capture fine-grained information, a sparse keyword index is constructed during tree indexing using BM25 (Robertson et al., 2009). During retrieval, the R&A agent combines results from both the tree and sparse indexes via two optional strategies: (1) parametrically, using a reranker model to integrate both top-k chunks; or (2) non-parametrically, via reciprocal rank fusion (RRF) (Cormack et al., 2009).
3.2. Multi-granular Agentic Retrieval Existing Tree-RAG frameworks struggle with multi-hop questions due to the structural isolation of tree indexes. For a multi-hop query like “Who is the wife of the man (David Gest) who produced the documentary of the pop star who influenced Beyoncé?”, a retriever relying solely on dense vector similarity would prioritize content related to “Beyoncé” and “documentary”, while missing the true subject “David Gest”. As such implicit associations often follow a causal order, existing tree retrieval methods like beam search (Sarthi et al., 2024; Gupta et al., 2025) are insufficient for ordered causality reasoning.
Furthermore, the R&A agent broadens the scope of sparse retrieval. It is encouraged to reorganize its query with enriched context, such as inserting descriptive appositions: reorganization
q : “Who is the wife of David Gest?” −−−−−−−→ q ′ : “Who is the wife of the American film producer David Gest?” This adds thematic keywords for the sparse retriever and, more importantly, aids the tree retriever in locating relevant upper-level abstract nodes with the high-level context. An algorithm of the agentic retrieval is given in Appendix A.
Retrieval and Answering (R&A) Agent. To capture ordered causality during reasoning, we employ a versatile R&A agent that intelligently engages in multi-turn interactions with the abstract tree index. It first assesses whether the available information is sufficient to answer the user query accurately or whether an additional retriever call is necessary. The agent response is a triple a = (R, <action>, ·) where the action tag is either <answer> or <retrieve>. If <retrieve> is returned, the agent proposes a new query q ′ and requests another retrieval. The newly retrieved documents are then fed back to the agent alongside the original user query for the next reasoning step.
4. Distribution Adaptability of Tree-RAG This section analyzes the distribution adaptability of kmeans-type Tree-RAG and Ψ-RAG. Tree-RAG methods like RAPTOR (Sarthi et al., 2024) build an equi-depth tree index via bottom-up k-means-type clustering, such as the Gaussian Mixture Model (GMM). However, k-means-type clustering tends to assign objects from major clusters to minor ones, resulting in clusters of relatively uniform size even when the corpus follows a skewed distribution. This is known as the “uniform effect” (Xiong et al., 2006; Liang et al., 2012; Assran et al., 2023). For RAG, this effect may cause the retriever to overlook chunks with minor themes. In contrast, Ψ-RAG better preserves skewed distributions in corpora. We compare the two tree RAG frameworks through the lens of their optimization objectives.
For each retrieval step, Ψ-RAG performs top-down dense vector matching following (Sarthi et al., 2024). Starting from the root, it computes the cosine similarity s(q, u) between the query vector and each candidate node at layer l, selecting theStop-k nodes Ul . Then, all children of the selected nodes u∈Ul c(u) become the candidates for the next layer. This process iterates until the leaf layer is reached.
4.1. The Uniform Effect k-means-type tree index. A cluster can be defined as a family of leaf sets C = {c = ℓ(Tc )} from an equi-depth forest {Tc ⊆ T |δ(Tc ) = δ(T )−1}. A k-means-type cluster tree searches for an optimal C by minimizing the objective
Our agentic retrieval workflow is as follows. Given a user query q, an initial retrieval is invoked. The returned top-k chunks D0∗ are fed to the agent, yielding a1 = f (q0 ; I(D0∗ )). Then, “retrieval-generation” steps are iterated: i [ Di∗ = r(qi′ ,T ), ai+1 = f q; (I(Dj∗ )∪aj ) ∪ I(D0∗ ) (3)
L=
k X X i=1 xi ∈ci
j=1
4
2
∥xi − µi ∥ ,
(4)
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation
P where k = |C|, µi = xi ∈ci nxii is the cluster centroid and ni = |ci |. Theorem 4.1 presents a variant of (4) that reveals the “uniform effect” in k-means clustering.
minimization objective of AHC (Moseley & Wang, 2017; Charikar & Chatziafratis, 2017; Chami et al., 2020). Based on Dasgupta’s cost, we analyze two scenarios: (1) whether Ψ-RAG tends to build a tree with uniform leaf distribution, and (2) whether it adaptively generates subtrees of varying sizes for minor clusters. Our findings are formalized in the following Theorems.
Theorem 4.1 (Uniform effect of k-means (Liang et al., 2012)). Given L in (4), we have X 2 L = −A ni nj ∥µi − µj ∥ + B (5) 1≤i<j≤k
Theorem 4.3 (Non-uniformity preference of Ψ-RAG). Consider a 3-layer equi-depth multifurcating tree T with a perfectly uniform leaf distribution among its subtrees T1 , · · · , Tk : n1 = n2 = · · · = nk = n/k, where k ≥ 3, n ≥ 3k. A new tree T ′ is constructed by moving one leaf from Tj to another subtree Ti . Then: (1) c(T ′ ) < c(T ); ′ (2) Let T = ψ(TAHC ) and T ′ = ψ(TAHC ), where ψ(·) denotes the collapsing process from a binary tree to an equidepth multifurcating tree. Denote by ∆c and ∆c′ the increments of Dasgupta’s cost on T and T ′ introduced by ψ(·), respectively. Then we have c(T ′ ) − c(T ) = ∆c′ − ∆c.
where A and B are constants dependent only on the data. See Section B.1 for the proof. Assuming ni nj and 2 ∥µi − µj ∥ are independent, maximizing the term ni nj in (5) leads to n1 = n2 = · · · = nk = n/k. This indicates that k-means favors clusters of uniform size. (Proposition 1, (Assran et al., 2023)) further notes that soft k-means, i.e., GMM, shares the same global optimum and the uniform effect with k-means. Figure 4 shows a toy example where k-means gradually shifts the minor cluster centroid toward the major class, inflating the minor cluster beyond its actual size. This may confuse abstract nodes in a tree index which leads to semantic bias or neglect of minor nodes. Major cluster
Minor cluster
Major centroid
Theorem 4.4 (Distribution adaptability of Ψ-RAG). Consider a 3-layer equi-depth multifurcating tree T with subtrees T1 , · · · , Tk of any size where k ≥ 3. A subtree of a minor leaf cluster Ti has 2 ≤ ni < nj , ∀1 ≤ j ̸= i ≤ k. A new tree T ′ is constructed by moving one leaf from some subtree Tj to the minor subtree Ti . Then: (1) c(T ′ ) ≥ c(T ), and c(T ′ ) = c(T ) iff nj = ni + 1; ′ (2) Let T = ψ(TAHC ), T ′ = ψ(TAHC ) and ∆c, ∆c′ defined ′ as in Theorem 4.3. Then we have ∆c ≥ ∆c, and ∆c′ = ∆c iff nj = ni + 1.
Minor centroid
uniform shift
See Section B.2 and Section B.3 for the proofs and remarks. The above theorems prove that Ψ-RAG incurs a larger increment in Dasgupta’s cost for (1) a tree with perfectly uniform leaf distribution, and (2) a tree where nodes from major clusters are assigned to a minor cluster. They show that Ψ-RAG does not suffer from the uniform effect and, furthermore, adaptively preserves skewed distributions within corpora.
Figure 4. The uniform effect of k-means clustering. Initial centroids are set at the center of each class (step 0). As iteration proceeds, more major class nodes are misassigned to the minor cluster, eventually shifting the minor centroid (step 12).
Ψ-RAG’s hierarchical index. Ψ-RAG is inspired by agglomerative hierarchical clustering (AHC) (Florek et al., 1951; Sokal & Michener, 1958), a greedy heuristic algorithm without an explicit optimization objective. We therefore adopt a widely used metric for evaluating AHC.
4.2. Visualization Study on Skewed Data We conduct a visualization study by constructing tree indexes with both RAPTOR and Ψ-RAG on skewed datasets to validate the above conclusions. Three skewed datasets are generated from MultiHop-RAG (Tang & Yang, 2024): each combines the first 5 documents from one of three categories: “Business”, “Entertainment”, or “Technology”, with the first 50 documents from the semantically distant “Sports” class, as shown in Figure 5(a). We extract the bottom four layers of each tree and visualize them as circular trees.
Definition 4.2 (Dasgupta’s cost (Dasgupta, 2016)). For a tree T , the Dasgupta’s cost is defined as X c(T ) = d(ui , uj )|ℓ(LCA(ui , uj ))| (6) 1≤i<j≤n
where d(·, ·) is a distance function.
The results in Figure 5(b) reveal that major abstract nodes in RAPTOR tend to be confused with (i.e., share a parent with) minor ones especially at higher layers, which is a manifestation of the uniform effect. In contrast, Ψ-RAG assigns
The intuition is that semantically similar points (with small d) should have a deeper LCA, i.e., be placed closer in the tree. Dasgupta’s cost is widely regarded as the implicit 5
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation (a) Embedding space (MultiHop-RAG)
(b)
S[:50] + B[:5]
S[:50] + E[:5]
S[:50] + T[:5]
Major leaf nodes (S) Minor leaf nodes (B)
Major leaf nodes (S) Minor leaf nodes (E)
Major leaf nodes (S) Minor leaf nodes (T)
RAPTOR
Sports (S)
𝚿-RAG
Business (B) Entertainment (E)
Technology (T)
Major abstract nodes confused with minor abstract nodes
Figure 5. RAPTOR vs. Ψ-RAG on skewed distributions. (a) 2-dimensional embedding space of the four main categories of MultiHopRAG. (b) Circular tree visualizations (only regions containing minor class nodes are shown). The outermost ring represents leaf nodes. For S[:50]+B[:5], red points represent “Sports” nodes, while blue points and edges trace root-to-leaf paths for “Business” nodes. The red shaded area indicates the retrieval noise introduced by confused nodes (p). Comparing the number of confused nodes and the size of the shaded areas, Ψ-RAG organizes minor classes more effectively.
far fewer major abstract nodes to minor ones, resulting in an intuitively superior index structure. A detailed case study of the confused abstracts and its negative effect on retrieval is provided in Appendix D.2.
MultihopQA) (Ho et al., 2020), and MuSiQue (Trivedi et al., 2022). We also include the first 1,000 questions from MultiHop-RAG (Tang & Yang, 2024), a multi-hop benchmark containing negative samples. For narrative QA, 10 long documents are randomly sampled from NarrativeQA (Kočiskỳ et al., 2018). We also use the first 100 documents from the LongBook subset in ∞Bench (Zhang et al., 2024a), a narrative QA dataset featuring significantly longer documents. For summarization, we adopt QMSum (Zhong et al., 2021) and WCEP (Ghalandari et al., 2020). Overly short documents are filtered out following (Zhang et al., 2025a). Further dataset details are provided in Appendix C.
5. Experiments 5.1. Experimental Setup Tasks and evaluation metrics. Our evaluation encompasses four types of tasks. (1) Single-hop and multi-hop QA (token-level fact answering) involves detailed facts within one or multiple passages under a cross-document setting. A word or a phrase is required as an answer. We use Recall@k (k = 2, 5) for retrieval metrics and use Exact Match (EM) and F1 score for QA. (2) Narrative QA (passage-level causal reasoning) requires the model to identify causal relationships within a single long document for a narrative answer. Given the variable answer length, we employ F1 and the Recall-Oriented Understudy for Gisting Evaluation using the Longest Common Subsequence (ROUGE-L) as metrics. (3) Document-level summarization requires a comprehensive understanding of a single long document in response to a fixed query: “Summarize the contents of this meeting / news event”. Iterative retrieval and the sparse index are disabled for this task. Given the variable answer length and format, we use ROUGE-L as the metric.
Baselines. Our baselines cover various RAG paradigms. (1) Traditional RAG: the sparse retriever BM25 (Robertson et al., 2009), the dense vector retriever DPR (Karpukhin et al., 2020) with Faiss (Douze et al., 2025), and the strong hybrid retriever BM25 + DPR equipped with a reranker. Another baseline involves DPR equipped with an iterative agentic retriever IRCoT (Trivedi et al., 2023). (2) Graph-RAG: GraphRAG from Microsoft (Edge et al., 2024), the state-ofthe-art framework HippoRAG 22 (Jiménez Gutiérrez et al., 2025), and GoR (Zhang et al., 2025a), a new summarizationexclusive Graph-RAG framework. (3) Tree-RAG: RAPTOR (Sarthi et al., 2024), the only open-source framework that can be technically implemented to a corpus-level index. Implementation details. Ψ-RAG (and all dense retrieval baselines) by default uses Qwen3-Embedding-8B (Q3-8B) (Zhang et al., 2025b) as the encoder and Llama-3.3-70B (L370B) (Dubey et al., 2024) as the abstraction and R&A agent. We use BM25S (Lù, 2024) as the BM25 implementation.
Datasets. Each task is evaluated on multiple benchmark datasets. For single-hop and multi-hop QA, we mainly follow HippoRAG 2 (Jiménez Gutiérrez et al., 2025) and use 1,000 randomly sampled queries from (1) single-hop: NQ (Kwiatkowski et al., 2019) and PopQA (Mallen et al., 2023); (2) multi-hop: HotpotQA (Yang et al., 2018), 2Wiki (2Wiki-
2 We report both the original setting (with NV-Embed-V2 (Lee et al., 2025)) and our setting with Q3-8B and Q3R.
6
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation Table 2. Single- and multi-hop QA results in EM (%) and F1 (%). Best results are in bold. Second-bests are underlined. MuSiQue
MultiHop-RAG
EM
F1
EM
F1
EM
F1
EM
F1
EM
F1
EM
F1
EM
F1
Traditional RAG
BM25 DPR BM25 + DPR + Q3R DPR + IRCoT + Q3R
45.4 46.0 48.2 50.1
56.76 59.09 60.58 62.71
40.9 47.2 47.2 47.3
49.01 55.89 56.01 56.98
43.8 52.0 58.4 59.1
54.07 63.10 70.98 71.00
34.7 39.9 41.6 48.9
36.90 43.13 45.43 53.44
13.0 18.7 28.3 29.7
17.96 24.03 34.81 37.36
2.5 41.3 52.9 41.7
3.93 42.72 53.49 42.28
23.55 40.85 46.10 46.13
36.44 47.99 53.55 53.96
Graph-RAG
GraphRAG HippoRAG 2 HippoRAG 2 + Q3R
36.0 47.4 45.7
50.85 62.42 60.99
32.7 43.4 43.3
42.13 55.90 56.05
54.9 61.9 58.7
66.30 75.40 71.52
52.2 64.8 60.1
56.62 71.35 66.00
25.8 37.5 32.9
30.70 48.00 43.27
37.3 17.7 17.6
39.08 19.36 19.37
39.82 45.45 43.05
47.61 55.41 52.87
Tree-RAG
RAPTOR + Q3R Ψ-RAG A Ψ-RAG ø
43.5 50.0 50.6
55.40 63.45 63.58
19.8 46.7 46.1
25.76 56.74 55.88
43.1 62.1 62.2
52.54 74.59 74.85
19.1 69.1 69.0
22.16 76.73 76.94
16.6 38.7 37.9
21.10 48.90 47.83
42.5 55.3 54.1
43.20 56.23 55.18
30.77 53.65 53.32
36.69 62.77 62.38
Type
NQ
Method
PopQA
HotpotQA
2Wiki
Average
Table 3. Retrieval results for single- and multi-hop QA in Recall@2 (R@2%) and Recall@5 (R@5%). Best results are in bold. Second-bests are underlined. Type
NQ
Method
PopQA
HotpotQA
2Wiki
MuSiQue
Average
R@2
R@5
R@2
R@5
R@2
R@5
R@2
R@5
R@2
R@5
R@2
R@5
Traditional RAG
BM25 DPR BM25 + DPR + Q3R DPR + IRCoT + Q3R
28.20 27.13 46.29 46.16
56.03 69.51 76.63 76.10
23.90 20.85 42.90 42.75
35.70 49.70 50.55 50.45
57.25 35.25 85.70 84.50
74.80 86.75 93.80 92.40
54.70 32.30 68.95 69.20
64.98 71.03 74.52 74.08
28.78 33.11 50.92 50.90
35.40 48.08 67.35 66.02
38.57 29.73 58.95 58.70
53.38 65.01 72.57 71.81
Graph-RAG
HippoRAG 2 HippoRAG 2 + Q3R
45.32 42.09
77.11 73.68
44.30 46.60
50.75 50.45
84.05 74.70
94.40 90.65
75.40 70.00
89.92 80.73
55.67 49.02
73.77 64.64
60.95 56.48
77.19 72.03
Tree-RAG
RAPTOR + Q3R Ψ-RAG A Ψ-RAG ø
41.56 46.08 45.88
68.48 75.72 75.13
21.20 43.35 42.60
23.80 51.30 50.55
67.10 88.15 88.10
72.25 96.00 95.80
40.93 81.35 81.23
44.57 96.13 95.85
33.29 57.21 55.69
42.26 75.77 75.08
40.82 63.23 62.70
50.27 78.98 78.48
Ψ-RAG is equipped with Qwen3-Reranker-8B (Q3R) to fuse retrieval results from sparse and dense retrievers. For a fair comparison, most baselines are also equipped with Q3R. Detailed configurations and instruction prompts are provided in Appendix C.
On 5 out of 6 datasets, RAPTOR + Q3R underperforms DPR without a reranker, showing degradations exceeding 25% in Recall@5 and 30% in F1 on PopQA. This highlights a key limitation of traditional Tree-RAG: as the index space expands, performance on factual QA is severely hampered by coarse-grained abstracts.
5.2. Single- and Multi-Hop QA
(4) Ψ-RAG achieves strong performance across both task types. Compared to RAPTOR, Ψ-RAG achieves average gains of 25.9% in F1 and 23.7% in Recall@5, irrespective of the abstraction type. Notably, Ψ-RAG surpasses RAPTOR by up to 54.78% in F1 on 2Wiki. To our knowledge, Ψ-RAG is the first Tree-RAG to surpass advanced GraphRAG, outperforming HippoRAG 2 by 7.4% and HippoRAG 2 + Q3R by 9.9% in average F1. We also find that the summative abstract slightly outperforms the keyword abstract. This indicates that logical relationships between entities can effectively compensate for abstract coarseness.
We use the symbols “ A ” and “ ø ” to denote Ψ-RAG with summative and keyword abstract, respectively. Retrieval and QA results on single-hop and multi-hop datasets are presented in Table 2 and 3, yielding several key observations. (1) Traditional baselines excel at single-hop QA. For factual questions with little context such as NQ and PopQA, DPR and its hybrid combination with BM25 achieve recall and accuracy competitive with HippoRAG 2 and Ψ-RAG. In such cases, answers often lie in documents with frequent query-related entities or strong semantic correlation.
5.3. Narrative QA and Summarization
(2) Multi-hop QA is the domain of iterative agentic RAG and structured RAG. Both IRCoT and HippoRAG 2 outperform the hybrid retriever BM25 + DPR on 3 out of 4 multi-hop datasets, with the highest F1 gains exceeding 20%. This underscores the necessity of modeling implicit entity relationships for multi-hop reasoning.
Table 4 shows the performance of narrative QA and summarization. We derive the following observations: (1) Traditional baselines struggle to capture causal relationships and high-level semantics. Unlike in token-level QA, BM25 and DPR achieve the lowest performance in most cases. This indicates that simple keyword matching
(3) RAPTOR’s effectiveness diminishes at corpus scale. 7
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation Table 4. Narrative QA results in F1 (%) and ROUGE-L (R-L%), and summarization results in ROUGE-L (R-L%). Best results are in bold. Second-bests are underlined. ∞-LongBook
NarrativeQA
Method BM25 DPR BM25 + DPR + Q3R
WCEP
F1
R-L
F1
R-L
R-L
R-L
13.95 17.78 20.30
14.07 17.87 20.37
14.87 21.51 24.46
15.54 23.60 24.87
15.63 13.43 13.42
16.08 8.14 8.14
–
–
–
–
15.98
13.98
21.36 27.84 27.66
21.61 28.43 28.35
13.90 25.52 28.44
15.85 27.11 28.36
16.53 16.87 16.65
18.33 20.28 18.81
GoR + Q3R RAPTOR + Q3R Ψ-RAG A Ψ-RAG ø
QMSum
Table 5. Query reorganization (QR) ablation in F1 (%). Best results are in bold. Ψ-RAG w/o QR
2Wiki
MuSiQue
MultiHop-RAG
74.85 74.17 (↓ 0.68)
76.94 76.71 (↓ 0.23)
47.83 45.82 (↓ 2.01)
55.18 55.03 (↓ 0.15)
more effectively than the non-parametric RRF, but it does not provide a core performance contribution in Ψ-RAG. (2) R&A agent is also beneficial for single-hop QA. For example, it brings a 1.89% F1 gain on NQ. This benefit stems from its query reorganization mechanism, which improves retrieval for queries with insufficient context.
and vector similarity are insufficient for passage-level and document-level user demands. On the contrary, structured indexes of RAPTOR and GoR empower the agent with highlevel information and thus higher performance on passageand document-level tasks.
Query reorganization. Table 5 evaluates a counterpart of Ψ-RAG without query reorganization, that is, the R&A agent is no longer encouraged to reorganize and enrich their generated queries at each retrieval attempt. This leads to performance degradation across multi-hop datasets, with a 2% F1 drop on MuSiQue. Therefore, the thematic keywords and high-level context introduced by query reorganization contribute to accurate hybrid retrieval of Ψ-RAG.
(2) Ψ-RAG excels in both narrative and summarization tasks. It consistently outperforms all baseline methods across both settings, surpassing RAPTOR by an average of 9.7% in F1 on NarrativeQA and ∞-LongBook. It also surpasses GoR by 3.2% in average ROUGE-L.
Table 6. Experiment results of Ψ-RAG with different open-source backbones. Replaced components are shaded.
NQ 63.58 60.07
HotpotQA
61.69
HotpotQA 53.64
MuSiQue
PopQA
47.83
55.71
42.21
55.88
45.78 27.83 27.56
34.06 20
35.73
44.93
67.04 69.24
76.94
2Wiki
R&A
Reranker
Q3-8B Q3-0.6B Q3-8B Q3-8B Q3-8B Q3-8B
L3-70B L3-70B L3-1B L3-8B L3-70B L3-70B
L3-70B L3-70B L3-70B L3-70B G3-27B L3-70B
Q3R Q3R Q3R Q3R Q3R BGE
74.85
MuSiQue
F1
R@5
F1
R@5
F1
95.80 94.40 94.45 93.65 95.00 95.10
74.85 74.48 73.23 73.72 73.65 74.32
95.85 95.55 95.77 95.83 94.05 95.80
76.94 75.94 76.78 76.30 71.78 76.85
75.08 73.42 73.14 74.29 71.80 72.46
47.83 46.57 47.00 47.46 49.30 48.40
w/o SR
HotpotQA
HotpotQA R&A
5.4. Ablation Studies w/o Q3R
2Wiki
R@5
Table 7. Experiment results of Ψ-RAG with different closed-source NQ R&A backbones.
w/o R&A
Figure 6. Ablation studies in F1 (%).
Ψ-RAG
Abstraction
Ψ-RAG
52.54
w/o Q3R 69.35
Embedding
w/o R&A
MuSiQue
MuSiQue
R@5
25
F1
R@5 PopQA F1
GPT-5-mini Gemini-2.5-Flash
94.40 96.00
78.10 77.18
72.67 77.06
49.48 51.86
25
w/o SR
Figure 6 presents the QA performance of Ψ-RAG with different components ablated: the R&A agent, sparse retrieval (SR), and reranker (Q3R). We use RRF instead of the reranker in the “w/o Q3R” setting. We have some key observations:
5.5. Backbone Flexibility Ψ-RAG can flexibly accommodate different backbone language models for its embedding model, abstraction agent, 2Wiki HotpotQA R&A agent, and reranker. We select various open-source models, including (1) Qwen3-Embedding-0.6B (Q3-0.6B) (Zhang et al., 2025b) as the embedding model; (2) Llama3.2-1B (L3-1B) and Llama-3.1-8B (L3-8B) (Dubey et al., 2024) as the abstraction agent; (3) Gemma-3-27B (G3-27B) (Kamath et al., 2025) as the R&A agent; and (4) BGEReranker-Large (BGE) (Li et al., 2023) as the reranker. The results are shown in Table 6. We observe that these models, especially L3-1B/8B and BGE, serve as effective lightweight alternatives, as they achieve comparable or even superior performance with lower costs.
(1) Ψ-RAG achieves peak performance when all components are combined together. Our R&A agent consistently improves performance on multi-hop QA tasks with an average gain of ∼20%. The contribution of sparse retrieval is also significant, especially on datasets like PopQA (+21.82%) and 2Wiki (+41.21%) with large amounts of short factual questions related to specific names. This validates its effectiveness in mitigating the coarse abstraction of the tree index. Furthermore, despite additional computational and storage costs, a large reranker integrates retrievers 8
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation Table 8. Time costs of different structured RAG. All experiments follow the settings in Appendix C. The embedding time of Q3-8B for HotpotQA and MuSiQue is 277.3s and 309.0s, respectively. L3-70B is used by default for abstraction of both RAPTOR and Ψ-RAG. “↑” and “↓” indicate a distinguishable higher and lower efficiency compared to RAPTOR + Q3R, respectively. Indexing time Method
HotpotQA
MuSiQue
Average single retrieval time HotpotQA
Average QA time
MuSiQue
HotpotQA
MuSiQue
HippoRAG 2
OpenIE: 105, 360s Graph indexing: 32, 187s Total: 137, 547s ↓↓
OpenIE: 128, 192s Graph indexing: 20, 668s Total: 148, 860s ↓↓
Graph retrieval: 10.44s ↓↓
Graph retrieval: 8.94s ↓↓
19.24s ↓
17.56s ↓
RAPTOR + Q3R
Tree indexing: 1, 123s Abstraction: 5, 509s Total: 6, 632s
Tree indexing: 1, 684s Abstraction: 7, 570s Total: 9, 254s
Tree retrieval: 0.22s Reranking: 0.98s Total: 1.20s
Tree retrieval: 0.22s Reranking: 2.17s Total: 2.39s
Single retrieval: 8.03s
Single retrieval: 12.71s
Ψ-RAG
Tree indexing: 124s ↑ Abstraction: 10, 425s ↓ Total: 10, 549s ↓
Tree indexing: 258s ↑ Abstraction: 11, 899s ↓ Total: 12, 157s ↓
Tree retrieval: 0.19s Sparse retrieval: < 0.01s Reranking: 0.79s Total: 0.98s ↑
Tree retrieval: 0.19s Sparse retrieval: < 0.01s Reranking: 1.07s ↑ Total: 1.26s ↑
Agentic retrieval: 8.49s
Agentic retrieval: 19.66s ↓
Ψ-RAG (Abstraction: L3-8B; R&A Agent: G3-27B; Reranker: BGE)
Tree indexing: 128s ↑ Abstraction: 2, 058s ↑ Total: 2, 186s ↑
Tree indexing: 265s ↑ Abstraction: 2, 222s ↑ Total: 2, 487s ↑
Tree retrieval: 0.19s Sparse retrieval: < 0.01s Reranking: 0.56s ↑ Total: 0.75s ↑
Tree retrieval: 0.19s Sparse retrieval: < 0.01s Reranking: 0.37s ↑ Total: 0.56s ↑
Agentic retrieval: 5.45s ↑
Agentic retrieval: 7.17s ↑
We also employ two popular closed-source LLMs: GPT5-Mini (OpenAI, 2025) and Gemini-2.5-Flash (Comanici et al., 2025), as the R&A agent in Ψ-RAG. The results are presented in Table 7. Even with a much smaller size than L3-70B, both models yield certain improvements in F1 score. For instance, employing Gemini-2.5-Flash as the R&A agent achieves a notably high F1 score of 51.86%.
HotpotQA), so we believe that it is justified in quality improvement for complex queries. Considering the limitations of similarity ranking when applied to industrial-scale corpora with 10M+ and even 100M+ tokens, we further propose two efficient tree-building extensions for Ψ-RAG: Bucketing and Approximate Nearest Neighbor Search with Hierarchical Navigable Small World (HNSW) (Malkov & Yashunin, 2018). See Appendix E for details.
5.6. Efficiency Analysis As Ψ-RAG is based on AHC, the computation, sorting, and storage of the similarity matrix introduce time and space complexities of O(n2 log n) and O(n2 ), respectively3 . Similarly, the iterative merging and collapse process takes O(n2 ) time. However, the highly optimized matrix multiplication and sorting techniques make our proposed framework still efficient for a domain-specific index.
More experiment results. Appendix D provides more extensive results, including case studies, failure studies, and more analyses towards the effectiveness of Ψ-RAG components.
Table 8 compares the time efficiency of Ψ-RAG with other baseline methods. Our abstract tree indexing is very fast, taking only 258 seconds on MuSiQue with 1.3 million tokens (the similarity ranking process only takes ∼30s), which is 6.5× faster than RAPTOR and considerably more efficient than HippoRAG 2 on domain-specific corpora4 . However, as Ψ-RAG includes more abstract nodes, it takes more time for abstraction. For retrieval efficiency, the top-down search algorithm inherently has O(log n) complexity, resulting in lower average retrieval latency compared to HippoRAG 2. While Ψ-RAG’s iterative agentic retrieval process increases the latency, it is proportional to the complexity of the user demand (one additional retrieval attempt opportunity only brings an increment of 0.46s compared to RAPTOR on
We propose Ψ-RAG, a hierarchical Tree-RAG framework supporting corpus-level indexing and cross-document multihop user questions. By a hierarchical clustering-based abstract tree index and a multi-granular agentic retriever, ΨRAG addresses key limitations of k-means-type tree indexes such as poor distribution adaptability, structural isolation, and coarse abstraction. Extensive experimental results demonstrate that Ψ-RAG achieves substantial gains across tasks of diverse granularities, promoting the development of tree-RAG in the rapidly evolving era of LLMs.
6. Conclusion
Acknowledgements This work was partially supported by the Guangdong Provincial Natural Science Foundation General Program (Grant No. 2026A1515012118).
3
We omit the vector dimension d as d ≪ n in the real-world scenario. 4 Existing Graph-RAG papers tend not to include OpenIE extraction in the calculation of indexing time. This may lead to a significant inconsistency between the reported time and the actual running time.
We thank Linxiao Cao for his assistance in the comparative experiment. We also thank the anonymous reviewers, the Associate Chair, the Program Chair, etc. for their constructive feedback and recognition of this work. 9
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation
Impact Statement
Conference on Empirical Methods in Natural Language Processing, pp. 15159–15177, 2024.
This work focuses on retrieval-augmented generation (RAG) for large language models (LLMs) with a structured index. While this work may have broad applications in knowledge-intensive natural language processing tasks, we do not identify any societal impacts that extend beyond those common to LLMs and retrieval systems.
Comanici, G., Bieber, E., Schaekermann, M., Pasupat, I., Sachdeva, N., Dhillon, I., Blistein, M., Ram, O., Zhang, D., Rosen, E., et al. Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities. arXiv preprint arXiv:2507.06261, 2025.
References
Cormack, G. V., Clarke, C. L., and Buettcher, S. Reciprocal rank fusion outperforms condorcet and individual rank learning methods. In Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, pp. 758–759, 2009.
Arivazhagan, M. G., Liu, L., Qi, P., Chen, X., Wang, W. Y., and Huang, Z. Hybrid hierarchical retrieval for opendomain question answering. In Findings of the Association for Computational Linguistics: ACL 2023, pp. 10680–10689, 2023.
Dasgupta, S. A cost function for similarity-based hierarchical clustering. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 118–127, 2016.
Asai, A., Wu, Z., Wang, Y., Sil, A., and Hajishirzi, H. SelfRAG: Learning to retrieve, generate, and critique through self-reflection. In Proceedings of the 12th International Conference on Learning Representations, 2024.
Douze, M., Guzhva, A., Deng, C., Johnson, J., Szilvasy, G., Mazaré, P.-E., Lomeli, M., Hosseini, L., and Jégou, H. The Faiss library. IEEE Transactions on Big Data, 2025.
Assran, M., Balestriero, R., Duval, Q., Bordes, F., Misra, I., Bojanowski, P., Vincent, P., Rabbat, M., and Ballas, N. The hidden uniform cluster prior in self-supervised learning. In Proceedings of the 11th International Conference on Learning Representations, 2023.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., AlDahle, A., Letman, A., Mathur, A., Yang, A., Fan, A., et al. The Llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024.
Banko, M., Cafarella, M. J., Soderland, S., Broadhead, M., and Etzioni, O. Open information extraction from the web. In Proceedings of the 20th International Joint Conference on Artifical intelligence, pp. 2670–2676, 2007.
Edge, D., Trinh, H., Cheng, N., Bradley, J., Chao, A., Mody, A., Truitt, S., Metropolitansky, D., Ness, R. O., and Larson, J. From local to global: A graph RAG approach to query-focused summarization. arXiv preprint arXiv:2404.16130, 2024.
Bentley, J. L. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18 (9):509–517, 1975.
Fan, W., Ding, Y., Ning, L., Wang, S., Li, H., Yin, D., Chua, T.-S., and Li, Q. A survey on RAG meeting LLMs: Towards retrieval-augmented large language models. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 6491–6501, 2024.
Chami, I., Gu, A., Chatziafratis, V., and Ré, C. From trees to continuous embeddings and back: Hyperbolic hierarchical clustering. In Proceedings of the 34th International Conference on Neural Information Processing Systems, volume 33, pp. 15065–15076, 2020.
Fatehkia, M., Lucas, J. K., and Chawla, S. T-RAG: lessons from the LLM trenches. arXiv preprint arXiv:2402.07483, 2024.
Charikar, M. and Chatziafratis, V. Approximate hierarchical clustering via sparsest cut and spreading metrics. In Proceedings of the 38th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 841–854. SIAM, 2017.
Florek, K., Łukaszewicz, J., Perkal, J., Steinhaus, H., and Zubrzycki, S. Sur la liaison et la division des points d’un ensemble fini. In Colloquium Mathematicum, volume 2, pp. 282–285, 1951.
Chen, B., Guo, Z., Yang, Z., Chen, Y., Chen, J., Liu, Z., Shi, C., and Yang, C. PathRAG: Pruning graph-based retrieval augmented generation with relational paths. In Proceedings of the 40th AAAI Conference on Artificial Intelligence, 2026.
Gao, L., Dai, Z., Chen, T., Fan, Z., Van Durme, B., and Callan, J. Complement lexical retrieval model with semantic residual embeddings. In 43rd European Conference on Information Retrieval, pp. 146–160. Springer, 2021.
Chen, T., Wang, H., Chen, S., Yu, W., Ma, K., Zhao, X., Zhang, H., and Yu, D. Dense X Retrieval: What retrieval granularity should we use? In Proceedings of the 2024 10
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation
Ghalandari, D. G., Hokamp, C., Glover, J., Ifrim, G., et al. A large-scale multi-document summarization dataset from the Wikipedia current events portal. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 1302–1308, 2020.
Jin, J., Zhu, Y., Dou, Z., Dong, G., Yang, X., Zhang, C., Zhao, T., Yang, Z., and Wen, J.-R. FlashRAG: A modular toolkit for efficient retrieval-augmented generation research. In Companion Proceedings of the ACM on Web Conference, pp. 737–740, 2025c.
Guo, Z., Xia, L., Yu, Y., Ao, T., and Huang, C. LightRAG: Simple and fast retrieval-augmented generation. In Findings of the Association for Computational Linguistics: EMNLP 2025, 2025.
Jones, C. H. Generalized hockey stick identities and ndimensional blockwalking. The Fibonacci Quarterly, 34 (3):280–288, 1996.
Gupta, N., Chang, W.-C., Bui, N., Hsieh, C.-J., and Dhillon, I. S. LLM-guided hierarchical retrieval. arXiv preprint arXiv:2510.13217, 2025.
Kamath, A., Ferret, J., Pathak, S., Vieillard, N., Merhej, R., Perrin, S., Matejovicova, T., Ramé, A., Rivière, M., et al. Gemma 3 technical report. arXiv preprint arXiv:2503.19786, 2025.
Ho, X., Nguyen, A.-K. D., Sugawara, S., and Aizawa, A. Constructing a multi-hop QA dataset for comprehensive evaluation of reasoning steps. In Proceedings of the 28th International Conference on Computational Linguistics, pp. 6609–6625, 2020.
Karpukhin, V., Oguz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., and Yih, W.-t. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 6769–6781, 2020.
Huang, H., Huang, Y., Yang, J., Pan, Z., Chen, Y., Ma, K., Chen, H., and Cheng, J. Retrieval-augmented generation with hierarchical knowledge. arXiv preprint arXiv:2503.10150, 2025.
Khattab, O. and Zaharia, M. ColBERT: Efficient and effective passage search via contextualized late interaction over BERT. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, pp. 39–48, 2020.
Izacard, G., Caron, M., Hosseini, L., Riedel, S., Bojanowski, P., Joulin, A., and Grave, E. Unsupervised dense information retrieval with contrastive learning. Transactions on Machine Learning Research, 2022.
Kočiskỳ, T., Schwarz, J., Blunsom, P., Dyer, C., Hermann, K. M., Melis, G., and Grefenstette, E. The NarrativeQA reading comprehension challenge. Transactions of the Association for Computational Linguistics, 6:317–328, 2018.
Jardine, N. and van Rijsbergen, C. J. The use of hierarchic clustering in information retrieval. Information Storage and Retrieval, 7(5):217–240, 1971.
Kwiatkowski, T., Palomaki, J., Redfield, O., Collins, M., Parikh, A., Alberti, C., Epstein, D., Polosukhin, I., Devlin, J., Lee, K., et al. Natural Questions: a benchmark for question answering research. Transactions of the Association for Computational Linguistics, 7:453–466, 2019.
Jiménez Gutiérrez, B., Shu, Y., Gu, Y., Yasunaga, M., and Su, Y. HippoRAG: Neurobiologically inspired long-term memory for large language models. Proceedings of the 38th Conference in Neural Information Processing Systems, pp. 59532–59569, 2024.
Lee, C., Roy, R., Xu, M., Raiman, J., Shoeybi, M., Catanzaro, B., and Ping, W. NV-Embed: Improved techniques for training LLMs as generalist embedding models. In Proceedings of the 13th International Conference on Learning Representations, 2025.
Jiménez Gutiérrez, B., Shu, Y., Qi, W., Zhou, S., and Su, Y. From RAG to memory: Non-parametric continual learning for large language models. In Proceedings of the 42nd International Conference on Machine Learning, pp. 21497–21515, 2025. Jin, B., Yoon, J., Han, J., and Arik, S. O. Long-context LLMs meet RAG: Overcoming challenges for long inputs in RAG. In Proceedings of the 13th International Conference on Learning Representations, 2025a.
Lee, D., Hwang, S.-w., Lee, K., Choi, S., and Park, S. On complementarity objectives for hybrid retrieval. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 13357–13368, 2023.
Jin, J., Li, X., Dong, G., Zhang, Y., Zhu, Y., Wu, Y., Li, Z., Qi, Y., and Dou, Z. Hierarchical document refinement for long-context retrieval-augmented generation. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 3502–3520, 2025b.
Lewis, P., Perez, E., Piktus, A., Petroni, F., Karpukhin, V., Goyal, N., Küttler, H., Lewis, M., Yih, W.-t., Rocktäschel, T., et al. Retrieval-augmented generation for knowledgeintensive NLP tasks. In Proceedings of the 34th Conference on Neural Information Processing Systems, pp. 9459–9474, 2020. 11
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation
Li, C., Liu, Z., Xiao, S., and Shao, Y. Making large language models a better foundation for dense retrieval. arXiv preprint arXiv:2312.15503, 2023.
Moseley, B. and Wang, J. R. Approximation bounds for hierarchical clustering: average linkage, bisecting K-means, and local search. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 3097–3106, 2017.
Li, M., Miao, S., and Li, P. Simple is effective: The roles of graphs and large language models in knowledge-graphbased retrieval-augmented generation. In Proceedings of the 13th International Conference on Learning Representations, 2025a.
Nair, I., Garimella, A., Srinivasan, B. V., Modani, N., Chhaya, N., Karanam, S., and Shekhar, S. A neural CRF-based hierarchical approach for linear text segmentation. In Findings of the Association for Computational Linguistics: EACL 2023, pp. 883–893, 2023.
Li, X., Bai, Y., Jin, B., Zhu, F., Pan, L., and Cao, Y. Long context vs. RAG: Strategies for processing long documents in LLMs. In Proceedings of the 48th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 4110–4113, 2025b.
Omohundro, S. M. Five balltree construction algorithms. International Computer Science Institute Berkeley, 1989. OpenAI. Introducing GPT-5. 2025. URL https:// openai.com/index/introducing-gpt-5/.
Li, X., Dong, G., Jin, J., Zhang, Y., Zhou, Y., Zhu, Y., Zhang, P., and Dou, Z. Search-o1: Agentic search-enhanced large reasoning models. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pp. 5420–5438, 2025c.
Peng, B., Zhu, Y., Liu, Y., Bo, X., Shi, H., Hong, C., Zhang, Y., and Tang, S. Graph retrieval-augmented generation: A survey. ACM Transactions on Information Systems, 2025. Rezazadeh, A., Li, Z., Wei, W., and Bao, Y. From isolated conversations to hierarchical schemas: Dynamic tree memory representation for LLMs. In Proceedings of the 13th International Conference on Learning Representations, 2025.
Li, Y., Zhang, W., Yang, Y., Huang, W.-C., Wu, Y., Luo, J., Bei, Y., Zou, H. P., Luo, X., Zhao, Y., et al. Towards agentic RAG with deep reasoning: A survey of RAG-reasoning systems in LLMs. In Findings of the Association for Computational Linguistics: EMNLP 2025, 2025d.
Robertson, S., Zaragoza, H., et al. The probabilistic relevance framework: BM25 and beyond. Foundations and Trends® in Information Retrieval, 3(4):333–389, 2009.
Liang, J., Bai, L., Dang, C., and Cao, F. The K-means-type algorithms versus imbalanced data distributions. IEEE Transactions on Fuzzy Systems, 20(4):728–745, 2012. Liu, J. LlamaIndex, 2022. URL https://github. com/jerryjliu/llama_index. Liu, Y., Hashimoto, K., Zhou, Y., Yavuz, S., Xiong, C., and Yu, P. S. Dense hierarchical retrieval for open-domain question answering. In Findings of the Association for Computational Linguistics: EMNLP 2021, pp. 188–200, 2021.
Sarthi, P., Abdullah, S., Tuli, A., Khanna, S., Goldie, A., and Manning, C. D. RAPTOR: Recursive abstractive processing for tree-organized retrieval. In Proceedings of the 12th International Conference on Learning Representations, 2024. Sokal, R. R. and Michener, C. D. A statistical method for evaluating systematic relationships. 1958. Sparck Jones, K. A statistical interpretation of term specificity and its application in retrieval. Journal of documentation, 28(1):11–21, 1972.
Lù, X. H. BM25S: Orders of magnitude faster lexical search via eager sparse scoring. arXiv preprint arXiv:2407.03618, 2024.
Tang, Y. and Yang, Y. MultiHop-RAG: Benchmarking retrieval-augmented generation for multi-hop queries. In First Conference on Language Modeling, 2024.
Malkov, Y. A. and Yashunin, D. A. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4):824– 836, 2018.
Tao, W., Xing, X., Chen, Y., Huang, L., and Xu, X. TreeRAG: Unleashing the power of hierarchical storage for enhanced knowledge retrieval in long documents. In Findings of the Association for Computational Linguistics: ACL 2025, pp. 356–371, 2025.
Mallen, A., Asai, A., Zhong, V., Das, R., Khashabi, D., and Hajishirzi, H. When not to trust language models: Investigating effectiveness of parametric and non-parametric memories. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 9802–9822, 2023.
Trivedi, H., Balasubramanian, N., Khot, T., and Sabharwal, A. MuSiQue: Multihop questions via single-hop question composition. Transactions of the Association for Computational Linguistics, 10:539–554, 2022. 12
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation
Trivedi, H., Balasubramanian, N., Khot, T., and Sabharwal, A. Interleaving retrieval with chain-of-thought reasoning for knowledge-intensive multi-step questions. In Proceedings of the 61st annual meeting of the association for computational linguistics (volume 1: long papers), pp. 10014–10037, 2023.
Computational Linguistics (Volume 1: Long Papers), pp. 15262–15277, 2024a. Zhang, X., Wang, M., Yang, X., Wang, D., Feng, S., and Zhang, Y. Hierarchical retrieval-augmented generation model with rethink for multi-hop question answering. arXiv preprint arXiv:2408.11875, 2024b.
Wang, S., Fang, Y., Zhou, Y., Liu, X., and Ma, Y. ArchRAG: Attributed community-based hierarchical retrieval-augmented generation. arXiv preprint arXiv:2502.09891, 2025.
Zhang, Y., Li, M., Long, D., Zhang, X., Lin, H., Yang, B., Xie, P., Yang, A., Liu, D., Lin, J., et al. Qwen3 Embedding: Advancing text embedding and reranking through foundation models. arXiv preprint arXiv:2506.05176, 2025b.
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., et al. Chain-of-thought prompting elicits reasoning in large language models. In Proceedings of the 36th Conference in Neural Information Processing Systems, volume 35, pp. 24824–24837, 2022.
Zhao, Y., Zhu, J., Guo, Y., He, K., and Li, X. E2 GraphRAG: Streamlining graph-based RAG for high efficiency and effectiveness. arXiv preprint arXiv:2505.24226, 2025. Zhong, M., Yin, D., Yu, T., Zaidi, A., Mutuma, M., Jha, R., Hassan, A., Celikyilmaz, A., Liu, Y., Qiu, X., et al. QMSum: A new benchmark for query-based multi-domain meeting summarization. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 5905–5921, 2021.
Wu, Y., Wang, Y., Ye, Z., Du, T., Jegelka, S., and Wang, Y. When more is less: Understanding chain-of-thought length in LLMs. In ICLR 2025 Workshop on Reasoning and Planning for Large Language Models, 2025. Xiao, Y., Dong, J., Zhou, C., Dong, S., Zhang, Q.-w., Yin, D., Sun, X., and Huang, X. GraphRAG-Bench: Challenging domain-specific reasoning for evaluating graph retrieval-augmented generation. arXiv preprint arXiv:2506.02404, 2025. Xiong, H., Wu, J., and Chen, J. K-means clustering versus validation measures: a data distribution perspective. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 779–784, 2006. Yang, Z., Qi, P., Zhang, S., Bengio, Y., Cohen, W., Salakhutdinov, R., and Manning, C. D. HotpotQA: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 conference on empirical methods in natural language processing, pp. 2369–2380, 2018. Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K. R., and Cao, Y. ReAct: Synergizing reasoning and acting in language models. In Proceedings of the 11th International Conference on Learning Representations, 2022. Zhang, H., Feng, T., and You, J. Graph of records: Boosting retrieval augmented generation for long-context summarization with graphs. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 23780–23799, 2025a. Zhang, X., Chen, Y., Hu, S., Xu, Z., Chen, J., Hao, M., Han, X., Thai, Z., Wang, S., Liu, Z., et al. ∞Bench: Extending long context evaluation beyond 100k tokens. In Proceedings of the 62nd Annual Meeting of the Association for 13
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation
Appendix Contents A Algorithms of Ψ-RAG
15
B Theoretical Proofs
16
B.1 Proof of Theorem 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
B.2 Proof of Theorem 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
B.3 Proof of Theorem 4.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
C Detailed Experimental Setup
22
C.1 Dataset and Index Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
C.2 Configurations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
C.3 Instruction Prompts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
D Supplemental Experiments
25
D.1 Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
D.2 Analyses on Hierarchical Abstract Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
D.3 Analyses on Multi-granular Agentic Retriever . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
D.4 Failure Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
E Real-World Extensions
29
E.1 Approximate Nearest Neighbor Search for Efficient Indexing . . . . . . . . . . . . . . . . . . . . . . . .
29
E.2 Query Hop Discriminator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
F Related Work
30
G Discussion and Future Work
30
14
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation
A. Algorithms of Ψ-RAG
Algorithm 2 Tree Retrieval r(q, T ) Input: query q, tree index T , number of retrieved chunks k, maximum retrieval step imax Initialize candidate nodes V0 = {root(T )} for l = 0 to δ(T ) do if l = δ(T ) and |{u|δ(u) = l}| ≤ k then D∗ = ℓ(T ) break else if |{u|δ(u) = l}| ≤ k then Vl+1 = {u|δ(u) = l + 1} continue end if {Top-k nearest neighbor search} Ul = topk(Vl , q; k) if l = δ(T ) then D∗ = Ul else S Vl+1 = u∈Ul c(u) end if end for Output: top-k chunks D∗
Algorithm 1 shows the algorithm of Abstract Tree Indexing, while Algorithm 2 and Algorithm 3 show the algorithm of Multi-granular Agentic Retrieval. Algorithm 1 Abstract Tree Indexing Input: pairwise similarity matrix S Descending sort s(i, j) for all 1 ≤ i < j ≤ n Initialize T = (V = ∅, E = ∅) for rank(u, v) = 1 to n − 1, (u, v) ∈ S do if p(u) = p(v) = ∅ then Add node a in V and set c(a) = {u, v} else if root(u) ̸= root(v) and δ(u) = δ(v) then Add node a in V and set c(a) = {root(u), root(v)} else if root(u) ̸= root(v) and δ(u) > δ(v) then c(pδ(v)+1 (u)) ← c(pδ(v)+1 (u)) ∪ {root(v)} else if root(u) ̸= root(v) and δ(u) < δ(v) then c(pδ(u)+1 (v)) ← c(pδ(u)+1 (v)) ∪ {root(u)} end if end for Tree rebalancing by splitting overload nodes Generate abstract text for every abstract node Output: abstract tree T
Algorithm 3 Multi-granular Agentic Retrieval Input: user query q, tree index T , sparse index I, LLM agent f (·; I(·)), number of retrieved chunks k {Hybrid retrieval} Initialize D0∗ = r(q, T ) ∪ r(q, I) Current retrieval step i = 1 repeat if i = imax then Set I(Di∗ ) such that <action> = <answer> end if Generate ai = (Ri , <action>, ·) from (3) if ai = (Ri , <retrieve>, qi′ ) then Di∗ = r(qi′ , T ) ∪ r(qi′ , I) i←i+1 end if until ai = (R, <answer>, y) Output: answer y
15
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation
B. Theoretical Proofs B.1. Proof of Theorem 4.1 Theorem 4.1 (Uniform effect of k-means (Liang et al., 2012)). Given L in (4), we have X 2 L = −A ni nj ∥µi − µj ∥ + B
(7)
1≤i<j≤k
where A and B are constants only relative to the data. Proof. Let d(ci , cj ) = within k clusters as
P
2 xi ∈ci ,xj ∈cj ∥xi − xj ∥ . We first denote the sum of all pairwise distances of data samples x ∈ ℓ(T )
Pk =
n X n X
2
∥xi − xj ∥ =
i=1 j=1
k X
X
d(ci , ci ) + 2
i=1
d(ci , cj )
(8)
1≤i<j≤k
Then, we are going to prove Pk = where L↔ k =
k X n
n i=1 i
d(ci , ci ) + 2L↔ k ,
(9)
2
(10)
X
ni nj ∥µi − µj ∥
1≤i<j≤k
with mathematical induction. For k = 1, we have L↔ 1 = 0 as condition 1 ≤ i < j ≤ k cannot be met. So P1 =
P
x,y∈ℓ(T ) ∥x − y∥
2
which meets (9).
For k = 2, we have P2 = d(c1 , c1 ) + d(c2 , c2 ) + 2d(c1 , c2 ) X X X 2 2 = ∥xi − xj ∥ + ∥xi − xj ∥ + 2
(11) X
2
∥xi − xj ∥
(12)
1≤i≤n1 1≤j≤n2 n1 n2 X X X X 2 2 = 2(n1 − 1) ∥xi ∥ − 4 xi xj + 2(n1 − 2) ∥xi ∥ − 4 xi xj i=1 i=1 1≤i<j≤n1 1≤i<j≤n2 n1 n2 X X X X 2 2 + 2n2 ∥xi ∥ + 2n1 ∥xi ∥ − 4 xi xj i=1 i=1 1≤i≤n1 1≤j≤n2 1≤i<j≤n1
1≤i<j≤n2
(13)
n1 n2 X X X X n 2n(n − 1) n 2n(n − 1) 2 1 2 2 ∥xi ∥ − 4 · xi xj + ∥xi ∥ − 4 · xi xj = n1 n n n2 1 2 i=1 i=1 1≤i<j≤n1 1≤i<j≤n2 n1 n2 X X X X X X 2n 2n 2 1 2 2 ∥xi ∥ + 2 xi xj + ∥xi ∥ + 2 xi xj − 4 xi xj + n1 n 2 i=1 i=1
1≤i<j≤n1
1≤i<j≤n2
1≤i≤n1 1≤j≤n2
(14) n = n1 =
X 1≤i<j≤n1
n 2 ∥xi − xj ∥ + n2
X
2
∥xi − xj ∥ + 2n1 n2 ∥µ1 − µ2 ∥
2
(15)
1≤i<j≤n2
n n d(c1 , c1 ) + d(c2 , c2 ) + 2L↔ 2 n1 n2
(16)
which meets (9). Assume (9) holds with k = K − 1. Then for k = K, we have î PK = PK−1 + d(ci , ci ) + 2
X 1≤j̸=i≤K
16
d(ci , cj )
(17)
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation î where PK−1 is the sum of pairwise distances within K − 1 clusters excluding cluster ci for i = 1, 2, · · · , K.
We sum up (17) for every cluster ci and get KPK =
K X
î PK−1 +
i=1
K X
X
d(ci , ci ) + 4
i=1
d(ci , cj )
(18)
1≤i<j≤K
With our assumption: X
î PK−1 =
1≤j̸=i≤K
So K X
î PK−1 = (K − 2)
i=1
n − ni d(cj , cj ) + 2 nj
K X n i=1
ni
X
2
nj nκ ∥µj − µκ ∥
X
d(ci , ci ) + 2
(19)
1≤j<κ̸=i≤K
2
ni nj ∥µi − µj ∥
+
k X
d(ci , ci ),
(20)
d(ci , cj )
(21)
i=1
1≤i<j≤K
and from (8), we have KPK = (K − 2)
K X n i=1
= (K − 2)
⇒
PK =
K X n
n i=1 i
ni
K X n
n i=1 i
! d(ci , ci ) + 2L↔ K
+2
k X
d(ci , ci ) + 4
i=1
X 1≤i<j≤K
! d(ci , ci ) + 2L↔ K
+ 2PK
d(ci , ci ) + 2L↔ K
(22)
(23)
So (9) holds. With (9), we can now write L as k X X
k
1 X d(ci , ci ) 2 i=1 ni i=1 xi ∈ci k k 1 X n 1X ↔ ↔ L = d(ci , ci ) + 2Lk − 2n i=1 ni n i=1 k
L=
2
∥xi − µi ∥ =
1 Pk = − L↔ + , n k 2n
(24)
(25) (26)
k which completes the proof with A = − n1 and B = P 2n .
P 2 Remark. Theorem 4.1 proves that the objective of k-means is essentially maximizing L↔ k = 1≤i<j≤k ni nj ∥µi − µj ∥ . If 2 we assume ni nj and ∥µi − µj ∥ is independent, the maximization of ni nj leads to n1 = n2 = · · · = nk = n/k. B.2. Proof of Theorem 4.3 We first introduce necessary lemmas for Theorem 4.3 and Theorem 4.4. Lemma B.1 (Modularity of Dasgupta’s cost (Dasgupta, 2016)). Let Ta be the subtree in T rooted at node a. If a different tree T ′ is constructed by replacing Ta with another subtree Ta′ satisfying ℓ(Ta′ ) = ℓ(Ta ), then c(T ′ ) = c(T ) − c(Ta ) + c(Ta′ ) Proof. For any leaf pair where one leaf is inside Ta′ and the other is outside, the leaf count of its LCA is given by X ccross (Ta′ , T ′ \Ta′ ) = |ℓ(LCA(u, v))| = n′a + n1 + n2 + · · · u∈Ta′ ,v∈T ′ \Ta′
17
(27)
(28)
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation
Here, the total number of leaves in the current subtree n′a = na remains unchanged regardless of the subtree structure. Therefore: c(T ′ ) = c(Ta′ ) + c(T ′ \Ta′ ) + ccross (Ta′ , T ′ \Ta′ )
(29)
= c(Ta′ ) + c(T \Ta ) + ccross (Ta , T \Ta )
(30)
= c(Ta′ ) + c(T ) − c(Ta )
(31)
where c(T \Ta ) denotes the sum of costs among the subtrees of T excluding Ta . Remark. The modularity of Dasgupta’s cost allows us to, without loss of generality, decompose the problem of computing the global cost into analyzing cost differences within corresponding subtrees. 𝒯
𝒯AHC
𝑎 𝑐 𝑎
𝑏
𝛿(left subtree of ) = 1 𝛿(right subtree of ) = 0
𝑎
𝑑
𝑒
𝑐
𝑒 𝑏
𝑑
𝑏 𝛿(left subtree of ) = 0 𝛿(right subtree of ) = 1 𝛿(left subtree of ) = 0 𝛿(right subtree of ) = 1
Figure 7. Illustration of ψ(·): bottom-up traversal and collapsing. Note that both TAHC and T here are unordered, so the positions of b and c in T do not matter as long as they are children of a.
Lemma B.2 establishes the connection between the equi-depth multifurcating tree of Ψ-RAG and the binary tree of AHC. Lemma B.2 (Connection between AHC and Ψ-RAG). There exists a surjection ψ : TAHC 7→ T that maps every binary tree TAHC to an equi-depth multifurcating tree T by iteratively performing node collapsing. Proof. The proof is intuitive. First, the merging process of Ψ-RAG is identical to that in an AHC tree: both of them group two nodes under a common parent. We now focus on collapsing. As illustrated in Figure 7, the process ψ(TAHC ) can be viewed as a bottom-up layer-by-layer traversal process. Whenever a node is found whose subtrees have unequal depths, the root of the shallower subtree is collapsed to the corresponding node in the deepest subtree. This process iterates until every node has subtrees of equal depth. Therefore, any TAHC can always be mapped to an equi-depth multifurcating tree T = ψ(TAHC ). Remark. Lemma B.2 allows us to decompose ψ(TAHC ) bottom-up into a sequence of collapsing operations. Combined with Lemma B.1, it implies that ∆c = c(ψ(TAHC )) − c(TAHC ) can be decomposed into a layer-by-layer summation of the cost increments introduced by node collapse. Moreover, it is obvious that Dasgupta’s cost is invariant to the order of children of a certain node, so ∆c is invariant to the order of collapsing within a certain layer as well. In the following analysis, we follow the original paper (Dasgupta, 2016) by considering a computable scenario where the distance d = 1 for all pairs of chunks. The subsequent conclusions demonstrate that this assumption does not affect our conclusion of Ψ-RAG’s property. To analyze the non-uniformity preference of Ψ-RAG, Lemma B.3 quantifies the increment in Dasgupta’s cost introduced by node collapse. Lemma B.3 (Increment of Dasgupta’s cost of node collapse). The following holds: (1) For a leaf node collapse within a tree T , let the total number of leaves be |ℓ(T )| = n, and let Ta be the subtree rooted at the abstract node a to which the leaf node u is being linked, with |ℓ(Ta )| = na . This introduces an increment of Dasgupta’s cost ∆c = n2a . (2) For an abstract node collapse within a tree T , let the number of leaves of the subtree to be collapsed Tu be n′ . Let Ta be the subtree rooted at the abstract node a to which Tu is being linked. Ta has k branches with the number of leaves P n1 , n2 , · · · , nk , respectively. This introduces an increment of Dasgupta’s cost ∆c = n′ 1≤i<j≤k ni nj . 18
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation (a) leaf node
(b) abstract node 𝑛𝑎 𝑛 (1) within 𝒯𝑎 : 𝑐 = 2 𝑎
⋯ 𝒯𝑎
⋯
⋯
𝑘
𝒯𝑎
𝑎
(2) between 𝑢 and 𝒯𝑎 : 𝑐 = 𝑛𝑎 𝑛 + 1
𝑎 𝑢
𝑛𝑎
(1) between subtrees in 𝒯𝑎 : 𝑐= 𝒯𝑢
⋯
𝑘
(3) between 𝑢 and 𝒯 \ 𝒯𝑎 : 𝑐 = 𝑛 − 𝑛𝑎 𝑛 + 1 (4) between 𝒯𝑎 and 𝒯 \ 𝒯𝑎 : 𝑐 = 𝑛𝑎 𝑛 − 𝑛𝑎 𝑛
𝑛
⋯
⋯
⋯
𝑛1
𝑛𝑘
𝑛′
𝑛𝑚 + 𝑛′
𝑛𝑖 𝑛𝑗
1≤𝑖<𝑗≤𝑘
𝑚=1
(2) between 𝒯𝑢 and 𝒯𝑎 : 𝑘
𝑘
𝑐 = 𝑛′ 𝑛𝑖 ⋅ 𝑛𝑖 + 𝑛′ 𝑖=1
𝑖=1
collapse
collapse (1) within 𝒯𝑎 : 𝑐 = ⋯ 𝒯𝑎
𝑎 ⋯
⋯
𝑛𝑎 2
(1) between subtrees in 𝒯𝑎 : 𝒯𝑎
𝑛𝑎 + 1
𝑎
𝑛𝑎 𝑛
𝒯𝑢
⋯
(2) between 𝑢 and 𝒯𝑎 : 𝑐 = 𝑛𝑎 𝑛𝑎 + 1 𝑢
𝑘
𝑘
(3) between 𝑢 and 𝒯 \ 𝒯𝑎 : 𝑐 = 𝑛 − 𝑛𝑎 𝑛 + 1 (4) between 𝒯𝑎 and 𝒯 \ 𝒯𝑎 : 𝑐 = 𝑛𝑎 𝑛 − 𝑛𝑎 𝑛 + 1
𝑐=
⋯
⋯
⋯
𝑛1
𝑛𝑘
𝑛′
𝑛𝑖 𝑛𝑗
𝑛𝑚
1≤𝑖<𝑗≤𝑘
𝑚=1
(2) between 𝒯𝑢 and 𝒯𝑎 : 𝑘
𝑘
𝑐 = 𝑛′ 𝑛𝑖 ⋅ 𝑛𝑖 + 𝑛′ 𝑖=1
𝑖=1
Figure 8. Decomposition of Dasgupta’s cost for (a) leaf node collapse and (b) abstract node collapse. The Dasgupta’s costs of unmentioned components in the figure obviously remain invariant before and after the collapse.
Proof. (1) From Fig 8 (a), na na ∆c = (na + 1 − na ) + na (na + 1) − na (n + 1) + na (n − na )(n + 1 − n) = {z } | {z } | 2 2 | {z } ∆c(between u and Ta ) ∆c(between Ta and T \Ta )
(32)
∆c(within Ta )
(2) From Fig 8 (b), X
∆c =
ni nj
k X
′
nm + n −
m=1
1≤i<j≤k
!
∆c(between subtrees in Ta )
X
= n′
nm
m=1
{z
|
k X
ni nj
(33)
1≤i<j≤k
}
which ends the proof. Corollary B.4. By the Hockey-stick identity (Jones, 1996), the total cost increment from performing n − 2 consecutive leaf collapses on a binary branch (resulting in n ≥ 3 leaves) is n−1 X i n ∆c = = (34) 2 3 i=2 The total cost increment from collapsing K − k (K > k ≥ 2) identical subtrees onto node a (resulting in K subtrees) is K−1 K−1 X X X X ′ ′ ∆c = n ni nj = n ni nj (35) κ=k
1≤i<j≤κ
κ=k 1≤i<j≤κ
Now we are ready for the following theorem. Theorem 4.3 (Non-uniformity preference of Ψ-RAG). Consider a 3-layer equi-depth multifurcating tree T with a perfectly uniform leaf distribution among its subtrees T1 , · · · , Tk : n1 = n2 = · · · = nk = n/k, where k ≥ 3, n ≥ 3k. A new tree T ′ is constructed by moving one leaf from Tj to another subtree Ti . Then: (1) c(T ′ ) < c(T ); ′ (2) Let T = ψ(TAHC ) and T ′ = ψ(TAHC ). Denote by ∆c and ∆c′ the increments of Dasgupta’s cost on T and T ′ introduced by ψ(·), respectively. Then we have c(T ′ ) − c(T ) = ∆c′ − ∆c. Proof. (1) We visualize the scenario in Figure 9. Let m = n/k and we can know from Lemma B.1 that m k c(T ) = k m+ m2 n, 2 2 19
(36)
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation 𝒯′
𝒯 𝑘
𝑘 𝒯𝑗
𝒯𝑖 ⋯
⋯
⋯
⋯
𝑚
⋯
𝑚
𝒯𝑗
𝒯𝑖 ⋯
𝑚
⋯
⋯
𝑚
𝑚
⋯
⋯
⋯
𝑚+1
⋯
⋯
𝑚−1
𝑛
⋯
𝑚
𝑛 𝒯′
𝒯
Figure 9. An example of a uniform cluster tree (left) and moving a node from Tj to another subtree Ti (right). 𝑘
𝑘 m m+1 m−1 𝒯𝑗 𝒯𝑖 c(T ) = (k − 2) m+ (m + 1) + (m − 1) 2 2 2 ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ k−2 2 𝑛𝑗 n + (m + 1) 𝑛𝑘(m − 1) n + (k −𝑛2)(m + 1)mn + (k − 2)(m m 𝑛+ 𝑛𝑗 − 1 − 1)mn 𝑛𝑘 𝑛1 + 1 𝑖 1 2 major minor {z } | cluster cluster 𝒯𝑗
′ 𝒯𝑖
⋯
𝑛1
(37)
0 if k=3
So c(T ′ ) − c(T ) = 3m − n − 1,
(38)
′
which yields c(T ) < c(T ) if k ≥ 3. (2) According to Lemma B.2, we can decompose ψ(·) bottom-up into multiple leaf node collapses and multiple abstract ′ node collapses. From Corollary B.4, the total cost increments introduced by ψ(TAHC ) and ψ(TAHC ) are ∆c = k
k−1 X i m m k m2 = k + m3 , +m 3 2 3 3 i=2
(39)
m m−1 k−2 m+1 k−2 ∆c′ = (k − 2) + + m3 + (m − 1)m2 + 3 3 3 3 2 | {z } | {z } | {z } 0 if m=3
0 if k≤4
0 if k=3
k−2 m2 +(k − 2)m(m − 1) + (m + 1) 2 | {z }
(40)
0 if k=3
So we have ∆c′ − ∆c = 3m − n − 1 = c(T ′ ) − c(T )
(41)
which ends the proof. Remark. Theorem 4.3 proves that while traditional AHC assigns the same Dasgupta’s cost to the two different tree structures (c(T ) − ∆c = c(T ′ ) − ∆c′ ), the collapsing process in Ψ-RAG results in a lower Dasgupta’s cost for the tree with a non-uniform leaf distribution. This indicates that there is no uniform effect for Ψ-RAG even when pairwise distances between leaf nodes are unsorted. Moreover, as the computation of Dasgupta’s cost can be decomposed into that of each subtree, our conclusions can be generalized to trees with δ > 3. B.3. Proof of Theorem 4.4 Theorem 4.4 (Distribution adaptability of Ψ-RAG). Consider a 3-layer equi-depth multifurcating tree T with subtrees T1 , · · · , Tk of any size where k ≥ 3. A subtree of a minor leaf cluster Ti has 2 ≤ ni < nj , ∀1 ≤ j ̸= i ≤ k. A new tree T ′ is constructed by moving one leaf from some subtree Tj to the minor subtree Ti . Then: (1) c(T ′ ) ≥ c(T ), and c(T ′ ) = c(T ) iff nj = ni + 1; ′ (2) Let T = ψ(TAHC ), T ′ = ψ(TAHC ) and ∆c, ∆c′ defined as in Theorem 4.3. Then we have ∆c′ ≥ ∆c, and ∆c′ = ∆c iff nj = ni + 1. 20
𝒯𝑗
𝒯𝑖 ⋯
⋯
⋯
⋯
𝑚
⋯
𝑚
𝒯𝑗
𝒯𝑖 ⋯
𝑚
⋯
⋯
𝑚
𝑚
⋯
⋯
⋯
𝑚+1
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation 𝑛
𝑛1
𝑘
𝒯𝑗
⋯
⋯
𝑛𝑖 minor cluster
⋯
𝑚
𝑛
𝑘
⋯
⋯
𝒯′
𝒯
𝒯𝑖
⋯
𝑚−1
𝒯𝑗
𝒯𝑖 ⋯
⋯
𝑛𝑗 major cluster
⋯
⋯
𝑛𝑘
𝑛1
⋯
⋯
𝑛1 + 1
⋯
𝑛𝑗 − 1
⋯
⋯
𝑛𝑘
Figure 10. An example of a tree with a minor subtree Ti (left) and moving a node from a major subtree Tj to Ti (right).
Proof. (1) We visualize the scenario in Figure 10. So we have ni nj c(T ) = ni + nj + ni (n − ni )n + nj (n − nj )n + C, 2 2 ni + 1 nj − 1 c(T ′ ) = (ni + 1) + (nj − 1) + (ni − 1)(n − ni + 1)n + (nj − 1)(n − nj + 1)n + C 2 2 where C is a constant that remains invariant to the structure change. So 3n2i + ni − 3n2j + 5nj − 2 2 When nj = ni + 1, c(T ′ ) − c(T ) = 0. When nj = ni + x where x > 1, then c(T ′ ) − c(T ) = 2n(nj − ni − 1) +
3n2 + ni − 3(ni + x)2 + 5(ni + x) − 2 c(T ′ ) − c(T ) = 2n(x − 1) + i 2 3x − 2 = 2n − 3ni − (x − 1) 2 X 3x − 2 (x − 1) = 2 ni + n i + x + no − 3ni − 2 o̸=i,j X x = ni + 2 no + + 1 (x − 1) 2
(42) (43)
(44)
(45) (46)
(47)
(48)
o̸=i,j
>0
(49)
′
which yields c(T ) > c(T ). ′ (2) From Corollary B.4, the total cost increments introduced by ψ(TAHC ) and ψ(TAHC ) are ni nj ∆c = + + (n − ni − nj )ni nj + C, 3 3 ni + 1 nj − 1 ′ ∆c = + +(n − ni − nj )(ni + 1)(nj − 1) + C 3 3 | {z }
(50) (51)
0 if nj =3
where C is a constant that remains invariant to the structure change. So ni + n j ′ ∆c − ∆c = (nj − ni − 1) n − ni − nj − +1 2
(52)
When nj = ni + 1, ∆c′ − ∆c = 0. When nj is larger, nj − ni − 1 > 0, so we focus on the second part of the right hand side. We consider the minimum case of n = ni + nj + nj and nj − n i ′ ∆c − ∆c = (nj − ni − 1) +1 >0 (53) 2 which ends the proof. 21
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation Table 9. Statistics of datasets. Dataset NQ PopQA HotpotQA 2Wiki MuSiQue MultiHop-RAG NarrativeQA ∞-LongBook QMSum WCEP
Task type
Index scale
#Queries
#Documents
Average #tokens per document
Single-hop QA Single-hop QA Multi-hop QA Multi-hop QA Multi-hop QA Multi-hop QA Narrative QA Narrative QA Summarization Summarization
Corpus Corpus Corpus Corpus Corpus Corpus Passage Passage Passage Passage
1,000 1,000 1,000 1,000 1,000 1,000 293 100 35 119
9,633 8,676 9,811 6,119 11,656 609 10 19 35 119
141.330 136.536 131.602 110.436 114.516 2346.064 62,824.500 214,711.895 14,375.543 9,567.235
Table 10. Statistics of abstract tree indexes of Ψ-RAG. Dataset NQ PopQA HotpotQA 2Wiki MuSiQue MultiHop-RAG NarrativeQA ∞-LongBook QMSum WCEP
#Trees
#Average leaf nodes
#Average abstract nodes
Average tree depth
1 1 1 1 1 1 10 19 35 119
9,633 8,676 9,811 6,119 11,656 16,349 411 2,446 155 109
3,164 2,810 2,635 1,704 2,938 4,377 85 488 41 33
6 5 6 5 6 6 3.5 4.2 3.3 3.2
Average compression rate 82.35% A / 83.06% ø 83.26% A / 81.87% ø 85.98% A / 85.85% ø 82.14% A / 82.89% ø 84.79% A / 83.09% ø 78.94% A / 78.87% ø 90.71% A / 98.25% ø 84.36% A / 84.31% ø 82.19% A / 82.33% ø 76.32% A / 76.35% ø
Remark. Theorem 4.4 proves that Ψ-RAG incurs a larger cost to assign a major cluster node to a minor cluster. For a minor class in a corpus with cluster c = {u|∃v ∈ c, d(u, v) < d(u, w) ∀w ∈ / c}, it always form a minor subtree in T following the similarity ranking and iterative merging & collapse processes of Ψ-RAG. In conclusion, Ψ-RAG tends to preserve the size of minor classes in a skewed corpus. As the computation of Dasgupta’s cost can be decomposed into that of each subtree, our conclusions can be generalized to trees with δ > 3.
C. Detailed Experimental Setup C.1. Dataset and Index Statistics Statistics of datasets. We provide the statistics of datasets used in our experiments in Table 9. Dataset split. We follow RAPTOR’s document splitting strategy, segmenting documents into chunks of approximate 100 tokens without cutting mid-sentence. Notably, we do not re-split datasets composed of similarly sized paragraphs: NQ, PopQA, HotpotQA, 2Wiki, and MuSiQue. Statistics of abstract trees. We provide the statistics of Ψ-RAG’s abstract tree indexes for each dataset in Table 10. The results show that for corpus-level datasets, the tree depth of Ψ-RAG stabilizes at 5 to 6 layers. This demonstrates Ψ-RAG’s key advantage of generalization ability: it does not require prior assumptions about data, as it naturally uncovers the underlying semantic hierarchy. C.2. Configurations Indexing setup. We set the maximum token length of the summative abstract for each abstract node to 100, and the maximum number of keywords of the keyword abstract to 20. We set the maximum number of children nodes to 40. Abstract nodes with excessive children will be split in half in the rebalancing process. The keyword abstract ø is used for Ψ-RAG in all non-comparative experiments in this paper, unless otherwise stated. 22
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation
Retrieval setup. We mainly follow the multi-step setting of HippoRAG (Jiménez Gutiérrez et al., 2024) for agentic retrieval. For QA tasks, top-10 retrieved passages from both sparse and dense tree retrievers are integrated and reranked to the final top-5 at each retrieval step. We maintain a maximum score list for retrieved document chunks at each step and take top-5 documents from the list for recall@k evaluation. For multi-hop datasets, we limit the maximum number of retrieval attempts (imax + 1) to be equal to the maximum hop count of user questions: 2 for HotpotQA and 2Wiki, 4 for MuSiQue and MultiHop-RAG. For single-hop datasets (NQ and PopQA), though, we allow one extra retrieval attempt for possible query reorganization. For summarization datasets, we perform single retrieval. The k value is determined by the size of documents: top-20 for QMSum and top-15 for WCEP. LLM setup. All experiments are conducted on up to 3 NVIDIA GeForce RTX 4090 GPUs with 48GB VRAM each. We use Ollama5 and Hugging Face as default LLM sources. We follow the majority of default settings of Ollama and Hugging Face models: for example, the context window is fixed to 4096 tokens. We set the decoding temperature to 0 and the penalty for generating repetitive content to 1.3 for every LLM. For the summarization task, the maximum LLM response token length is determined by the size of documents: 200 for QMSum and 150 for WCEP. C.3. Instruction Prompts We show LLM prompts used for generating summative abstract, keyword abstract, and R&A agent below. For single-hop and multi-hop QA, we follow existing works and provide a one-shot in-context example. LLM Prompt for A Summative Abstract ======================== {System Instruction} ======================== As an advanced document summarization assistant, your task is to summarize the given list of documents, including as many key details and relationships as possible. (1) Your answer should always start with “Summary:”. NO UNNECESSARY WORDS: Always directly output the summary instead of useless modifiers like ‘Here is a summary of the given list ...’. (2) Be faithful to the original documents. Unnecessary paraphrasing and adding content not mentioned in the original documents are NOT allowed. (3) Your summary should be NO MORE THAN {summary max length} WORDS. Keep in mind that a longer summary is not always better. An in-context example is provided below. ======================== {In-context example} ======================== User input: Hotel Tallcorn The Hotel Tallcorn is located in Marshalltown, Iowa... The Oberoi Group The Oberoi Group is a hotel company with its head office in Delhi... Hotel Bond Hotel Bond is a historic hotel, built in two stages in 1913 and 1921... Mohan Singh Oberoi Rai Bahadur Mohan Singh Oberoi (15 August 1898 – 3 May 2002)... Ritz-Carlton Jakarta The Ritz-Carlton Jakarta is a hotel and skyscraper in Jakarta... Æ Assistant response: The Hotel Tallcorn in Marshalltown, Iowa, built in 1928, is now an apartment building. It was part of one of the second-largest hotel sales in U.S. history in 1956. Hotel Bond is a historic hotel in Hartford, Connecticut, built in two stages. After facing competition, it went through multiple ownership changes and bankruptcies. It is now a Homewood Suites by Hilton, with its ballroom having reopened in 2001. The Oberoi Group, founded in 1934, is a luxury hotel company based in Delhi. It owns and operates over 30 hotels and two cruise ships. It was founded by Mohan Singh Oberoi, who started India’s second-largest hotel company. The Ritz-Carlton Jakarta is a skyscraper hotel in Indonesia, opened in 2005. It consists of two towers, one for the hotel and one for apartments, and is located near the JW Marriott Hotel.
5
https://ollama.com/
23
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation LLM Prompt for ø Keyword Abstract ======================== {System Instruction} ======================== As an advanced document summarization assistant, your task is to summarize the given list of text paragraphs into multiple key phrases or words. These key phrases include: · Key phrases that overview the types of information covered in the text; · Key phrases that reflect the common themes of these paragraphs; · Key phrases that distinguish the specific content of each paragraph. Requirements: (1) Generate key phrases mentioned above in order. All key phrases should be strictly formatted as ONE line of text, separated by commas, equivalent to the output format of Python code “‘,’.join(list of keywords)”. (2) Different key phrases should be distinct from one another. (3) NO UNNECESSARY WORDS: Always output the direct key phrase list instead of useless modifiers like ‘Here are the key phrases according to the documents: ...’ or ‘Information key phrases: ... Theme key phrases: ...’. (4) The number of key phrases should be NO MORE THAN {max num keywords}. An in-context example is provided below. ======================== {In-context example} ======================== User input: Hotel Tallcorn The Hotel Tallcorn is located in Marshalltown, Iowa... The Oberoi Group The Oberoi Group is a hotel company with its head office in Delhi... Hotel Bond Hotel Bond is a historic hotel, built in two stages in 1913 and 1921... Mohan Singh Oberoi Rai Bahadur Mohan Singh Oberoi (15 August 1898 – 3 May 2002)... Ritz-Carlton Jakarta The Ritz-Carlton Jakarta is a hotel and skyscraper in Jakarta... Æ Assistant response: historic hotels,hotel companies,bankruptcy and renovation,brand operations,Indian hospitality industry,Indonesia skyscraper,hotel locations,hotel building time,hotel architecture,hotel founders,hotel ownership history,Marshalltown Iowa,Hotel Tallcorn,Eppley Hotel Company,Sheraton sale,The Oberoi Group,Mohan Singh Oberoi,Hotel Bond,Hartford Connecticut,Bond Ballroom,RitzCarlton Jakarta
LLM Prompt for R&A Agent in single-hop and multi-hop QA ======================== {System Instruction} ======================== As an advanced reading comprehension and information retrieval agent, your task is to answer the user question by retrieving documents and multi-step reasoning, following the instructions below: (1) Your response starts after “Thought: ”, where you will methodically break down the reasoning process, illustrating how you arrive at conclusions step-by-step. If you believe you have found the answer, conclude with “Answer: <answer>” to present a concise, definitive response. (2) You can request for retrieving supporting documents from a relevant database a maximum of {max retrieval time} times. Some retrieved documents are provided the first time. When the question involves content you do not understand, or current documents do not provide enough information, request retrieval by responding with “Retrieve: <retrieve query>”, where <retrieve query> is a sub-question derived from the user question, which you believe must be resolved to answer the user question. (3) The retrieval results will be provided in the format “Retrieved documents: ...”, and you should continue your reasoning based on the user question, your previous reasoning steps, and all retrieved documents. Obtain your answer with as few retrieval attempts as possible, which means you need to make your <retrieve query> as precise as possible. If newly retrieved documents do not help, try reorganizing your <retrieve query>. If you run out of retrieval attempts and still cannot answer the question, answer with “Not mentioned” only. Do NOT provide additional uncertain information. (4) NO UNNECESSARY WORDS: After your reasoning, you MUST end your response with “Answer: <answer>” or “Retrieve: <retrieve query>” in a new line. <answer> is in most cases a word or a phrase. Avoid ambiguous words like “approximately”. (5) Your “Thought: ” response should be NO MORE THAN {thought max length} WORDS. An in-context example is provided below.
24
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation ======================== {In-context example} ======================== User input: Retrieved documents: Hotel Tallcorn The Hotel Tallcorn is located in Marshalltown, Iowa... Hotel Bond Hotel Bond is a historic hotel, built in two stages in 1913 and 1921... Ritz-Carlton Jakarta The Ritz-Carlton Jakarta is a hotel and skyscraper in Jakarta... User question: The Oberoi family is part of a hotel company that has a head office in what city? Retrieval time remaining: 3 Thought: Æ Assistant response: According to the user question, I need to first figure out the hotel company that the Oberoi family is part of. However, the retrieved documents do not include any details regarding the Oberoi family. Retrieve: Which hotel company is the Oberoi family part of? User input: Retrieved documents: The Oberoi Group The Oberoi Group is a hotel company with its head office in Delhi... Mohan Singh Oberoi Rai Bahadur Mohan Singh Oberoi (15 August 1898 – 3 May 2002)... User question: The Oberoi family is part of a hotel company that has a head office in what city? Retrieval time remaining: 2 Thought: Æ Assistant response: According to “Mohan Singh Oberoi”, Mohan Singh Oberoi is the founder and chairman of Oberoi Hotels & Resorts. From “The Oberoi Group”, Oberoi Hotels & Resorts is a brand and its company, The Oberoi Group, is a hotel company with its head office in Delhi. Answer: Delhi LLM Prompt for R&A Agent in summarization ======================== {System Instruction} ======================== As an advanced reading comprehension and information retrieval agent, your task is to answer summative user questions based on retrieved documents. For each document, an [ID] is prepended to indicate the relative order in the document corpus. These documents provide a condensed version of the original long corpus to help you with summative tasks. Requirements: (1) Organize the documents to form a logically clear summary of the main content or plot of the original long corpus. (2) Your answer should be comprehensive and coherent. Your summative answer should be an independent paragraph, enabling the user to comprehend the content or plot of the original corpus. Do NOT include additional uncertain or made-up information in your answer. (3) Your answer should be NO MORE THAN {response max length} WORDS.
D. Supplemental Experiments D.1. Case Study We present a multi-hop example from MuSiQue in Table 11 to intuitively illustrate how Ψ-RAG performs multi-granular agentic retrieval on the abstract tree. The question, “Who is the wife of the man who produced the documentary of the pop star who influenced Beyoncé?” requires up to 3 hops to answer. The example shows that the keywords retrieved by Ψ-RAG ø at the first layer are relatively coarse, covering broad themes such as music, sports, and movies. With the search going deeper into the tree, the keywords become finer-grained. Consequently, two semantically related retrieved chunks tell that the required “man who produced the documentary” is David Gest. However, due to the structural isolation, we still do not know who is David Gest’s wife, so the R&A agent calls for a second retrieval attempt. As the second question lacks sufficient context, the coarse abstraction in the upper tree layers confuses 25
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation
Table 11. Retrieved documents and agent response of a multi-hop question example. “✓” and “p” indicate supporting chunks and irrelevant chunks, respectively. Relevant tokens matched by BM25 are highlighted. Query
Who is the wife of the man who produced the documentary of the pop star who influenced Beyoncé?
Ψ-RAG ø (1st attempt: original query)
Ψ-RAG ø (2nd attempt: Who is the spouse of David Gest?)
BM25
p 1: “The Mistress” features... a married man, whose wife was played by... p 2: Pizza Man is a 1991 comedy film starring Bill Maher... p 3: Real Life is a 1979 American comedy film starring Albert Brooks... p 4: No Escape is a 1936 British thriller film directed by... ✓ 5: Michael Jackson: The Life of an Icon is a documentary film about pop singer... produced by his friend, David Gest ...
✓ 1: Liza and David... featuring Liza Minnelli and her then-husband, David Gest. ✓ 2: Michael Jackson: The Life of an Icon... produced by his friend, David Gest... p 3: Dave Fennoy Fennoy in Phoenix, Arizona David Henderson Fennoy... p 4: Chileab... was the second son of David, King of Israel... p 5: Random Hearts is a 1999 American romantic drama film... their spouses were having an affair...
1st layer
1: Beyoncé’s music career, NBA players, American football, ... 2: film characters, biographies of actors, musical fantasy comedies, ... 3: DC Comics characters, superhero films, Marvel and DC comics, ...
1: DC Comics characters, superhero films, Marvel and DC comics, ... 2: cricket tournaments, FIFA Confederations Cup, ICC Champions Trophy, ... 3: film characters, biographies of actors, musical fantasy comedies, ...
1: Beyoncé’s music career, R&B and pop genres, female empowerment, ... Last abstract 2: show business families, celebrity siblings, marriages and spouses, ... 3: Beyoncé’s solo career, music awards, Billboard charts, ... layer
1: Swedish personalities, biographical accounts, historical figures, ... 2: Game of Thrones, Justice League, Aquaman, ... 3: European royalty, medieval history, noble families, ...
p 1: Beyoncé’s work has influenced numerous artists... p 2: On March 30, 2015, it was announced that Beyoncé is a co-owner... ✓ 3: Beyoncé names Michael Jackson as her major musical influence... ✓ 4: Michael Jackson: The Life of an Icon is a documentary film... p 5: Beyoncé Giselle Knowles-Carter (/bi:’jOnseI/ bee-YON-say)...
p 1: Dave Fennoy Fennoy in Phoenix, Arizona... p 2: Gal Gadot - Varsano (Hebrew: ... p 3: Gal Gadot - Varsano (Hebrew: ... p 4: Gal Gadot - Varsano (Hebrew: ... p 5: Catharina Wallenstedt was the daughter of Bishop Laurentius...
Leaf layer
✓ 1: Michael Jackson: The Life of an Icon... [score: 0.406] p 2: Nine Days that Changed the World is a 2010 documentary... [score: 0.101] Final retrieved ✓ 3: Beyoncé names Michael Jackson as her major musical influence... [score: chunks 0.071] p 4: Beyoncé’s work has influenced numerous artists... [score: 0.064] p 5: Following the disbandment of Destinyś Child... [score: 0.038]
✓ 1: Liza and David... featuring Liza Minnelli and her then-husband, David Gest. [score: 0.980] ✓ 2: Michael Jackson: The Life of an Icon... [score: 0.201] p 3: Gal Gadot - Varsano (Hebrew: ... [score: 0.029] p 4: Gal Gadot - Varsano (Hebrew: ... [score: 0.026] p 5: Gal Gadot - Varsano (Hebrew: ... [score: 0.020]
According to “Michael Jackson: The Life of an Icon”, David Gest is the friend According to “Michael Jackson: The Life of an Icon”... Lastly, I found that Liza and producer of the documentary film about pop singer Michael Jackson... I need Minnelli was the wife of David Gest at some point in time. Agent <answer> Liza Minnelli ✓ response more information on who David Gest’s wife was at that time or if he had a wife. <retrieve> Who is the spouse of David Gest?
Table 12. An example of minor class retrieval on MultiHop-RAG (S[:50]+E[:5]). The top-1 summative abstract in each layer is listed. Red and purple text relate to the major class “Sports” and the minor class “Entertainment”, respectively. Query
What was the name of the tunnel where the fatal car crash occurred in The Crown? RAPTOR (Sarthi et al., 2024)
Ψ-RAG A
Various sports teams face outcomes: Inter Miami eliminated, Italy and Australia in Davis Cup final, Rangers lead Diamondbacks 3-1, Lions beat Packers, 49ers defeat Cowboys, Vikings lose to Broncos and Bears, amidst other results and controversies including Mattel’s inaccurate Cherokee Barbie.
The Crown’s final season covers Prince Charles and Camilla, Princess Diana, and Dodi Fayed. Diana’s death and her sons’ reactions are depicted. Separate stories include Jada Pinkett Smith and Will Smith’s marriage, Mattel’s Barbie honoring Wilma Mankiller, and Dodi Fayed’s past engagement to Kelly Fisher.
Inter Miami loses 1-0 to FC Cincinnati, eliminating them from MLS playoff contention, despite Lionel Messi’s 35-minute appearance off the bench, as Alvaro Barreal scores late, while other teams like Manchester United struggle in Europe with defensive issues and Chelsea’s Reece James faces an abusive conduct charge.
Season six focuses on Prince Charles and Camilla, Princess Diana and Dodi Fayed. After Diana’s 1997 death, William went missing at Balmoral, returning 14 hours later. Before her death, Diana told William and Harry not to believe papers and planned life changes, but a planned meeting never occurred due to her fatal car crash in Paris.
So, our mistakes can never happen in the Champions League, you get punished for it, so we have to learn from that ” However, Aston Villa legend Gabby Agbonlahor insists Onana needs to take a significant chunk of the blame for United’s collapse on Wednesday night “I feel sorry for Onana,” Agbonlahor told talkSPORT “There’s a clip of him throwing his gloves to the ground after the game He’s angry with himself
In both the series and in real-life, Diana and Dodi - along with their chauffeur, Henri Paul - were killed on 31 August 1997 when their Mercedes-Benz was pursued by paparazzi and crashed in the Pont de l’Alma tunnel in Paris The mother of two was 36 years old The fatal car crash was recreated in the very first scene of season six
The retrieved documents once again do not mention anything about a tunnel or a fatal car crash from “The Crown”. They are still discussing football, specifically Aston Villa and Manchester United. Since I have run out of retrieval attempts and Agent the provided information does not answer the question. response <answer> Not mentioned p
To answer this user question, I need to identify the location and details regarding a specific event depicted in “The Crown”. According to the retrieved document, Diana, Dodi, their chauffeur Henri Paul were involved in a fatal car crash. This incident occurred when they were pursued by paparazzi while driving through Paris. Their Mercedes-Benz crashed inside the Pont de l’Alma tunnel on 31 August 1997. <answer> Pont de l’Alma ✓
1st layer
2nd layer
Leaf layer
26
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation
the retriever, leading it to irrelevant chunks. In contrast, sparse retrieval can provide straightforward facts about David Gest by simply searching for documents with the keyword. As a result, the retrieved chunk leads to the final answer “Liza Minnelli”. This demonstrates the importance of synergy between Ψ-RAG’s hierarchical tree index and the multi-granular hybrid retriever, the key to its effectiveness. D.2. Analyses on Hierarchical Abstract Tree Case study: retrieval on skewed data. To further demonstrate the impact of the uniform effect and distribution adaptability, we conduct a case study based on the visualization study in Section 4.2. We compare the agent response processing a minor-class question on both tree indexes of RAPTOR and Ψ-RAG. From Table 12, the 1st layer abstract nodes of RAPTOR are confused because of the uniform effect, with most of the contents related to the major class “Sports”. This significantly interrupts the retriever which selects a major class abstract node in the 2nd layer. On the contrary, Ψ-RAG’s minor abstract node at the 1st layer clearly points to the relevant topic “The Crown”. This assists the retriever in finding the correct chunk.
Index
Single retrieval time (s)
F1 (%)
Flat GMM HAT GMM + SR + R&A + Q3R HAT + SR + R&A + Q3R
MuSiQue 33.39 0.16 0.15 1.17 1.12
30.50 17.17 18.62 (↑ 1.45) 47.26 48.90 (↑ 1.64)
MultiHop-RAG Flat 62.21 GMM 0.17 HAT 0.16 GMM + SR + R&A + Q3R 0.66 HAT + SR + R&A + Q3R 0.62
42.44 35.81 36.30 (↑ 0.49) 51.32 56.23 (↑ 4.91)
context window size
4,096
8,192
16,384
F1 (%)
Table 13. Comparative results of the indexes. “SR”, “R&A”, and “Q3R” refer to the sparse retriever, the R&A agent, and the reranker, specifically.
No rebalancing: 45.82
Maximum #children per abstract node
Figure 11. Sensitivity of Ψ-RAG to the maximum number of children per abstract node on MuSiQue.
Quantitative study on tree indexes. We conduct a quantitative comparison between the hierarchical abstract tree (HAT) of Ψ-RAG A and (1) a flat index, which performs brute-force sequential search on all document chunks with O(n) time; (2) the GMM-based cluster tree of RAPTOR (Sarthi et al., 2024), both without and with the proposed multi-granular agentic retriever modules. From Table 13, we make the following observations: (1) Flat dense retrieval is much slower than tree retrieval. Although dense retrieval on a flat index serves as a performance upper bound for tree indexes, its linear time complexity incurs at least ∼100× higher runtime than the logarithmic retrieval of tree indexes. (2) HAT outperforms the GMM tree both with or without the agentic retriever modules. The performance increase points to the minor class distribution in the data, which characterizes the contribution of our tree index to alleviating poor distribution adaptability. Effect of rebalancing. We have set the maximum number of children per abstract node for the abstract tree. This keeps the total abstract length within the context window of the abstraction agent. Figure 11 shows the sensitivity of Ψ-RAG to the rebalancing process after tree construction, which lead to three observations. (1) Rebalancing without excessive splitting helps build a better tree structure with higher performance. (2) Splitting an abstract node too many times may lead to relevant node missing during top-k dense vector matching: setting maximum #children to 10 makes the F1 lower than that without rebalancing. (3) When the abstracts become too long (8k–16k tokens), their semantics become more vague which also reduces the accuracy. D.3. Analyses on Multi-granular Agentic Retriever Maximum number of retrieval attempts. We evaluate how the efficiency and performance of the R&A agent vary with the maximum number of iterative retrieval attempts (imax + 1), as shown in Figure 12. The results indicate that on multi-hop datasets, the first extra retriever call yields the greatest performance gain, while subsequent attempts contribute minimal or even negative improvement. Each retrieval attempt introduces a relatively constant time overhead, and longer reasoning
27
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation HotpotQA
2Wiki
MuSiQue
MultiHop-RAG
Maximum retrieval attempts
Maximum retrieval attempts
Maximum retrieval attempts
Maximum retrieval attempts
Maximum retrieval attempts
Maximum retrieval attempts
Maximum retrieval attempts
Maximum retrieval attempts
Figure 12. Retrieval and QA performance in Recall@5 (R@5%) and F1 (%), and average processing time for each query (s) under concurrent execution, w.r.t. the maximum number of retrieval attempts.
False Rate
Not Mentioned Rate Ψ-RAG
False Rate (%)
Not Mentioned Rate (%)
Ψ-RAG
NQ
PopQA
HotpotQA
2Wiki
MuSiQue
MultiHop-RAG NarrativeQA
∞-LongBook
Figure 13. False Rate and Not Mentioned Rate of Ψ-RAG on different datasets.
chains tend to introduce unnecessary noise (Wu et al., 2025). Therefore, it is crucial to strike a balance between the cost of retrieval iterations and the performance gains across different application scenarios. D.4. Failure Analysis We analyze the failure cases of Ψ-RAG by measuring the False Rate (rate of incorrect answers) and Not Mentioned Rate (rate of retrieval failures). An incorrect answer is defined as sharing no overlapping tokens with the ground truth. Figure 13 reveals the following key patterns: (1) Retrieval failures stem from multiple factors. Index scale is a primary factor: the Not Mentioned Rate for ∞LongBook is significantly higher than that for NarrativeQA, which has an index only 30% the size on average. This is because upper-level abstracts in a larger search space are coarser and introduce more noise. Another factor is query complexity: datasets with higher maximum hop counts (MuSiQue with 4 hops) exhibit higher Not Mentioned Rates than those with fewer hops (HotpotQA and 2Wiki with 2 hops). Although we increase the maximum retrieval attempts for complex questions, we observe that if the initial retrieval for a reorganized query fails, subsequent retrieval attempts are also highly likely to fail. This is because the reorganized query often does not shift the high-level semantic focus, causing the tree retriever to revisit the same abstract nodes. Meanwhile, the high-frequency entities in the reorganized query lead the sparse retriever to return many noisy chunks. As shown in Section D.1, BM25 retrieves many irrelevant chunks with “David” that are unrelated to the target “David Gest”. 28
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation
(2) The False Rate consistently exceeds the Not Mentioned Rate. This occurs on most datasets excluding MultiHop-RAG (with unanswerable negative samples). A manual analysis of 50 failure cases from L3-70B on MuSiQue identifies the following causes: (i) LLM misguidance or guesses resulting from incomplete retrieval (29 cases); (ii) logical errors in agentic reasoning (8 cases); (iii) LLM hallucination (6 cases); (iv) granularity mismatch between the answer and the ground truth (7 cases). Therefore, the primary cause of a higher false rate is missing key document chunks in retrieval.
E. Real-World Extensions E.1. Approximate Nearest Neighbor Search for Efficient Indexing We extend Ψ-RAG with two efficient techniques for very large corpora with 10M+ and even 100M+ tokens. They include: • Bucketing: following the inverted-file index in Faiss (Douze et al., 2025), we first partition a large corpus into multiple buckets using a fast recursive spherical k-means. We then build a tree inside each bucket and finally merge them at the highest layer. Assuming b ≪ n buckets of balanced size, bucketing reduces the average indexing time complexity from O(n2 ) to O(n2 /b) and space complexity from O(n2 ) to O(n2 /b2 ). • ANN search with HNSW (Malkov & Yashunin, 2018): we build an HNSW graph over all chunk embeddings and use the top-k graph neighbor pairs of each chunk, which are then ranked to build the tree. This reduces the average time complexity of similarity ranking from O(n2 log n) to O(kn log kn) and space complexity from O(n2 ) to O(kn). We evaluate the efficiency of the two extensions on two large subsets from Wiki18 (∼3B tokens) in FlashRAG (Jin et al., 2025c): Wiki18-6M (6.1M tokens, ∼42k chunks) and Wiki18-50M (50.8M tokens, ∼350k chunks). The time and memory costs are listed in Table 14. It shows that HNSW can generate sorted document pairs for a corpus of 50M tokens with less than 1.5 GB of storage. Combined with bucketing, tree indexing can be completed with MB-level memory usage and at less than 1% of the original time cost. Therefore, LLM-based abstraction becomes the primary efficiency bottleneck for scaling the framework to industrial corpora. Exploring efficient alternatives to LLM-based abstraction will be a key direction for our future work. Table 14. Time and memory comparison of Ψ-RAG’s extensions on large-scale Wiki18 subsets. Embedding dimension is set to 1,024. Experiments are conducted on 8 CPU cores (Wiki18-6M) / 64 CPU cores (Wiki18-50M) and 256GB Memory. Data
Wiki18-6M
Wiki18-50M
Method
Vanilla Ψ-RAG
+ HNSW
+ Bucketing (b = 4) + HNSW
+ HNSW
+ Bucketing (b = 63) + HNSW
Embedding time (s) Similarity ranking time (s) Similarity matrix memory Similarity ranking memory Tree indexing time (s) Abstraction time (s)
1,229 304.84 13.16GB 65.81GB 15,996 ∼205,000
55.99 (5.44×) 10.55MB (1,277×) 656.7MB (102.6×) 13,957 (1.15×) ∼200,000
0.89 (342.5×) 2.45MB (5,483×) 37.89MB (1,778×) 848 (18.86×) ∼89,400
10,208 168.02 88.17MB 1.34GB ∼280,000 ∼1,800,000
7.87 (21.35×) 2.15MB (41.01×) 34.10MB (40.24×) 2,261 (∼124×) ∼1,400,000
E.2. Query Hop Discriminator Our evaluation utilizes the maximum hop count of each dataset for the maximum number of iterative retrieval time imax . This limits the applicability in real-world datasets with diverse user queries. For practical settings without prior maximum hop count, we implement a lightweight Table 15. Multi-hop QA results of ΨRAG with the query hop discriminator. query hop discriminator Q : q 7→ imax using a 2-layer MLP trained on questions with 1 to 4 hops. It predicts the hops of each user query before retrieval to Dataset R@5 (%) F1 (%) automatically decide the maximum retrieval time for the R&A agent with very 6 small latency. Table 15 shows the QA results with Q on some multi-hop datasets . HotpotQA 95.05 74.27 Results indicate that the query hop discriminator preserves strong effectiveness of MuSiQue 72.68 46.63 Ψ-RAG without the prior maximum hop count. 6
We train Q with user questions from datasets other than the indexed corpus: NQ, 2Wiki, MultiHop-RAG without negative samples, and MuSiQue for indexing HotpotQA (HotpotQA for indexing MuSiQue). The lengths of decomposed sub-query lists or the number of evidence passages serve as labels.
29
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation
F. Related Work Retrieval-Augmented Generation (Lewis et al., 2020; Fan et al., 2024). Based on the type of index and retriever, RAG frameworks can be categorized as: (1) Sparse retrieval: methods such as TF-IDF (Sparck Jones, 1972) and BM25 (Robertson et al., 2009) retrieve documents where keywords from the user question appear more often in the corpus. They are fast and suitable for token-level detailed search but less capable of capturing deep semantic meanings. (2) Dense vector retrieval (Karpukhin et al., 2020): this approach utilizes powerful language embedding models (Khattab & Zaharia, 2020; Izacard et al., 2022; Lee et al., 2025; Zhang et al., 2025b) to map queries and documents into a continuous vector space (Fan et al., 2024). It retrieves the top-k documents most relevant to the user question using vector metrics like cosine similarity. Sometimes, embedding-based rerankers (Li et al., 2023; Zhang et al., 2025b) are also utilized to rerank retrieved documents based on user preference, further improving retrieval quality. Dense vector-based RAG excels at capturing deep semantics and key features of entities, making it suitable for more complex QA scenarios. Nonetheless, dense retrieval could prefer documents highly relevant in features but totally unrelated to target entities. (3) Hybrid retrieval: some approaches integrate both sparse and dense retrieval to combine their strengths, leading to a number of powerful RAG frameworks (Gao et al., 2021; Lee et al., 2023; Arivazhagan et al., 2023; Zhang et al., 2024b). Agentic RAG. The rapid advancement in the intelligence of LLMs has heightened focus on their reasoning capabilities and demands on RAG frameworks. Recent efforts (Yao et al., 2022; Trivedi et al., 2023; Asai et al., 2024; Li et al., 2025c) incorporate specifically designed LLM agents to integrate retrieval into LLM reasoning process. Specifically, the agent recursively decomposes a question into multiple sub-questions and invokes the retriever at each step (Li et al., 2025d). This enables the LLM to autonomously and flexibly handle multi-hop questions. However, most of them are built upon flattened linear or inverted indexes for token-level information. Graph-RAG. As the most popular form of structured RAG, knowledge graph indexes (Edge et al., 2024; Peng et al., 2025; Xiao et al., 2025) can capture semantic relationships between document chunks or entities. They often build a unified index for an entire corpus using named entity recognition and extraction methods like the Open Information Extraction (OpenIE) (Banko et al., 2007). Cross-document multi-hop associations are then captured by walking from node to node (Jiménez Gutiérrez et al., 2024; 2025), extracting shortest paths (Huang et al., 2025; Chen et al., 2026), or extracting subgraphs (Guo et al., 2025; Li et al., 2025a). However, graph indexes are less effective at capturing hierarchy. Some Graph-RAG methods have to resort to less efficient compensatory strategies to handle summative tasks, including but not limited to hierarchical graphs (Malkov & Yashunin, 2018; Huang et al., 2025), community summaries (Edge et al., 2024; Wang et al., 2025), LLM-based hierarchical filtering (Guo et al., 2025), or graph neural network-based message aggregation (Zhang et al., 2025a). Coupled with the significant overhead of OpenIE, efficient index construction remains a key challenge for Graph-RAG. Tree-RAG. Tree indexes are introduced to explicitly model the hierarchical relationships of documents while achieving fast retrieval with logarithmic complexity (Liu, 2022). Traditional tree indexes for nearest neighbor search include top-down splitting (Bentley, 1975; Omohundro, 1989) and bottom-up hierarchical clustering (Florek et al., 1951; Sokal & Michener, 1958; Jardine & van Rijsbergen, 1971). However, traditional algorithms offer limited generalization. Most existing dense vector-based Tree-RAG methods (Liu et al., 2021; Liu, 2022; Jin et al., 2025b; Zhao et al., 2025; Fatehkia et al., 2024; Tao et al., 2025) rely on explicit document structure (session titles, tables of contents, etc.) or contextual relationships between adjacent text chunks. As a result, they are not directly applicable to documents lacking explicit structure or to cross-document retrieval. RAPTOR (Sarthi et al., 2024) is the first passage-level Tree-RAG framework designed for unstructured long documents. It recursively clusters document chunks via Gaussian Mixture Model (GMM) and generates a summary for each cluster. MemTree (Rezazadeh et al., 2025) further adapts Tree-RAG to the long-term LLM memory scenario, but both of them are limited to the passage-level indexes and the single-document retrieval setting. To our knowledge, the only corpus-level Tree-RAG is LATTICE (Gupta et al., 2025), which performs beam search retrieval using an LLM-evaluated path relevance score. However, there are no discussions towards the limitations on multi-hop QA, and its tree building process is not open-sourced at the time of writing.
G. Discussion and Future Work Updating the index. Real-time document insertion and index updates are common requirements for RAG applications, yet they pose challenges for traditional Tree-RAG methods, as adding new documents necessitates re-clustering the entire corpus. Our abstract tree index is constructed based on local pairwise similarities, making it feasible to be updated with new documents. 30
Hierarchical Abstract Tree for Cross-Document Retrieval-Augmented Generation
We propose an easy-to-implement approach for the insertion of ∆n new document chunks. A single new node is collapsed to the leaf layer by searching for its most similar leaf in the tree via dense vector matching. Then, for keyword abstracts, Ψ-RAG traverses upstream to find the parent abstract nodes of the new node (or maintains an O(n) parent index table for faster lookups) and appends new keywords to each parent. For summative abstracts, the abstraction LLM is invoked to regenerate the abstract for each parent node, similar to existing abstract updating strategies (Rezazadeh et al., 2025). This costs up to O(n∆n) time. For batch insertion of ∆n chunks, a tree can first be built with only new chunks and then integrated into the main branch via abstract node collapse. If it is collapsed into the lth layer with nl nodes, then this updating costs O((∆n)2 nl log ∆n) which is much smaller than that of re-indexing. We note that repeatedly inserting isolated nodes under the same parent may amplify the semantic or granularity biases between them. Considering the semantic coherence in the real-world textual data, we thus recommend inserting new contents as a subtree rather than as individual nodes when they differ substantially from the existing tree. Future work. An efficiency challenge for Ψ-RAG and other passage-level Tree-RAG lies in the abstraction LLM calls during indexing. Developing a more efficient abstraction scheme is a key direction for scaling Tree-RAG to industrial applications. Moreover, as analyzed in Section D.4, sparse retrievers like BM25 resort to the traditional named entity recognition technique, neglecting the high co-occurrence frequency of named entities. Another future work involves adapting agents to more specialized and diverse user needs with various post-training techniques, such as reinforcement learning and rejection sampling-based supervised fine-tuning.
31