對代理程式軌跡進行樹搜尋（LATS）

資料來源#

• CS329A Self-Improving AI Agents — Part 5: Planning and Multi-Step Reasoning

摘要#

LATS — Language Agent Tree Search unifies reasoning, acting and planning in language models（ICML 2024）— 是 CS329A 第 5 堂課介紹的第一篇論文，也是本 wiki 首次探討將 Monte Carlo Tree Search 套用於代理程式在環境中的動作。本 wiki 已介紹過對證明進行樹搜尋（Evolutionary Proof Search 的 P-UCB）以及對推論管線進行搜尋（Inference-Time Architecture Search）；LATS 則是以代理程式正在操作的世界狀態為節點的版本。

用一句話說明其主張：採用 ReAct 的思考／動作／觀察交替模式，不要一開始就選定一條軌跡，而是在外層加上 MCTS。Mirhoseini 對目標問題的描述，是她認為至今仍成立的能力批評：模型「在產生多樣解法或採取行動方面可能較弱」，因此預設只取樣一個計畫會探索不足。搜尋就是從 harness 端提出的解法。

證據。 CS329A Self-Improving AI Agents — Part 5: Planning and Multi-Step Reasoning（Azalia Mirhoseini 個人演講，於 2025-10-06 進行，2026-08-03 發布，practitioner-opinion）— 投影片導讀。LATS 論文不在 raw/ 中；所有圖表都是根據 ASR 讀取投影片而得，而課堂對這篇論文幾乎沒有提供任何數字。這裡沒有 COI：LATS 不是她實驗室的研究（也是這堂課介紹的三篇論文中唯一一篇非其實驗室的研究）。

六個階段#

課堂列出六個階段，並以迷宮範例逐一說明——「你在一間光線昏暗的房間裡，面前有兩扇門」：

1. 選擇。 依據 UCT（見下文）選出要擴展的節點，而非選取價值最高者。
2. 擴展。 從選定節點取樣 k 個候選動作（範例取樣三個：開左邊的門、開右邊的門、檢查房間尋找線索）。
3. 評估。 在環境中執行每個動作，將觀察結果附加至上下文，並為結果狀態評分。
4. 模擬。 將最佳子節點向前推進——課堂版本採用貪婪方式——持續取樣與擴展，直到抵達終端狀態（成功或失敗），或耗盡擴展預算。
5. 回傳。 沿路徑向上傳遞軌跡回報，更新每個節點的價值。
6. 反思。 讓模型以自由文字說明軌跡成功或失敗的原因，並將反思附加到上下文，供後續擴展使用。Mirhoseini 表示，這「顯然對整體提升這個方法的品質很有幫助」。

階段 1–5 是教科書上的 MCTS。階段 3 和 6 則是語言模型能做、但遊戲 MCTS 做不到的部分。

價值函數是兩項分數相加#

狀態的價值由下列兩項相加而得：

• LLM-as-a-judge 分數。 提示模型查看動作及其觀察結果，並直接要求它用 [0, 1] 的數字評估該狀態有多值得期待。見 LLM-as-a-Judge。
• 自我一致性分數。 從父節點取樣大量動作——課堂示意採用 50 次而非 3 次——依類型分組，並依某個動作被取樣的頻率為其評分。在示範範例中，狀態 A 得分較高，因為「可能有 75% 的時候會取樣到動作 A」。

將兩者相加，得到每個狀態的一個數值。

選擇與回傳#

UCT（套用於樹的上置信界）直接沿用 MCTS 文獻中的方法，未作修改：價值加上依父節點造訪次數 n_p 和節點自身造訪次數 n_s 計算的加權探索項。因此，相較於父節點而言，較少被造訪的節點會獲得獎勵，造訪次數較多的節點則會被折減。（課堂描述了該項的行為，但沒有清楚寫出公式；逐字稿無法還原其精確形式，因此此處不重建。） 被問及論文是否比較過其他 bandit 演算法時，Mirhoseini 表示沒有，並認為選擇哪種方法並不重要——「他們的主要貢獻是建立一個平台，讓其他人可以加入其他最佳化方法。」

回傳採用移動平均：節點的新價值依其造訪次數更新為 (V_old·(n−1) + return) / n。沒有學習、沒有訓練——每個部分都是透過提示完成。

課堂比較中，LATS 與哪些方法不同#

Mirhoseini 將 LATS 與課程已介紹過的兩種方法比較，而兩者之間的差異比乍看之下更明確：

• 與 Math-Shepherd 相比（Process vs Outcome Reward Models）：Math-Shepherd 使用訓練過的 verifier 為推理步驟評分並引導搜尋。LATS 評分的是在環境中執行動作的結果，以及模型對軌跡的反思和環境回傳的觀察。評分的單位從一段 token 移到世界狀態。
• 與 ReAct 相比（Reasoning–Acting Interleaving (ReAct)）：ReAct 不會回頭。LATS 加入對已評分替代方案的記錄、回到同層分支的能力，以及反思步驟。用課堂上的說法，就是「過程中的規劃愈來愈多」。

課堂所報告的結果#

兩項基準測試都已透過 ReAct 出現在本 wiki：

• HotpotQA — 多跳 QA，需要從至少兩個 Wikipedia 頁面擷取資料，因此天生就是多步驟任務。據報告，取樣的軌跡數量增加時，準確率會顯著上升，而加入反思軌跡「會帶來很大的提升」。ASR 中沒有留下任何數字。對本 wiki 而言，Mirhoseini 的總結最重要：LATS 為多步驟任務提供「一種有效地將更多測試時運算轉化為更佳解答的機制」——將 test-time scaling 套用於行動，而不是回答。
• WebShop — 在模擬商店中購買符合自然語言規格的商品。據報告，LATS 的結果「非常好，甚至接近人類專家」，而且完全沒有微調。作為比較，單獨使用 ReAct 在第 4 堂課的投影片中得分為 66.6，人類專家則為 82.1；LATS 的分數沒有明確報告，因此只能做方向性的比較。

其可移植性主張相當實在：所有流程都是在凍結模型上透過提示完成，因此方法「非常容易移植，也相對容易實作」。

課堂承認的兩項限制，以及一項未提及的限制#

從未分析成本。 Mirhoseini 直言不諱：每次擴展、每次模擬、每次 judge 呼叫和每次回傳都會增加推論成本，而「論文並沒有真正分析成本效益」。一種主打將測試時運算轉化為品質的方法，發表時卻沒有運算量這個維度，正是 Compute-Controlled Benchmarking 要指出的缺口。

動作必須可復原。 這是更根本的限制，而且被明確列為論文未處理的假設：搜尋會在環境中執行候選動作，以便為它們評分，因此探索一個分支就代表真的採取該動作。Mirhoseini 舉例說，模型可能「執行一筆交易……支付一項服務的費用」。在無法復原的環境中，擴展階段不是探測，而是做出承諾；其他同層分支也都得付出代價。因此，LATS 適用於模擬或沙盒環境，而課堂中的迷宮和商店都是模擬器——這讓 containment 中的沙盒承擔了一種原本未設計的用途：它不再只是限制損害，而是演算法能否正確運作的先決條件。

未明說的限制：價值函數有一半是這門課已證明會到達平台期的選擇器。 自我一致性項依據某動作被取樣的次數評分——也就是每個節點的多數決。第 2 堂課的核心結果指出，多數決在 10–50 次取樣後便達到飽和，但覆蓋率仍持續上升，因為最難的問題在 10,000 次嘗試中只會解出 1–3 次；因此，依頻率選擇的機制在結構上會忽略罕見但正確的分支。LATS 將這個盲目選擇器與 LLM 評審相加，再用結果引導整場搜尋。課堂在相隔三週的內容中分別陳述這兩項事實，卻沒有將它們連在一起；本篇編者的解讀補上了這個連結，也由此預測其失效模式——搜尋自信地收斂到最常見的計畫，這正是促使論文提出方法的解法多樣性問題。

重複動作，以及樹／圖的問題#

一位學生詢問，如果同一個動作在不同分支中反覆出現（A、B、A、B），或透過不同路徑抵達相同狀態，會如何處理——能否將樹合併？Mirhoseini 的回答保留了樹的形式：在特定父節點之下的重複情況，會由傳入 UCT 的造訪次數記錄，而「理想狀況下，你建立的是一棵樹，而不是某種完全連通的圖」。因此，從不同祖先節點抵達的相同狀態會是不同節點，各自評估、各自付費——這是設計中已知卻未計價的低效率，也再次說明成本分析缺失為何重要。

相同演算法，但環境是編譯器（2026-08）#

Vamshi 和 Yang（Reward-Oracle MCTS for Formal Theorem Proving: Sample-Efficient Search and the Need for Kernel-Level Proof Auditing，arXiv 2608.28639，empirical）在形式數學中執行結構上相同的搜尋，而兩者的差異恰好就在本頁指出 LATS 較弱的三個地方。其樹節點是自然語言的證明計畫，而不是世界狀態；分解器會將選定節點擴展成 K = 4 個候選下一子目標；生成器會為每個子節點撰寫 S 個完整 Lean 4 證明嘗試；選擇方式為 c = √2 的 UCB；模擬回報則以移動平均回傳。各模型的結果見 Agentic Loops Overtake Bespoke Systems；該研究在基準測試分母中的位置見 AI-Driven Formal Proof Search。

價值函數仍是兩項分數相加，但第二項是可靠的。 LATS 將 LLM 評審的 [0,1] 分數與樣本頻率項相加。此系統則將 LLM 評論者的分數（由 0–100 評分規準正規化而來，以 τ = 0.3 取樣五次後取平均）與 s_k/S 相加——也就是通過 Lean 編譯器檢查的節點證明嘗試比例。形式相同、項數相同，但第二項是由可靠 verifier 測量的成功頻率，而非模型自身先驗所測量的取樣頻率。這是本頁所指出的盲目選擇器的結構性修正：即使某個分支很少被取樣，只要能通過編譯，就能獲得分數；LATS 的頻率項則會把它埋沒。

在這裡，可復原性是免費的，這也是此方法能部署的原因。 本頁對 LATS 最尖銳的批評，是擴展代表執行候選動作，因此搜尋只能在模擬器中運作。編譯候選 Lean 證明不會造成副作用：依照設計，探測和承諾是兩種不同的操作。因此，形式證明搜尋是軌跡樹搜尋最自然的應用環境，也是這種方法不斷出現在該領域的原因（本 wiki 中另一個例子是 Evolutionary Proof Search 的 P-UCB）。

LATS 從未進行的成本分析。 在證明嘗試預算相同的情況下，三角色搜尋比平面取樣少消耗 32.8% 的總推論 token，以及 35.8% 的輸出 token——分解器和評論者的呼叫很短（最多分別輸出 1,024 和 3 個 token），而以明確分解結果為條件的生成器所寫出的證明明顯較短。因此，在這個領域中，搜尋根本不必以測試時運算換取品質，而是呈現 Pareto 優勢。論文也公布了本頁 UCT 討論所需的配置掃描結果：在 N·K·S = 32 固定時，一次寬幅擴展（N=1, K=16）得到 82.1%，四輪各四個（N=4, K=4）得到 84.2%；兩者的分解器呼叫、評論者評估及證明嘗試次數完全相同——因此增益來自中間的反向傳播，而非呼叫預算。最窄的配置（N=16, K=1）只多得 0.1 分，耗時卻是 2.8 倍，而另一種配置是 1.5 倍。

相關連結#

• CS329A: Self-Improving AI Agents (Stanford) — 第 5 堂課介紹的第一篇論文；課程從驗證轉向規劃
• Reasoning–Acting Interleaving (ReAct) — LATS 包在外層的內部迴圈：ReAct 提供思考／動作／觀察單位，LATS 則提供 ReAct 無法做到的分支搜尋、評分與回溯
• Intra-Trace Parallel Planning (SPRINT) — 第 5 堂課介紹的第二篇論文，採取相反的取捨：LATS 在推論時花費更多連續運算來搜尋替代方案；SPRINT 則訓練模型透過同時執行獨立計畫來花費更少運算。兩者在同一堂課都被稱為「規劃」，卻讓延遲朝相反方向變化
• Offline Multi-Step Tool-Use RL (SWiRL) — 第 5 堂課介紹的第三篇論文，也是針對相同問題的訓練時解法：LATS 讓凍結模型周圍的搜尋更徹底，SWiRL 則改變權重，讓第一條軌跡變得更好
• Process vs Outcome Reward Models — LATS 所界定的 verifier 脈絡：Math-Shepherd 以訓練過的 PRM 為推理步驟評分，LATS 則以提示式評審和頻率項為世界狀態評分
• LLM-as-a-Judge — LATS 的價值函數有一半是 0 到 1 的評審提示；搜尋繼承了這種模式已知的可靠性限制
• Large-Scale Test-Time Compute — LATS 是將推論預算花在品質上的行動代理程式版本，而課堂正是如此定位它
• The Verifiability Thesis — 搜尋品質取決於引導它的分數，而自我一致性部分正是這個樞紐用來解釋其限制的選擇器
• Turn-Level Credit Assignment — 同一評分問題在管線另一端的解法：LATS 在推論時沒有梯度地將終端回報沿樹反向傳播；TRACE 則在訓練時將單一軌跡的回報分配給各個回合。回傳公式相似，但更新的對象不同
• Evolutionary Proof Search — 本 wiki 中最接近的既有方法：依 Elo 排名並以 P-UCB 選擇證明草稿族群，也就是同一個 UCB 家族的搜尋，只是以編譯器而非 LLM 評審作為適應度訊號
• Inference-Time Architecture Search — 在不同層次進行搜尋：Archon 離線搜尋管線，LATS 則在線搜尋軌跡
• Stopping Under a Noisy Verifier — 成本分析缺失而必須面對的問題：評分器有雜訊時，增加搜尋不會單調帶來改善；即使回報分數上升，迴圈的真實品質也可能下降
• Compute-Controlled Benchmarking — 這篇論文的主要結果所缺少的評估準則
• Blast Radius (Agentic) — 說明可復原性假設為何是關鍵：擴展節點代表執行該節點，因此沙盒不再只是損害控制措施，而是正確性的先決條件
• Kernel-Level Proof Auditing — 此演算法在形式數學中的實例，以及其 verifier 值得信任的原因：相同的 UCB 樹、相同的雙項價值函數，但第二項是編譯器的接受次數，而非取樣頻率；該頁也衡量回報此數字的 harness 比其背後的 kernel 弱時會發生什麼事
• Azalia Mirhoseini — 授課者
• Selection Under a Submission Budget — 這個方法要解決的需求，是兩堂課之後從程式碼角度重新推導出的結果。大規模單次取樣在困難的競賽程式題上會到達平台期，而課堂本身的結論是需要分解、逐步取樣與回溯——這一頁的搜尋方法，則是在平行替代方案用盡後得出的解法

尚待解答的問題#

• LATS 使用提示式評審加上樣本頻率項為狀態評分，而同一門課也指出，依頻率選擇會忽略罕見但正確的解法。在困難問題上，評審部分能否帶動搜尋，還是頻率部分會佔上風，使這個方法原本要建立的探索能力崩解？對這兩項進行消融即可釐清。2026-09-23 部分解答：Reward-Oracle MCTS for Formal Theorem Proving: Sample-Efficient Search and the Need for Kernel-Level Proof Auditing 在第二項是可靠 verifier 而非樣本頻率的領域中，執行了完全相同的消融：只用評論者分數，對比評論者分數加上編譯通過比例；樹和預算相同，使用五個隨機種子。因此，單靠評審分數無法帶動搜尋——在 DeepSeek-Prover-V2-7B 上移除第二項會使 PAB@32 降低 3.4 分（77.1 → 73.7），在 Goedel-Prover-V2-8B 上則降低 2.6 分（84.2 → 81.6）；預算增加時，差距不減反增。因此，雙項設計具有關鍵作用，而消融測試也容易執行，這是可轉用的部分。此問題仍標記為 #oq/source，因為替代項並非相同對象：LATS 的頻率項測量模型提出某個動作的次數，這項研究測量的則是編譯器接受結果的次數；本問題所關注的罕見正確解盲點，只存在於前者。沒有人對 LATS 自身的兩項分數做過消融。
• 可復原性假設將樹搜尋限制在模擬器中。是否有方法能在不執行候選動作的情況下評分，例如使用學得或提示式的轉移模型？還是對真實世界動作進行搜尋，終究只能「在沙盒中探索，再重播勝出的軌跡」？

資料來源#

• CS329A Self-Improving AI Agents — Part 5: Planning and Multi-Step Reasoning — CS329A Self-Improving AI Agents — Part 5: Planning and Multi-Step Reasoning，Azalia Mirhoseini 個人演講，Stanford Online。於 2025-10-06 進行，2026-08-03 發布至 YouTube（practitioner-opinion，YouTube 自動字幕逐字稿，約 11.3k 字）。課堂中介紹 LATS 的部分：旅程規劃與迷宮導覽、六個階段、雙項價值函數及其 0–1 評審提示、UCT 選擇與移動平均回傳、反思階段、與 Math-Shepherd 和 ReAct 的差異、HotpotQA 和 WebShop 結果，以及承認的限制（沒有成本分析、動作不可復原），並涵蓋關於 bandit 替代方法和重複動作的兩段學生問答。LATS 論文不在 raw/ 中；課堂未說明作者，提供的數字也寥寥無幾，因此本文所有內容都根據 ASR 讀取投影片，並依據證據強度調整措辭