时间顺序对智能体记忆至关重要：用于长时域智能体的线段树架构

# 时序对智能体记忆至关重要：用于记忆构建与检索的线段树
来源：https://arxiv.org/html/2606.04555
Yifan Simon Liu¹，Liam Gallagher¹，Faeze Moradi Kalarde¹，Jiazhou Liang¹，Armin Toroghi¹，Scott Sanner¹'²
¹多伦多大学 ²Vector Institute for Artificial Intelligence
yifanliu\.liu@mail\.utoronto\.ca

###### 摘要

长时域对话智能体需要在不断演变的事件、任务和目标中与用户进行交互，其中某一时段内的话语往往围绕一个共同话题展开，随后对话再转向新的语境。这类历史记录可自然地表示为按时间顺序排列的线段树，其中连续话语组合成更高层次的片段。然而，现有的基于树的记忆系统大多聚焦于主题结构化的层次体系，往往忽视时间顺序，使得面向时序记忆的两个关键设计问题尚未得到充分探索：（i）如何在新话语到达时在线更新时序树；（ii）如何在检索时同时利用时序层次结构与主题结构。我们提出了线段树记忆（SegTreeMem），这是一种将对话历史表示为话语线段树并保留时间顺序的记忆架构。为支持在线更新，SegTreeMem 将新话语增量地融入线段树，同时维护时间上连续的交互片段。在检索方面，SegTreeMem 通过树结构传播相关性信号，使模型能够整合对话相关部分的信息，更有效地识别与查询相关的上下文。我们的实验表明，在三个数据集和两种 LLM 主干上，SegTreeMem 相比非时序树基线和其他强记忆基线，LLM 评判准确率提升近 20%。这些结果支持以下观点：长时域对话智能体受益于*同时*具备时序性和层次性的记忆索引。

## 1 引言

长时域对话智能体通过多轮对话与用户进行交互，对话由用户和智能体的顺序话语构成\[24 (https://arxiv.org/html/2606.04555#bib.bib24),40 (https://arxiv.org/html/2606.04555#bib.bib40),10 (https://arxiv.org/html/2606.04555#bib.bib10)\]。为了准确回应查询，智能体必须保留并利用早期话语中的相关信息。这就需要一个记忆系统，既能在话语到达时支持高效的**在线构建**以保留完整历史，又能提供**检索机制**以访问与查询相关的信息来支持响应生成\[30 (https://arxiv.org/html/2606.04555#bib.bib30),28 (https://arxiv.org/html/2606.04555#bib.bib28),5 (https://arxiv.org/html/2606.04555#bib.bib5)\]。

参见图注图 1：记忆树的表示方式。语义树可能将不连续的话语分组，忽略时间顺序（上图），而 SegTreeMem 通过为每个节点分配连续的话语跨度来保留时间顺序（下图）。

在现实交互中，对话自然地组织为主题连贯且按时间顺序排列的片段，连续的话语在转向新话题之前共享同一主题\[7 (https://arxiv.org/html/2606.04555#bib.bib7),12 (https://arxiv.org/html/2606.04555#bib.bib12)\]。这意味着过去某条话语与当前查询的相关性不能仅凭其内容来判断，因为同一片段内的话语在语义上相互关联，其含义依赖于同一片段内的周围话语。不考虑时间顺序的记忆系统可能检索到语义相似但上下文不匹配的信息。这使得基于树的记忆结构成为自然之选，因为它们能将对话组织为按层次嵌套、按时间顺序排列的片段，同时保留局部上下文依赖关系。

然而，现有基于树的记忆系统往往聚焦于主题结构化的层次体系，对时间顺序的重视程度较低，留下了两个面向时序树记忆的关键设计问题有待解答：（i）*如何在线构建树，以实时索引传入的话语，同时保持主题连贯性和时间顺序？*（ii）*检索时如何利用结果树结构中的主题组织和时序组织？*

为了在记忆中保留话语的时间顺序，我们使用线段树\[6 (https://arxiv.org/html/2606.04555#bib.bib6)\]，其中每个节点表示连续的话语跨度，内部节点递归地将其跨度划分为有序、互不重叠的子跨度。在线段树结构的基础上，我们提出了线段树记忆（SegTreeMem，如图 1 (https://arxiv.org/html/2606.04555#S1.F1) 所示）。具体而言，我们的贡献如下：

- • SegTreeMem 通过仅更新最右侧前沿路径上的少量节点来插入每条新话语，支持实时树构建，同时保留时间顺序和连贯的节点表示（图 2 (https://arxiv.org/html/2606.04555#S4.F2)）。
- • SegTreeMem 采用结构感知的检索机制，将树用作时序和层次记忆索引，并通过转移矩阵将检索表述为树上的相关性传播，将局部语义匹配与层次主题结构和时序依赖结合起来（图 3 (https://arxiv.org/html/2606.04555#S4.F3)）。
- • 我们在三个记忆数据集和两种 LLM 主干上对 SegTreeMem 进行了实验评估，结果显示相比现有基线有一致的准确率提升，证明了时序和层次记忆索引对对话智能体的益处。

## 2 问题定义

我们考虑一个通过一系列话语与用户交互的对话智能体。令 $x_t$ 表示第 $t$ 条话语。经过 $t$ 条话语后的对话历史为 $X_t=(x_1,\ldots,x_t)$。长时域智能体在整个对话过程中维护一个外部记忆状态。令 $M_t$ 表示处理前 $t$ 条话语后的记忆状态。在本文中，我们关注记忆的两个组成部分：在线记忆构建和记忆检索，分别描述如下。

##### 在线记忆构建。

当新话语 $x_{t+1}$ 到达时，记忆状态更新为 $M_{t+1}=\mathcal{U}(M_t,x_{t+1})$，其中 $\mathcal{U}$ 表示在线更新算子。有效的 $\mathcal{U}$ 应满足：

1. （i）**增量更新**：将 $x_{t+1}$ 融入 $M_t$，无需从头重建记忆。
2. （ii）**高效更新范围**：令 $\mathcal{C}_t$ 和 $\Delta_t$ 分别表示更新过程中检查和修改的记忆单元。为支持实时交互，$|\mathcal{C}_t|,|\Delta_t|\ll|M_t|$，理想情况下相对于 $|M_t|$ 呈次线性。
3. （iii）**结构与时序保留**：更新后的记忆 $M_{t+1}$ 应保留结构组织和对话顺序。记忆单元可以被分组或抽象，但不能被重新排序，即 $s_q^{\mathrm{prev}}$

// 分数传播
11: $\tilde{s}_q\leftarrow\tilde{s}_q+\alpha^k s_q^{(k)}$ // 传播分数累积
12: $s_q^{\mathrm{prev}}\leftarrow s_q^{(k)}$
13: **end for**
14: $\widehat{\mathcal{V}}_K\leftarrow\operatorname{TopK}_{v\in\mathcal{G}}\tilde{s}_q(v)$ // 检索最终分数最高的节点
15: **return** $\widehat{\mathcal{V}}_K$

##### 检索不变性。

算法 2 (https://arxiv.org/html/2606.04555#alg2) 首先利用每个节点的标注对其独立评分，然后将局部分数分布与通过对 $W_P$ 应用最多 $H$ 步所得的传播分布混合。设置 $H=0$ 退化为折叠检索。对于自顶向下传播，概率质量从更宽泛的摘要向子跨度移动。对于自底向上传播，质量从具体匹配向其包含的时序上下文移动。最终的 Top-$K$ 选择限制在 $\mathcal{G}$ 内，使得同一评分流程既可支持内部节点检索，也可支持仅叶节点的证据选择。

## 附录 B 扩展相关工作

### B.1 长时域记忆基准

长时域对话记忆基准评估智能体在扩展交互中保留、更新和检索信息的能力。该设置与标准长上下文 RAG\[2 (https://arxiv.org/html/2606.04555#bib.bib2),36 (https://arxiv.org/html/2606.04555#bib.bib36),38 (https://arxiv.org/html/2606.04555#bib.bib38),39 (https://arxiv.org/html/2606.04555#bib.bib39),15 (https://arxiv.org/html/2606.04555#bib.bib15)\] 不同：记忆状态是在一系列用户-智能体交互过程中逐步建立的，查询可能需要跨越时间上分离的轮次、更新的事实、演变的偏好或任务状态来解析信息。我们在三个直接针对这一设置的基准上评估 SegTreeMem：

- • **LoCoMo** 评估跨多会话对话的超长期对话记忆，问题需要从扩展交互历史中检索事实、偏好和事件\[24 (https://arxiv.org/html/2606.04555#bib.bib24)\]。
- • **LongMemEval-MAB** 基于 LongMemEval 的 MemoryAgentBench 重构版本，记忆在扩展对话中增量构建，并在整个交互过程中被反复查询\[40 (https://arxiv.org/html/2606.04555#bib.bib40),10 (https://arxiv.org/html/2606.04555#bib.bib10)\]。该设置与在线记忆构建尤为相关，因为系统必须在新话语到达时维护记忆状态，而非对固定文档进行一次性处理。
- • **RealMem** 在更贴近现实的面向用户场景中评估记忆驱动的交互，问题可能依赖于不断演变的项目状态、用户偏好或先前的任务上下文\[3 (https://arxiv.org/html/2606.04555#bib.bib3)\]。

这些基准与我们的目标高度匹配，因为它们将记忆评估为在交互历史中维护的外部状态。其他长上下文基准（包括合成的"大海捞针"检索任务、长文档问答和书籍级阅读理解）有助于衡量模型能否关注长输入序列。然而，它们并不直接评估本文的核心设置：持久对话记忆索引的在线构建，以及随交互演进从该索引中进行检索。因此，我们将实验重点放在记忆构建和检索都是任务组成部分的基准上。

### B.2 平面检索方法

##### 记忆构建。

平面检索方法将过去的上下文存储为无序的独立记忆记录集合。在稀疏检索中，记录通过词汇匹配信号（如 BM25\[33 (https://arxiv.org/html/2606.04555#bib.bib33)\]）进行索引。在密集检索中，记录被嵌入向量空间并建立最近邻搜索索引\[13 (https://arxiv.org/html/2606.04555#bib.bib13)\]。这些方法简单、可扩展，通常是检索增强生成的强基线。然而，其构建步骤并未显式建模对话的层次结构或时序结构。每个记忆单元通常被视为独立条目，即使其含义依赖于周围的话语。

##### 检索。

在检索时，平面方法通过词汇或语义相似度独立对记忆记录排序。这支持主题匹配，但未显式利用时序或结构上下文。例如，如果某个查询匹配较长连贯跨度中的某条话语，平面检索不会自动恢复附近的话语、包含该话语的摘要或同一交互片段的其他部分。按我们的术语，平面检索满足主题相关性，但不直接利用匹配周围允许的时序或结构邻域。

### B.3 基于图的方法与智能体记忆方法

##### 记忆构建。

基于图的记忆系统和智能体记忆系统通过提取、链接、更新或整合记忆记录来丰富平面记忆。Generative Agents 将记忆存储在流中，并定期综合生成更高层次的反思\[30 (https://arxiv.org/html/2606.04555#bib.bib30)\]。MemoryBank 为长期用户记忆引入了重要性加权和遗忘机制\[43 (https://arxiv.org/html/2606.04555#bib.bib43)\]。MemGPT 将记忆组织为多层级，并允许智能体通过类似分页的操作管理记忆\[28 (https://arxiv.org/html/2606.04555#bib.bib28)\]。更新的智能体记忆系统（如 A-MEM 和 Mem0）强调显式记忆操作，包括提取、更新、链接和整合\[41 (https://arxiv.org/html/2606.04555#bib.bib41),5 (https://arxiv.org/html/2606.04555#bib.bib5)\]。面向目标的记忆推理进一步研究智能体如何将用户话语分解为子目标并检索针对这些推理需求的记忆\[16 (https://arxiv.org/html/2606.04555#bib.bib16)\]。这些系统专为持久智能体记忆设计，但其记忆组织通常由学习到的或启发式的记忆重要性估计、提取的实体或智能体更新决策驱动，而非由确定性的时序约束决定。

##### 检索。

基于图结构的检索方法利用记忆记录之间的链接来扩展初始主题匹配\[21 (https://arxiv.org/html/2606.04555#bib.bib21),22 (https://arxiv.org/html/2606.04555#bib.bib22)\]。这一思路与经典图排序方法（如 PageRank、个性化 PageRank 和带重启的随机游走）相关\[29 (https://arxiv.org/html/2606.04555#bib.bib29),11 (https://arxiv.org/html/2606.04555#bib.bib11),37 (https://arxiv.org/html/2606.04555#bib.bib37)\]。HippoRAG 将这一视角应用于 LLM 记忆，通过构建基于语料库的知识图谱并使用个性化 PageRank 获取结构感知的相关性信号\[9 (https://arxiv.org/html/2606.04555#bib.bib9)\]。A-MEM 也使用显式记忆链接来支持联想检索\[41 (https://arxiv.org/html/2606.04555#bib.bib41)\]。我们的检索方法与相关性可通过结构传播的高层思路一致。关键区别在于底层结构。基于图的方法通常在实体、事实或记忆记录链接上传播。相比之下，SegTreeMem 在时序层次结构上传播，其节点对应连续的对话跨度。这使得传播可以直接解释为在局部话语、包含它们的时序上下文以及相关邻近跨度之间移动。

### B.4 基于树的记忆方法

##### 记忆构建。

基于树的记忆方法将文本组织为层次抽象。RAPTOR 通过聚类文本块并对聚类进行摘要来构建递归抽象树\[34 (https://arxiv.org/html/2606.04555#bib.bib34)\]。LATTICE 类似地为 LLM 引导的检索构建语义层次结构\[8 (https://arxiv.org/html/2606.04555#bib.bib8)\]。MemWalker 通过将相邻片段分组为固定大小的单元来保留文档顺序\[4 (https://arxiv.org/html/2606.04555#bib.bib4)\]。MemTree 专为对话记忆设计，通过将新记忆插入语义最相似的分支来支持在线更新\[31 (https://arxiv.org/html/2606.04555#bib.bib31)\]。这些方法在是否支持在线构建以及是否保留顺序方面存在差异。RAPTOR 和 LATTICE 通过聚类构建语义抽象树，可能将不相邻的片段分组，并且