# PaTH Attention：通过累积 Householder 变换编码位置 **论文**：*PaTH Attention: Position Encoding via Accumulating Householder Transformations* **作者**：Songlin Yang、Yikang Shen、Kaiyue Wen、Shawn Tan、Mayank Mishra、Liliang Ren、Rameswar Panda、Yoon Kim **版本**：arXiv:2505.16381v2，2026-02-03 修订；NeurIPS 2025 camera ready。初稿发表于 2025-05-22。 **获取与研读日期**：2026-10-13 **原文**：[arXiv v2](https://arxiv.org/abs/2505.16381v2) · [本地 PDF](../source/paper.pdf) · [英文汇报](slides.en.pdf) ## 论文总览 PaTH 把位置关系表示为**沿输入序列累积的、由内容决定的矩阵变换**。位置 $j$ 的 key 与位置 $i$ 的 query 相遇之前，要经过 $j+1$ 到 $i$ 的一连串 Householder-like 变换。于是，写入、覆盖、交换等中间事件可以直接改变两者的匹配方式。模型继续使用 softmax 对历史 value 做加权读取，同时获得类似线性递归网络的状态变换结构。 这项工作的贡献连成三步：用单位阵加秩一修正构造便宜而富有表达力的转移；用 UT 紧凑表示和分块扫描把递归式乘积组织成 GPU 友好的计算；在合成状态追踪、760M 语言模型及预训练模型转换中验证效果。760M 模型以 50B tokens、4096 上下文训练时，PaTH 的六项常识推理平均分从 RoPE 的 52.7 提高到 54.2；加入 FoX 后，16K RULER 达到 22.6，而 RoPE、FoX 分别为 0.0、4.9。长距离精确检索更依赖组合设计：8K PhoneBook 上，PaTH 为 0.0，PaTH-FoX 为 66.6。（Sec. 4.2，PDF pp. 8–9，Tables 2–3） 理解这篇论文的关键，是同时看见**路径中的状态变换**和**显式历史检索**。前者解释状态追踪优势，后者保留 softmax attention 的读取方式；两者结合并未把训练复杂度降成关于序列长度的线性复杂度。 ## 结构地图 以下页码均为从 1 开始的 PDF 页码，与本版本印刷页码一致。 | 原文章节 | 作用 | PDF 定位 | |---|---|---| | 1 Introduction | 从 RoPE 的静态位置变换引出状态追踪问题 | pp. 1–2 | | 2 PaTH Attention | 乘法位置编码、Householder 参数化、RNN 关系、PaTH-FoX | pp. 2–3；Theorem 2.1 | | 3 Efficient Training and Inference for PaTH Attention | UT 表示、全矩阵形式、分块训练、缓存更新、分布式讨论 | pp. 3–7；Fig. 1、Eq. (1) | | 4.1 Synthetic Tasks | FFLM、$A_5$ 群字问题、MQRAR-$N$ | pp. 7–8；Table 1、Fig. 2 | | 4.2 Language Modeling | 常规语言建模、长度外推、四组长上下文任务 | pp. 8–9；Tables 2–3、Figs. 3–4 | | 4.3 Converting RoPE into PaTH | 两阶段蒸馏、继续预训练及模型转换结果 | pp. 9–10；Tables 4–5 | | 5 Related Work；6 Limitation；7 Conclusion | 与动态位置编码的关系、数值与效率限制 | p. 10 | | A Representation Power of Transformers with PaTH Attention | 置换追踪与 FFLM 的构造 | pp. 17–19 | | B Experimental Setup & Additional Results | 训练参数、BABILONG 分项、LongBench-E 明细 | pp. 20–21；Fig. 5、Tables 6–7 | ## 一：动机——让位置变换反映途中发生的事件 RoPE 的注意力分数可以写成 $\mathbf q_i^\top\mathbf R^{i-j}\mathbf k_j$。其中 query 和 key 当然依赖内容；这里的限制是，**作用在两端之间的位置变换 $\mathbf R^{i-j}$ 只依赖相对距离**。距离相同的两段序列，无论中间发生多少次变量覆盖或对象交换，位置变换都相同。 状态追踪要求模型组合一连串操作。例如“写入 1—忽略若干位—写入 0—读取”要求保留最近一次写入并忽略旧值；置换任务要求按顺序组合交换，改变操作次序通常会改变答案。PaTH 将这些中间操作纳入 query–key 的双线性匹配，使相对关系具有输入依赖性。（Sec. 1–2，PDF pp. 1–3） 从表达能力看，论文借用固定深度、受限数值精度的 Transformer 电路分析作为背景，并构造 PaTH 可解的 $\mathsf{NC}^1$ 完全问题。在相应模型假设与 $\mathsf{TC}^0\ne\mathsf{NC}^1$ 的条件下，这给出与普通 RoPE Transformer 的表达能力区分。训练能否找到这种计算，则由后续合成实验单独检验。 ## 二：方法——从秩一转移到 softmax 路径注意力 ### 2.1 输入、符号与输出 | 符号 | 含义与维度 | |---|---| | $\mathbf x_t$ | 本层位置 $t$ 的输入表示 | | $\mathbf q_t,\mathbf k_t,\mathbf v_t$ | 单个注意力头的 query、key、value；论文统一采用 $\mathbb R^d$ | | $\mathbf w_t\in\mathbb R^d$ | 归一化的转移方向，$\|\mathbf w_t\|_2=1$ | | $\beta_t\in(0,2)$ | 转移强度 | | $\mathbf H_t\in\mathbb R^{d\times d}$ | 位置 $t$ 的内容相关转移 | | $L,B$ | 序列长度与分块大小 | 为明确非交换矩阵的乘法顺序，本笔记定义 $$ \mathbf F_{a:b}=\mathbf H_a\mathbf H_{a+1}\cdots\mathbf H_b, \qquad \mathbf F_{a:b}=\mathbf I\quad(a>b). $$ 给定本层输入，先产生 query、key、value；额外分支通过**低秩线性层、宽度为 3 的短卷积、$L_2$ 归一化**产生 $\mathbf w_t$，并计算 $$ \beta_t=2\sigma(\mathbf u^\top\mathbf x_t+b), \qquad \mathbf H_t=\mathbf I-\beta_t\mathbf w_t\mathbf w_t^\top. $$ 随后，对因果位置 $j\le i$ 计算 $$ \widetilde A_{ij}=\mathbf k_j^\top\mathbf F_{j+1:i}\mathbf q_i, \qquad A_{ij}=\frac{\exp(\widetilde A_{ij})}{\sum_{r\le i}\exp(\widetilde A_{ir})}, \qquad \mathbf o_i=\sum_{j\le i}A_{ij}\mathbf v_j. $$ 这里沿用原文省略 attention scale 的记法。位置 $j$ 自身的转移不在路径内，位置 $i$ 的转移在路径内；$i=j$ 时路径为空，恢复 $\mathbf k_i^\top\mathbf q_i$。这两个端点决定分块公式中的严格下三角与非严格下三角掩码。（Sec. 2，PDF pp. 2–3） ### 2.2 Householder-like 转移为什么有效 将任意向量分为 $\mathbf z=\mathbf z_\perp+\alpha\mathbf w_t$，可直接得到 $$ \mathbf H_t\mathbf z=\mathbf z_\perp+(1-\beta_t)\alpha\mathbf w_t. $$ 也就是每次只改变一个方向，其余方向保持不动。核心特征值为 $1-\beta_t$，其余为 1。 | 强度 | 沿 $\mathbf w_t$ 的作用 | 含义 | |---|---|---| | $0<\beta_t<1$ | 正向收缩 | 减弱旧信息的一部分 | | $\beta_t=1$ | 投影为零 | 可以擦除该方向，转移不可逆 | | $1<\beta_t<2$ | 变号并收缩 | 能表达普通正衰减不具备的状态变化 | | $\beta_t=2$ | 精确反射 | 理论构造采用的端点；有限实数输入的 sigmoid 参数化不精确达到它 | 在精确运算和单位范数前提下，单步谱范数不超过 1。但不同 $\mathbf w_t$ 对应的转移通常不交换，因此它们的累计效果能够记录事件次序。原文 Related Work 将这些变换概括为“non-invertible”；准确地说，单步在 $\beta_t=1$ 时奇异，其他 $\beta_t\in(0,2)$ 通常可逆。方法允许擦除，而不是每一步都必须擦除。 **教学例子**：令 $\mathbf w=(\mathbf e_1-\mathbf e_2)/\sqrt2$，$\beta=2$，则 $$ \mathbf I-2\mathbf w\mathbf w^\top= \begin{bmatrix}0&1\\1&0\end{bmatrix}. $$ 一次反射即可交换两个坐标；把这样的矩阵连乘，就得到对连续交换操作的追踪。另一方面，$\mathbf w=\mathbf e_1,\beta=1$ 会擦除第一个坐标，适合解释“新写入阻断旧记录”的机制。（参数化：Sec. 2.2，PDF p. 2；交换构造：Appendix A，p. 17） ### 2.3 与线性 RNN 的关系：共享路径，改变读取权重 考虑论文使用的线性递归形式 $$ \mathbf S_t=\mathbf S_{t-1}\mathbf H_t+\mathbf v_t\mathbf k_t^\top, \qquad \mathbf o_t=\mathbf S_t\mathbf q_t, \qquad \mathbf S_0=\mathbf0. $$ 展开之后，历史 value 的系数为 $$ c_{tj}=\mathbf k_j^\top\mathbf F_{j+1:t}\mathbf q_t. $$ 线性 RNN 直接用 $c_{tj}$ 加权，PaTH 则使用 $\exp(c_{tj})/\sum_r\exp(c_{tr})$。这样，PaTH 引入了递归网络的转移代数，同时保留对各个历史 value 的 softmax 选择。它仍需显式历史 KV，不能沿用上述 $d\times d$ 状态就精确算出一般的 softmax 输出。（Sec. 2.2，PDF p. 3） ### 2.4 理论构造抓住了什么 **Theorem 2.1** 声明：一层、两头、$\log n$ 数值精度的 PaTH Transformer 可以解一个在 $\mathsf{AC}^0$ 归约下的 $\mathsf{NC}^1$ 完全问题。Appendix A 用五个元素的迭代交换是否构成恒等置换来实现它。（PDF pp. 3、17–18） 证明的关键链条是：每个交换 token 对应一次上述反射；累计乘积表示最终置换 $\pi$；设计起始 token 的 key 和末尾 query，使其 logit 为 $$ s_0=n\left(\sum_{r=1}^{5}r\pi(r)-54.5\right). $$ 恒等置换时总和为 55，$s_0=n/2$；非恒等置换时整数总和至多为 54，故 $s_0\le-n/2$。其他 token 的 logit 均设为零，于是第一头对起始 token 的注意力为 $e^{s_0}/(e^{s_0}+n)$。第二头输出均匀注意力参照 $1/(n+1)$，比较两者即可判定恒等性。这里使用精确 $\beta=2$ 的理想反射以及依赖 $n$ 的构造，不应直接等同于实际 BF16 训练的参数配置。 **Theorem A.1** 另声明两层 PaTH、$O(\log n)$ 精度可在长度至多 $n$ 的 FFLM 上实现高于 $1-1/n^{100}$ 的准确率。其构造意图是：第一层让 bit 识别紧邻的操作符；第二层在新写入处截断旧写入路径，从而只读取最近一次写入。实证部分则用一层模型取得极低错误率，理论层数与实验层数应分别理解。 附录 p. 19 的具体坐标公式有明显不一致：第一 FFN 用 $h_{10},h_{11}$ 表示 write-0/write-1，第二层 value 与 $\beta$ 却引用 $h_8,h_9$；末尾两个输出位也使用了相同判别式。因此上面的解释保留作者的构造思路，不把这些坐标公式当作可直接执行的实现。 ### 2.5 PaTH-FoX：路径变换与遗忘可以分工 FoX 为每一步生成 $f_t=\sigma(\mathbf u_f^\top\mathbf x_t+b_f)\in(0,1)$，在 logits 中加入 $\sum_{s=j+1}^i\log f_s$。组合后为 $$ A_{ij}\propto \exp\left(\mathbf k_j^\top\mathbf F_{j+1:i}\mathbf q_i +\sum_{s=j+1}^{i}\log f_s\right) =\left(\prod_{s=j+1}^{i}f_s\right) \exp\left(\mathbf k_j^\top\mathbf F_{j+1:i}\mathbf q_i\right). $$ PaTH 改变内容匹配的方向和结构，FoX 直接衰减旧位置的未归一化权重。两者的作用位置不同：$\prod f_s$ 位于指数函数外，不能与“先给 logit 乘一个衰减再取指数”混为一谈。这种分工解释了为何 PaTH 的状态追踪优势与 FoX 的长距离遗忘能力可以互补。（Sec. 2.2，PDF p. 3） ### 2.6 UT 表示：把很多秩一操作组织成矩阵乘法 直接为每个 $(i,j)$ 计算一遍路径乘积，会反复处理相同区间。设 $$ \mathbf W=[\mathbf w_1^\top;\ldots;\mathbf w_L^\top],\quad \mathbf D=\operatorname{diag}(\beta_1,\ldots,\beta_L),\quad \mathbf U=\left(\mathbf I+\operatorname{strictLower}(\mathbf D\mathbf W\mathbf W^\top)\right)^{-1}\mathbf D. $$ $\mathbf U$ 对应原文简写的 $\mathbf T^{-1}$，是一个下三角系数矩阵，并不要求先逐个求 $\mathbf H_t^{-1}$。三角系统和矩阵乘法比许多零散的 rank-one 更新更适合 GPU。 **按本笔记明示的乘法顺序**，正确的两种方向是 $$ \mathbf H_L\cdots\mathbf H_1=\mathbf I-\mathbf W^\top\mathbf U\mathbf W, \qquad \mathbf F_{1:L}=\mathbf H_1\cdots\mathbf H_L =\mathbf I-\mathbf W^\top\mathbf U^\top\mathbf W. $$ 例如两步展开中的交叉项分别为 $\beta_1\beta_2\mathbf w_2(\mathbf w_2^\top\mathbf w_1)\mathbf w_1^\top$ 及其转置；当转移不交换时，转置不能省略。 利用连续区间的三角结构，可以得到原文的全矩阵 logits 形式 $$ \widetilde{\mathbf A} =\operatorname{lower}(\mathbf Q\mathbf K^\top) -\operatorname{lower}(\mathbf Q\mathbf W^\top)\, \mathbf U\, \operatorname{strictLower}(\mathbf W\mathbf K^\top). $$ 第一个 lower 允许转移位置等于 query 位置；strictLower 则使转移严格晚于 key 位置。对标量而言，这一式计算的是 $\mathbf q_i^\top\mathbf H_i\cdots\mathbf H_{j+1}\mathbf k_j$，恰为原始 logit 的转置等值表达。上三角在做 softmax 前仍须设为 $-\infty$；代数中“置零”与概率归一化中的因果屏蔽有不同用途。 原文 p. 4 将下三角 UT 表示与未明示方向的乘积混用，单个区间的左右掩码式也与后面的全矩阵式不一致。一个避免歧义的区间写法是：令 $I=\{a,a+1,\ldots,b\}$，$\mathbf W_I$ 为这些行组成的子矩阵，则前向乘积为 $\mathbf I-\mathbf W_I^\top\mathbf U[I,I]^\top\mathbf W_I$；这里连续主子块的三角求解结构保证等式成立。以上方向说明和区间表达是根据定义整理的推导。（Sec. 3.1–3.2，PDF p. 4） ### 2.7 分块训练：当前块精确计算，历史块由右向左扫描 全序列三角求解在原文的常规复杂度计数下需要 $O(L^3)$，因此实际算法仅在长度为 $B$ 的块内建立 $\mathbf U_b$。每块预处理三类量： $$ \overleftarrow{\mathbf Q}_b =\mathbf Q_b-\operatorname{lower}(\mathbf Q_b\mathbf W_b^\top)\mathbf U_b\mathbf W_b, $$ $$ \overrightarrow{\mathbf K}_b =\mathbf K_b- \left(\mathbf U_b\operatorname{strictLower}(\mathbf W_b\mathbf K_b^\top)\right)^\top\mathbf W_b, $$ $$ \mathbf F_b=\prod_{t\ \text{in block }b}^{\text{时间从早到晚}}\mathbf H_t =\mathbf I-\mathbf W_b^\top\mathbf U_b^\top\mathbf W_b. $$ 前两项把 token 内部的路径分别折算到块的左、右边界；$\mathbf F_b$ 表示穿过整块的转移。固定 query 块 $b$ 后，算法可以理解为： ```text 用局部全矩阵公式计算对角块，并纳入 online softmax Qwork ← Qleft[b] for c = b−1, b−2, …, 0: logits ← Qwork · Kright[c]^T 更新 online softmax，累积对 V[c] 的加权输出 Qwork ← Qwork · F[c]^T 归一化输出并写回显存 ``` 先计算当前历史块的贡献，再穿过该块继续向左，恰好避免将当前 key 之前的操作错误计入路径。不同 query 块可以并行，内部扫描使用 SRAM 中的小矩阵，不把完整 $L\times L$ attention 写回 HBM。（Sec. 3.3，PDF p. 5） **复杂度按块数展开**：每对块的工作是 $O(B^2d+Bd^2)$，约有 $(L/B)^2$ 对，因此应为 $$ O\left(L^2d+\frac{L^2d^2}{B}\right). $$ 局部三角求解及边界变换还需 $O(LB^2+LBd)$；若显式形成每块 $d\times d$ 转移，再计入 $O(Ld^2)$。当 $B\approx d$ 时，主导计算仍为 $O(L^2d)$，但常数和额外存储增加。 原文 p. 6 写成 $O(L^2d+Ld^2/B)$，第二项少了一个 $L$；p. 5 的块转移定义又漏写 $\mathbf I-$，并需与乘积方向统一。上述式子依据逐块操作重新整理，保留了作者关于“序列长度仍为二次复杂度”的结论。 ### 2.8 解码：持续改写历史 key 到达新位置 $t$ 时，对所有历史 key 进行 $$ \mathbf k_j^{(t)} =\mathbf H_t\mathbf k_j^{(t-1)} =\mathbf k_j^{(t-1)}-\beta_t\mathbf w_t \left(\mathbf w_t^\top\mathbf k_j^{(t-1)}\right),\quad j