今天是個(gè)好日子，DeepSeek 與 Kimi 都更新了最新版的推理模型，吸引了廣泛關(guān)注。與此同時(shí)，谷歌 DeepMind、加州大學(xué)圣地亞哥分校、阿爾伯塔大學(xué)的一篇新的研究論文也吸引了不少眼球，并直接沖上了 Hugging Face 每日論文榜第一（1 月 20 日）。

這篇論文題為《Evolving Deeper LLM Thinking》，可譯為「進(jìn)化式更深度 LLM 思維」，其中提出了一種進(jìn)化搜索策略，可用于 scaling LLM 的推理時(shí)計(jì)算（inference time compute）。該方法被命名為 Mind Evolution，即心智進(jìn)化。實(shí)驗(yàn)表明，在同等推理成本下，新方法的自然語言規(guī)劃任務(wù)表現(xiàn)會(huì)顯著優(yōu)于 Best-of-N 和 Sequential Revision 等其它推理策略。

論文地址：https://arxiv.org/pdf/2501.09891

如何實(shí)現(xiàn)心智進(jìn)化

Mind Evolution 采用了遺傳搜索策略，并結(jié)合了一個(gè) LLM 和定制的提示集，從而可以有效地搜索自然語言規(guī)劃任務(wù)的解。為了理解 Mind Evolution，我們首先需要簡單了解基于語言的遺傳算法。

基于語言的遺傳算法

遺傳算法是一種受自然選擇啟發(fā)的元啟發(fā)式算法。在遺傳算法中，候選解種群會(huì)朝著包含更多高質(zhì)量個(gè)體的種群方向演化，這里的質(zhì)量是相對(duì)于目標(biāo)優(yōu)化目標(biāo)而言的。這個(gè)目標(biāo)通常也被稱為「適應(yīng)度」函數(shù)。每個(gè)候選個(gè)體都有一個(gè)可以突變并與其他個(gè)體重組的遺傳表示。

演化搜索通常始于獨(dú)立生成的候選解種群。在每一代中，都會(huì)根據(jù)目標(biāo)評(píng)估每個(gè)個(gè)體的適應(yīng)度。然后基于適應(yīng)度對(duì)候選個(gè)體進(jìn)行隨機(jī)選擇（「選擇」）。在繁殖過程中，被選擇的父代的遺傳表示會(huì)進(jìn)行組合（「雜交」）并可能發(fā)生改變（「突變」）以產(chǎn)生新的子代解。這個(gè)過程創(chuàng)造了下一代的子代，它們隨后進(jìn)入種群。由于適應(yīng)度更高的父代更有可能被選擇進(jìn)行重組，種群適應(yīng)度通常會(huì)隨著連續(xù)幾代而提高。

島嶼模型。為了維持演化種群的多樣性，還可引入島嶼模型。在該模型中，不同的子種群（「島嶼」）會(huì)獨(dú)立演化，直到按照特定頻率發(fā)生「遷移」和「島嶼重置」事件。對(duì)于遷移操作，一個(gè)島嶼上的解會(huì)基于適應(yīng)度被隨機(jī)選擇遷移到相鄰島嶼。對(duì)于島嶼重置操作，整體適應(yīng)度較低的島嶼上的種群會(huì)被全局種群中的強(qiáng)解替換，這也具有選擇效應(yīng)。最近已經(jīng)有一些研究成功采用了島嶼模型，如 FunSearch。

基于語言的遺傳表示?；谡Z言的遺傳算法中的個(gè)體候選解由自然語言表示。這允許通過提示詞來利用 LLM 強(qiáng)大的語言理解和生成能力來實(shí)現(xiàn)強(qiáng)大的重組（雜交和突變）和島嶼重置操作。

Mind Evolution

Mind Evolution 的設(shè)計(jì)見圖 1，其超參數(shù)則見表 1。

Mind Evolution 的核心組件包括：

1. 選擇和遷移操作的具體選擇；
2. 一個(gè)提示集，可使用 LLM 實(shí)現(xiàn)初始化、重組（雜交和突變）以及島嶼重置操作；
3. 一個(gè)適應(yīng)度函數(shù)，用于評(píng)估給定解的質(zhì)量并可選擇性地反饋檢測到的問題。

整個(gè)演化過程會(huì)重復(fù)進(jìn)行，直到找到有效解，或者直到完成 N_gens 代演化，之后返回得分最高的候選解。

適應(yīng)度評(píng)估。該團(tuán)隊(duì)為每個(gè)問題域?qū)崿F(xiàn)了一個(gè)適應(yīng)度函數(shù)，其中候選解會(huì)被解析并以編程方式進(jìn)行評(píng)估。原則上，任何可以評(píng)估解質(zhì)量的函數(shù)都可以使用，包括 LLM 評(píng)估。

在 Mind Evolution 中，評(píng)估函數(shù)有三個(gè)關(guān)鍵作用：

• 通過衡量優(yōu)化目標(biāo)為解評(píng)分（如果有的話）；
• 驗(yàn)證解是否滿足給定約束；
• 提供相應(yīng)的文本反饋。

需要注意的是，對(duì)于許多經(jīng)典搜索問題（如 NP 完全問題），驗(yàn)證解比解決問題要容易得多。同樣，該該團(tuán)隊(duì)觀察到，對(duì)于所考慮的自然語言規(guī)劃任務(wù)，編寫評(píng)估函數(shù)是可能的。能夠檢查候選解的正確性并不意味著能在這個(gè)任務(wù)找到有效解。也就是說，實(shí)現(xiàn)評(píng)估函數(shù)并不等同于解決任務(wù)。

種群初始化。給定目標(biāo)問題，通過向 LLM 提供問題描述、解決問題所需的任何信息以及相關(guān)指令，獨(dú)立采樣 N_convs 個(gè)初始解。如果 N_seq > 1，則每個(gè)初始解都會(huì)通過「通過批評(píng)性對(duì)話進(jìn)行優(yōu)化（Refinement through Critical Conversation）」過程的 N_seq - 1 個(gè)額外輪次進(jìn)行評(píng)估和改進(jìn)，該過程將在下文解釋。

這個(gè)初始化過程一共會(huì)生成 N_convs × N_seq 個(gè)候選解，它們構(gòu)成了第一代第一個(gè)島嶼上的初始種群。

通過批評(píng)性對(duì)話進(jìn)行優(yōu)化（RCC）。給定一個(gè)候選解（或用于重組過程的一組候選解），該團(tuán)隊(duì)利用 LLM 通過組織「批評(píng)者」角色和「作者」角色之間的批評(píng)性對(duì)話來生成改進(jìn)的解，如圖 2 所示。

分離這兩個(gè)角色的目標(biāo)是提高 LLM 的批判性思維能力。每輪對(duì)話都會(huì)被構(gòu)建為一個(gè)由提示詞驅(qū)動(dòng)的過程，其中解會(huì)根據(jù)批評(píng)性反饋進(jìn)行改進(jìn)，類似于 Reflexion。

具體來說，批評(píng)者首先會(huì)分析輸入的候選解，解讀文本評(píng)估反饋，并建議糾正反饋中提到的問題的方法。然后，作者基于輸入候選解、后續(xù)評(píng)估和批評(píng)者的分析提出一個(gè)改進(jìn)的解。

選擇。為了產(chǎn)生島嶼的下一代，該團(tuán)隊(duì)遵循玻爾茲曼錦標(biāo)賽選擇（Boltzmann tournament selection）方法，其中根據(jù)從適應(yīng)度分?jǐn)?shù)的 softmax 變換得到的概率分布，從種群中隨機(jī)采樣 0 到 N_parent 個(gè)父代。通過這種方式，表現(xiàn)更好的解更有可能被選擇用于繁殖，而其他候選解仍然可以偶爾被選擇以保持多樣性。

雜交和突變。該團(tuán)隊(duì)將雜交和突變操作實(shí)現(xiàn)為單個(gè)重組步驟，即指示 LLM 使用上述 RCC 過程來改進(jìn)給定的一組父代（圖 2）。具體來說，對(duì)于重組，采樣 1 到 N_parent 個(gè)父代，并修改圖 2 中的步驟（b）以首先納入父代的評(píng)估結(jié)果，然后對(duì)所有父代應(yīng)用批評(píng)者并將修改后的解作為下一代的「初始解」提出。然后，如果 N_seq > 1，繼續(xù)遵循步驟（c）（d）（e）順序生成 N_seq - 1 個(gè)子代解，通過使用 RCC 過程改進(jìn)每個(gè)先前的子代。

對(duì)于每個(gè)島嶼上的每一代，都會(huì)將 N_convs × N_seq 個(gè)子代解添加到島嶼種群中，并移除重復(fù)的解。對(duì)于選擇，該團(tuán)隊(duì)遵循玻爾茲曼錦標(biāo)賽而不是顯式地淘汰候選解，除非執(zhí)行如下的島嶼重置。

島嶼間遷移。在遷移事件之間，每個(gè)島嶼種群獨(dú)立演化。在遷移期間，在完成當(dāng)前島嶼上的這一代后，頂部的 N_emigrate 個(gè)解從當(dāng)前島嶼 i 克隆到下一個(gè)島嶼 i + 1（該團(tuán)隊(duì)按從 1 到 N_island 的順序順序更新島嶼上的種群）。遷移在島嶼之間循環(huán)進(jìn)行，所以從島嶼 N_island 的移民會(huì)到達(dá)島嶼 1。該團(tuán)隊(duì)發(fā)現(xiàn)這種形式的循環(huán)遷移可加速整體演化過程。

島嶼重置。島嶼重置每隔 N_reset 代就發(fā)生一次。在島嶼重置事件期間，首先從全局種群中選擇表現(xiàn)最好的個(gè)體，平均得分最低的 N_reset 個(gè)島嶼上的種群被淘汰，選定的表現(xiàn)最好的個(gè)體被克隆到重置的島嶼上。為了選擇表現(xiàn)最好的個(gè)體，該團(tuán)隊(duì)探索了兩種方法：

• 根據(jù)適應(yīng)度直接選擇排名前 N_top 的候選解；
• 首先根據(jù)適應(yīng)度選擇排名前 N_candidate 的候選解，然后提示 LLM 從這個(gè)池中選擇 N_top 個(gè)彼此有實(shí)質(zhì)性差異的好候選解。消融研究表明，后一種策略的效果更好。

心智進(jìn)化的實(shí)驗(yàn)表現(xiàn)

任務(wù)。該團(tuán)隊(duì)在三個(gè)基準(zhǔn)自然語言規(guī)劃領(lǐng)域上評(píng)估了 Mind Evolution，其中包括來自 Natural Plan 的兩個(gè)任務(wù)（Trip Planning 和 Meeting Planning ），以及 TravelPlanner 基準(zhǔn)。

模型。在實(shí)驗(yàn)中，該團(tuán)隊(duì)使用的默認(rèn) LLM 是 Gemini 1.5 Flash（gemini-1.5-flash001）。表 1 給出了將 Mind Evolution 應(yīng)用于 Flash 時(shí)使用的超參數(shù)。除了評(píng)估使用 Flash 模型的 Mind Evolution 外，該團(tuán)隊(duì)還研究了一種兩階段方法，其中對(duì)于在 N_gens 代限制內(nèi)未解決的問題使用 Gemini 1.5 Pro 模型（gemini-1.5-pro-exp-0827）。這種兩階段方法比在每個(gè)問題實(shí)例上都使用 Pro 模型更具成本效益。

對(duì)比基線。對(duì)于每個(gè)任務(wù)，Mind Evolution 都與三種基線搜索策略進(jìn)行了比較，這些策略使用了相同的解評(píng)估器和特定任務(wù)的提示詞：

1. 1-Pass，其中使用 LLM 的單次前向傳遞得到解。
2. Best-of-N，獨(dú)立生成最多 800 個(gè)候選解，直到找到成功的解（與 Mind Evolution 上限相同）。
3. Sequential-Revision+，其中獨(dú)立提出 10 個(gè)候選解，然后使用 RCC 過程分別修改 80 輪。注意使用 10 個(gè)獨(dú)立的 80 輪改進(jìn)線程而不是單個(gè) 800 輪改進(jìn)，因?yàn)樵搱F(tuán)隊(duì)表示很少能觀察到 80 輪后的改進(jìn)。這個(gè)基準(zhǔn)方法類似于運(yùn)行 10 次多輪 Reflexion。

此外，作為參考，該團(tuán)隊(duì)還在對(duì)比中加入了使用 OpenAI o1-preview 的 1-Pass 基準(zhǔn)。

TravelPlanner

TravelPlanner 是一個(gè)自然語言規(guī)劃基準(zhǔn)，它模擬的問題是：根據(jù)用戶給出的偏好和約束條件，為用戶組織旅行計(jì)劃。

表 2 比較了 Mind Evolution 與基線策略的總體成功率和計(jì)算成本。

可以看到，在成功率方面，Mind Evolution 明顯優(yōu)于基線策略，超過 95%。相比之下，Sequential-Revision+ 的表現(xiàn)也還行，接近 83%，而 Best-of-N 遜色多了，僅有 55.6%。總的來說，進(jìn)化策略的優(yōu)勢得到了明顯體現(xiàn)。

再來看看上面的兩階段方法，即使用 Gemini 1.5 Pro 處理未被解決的問題，該團(tuán)隊(duì)發(fā)現(xiàn)幾乎整個(gè)數(shù)據(jù)集都可以被解決 —— 在驗(yàn)證和測試問題上分別達(dá)到 100% 和 99.9% 的成功率。

該團(tuán)隊(duì)表示，唯一接近這個(gè)成功率的研究成果是《Large language models can plan your travels rigorously with formal verification tools》（arXiv:2404.11891）—— 該方法使用 GPT-4 進(jìn)行自動(dòng)形式化，然后利用形式求解器分別在驗(yàn)證和測試集上達(dá)到 98.9% 和 97.0% 的成功率。相較之下，Mind Evolution 完全無需形式求解器。

最后需要注意的是，TravelPlanner 數(shù)據(jù)集包含三個(gè)難度級(jí)別（簡單、中等、困難）和三個(gè)旅行時(shí)長（3 天、5 天、7 天），這就形成了 9 個(gè)不同的問題類別。圖 3 展示了在這些不同類別上的成功率的細(xì)分情況。

可以看到 1-Pass 和 Best-of-N 的成功率會(huì)在規(guī)劃更多旅行天數(shù)時(shí)下降，但對(duì)于 Mind Evolution 和 Sequential-Revision+ 這種迭代改進(jìn)方法，這種趨勢不太明顯。

Natural Plan – Trip Planning

Trip Planning 任務(wù)的目標(biāo)是找到一個(gè)行程安排，其中包含要訪問的城市序列以及在每個(gè)城市停留的天數(shù)，需要滿足航班連接性和日程安排約束。表 3 給出了一些問題實(shí)例。該團(tuán)隊(duì)將基準(zhǔn)數(shù)據(jù)集分為了 320 個(gè)驗(yàn)證和 1280 個(gè)測試實(shí)例。

同樣，從表 2 可以看到，Mind Evolution 在這個(gè)任務(wù)上明顯優(yōu)于基線方法，其成功率在驗(yàn)證集上達(dá)到 96.2%，在測試實(shí)例上達(dá)到 94.1%。

值得注意的是，Best-of-N（77.2%）在這個(gè)任務(wù)上超過了 Sequential-Revision+（74.4%）。

該團(tuán)隊(duì)發(fā)現(xiàn)，對(duì)于兩階段方法，Mind Evolution 在驗(yàn)證集上的成功率達(dá)到了 100%，在測試集上也達(dá)到 99.6%。這些發(fā)現(xiàn)再次突出了進(jìn)化搜索相對(duì)于簡單采樣和順序改進(jìn)的優(yōu)勢。

最后需要指出，這個(gè)任務(wù)的難度會(huì)隨要訪問的城市數(shù)量而變化，范圍從 3 到 10 個(gè)城市。圖 4 顯示了按城市數(shù)量劃分的成功率細(xì)分情況，看起來 Mind Evolution 的相對(duì)優(yōu)勢隨著城市數(shù)量的增加而增加。

Natural Plan – Meeting Planning 

Meeting Planning 的任務(wù)目標(biāo)是安排一系列會(huì)議以最大化個(gè)人之間的會(huì)議數(shù)量，所涉及的限制條件包括可用性、位置和交通時(shí)間。這個(gè)任務(wù)與 TravelPlanner 和  Trip Planning  的不同之處在于，并非每個(gè)問題實(shí)例的每個(gè)會(huì)議都可安排，這意味著無法知道是否已達(dá)到最優(yōu)解。因此，該團(tuán)隊(duì)允許搜索繼續(xù)進(jìn)行直到達(dá)到迭代次數(shù)的上限，最終得到了表 2 中的結(jié)果。對(duì)于這個(gè)任務(wù)，該團(tuán)隊(duì)將實(shí)例集分為了 500 個(gè)驗(yàn)證和 500 個(gè)測試實(shí)例。

從表 2 可以看到，Mind Evolution 在驗(yàn)證集上達(dá)到 85.0% 的成功率，在測試集上達(dá)到 83.8%。值得注意的是，使用 Gemini 1.5 Pro 的兩階段方法在驗(yàn)證和測試上的成功率分別為 98.4% 和 98.2%。

最后，圖 5 顯示了按需要安排會(huì)議的人數(shù)劃分的成功率細(xì)分情況。該團(tuán)隊(duì)發(fā)現(xiàn)，隨著人數(shù)增加，Mind Evolution 可保持顯著的成功率優(yōu)勢。

實(shí)驗(yàn)結(jié)果分析

為了理解 Mind Evolution 的 scaling 性能，該團(tuán)隊(duì)還進(jìn)行了更多研究。

scaling 性能。圖 6 報(bào)告了 Mind Evolution 在規(guī)劃任務(wù)中隨著代數(shù)增加的成功率變化情況。這些結(jié)果清楚地表明， Mind Evolution 會(huì)隨著代數(shù)增加而穩(wěn)步提升。

為了比較 Mind Evolution 與基線搜索方法的 scaling 性能，該團(tuán)隊(duì)還做了每種策略生成的候選解數(shù)量與成功率和平均任務(wù)評(píng)估分?jǐn)?shù)的關(guān)系圖（圖 7-9）。任務(wù)評(píng)估分?jǐn)?shù)通過對(duì)未滿足的約束和目標(biāo)值的次優(yōu)性進(jìn)行懲罰來計(jì)算，因此在任何問題實(shí)例中可以達(dá)到的最高分?jǐn)?shù)是零。

圖 7-9 分別顯示了在 TravelPlanner、Trip Planning 和 Meeting Planning 任務(wù)上的結(jié)果。在每種情況下，都可以看到所有搜索方法的整體成功率和平均任務(wù)評(píng)估分?jǐn)?shù)都會(huì)隨著提出的解數(shù)量的增加而單調(diào)改善。這些圖還表明，就達(dá)到指定成功率水平（或平均任務(wù)性能）所需的候選解數(shù)量而言，Mind Evolution 始終比基線策略更有效。

該團(tuán)隊(duì)注意到 Best-of-N 在 TravelPlanner 上的表現(xiàn)明顯不佳。該團(tuán)隊(duì)認(rèn)為這是因?yàn)樵撊蝿?wù)涉及隱含的常識(shí)約束（例如，旅行計(jì)劃應(yīng)該返回出發(fā)城市，不能兩次訪問同一餐廳等），這些約束不在問題實(shí)例中給出，而是從評(píng)估反饋中學(xué)習(xí)得到，而 Best-of-N 沒有利用這些反饋。

該團(tuán)隊(duì)還進(jìn)行了一系列消融研究，以研究 Mind Evolution 不同組件的效果，具體詳情請(qǐng)參閱原論文。

一個(gè)高難度新任務(wù)：StegPoet

最后，在這篇論文中，該團(tuán)隊(duì)還提出了一個(gè)具有挑戰(zhàn)性的新任務(wù) StegPoet，其中需要將隱藏消息通過隱寫術(shù)編碼到一篇?jiǎng)?chuàng)意寫作文章中。

即使這個(gè)問題難以形式化，它仍然適合程序化驗(yàn)證，這使得本文考慮的方法可以處理它。

在這個(gè)任務(wù)中，由數(shù)字序列表示的隱藏消息（M）應(yīng)該被編碼在關(guān)于特定主題的創(chuàng)意文本中，以散文、故事或詩歌的形式表達(dá)。目標(biāo)是既提供一個(gè)數(shù)字到單詞的替換密碼，又生成使用該密碼編碼消息的文本。

圖 10 給出了一個(gè)例子。該團(tuán)隊(duì)額外施加了一個(gè)約束，即在生成的文本中，連續(xù)密碼詞之間必須平均有 B 個(gè)單詞，這確保當(dāng) B > 0 時(shí)，簡單地將密碼詞作為文本部分列出不符合作為解的資格。

這個(gè)問題的難度在四個(gè)維度上變化：

1. 隨著隱藏消息 M 的長度增加，難度增加。該團(tuán)隊(duì)設(shè)定 10 ≤ |M| ≤ 30。
2. M 中數(shù)字的重復(fù)性。重復(fù)越多，約束越嚴(yán)格。
3. 重復(fù)數(shù)字彼此之間的「接近程度」。每種寫作形式都規(guī)定了同一個(gè)詞的重復(fù)和出現(xiàn)接近程度的可接受性。LLM 必須在遵守形式和正確編碼消息的需求之間取得平衡。
4. 根據(jù)經(jīng)驗(yàn)，隨著 B（密碼詞之間的平均距離）增加，問題變得更加困難。測試中，3 ≤ B ≤ 7。

該團(tuán)隊(duì)將問題實(shí)例分為了 101 個(gè)驗(yàn)證實(shí)例和 245 個(gè)測試實(shí)例。表 6 給出了 Mind Evolution 和基線策略的詳細(xì)性能結(jié)果，而圖 11 顯示了每個(gè)難度級(jí)別的性能。

可以看到，兩階段 Mind Evolution（+pro）在驗(yàn)證集上達(dá)到 87.1% 的成功率，在測試集上達(dá)到 79.2%。相較之下，Best-of-N 僅能解決 1% 的驗(yàn)證任務(wù)。