算法与理论计算机2021arxiv.org
不做乘法的矩阵乘法
Multiplying Matrices Without Multiplying
进阶 · 约 60 分钟读完前置知识：矩阵乘法与 GEMM、K-means 聚类、乘积量化
导读
这篇论文提出 MADDNESS 方法，用学习到的哈希查找表替代矩阵乘法中的乘法运算，实现近似矩阵乘法而无需真正做乘法。作者展示了在小规模实验（如 CIFAR-10/100）上的效果，作为深度神经网络推理加速的一种新思路。
HN 关注点：是因为用乘积量化/哈希查找替代矩阵乘法这一反直觉思路，可能影响 AI 推理加速和硬件设计。
HN 评论精选
这几条评论里：支持 1 质疑 1 补充 1 亲历 1
补充用点积即相似度的视角解释了该方法的直觉原理
矩阵乘法的每个元素本质上是两个向量的点积，而点积衡量的是向量相似度。不难想象可以学习训练向量的 K-means 聚类代表，运行时用高效哈希方案找到相似向量，通过查表得到近似的点积相似度分数——完全不需要做乘法。虽然我简化了很多细节，但这是个有用的心智模型。非常巧妙。
cs702查看英文原文
Every element of a matrix multiplication is a dot-product of two vectors. The dot-product of two vectors quantifies their similarity -- in fact, we call it "dot-product similarity" in a nearest-neighbors context: If the dot product > 0, the vectors point in similar directions; if < 0, the two vectors point in dissimilar directions; if = 0, the two vectors are orthogonal. It's not too hard to imagine that it might be possible to learn representative K-means clusters of training vectors and then, at run-time, find similar vectors using an efficient hashing scheme and do the equivalent of a table lookup to get the approximate dot-product similarity scores -- without having to perform any multiplications. This isn't quite correct (I'm oversimplifying and ignoring many important details), but I think it's a helpful mental image. Very clever stuff.
亲历作者本人现身答疑，并透露已有硬件厂商关注
一作在此，欢迎提问！也欢迎发邮件到论文中的地址深入讨论，比如已经有硬件领域的人在考虑扩展这项工作。
ffast-math查看英文原文
Primary author here. Happy to answer questions! Also, feel free to email me at the address in the paper if you're interested in talking about it in more detail. E.g., I've already heard from some hardware folks looking at expanding on this work.
质疑质疑实验规模小、未测主流网络和 TensorCore 硬件，实用价值待验证
有趣的工作，但有待解决的问题：1. 只在小规模实验（CIFAR-10/100）上覆盖了 GEMM 部分，未涉及卷积，也未覆盖 Transformer/BERT 等主流网络中的 GEMM。2. 作为近似方法存在精度损失风险，对训练加速吸引力不大，可能更适合作为推理加速的补充手段。3. 没有在带 TensorCore 的 GPU 上评估——现代 AI 加速器本身就为 GEMM 设计了硬件加速，这种近似方法的附加价值存疑。
yangjunpro查看英文原文
An interesting work, with some to-be-addressed questions: 1.The paper only covers the GEMM part with small-scale experiments(CIFAR-10/100), not covering convolution, not covering GEMM part in more popular network such as Transformer/BERT, etc. 2. It is still an approximating method, meaning potential accuracy loss. So I think this method is less attractive to training acceleration scenario, maybe potentially as a complementing methods for inference acceleration. 3. No results evaluated in GPU with TensorCore equipment. I am a little bit curious, since modern AI accelerator(including NV GPU) all incorporate TensorCore which by-design supports GEMM acceleration, what is the add-on value brought by the approximating method mentioned in this paper.
支持指出方法源自乘积量化，并认为在容忍近似的场景中很有前景
MADDNESS 这个名字很贴切：用哈希查找替代矩阵乘法（警告：过度简化的说法）。这是乘积量化（PQ）的一个有趣应用，PQ 本身通常也需要学习（一般是 K-means）。考虑到神经网络已经经受住了许多近似（低精度、剪枝），且很多应用本身对精度要求就是主观的（图像处理、推荐系统），我认为这在很多场景会非常有用。
esjeon查看英文原文
> MADDNESS I think this name really fits well to the concept. Replacing matrix-multiplication with some hash-lookups! (warning: an overly simplified statement) This is a really interesting application of PQ(product quantization), which itself also requires learning (usually K-means). Paper: https://lear.inrialpes.fr/pubs/2011/JDS11/jegou_searching_with_quantization.pdf Considering that ANN has survived through many approximations (e.g. lower precision, pruning), and that many ANN applications are anyway subjective (e.g. image processing, recommendation), I think this can be highly useful in many cases.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2021Hacker News 讨论帖235 分 · 122 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选