編輯：編輯部

【新智元導(dǎo)讀】讓陶哲軒大神贊不絕口的形式化研究神器Lean，運(yùn)行LLM的推理卻有個(gè)bug。最近，加州理工團(tuán)隊(duì)解決了這個(gè)bug，把80%以上的數(shù)學(xué)證明步驟，都自動(dòng)化了！

Lean Copilot，讓陶哲軒等眾多數(shù)學(xué)家贊不絕口的這個(gè)形式化數(shù)學(xué)工具，又有超強(qiáng)進(jìn)化了？

就在剛剛，加州理工教授Anima Anandkumar宣布，團(tuán)隊(duì)發(fā)布了Lean Copilot論文的擴(kuò)展版本，并且更新了代碼庫。

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

最新實(shí)驗(yàn)表明，這個(gè)Copilot工具，可以自動(dòng)化80%以上的數(shù)學(xué)證明步驟了！這個(gè)紀(jì)錄，比以前的基線aesop還要好2.3倍。

并且，和以前一樣，它在MIT許可下是開源的。

而對(duì)此做出巨大貢獻(xiàn)的，是一位華人小哥宋沛洋，他是UCSB的榮譽(yù)CS本科生，加州理工學(xué)院計(jì)算 數(shù)學(xué)科學(xué)（CMS）系的SURF研究員。

網(wǎng)友驚呼：所以，陶哲軒現(xiàn)在的數(shù)學(xué)研究可以原地加速5倍了？

LLM提出證明策略，人類無縫干預(yù)

團(tuán)隊(duì)就發(fā)布了這個(gè)Lean Copilot的工具，希望啟動(dòng)人類和LLM的協(xié)作，編寫出100%準(zhǔn)確的形式化數(shù)學(xué)證明。

它解決了一個(gè)核心技術(shù)挑戰(zhàn)：在Lean中運(yùn)行LLM的推理。

通過這個(gè)工具，我們就可以讓LLM在Lean中提出證明策略，允許人類以無縫的方式干預(yù)和修改。

之所以開發(fā)這個(gè)項(xiàng)目，是因?yàn)樽詣?dòng)化定理證明在如今仍是一項(xiàng)艱巨的挑戰(zhàn)。

我們都知道，LLM在做數(shù)學(xué)和推理任務(wù)時(shí)，時(shí)常會(huì)犯錯(cuò)誤、產(chǎn)生幻覺，十分不可靠。

因此，到目前為止，數(shù)學(xué)證明大多是手動(dòng)推導(dǎo)的，需要仔細(xì)驗(yàn)證。

像Lean這的定理證明工具，倒是可以形式化證明過程的每一步，但人類編寫起Lean，著實(shí)很費(fèi)力。

在這種情況下，Lean Copilot的誕生就顯得意義重大。

讓陶哲軒多次震驚的神器：數(shù)學(xué)家還不會(huì)用就完蛋了

LLM可以作為輔助人類證明定理的工具，這一論點(diǎn)已經(jīng)被陶哲軒多次證實(shí)了。

他前腳剛在博客里預(yù)測(cè)，26年AI將和搜索、符號(hào)數(shù)學(xué)工具結(jié)合，成為數(shù)學(xué)研究中值得信賴的合著者。

緊接著，佐證他觀點(diǎn)的研究就如雨后春筍一般源源不斷地冒出來。

去年6月，加州理工、英偉達(dá)、MIT等機(jī)構(gòu)的學(xué)者，就構(gòu)建了一個(gè)基于開源LLM的定理證明器LeanDojo。

9月，微軟亞洲研究院、北大、北航等機(jī)構(gòu)的研究人員，通過97個(gè)回合的「蘇格拉底式」嚴(yán)格推理，成功讓GPT-4得出了「P≠NP」的結(jié)論，破解了這個(gè)千禧年難題。

在第97輪對(duì)話中，GPT-4得出結(jié)論，證明示例在沒有窮舉法的情況下無法求解，證明了結(jié)論為P≠NP

去年10月，陶哲軒在GPT-4、Copilot的幫助下，直接發(fā)現(xiàn)了自己論文中的一處隱藏bug。

在用Lean4形式化第6頁論點(diǎn)的過程中發(fā)現(xiàn)，他發(fā)現(xiàn)表達(dá)式

在n=3,k=2時(shí)，實(shí)際上是發(fā)散的。

這個(gè)不太容易看出的bug能被及時(shí)捉住，多虧了Lean4。原因是，Lean要求他構(gòu)建0<n?3，但陶哲軒只假設(shè)了n>2。由此，Lean無法基于負(fù)的0<n?3得到反證。

這一發(fā)現(xiàn)直接讓陶哲軒瞳孔震驚。

而在去年年底，陶哲軒直接成功地用AI工具，完成了形式化多項(xiàng)式Freiman-Ruzsa猜想證明過程的工作。

最后，依賴關(guān)系圖已經(jīng)完全被綠色所覆蓋，Lean編譯器也報(bào)告說，這個(gè)猜想完全遵循標(biāo)準(zhǔn)公理。

在這個(gè)過程中，所有最前線的數(shù)學(xué)研究者，都在第一時(shí)間感受到了AI對(duì)于數(shù)學(xué)研究顛覆力量的直接沖擊。

Lean Coilot，讓Lean更好用

而今天，Lean Copilot的這項(xiàng)研究，讓Lean直接變得更強(qiáng)大了。

在這篇論文中，團(tuán)隊(duì)基于Lean Copilot構(gòu)建了一些工具，用于建議證明步驟（策略建議）、完成中間證明目標(biāo)（證明搜索）和使用LLM選擇相關(guān)前提（前提選擇）。

實(shí)驗(yàn)結(jié)果也充分表明了，跟Lean中現(xiàn)有的基于規(guī)則的證明自動(dòng)化相比，Lean Copilot在輔助人類自動(dòng)化定理證明上，是有效的。

Lean Copilot提供了一個(gè)通用框架，可以通過CTranslate 2在本地，或者在服務(wù)器上運(yùn)行LLM的推理。

通過這個(gè)框架，用戶就能創(chuàng)建各種自動(dòng)化證明工具。

Lean是一個(gè)在數(shù)學(xué)家中很受歡迎的證明助手。如下圖所示，Lean中的一個(gè)證明，是由一系列被稱為策略（Tactics）的證明步驟組成。

從整個(gè)定理開始作為初始目標(biāo)，策略反復(fù)地將當(dāng)前的目標(biāo)轉(zhuǎn)化為更簡單的子目標(biāo)，直到所有目標(biāo)都被解決。

用戶在由VSCode驅(qū)動(dòng)的IDE中交互編寫策略，在右邊的infoview面板中顯示目標(biāo)。

生成策略建議

利用Lean Copilot，團(tuán)隊(duì)構(gòu)建出了suggest_tropics，一種用LLM生成策略建議的工具。

而它本身，也是一種策略。

應(yīng)用時(shí)，它將當(dāng)前目標(biāo)輸入LLM，并且從LLM獲取生成的策略候列表。

它會(huì)查看每個(gè)選項(xiàng)，看它們是否會(huì) 1）導(dǎo)致錯(cuò)誤；2）結(jié)果沒有錯(cuò)，但不能完成證明；3）順利完成證明。

如果是1），這個(gè)策略就會(huì)被刪除。

只有無錯(cuò)誤的策略，才會(huì)顯示在右邊的視圖面板中。

其中，成功完成證明的策略，使用綠色標(biāo)記（類別3）；沒有錯(cuò)誤改變證明目標(biāo)，但未完成證明的策略，使用藍(lán)色標(biāo)記（類別2）。

注意！當(dāng)所有列出的策略都屬于類別2時(shí)，這個(gè)信息對(duì)于用戶來說，可能極有價(jià)值。

在這種情況下，剩余目標(biāo)的信息，可以直接幫助用戶選擇策略，作為下一個(gè)中間證明步驟。

看到建議后，用戶可以選擇是否接受，或使用它們作為靈感來源，制定新策略。

比如，我們?cè)贚ean代碼中定義了一個(gè)定理add_abc，它的初始目標(biāo)如圖3右所示。

當(dāng)我們輸入suggest_tropics時(shí)，會(huì)在右邊看到策略建議。

第一個(gè)策略顯示為綠色，表示證明已成功完成。

接下來三個(gè)建議均為藍(lán)色，這就表明無法直接完成證明，但不會(huì)導(dǎo)致錯(cuò)誤。

因而，它們很有可能是有效的中間證明步驟！

同時(shí)，剩余子目標(biāo)也顯示了出來。

而Tactic state字段顯示No goal，是因?yàn)橹辽儆幸粋€(gè)策略建議可以被證明。

搜索完整證明

此外，因?yàn)槿祟惡蜋C(jī)器都不能始終如一地產(chǎn)生正確的策略，因此在這個(gè)過程中必須回溯、探索不同的替代方案，這個(gè)過程就是證明搜索。

當(dāng)是上面所說的Suggest_tropics，僅能生成當(dāng)前步驟的策略，不具備搜索多策略證明的能力。

為此，團(tuán)隊(duì)將其與基于規(guī)則的證明搜索工具aesop結(jié)合起來，構(gòu)建了一個(gè)基于LLM的證明搜索工具。

Aesop會(huì)將最佳優(yōu)先搜索作為Lean的策略實(shí)施，并且允許用戶配置搜索樹的擴(kuò)展方式。

搜索樹是由作為節(jié)點(diǎn)的目標(biāo)組成。

起初，它只有原始目標(biāo)作為根節(jié)點(diǎn)。在每一步中，aesop都會(huì)選擇最有希望的未擴(kuò)展節(jié)點(diǎn)，通過應(yīng)用策略對(duì)其擴(kuò)展，將生成的節(jié)點(diǎn)添加為子節(jié)點(diǎn)。

而當(dāng)aesop找到一條從根源到可輕松解決的目標(biāo)的路徑，就證明搜索成功了！

因此，aesop的性能關(guān)鍵取決于用戶是否配置了有效的規(guī)則集。

這就可以看出，aesop缺乏靈活性。因此，Search_proof通過在每一步中由suggest_tropics生成的目標(biāo)相關(guān)策略，來增強(qiáng)aesop的規(guī)則集，讓它變得更加靈活。

對(duì)于圖3中的原始目標(biāo)，用戶只需輸入search_prrof，找到可以解決目標(biāo)的完整證明，就顯示在了信息視圖中（圖5右）。

可以看到，由于發(fā)現(xiàn)了成功的證據(jù)，所以剩余的Tactic state是No goals。

選擇注釋好的前提

此外，定理證明中另一項(xiàng)具有挑戰(zhàn)性的重要任務(wù)是，找到減少或完成證明的相關(guān)前提。

除了源碼庫和標(biāo)準(zhǔn)庫中有大量前提，Lean還有一個(gè)大型數(shù)學(xué)庫（MathLib）。

然而，從所有庫中搜索候選前提，極其困難且耗時(shí)耗力。

所以許多人都試圖，能在Lean，或其他的證明助手中得到輔助，或自動(dòng)完成這一過程。

在Lean中，最先進(jìn)的前提選擇方法是，直接在Lean中實(shí)現(xiàn)的基于隨機(jī)森林（random forest）的框架。

然而，前提選擇任務(wù)非常適合檢索增強(qiáng)型LLM，即在大模型訓(xùn)練期間訓(xùn)練檢索矩陣（前提嵌入），以估計(jì)證明目標(biāo)與候選前提之間的相關(guān)性。

給定推理時(shí)的證明目標(biāo)，首先將目標(biāo)編碼成一個(gè)向量，然后在前提嵌入和目標(biāo)向量之間執(zhí)行矩陣向量乘法。

然后，為了選擇前k個(gè)前提（其中k可以是一個(gè)超參數(shù)，決定用戶想要返回多少個(gè)前提），這時(shí)只需返回得分最高的k個(gè)前提。

而要在Lean中執(zhí)行推理任務(wù)，除了Lean Copilot提供的快速推理外，還需要一個(gè)高效的矩陣乘法庫和一個(gè)C 的numpy矩陣閱讀器。

研究人員采用了來自CTranslate2的矩陣乘法函數(shù)，和來自Libnpy的C 快速numpy文件閱讀器。

他們?cè)俅瓮ㄟ^FFI機(jī)制，將這些數(shù)鏈接到Lean。

因此，前提選擇的策略可以非常高效地運(yùn)行，因?yàn)榍疤崆度肟梢灶A(yù)先計(jì)算，所有后續(xù)操作都可以使用上文介紹的庫在C 中快速完成。

在獲得返回的前提后，研究者進(jìn)一步用有用的信息對(duì)其進(jìn)行注釋。

這里將所有前提所分為兩類：可直接在當(dāng)前環(huán)境中使用的前提（范圍內(nèi)前提）和不可直接在當(dāng)前環(huán)境中使用的前提（范圍外前提）。

這取決于是否導(dǎo)入了所需的軟件包。

如果已經(jīng)導(dǎo)入了前提所需的包，則可以輕松使用該前提。如下圖6顯示了帶注釋的范圍內(nèi)前提。

圖7所示是帶注釋的范圍外前提。

下面舉個(gè)使用「前提選擇」的例子，對(duì)于圖3中的定理add_abc，可以直接在證明中輸入select_premises（圖8左）。

然后，相關(guān)前提的列表，就會(huì)出現(xiàn)在信息視圖中（圖8右）。

對(duì)于這個(gè)簡單的定理，可以清晰看到所選的前提確實(shí)相關(guān)，因?yàn)樗鼈兌寂c自然數(shù)和加法規(guī)則有關(guān)。

在這種情況下，所選的4個(gè)前提都在當(dāng)前范圍內(nèi)，這意味著它們的模塊已經(jīng)導(dǎo)入。

如上，便是研究人員通過Lean Copilot構(gòu)建的三個(gè)實(shí)用的證明自動(dòng)化工具，用于策略建議、搜索證明和前提選擇。

81.2%的證明步驟，全都自動(dòng)化了

通過Lean Copilot框架，研究人員憑經(jīng)驗(yàn)提出了假設(shè)——在Lean交互式定理證明（ITP）中進(jìn)行人機(jī)協(xié)作是有益的。

由于Lean中的定理證明過程，主要以策略證明為主。

因此，在具體實(shí)驗(yàn)中，作者主要評(píng)估了用于「策略建議」，以及「證明搜索」的證明自動(dòng)化工具。

總而言之，aesop是當(dāng)前是一種用于證明搜索，最先進(jìn)的基于規(guī)則的證明自動(dòng)化工具。

研究人員在兩種情況下，驗(yàn)證了基于LLM的搜索證明與aesop相比的有效性：

（1）自主證明定理（LLM獨(dú)立完成）

（2）協(xié)助人類進(jìn)行定理證明（人類與AI協(xié)作）

此外，研究者還將搜索證明與策略建議進(jìn)行了比較，以證明除了單一策略建議之外，搜索證明體現(xiàn)的優(yōu)勢(shì)。

研究Lean Copilot如何有效地幫助人類進(jìn)行ITP的過程，類似于人類在軟件編程中使用Copilot的范式。

也就是說，當(dāng)我們面對(duì)一個(gè)目標(biāo)時(shí)，首先會(huì)調(diào)用Copilot，看其是否可以直接解決問題。

如果不能，我們會(huì)進(jìn)一步簡化目標(biāo)，然后再次嘗試Copilot。然后，一直重復(fù)上述過程，直至Copilot成功解決剩余目標(biāo)。

而研究人員便是通過這樣的迭代協(xié)作范例中，去查看每個(gè)證明自動(dòng)化工具可以自動(dòng)化多少人力。

具體結(jié)果，如下表1顯示。

證明搜索（search_proof）可以自動(dòng)證明64%的定理（50個(gè)中的32個(gè)），明顯高于aesop和策略建議（suggest_tropics）。

當(dāng)用于輔助人類時(shí)， 證明搜索僅需要平均1.02個(gè)手動(dòng)輸入策略，這也比aesop（3.62）和策略建議（2.72）更好。

最后，對(duì)于每個(gè)測(cè)試的定理，作者計(jì)算了三個(gè)工具中每一個(gè)可以自動(dòng)化的證明步驟的百分比。

結(jié)果發(fā)現(xiàn)，證明搜索可以自動(dòng)完成定理中約81.2%的證明步驟，明顯高于策略建議（48.6%）和aesop（35.2%）。

總之，證明搜索的性能比策略建議，要高出1.67倍，比基于規(guī)則的基線aesop高2.31倍。

通過Copilot在Lean中進(jìn)行本地LLM推理

Lean Copilot中的tactic建議、證明搜索和前提選擇，這三個(gè)任務(wù)在本質(zhì)上可能看起來不同，但對(duì)于用戶體驗(yàn)的要求是相似的。

它們都需要足夠快速地生成響應(yīng)，具有適中的計(jì)算需求，同時(shí)在Lean中運(yùn)行。

用戶之所以有這些要求，是因?yàn)長ean本身在大多數(shù)情況下都能非?？焖俚靥峁┉h(huán)境反饋（比如剩余目標(biāo)，錯(cuò)誤信息，類型信息等）。

這種快速，跟證明定理的本質(zhì)是一致的——它需要連貫的推理。

如果Lean Copilot需要用戶等待很長一段時(shí)間，那么人類和AI之間的協(xié)作就很難發(fā)揮作用。

同樣，我們也非常希望滿足低計(jì)算的需求。因?yàn)長ean中的定理證明本身不需要GPU，可以在用戶本地的筆記本電腦上運(yùn)行。

因此，能夠在大多數(shù)硬件（包括沒有GPU的筆記本電腦）上高效運(yùn)行，對(duì)于Lean的用戶就非常重要。

因?yàn)橛脩粼诰帉懽C明時(shí)，可能無法訪問支持CUDA的GPU。

因?yàn)樾枰獫M足快速推理和低計(jì)算需求，而且所有流行的高效深度學(xué)習(xí)框架都是在Python中，團(tuán)隊(duì)想到的一個(gè)自然的解決方案，就是在Python中托管模型(本地或遠(yuǎn)程)，然后從Lean向模型發(fā)出請(qǐng)求。

然而，這種方法會(huì)受到進(jìn)程間通信的開銷的影響，并且它需要用戶執(zhí)行額外的設(shè)置步驟，并不適合Lean的傳統(tǒng)工作流程。

為了克服這些問題，Lean Copilot通過外部功能接口(FFI)在Lean中本地運(yùn)行LLM。

FFI是一種機(jī)制，可以用一種語言編寫的程序調(diào)用另一種語言的子程序。

Lean部分用c 實(shí)現(xiàn)，可以與c 高效互操作。

程序員可以在Lean中聲明一個(gè)函數(shù)，但在c 中實(shí)現(xiàn)函數(shù)體。實(shí)現(xiàn)會(huì)被編譯到一個(gè)共享庫中，并動(dòng)態(tài)鏈接到Lean。

默認(rèn)情況下，我們采用的是LeanDojo預(yù)訓(xùn)練的repver模型。它基于一個(gè)編碼器-解碼器轉(zhuǎn)換器，BVT5，它將輸入字符串映射到輸出字符串。

Lean Copilot通過將模型包裝成一個(gè)對(duì)字符串操作的c 函數(shù)，使其在Lean中可運(yùn)行，該函數(shù)可以通過FFI在精益中調(diào)用。

華人作者立大功

最新論文中的三人團(tuán)隊(duì)，也是23年6月開源平臺(tái)LeanDojo其中的作者。

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

Peiyang Song（宋沛洋）

宋沛洋是加州大學(xué)圣巴巴拉分校創(chuàng)意研究學(xué)院（CCS）的計(jì)算機(jī)科學(xué)榮譽(yù)本科生，導(dǎo)師是Richert Wang和Phill Conrad 。

與此同時(shí)，他還是加州理工學(xué)院計(jì)算與數(shù)學(xué)科學(xué)系（CMS）的SURF研究員，由Anima Anandkumar教授和Kaiyu Yang博士共同指導(dǎo)。

另外，他還是UC伯克利建筑實(shí)驗(yàn)室的研究員，與Tim Sherwood和Dr. Jeremy Lau（谷歌）一起合作。

他的研究興趣是機(jī)器學(xué)習(xí)（ML），涉及自然語言處理（NLP）和計(jì)算機(jī)視覺（CV）等應(yīng)用領(lǐng)域，以及系統(tǒng)和編程語言（PL）等基礎(chǔ)理論。

宋沛洋最近的研究主要有兩個(gè)方向。

一是神經(jīng)符號(hào)推理和人工智能數(shù)學(xué)（AI4Math），將大模型與交互式定理證明器（ITPs）相結(jié)。

另一個(gè)是基于時(shí)序邏輯的高能效機(jī)器學(xué)習(xí)。

Kaiyu Yang（楊凱峪）

楊凱峪是加州理工學(xué)院計(jì)算 數(shù)學(xué)科學(xué)（CMS）系的博士后研究員，導(dǎo)師是Anima Anandkumar。

他曾在普林斯頓大學(xué)獲得了博士學(xué)位，導(dǎo)師是Jia Deng，還曾與Olga Russakovsky、陳丹琦一起工作。

他的研究重點(diǎn)是神經(jīng)符號(hào)人工智能，旨在使機(jī)器學(xué)習(xí)能夠進(jìn)行符號(hào)推理，希望通過兩個(gè)方向?qū)崿F(xiàn)：

（1）將機(jī)器學(xué)習(xí)應(yīng)用于符號(hào)推理任務(wù)，如形式邏輯或自然語言中的數(shù)學(xué)推理和定理證明；

（2）將符號(hào)組件引入機(jī)器學(xué)習(xí)模型，使其更具可解釋性、可驗(yàn)證性和數(shù)據(jù)高效。

目前，他正在研究能夠理解和推理數(shù)學(xué)的人工智能。數(shù)學(xué)推理是人類智能的一個(gè)重要里程碑，它有可能改變科學(xué)和工程中的許多重要問題，比如解決偏微分方程和公式驗(yàn)證。

Anima Anandkumar

Anima Anandkumar現(xiàn)在是加州理工學(xué)院計(jì)算和數(shù)學(xué)科學(xué)教授。

她的研究興趣主要集中在大規(guī)模機(jī)器學(xué)習(xí)、非凸優(yōu)化和高維統(tǒng)計(jì)等領(lǐng)域。

特別是，她一直在帶頭開發(fā)和分析機(jī)器學(xué)習(xí)的張量算法。

張量分解方法具有極高的并行性和可擴(kuò)展性，可應(yīng)用于海量數(shù)據(jù)。它可以保證收斂到最優(yōu)解，并對(duì)許多概率模型（比如Markov模型）輸出一致的估計(jì)結(jié)果。

更廣泛地說，Anandkumar教授一直在研究加速非凸優(yōu)化的高效技術(shù)。

參考資料：

https://arxiv.org/abs/2404.12534

https://github.com/lean-dojo/LeanCopilot

https://twitter.com/AnimaAnandkumar/status/1782518528098353535