🤖 machine learning

LAPLEX: The FFT of Learnable Laplace Kernels

LAPLEX 引入了一类精确且可训练的拉普拉斯核算子，其实现类似快速傅里叶变换的扩展性，从而在无需稠密矩阵存储成本的情况下实现数据自适应的全局交互与高维协方差建模，有效将表达能力与内存需求解耦。

原作者： Łukasz Struski, Hanna Blazhko, Piotr Kubaty, Jacek Tabor

发布于 2026-05-26

📖 1 分钟阅读☕ 轻松阅读

原作者： Łukasz Struski, Hanna Blazhko, Piotr Kubaty, Jacek Tabor

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

想象一下，你正在试图整理一个拥有数十亿本书籍的庞大图书馆。在现代人工智能的世界里，“书籍”只是数字（数据点），而“整理”意味着执行复杂的数学运算以寻找模式。

通常，当人工智能试图在大规模上执行此操作时，它会面临一个令人沮丧的选择：

僵化的图书管理员（固定几何结构）： 就像标准的图书馆目录一样，它快速且精确，但书架是固定的。你无法根据搜索内容将书籍移动到更好的位置。（这就像FFT或傅里叶变换）。
灵活但沉重的图书管理员（稠密参数）： 这位图书管理员可以随意重新排列书架以完美契合书籍，但为此，他们需要巨大的仓库来存储每一本书的指令。如果图书馆变得太大，仓库就会空间不足，导致系统崩溃。（这就是标准的稠密矩阵）。
近似图书管理员（低秩/草图）： 这位图书管理员试图通过只记住书籍的“总体氛围”或使用随机猜测游戏来节省空间。它速度快且能放入仓库，但会丢失精确细节，无法学习最佳的排列方式。

LAPLEX 是一种新型图书管理员，打破了这种权衡。它声称是“金发姑娘”式的解决方案：它是精确的，它是可训练的（它可以学习最佳排列），并且它是轻量级的（它不需要巨大的仓库）。

以下是它的工作原理，使用简单的类比：

1. 秘密：学习“坐标”而非“地图”

想象你有一张包含数百万条街道的城市巨幅地图。

旧方法： 为了知道每对街道之间的距离，你需要为每一对街道写下一个数字。对于拥有 100 万条街道的城市，这意味着一万亿个数字。你无法存储这么多。
LAPLEX 方法： LAPLEX 不是写下每一个距离，而是只写下一份“锚点”列表（如主要地标）。然后，它利用一个巧妙的数学规则（拉普拉斯核）来根据任意两点与这些地标的接近程度，计算它们之间的距离。

由于规则如此简单，LAPLEX 不需要存储那一万亿个数字。它只需要存储地标列表。但这里有个神奇之处：它可以学习将这些地标放在哪里。 如果数据表明“街道 A"和“街道 B"经常相关，LAPLEX 就会学习移动其地标，使 A 和 B 在其内部逻辑中彼此靠近。

2. “扫描”技巧：无需繁重劳动即可进行数学运算

该论文声称，尽管 LAPLEX 表现得像一张巨大的稠密地图，但它能以极快的速度进行数学运算。

把它想象成工厂里的传送带。

稠密方式： 为了计算一个项目的结果，你必须停下来，查看仓库中的每一个其他项目，并进行计算。随着仓库的扩大，这会变得越来越慢。
LAPLEX 方式： 它首先将传送带上的物品排序。然后，它使用一种“扫描”技术。想象一名工人沿着生产线行走，他只需要记住到目前为止所看到的运行总计。由于拉普拉斯核的数学是指数级的（随着距离增加，数值变得非常小），这名工人只需查看“前缀”（之前的内容）和“后缀”（之后的内容），就能计算出整条生产线的最终结果。

这使得 LAPLEX 能够在现代计算机上处理高达10 亿（10⁹）的维度，而在该规模下，“稠密”方法会立即耗尽内存。

3. 它实际做了什么（实验）

该论文在三种特定场景中测试了这位“图书管理员”，以证明其有效性：

“扁平化图像”测试： 他们获取高分辨率照片（数百万像素），将其展平为单行长数字序列（忽略二维网格），并尝试对数据进行建模。
- 结果： 标准的“低秩”模型（近似图书管理员）未能识别出原始照片中相邻像素应该相关；它只看到了噪声。然而，LAPLEX 学会了以保留图像形状（如海滩或棕榈树）的方式放置其“地标”，即使它从未将图像视为网格。它在未被告知网格概念的情况下，学会了数据的几何结构。
“分类头”测试： 他们尝试用 LAPLEX 替换神经网络的最后一层（决定“这是猫还是狗？”的部分）。
- 结果： 仅使用极少量的参数（约为通常大小的 1-5%），LAPLEX 的表现几乎与庞大的全尺寸网络一样好。它比标准的“低秩”捷径更好地学会了路由信息。
“速度”测试： 他们比较了其在超级计算机（GPU）上的运行速度。
- 结果： 在大型数据集上，LAPLEX 的前向传播速度比标准方法快约65 倍，训练速度（前向 + 反向）快430 倍。它还使用了少 100 倍的内存。

4. 为什么这很重要（简单来说）

该论文认为，长期以来，我们一直认为必须在速度/大小与准确性/灵活性之间做出选择。

如果你想要速度，就必须使用固定规则（如 FFT）或随机猜测。
如果你想要学习最佳规则，就必须使用如此多的内存，以至于无法在大数据上运行。

LAPLEX 说：“你不必做出选择。”通过将数据的坐标视为可学习变量而非固定槽位，它创建了一个具有以下特性的系统：

精确： 它不猜测；它计算真实的数学。
可训练： 它适应其看到的特定数据。
高效： 它能适应原本会导致崩溃的硬件。

总结类比

想象你正在试图组织一个盛大的派对，数百万名客人需要找到他们的座位。

稠密矩阵： 你打印一张巨大的座位表，将每位客人的名字列在每位其他客人的名字旁边。这很完美，但纸张堆太重，无法搬运。
低秩/草图： 你只是随机告诉客人坐在"A 区”或"B 区”。这很轻便，但座位安排混乱且低效。
LAPLEX： 你给客人几个“磁性锚点”（如 VIP 桌）。你教导客人根据他们与这些锚点的接近程度来就座。锚点在派对期间会移动以找到最佳位置。你不需要巨大的图表；你只需要锚点列表。客人瞬间找到座位，安排完美，你可以将整个计划装进口袋。

该论文得出结论，这种方法使人工智能能够在以前不可能的规模上处理“稠密”交互（即万物互联），同时不牺牲从数据中学习的能力。

技术摘要：LAPLEX——可学习拉普拉斯核的快速傅里叶变换

1. 问题陈述

现代机器学习系统日益运行在环境维度达到数百万甚至数十亿的领域。在这些高维设置中，瓶颈通常是线性操作（如应用稠密矩阵、计算 Gram 算子以及混合特征）的时钟成本和内存占用。

现有的线性代数扩展方法通常以牺牲以下三个理想属性之一为代价：精确性、可学习性或近线性扩展性。

低秩方法（例如 LoRA）保留了稠密的、基于基的交互，但由于必须存储输入基的系数，即使输出秩被压缩，其内存占用仍为 $O(nk)$。
随机草图和随机特征（例如 CountSketch、随机傅里叶特征）提供了可扩展性，但作用于固定的索引或近似核，以牺牲精确性换取效率。它们无法适应坐标的匹配方式。
稀疏方法可能破坏硬件规律性，且难以进行端到端训练。
经典快速变换（例如 FFT）是精确且廉价的（ $O(n \log n)$ ），但固定于特定的网格几何结构，无法学习坐标系。

识别出的核心限制是基依赖性：标准算子直接参数化矩阵值，需要与输入维度成比例的存储。本文主张转向索引级算子，使其能够在不存储稠密矩阵的情况下学习输入几何结构本身。

2. 方法论：LAPLEX

作者引入了LAPLEX，这是一类基于拉普拉斯核的精确、可训练算子。LAPLEX 层由可学习的坐标锚点隐式定义，而非显式的矩阵权重。

2.1 算子

核心原语是由两组可学习锚点 $a \in \mathbb{R}^n$ 和 $b \in \mathbb{R}^k$ 定义的拉普拉斯核矩阵：
$\text{LAPLEX}(a, b)_{ij} = \exp(-|a_i - b_j|)$
在自然极限机制（温度 $t \to 0$ ）下，该算子编码了坐标集的所有排列。通过添加相位参数 $\phi, \psi$ ，该算子可扩展为：
$\text{LAPLEX}(a, \phi; b, \psi)_{jk} = \exp(-|a_j - b_k|) \cdot \cos(\phi_j - \psi_k)$
这使得该算子能够作为稠密、可训练的矩阵运行，同时仅使用 $O(n)$ 个参数（即锚点）。

2.2 精确扫描代数

关键的算法贡献是一种精确的、完全并行的 $O(n \log n)$ 算法，用于矩阵 - 向量和 Gram 乘积，且从不实例化稠密矩阵。

对称情况 ( $a=b$ )：在对锚点排序后，核矩阵分解为下三角和上三角部分。每一部分都可以通过前缀扫描和后缀扫描递归来计算。例如，下三角乘积 $y_i = \sum_{j \le i} \exp(a_j - a_i)x_j$ 满足递推关系 $y_{i+1} = x_{i+1} + \exp(a_i - a_{i+1})y_i$ ，该关系可在 $O(n)$ 工作量和 $O(\log n)$ 并行深度内求值。
一般情况 ( $a \neq b$ )：该算法将来自 $b$ -锚点的贡献聚合到由排序后的 $a$ -锚点定义的区间中。局部贡献被汇总为向量 $u$ 和 $v$ ，随后利用对称扫描原语进行全局传播。
Gram 算子：相同的排序结构使得加权 Gram 矩阵 $M = A \text{diag}(D) A^\top$ 的精确计算成为可能，时间复杂度为 $O(n^2 + k \log n)$ ，避免了朴素的 $O(n^2 k)$ 成本。这对于二阶优化和核方法至关重要。

2.3 表达能力与极限

本文确立了 LAPLEX 是一个连续族，插值于不同的算子类之间：

零温极限：当温度参数趋近于零时，平滑核收敛为离散相等路由矩阵，恢复了CountSketch和任意排列。
通用性：结合对角缩放和稀疏复制，该族对于任意矩形稠密矩阵是通用的。
与 FFT 的关系：如果锚点被冻结为均匀网格，LAPLEX 变为 Toeplitz 矩阵，算法简化为Toeplitz-FFT。如果核被有限谱展开替代，则变为随机傅里叶特征 (RFF)。LAPLEX 保持了相对于锚点的精确性和可微性，而 RFF 由于拉普拉斯核的重尾柯西谱密度，遭受无界梯度方差的影响。

3. 主要贡献

基依赖性的识别：本文提出了索引级、感知排列的算子作为低秩方法的原理性替代方案。低秩方法无法摆脱 $O(nk)$ 的内存占用，因为它们没有压缩输入基。
可学习几何：它证明了拉普拉斯核矩阵在自然极限机制下编码了所有坐标排列，同时仅使用 $O(n)$ 个参数。
精确、可扩展的算法：作者提供了一种精确的、完全并行的 $O(n \log n)$ 算法，用于矩阵 - 向量和 Gram 乘积，使用 $O(n)$ 内存。这使得在现代 GPU 上无需实例化矩阵即可处理高达 $10^9$ 的维度。
实证验证：本文表明，LAPLEX 在保持 FFT 类扩展性的同时，能够作为即插即用的结构化层高效运行。它在内存和速度上优于稠密基线，在准确性和梯度稳定性上优于低秩和随机特征基线。

4. 实验结果

4.1 扩展性与性能

GPU 扩展：在 NVIDIA H100 和 RTX 2080 上，LAPLEX 平滑扩展至 $n = 2^{20}$ （约 100 万个元素），而稠密基线在 $n = 2^{14}$ 时因内存不足 (OOM) 而失败。
速度：在两种方法都能运行的最大尺寸 ( $n=2^{14}$ ) 下，与前向传播相比，LAPLEX 快约 65 倍；与前向 + 反向传播相比，快约 430 倍。
内存：LAPLEX 的峰值内存使用量比稠密基线少约 100 倍。
数值精度：尽管在 float32 下运行，LAPLEX 相对于 float64 参考值的相对误差低于稠密 float32 矩阵乘法和 Toeplitz-FFT。这归因于扫描算法能够将指数缩放因子与尾数保持分离，从而避免了稠密求和中 $O(n \epsilon)$ 的误差累积。

4.2 高维密度建模

作者使用精确 Gram 算子在展平的 DIV2K 图像（维度 $3 \cdot 10^6$ ）上训练了高斯密度模型。

设置：将 LAPLEX 因子（秩 1000，约 1400 万参数）与稠密低秩基线（秩 4，约 1500 万参数）进行比较。
结果：稠密基线由于秩不足而退化为均匀噪声。尽管 LAPLEX 模型在没有任何卷积偏置的情况下操作于展平向量，但它学习到了连贯的空间颜色结构（连续区域、轮廓）。测试对数似然比稠密基线高 4.5 倍。

4.3 结构化投影与分类

ImageNet10 投影：在冻结投影设置中（将展平的 150,528 维图像投影到 $m \in \{25, \dots, 1000\}$ ），LAPLEX 比 CountSketch 和随机投影更稳定，并在较大的 $m$ 值下成为最佳表现者。
可训练头：当用作 Swin-T 和 MaxViT-T 的分类头时，LAPLEX 在相同输出维度下匹配或超过了无约束稠密投影的准确性，同时使用 $\Theta(m+d)$ 参数而非 $\Theta(md)$ 。在低秩情况下，LAPLEX 显著优于低秩分解（LoRA 风格）。

5. 意义与主张

本文主张LAPLEX 将表达能力与存储成本分离开来。它表现得像稠密可训练矩阵，但通过一小组结构化参数（锚点）进行表示和应用。

表达能力与存储的分离：可以在不存储稠密矩阵的情况下学习稠密几何结构。这使得在普通稠密层不可行的领域实现数据自适应的全局交互成为可能。
精确性与近似性：与随机傅里叶特征或 Nyström 方法不同，LAPLEX 提供精确的核应用和 Gram 计算。它避免了随机特征的价值/梯度权衡，特别是由拉普拉斯核的柯西谱密度引起的锚点梯度的无界方差。
可学习快速变换：这项工作证明快速变换不必局限于固定的坐标系。通过可学习的拉普拉斯锚点参数化稠密算子，几何结构本身变成了一个可微参数。

6. 局限性

作者承认以下局限性：

维度：当前的构造使用一维拉普拉斯锚点和基于排序的算法。将这种精确性扩展到更高维的锚点几何结构和更丰富的核是一个开放的数学方向。
系统成熟度：该实现展示了算法机制，但大规模注意力块、优化器和生成模型将需要专门的核和仔细的结构设计。
范围：该方法目前仅限于拉普拉斯核及其特定的基于扫描的分解。

总之，LAPLEX 为低秩和随机化方法提供了一种原理性替代方案，通过将参数化矩阵转变为参数化索引交互，实现了高维领域中的精确、可学习和可扩展的线性代数。