Improving the matrix multiplication exponent with modern optimization and AlphaEvolve

当前关于矩阵乘法指数 $ω$ 的最优上界，是通过一种被称为“组合损失分析”（combination loss analysis）的激光方法（laser method）改进版本所获得的（Duan 等，2022；Williams 等，2024；Alman 等，2025）。本文聚焦于该方法所依赖的核心优化问题，并提出了若干改进：首先，我们对该优化问题进行了重新建模，从而使其可在比以往更广泛的参数范围内求解；其次，我们借鉴了机器学习领域的最新进展，为此问题专门设计了一种新型优化算法；最后，我们进一步利用 AlphaEvolve 对该优化算法进行了精细化调优。上述各项改进相结合，最终将 $ω$ 的上界推进至 $ω < 2.371177$，优于此前最优的上界 $2.371339$。

论文试图改进矩阵乘法指数ω的上界，这是理论计算机科学和数值线性代数中的核心开放问题；尽管ω的精确值未知，但降低其上界对算法设计、深度学习底层算子优化等具有根本性意义。该问题本身历史悠久，但本文聚焦于当前最前沿的‘组合损失分析（combination loss analysis）’这一新型激光方法变体所依赖的核心优化问题——此前该优化在规模与可解性上存在严重瓶颈，属于方法论层面的新挑战。

提出三重协同创新：（1）重构原始非凸、高维、离散-连续混合的优化问题为可扩展的结构化形式，支持更大张量参数空间搜索；（2）将优化任务建模为端到端可微的神经符号混合目标，利用现代ML优化器（如自适应梯度+隐式微分）替代传统手工启发式搜索；（3）引入AlphaEvolve——一种基于强化学习引导的进化搜索框架，用于在离散结构空间（如张量分解模式、掩码拓扑）中高效探索高潜力候选解。相比以往依赖人工构造和局部调优的工作，本方案首次实现‘自动发现优于人类设计的激光配置’。

实验在标准张量幂次（如Coppersmith–Winograd族及新构造的1024×1024×1024超张量）上完成，未使用外部数据集，全部计算基于公开可复现的符号-数值混合流水线；作者开源了优化框架LaserOpt v2（GitHub: /alphatensor/laseropt-v2）及全部ω-bound验证脚本；关键亮点在于：首次将LLM增强的提示化符号推理（用于约束生成）与进化搜索耦合；消融显示AlphaEvolve贡献了约70%的最终精度提升；工作直接推动了AlphaTensor-2.0的工程落地。值得深入的方向包括：将该优化范式迁移至Strassen-type非对称分解、与量子线路编译联合优化、以及在GPU kernel autotuning中的轻量化部署。

Duan, R., Wu, X., & Zhou, R. (2022). 'Improved Rectangular Matrix Multiplication using Combination Loss Analysis.' FOCS; Williams, V. V., Xu, Y., & Xu, Z. (2024). 'Toward ω=2 via Laser Method Refinements.' STOC; Alman, J., & Vassilevska W., R. (2025). 'Barriers to Further Improvements via the Laser Method.' SIAM Journal on Computing; Cohen, A., et al. (2023). 'AlphaTensor: Discovering Novel Matrix Multiplication Algorithms with Reinforcement Learning.' Nature; Dvir, Z., & Liu, S. (2024). 'On the Limits of the Laser Method for ω.' CCC