DeepMind 用 AlphaEvolve 把矩陣乘法指數上界降至 2.371177
arXiv · 2026-08-17
Google DeepMind 與哥倫比亞大學、MIT 的學者（Josh Alman、Virginia Vassilevska Williams 等人）於 2026 年 8 月 17 日在 arXiv 發布論文 arXiv:2608.16884 v1，將矩陣乘法複雜度指數 ω 的已知上界從 2.371339 降至2.371177。這項工作延續團隊先前用 AlphaEvolve 尋找矩陣乘法演算法的路線，這次改把同一套「演化編碼代理」用在理論上界的最佳化搜尋上。距離目前公認下界 2 雖仍有差距，但顯示 LLM 驅動的搜尋工具已能直接介入純數學最佳化問題。
背景：組合損失分析與 ω 的意義
矩陣乘法指數 ω 定義兩個 n×n 矩陣相乘所需的最少運算量規模（O(n^ω)），理論下界是 2，但確切數值仍是電腦科學未解問題之一。近年上界的推進多半基於組合損失分析（combination loss analysis）——雷射法（laser method）的一種精煉，由 Duan 等人於 2022 年提出，後續由 Williams、Alman 等人在 2024、2025 年持續改良。該分析最終會化約成一個高維度非凸最佳化問題，搜尋空間越大越有機會壓低 ω，但也越難直接求解。
核心方法：重構問題 + AlphaEvolve 精修
作者團隊採取兩階段作法：先重新表述最佳化問題，讓求解器能處理比過去大得多的搜尋空間；再引入近期機器學習最佳化技巧，並用 AlphaEvolve 對搜尋出的候選解做進一步演化式精修。具體流程包含：
- 將組合損失分析中的張量分解問題改寫為可大規模求解的形式
- 用機器學習最佳化方法在放大後的搜尋空間中尋找候選解
- 以 AlphaEvolve 對候選演算法反覆評估、變異、篩選，收斂到更優數值解
實驗結果與意義
最終結果是把 ω 上界由 2.371339 壓到2.371177，是組合損失分析方法提出以來的最新紀錄。論文本身沒有提供實際矩陣乘法程式的加速比，這仍是純理論複雜度上界的推進；但方法論上證實 AlphaEvolve 這類「LLM + 演化搜尋」代理，能直接處理沒有現成梯度或簡單獎勵訊號的抽象數學最佳化問題，而不只是工程效能調校。
Sentence Transformers 推出多向量（Late Interaction）嵌入模型支援
Hugging Face · 2026-08-18
Hugging Face 於 2026 年 8 月 18 日在官方部落格發布文章，由 Tom Aarsen 與 Antoine Chaffin（及三十多位貢獻者）撰寫，宣布 sentence-transformers 函式庫正式支援多向量（multi-vector / late interaction）嵌入模型。這類模型不再把整段文字壓成單一向量，而是保留「每個 token 一個向量」，並用 MaxSim 運算子在查詢與文件之間逐 token 比對。這是繼 ColBERT 系列研究之後，首次被整合進主流嵌入函式庫的官方 API。
核心機制：MaxSim 與新類別 MultiVectorEncoder
MaxSim 的計算方式是：對查詢中的每個 token，在文件的所有 token 向量中找出相似度最高的那一個，再把所有查詢 token 的最高相似度加總作為最終分數。相較於單向量嵌入把語意壓縮成一個定長向量，這種逐 token 比對能保留更細粒度的匹配資訊，對多重限制條件的查詢、精確符號比對（型號、專有名詞）與長文件特別有利。函式庫新增的 MultiVectorEncoder 類別把查詢與文件編碼分開處理：
from sentence_transformers import MultiVectorEncoder
model = MultiVectorEncoder("lightonai/LateOn")
query_embeddings = model.encode_query(["query text"])
document_embeddings = model.encode_document(["document text"])
實驗結果：檢索品質提升，索引成本上升
在涵蓋 13 個子資料集的 NanoBEIR 評測上，多向量模型 LateOn 平均 NDCG@10 為 0.6868，優於單向量基準 DenseOn 的 0.6764，且在 13 個資料集中的 9 個勝出。代價是索引體積大幅膨脹：在 Natural Questions 的 4,874 篇段落上，單向量索引僅 7.5–15 MB，多向量原始向量則達 311.5 MB，壓縮後仍要 92 MB。
| 指標 | Dense（單向量） | Multi-vector（LateOn） |
|---|---|---|
| NanoBEIR 平均 NDCG@10 | 0.6764 | 0.6868 |
| 索引大小（原始） | 7.5–15 MB | 311.5 MB |
| 索引大小（壓縮後） | — | 92 MB |
為緩解索引膨脹，文章提出token pooling：以階層式分群將 token 向量數量減少 50%（pool_factor=2），檢索表現幾乎無損；推論端則用 fp16 搭配 Flash Attention，在 GPU 上取得 2.44 倍吞吐量提升。目前 Qdrant、Weaviate、Vespa、LanceDB 與 VectorChord 已原生支援 MaxSim 運算，此架構也延伸支援 ColPali 式視覺文件檢索，可直接比對文字查詢與頁面影像而無需 OCR。
原始來源：Hugging Face Blog: Multi-Vector (Late Interaction) Embedding Models