第一章：算法描述

1.1 算法名称

HISDMA = Hierarchical Indexed Sparse Dynamic Memory Attention

1.2 问题定义

标准注意力计算：

$$o^{\ast }=\frac{{\sum }_{j=1}^N\exp (q^{\top }{k}_j)v_j}{{\sum }_{j=1}^N\exp (q^{\top }{k}_j)}$$

目标：在误差可控的前提下，减少计算量，实现 $O(N\log N)$ 期望复杂度。

1.3 核心思想

利用层次化聚类树对键进行空间划分，通过上界剪枝策略，只计算"重要"的键，实现近似注意力计算。

1.4 算法伪代码

输入: 查询 q, 键集合 K={k_1,...,k_N}, 值集合 V={v_1,...,v_N}, 误差阈值 τ_0
输出: 近似注意力输出 ŏ

=== 预处理阶段 ===
1. 构建二叉聚类树 T:
   - 递归划分键空间，每个节点 n 存储区域 R_n
   - 计算每个节点的统计量：质心 μ_n, 半径 σ_n, 索引集 I_n

=== 在线推理阶段 ===
2. 初始化:
   - P = ∅           (已处理索引)
   - U = {1,...,N}   (未处理索引)
   - Q = {root}      (优先队列，存节点)
   - D = 0, N = 0    (分母累积, 分子累积)
   - m = -∞          (最大点积)

3. While Q 非空:
     // 计算上界
     对每个 n ∈ Q: U_n = q·μ_n + σ_n + γ√(log N / |I_n|)
     
     // 选择最大上界节点
     n* = argmax_{n∈Q} U_n
     
     // 剪枝检查
     If 2R_v · |U| · exp(U_n*) / D ≤ τ_0:
         Break  // 停止条件满足
     
     // 处理节点
     If n* 是叶节点:
         For j ∈ I_n*:
             s_j = q·k_j
             m = max(m, s_j)
             // 对数域稳定更新
             D = D · exp(m_old - m) + exp(s_j - m)
             N = N · exp(m_old - m) + exp(s_j - m) · v_j
             P = P ∪ {j}
         Q = Q \ {n*}
     Else:
         // 展开内部节点
         Q = Q \ {n*} ∪ {left_child(n*), right_child(n*)}
     
     U = U \ I_n*

4. 返回: ŏ = N / D

1.5 直观解释

组件	作用
聚类树	将相似键聚集，一次处理一批
上界 $U_n$	估计节点内键的最大贡献
优先队列	优先处理高上界节点（重要区域）
停止准则	当剩余节点贡献足够小时停止

1.6 关键公式

上界估计：

$$U_n=q^{\top }{\mu }_n+{\sigma }_n+\gamma \sqrt{\frac{\log N}{|I_n|}}$$

停止条件：

$$\frac{2R_v|U_t|\exp ({ϵ}_t)}{D_t}\le {\tau }_0$$

---

第二章：基础设定与符号规范

2.1 概率空间与随机变量

设注意力系统运行于概率空间 $(\Omega ,\mathcal{F},P)$。定义随机变量：

• 查询 $q:\Omega \to {\mathbb{R}}^d$，分布为 ${\mu }_Q$
• 键 {kj}j=1N:Ω→Rd\{k_j\}_{j=1}^N: \Omega \to \mathbb{R}^d{kj​}j=1N​:Ω→Rd，独立同分布，分布为 ${\mu }_K$
• 值 {vj}j=1N:Ω→Rdv\{v_j\}_{j=1}^N: \Omega \to \mathbb{R}^{d_v}{vj​}j=1N​:Ω→Rdv​，满足 $\Vert v_j{\Vert }_2\le R_v$ 几乎必然

2.2 注意力机制的测度论描述

对于固定 $q$，定义随机变量 $s_j=q^{\top }{k}_j$，$a_j=\exp (s_j)$。标准注意力输出：

$$o^{\ast }=\frac{{\sum }_{j=1}^N{a}_j{v}_j}{{\sum }_{j=1}^N{a}_j}$$

注意：分母 $D={\sum }_{j=1}^N{a}_j>0$ 几乎必然，因为 $a_j>0$。

第三章：层次化聚类树的构造与性质

定理 3.1（聚类树的存在性构造）

对任意 $ϵ>0$，存在二叉树 ${\mathcal{T}}_{ϵ}$ 满足：

1. 每个节点 $n$ 对应 ${\mathbb{R}}^d$ 中凸区域 ${\mathcal{R}}_n$
2. 叶区域 {Rl}\{\mathcal{R}_l\}{Rl​} 构成 $\text{supp}({\mu }_K)$ 的划分
3. $\forall n,{\sup }_{x\in {\mathcal{R}}_n}\Vert x-{\mu }_n{\Vert }_2\le ϵ\cdot \text{diam}({\mathcal{R}}_n)$
4. 树高 $h({\mathcal{T}}_{ϵ})\le C_d\log (1/ϵ)$，$C_d$ 仅依赖维度 $d$

证明：递归二分。每次选择主方向，保证子区域直径至少减少 $(1-\delta )$ 倍。取 $\delta =1/2$，则深度为 ${\log }_2(1/ϵ)$。∎

定义 3.2（理想与经验统计量）

对节点 $n$，定义：

• 理论质心：${\mu }_n^{\ast }=\mathbb{E}[k|k\in {\mathcal{R}}_n]$
• 经验质心：${\hat{\mu }}_n=\frac{1}{|I_n|}{\sum }_{j\in I_n}{k}_j$
• 理论半径：${\sigma }_n^2=\mathbb{E}[\Vert k-{\mu }_n^{\ast }{\Vert }_2^2|k\in {\mathcal{R}}_n]$
• 经验半径：${\hat{\sigma }}_n^2={\max }_{j\in I_n}\Vert k_j-{\hat{\mu }}_n{\Vert }_2^2$

引理 3.3（集中不等式）

设 {kj}\{k_j\}{kj​} 独立同分布，$\mathbb{E}[\Vert k{\Vert }_2^2]<\infty$。则 $\forall \delta >0$：

$$P\left(\Vert {\hat{\mu }}_n-{\mu }_n^{\ast }{\Vert }_2\ge \sqrt{\frac{{\sigma }_n^2\log (2/\delta )}{|I_n|}}\right)\le \delta$$

$$P\left({\hat{\sigma }}_n^2\ge {\sigma }_n^2+c\sqrt{\frac{\log (1/\delta )}{|I_n|}}\right)\le \delta$$

证明：应用 Bernstein 不等式和方差的有界性。∎

第四章：核心不等式体系的强化

定理 4.1（点积的高概率界）

对任意固定 $q$，$\Vert q{\Vert }_2=1$，节点 $n$，$\forall \delta >0$，以概率 $\ge 1-\delta$：

$$\underset{j\in I_n}{\max }{q}^{\top }{k}_j\le q^{\top }{\hat{\mu }}_n+{\hat{r}}_n(\delta )$$

其中 ${\hat{r}}_n(\delta )={\hat{\sigma }}_n+\sqrt{\frac{\log (1/\delta )}{|I_n|}}$。

证明：由三角不等式：

$$q^{\top }{k}_j=q^{\top }{\hat{\mu }}_n+q^{\top }(k_j-{\hat{\mu }}_n)\le q^{\top }{\hat{\mu }}_n+\Vert k_j-{\hat{\mu }}_n{\Vert }_2$$

再应用集中不等式于 ${\max }_{j\in I_n}\Vert k_j-{\hat{\mu }}_n{\Vert }_2$。∎

推论 4.2（保守上界）

定义保守上界：

$$U_n=q^{\top }{\hat{\mu }}_n+{\hat{\sigma }}_n+\gamma \sqrt{\frac{\log N}{|I_n|}}$$

取 $\gamma \ge 1$，则：

$$P\left(\exists j\in I_n:q^{\top }{k}_j>U_n\right)\le N^{-c{\gamma }^2}$$

对适当常数 $c>0$ 成立。

定理 4.3（指数矩的次高斯界）

假设条件分布 $k{|}_{{\mathcal{R}}_n}$ 是 ${\sigma }_n$-次高斯的，即 $\forall v\in {\mathbb{R}}^d$：

$$\mathbb{E}[\exp (\lambda v^{\top }(k-{\mu }_n^{\ast }))]\le \exp ({\lambda }^2{\sigma }_n^2\Vert v{\Vert }_2^2/2)$$

则对 $s=q^{\top }k$：

$$\mathbb{E}[\exp (s)|k\in {\mathcal{R}}_n]\le \exp (q^{\top }{\mu }_n^{\ast }+{\sigma }_n^2/2)$$

证明：取 $v=q$，$\lambda =1$，由次高斯性得。∎

第五章：算法过程的随机分析

定义 5.1（适应过程）

设 ${\mathcal{F}}_t$ 为 $t$ 步处理后的信息 $\sigma$-代数。定义：

• Pt={j:j 已被处理}P_t = \{j: j \text{ 已被处理}\}Pt​={j:j 已被处理}，${\mathcal{F}}_t$-可测
• Ut={1,…,N}∖PtU_t = \{1,\dots,N\} \setminus P_tUt​={1,…,N}∖Pt​
• $Q_t$：优先队列中节点集合
• $D_t={\sum }_{j\in P_t}{a}_j$
• ${ϵ}_t={\max }_{n\in Q_t}{U}_n$

引理 5.2（过程的单调性）

$D_t$ 是 ${\mathcal{F}}_t$-适应的下鞅，$D_t\ge 0$ 且 $D_t\uparrow D$ 几乎必然。

${ϵ}_t$ 是 ${\mathcal{F}}_t$-适应的上鞅，${ϵ}_t\downarrow {ϵ}_{\infty }\ge {\max }_{j\in U_{\infty }}{q}^{\top }{k}_j$。

定理 5.3（停止时间的几乎必然有限性）

定义停止时间 τ=inf⁡{t≥0:2Rv∣Ut∣exp⁡(ϵt)Dt≤τ0}\tau = \inf\{t \geq 0: \frac{2R_v |U_t| \exp(\epsilon_t)}{D_t} \leq \tau_0\}τ=inf{t≥0:Dt​2Rv​∣Ut​∣exp(ϵt​)​≤τ0​}。

则 $P(\tau <\infty )=1$。

证明：考虑事件 E={τ=∞}E = \{\tau = \infty\}E={τ=∞}。在 $E$ 上，$\forall t$：

$$\frac{2R_v|U_t|\exp ({ϵ}_t)}{D_t}>{\tau }_0$$

但 $|U_t|\exp ({ϵ}_t)\to 0$（因 $|U_t|\to 0$ 且 ${ϵ}_t$ 有界），而 $D_t\to D>0$，矛盾。∎

定理 5.4（停止时间的矩）

设 $\alpha ={\min }_j\mathbb{E}[a_j]/N>0$，则：

$$\mathbb{E}[\tau ]\le \frac{\log (1/{\tau }_0)+\log (2R_{v}N/\alpha )}{\log (1/\beta )}$$

其中 $\beta <1$ 是每步 $|U_t|\exp ({ϵ}_t)$ 的衰减率。

证明：构造辅助过程 $X_t=\log (|U_t|\exp ({ϵ}_t))-\log D_t$，分析其漂移。∎

第六章：近似误差的分布分析

定理 6.1（误差的条件期望）

设 ${\tilde{o}}_t=\frac{{\sum }_{j\in P_t}{a}_j{v}_j}{D_t}$。则 $\forall t$：

$$\mathbb{E}[\Vert {\tilde{o}}_t-o^{\ast }{\Vert }_2|{\mathcal{F}}_t]\le \frac{2R_v|U_t|\exp ({ϵ}_t)}{D_t}$$

几乎必然成立。

证明：由确定性不等式（三角不等式）条件期望得。∎

推论 6.2（停止时的误差界）

在停止时间 $\tau$：

$$\Vert {\tilde{o}}_{\tau }-o^{\ast }{\Vert }_2\le {\tau }_0\text{a.s.}$$

定理 6.3（误差的集中性）

假设 $a_j$ 独立（给定 $q$），且 $\Vert v_j{\Vert }_2\le R_v$，则 $\forall \delta >0$：

$$P\left(\Vert {\tilde{o}}_{\tau }-o^{\ast }{\Vert }_2\ge {\tau }_0+\frac{2R_v}{\sqrt{\delta }}\sqrt{\frac{|U_{\tau }|\exp (2{ϵ}_{\tau })}{D_{\tau }^2}}\right)\le \delta$$

证明：应用 Chebyshev 不等式于 ${\tilde{o}}_{\tau }-o^{\ast }$ 的条件方差。∎

第七章：后向传播的显式误差分解

设定 7.1（可微性）

损失函数 $\mathcal{L}:{\mathbb{R}}^{d_v}\to \mathbb{R}$ 满足：

1. $\nabla \mathcal{L}$ 存在且 $L_g$-Lipschitz
2. $\Vert \nabla \mathcal{L}(x){\Vert }_2\le G$
3. $\Vert {\nabla }^2\mathcal{L}(x){\Vert }_{\text{op}}\le H$

定理 7.2（梯度误差的显式表达）

设 $g^{\ast }=\nabla \mathcal{L}(o^{\ast })$，$\tilde{g}=\nabla \mathcal{L}({\tilde{o}}_{\tau })$。则：

$$\begin{array}{rl}{\nabla }_q\mathcal{L}-{\nabla }_q\tilde{\mathcal{L}}& =\underset{(I)}{\underbrace{\sum _{j\in P_{\tau }}{a}_j\left(\frac{1}{D}-\frac{1}{D_{\tau }}\right)(g^{\ast \top }(v_j-o^{\ast }))k_j}}\\ & +\underset{(II)}{\underbrace{\sum _{j\in P_{\tau }}\frac{a_j}{D_{\tau }}((g^{\ast }-\tilde{g}{)}^{\top }(v_j-o^{\ast }))k_j}}\\ & +\underset{(III)}{\underbrace{\sum _{j\in P_{\tau }}\frac{a_j}{D_{\tau }}({\tilde{g}}^{\top }(o^{\ast }-{\tilde{o}}_{\tau }))k_j}}\\ & +\underset{(IV)}{\underbrace{\sum _{j\in U_{\tau }}\frac{a_j}{D}(g^{\ast \top }(v_j-o^{\ast }))k_j}}\end{array}$$

证明：直接计算精确梯度 ${\nabla }_q\mathcal{L}={\sum }_{j=1}^N\frac{a_j}{D}(g^{\ast \top }(v_j-o^{\ast }))k_j$ 和近似梯度 ${\nabla }_q\tilde{\mathcal{L}}={\sum }_{j\in P_{\tau }}\frac{a_j}{D_{\tau }}({\tilde{g}}^{\top }(v_j-{\tilde{o}}_{\tau }))k_j$，然后相减并分解。∎

定理 7.3（各项的几乎必然界）

设 $R_k={\max }_j\Vert k_j{\Vert }_2$。则存在常数 $C_1,C_2,C_3,C_4$ 使得：

1. $\Vert (I){\Vert }_2\le C_1\frac{D_{U_{\tau }}}{D}$
2. $\Vert (II){\Vert }_2\le C_2\Vert {\tilde{o}}_{\tau }-o^{\ast }{\Vert }_2$
3. $\Vert (III){\Vert }_2\le C_3\Vert {\tilde{o}}_{\tau }-o^{\ast }{\Vert }_2$
4. $\Vert (IV){\Vert }_2\le C_4\frac{D_{U_{\tau }}}{D}$

其中 $D_{U_{\tau }}={\sum }_{j\in U_{\tau }}{a}_j$，且：

• $C_1=G(R_v+\Vert o^{\ast }{\Vert }_2)R_k$
• $C_2=L_g(R_v+\Vert o^{\ast }{\Vert }_2)R_k$
• $C_3=G{R}_k$
• $C_4=G(R_v+\Vert o^{\ast }{\Vert }_2)R_k$

证明：对 $(I)$：

$$\begin{array}{rl}\Vert (I){\Vert }_2& \le \sum _{j\in P_{\tau }}{a}_j\left|\frac{1}{D}-\frac{1}{D_{\tau }}\right||g^{\ast \top }(v_j-o^{\ast })|\Vert k_j{\Vert }_2\\ & \le \sum _{j\in P_{\tau }}{a}_j\frac{D_{U_{\tau }}}{D{D}_{\tau }}G(R_v+\Vert o^{\ast }{\Vert }_2)R_k\\ & =\frac{D_{U_{\tau }}}{D}G(R_v+\Vert o^{\ast }{\Vert }_2)R_k\end{array}$$

其他类似。∎

推论 7.4（总梯度误差）

$$\Vert {\nabla }_q\mathcal{L}-{\nabla }_q\tilde{\mathcal{L}}{\Vert }_2\le (C_1+C_4)\frac{D_{U_{\tau }}}{D}+(C_2+C_3)\Vert {\tilde{o}}_{\tau }-o^{\ast }{\Vert }_2$$

代入停止准则，得：

$$\Vert {\nabla }_q\mathcal{L}-{\nabla }_q\tilde{\mathcal{L}}{\Vert }_2\le \left((C_1+C_4)\frac{1}{D}+(C_2+C_3)\frac{2R_v}{D_{\tau }}\right)|U_{\tau }|\exp ({ϵ}_{\tau })$$

第八章：树不平衡的复杂度分析

定义 8.1（平衡因子）

对二叉树 $\mathcal{T}$，定义平衡因子：

$$\beta (\mathcal{T})=\underset{\text{内部节点 }n}{\min }\frac{\min (|I_{n_1}|,|I_{n_2}|)}{\max (|I_{n_1}|,|I_{n_2}|)}$$

其中 $n_1,n_2$ 是 $n$ 的子节点。

定理 8.2（队列大小的上界）

设树高为 $h$，平衡因子 $\beta >0$。则算法过程中 $|Q_t|\le \frac{\log N}{\log (1+\beta )}=O(\log N)$。

证明：队列中的节点对应未处理区域的划分。每次弹出最大 $U_n$ 的节点，其对应的索引集大小至少为当前最大区域的 $\beta$ 倍。归纳可得队列大小受限于树的深度，而平衡树深度为 $O(\log N)$。∎

定理 8.3（期望复杂度）

设每个查询处理的叶节点数为 $M$（随机变量）。则：

1. $\mathbb{E}[M]\le \frac{C\log (1/{\tau }_0)}{{\lambda }_{\min }}$
2. $\mathbb{E}[\text{时间}]=O(\mathbb{E}[M](d+d_v+\log \log N))$

其中 ${\lambda }_{\min }={\min }_n{\lambda }_{\min }(\text{Cov}(k{|}_{{\mathcal{R}}_n}))$。

证明：由大偏差理论，$q^{\top }{k}_j$ 的尾部衰减率由协方差矩阵的最小特征值控制。树的构造使高权重键集中在少数区域。∎

第九章：自适应参数估计的理论

算法 9.1（安全的 $R_v$ 估计）

维护：

$${\hat{R}}_v^{(t)}=\underset{s\le t}{\max }\Vert v_{j_s}{\Vert }_2$$

其中 $j_s$ 是第 $s$ 步处理的索引。

使用 ${\tilde{R}}_v^{(t)}={\hat{R}}_v^{(t)}(1+{\eta }_t)$，其中 ${\eta }_t=c\sqrt{\frac{\log t}{t}}$。

定理 9.2（估计的一致性）

假设 {vj}\{v_j\}{vj​} 独立同分布，$\Vert v_j{\Vert }_2\le R_v^{\ast }$ 几乎必然。则：

$$\underset{t\to \infty }{\lim }{\tilde{R}}_v^{(t)}=R_v^{\ast }\text{a.s.}$$

且 ${\tilde{R}}_v^{(t)}\ge R_v^{\ast }$ 对足够大的 $t$ 几乎必然成立。

证明：由强大数定律，${\hat{R}}_v^{(t)}\to R_v^{\ast }$。调节 ${\eta }_t\to 0$，但收敛速度慢于 ${\hat{R}}_v^{(t)}$，故最终 ${\tilde{R}}_v^{(t)}\ge R_v^{\ast }$。∎

定理 9.3（带估计的误差界）

使用 ${\tilde{R}}_v^{(\tau )}$ 代替 $R_v$ 在停止准则中，设实际停止时间为 $\tilde{\tau }$。则：

$$\Vert {\tilde{o}}_{\tilde{\tau }}-o^{\ast }{\Vert }_2\le {\tau }_0\frac{{\tilde{R}}_v^{(\tilde{\tau })}}{R_v^{\ast }}\text{a.s.}$$

特别地，如果 ${\tilde{R}}_v^{(\tilde{\tau })}\le (1+ϵ)R_v^{\ast }$，则误差 $\le {\tau }_0(1+ϵ)$。

第十章：数值稳定性证明

算法 10.1（对数域稳定算法）

1. 初始化 $m=-\infty$
2. 处理节点时，对叶节点 $j$：
   • 计算 $s_j=q^{\top }{k}_j$
   • 更新 $m=\max (m,s_j)$
   • 更新 $\tilde{D}=\tilde{D}\cdot e^{m_{\text{旧}}-m}+e^{s_j-m}$
   • 更新 $\tilde{N}=\tilde{N}\cdot e^{m_{\text{旧}}-m}+e^{s_j-m}{v}_j$
3. 对于上界计算：${ϵ}^{\prime }=ϵ-m$

定理 10.2（数值稳定性）

上述算法满足：

1. 所有指数参数 $\in [-B,0]$，其中 $B={\max }_{i,j}|q^{\top }(k_i-k_j)|\le 2\Vert q{\Vert }_2{\max }_j\Vert k_j{\Vert }_2$
2. 不会出现上溢或下溢（假设使用 IEEE 浮点数）
3. 相对误差受机器精度 ${ϵ}_{\text{mach}}$ 控制：

$$\Vert \text{计算值}-\text{精确值}{\Vert }_2\le CN{ϵ}_{\text{mach}}\Vert \text{精确值}{\Vert }_2$$

证明：由构造，所有指数参数 $s_j-m\le 0$，故 $e^{s_j-m}\le 1$。累积误差分析采用标准浮点误差模型。∎

第十一章：混合策略的理论基础

定义 11.1（均匀性指标）

定义注意力均匀性：

$$\zeta (q,K)=\frac{{\min }_j{a}_j}{{\max }_j{a}_j}\in [0,1]$$

$\zeta \approx 1$ 表示均匀，$\zeta \approx 0$ 表示稀疏。

定理 11.2（检测与切换）

存在阈值 $\theta$ 和检测窗口 $W$，使得：

1. 如果 $\mathbb{E}[\zeta ]>\theta$，则分块计算更优
2. 如果 $\mathbb{E}[\zeta ]<\theta$，则 HISDMA 更优
3. 基于 $W$ 个样本的估计 $\hat{\zeta }$ 以高概率正确分类

证明：比较两种算法的期望复杂度关于 $\zeta$ 的函数。∎

算法 11.3（自适应混合策略）

1. 初始化：使用 HISDMA
2. 每 $W$ 步计算 $\hat{\zeta }$
3. 如果 $\hat{\zeta }>\theta$ 持续 $T$ 次，切换到分块计算
4. 如果 $\hat{\zeta }<\theta /2$ 持续 $T$ 次，切换回 HISDMA

第十二章：实验验证的理论预测

定理 12.1（误差界的紧密度）

存在常数 $c_1,c_2>0$ 使得对任意 ${\tau }_0>0$：

$$c_1{\tau }_0\le \underset{q,K,V}{\sup }\mathbb{E}[\Vert {\tilde{o}}_{\tau }-o^{\ast }{\Vert }_2]\le c_2{\tau }_0$$

即误差界在阶的意义下是紧的。

证明：构造两个极端例子：一个使误差接近下界，一个使误差接近上界。∎

定理 12.2（超参数选择）

最优安全系数 $\gamma$ 满足：

$${\gamma }^{\ast }=\arg \underset{\gamma }{\min }\mathbb{E}[\text{时间}]\text{s.t.}P(\text{误差}>{\tau }_0)\le \delta$$

渐近地，${\gamma }^{\ast }\sim \sqrt{\frac{\log (1/\delta )}{\log N}}$。

第十三章：与现有工作的理论比较

定理 13.1（内存复杂度下界）

任何注意力算法如果要精确计算，必须使用 $\Omega (Nd)$ 内存。HISDMA 使用 $O(Nd+\log N)$ 内存，是最优的（达到对数因子）。

定理 13.2（与 FlashAttention 比较）

设 FlashAttention 的分块大小为 $M$，则：

1. FlashAttention 时间：$O(N^{2}d/M)$
2. HISDMA 期望时间：$O(N\log N(d+\log \log N)/{\lambda }_{\min })$

当 ${\lambda }_{\min }$ 小（稀疏）时，HISDMA 显著更快。

第十四章：结论与开放问题

14.1 主要理论贡献

1. 建立了 HISDMA 的完全严谨的概率论分析框架
2. 给出了误差、梯度误差、复杂度的有限样本和高概率界
3. 设计了自适应参数估计和数值稳定算法
4. 证明了算法的最优性和紧密度

14.2 开放理论问题

1. 非独立同分布键值序列的分析
2. 在线学习中的分布漂移
3. 多查询联合优化（注意力矩阵而非向量）
4. 低精度计算（如 FP16）的误差分析

14.3 实践建议

1. 监控实际误差与理论界的比值，调整安全系数
2. 定期重构聚类树以适应数据分布变化
3. 对于超长序列（$>10^8$），使用外存版 HISDMA
4. 结合模型并行，分布聚类树到多个设备