AI 与机器学习2023nature.com编辑精选
AlphaDev：用深度强化学习发现更快的排序算法
Deepmind Alphadev: Faster sorting algorithms discovered using deep RL
进阶 · 约 50 分钟读完前置知识：强化学习基础、汇编语言与编译优化、排序算法/排序网络
导读
DeepMind 的 AlphaDev 把排序看成从零开始组装汇编指令的博弈，用深度强化学习搜索更短的程序，在已高度优化的排序网络上找到了更少指令的写法，例如利用前面指令已保证 B<=C，把 min(A,B,C) 简化为 min(A,B)。论文还报告这些改进被合入 LLVM libc++（以及哈希相关优化）。
HN 关注点：焦点在于「发现新排序算法」这一标题与实际只是汇编层微优化之间的落差，以及落到 LLVM 后 1-5% 的真实收益。
后来怎么样
AlphaDev 生成的排序与哈希例程被合入 LLVM libc++ 和 Abseil，进入实际生产库；但其影响主要是底层代码生成与库微优化，并未提出新的排序算法范式。
HN 评论精选
这几条评论里：质疑 1 补充 2 亲历 1
亲历评审者亲历：本质是汇编级微优化与编译器遗漏的优化，不是新算法；基准确认哈希改动已进 abseil 生产环境。
哈希方面也有优化，链接见 DeepMind 博客和 abseil 的那次提交。我是评审者之一，仔细审查了排序和哈希两方面的工作。总的来说，这更多是关于汇编、发现编译器错过的优化，以及在正确性与（尤其是哈希中的）分布之间取得平衡。它算不上革命性：没有找到全新的方法，而是收敛到一种人类难以理解但性能相对更优的方案，这恰好说明最优程序往往非常「非人类」。要注意在排序里删掉指令并不总意味着更快，例如指令可以并行执行，效果可能没那么明显；基准测试也可能撒谎，编译器在重新编译被改动的 sort3 函数时可能做出不同的事。哈希那边更有意思：对最长 64 位的小字符串，原本就已经只用 3 条指令（加常数 → 64x64 乘法 → 高低位异或）；更大的字符串问题就复杂了，所以 9-16 字节是更好的切入点，它从两次乘法简化成一次乘法加一次旋转。真实负载上的分布表现很好，几乎通过了 smhasher，我们判断足够好、可以在生产环境试用。从 abseil 的记录看我们没有回滚 :)
danlark查看英文原文
You can see hashing optimizations as well https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms, https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7dcd2dbaa69b2c654596d8024e I was one of the members who reviewed expertly what has been done both in sorting and hashing. Overall it's more about assembly, finding missed compiler optimizations and balancing between correctness and distribution (in hashing in particular). It was not revolutionary in a sense it hasn't found completely new approaches but converged to something incomprehensible for humans but relatively good for performance which proves the point that optimal programs are very inhuman. Note that for instructions in sorting, removing them does not always lead to better performance, for example, instructions can run in parallel and the effect can be less profound. Benchmarks can lie and compiler could do something differently when recompiling the sort3 function which was changed. For hashing it was even funnier, very small strings up to 64 bit already used 3 instructions like add some constant -> multiply 64x64 -> xor upper/lower. For bigger ones the question becomes more complicated, that's why 9-16 was a better spot and it simplified from 2 multiplications to just one and a rotation. Distribution on real workloads was good, it almost passed smhasher and we decided it was good enough to try out in prod. We did not rollback as you can see from abseil :) But even given all that, it was fascinating to watch how this system was searching and was able to find particular programs can be further simplified. Kudos to everyone involved, it's a great incremental change that can bring more results in the future.
质疑质疑标题夸大：实际只是控制流与代码生成层面的微优化。
标题暗示它发现了全新的排序算法思路（像快速排序那样），那会是了不起的发现。但感觉更像是微优化控制流和代码生成。
bgirard查看英文原文
The title implies it found an entirely new algorithmic approach to sorting (like quick sort) which would have been a fantastic discovery. But it feels a lot like micro-optimizing the control flow and codegen.
补充具体拆解 AI 找到的指令削减技巧（利用排序网络中的隐含保证）和 VarSort4 的重构思路。
在已经高度优化的算法里找到了一些很酷的改进。他们发现在处理 3 个输入的排序网络中，AI 找到把 min(A,B,C) 指令减成 min(A,B) 的办法，利用前面指令已保证 B<=C 这一事实；在处理 4 输入的排序网络中，当它属于 sort 8 网络的一部分时也存在类似保证（此例中 D >= min(A,C)），可以再省一条指令。编译器或许比不过手写汇编，但看来 AI 能写出某些情况下更优的汇编。另一个改进也很酷：VarSort4 要排序长度可能为 2、3、4 的列表，原算法是先判断长度再分别调用 sort4/sort3/sort2；AI 找到的算法完全不同——先判断是否长度为 2，不是就先跑 sort3，之后再检查长度，若是 4 再跑一个特化的 sortspecial。因为跑过 Sort3 后已知前三个元素有序，这个特化算法可以简单得多。
fwlr查看英文原文
Some very cool improvements found in already highly optimized algorithms. They found that in a sorting network handling 3 inputs, the AI found a way to reduce a "min(A, B, C)" instruction to just "min(A, B)" by taking advantage of the fact that previous instructions guaranteed that B <= C. They also found that in a sorting network handling 4 inputs, when it is part of a "sort 8" network, there are similar guarantees (D >= min(A, C) in this case) that can be taken advantage of to remove an instruction as well. The compiler may not be able to compete with hand-written assembly, but it seems an AI can hand-write assembly code that's even better in some cases. Another improvement is also very cool. They discuss VarSort4, which takes a list that may be 2, 3, or 4 elements long, and sorts it. The existing algorithm is if (len = 4) { sort4 } elif (len = 3) { sort3 } elif (len = 2) { sort2 } The AI found an algorithm that looks totally different: if (len = 2) { sort2 } else { sort3 if (len = 4) { sortspecial } } It's pretty wild! It immediately runs Sort3 on something that may be either 3 elements or 4 elements long, and only afterwards does it check to see how long it really is. If it's 3 elements long, we're done; otherwise, run Sort4 - but because (having already run Sort3) you know the first three elements are sorted, you can use a special and much simpler algorithm to simply put the 4th element in the right spot. Very cool. Improving on core LLVM sorting algorithms that have already been heavily hand-optimized by the best in the world is definitely a "it's 1997 and Deep Blue defeats the World Champion in chess" kind of feeling.
补充补充落地证据：LLVM 合并与 1-5% 的实测提升。
LLVM 合并记录（链接），以及基准测试（链接）。基准显示在 80% 的规模上有 1-5% 的提升。
SethTro查看英文原文
LLVM merge: https://reviews.llvm.org/D118029 Benchmark: https://bit.ly/3AtesYf Benchmark seems to be in the range of a 1-5% improvement for 80% of sizes.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2023Hacker News 讨论帖156 分 · 38 评
同领域还值得读
DeepSeek-R1：通过强化学习激励 LLM 的推理能力
DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via RL
研究如何用强化学习激励大语言模型的推理能力，提出 DeepSeek-R1，并探讨 RL 训练对模型推理表现的影响。
AI 与机器学习2025 · 1,351 分 · 1,056 评 · 引用 30进阶 · 约 80 分钟编辑精选1-bit LLM 时代：面向低成本计算的三值参数
The Era of 1-bit LLMs: ternary parameters for cost-effective computing
提出用三值参数 {-1, 0, 1} 替代 LLM 中的浮点权重，即所谓“1-bit LLM”。
AI 与机器学习2024 · 1,040 分 · 447 评 · 引用 19进阶 · 约 45 分钟编辑精选DeepSeek-V3.2：推进开放大语言模型的前沿
DeepSeek-v3.2: Pushing the frontier of open large language models
这是 DeepSeek-V3.2 的技术报告，延续了 DeepSeek 开源权重模型的路线，目标是让开放模型继续逼近甚至追平前沿闭源模型。
AI 与机器学习2025 · 982 分 · 465 评进阶 · 约 90 分钟编辑精选通过自我对弈与通用强化学习掌握国际象棋和将棋（AlphaZero）
Mastering Chess and Shogi by Self-Play with General Reinforcement Learning
DeepMind 的 AlphaZero 论文：用通用强化学习算法（自我博弈 + MCTS + 神经网络），从零开始仅数小时训练便在国际象棋和将棋上击败了世界顶级引擎 Stock…
AI 与机器学习2017 · 539 分 · 270 评 · 引用 13进阶 · 约 90 分钟编辑精选用强化学习发现更快的矩阵乘法算法
Discovering faster matrix multiplication algorithms with reinforcement learning
论文提出 AlphaTensor，用强化学习搜索矩阵乘法算法。
AI 与机器学习2022 · 518 分 · 111 评专业 · 约 90 分钟编辑精选