预算约束下的递归绑定：阶-p张量记忆中的子空间雕刻

# 阶-p 张量记忆中的子空间雕刻 来源：https://arxiv.org/html/2606.11391 ## 资源受限下的递归绑定：阶-p 张量记忆中的子空间雕刻 ###### 摘要 张量积表示为模型中的符号推理提供了所需的结构保真度，但在编码深度递归结构时会遭受指数级维度增长。相反，向量符号架构保持恒定维度，但由于通过叠加进行的有损压缩，其容量和保真度会受到影响。在这项工作中，我们提出了正交子空间雕刻（Orthogonal Subspace Carving，OSC），一种通过将填充符投影到角色基的零空间后再聚合成固定阶-p 张量，从而将填充符绑定到角色的记忆架构。OSC 使用投影来在静态记忆痕迹中强制绑定结构之间的几何正交性。我们证明，这种机制将张量阶与结构深度解耦，从而在恒定记忆占用内实现深度递归绑定。通过基于识别的检索，这种构造允许组件向量比记忆张量**小若干个数量级**，从而在高叠加场景中实现卓越的记忆效率。我们还证明，TPR 是 Clifford 代数中绑定的一种特例，并给出了 OSC 的 Clifford 公式。 机器学习，ICML ## 1. 引言 人类推理的显著特征是其对符号表示执行结构化操作的能力 (Newell, 1980 (https://arxiv.org/html/2606.11391#bib.bib1), 1982 (https://arxiv.org/html/2606.11391#bib.bib2); Marcus, 2001 (https://arxiv.org/html/2606.11391#bib.bib4))。标准神经网络模型难以在已知结构的全新组合上进行系统化泛化 (Dziri et al., 2023 (https://arxiv.org/html/2606.11391#bib.bib8); Li et al., 2023 (https://arxiv.org/html/2606.11391#bib.bib7); Kim and Linzen, 2020 (https://arxiv.org/html/2606.11391#bib.bib6); Keysers et al., 2020 (https://arxiv.org/html/2606.11391#bib.bib5))。弥合这种“神经-符号鸿沟”需要能够支持丰富递归结构但又与连续向量空间的梯度优化兼容的表示 (Kanerva, 2009 (https://arxiv.org/html/2606.11391#bib.bib3); Kleyko et al., 2022 (https://arxiv.org/html/2606.11391#bib.bib15))。

解决上述挑战的一项重要工作是张量积表示 (Tensor Product Representation, TPR) (Smolensky, 1990 (https://arxiv.org/html/2606.11391#bib.bib9))。稍后我们将更详细地讨论，TPR 通过外积操作提供了一种将变量（"填充符"）绑定到结构"角色"的数学上严谨的方法。这显式构造了一种保持绑定之间完美正交性的表示，并允许无干扰（即完美地）精确检索组分。然而，TPR 的维度随结构深度呈**指数级**增长。例如，深度为 $k$ 的树需要一个阶为 $d^{k}$ 的张量空间，这使得精确的深度递归绑定变得棘手 (Soulos et al., 2023 (https://arxiv.org/html/2606.11391#bib.bib10))。虽然最近的稀疏近似可以缓解这种缩放问题，但它们在深层次结构上会遭受显著的性能下降 (Soulos et al., 2024 (https://arxiv.org/html/2606.11391#bib.bib11))。

向量符号架构 (Vector Symbolic Architectures, VSA) 提供了一种压缩的替代方案 (Kanerva, 2009 (https://arxiv.org/html/2606.11391#bib.bib3))。VSA 采用"简化"的绑定操作，如循环卷积或逐元素乘法，将张量积映射回组件向量的固定维空间 (Kleyko et al., 2022 (https://arxiv.org/html/2606.11391#bib.bib15))。这种固定维度使得 VSA 高效。它允许在**恒定**的内存占用内编码复杂结构。但是，存在一个权衡。在使用近似逆的 VSA 中，非正交噪声会随深度**累积**。此外，随着内存变得拥挤（更多叠加），信噪比 (SNR) 会降低，最终影响可靠检索 (Gosmann and Eliasmith, 2019 (https://arxiv.org/html/2606.11391#bib.bib12); Plate, 1995 (https://arxiv.org/html/2606.11391#bib.bib13))。

我们的**贡献**是：  
(a) OSC，一种新颖的记忆架构，通过基于投影的绑定机制将组件向量维度与记忆容量解耦；  
(b) 在高叠加任务中大幅减少内存占用。我们实现了稳健的检索，组件向量比记忆空间小几个数量级；  
(c) 在高叠加场景中近乎无损耗的检索精度，这得益于次线性填充符缩放，允许在较小的总内存占用内实现更大的叠加记忆空间，而无需 TPR 的指数级维度成本。我们针对 VSA 和标准下游应用进行了广泛的实证验证。代码见 https://github.com/vsingh-group/OrthogonalSubspaceCarving。

**利益冲突声明**。无利益冲突。

## 2. 预备知识

我们首先简要概述张量积表示（TPR）和向量符号架构（VSA）。

**空间**。VSA/TPR 操作三种特定类型的"空间"，即：**填充符**、**角色**和**记忆**。  
**填充符**表示正在存储的原子内容、概念或对象（例如，“蓝色”、“狗”、“5”）。  
**角色**定义了与该内容关联的结构槽或属性（例如，“颜色”、“动物”、“数值”）。  
将角色绑定到填充符会在记忆内创建该概念的实例，从而允许表示层次化数据。见图 1 (https://arxiv.org/html/2606.11391#S2.F1)。

###### 定义 2.1 (VSA/TPR 填充符)。填充符空间是超空间 $\mathcal{V}$，通常为 $\mathbb{R}^{d}$、$\mathbb{C}^{d}$ 或 $\{0,1\}^{d}$。一个特定的填充符 $f \in \mathcal{V}$ 是填充符空间中的一个单一向量。

###### 定义 2.2 (VSA/TPR 上下文)。类似地，角色空间也是 $\mathcal{V}$。一个特定的角色 $r \in \mathcal{V}$ 是一个单一向量。一个**上下文** $\mathcal{C}$ 只是角色 $r_1, r_2, \ldots, r_c \in \mathcal{V}$ 的集合。

VSA 和 TPR 使用三个主要操作：
1. **绑定 ($\otimes$)**：该操作用角色**关联**填充符，创建绑定对象 $T=f \otimes r$。
2. **解绑 ($\oslash$)**：该操作利用角色从对象**检索**填充符，$(f \otimes r) \oslash r = f$。
3. **捆绑 ($\oplus$)**：该操作将多个绑定对象叠加到一个记忆空间中：$M = T_1 \oplus T_2 \oplus \dots \oplus T_k$。这几乎总是简单的加法。

![图 1](https://arxiv.org/html/2606.11391/S2.F1)  
**图 1：** 原始信号属性被识别（步骤 1）并使用码本映射到向量（步骤 2）。然后将它们绑定到相应的角色并叠加形成记忆（步骤 3）。

### 2.1 张量积表示（TPR）

在 TPR 中，记忆空间**并非**与角色和填充符空间相同，而是更高阶的张量。

###### 定义 2.3 (TPR 绑定)。绑定操作就是张量积。给定一个填充符 $f \in \mathbb{R}^{d}$ 和一个角色 $r \in \mathbb{R}^{d}$，绑定对象 $T$ 是 $\mathbb{R}^{d \times d}$ 中的一个矩阵：
$$
T = f \otimes r = f r^{\top}
$$
(1)  
因此，当我们将 $1$ 个角色绑定到一个填充符时，记忆空间是 $2$ 阶张量。当将 $|\mathcal{C}|$ 个角色绑定到一个填充符时，记忆空间是 $(|\mathcal{C}|+1)$ 阶张量，有 $d^{|\mathcal{C}|+1}$ 个条目。这随上下文大小呈指数增长。

###### 定义 2.4 (TPR 解绑)。解绑是绑定对象与角色向量的内积收缩：
$$
f = M(r) = M \cdot r = \sum_{i} M_{ij} r_j \quad \text{需要修正，标准形式是} \quad f = M r
$$
(2) 实际上，TPR 解绑是通过收缩实现的，但这里公式需要准确。原文可能是 $f = M r$。

**正交性与叠加**。TPR 的一个关键特性是，如果角色向量相互正交，叠加是**无损的**。也就是说，多个填充符-角色绑定可以捆绑到单个记忆矩阵 $M$ 中，而项之间**没有任何**干扰。设角色 $r_1, r_2$ 正交。

###### 示例 2.5。对于记忆 $M = f_1 r_1^{\top} + f_2 r_2^{\top}$，检索是精确的：
$$
M r_1 = f_1 (r_1^{\top} r_1) + f_2 (r_2^{\top} r_1) = f_1 (1) + f_2 (0) = f_1
$$
(3)

### 2.2 向量符号架构（VSA）

TPR 通过正交性保证完美检索，但记忆大小呈指数级增长（随上下文大小）。相反，VSA 使用压缩的、保持维度的操作。因此，VSA 可以被视为 TPR 的近似。基本上，张量积被"折叠"回原始向量空间 $\mathcal{V}$，以固定记忆大小换取精确性。

###### 定义 2.6 (VSA 绑定)。绑定操作是一个映射 $\otimes: \mathcal{V} \times \mathcal{V} \to \mathcal{V}$，**保持维度**。对于填充符 $f \in \mathbb{R}^{d}$ 和角色 $r \in \mathbb{R}^{d}$，绑定对象 $T$ 仍然是 $\mathbb{R}^{d}$ 中的向量：
$$
T = f \otimes r \in \mathbb{R}^{d}
$$
(4)

###### 定义 2.7 (VSA 解绑)。解绑 $\oslash: \mathcal{V} \times \mathcal{V} \to \mathcal{V}$ 也保持维度。给定绑定对象 $T = f \otimes r$，用角色解绑给出填充符的一个版本：
$$
\hat{f} = T \oslash r
$$
(5)  
在许多架构中，对于单个对，该操作是精确的 ($\hat{f} = f$)。但当解绑多个对的叠加时，解绑给出 $f$ 加上一个伪随机噪声项（来自其他存储对的干扰）。
$$
(f_1 \otimes r_1 + f_2 \otimes r_2) \oslash r_1 = f_1 + \underbrace{(f_2 \otimes r_2) \oslash r_1}_{\text{噪声}}
$$
(6)

### 2.3 识别、回忆和清理记忆

符号记忆系统可以使用两种不同的查询模式。  
**回忆**从线索重建内容："这个位置存储了什么？"  
相比之下，**识别**测试一个假设："这个特定的绑定存在吗？" 识别将候选绑定与记忆进行比较，并返回相似度分数。

许多系统将解绑与**清理记忆**结合使用。这是一个有效符号的码本。在解绑产生噪声向量后，系统可以识别最近的码本条目录。这有效地将回忆转化为识别：测试每个词汇项并选择最佳匹配。

### 2.4 投影算子

对于子空间 $S \subset \mathbb{R}^{d}$，具有标准正交基矩阵 $B$，到 $S$ 的正交投影是 $P_S = B^{\top} B$。到正交补的互补投影是 $P_S^{\perp} = I - B^{\top} B$。  
$P_S^{\perp}$ 是幂等的 ($P_S^{\perp} P_S^{\perp} = P_S^{\perp}$)，并且 $P_S P_S^{\perp} = 0$（投影是不相交的）。

## 3. 符号记忆的结构性挑战

考虑在符号记忆中存储 $1000$ 棵解析树的任务，每棵深度为 $5$。一个标准 TPR 即使对于适度维度 $d=128$ 也需要一个阶为 $d^{5}$ 的记忆张量。这需要 $3 \times 10^{10}$ 个参数。VSA 将记忆保持在 $d=128$，这很好。但叠加 $1000$ 个绑定会使信噪比 (SNR) 降至 $128/1000 \approx .358$（接近噪声底限）。

**挑战**。为了支持符号推理，记忆系统必须适应深度递归结构，允许在单个痕迹内叠加多个结构，并在查询时保持高判别能力。这些要求相互矛盾。

### 3.1 记忆三角

我们上面描述的张紧体现为结构保真度、内存占用和叠加容量之间的三方权衡，我们可以快速检查一下。

**完美检索** $\rightarrow$ **指数增长**。TPR 将每个绑定放置在不同的张量维度中。这带来零干扰。深度为 $k$ 的树需要 $O(d^{k})$ 空间，即使对于适中的深度也是棘手的。

**固定占用** $\rightarrow$ **累积干扰**。VSA 将所有绑定压缩到 $O(d)$ 维度中。叠加 $N$ 项引入的干扰缩放为 $O(\sqrt{N/d})$。随着记忆填充，容量会下降。

所有方法都必须占据三角形的某个区域。权衡是不可避免的。问题在于在给定的约束条件下**哪些**权衡能产生有利的缩放。

这种权衡也可以用几何方式表述。如果 $N$ 个单位范数的记忆痕迹嵌入到一个 $D$ 维空间中，平均平方相干性 $\mu^{2} = \frac{1}{N(N-1)} \sum_{i \neq j} |\langle T_i, T_j \rangle|^{2}$ 的下界由韦尔奇界 (Welch, 1974 (https://arxiv.org/html/2606.11391#bib.bib54)) 给出：
$$
\mu^{2} \geq \frac{N-D}{D(N-1)} \quad \text{当 } N > D.
$$
(7)  
一旦存储项的数量超过有效维度，串扰就不能被驱动到零。因此相关的设计问题不在于干扰是否可以消除，而在于架构如何在上下文复杂度、词汇表大小和叠加容量之间分配有效维度。OSC 利用记忆张量的 $d^{p}$ 有效维度，同时将每个填充符的存储保持在 $p \cdot d$。

### 3.2 识别和局部结构可能就足够了

为了驾驭这种权衡，我们必须重新评估符号处理中严格必要的条件。

**识别与重建**。大多数符号推理系统在固定词汇表上操作：解析树