Grounded Reasoning

grounded-reasoning — 面向 LLM 和 Agent 的有依据、可保证推理

TL;DR. LLM 在多跳关系推理中会产生幻觉。这是一个 关系代数验证器，Agent 可以调用它，在断言某个主张之前进行核验： 不消耗模型 token，精度有保证（当且仅当存在有依据的证明路径时才接受主张），与语言和提供商无关。可作为库、 函数调用工具或 MCP 服务接入。已在真实 LLM（DeepSeek 等）和公开的 CLUTRR 基准上验证。参见 docs/integration.md。

📄 完整论文：PAPER.md · 集成指南：docs/integration.md · 30 秒上手：快速入门笔记本

越南语版：README.vi.md

---

为什么要做这个项目

LLM 在单跳事实上表现可靠，但在组合推理上会崩溃——无法将多个正确事实串联成多步结论。在 CLUTRR（亲属关系推理）上，DeepSeek 的准确率会随着推理深度增加而下降，而有依据的算子组合求解器则能保持约 100% 的准确率——且不消耗 token：

acc
100% ●─────●─────●─────●─────●─────●─────●   ● Grounded solver (algebra, 0 tokens)
 90% |
 80% ○
 70% |  ╲
 60% |   ╲
 50% |    ╲
 40% |     ○           ○                     ○ DeepSeek (LLM)
 30% |      ╲         ╱ ╲
 20% |       ○─────○     ╲
 10% |                    ○─────○
  0% +──┴─────┴─────┴─────┴─────┴─────┴─────┴─
      hop 2    3     4     5     6     7     8   (composition steps)

     hop:      2     3     4     5     6     7     8
     DeepSeek: 83%   42%   25%   25%   42%   17%   8%
     Solver:   100%  100%  100%  100%  100%  100%  100%

(CLUTRR/v1 gen_train234_test2to10，clean-chain，每跳 n=12；完整测试集 n=635：求解器覆盖率为 99.5%，准确率为 99.2%。grounded_reasoning/experiments/clutrr_eval.py。)

---

它是什么 / 不是什么（坦诚说明）

**它是：**基于关系算子代数构建的、具有保证的推理验证层。

• 精度 = 1.0，有保证（定理 G）——仅当存在有依据的证明路径时才接受主张。
• 不额外消耗 token——本地矩阵乘法，无需调用 LLM。相比之下，“让 LLM 自行验证”会多消耗 110% 的 token，精度却只有 34%。
• 双向保证（定理 I）——精度和召回率都有严格界限。
• 无需外部知识库（SGDC）——使用 LLM 自身的一致性。 精度 = 1.0 的前提是 LLM 自身的原子事实可靠；这一假设也可以测量——calibrate_transitivity 不关心事实来自外部知识库还是模型自身的断言，因此无需编写新代码，就能校准 SGDC 实际输出的精度（参见 self_grounded_calibration_eval.py， PAPER.md §6 的备注）。

它不是：“前所未有的突破”。Katz 指数、Neumann 级数、 图可达性和神经符号落地都是经典数学与技术。这里的贡献在于将它们统一、给出经过测量的保证以及基准数据——而不是提出新的基本方法。这个防护模块需要关系图 （由用户提供或从 LLM 事实中提取）；灵活性有限（参见 PAPER §5）。

代数本身无法察觉的两个隐患（以及如何防范）

这些问题在评审中被提出，经过复现并修复；每个问题都提供了一个可选防护措施，而不是被掩盖起来：

• 默认情况下，实体身份按精确字符串判断。 如果 LLM 抽取对某个实体的表面形式不一致（"Bob" 与 "bob"），图会将它们视为两个节点，导致真实路径悄然中断——随后防护措施会（根据其自身的约定，正确地）拒绝一条实际上为真的声明。 修复（二元）：GroundedReasoner(normalize=lambda s: s.strip().casefold()) 会在表面形式变体成为图键之前将它们合并；证明仍会显示每个实体首次出现时的原始拼写。定理 N 精确刻画了何时这样做是安全的：只要 normalize 不会合并两个实际不同的实体，精确率就会保持 恰好为 1.0——这是唯一可能出错的情况，因此 gr.calibrate_normalization(labeled_pairs) 正是要用留出证据衡量这一点，并复用与定理 M 相同的 Clopper-Pearson 方法。
• 定理 G 不知道 via 在现实中是否具有传递性。 它保证的是“在 via 的闭包下存在一条路径”，而不是“via 在现实中确实可以组合”。如果组合的关系只有部分或条件性传递（"trusts"：A 信任 B，B 信任 C，并不意味着 A 信任 C），你就会得到一个置信度很高且数学上正确的 grounded=True，但它回答的是一个与你原本想问的问题不同的问题。 修复（二元）：GroundedReasoner(transitive_relations={"parent", "is_a", ...}) 会让防护措施对任何未声明的关系抛出 ValueError，将一个隐式的建模假设变成明确且经过检查的假设。修复（测量式——定理 M）：gr.calibrate_transitivity(rel, labeled_pairs) 用一个实际数值取代二元的“声明或拒绝”机制——即基于留出的带标签对，计算“图中有依据的 rel 声明确实为真”的 Clopper-Pearson 置信下界。二元防护措施只能猜测或直接拦截，而校准后的界限会告诉你应该信任它多少。

这两种可选防护措施默认均关闭（与先前版本行为完全一致）。复现方式：tests/test_agent.py::TestEntityNormalization、::TestTransitiveRelationsGuard、::TestTransitivityCalibration、::TestNormalizationCalibration；A/B 对比： transitivity_calibration_eval.py、 normalization_calibration_eval.py。

异构关系链。 verify(via=rel) 将一种关系与其自身组合；gr.verify_path(subject, obj, via=["parent","employer"]) 则按精确顺序组合不同关系（例如，推导出“经济上依赖于”的声明）——这并不是新的数学方法（OperatorRelationAlgebra.follow 已经可以按照定理 G 精确组合混合关系链；这里仅是在门面接口中公开该功能，并重建证明路径）；而 gr.calibrate_path(via, labeled_pairs) 则使用与 calibrate_transitivity 相同的 Clopper-Pearson 引擎校准这一固定模式（参见 PAPER.md §5.3.4）。在 8,000 个三元组上与独立的真实值 BFS 进行核对，结果为零处不匹配：tests/test_agent.py::TestHeterogeneousPathVerification、 heterogeneous_path_calibration_eval.py。

这与常见修复方案有何不同

方案	额外 token	保证	需要外部知识库
LLM 自我验证（第 2 次调用）	+110%	无（测得的精确率为 34%）	否
自一致性 / 多数投票	随样本数量增加	无，仅有统计保证	否
RAG / 外部 KG grounding	不定	取决于检索效果	是
此防护机制	+0	精确率 = 1.0（定理 G）	否
此防护机制，自我 grounding（SGDC）	+0	给定可靠原子事实时，精确率 = 1.0（定理 I）	否
此防护机制，保形	+0	覆盖率 ≥ 1−α，与分布无关（定理 K）	否

---

三个定理，一个算子（F = G = H）

推理核心建立在一个统一关系之上（已通过数值验证，误差为零）：

视角	定理	内容
模糊扩散推理	F	conf(a→b) = Σ αᵏ(Pᵏ)[a,b]，经过校准且有依据
关系算子代数	G	组合 = 算子乘积，传递闭包 = Σ 次幂
谱分析（Katz）	H	engine.infer = resolvent (I−αP)⁻¹−I（误差为 0.0）

⟹ 模糊推理就是对关系算子的谱分析。grounded_reasoning/reasoning/。

另外六个定理扩展了这一核心：I（针对自我 grounding、无需外部知识库的变体，提供双向精确率 / 召回率保证）、J（闭包学习完备性，已在 CLUTRR 上验证）、K（保形推理——在有噪声的关系图上提供与分布无关的覆盖率，其中包括由 LLM 从原始文本中抽取得到的关系图）、L（Horn 前向链式推理，将传递闭包推广到合取规则）、M（经验传递性校准——用 Clopper-Pearson 置信界取代盲目的传递性假设，改用实测值）、以及 N（归一化精确率隔离——精确率 = 1.0 只会因过度合并而失效，只有这一点需要校准）。全部九个定理均已在 PAPER.md 中陈述、证明并通过数值验证。

---

真实 LLM 上的证据（DeepSeek）

实验	结果
幻觉防护（亲属关系）	精确率 33% → 100%，检出 92/92（两个随机种子），0 个误拒绝
幻觉防护，更难的压力测试（48 人家谱、包含兄弟姐妹 / 配偶干扰事实、打乱的文本、T=0.7、保证无答案的陷阱问题）	原始 DeepSeek 精确率 4.6%（捏造了 2124 个名字，90 个陷阱问题中有 86 个以捏造内容作答）；防护后精确率 100%，0 个泄漏，0 个正确答案被丢弃 — guard_llm_stress_eval.py
防护机制的 token 成本	+0 个 token（相比之下，LLM 自我验证：token 增加 +110%，精确率为 34%）
SGDC（自我 grounding，无外部知识库）	仅凭内部一致性，精确率从 78% → 100%
稠密、反常识本体	精确率 31% → 100%，检出 106/106，0 个误拒绝 — nl_ontology_eval.run_dense
CLUTRR（公开基准）	求解器在每一跳都达到约 100%，而 DeepSeek 从 83% 降至 8%
困难段落（9 步链、8 个问题）	DeepSeek 捏造 1/8（方向错误）；有依据的系统 8/8，且提供证明 — examples/hallucination_demo.py

---

基于 LLM 从原始文本中抽取的关系图进行可靠推理

防护机制 / 求解器需要一张干净的图。但如果让 LLM 从自然语言文本中抽取关系，得到的图就会带有噪声（缺少 / 多出边）。保形推理（定理 K）正是为此而设：将算子置信度作为评分，校准阈值 ⟹ 即使面对带噪声的图，也能获得与分布无关的覆盖率 ≥ 1−α。

端到端演示：DeepSeek 从文本中抽取「is a」关系图 → 保形推理在抽取出的图上运行（真实值仅用于评分）：

文本	LLM 提取（P / R）	覆盖率（目标 ≥90%）	效率（FPR）
简单	100% / 99.7%	91.3%	0.0
困难（嵌套子句 + 易混淆干扰项）	99.5% / 68.5%	93.0%	0.77

LLM 提取漏掉了 31% 的边（图确实充满噪声）→ 覆盖率保证依然成立（93% ≥ 90%），只有效率会下降。 有效性始终成立；效率取决于图的质量。

⟹ 为自然语言关系上的保证推理开辟了一条路径——硬性防护机制无法触及这类关系。grounded_reasoning/experiments/conformal_llm_eval.py。

在丢弃边占主导的噪声下，可以进一步提高效率，而不牺牲有效性。 ConformalReasoner.calibrate(..., group_fn=...) 会为每个组单独校准阈值，而不是使用一个全局阈值（Mondrian conformal——经典方法，并非新方法）；redundancy_group 根据一对节点在提取图中是否存在多条游走对其分组，无需真实标注即可计算。先前尝试的另一种分组方式（按跳数距离）在发布前经数值验证被证伪——它让效率变得更差，而非更好，因此被弃用。当丢弃的边主导噪声时（这与本系统实际的 LLM 提取噪声模式相符），冗余分组会将 FPR 从 98.7% 降至 80.8%，同时覆盖率仍保持 ≥90%；而当噪声主要来自虚假新增边时，我们也如实说明它几乎没有帮助。 redundancy_conformal_eval.py，PAPER.md §7.1 的说明。

另一种不同且相互独立的弱点——噪声水平随时间漂移，而非噪声具有异质性——需要另一种经典工具。 Split-conformal（以及上文提到的 Mondrian 扩展）假设校准数据和测试数据来自同一分布；如果不同文档批次之间的提取质量发生变化，这一假设便不再成立。AdaptiveConformalReasoner（自适应共形推断——Gibbs 和 Candès，2021 年，经典方法，并非新方法）会根据持续输入的已确认真实样例更新阈值，而不是在一次校准后将其固定。当噪声在数据流中途发生变化（p_drop 从 0.05 → 0.45）时，固定阈值的覆盖率会从 88.6% 降至 47.6%——悄无声息地远低于 90% 的目标；而 ACI 在测试的 15/15 次试验中恢复至 89.6%。 drift_conformal_eval.py，PAPER.md §7.1 的说明。 效率提升最大的结果：移除特定的坏边，胜过围绕它们进行校准。 identify_suspect_edges 会移除出现在留出集 FALSE 标签声明的证明路径上、但未出现在任何 TRUE 标签声明的证明路径上的边——这是一条简单的决策规则，并非统计保证。在 5 种噪声条件（每种 60 个种子）下均已验证：假阳性率（FPR）在所有条件下都大幅且稳定地下降，例如 77.0% → 49.2%（丢边占主导）以及 58.7% → 15.7%（伪边占主导；在这种情况下，redundancy_group 几乎毫无作用）——剩余图上的覆盖率基本不受影响。与上述所有校准方法不同，这种方法不提供错误发现率保证——这是一个经过实际测量的权衡：在默认配置（identify_frac=0.5, min_evidence=1）下，各种条件中的汇总误删率为 13.2%–32.2%。在推荐配置（identify_frac=0.85, min_evidence=2，通过帕累托扫描得出——这是 identify_and_prune_edges 的默认配置，该函数会自动应用此配置，因此这是最省事的选择）下，误删率降至 1.5%–3.1%（95% 置信上限为 2.6%–6.6%），代价是清理后的 FPR 略有上升（例如，在丢边占主导的条件下约从 49% → 59%，仍远低于原始基线 77%），且预留用于评估的数据集更小。我们还在真实 LLM（DeepSeek）上进行了验证，而不仅仅是在模拟噪声下：数据中每条候选边都恰有一次带标签的交互作为依据（不重复查询——这符合部署时每条声明只验证一次的实际情况）。在这种条件下，上述计数规则（min_evidence≥2，以及启用 use_propagation=True 的感知枢纽节点版本）完全不会触发，因为它们要求一条边独立达到证据门槛两次，而单次交互证据永远无法满足这一要求。将 min_evidence 降至 1 确实能拦截真实的幻觉边，但单独使用时会使下游 FPR 高于什么都不做时的水平（63.0% → 70.7%；在 15 个数据划分中仅 4 个优于原始结果）——追溯发现，这是因为扩散引擎会按行归一化；当某个源的其他边被剪除后，转移概率便会集中到该源剩余的边上。将这一拦截决策与 masked_infer 配合使用（按每个源剪枝前的度数进行归一化，因此移除边只会移除置信度，不会重新分配置信度），则能获得实际改善：63.0% → 54.0%，在 15 个划分中有 12 个优于原始结果，且合成基准测试上没有性能回退。我们也尝试了学习式（逻辑回归）替代方案，但予以否决：它完全无法将合成训练数据中学到的内容泛化到真实数据。对于任何仅依赖被移除边的真实声明，剪枝也会损害召回率；此外，它会原地修改图（这是不可逆的变更，不同于只调整阈值的校准）。 edge_pruning_eval.py、 edge_pruning_llm_eval.py、 PAPER.md §7.1 的说明。

---

无外部知识库的自我验证（SGDC）

上述防护机制需要提供某种关系图。自我锚定演绎一致性（定理 I）连这一步都省去了：它利用了这样一个事实——大模型对原子（1 跳）事实的准确率通常很高，但在组合推理时会产生幻觉。取模型自身确信的 1 跳事实，用这些事实构建算子闭包，然后拒绝模型自身得出的、超出其自身闭包的任何多跳结论——幻觉信号来自自我矛盾，而不是与外部来源不一致。

from grounded_reasoning import GroundedReasoner

# the LLM's OWN atomic facts (no external KB) -- taken at face value
gr = GroundedReasoner()
gr.add_facts([("sparrow", "is_a", "bird"), ("bird", "is_a", "animal")])

# the LLM's OWN multi-hop conclusion, self-verified against ITS OWN facts above
gr.verify("sparrow", "animal", via="is_a")   # grounded=True: self-consistent
gr.verify("sparrow", "plant",  via="is_a")   # grounded=False: self-contradiction, blocked

	精确率	召回率
原始多跳（大模型）	78%	87%
SGDC（自我锚定，无外部知识）	100%	72%
上限：使用外部图进行过滤	100%	87%

代价是召回率降低（72%，而非 87%）：自闭包较为保守。而定理 I 的 precision=1.0 是有条件的——只有模型自身的原子事实可靠时，这一结论才成立；在与先验认知相悖的领域（例如“鲸鱼是一种鱼”），原子精确率本身可能下降，召回率也会随之降低（PAPER.md §6 如实记录了这一点，并未加以掩饰）。

这一假设也可以测量，无需编写任何新代码。 gr.calibrate_transitivity(rel, labeled_pairs)（定理 M）并不关心 gr 的事实来自外部 KB，还是模型自身的原子自我断言——因此，对仅由大模型自身事实构建的推理器调用它，可以直接根据留出证据校准 SGDC 的实际输出精确率，而不是假设原子事实可靠。在一个特意将 15% 原子事实设为错误的合成领域中，SGDC 的实际精确率降至约 74%（并非直觉上预期的约 85%——单条错误的原子边会组合出多个下游结论，放大其影响），而校准后的界限在 98.3% 的试验中都正确地低于这一数值——self_grounded_calibration_eval.py，参见 PAPER.md §6 的说明。

可运行示例：examples/self_grounded_demo.py（离线）· DeepSeek 实时示例： grounded_reasoning/experiments/self_grounded_eval.py。

---

快速入门

pip install grounded-reasoning

# or, for development (tests + lint):
git clone https://github.com/ALEXaquarius/grounded-reasoning
cd grounded-reasoning && pip install -e ".[dev]"
pytest tests/                       # every theorem + offline-locked logic, no network needed

# Use it right now (no LLM/network needed):
python -c "from grounded_reasoning import GroundedReasoner as G; r=G(); r.add_facts([('a','p','b'),('b','p','c')]); print(r.verify('a','c',via='p'))"

# Real-LLM experiments (need a key — read from an env var, NEVER hardcoded):
export DEEPSEEK_API_KEY=sk-...        # bring your own; .env is gitignored
python -m grounded_reasoning.experiments.guard_llm_eval        # hallucination guard
python -m grounded_reasoning.experiments.guard_llm_stress_eval # harder: distractors + traps + high temperature
python -m grounded_reasoning.experiments.self_grounded_eval    # SGDC
python -m grounded_reasoning.experiments.clutrr_eval           # public CLUTRR benchmark
python -m grounded_reasoning.experiments.conformal_llm_eval    # end-to-end conformal (LLM-extracted graph)
python -m grounded_reasoning.experiments.guard_cost_eval       # token cost: guard vs. LLM self-verify
python -m grounded_reasoning.experiments.nl_ontology_eval      # dense anti-commonsense ontology (add run_dense() for the 106/106 result)

---

与 Agent / 大模型集成（grounded_reasoning/agent/）

面向 Agent 的关系推理验证器：在断言多跳结论之前进行检查——不消耗模型 Token，并保证精确率（仅当存在有依据的证明路径时才接受）。

from grounded_reasoning import GroundedReasoner
gr = GroundedReasoner()
gr.add_facts([("alice","parent","bob"),("bob","parent","carol")])
gr.verify("alice","carol", via="parent")   # Verdict(grounded=True, proof=['alice','bob','carol'], confidence=0.36, relation='parent')
gr.verify("alice","zed",   via="parent")   # Verdict(grounded=False, proof=None, confidence=0.0, relation='parent')  ← hallucination blocked

三种集成方式（详情见：docs/integration.md）：

• 库：GroundedReasoner.verify / filter_claims / contradictions。
• 函数调用：TOOL_SPEC（Anthropic）/ openai_tool_spec()（OpenAI）+ run_tool——一个无状态的 verify_relation 工具。
• MCP 服务：python -m grounded_reasoning.agent.mcp_server——可接入 Claude 或任何兼容 MCP 的 Agent。

多提供商（不只支持 DeepSeek）：使用 LLMClient(provider=...)，支持 DeepSeek / OpenAI / Groq / OpenRouter / Together / Mistral / Ollama（本地）——均兼容 OpenAI，可在不修改代码的情况下切换提供商。多语言：实体/关系是不可解释的 Unicode 字符串 ⟹ 无需配置即可支持任意语言（cha、父、والد……）。

真实的函数调用演示（Agent 验证自身并阻止幻觉）： python -m grounded_reasoning.experiments.agent_demo。当图中存在噪声（由大模型从文本中提取关系）时，请使用 ConformalReasoner，以获得覆盖率 ≥1−α保证，而非硬性精确率保证。

---

源码映射

路径	内容
grounded_reasoning/	公共包 — GroundedReasoner、verify_relation、TOOL_SPEC、ConformalReasoner、AdaptiveConformalReasoner、LLMClient
grounded_reasoning/agent/{verifier,tool,mcp_server}.py	公共 API 实现 — HallucinationGuard、函数调用工具、MCP 服务
grounded_reasoning/reasoning/abstract_inference.py	FuzzyInferenceEngine、TypedInferenceEngine、HallucinationGuard（定理 F）
grounded_reasoning/reasoning/operator_algebra.py	关系算子代数（定理 G）
grounded_reasoning/reasoning/relation_spectrum.py	谱、幂零性、Katz 解算子（定理 H）
grounded_reasoning/reasoning/conformal_reasoning.py	保形推理 — 噪声下的覆盖率保证（定理 K）
grounded_reasoning/reasoning/composition_algebra.py	组合表学习，在 CLUTRR 上验证（定理 J）
grounded_reasoning/reasoning/horn.py	Horn 前向链式推理、最小模型语义（定理 L）
grounded_reasoning/reasoning/transitivity_calibration.py	Clopper-Pearson 校准 — 同时用于传递性假设（定理 M）和归一化过度合并风险（定理 N）
grounded_reasoning/reasoning/edge_pruning.py	基于留出证据的边剪枝 — 一种启发式决策规则，并非定理，具有自身经测量的权衡
grounded_reasoning/reasoning/llm_client.py	与提供商无关的 LLM 客户端（从环境变量读取密钥）
grounded_reasoning/theory/theorems.py	九个定理（F–N），附有数值验证
grounded_reasoning/experiments/{guard_llm,guard_llm_stress,self_grounded,self_grounded_calibration,nl_ontology,guard_cost,clutrr,conformal_llm,redundancy_conformal,drift_conformal,inference,transitivity_calibration,normalization_calibration,heterogeneous_path_calibration,edge_pruning,edge_pruning_llm}_eval.py	支撑以上每项主张的真实 LLM 和基准实验
examples/hallucination_demo.py	端到端函数调用演示（真实 LLM，需要密钥）
examples/self_grounded_demo.py	SGDC（定理 I）：在没有外部 KB 的情况下自我验证模型自身的多跳主张（离线）
examples/rag_pipeline_demo.py	将 filter_claims 用作 RAG/Agent 后处理防护，处理异构主张（离线）
examples/calibration_demo.py	并列展示定理 M 和 N：测量传递性和归一化可信度，而非直接假设（离线）
examples/conformal_demo.py	并列展示覆盖率保证与噪声权衡，以及干净图和含噪图（离线）
examples/quickstart.ipynb	可运行的库入门教程（离线，可用于 Colab）

---

起源

本项目最初尝试发明一种无需嵌入的检索算法，使其能够与稠密/RAG 检索竞争。这个研究问题最终得出了严谨、完全诚实的否定结论（与 BM25 打平，明显逊于稠密嵌入，并给出了原因证明）。同一套数学工具——算子代数、谱分析——在另一个问题上则展现出了真实且可测量的价值：保障多跳关系推理。本仓库仅发布经过验证和测试的推理系统；完整的检索研究历程（包括如实记录的每一次失败尝试）保存在单独的研究仓库中，不属于本软件包。完整介绍请参阅 PAPER.md §1。

---

贡献与社区

• 如何贡献及研究原则：CONTRIBUTING.md
• 行为准则：CODE_OF_CONDUCT.md · 安全：SECURITY.md
• 版本历史：CHANGELOG.md · 引用：CITATION.cff
• 许可证：MIT（LICENSE）

---

原则：先证明，再编写代码；采用形式化定义，确保可证伪，并如实报告否定结果 — 参阅 CONTRIBUTING.md。