研究问题与动机
- Tree-RAG 用层级树组织实体与上下级关系,理论上比纯文本索引更容易保留结构上下文。
- 但它的瓶颈也很明确:
- query 中出现实体后,系统必须在一片 forest 里找到这个实体在不同树中的所有位置;
- 再回溯父节点、下探子节点,拼成增强上下文。
- 当树数量和深度上去后,实体定位本身就会变成主要开销,而不是 LLM 生成。
论文的判断很直接:
- Tree-RAG 的问题不一定是“模型不够强”;
- 很可能是前面的知识结构查找太慢。
方法与机制
1. 先把原始数据处理成 entity forest
- 对已有层级数据,直接抽取 parent-child 对。
- 对原始文本,先做清洗,再做:
- entity recognition:论文沿用 T-RAG,使用 spaCy 抽 query/entity;
- relationship extraction:结合 GPT-4 和开源依存句法工具识别“belongs to / contains / depends on”等层级关系;
- relationship filtering:删掉不适合树结构的关系。
- 过滤规则包括:
- 删除传递性冗余边;
- 删除环;
- 删除 self-loop;
- 删除重复边。
这一步的目标不是构图,而是保证最后得到的是可遍历、可索引的 entity tree / forest。
2. Cuckoo Filter 里存的不是实体文本本身,而是实体出现位置
- 每个实体先计算 fingerprint。
- 论文默认用较短的 fingerprint(文中举例为
12-bit)来压缩存储。 - 每个 bucket entry 里不只存 fingerprint,还存三类信息:
- fingerprint 本身;
- temperature:该实体被访问的频率;
- block linked list head pointer:指向这个实体在 forest 中所有出现位置的地址块链表。
这里的 block linked list 很关键:
- Tree-RAG 真正需要的不是“实体是否存在”;
- 而是“它在不同树里分别出现在哪些节点”。
- 论文因此没有把 Filter 只当 membership test,而是把它变成了位置索引入口。
3. 插入与扩容:沿用 Cuckoo Hashing 的两候选桶机制
- 对实体
x,候选桶位置为:i1 = h(x)i2 = i1 xor h(f(x))
- 如果
i1或i2有空位,就直接插入。 - 如果都满了,就执行 cuckoo eviction:
- 随机踢出一个已有 fingerprint;
- 把它搬去替代位置;
- 重复直到找到空位或达到最大 kick 次数。
因此它相比 Bloom Filter 有两个明显系统优势:
- 支持删除和动态更新;
- 在相似存储预算下,假阳性率更低。
4. 查找与上下文生成:命中实体后顺着地址块回收树上下文
- Lookup 时同样只检查
i1和i2两个桶。 - 如果 fingerprint 命中:
- temperature 加一;
- 返回 block linked list 头指针。
- 然后系统沿着地址链表,拿到这个实体在不同树中的所有位置,再抽:
- 向上的多级父节点;
- 向下的多级子节点。
- 论文把这些
(H_up, H_down)层级关系组织成上下文模板,再和原 query 拼成增强 prompt。
换句话说,CFT-RAG 的核心不是“过滤掉无关树”,而是:
- 先用 Cuckoo Filter 极快地命中实体位置;
- 再从命中的位置局部展开,拿结构上下文。
5. 两个专门为 Tree-RAG 设计的增强
temperature sorting
- bucket 内的实体会根据访问频率重新排序;
- 热实体被放到更靠前的位置;
- 因为 bucket 查找是线性的,所以后续重复查询会更快。
block linked list
- 同一实体在多棵树中的多个地址被集中挂在一个块链表里;
- 减少普通链表节点碎片化;
- 兼顾随机访问与空间利用率。
所以这篇论文真正的创新点不是单纯“使用 Cuckoo Filter”,而是把它改造成适合 Tree-RAG 的位置索引器 + 热度缓存器。
证据与结果
1. 数据集与实现
- 论文用了两类数据:
- UNHCR organizational chart 英文数据集
- 来自 T-RAG,已预分好实体
- 中文 hospital histories 真实数据集
- 需要额外做实体与关系抽取
- UNHCR organizational chart 英文数据集
- 实现上:
- RAG 框架主体用 Python
- Bloom / Cuckoo Filter 关键数据结构用 C++
- 硬件为
NVIDIA H100 + 22 CPU cores + 220 GiB memory - 每个算法重复
100次取平均
- 回答准确率用 LangSmith 评估,但把默认 OpenAI scorer 换成了 Doubao。
2. 对比基线
- Naive T-RAG
- 不做过滤优化,直接 BFS 查树
- BF T-RAG
- 在每个树节点挂 Bloom Filter,用于剪枝
- BF2 T-RAG
- 在 BF T-RAG 基础上,跳过接近叶节点处的部分 Bloom 检查
- CF T-RAG
- 也就是本文方法
3. 主结果一:树越多,CFT-RAG 的优势越明显
在不同 tree number 下,CF T-RAG 的检索时间分别是:
50棵树:- Naive
0.320925s - BF
0.250479s - BF2
0.188924s - CF
0.011772s
- Naive
300棵树:- Naive
1.767487s - BF
1.360986s - BF2
1.097023s - CF
0.017502s
- Naive
600棵树:- Naive
3.301436s - BF
2.638721s - BF2
2.171958s - CF
0.023776s
- Naive
最关键的是 600 棵树时:
- 相比 Naive T-RAG,速度大约提升
138x - 而准确率仍保持在同一量级:
- Naive
66.45% - CF
66.50%
- Naive
这基本说明它确实把 Tree-RAG 的主要瓶颈从“查树”里移走了。
4. 主结果二:query 里实体越多,CFT-RAG 越显得稳定
在 600 棵树时,若 query 中包含不同数量的实体:
- 5 个实体
- Naive
12.615021s - BF
6.568509s - BF2
4.704859s - CF
0.074715s
- Naive
- 10 个实体
- Naive
13.673550s - BF
8.700830s - BF2
5.256318s - CF
0.090924s
- Naive
- 20 个实体
- Naive
38.479844s - BF
11.146254s - BF2
10.461809s - CF
0.087526s
- Naive
这里最有意思的现象是:
- baseline 会随着 query 中实体数增加明显变慢;
- CFT-RAG 的时间几乎保持平稳。
这说明它的收益不只是“常数更小”,而是把实体数增长带来的树遍历膨胀抑制住了。
5. 误差率和空间利用
- 在 hospital dataset 上:
- Cuckoo Filter 使用
1024个 buckets - 每个 bucket 最多容纳
4个 fingerprints / head pointers - 总实体数
3,148 - load factor 为
0.7686
- Cuckoo Filter 使用
- 论文报告:
- 查找错误几乎为
0 - 在该设置下,lookup error 约相当于
1024个桶里只有0-1个实体因 hash collision 出错
- 查找错误几乎为
这说明它不是只靠暴力扩内存换时间,而是在较高负载下仍然保持很低错误率。
6. 消融:temperature sorting 确实带来后续查询加速
- 论文用 Figure 5 比较了有无 sorting design 的多轮查询时间。
- 结论是:
- 第一轮之后,检索时间明显继续下降;
- 原因是每轮查询后都会更新 entity temperature,并把“热实体”排到 bucket 前部。
所以论文的加速不只是静态哈希结构本身,还来自一种轻量的query locality 利用机制。
局限与开放问题
- 论文几乎所有收益都体现在检索时间,而不是答案质量提升。
- 实验里的 answer accuracy 大多在
66%左右,各方法差距很小,因此这篇论文不能说明它改善了 reasoning。 - 方法高度依赖 entity forest / Tree-RAG 设定;如果知识库不是层级树,优势不一定成立。
- 评测规模和任务形态都偏系统实验,不像通用 QA benchmark 那样全面。
关联与拓展
- GraphRAG MOC - GraphRAG研究全景图
- LinearRAG - 关注索引结构与检索效率
- LightRAG - 轻量检索路线
- GraphRAG-Microsoft - 偏全局总结与组织
- GNN-RAG - 从学习式图检索角度提升效率与效果