递归推理系统的状态表示与终止条件

# 递归推理系统的状态表示与终止条件

来源: https://arxiv.org/html/2605.06690
Debashis Guha Amritendu Mukherjee Sanjay Kukreja Tarun KumarS P Jain全球管理学院;debashis\.guha@spjain\.org印度统计研究所;amritendum@alum\.iisc\.ac\.inS P Jain全球管理学院;sanjay\.ds18dba008@spjain\.orgeClerx Services Ltd\.;Tarun\.Kumar06@eclerx\.com

###### 摘要

递归推理系统在获取新证据和细化累积理解之间交替进行。两个设计选择通常隐含其中：如何表示不断变化的推理状态，以及何时停止迭代。本文解决了这两个问题。我们将推理状态表示为一个*认知状态图（epistemic state graph）*，其中编码了提取的主张、证据关系、未决问题以及置信度权重。我们定义了*顺序间隙（order-gap）*，即“先扩展后整合”与“先整合后扩展”所达到的状态之间的距离；较小的顺序间隙表明这两种顺序达成一致，进一步迭代不太可能有所帮助。我们的主要结果给出了线性化顺序间隙在不动点附近非退化的充要条件，展示了该准则在何时具有信息量而非代数上空洞。这是一个局部条件，而非全局收敛保证。我们将该框架应用于递归推理系统，并概述了其在代理循环、思维树推理、定理证明和持续学习中的应用。

关键词\.递归推理；知识图谱；状态表示；迭代细化；终止准则；算子非交换性；收敛检测；长上下文推理\.

## 1\. 引言

### 1\.1\. 作为适应性推理的递归推理

越来越多的机器学习系统通过迭代细化而非单次推断来运行。在每一步中，这样的系统都会获取新信息（检索到的文档、观察到的行动结果、采样的假设或新生成的思维链步骤），并在决定是进一步迭代还是提交输出之前，将其集成到累积的内部状态中。这种模式出现在迭代检索增强生成（Trivedi et al., 2023 (https://arxiv.org/html/2605.06690#bib.bib10)）、代理行动-观察循环（Yao et al., 2023a (https://arxiv.org/html/2605.06690#bib.bib12)）、递归语言模型（Zhang et al., 2025 (https://arxiv.org/html/2605.06690#bib.bib14)）、思维树（tree-of-thought）和思维图（graph-of-thought）推理（Yao et al., 2023b (https://arxiv.org/html/2605.06690#bib.bib13); Besta et al., 2023 (https://arxiv.org/html/2605.06690#bib.bib4)）以及持续学习（Kirkpatrick et al., 2017 (https://arxiv.org/html/2605.06690#bib.bib2)）中。我们将这一类称为*递归推理系统*。

尽管种类繁多，递归推理系统具有共同的结构。有一个内部状态 $s_t$ 代表系统在步骤 $t$ 所持有的内容。有一个*扩展（expansion）*步骤，引入新的外部证据。有一个*整合（consolidation）*步骤，仅利用已有的内容来细化状态。还有一个终止决策：进一步迭代，还是提交结果。

### 1\.2\. 缺失的两个组件

在当前系统中，状态和终止准则都是隐式处理或从外部强加的，它们的缺失导致了以下四种经过充分研究的架构中特有的失效模式：

**思维链和思维树推理。** 思维链提示（Wei et al., 2022 (https://arxiv.org/html/2605.06690#bib.bib11)）及其树状扩展（Yao et al., 2023b (https://arxiv.org/html/2605.06690#bib.bib13)）将推理状态表示为文本痕迹。没有明确记录哪些主张得到支持、哪些存在冲突、哪些仍未解决。矛盾在没有被检测到的情况下累积；推理在步骤间漂移；并且没有机制根据后来的证据重新审视或修正早期的结论。终止由固定的深度或迭代次数决定，没有推理完成的概念。

**检索增强生成和多跳问答。** 像 IRCoT（Trivedi et al., 2023 (https://arxiv.org/html/2605.06690#bib.bib10)）这样的迭代检索系统在检索证据和生成推理步骤之间交替进行。检索到的事实并未在迭代间进行关系跟踪，来源未以结构化方式保留，系统也没有表示它还需要寻找什么。这导致重复检索、遗漏关键证据以及跨文档的不一致综合。终止是固定的跳数或令牌预算，没有信号表明进一步检索是否会改变答案。

**代理行动-观察循环。** 在 ReAct 风格的代理中（Yao et al., 2023a (https://arxiv.org/html/2605.06690#bib.bib12)），状态是行动和观察的序列，没有目标、子目标或已解决与未解决任务的标准表示。这产生了循环行为、重复的工具调用以及无法识别完成。终止是任意的最大步数或手动停止条件。

**迭代自优化。** Self-Refine（Madaan et al., 2023 (https://arxiv.org/html/2605.06690#bib.bib9)）和相关方法在没有明确表示已修复的内容、仍不确定的内容或稳定内容的情况下，迭代生成-批评-优化循环。没有这样的状态，系统就无法获得何时进一步优化有益的信号。经验上，没有外部反馈的内在自我修正经常无法改善并可能降低性能（Huang et al., 2023 (https://arxiv.org/html/2605.06690#bib.bib6)）：系统在答案之间振荡、过度优化或幻觉出改进。终止是固定的迭代次数或主观启发式。

在所有四种情况下，状态隐含在瞬态文本或隐藏激活中，而不是结构化、持久且可检查的；终止是由固定限制强加的，而不是从系统自身的轨迹中推导出来的。

### 1\.3\. 提议

我们提出将状态表示和终止作为明确的设计选择，并对两者给出具体定义。对于状态，我们引入了*认知状态图*（第 2 节 (https://arxiv.org/html/2605.06690#S2)）：一个结构化图，其节点编码主张、部分答案和未决问题，其边编码证据支持、逻辑依赖和不一致性，所有这些都由置信度加权。这种表示在迭代中是结构化、持久且可检查的。对于终止，我们引入了*顺序间隙*（第 5 节 (https://arxiv.org/html/2605.06690#S5)）：一个源自系统自身算子结构的准则，测量系统状态是否仍然对扩展和整合的顺序敏感。当顺序间隙较小时，两种顺序产生的结果几乎相同，表明进一步迭代不太重要。当它较大时，顺序仍然很重要，系统尚未稳定。

### 1\.4\. 贡献

1. **状态表示**（第 2 节 (https://arxiv.org/html/2605.06690#S2)）：认知状态图，具有平滑的欧几里得嵌入，使得扩展和整合算子易于分析。
2. **算子框架**（第 3 节 (https://arxiv.org/html/2605.06690#S3)）：认知状态上扩展算子 $P_e$ 和整合算子 $Q$ 的形式化定义，及其动态和关键属性。
3. **顺序间隙终止**（第 5 节 (https://arxiv.org/html/2605.06690#S5)）：顺序间隙终止准则、窗口化停止规则以及刻画该准则何时具有信息量的非退化定理（命题 5.2 (https://arxiv.org/html/2605.06690#S5.Thmtheorem2)）。
4. **停止算法**（第 6 节 (https://arxiv.org/html/2605.06690#S6)）：带有顺序间隙终止的递归推理伪代码。
5. **其他递归推理系统**（第 8 节 (https://arxiv.org/html/2605.06690#S8)）：该框架如何应用于代理循环、思维树推理、定理证明和持续学习。
6. **示例**（第 9 节 (https://arxiv.org/html/2605.06690#S9)）：一个闭式二维示例，验证动态和顺序间隙公式。

## 2\. 状态表示

### 2\.1\. 推理状态的要求

递归推理系统通过处理新证据和细化其累积的理解来进行迭代。状态必须支持两种操作：扩展，即添加来自新证据的信息；整合，即细化已有的内容。为了使这两种操作都有原则，状态必须使其输入和输出明确。扩展需要知道哪些已经确立（以避免冗余）以及哪些仍然开放（以引导检索）。整合需要知道哪些主张冲突（以解决它们）以及哪些相互支持（以加强它们）。正确支持这两种操作所需的最少六个对象如下：

- **主张（Claims）**：提取的事实，及其来源和置信度。
- **证据关系（Evidential relations）**：哪些主张支持哪些其他主张，以及支持程度如何。
- **冲突（Conflicts）**：哪些主张彼此不一致。
- **部分结论（Partial conclusions）**：系统对问题或子问题的当前最佳答案，以及支持它的主张。
- **未决问题（Open questions）**：已识别但尚未解决的依赖关系：系统知道需要但尚未找到的东西。
- **置信度（Confidence）**：每个主张和每个关系上的权重，反映证据支持它的强度。

如果没有这些，系统就无法根据早期提取发现的内容来引导后续提取，无法检测新证据是否与已整合的内容相矛盾，也无法识别它仍然需要什么。一个明确持有所有这些内容的状态是原则性扩展和整合的基础。

### 2\.2\. 认知状态图

###### 定义 2.1（认知状态图）.

*认知状态图*是一个元组 $S=(V, E, \ell, c, w)$，其中：

- $V=V_C \cup V_A \cup V_{\mathrm{OQ}}$ 是一个有限的顶点集，划分为**主张**节点（$V_C$）、**部分答案**节点（$V_A$）和**未决问题**节点（$V_{\mathrm{OQ}}$）。
- $E \subseteq V \times V \times \mathcal{T}$ 是一组类型化的有向边，其中 $\mathcal{T}=\{\textsc{Supports}, \textsc{Requires}, \textsc{Contradicts}\}$。
- $\ell: V \to \mathbb{R}^k$ 为每个节点分配一个 $k$ 维属性向量，编码主张文本嵌入和源标识符。
- $c: V \to (0, 1]$ 为每个节点分配一个置信度权重。
- $w: E \to (0, 1]$ 为每条边分配一个置信度权重。

**节点类型。** 主张节点记录提取的事实。部分答案节点持有系统对问题或子问题的当前最佳答案，以及其支持主张。未决问题节点标记系统已识别但尚未解决的依赖关系。

**边类型。** **Supports**（支持）边从主张指向主张或部分答案，编码证据支持。**Requires**（需要）边从部分答案或主张指向未决问题，编码对未解决证据的逻辑依赖。**Contradicts**（矛盾）边连接在当前证据下相互不一致的主张。

**一致性。** 如果在阈值 $\delta \in (0, 1)$ 下，没有两个由 **Contradicts** 边连接的节点 $u, v$ 同时满足 $c(u) > \delta$ 和 $c(v) > \delta$，则图是*一致的*。整合推动图走向一致性。

### 2\.3\. 平滑欧几里得嵌入

认知图是一个组合对象；原始图操作如添加节点、合并节点和重新类型化边是离散的且不可微的。第 5 节 (https://arxiv.org/html/2605.06690#S5) 中的算子分析需要平滑映射。因此，我们使用可微松弛将图嵌入到固定维度的欧几里得空间中。

###### 定义 2.2（图嵌入）.

固定最大节点数 $N_{\max}$ 和属性维度 $k$。*图嵌入* $\varphi: \mathcal{G} \to \mathbb{R}^d$ 通过以下方式编码图状态：

1. 通过其属性向量 $\ell(v) \in \mathbb{R}^k$ 及其置信度权重 $c(v) \in (0, 1]$ 对每个节点进行编码，按节点类型的固定规范顺序填充到 $N_{\max}$ 个槽位中，给出一个维度为 $(k+1)N_{\max}$ 的块。
2. 追加一个扁平化的邻接-权重张量，索引为有序节点对和边类型，维度为 $N_{\max}^2 |\mathcal{T}|$。

总维度为 $d=(k+1)N_{\max} + N_{\max}^2 |\mathcal{T}|$。

嵌入 $\varphi$ 将 $S$ 转换为向量 $\theta = \varphi(S) \in \mathbb{R}^d$，图操作实现为可微坐标更新，使得 $P_e$ 和 $Q$ 在感兴趣状态的邻域内是 $C^1$ 的。我们在全过程中在 $\mathbb{R}^d$ 中使用欧几里得范数。

## 3\. 扩展和整合算子

### 3.1\. 状态空间与算子

令 $(\mathcal{S}, \|\cdot\|)$ 为一个范数完备（Banach）空间。嵌入状态 $\theta_t = \varphi(S_t) \in \mathbb{R}^d \subset \mathcal{S}$ 代表系统在步骤 $t$ 的累积理解。

*扩展算子* $P_e: \mathcal{S} \to \mathcal{S}$ 通过纳入新证据 $e \in \mathcal{E}$（来自可能依赖于当前状态的分布 $P(\cdot \mid \theta_t)$）来更新状态。在认知图设置中，$P_e$ 为新提取的事实添加主张节点，通过类型化边将它们链接到现有节点，并将任何 $e$ 直接解决的未决问题节点提升为部分答案节点。扩展是新外部信息进入状态的唯一途径。

*整合算子* $Q: \mathcal{S} \to \mathcal{S}$ 仅利用已有的内容来细化状态，而不获取新证据。在认知图中，$Q$ 通过移除或降低低置信度端点的权重来解决 **Contradicts** 对，合并冗余的主张节点，并将权重移向当前的最佳部分答案。

扩展-整合分解及其形式化属性在 Guha (2026 (https://arxiv.org/html/2605.06690#bib.bib5)) 中以一般性展开；本文将该分解应用于递归推理系统，并据此推导顺序间隙终止准则。

对于算子分析，我们施加以下假设。上述具体的图操作并不自动在所有嵌入下满足该假设；这是对实现的整合映射的条件，必须针对给定实现进行验证。

**假设（收缩性）。** $Q$ 是 $(\mathcal{S}, \|\cdot\|)$ 上的*收缩*：存在 $\rho \in [0, 1)$ 使得 $\|Q(\theta_1) - Q(\theta_2)\| \leq \rho \|\theta_1 - \theta_2\|$ 对所有 $\theta_1, \theta_2 \in \mathcal{S}$ 成立。

由于 $\mathcal{S}$ 是一个范数完备空间且 $Q$ 将 $\mathcal{S}$ 映射到自身，Banach 不动点定理保证存在唯一的不动点 $\theta^\star \in \mathcal{S}$ 满足 $Q(\theta^\star) = \theta^\star$。这是整合映射 $Q$ 本身的不动点，而不一定...