一個問題追蹤從 o3 到 GPT-5.6 及未來的 AI 進展

梯度流在凸函數上的路徑長度——在單位歐幾里得球內能有多長？

這是我兩年來用來測試 AI 進展的問題。這個問題陳述起來異常簡單，但解決起來卻極其困難。在 168 分鐘的思考時間裡，GPT-5.6 成功大幅超越了這個問題的已發表 SOTA，而且是以其他模型至今無法做到的方式。但我有點說得太快了，讓我們先思考一下這個問題，回顧相關文獻，然後再討論從 o3 到 GPT-5.6 的進展。

1. SOTA

直覺上可能有人會說：「嗯，梯度下降的收斂速度是與維度無關的——這也是為什麼它在處理多參數問題時如此令人興奮！——所以這類流的路徑長度應該也是與維度無關的吧？」但直覺有時候可能大錯特錯。首先，這樣的曲線是否真的是可求長的（也就是說，具有有限長度，更不用提維度依賴性了）？即便是這一點也不容易證明，而且事實上，對於 Nesterov 加速梯度下降來說，這個結論是錯誤的（參見 這篇論文，作者為 @ErnestRyu，所有工作都由 GPT-5.5 完成）。

那麼，關於這個問題我們到底知道些什麼？有一篇 1991 年由 Manselli 和 Pucci 發表的精美論文，證明了這類曲線確實是可求長的，而且它們的長度最多為 n^O(n)。你沒看錯，甚至比指數級還糟，這就是 35 年前的最佳上界！順帶一提，這篇論文還指出，這類曲線屬於所謂的「自收縮」曲線，也就是說，它們總是越來越接近自己的未來（取曲線上任一點在時間 t 的位置，則對於 s<t，dist(x(s), x(t)) 是非遞增的；見下圖說明）。

那麼下界呢？也就是要建構一條實際很長的自收縮曲線。從凸優化文獻中，一個標準的方法是考慮一個病態條件數的二次型，例如 x_1^2 + 很大常數x_2^2 + 更大常數x_3^2 + ...。關鍵在於，梯度下降會先沿著最大常數的方向幾乎直線前進，然後再沿次大常數的方向前進，以此類推（見下圖說明）。因此，路徑的總長度大約是 n，而這條路徑包含在半徑為 sqrt(n) 的超立方體內，所以通過重新縮放，我們可以得到一條長度為 sqrt(n) 的自收縮曲線。

就這樣。這就是已發表的 SOTA：上界為 n^O(n)，下界為 sqrt(n)。對於這麼簡單且自然的問題來說，這差距還真不小！

自收縮曲線的定義

一條長度為 sqrt(n) 的自收縮曲線

2. 人類未發表的工作

八年前，我與優秀的合作者 Omer Angel、Tomas Merchan Rodriguez 和 Fedja Nazarov 一起思考過這個問題。我們取得了相當大的進展，並確立了答案確實是維度指數級！具體來說，我們得到了 sqrt(2)^n 的下界和 4^n 的上界。包含這些估計值的論文已經寫得整整齊齊，並在我的 Dropbox 資料夾裡存放了將近十年，部分原因是我們知道這些界限還可以進一步改進。而事實上，Tomas 和 Fedja 確實取得了更多進展，首先將下界提高到 2^n，同時也將上界改進到 2.29...^n。請注意，我個人對這個問題的理解仍然停留在略優於 sqrt(2)^n 的下界和 4^n 的上界（事實上，我已經忘記了 2^n 和 2.29^n 的結果，直到 AI 開始在這個問題上取得進展……下面會詳細說明）。

3. AI 的進展

o3 是第一個能夠理解這個問題的 AI 模型。是的，你沒看錯。也許你忘了，兩年前，AI 是否能「理解」這種看似簡單的問題都還不清楚，更不用說解決它們了。特別值得一提的是，o3 能夠看出這個問題實際上與自收縮曲線有關，並且知道這個問題的 SOTA 是什麼。當時我對此感到非常非常印象深刻。

但後來事情變得棘手了，隨著 GPT-5 系列模型的到來，我把這個問題當作一個警示故事：直到今年二月，我還會在關於 LLM 在數學領域進展的演講中，把這個問題作為一個「不應該問 LLM 的問題」的例子。原因是，GPT-5 甚至 GPT-5.2/5.4 會嘗試給出複雜的答案，但它們總是在某處出錯，人們會浪費大量時間去檢查這些答案。所以這是一個很好的例子，說明要在數學上不浪費時間與 LLM 打交道，就必須知道該問什麼樣的問題。

這個情況在 GPT-5.5 時發生了改變。突然之間，在大量的反覆交流與專家提示下，Mark Sellke 能夠重新發現 2^n 下界的構造（這讓我非常震驚，部分原因是我忘記了 Tomer 和 Fedja 已經知道這個結果 😅）。另一方面，上界則完全沒有進展。

現在 GPT-5.6 來了，AI 的進展完全展現在眼前：

• GPT-5.6-pro 一次就完成了 2^n 下界。你可以在這裡看到這個一次完成的結果（80 分鐘的思考時間）：https://chatgpt.com/s/t_6a50cb2a29488191b643ecb2426df87d
• GPT-5.6-pro 一次就完成了 4^n 上界，而且實際上在它的思考鏈中非常快地就做到了，到思考結束時，它產生了一個 2.31...^n 的上界。雖然沒有完全追上 Fedja 的 2.29...^n（事實上，沒有新的想法，2.31...^n 的策略是無法進一步改進的——其實 Fedja 自己在 2018 年的 MathOverflow 貼文 中就指出過：「[對於 2.31..] 論證變得有些混亂，而且很明顯這種方法無法得到最優估計。」）。但這仍然非常令人印象深刻，並且超越了我個人當初認真研究這個問題時對此的理解程度。你可以在這裡看到這個一次完成的結果，花了 88 分鐘思考：https://chatgpt.com/share/6a50764e-3eec-83ea-97e6-3d1f30c07b64

4. 未來的挑戰

這個故事目前仍然以人類為贏家。人類的 2.29 對比機器的 2.31。自然，猜想是自收縮曲線的長度不能超過 2^n（這將是給定 2^n 下界後的最優答案）。這似乎非常難以證明，並且超出了 GPT-5.6 的能力範圍。我還能用這個問題來追蹤 AI 的進展多久呢？我猜可能不到六個月……

附註：我把上面的文章複製貼上到 ChatGPT 工作中，並要求它為這篇文章生成插圖。這裡的圖片集是從該查詢中一次獲得的。