🤖 AI

Nearly Optimal Attention Coresets

本文证明了针对单位范数键和值存在近乎最优规模的注意力核心集，给出了 $O(\sqrt{d} e^{\rho+o(\rho)}/\varepsilon)$ 的改进上界以及 $\Omega(\sqrt{d} e^{\rho}/\varepsilon)$ 的匹配下界，其性能优于先前结果。

原作者： Edo Liberty, Alexandr Andoni, Eldar Kleiner

发布于 2026-05-08

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Edo Liberty, Alexandr Andoni, Eldar Kleiner

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你正在运营一座庞大的图书馆（即现代人工智能模型），其中每本书都有一个“键”（关于其内容的摘要）和一个“值”（实际内容）。当读者提出一个问题（即“查询”）时，图书管理员会使用一种称为注意力（Attention）的特殊机制来扫描所有书籍，找出最相关的书籍，并将其内容总结为单一答案。

随着图书馆扩充至容纳数百万本书籍，图书管理员的办公桌变得杂乱无章。追踪每一本书的“键”和“值”会占用过多空间并拖慢整体速度。本文的目标是解决以下问题：我们能在仍向读者提供完全相同答案的前提下，从办公桌上扔掉多少本书？

以下是利用简单类比对本文研究发现的分解说明：

1. 问题所在：“挑樱桃者”

作者解释说，你不能随意扔掉书籍。如果读者提出一个非常具体且强烈的问题（例如“帮我找出唯一一本提到某个特定生僻词的书”），图书管理员必须能够完美地隔离出那本特定的书。如果你扔掉了太多书，可能会丢失那本特定的书，从而导致答案错误。

从技术术语来说，如果读者的问题被允许无限“响亮”或强烈，你就根本无法压缩图书馆。你将不得不保留每一本书。

解决方案：本文提出：“让我们约定，读者不会太大声喊叫。”如果我们限制问题的强度上限（即“有界范数”），我们就可以安全地扔掉大部分书籍，仅保留一个精心挑选的微小群体来代表整座图书馆。

2. 魔法技巧：“平衡术”

本文的核心是一种用于挑选保留哪些书籍的数学方法。作者使用了一种称为核心集选择（Coreset Selection）的技术。

想象你在天平上有一大堆重物（即书籍）。你想要移除一半的重量，但保持天平完美平衡，使其不倾斜。

旧方法：之前的方法试图通过逐个查看重量来平衡天平，这不仅缓慢，而且留下了大量额外的“噪声”（误差）。
新方法：作者利用了一个巧妙的数学技巧（基于名为班纳茨基向量平衡的定理）。他们将重量想象成指向不同方向的箭头，并为每本书分配一个“正”或“负”的符号。
- 如果符号选择得当，“正”书和“负”书几乎完全相互抵消。
- 带有“正”符号的书籍将成为你新的、微小的图书馆。
- 由于“负”书抵消了噪声，“正”书仍然能完美代表整个群体。

3. 结果：“近乎最优”的规模

本文证明了两个主要结论：

好消息（上界）：他们找到了一种方法，将图书馆规模缩小至大约 $\sqrt{d} \times e^{\rho}$ 的大小（其中 $d$ 代表书籍的复杂程度， $\rho$ 代表问题可以达到的响亮程度）。这是他们利用该方法在数学上证明可行的最小规模。这比之前任何人发现的规模都要小得多。
坏消息（下界）：他们也证明了规模无法比这更小。如果你试图进一步缩小图书馆，在某些问题上答案不可避免地会出现错误。

这就像打包行李箱。作者找到了一种折叠衣物的方法，使行李箱几乎小到物理极限。他们也证明了，如果不把衣物压坏，就无法折叠得更紧。

4. 为何这很重要

在人工智能领域，“键”和“值”是模型的内存。随着人工智能模型试图记住越来越长的对话（上下文），这种内存变得巨大且昂贵。

本文提供了一个理论保证，即只要问题不过于极端，我们就可以显著压缩这种内存而不损失准确性。它告诉工程师们：“你们不需要保留 100% 的数据。你们可以只保留极小的一部分，从数学上讲，人工智能的表现依然会同样出色。”

一句话总结

作者发现了一种数学上的“折叠技术”，允许人工智能模型将其内存缩小到在不损失准确性的前提下可能的最小规模，并证明了这一新规模几乎就是物理上可能达到的绝对极限。

基于所提供的论文，以下是“近乎最优注意力核心集”的详细技术总结。

问题定义

本文解决了压缩基于 Transformer 的生成模型中键值（KV）缓存的挑战。随着上下文窗口的扩大，KV 缓存的大小成为部署大语言模型的主要瓶颈。作者将注意力核心集选择问题形式化如下：给定 $\mathbb{R}^d$ 中的一组 $n$ 个键值对 $(K, V)$ （其中键和值均为单位范数），目标是找到一个大小为 $S$ 的小子集 $(K', V')$ ，使得对于所有范数有界 $\|q\| \le \rho$ 的查询向量 $q$ ，其注意力输出的近似误差在 $\epsilon$ 以内。

注意力机制定义为：
$\text{Attn}(q, K, V) = \frac{A(q, K, V)}{B(q, K)} = \frac{\sum_i e^{q^T k_i} v_i}{\sum_i e^{q^T k_i}}$

作者指出，如果不限制查询范数 $\rho$ ，则无法实现有损压缩。一个范数足够大的查询可以“精挑细选”单个键值对，迫使草图存储整个数据集以维持准确性。因此，该问题被限制在满足 $\|q\| \le \rho$ 的查询范围内。

方法论

核心技术方法依赖于差异理论（discrepancy theory），特别是利用Banaszczyk 向量平衡定理。该方法包含三个主要组成部分：

通过差异进行折半：作者采用了一种“折半技巧”，即为注意力求和中的各项分配符号 $\sigma_i \in \{-1, 1\}$ 。通过选择符号以最小化差异（即误差项 $E(q) = \sum \sigma_i e^{q^T k_i} v_i$ ），他们可以构建一个包含 $\sigma_i = 1$ 的项的子集 $(K', V')$ 。该子集的大小最多为原始集合的一半，且误差由带符号和的差异所界定。
张量范数平衡：为了界定向量值分子 $A(q, K, V)$ 的误差，作者利用泰勒级数展开指数项 $e^{q^T k_i}$ 。这将问题转化为平衡张量积之和（ $k_i^{\otimes m} \otimes v_i$ ）。他们定义了一个特定的缩放因子 $z(m)$ ，并构造了一个包含这些缩放张量分量的高维向量 $x_i$ 。
凸体构造：他们应用 Banaszczyk 定理证明存在符号 $\sigma_i$ ，使得和 $\sum \sigma_i x_i$ 位于特定的凸体 $K$ 内。该凸体由张量和的对偶范数约束定义。通过仔细选择该凸体的几何形状，他们确保了在所有张量阶数 $m$ 下误差均保持较小。
同时平衡：为了处理完整的注意力机制（包括分子 $A$ 和分母 $B$ ）以及键的居中，作者证明了一个同时平衡引理。这使得他们能够利用同一组符号同时满足多个目标（分子、分母和键居中）的差异界限，且误差界限仅增加一个常数因子。
迭代压缩：折半过程被迭代应用（ $\ell$ 次），直到累积误差在所需的容差 $\epsilon$ 之内。这将数据集大小从 $n$ 减少到 $O(\sqrt{d} e^\zeta / \epsilon)$ 。

主要贡献与结果

1. 上界（定理 1 和 4）：
本文确立了大小为以下形式的注意力核心集的存在性：
$S = O\left( \frac{\sqrt{d}}{\epsilon} e^{\zeta} \right)$
其中 $\zeta = \rho + \frac{1}{2}\log(\rho) + o(\log \log \rho)$ 。
这一结果将先前已知的最佳上界（来自流式注意力近似文献，例如 [30]）提高了约 $\log(n) \cdot e^{\rho - o(\rho)}$ 倍。作者通过外科手术式地修改和简化现有的差异论证，以更紧密地处理向量值函数，从而实现了这一突破。

2. 下界（定理 2 和 7）：
作者证明了一个匹配的下界，表明任何针对单位范数向量且查询范数至多为 $\rho$ 的 $\epsilon$ -核心集，其大小必须为：
$S = \Omega\left( \frac{\sqrt{d}}{\epsilon} e^{\rho} \right)$
该下界是通过对**单向索引（one-way Indexing）**问题进行归约推导得出的，利用球面码构造了难以区分的实例，其中区分比特需要很大的草图大小。

3. 近乎最优性：
比较上界和下界，两者之间的差距为 $O(e^{\frac{1}{2}\log(\rho) + O(\log \log \rho)}) = O(\rho^{1/2 + o(1)})$ 倍。作者声称，这确立了一个“近乎最优”的核心集大小，因为上下界在 $\rho$ 的次多项式因子范围内是匹配的。

意义与主张

本文声称解决了具有误差保证的注意力机制核心集最优大小的问题。

理论突破：它提供了注意力核心集的第一个紧致存在性界限，超越了启发式压缩方法（如聚类或蒸馏），转而基于差异理论提供可证明的保证。
实际意义：结果表明，对于有界范数查询，KV 缓存可以压缩到一个取决于维度 $d$ 、误差容差 $\epsilon$ 和查询范数 $\rho$ 的大小，但与令牌总数 $n$ 无关（一旦 $n$ 足够大）。
局限性：作者指出，如果没有对查询范数 $\rho$ 的约束，则无法进行任何压缩。此外，他们承认上界和下界之间剩余的差距（在最坏情况下约为 $\sqrt{\log n}$ ）可能需要根本不同的方法来消除。

本文并未提出新的实验实现或针对 Transformer 的具体架构变更，而是严格专注于注意力机制数据压缩的理论极限。