Ψ-RAG: Hierarchical Abstract Tree for Cross-Document RAG — L2 #

1. TL;DR #

Ψ-RAG replaces RAPTOR's $k$-means/GMM cluster tree with an AHC-style "merging and collapse" abstract tree (no distribution prior), adds an R&A agent with query reorganization for multi-hop causality, and fuses a BM25 sparse index to fix coarse abstraction. First Tree-RAG to beat SOTA Graph-RAG: +25.9% F1 over RAPTOR, +7.4% over HippoRAG 2, training-free.

2. Q1 / Q2 / Q3 #

Q1 — 痛点 (problem) #

Tree-RAG (RAPTOR) works well only at passage scale on a single document. When scaled to a corpus-level index (millions of tokens) for cross-document multi-hop QA, three failures emerge, each mapped to a distinct root cause:

1. Poor distribution adaptability — $k$-means-type clustering assumes spherical clusters and exhibits the uniform effect: it drives all clusters toward size $n/k$, so minor-theme chunks get absorbed into major clusters and the retriever overlooks them on skewed corpora.
2. Structural isolation — tree leaves have no lateral edges (unlike Graph-RAG's pairwise hops), so the index cannot express the implicit causal chain a multi-hop query traverses (e.g. "wife of the man who produced the documentary of the pop star who influenced Beyoncé").
3. Coarse abstraction — top-level abstracts act as a "mosaic" that buries token-level entities, so dense matching cannot align a specific query entity with a high-level abstract node.

Empirically RAPTOR+Q3R underperforms plain DPR (no reranker) on 5/6 datasets, dropping >30% F1 on PopQA (Table 2).

Q2 — 方法 (method) #

Ψ-RAG is a two-phase, training-free framework with each component targeting one limitation:

• Abstract Tree Indexing (fixes #1): build the tree by an iterative "similarity ranking → merging & collapse → abstraction" process inspired by agglomerative hierarchical clustering (AHC), with no $k$/distribution assumption. Rank chunk pairs by cosine similarity, then process the top $n-1$ pairs applying three operations (merging, leaf collapse, abstract-node collapse). Each abstract node gets a summative or keyword abstract from an abstraction LLM.
• Multi-granular Agentic Retrieval (fixes #2, #3): an R&A agent does top-down dense tree retrieval, decides vs , reorganizes the sub-query with appositive context, and fuses a BM25 sparse index (via reranker or RRF) to inject fine-grained facts.

核心技术壁垒: the load-bearing insight is that the deterministic collapse operator $\psi(\cdot)$ (binary AHC tree → equi-depth multifurcating tree) provably raises Dasgupta's cost more for uniform / major-into-minor leaf assignments (Theorems 3.3, 3.4). This is what mathematically severs Ψ-RAG from the $k$-means uniform effect while staying objective-free — the single hardest part to replicate because it is a property of the collapse mechanics, not a tuned loss (see §7).

Q3 — 结果 (results) #

• Token-level QA (Table 2): avg F1 62.77 (summative) vs RAPTOR 36.69 (+25.9 abs) and HippoRAG 2 55.41 (+7.4). Up to +54.78% F1 on 2Wiki.
• Retrieval (Table 3): avg Recall@5 78.98 vs RAPTOR 50.27 (+23.7).
• Narrative/summarization (Table 4): beats RAPTOR by 9.7% avg F1 on narrative, GoR by 3.2% avg ROUGE-L.
• Tree build 6.5× faster than RAPTOR (tree-indexing only); ~10× faster than OpenIE Graph-RAG corpus build.

3. 架构 / 方法图 #



Paper's Figure 2 (caption: "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 ... 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.").

The left half is the offline index build (similarity ranking → merging & collapse → abstraction into summative/keyword abstracts); the right half is the online loop where the R&A agent queries both the tree and the BM25 sparse index. The reader should notice the two granularity sources feeding one agent — this dual-granularity fusion is what lets a single framework span token-level QA to document-level summarization.



Paper's Figure 3 (caption: "Illustration of abstract tree building steps: merging, leaf node collapse, and abstract node collapse. Yellow arrows indicate the current chunk pair to be processed.").

This is the mechanism at the heart of the index. For the current top-similarity pair $(u,v)$: if both are isolated → merging (new parent over both); if one has a parent → leaf collapse (attach the orphan under the existing parent); if both have differing roots → abstract-node collapse (attach the shallower root onto the deeper node's path to equalize depth). Notice depths are always re-equalized, which is exactly what produces the equi-depth multifurcating tree the theory analyzes.

The retrieval side is a state machine rather than a static figure; redrawn here for clarity since the paper folds it into Fig 2:

stateDiagram-v2 [*] --> Retrieve0: user query q Retrieve0 --> Agent: D*_0 = r(q,T) ∪ r(q,I) Agent --> Decide Decide --> Answer: Decide --> Reorg: , propose q' Reorg --> RetrieveI: D*_i = r(q'_i,T) ∪ r(q'_i,I) RetrieveI --> Agent Decide --> Answer: i = i_max (forced) Answer --> [*]

Each retrieval step performs top-down dense matching from the root, and the reorganized query $q'$ enriches both the sparse retriever (thematic keywords) and the tree retriever (high-level context for locating abstract nodes).

4. 作者证明 #

Ψ-RAG's central claim is formally proven: its index does not suffer the $k$-means uniform effect and additionally preserves skewed (minor-class) distributions.

Notation table #

Symbol	Meaning
$\mathcal{T}=(\mathcal{V},\mathcal{E})$	tree index; $\ell(u)$ = leaves under $u$
$\delta(u)$	depth of node $u$; $p^k(u)$ = ancestor at distance $k$
$\text{LCA}(u,v)$	deepest common ancestor of $u,v$
$c(\mathcal{T})$	Dasgupta's cost of tree $\mathcal{T}$
$\mu_i, n_i$	centroid and size of cluster $c_i$
$\psi(\cdot)$	collapse map: binary AHC tree → equi-depth multifurcating tree
$\Delta c$	increment in Dasgupta's cost introduced by $\psi(\cdot)$

Equations and physical meaning #

The $k$-means objective is the within-cluster sum of squares:

$$\mathcal{L} = \sum_{i=1}^{k} \sum_{x_i \in c_i} \Vert x_i - \mu_i \Vert^2$$

Theorem 3.1 rewrites it (proved by induction on $k$, Appendix C.1) as $\mathcal{L} = -A\sum_{1\le iuniform effect.

Ψ-RAG has no explicit objective (it is greedy AHC), so the authors adopt Dasgupta's cost:

$$c(\mathcal{T})=\sum_{1\le i < j \le n} d(u_i,u_j)\, \vert \ell(\text{LCA}(u_i,u_j)) \vert$$

Physical meaning: penalizes placing similar leaves (small $d$) under a large, shallow LCA — lower cost ⇒ similar points share deep, small subtrees.

Theorems / proof sketch #

• Theorem 3.3 (Non-uniformity preference): for a 3-layer equi-depth uniform tree ($n_i=n/k$, $k\ge3$, $n\ge3k$), moving one leaf between subtrees gives $c(\mathcal{T}')prefers non-uniform trees — no uniform effect.
• Theorem 3.4 (Distribution adaptability): for subtrees of arbitrary size with a minor subtree $\mathcal{T}_i$ ($2\le n_ipenalized — minor sizes are preserved.

Proof skeleton (Appendix C.2/C.3): (i) Lemma C.1 modularity — a subtree swap changes cost only locally, so global cost decomposes; (ii) Lemma C.2 — a surjection $\psi$ maps every binary AHC tree to Ψ-RAG's equi-depth tree by bottom-up collapsing; (iii) Lemma C.3 gives closed-form collapse increments (leaf collapse $\Delta c=\binom{n_a}{2}$; abstract collapse $\Delta c=n'\sum_{i3$ by modularity).

6-minimum checks:

1. Assumptions: Thm 3.1 needs the independence of $n_i n_j$ and $\Vert\mu_i-\mu_j\Vert^2$ — breaks when large clusters are also far apart (correlated), then uniform sizing is not forced. Thms 3.3/3.4 assume unit distances $d=1$ and $k\ge3$.
2. Dimensional/units: Dasgupta's cost is (distance × leaf-count) summed over pairs; both sides of the increment equalities are pure counts — consistent.
3. Limiting behavior: at $k=2$ Thm 3.3's $k\ge3$ premise fails (moving a leaf then does not strictly reduce cost); matches the "$k\ge3$" guard.
4. Boundary/equality: Thm 3.4 equality iff $n_j=n_i+1$ (moving from a subtree only one larger is cost-neutral) — sensible edge case.
5. Constants recovered: proof recovers $A=1/n$, $B=\mathcal{P}_k/(2n)$ explicitly, matching Eq (5).
6. Does the conclusion require the mechanism? Yes — the result hinges on the collapse increments $\Delta c$, i.e. Ψ-RAG's own operator, not a generic AHC property (traditional AHC assigns equal cost to both structures; only $\psi$ breaks the tie).

5. 实验与数据 #



Paper's Table 2 (caption: "Single- and multi-hop QA results in EM (%) and F1 (%).").

The load-bearing headline table. Ψ-RAG (summative) reaches avg F1 62.77 vs RAPTOR 36.69 and HippoRAG 2 55.41. Notice the reversals: RAPTOR+Q3R collapses on PopQA (F1 25.76) and 2Wiki (22.16) — the coarse-abstraction failure at corpus scale — while on MultiHop-RAG (negative samples) HippoRAG 2 crashes to 19.36 but Ψ-RAG holds at 56.23. Ψ-RAG is not uniformly best: DPR+IRCoT+Q3R still wins PopQA and HippoRAG 2 wins HotpotQA F1 (75.40).



Paper's Table 3 (caption: "Retrieval results for single- and multi-hop QA in Recall@2 and Recall@5.").

Retrieval gains track QA gains: Ψ-RAG leads avg R@5 (78.98) and dominates the hard multi-hop sets (2Wiki R@5 96.13, HotpotQA 96.00). The single-hop R@2 columns are where traditional/hybrid baselines still edge it, confirming that the tree's advantage is multi-hop and skewed retrieval, not simple factoid lookup.



Paper's Figure 6 (caption: "Ablation studies in F1 (%).").

Component attribution: the R&A agent adds ~20% avg on multi-hop; sparse retrieval is the biggest single lever on factual-heavy sets (+21.82% PopQA, +41.21% 2Wiki), validating that it is the coarse-abstraction fix. The reranker (Q3R) integrates more effectively than RRF but is not a core contributor — an honest negative result.



Paper's Table 8 (caption: "Time costs of different structured RAG.").

Efficiency nuance the abstract glosses: Ψ-RAG tree indexing is 258s on MuSiQue (6.5× faster than RAPTOR's 1,684s), but total indexing (12,157s) is higher than RAPTOR (9,254s) because Ψ-RAG has more abstract nodes to summarize — LLM abstraction, not tree building, is the real bottleneck. Retrieval stays $O(\log n)$ and fast (0.98s), far below HippoRAG 2's graph retrieval (10.44s).

6. 论证链 #

#	Step	Paper-internal support
1	$k$-means/GMM Tree-RAG suffers the uniform effect, absorbing minor-theme chunks	Thm 3.1 (Eq 5) + Fig 4 toy centroid drift
2	Ψ-RAG's collapse operator provably avoids uniform sizing and preserves minor clusters	Thms 3.3, 3.4 (Appendix C) via Dasgupta's cost
3	This theory manifests as cleaner tree structure on skewed data	Fig 5 circular-tree visualization; Table 13 HAT > GMM
4	Cleaner index + agentic multi-hop + sparse fusion → higher retrieval and QA	Tables 2, 3; ablation Fig 6; case studies Tables 11, 12
5	Net effect: first Tree-RAG to surpass SOTA Graph-RAG, training-free, efficient index	Table 2 (+7.4% over HippoRAG 2); Table 8

7. 实现 cross-reference #

Code is open-sourced by the authors at https://github.com/Newiz430/Psi-RAG (per §0 footnote); not vendored in this workspace, so no local file:line citations — [实现未公开 locally].

核心技术壁垒 (detail): the hard-to-replicate piece is Algorithm 1's three-branch collapse and the rebalancing that keeps the tree equi-depth. The theory's guarantee only holds for the deterministic $\psi$ collapse — a naive AHC dendrogram cut would not reproduce the non-uniformity preference (Thm 3.3 shows plain AHC assigns equal cost to both structures; only the collapse breaks the tie). Faithfully implementing the depth-equalizing collapse (c(p^{δ(v)+1}(u)) ← c(p^{δ(v)+1}(u)) ∪ {root(v)}, Eq 2) is therefore the crux, not the clustering.

关键实现细节 (easy-to-miss tricks):

1. Rebalancing sweet spot (Appendix D.2, Fig 11): max children per abstract node = 40. Too few (10) hurts F1 below no-rebalancing because relevant nodes get missed in top-$k$ matching; too-long abstracts (8k–16k tokens) become semantically vague. The default abstract length is capped at 100 tokens (summative) / 20 keywords.
2. Query reorganization + forced-answer guard (Algorithm 3, Table 5): the agent inserts appositive context ("David Gest" → "the American film producer David Gest"), which is what lets the sparse retriever and the tree retriever both re-anchor; disabling it costs up to −2.01% F1 (MuSiQue). At $i=i_{\max}$ the instruction is rewritten to force , and exhaustion returns "Not mentioned" rather than hallucinating.