近段時(shí)間，AI 編程工具 Cursor 的風(fēng)頭可說是一時(shí)無兩，其表現(xiàn)卓越、性能強(qiáng)大。近日，Cursor 一位重要研究者參與的一篇相關(guān)論文發(fā)布了，其中提出了一種方法，可通過搜索自然語言的規(guī)劃來提升 Claude 3.5 Sonnet 等 LLM 的代碼生成能力。

具體來說，他們提出的方法名為 PlanSearch（規(guī)劃搜索）。主導(dǎo)團(tuán)隊(duì)是 Scale AI，本文一作為 Scale AI 研究者 Evan Wang。二作 Federico Cassano 現(xiàn)已加入如今炙手可熱的 AI 編程工具公司 Cursor。他曾參與創(chuàng)立了 GammaTau AI 項(xiàng)目，該項(xiàng)目的目標(biāo)是實(shí)現(xiàn) AI 編程的民主化。此外，他也是 BigCode 項(xiàng)目的活躍貢獻(xiàn)者，該項(xiàng)目負(fù)責(zé)開發(fā)用于 AI 編程的 StarCoder 系列大型語言模型。

• 論文標(biāo)題：Planning In Natural Language Improves LLM Search For Code Generation
• 論文地址：https://arxiv.org/pdf/2409.03733

論文開篇，該團(tuán)隊(duì)提到強(qiáng)化學(xué)習(xí)教父 Sutton 的經(jīng)典文章《The Bitter Lesson（苦澀的教訓(xùn)）》揭示的 Scaling Law 的兩大核心原則：學(xué)習(xí)和搜索。隨著大型語言模型的迅猛發(fā)展，人們對(duì)于「學(xué)習(xí)」是否有效的疑慮已基本消除。然而，在傳統(tǒng)機(jī)器學(xué)習(xí)領(lǐng)域中表現(xiàn)出色的「搜索」策略，將如何拓展大模型的能力，還是個(gè)未知數(shù)。

目前阻礙模型應(yīng)用「搜索」的主要難題是模型給出的答案過于雷同，缺乏多樣性。這可能是由于在預(yù)訓(xùn)練的基礎(chǔ)上，模型會(huì)在特定的數(shù)據(jù)集上進(jìn)行進(jìn)一步的訓(xùn)練，以適應(yīng)特定的應(yīng)用場(chǎng)景或任務(wù)所導(dǎo)致的。

經(jīng)過大量實(shí)證研究證明，許多大語言模型往往會(huì)被優(yōu)化，以產(chǎn)生一個(gè)正確的答案。比如下圖中所示，DeepSeek-Coder-V2-Lite-Base 的表現(xiàn)不如其基礎(chǔ)模型，但隨著回答的多樣性的減少，情況發(fā)生了逆轉(zhuǎn)。多個(gè)模型都存在這種現(xiàn)象：經(jīng)過特別指令調(diào)整的模型在只生成一個(gè)答案的情況下（pass@1）通常比基礎(chǔ)模型表現(xiàn)得好很多，但當(dāng)需要生成多個(gè)答案時(shí)，這種優(yōu)勢(shì)就不明顯了 —— 在某些情況下，甚至完全相反。

模型在生成答案時(shí)缺乏多樣性，這對(duì)于搜索的效果非常不利。特別是在極端情況，比如采用「貪心解碼」，模型給出的答案會(huì)非常相似，因?yàn)樗鼈兪菑哪Ｐ椭兄貜?fù)抽取的。這種情況下，即使模型花費(fèi)更多推理時(shí)間，也難以獲得更好的搜索結(jié)果。

通行的大模型排行榜，例如例如 LMSYS Chatbot Arena、LiveCodeBench、OpenLLMLeaderboard，很難反應(yīng)模型在回答多樣性方面的不足。這些排行榜主要關(guān)注模型在單一樣本上的通過率，沒有考慮到模型在更廣泛場(chǎng)景下的表現(xiàn)。由于模型需要很快地響應(yīng)用戶的需求，單一樣本的回答質(zhì)量是衡量一個(gè)聊天機(jī)器人的關(guān)鍵指標(biāo)，但這一指標(biāo)并不足以全面評(píng)估模型在允許更充裕推理時(shí)間時(shí)的綜合性能。

針對(duì)以上問題，研究人員對(duì)如何在大語言模型推理過程中提高回答的多樣性進(jìn)行了探索。對(duì)此，他們提出了假設(shè)，想讓模型輸出的答案更加豐富，需要在自然語言的概念或想法的空間內(nèi)進(jìn)行搜索。

為了驗(yàn)證這個(gè)假設(shè)，研究人員進(jìn)行了一系列實(shí)驗(yàn)。首先，研究人員發(fā)現(xiàn)，如果給模型一些簡(jiǎn)單的草圖（這些草圖是從已經(jīng)能解決問題的代碼中「回譯」而來），模型就能根據(jù)這些草圖寫出正確的最終程序。其次，研究人員還發(fā)現(xiàn)，如果讓模型在嘗試解決問題之前，先在 LiveCodeBench 上想出一些點(diǎn)子（這個(gè)過程叫做 IdeaSearch / 思路搜索），然后看看模型能不能用這些點(diǎn)子解決問題。

結(jié)果發(fā)現(xiàn)，模型要么完全解決不了問題（準(zhǔn)確度為 0%），要么就能完美解決問題（準(zhǔn)確度為 100%）。這表明當(dāng)模型嘗試解決一個(gè)問題時(shí)，成功與否主要取決于它最初的那個(gè)想法（草圖）對(duì)不對(duì)。

根據(jù)這兩個(gè)實(shí)驗(yàn)的結(jié)果，研究人員認(rèn)為一種提升 LLM 代碼搜索能力的自然方法是：搜索正確的思路，然后實(shí)現(xiàn)它！

于是，規(guī)劃搜索（PlanSearch）方法誕生了。

不同于之前的搜索方法（通常是搜索單個(gè) token、代碼行甚至整個(gè)程序）不一樣，規(guī)劃搜索是搜索解決當(dāng)前問題的可能規(guī)劃。這里，規(guī)劃（plan）的定義是：有助于解決某個(gè)特定問題的高層級(jí)觀察和草案的集合。

為了生成新規(guī)劃，規(guī)劃搜索會(huì)生成大量有關(guān)該問題的觀察，然后再將這些觀察組合成用于解決問題的候選規(guī)劃。

這個(gè)操作需要對(duì)生成的觀察的每個(gè)可能子集都執(zhí)行，以最大化地鼓勵(lì)在思路空間中進(jìn)行探索，之后再將結(jié)果轉(zhuǎn)譯成最終的代碼解決方案。

該團(tuán)隊(duì)的實(shí)驗(yàn)發(fā)現(xiàn)，在推理時(shí)有效使用計(jì)算方面，規(guī)劃搜索方法優(yōu)于標(biāo)準(zhǔn)的重復(fù)采樣方法以及直接搜索思路的方法。

方法

在這項(xiàng)研究中，該團(tuán)隊(duì)探索了多種不同方法，包括重復(fù)采樣（Repeated Sampling）、思路搜索（IdeaSearch）以及新提出的規(guī)劃搜索（PlanSearch）。其中前兩種方法顧名思義，比較直觀，這里我們重點(diǎn)關(guān)注新提出的規(guī)劃搜索。

該團(tuán)隊(duì)觀察到，雖然重復(fù)采樣和思路搜索能成功地提升基準(zhǔn)評(píng)測(cè)的結(jié)果。但在很多案例中，多次提示（pass@k）（即使在溫度設(shè)置很高）只會(huì)導(dǎo)致輸出代碼發(fā)生很小的變化，這些變化只會(huì)改變一些小方面，但無法改善思路中的缺陷。

下面來看具體的規(guī)劃搜索過程：

1. 通過提示來獲取觀察

首先假設(shè)有一個(gè)問題陳述 P，通過向 LLM 發(fā)送提示詞來獲取對(duì)該問題的「觀察」/ 提示。這里將這些觀察記為  O^1_i，其中 i ∈ {1, . . . , n_1}；這是因?yàn)樗鼈兪且浑A觀察。通常而言，n_1 的數(shù)量級(jí)在 3 到 6 之間。具體數(shù)量取決于 LLM 輸出。為了利用這些觀察結(jié)果來啟發(fā)未來的思路，該團(tuán)隊(duì)創(chuàng)建了 O^1_i 的集合 S^1 的且大小至多為 2 的所有子集。其中每個(gè)子集都是觀察結(jié)果的一個(gè)組合。這里將每個(gè)子集記為 C^1_i，其中 i ∈ {1, . . . , l_1}，而

2. 推導(dǎo)新的觀察

這樣一來，所有觀察結(jié)果的集合都可以定義為深度為 1 的有向樹，其中根節(jié)點(diǎn)為 P，并且每個(gè) C^1_i 都有一條從 P 指向 C^1_i  的邊。

然后，在每個(gè)葉節(jié)點(diǎn) C^1_i 上重復(fù)上一步流程，從而生成一個(gè)二階觀察集 S^2。為了得到二階觀察，該團(tuán)隊(duì)的做法是在給模型的提示詞中包含原始問題 P 和 C^1_i 中包含的所有觀察 —— 這些觀察被構(gòu)造為解決 P 所必需的原始觀察。然后再提示 LLM，讓其使用 / 合并在 C^1_i 中找到的觀察來得出新的觀察。

這個(gè)過程可以繼續(xù)延伸，但由于計(jì)算限制，這里在深度為 2 時(shí)對(duì)該樹進(jìn)行了截?cái)嗖僮鳌?/span>

3. 將觀察變成代碼

在得到了觀察之后，必須先將它們實(shí)現(xiàn)成具體思路，然后再將它們轉(zhuǎn)譯成代碼。

具體來說，對(duì)于每個(gè)葉節(jié)點(diǎn)，將所有觀察以及原始問題 P 放入提示詞來調(diào)用 LLM，以便生成問題 P 的自然語言解決方案。為了提升多樣性，對(duì)于每個(gè)生成的思路，該團(tuán)隊(duì)通過假設(shè)該思路是錯(cuò)誤的來生成一個(gè)額外的思路，并要求 LLM 給出批評(píng) / 反饋，從而將提議的思路翻倍了。

然后，再將這些自然語言解決方案轉(zhuǎn)譯成偽代碼；再把這些偽代碼轉(zhuǎn)譯成真正的 Python 代碼。

實(shí)驗(yàn)

實(shí)驗(yàn)采用了三個(gè)評(píng)估基準(zhǔn)：MBPP+、HumanEval+ 和 LiveCodeBench。參數(shù)設(shè)置等細(xì)節(jié)請(qǐng)參閱原論文。

至于結(jié)果，該團(tuán)隊(duì)報(bào)告了三種方法的結(jié)果，包括重復(fù)采樣、思路搜索和規(guī)劃搜索，見表 1、圖 1 和圖 5。

可以看到，規(guī)劃搜索和思路搜索的表現(xiàn)明顯優(yōu)于基礎(chǔ)的采樣方法，其中規(guī)劃搜索方法在所有實(shí)驗(yàn)方法和模型上都取得了最佳分?jǐn)?shù)。

圖 7、8、9 展示了在每個(gè)數(shù)據(jù)集上的詳細(xì) pass@k 結(jié)果。

可以看到，在 Claude 3.5 Sonnet 上使用規(guī)劃搜索方法時(shí)，在 LiveCodeBench 基準(zhǔn)上得到了當(dāng)前最佳的 pass@200 性能：77.0%。該表現(xiàn)優(yōu)于不使用搜索時(shí)獲得的最佳分?jǐn)?shù)（pass@1 = 41.4%）以及標(biāo)準(zhǔn)的 best-of-n 采樣方法的分?jǐn)?shù)（pass@200 = 60.6%）。

此外，使用小型模型（GPT-4o-mini）執(zhí)行規(guī)劃搜索時(shí)，僅僅 4 次嘗試后就能勝過未使用搜索增強(qiáng)的大型模型。這佐證了近期一些使用小模型進(jìn)行搜索的有效性的研究成果。

在另外兩個(gè)編程基準(zhǔn) HumanEval+ 和 MBPP+ 上，規(guī)劃搜索也能帶來類似的提升。

通過研究特定模型的差異，該團(tuán)隊(duì)注意到 pass@k 曲線所呈現(xiàn)的趨勢(shì)在所有模型中并不統(tǒng)一；事實(shí)上，每條曲線看起都不一樣。該團(tuán)隊(duì)猜想部分原因是思路多樣性的變化。

該團(tuán)隊(duì)還得到了一個(gè)有趣的觀察結(jié)果：規(guī)劃搜索并不利于某些模型的 pass@1 指標(biāo)，其中最明顯的是 Sonnet 3.5 在 LiveCodeBench 上的表現(xiàn) —— 這是實(shí)驗(yàn)中表現(xiàn)最好的組合。

該團(tuán)隊(duì)基于直覺給出了解釋：提升思路多樣性可能會(huì)降低生成任何特定思路的概率，同時(shí)增加在給定池中至少有一個(gè)正確思路的幾率。因此，pass@1 可能會(huì)略低于平常，但也正是由于這個(gè)原因，pass@k 指標(biāo)可能會(huì)優(yōu)于缺乏多樣性的思路池。

另外，表 1 和圖 1 給出了在嘗試 / 完成上經(jīng)過歸一化的主要結(jié)果。其中針對(duì)每個(gè)問題，每種搜索方法都可以嘗試 k 次。

最后，該團(tuán)隊(duì)還發(fā)現(xiàn)，在思路空間中觀察到的多樣性可用于預(yù)測(cè)搜索性能，這可通過模型 / 方法的 pass@1 與其 pass@200 之間的相對(duì)改進(jìn)計(jì)算得到，如圖 6 所示。

雖然熵是最常見的多樣性度量是，但由于種種原因，熵不足以精確衡量 LLM 的多樣性。

因此，該團(tuán)隊(duì)測(cè)量多樣性的做法是在所有生成的程序上使用簡(jiǎn)單的配對(duì)策略，將其置于思路空間中進(jìn)行計(jì)算。具體算法請(qǐng)?jiān)L問原論文。