GGraphRAG 文献图谱自动同步
LIT-C2F7C79A · 年份待核验

CFT-RAG: An Entity Tree Based Retrieval Augmented Generation Algorithm With Cuckoo Filter

CFT-RAG 关注的不是“怎样让 Tree-RAG 更会推理”,而是“**怎样让 Tree-RAG 在大规模实体树上查得足够快**”。它把改进版 Cuckoo Filter 直接嵌入实体树检索流程,用 `fingerprint + block linked list + temperature sorting` 把实体定位从树遍历变成近似 `O(1)` 的桶查找。

摘要级记录优先级 P1作者待核验发表信息待核验
内容状态:摘要级记录。结构化摘录继承当前知识库的来源等级;具体 claim 应回到一手论文核验。

研究问题与动机

  • 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 真实数据集
      • 需要额外做实体与关系抽取
  • 实现上:
    • 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
  • 300 棵树:
    • Naive 1.767487s
    • BF 1.360986s
    • BF2 1.097023s
    • CF 0.017502s
  • 600 棵树:
    • Naive 3.301436s
    • BF 2.638721s
    • BF2 2.171958s
    • CF 0.023776s

最关键的是 600 棵树时:

  • 相比 Naive T-RAG,速度大约提升 138x
  • 而准确率仍保持在同一量级:
    • Naive 66.45%
    • CF 66.50%

这基本说明它确实把 Tree-RAG 的主要瓶颈从“查树”里移走了。

4. 主结果二:query 里实体越多,CFT-RAG 越显得稳定

在 600 棵树时,若 query 中包含不同数量的实体:

  • 5 个实体
    • Naive 12.615021s
    • BF 6.568509s
    • BF2 4.704859s
    • CF 0.074715s
  • 10 个实体
    • Naive 13.673550s
    • BF 8.700830s
    • BF2 5.256318s
    • CF 0.090924s
  • 20 个实体
    • Naive 38.479844s
    • BF 11.146254s
    • BF2 10.461809s
    • CF 0.087526s

这里最有意思的现象是:

  • baseline 会随着 query 中实体数增加明显变慢;
  • CFT-RAG 的时间几乎保持平稳。

这说明它的收益不只是“常数更小”,而是把实体数增长带来的树遍历膨胀抑制住了。

5. 误差率和空间利用

  • 在 hospital dataset 上:
    • Cuckoo Filter 使用 1024 个 buckets
    • 每个 bucket 最多容纳 4 个 fingerprints / head pointers
    • 总实体数 3,148
    • load factor 为 0.7686
  • 论文报告:
    • 查找错误几乎为 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 那样全面。

关联与拓展

研究问题入口

Q1 领域边界与适用性, Q2 图构建与表示, Q3 证据检索与集合形成, Q4 查询规划与执行, Q8 效率与部署

展开原始论文笔记全文

基本信息

  • 作者: Zihang Li, Yangdong Ruan, Wenjun Liu, Zhengyang Wang, Tong Yang
  • 机构: Peking University, Beihang University 等
  • 发表: arXiv preprint, 2025(当前版本更新于 2026-02-02)
  • arXiv: 2501.15098

一句话理解

CFT-RAG 关注的不是“怎样让 Tree-RAG 更会推理”,而是“怎样让 Tree-RAG 在大规模实体树上查得足够快”。它把改进版 Cuckoo Filter 直接嵌入实体树检索流程,用 fingerprint + block linked list + temperature sorting 把实体定位从树遍历变成近似 O(1) 的桶查找。

核心问题

  • 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 真实数据集
      • 需要额外做实体与关系抽取
  • 实现上:
    • 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
  • 300 棵树:
    • Naive 1.767487s
    • BF 1.360986s
    • BF2 1.097023s
    • CF 0.017502s
  • 600 棵树:
    • Naive 3.301436s
    • BF 2.638721s
    • BF2 2.171958s
    • CF 0.023776s

最关键的是 600 棵树时:

  • 相比 Naive T-RAG,速度大约提升 138x
  • 而准确率仍保持在同一量级:
    • Naive 66.45%
    • CF 66.50%

这基本说明它确实把 Tree-RAG 的主要瓶颈从“查树”里移走了。

4. 主结果二:query 里实体越多,CFT-RAG 越显得稳定

在 600 棵树时,若 query 中包含不同数量的实体:

  • 5 个实体
    • Naive 12.615021s
    • BF 6.568509s
    • BF2 4.704859s
    • CF 0.074715s
  • 10 个实体
    • Naive 13.673550s
    • BF 8.700830s
    • BF2 5.256318s
    • CF 0.090924s
  • 20 个实体
    • Naive 38.479844s
    • BF 11.146254s
    • BF2 10.461809s
    • CF 0.087526s

这里最有意思的现象是:

  • baseline 会随着 query 中实体数增加明显变慢;
  • CFT-RAG 的时间几乎保持平稳。

这说明它的收益不只是“常数更小”,而是把实体数增长带来的树遍历膨胀抑制住了。

5. 误差率和空间利用

  • 在 hospital dataset 上:
    • Cuckoo Filter 使用 1024 个 buckets
    • 每个 bucket 最多容纳 4 个 fingerprints / head pointers
    • 总实体数 3,148
    • load factor 为 0.7686
  • 论文报告:
    • 查找错误几乎为 0
    • 在该设置下,lookup error 约相当于 1024 个桶里只有 0-1 个实体因 hash collision 出错

这说明它不是只靠暴力扩内存换时间,而是在较高负载下仍然保持很低错误率。

6. 消融:temperature sorting 确实带来后续查询加速

  • 论文用 Figure 5 比较了有无 sorting design 的多轮查询时间。
  • 结论是:
    • 第一轮之后,检索时间明显继续下降;
    • 原因是每轮查询后都会更新 entity temperature,并把“热实体”排到 bucket 前部。

所以论文的加速不只是静态哈希结构本身,还来自一种轻量的query locality 利用机制。

我的理解

  • 这篇论文更像一篇 RAG 系统/数据结构优化 论文,而不是语义检索或 reasoning 论文。
  • 它有价值的地方在于提醒我们:
    • RAG/GraphRAG 的瓶颈不一定都在 embedding、reranker 或 LLM;
    • 对有结构索引的系统,实体定位和索引访问模式本身就可能决定能不能上线。
  • 如果把它放进更大的 GraphRAG / Tree-RAG 脉络里,它代表的是一条很工程化的路线:
    • 不改生成器;
    • 不改 retrieval objective;
    • 先把知识结构查询层做快。

局限

  • 论文几乎所有收益都体现在检索时间,而不是答案质量提升。
  • 实验里的 answer accuracy 大多在 66% 左右,各方法差距很小,因此这篇论文不能说明它改善了 reasoning。
  • 方法高度依赖 entity forest / Tree-RAG 设定;如果知识库不是层级树,优势不一定成立。
  • 评测规模和任务形态都偏系统实验,不像通用 QA benchmark 那样全面。

相关主题