AI能否像人類一樣“按步驟”推理？一項數學證明的答案
在過去幾年里，大語言模型（LLM）與深度學習的浪潮席卷了幾乎所有計算領域。從醫學診斷到金融建模，從化學分子設計到物理模擬，這些模型在推理任務上的表現一次次刷新了人們的認知。
它們不僅能處理復雜的自然語言，還能跨越模態邊界，將圖像、語音、代碼等信息融會貫通，展現出驚人的“多才多藝”。
然而在這股熱潮背后，一個更為基礎的問題卻始終懸而未決——我們究竟能否量化并刻畫人工智能推理能力的極限？
當前的理論體系對這一問題的回答并不充分。雖然我們知道神經網絡在足夠的訓練和數據條件下具有極強的表達能力，但這種“能力”究竟能延伸到哪些推理類型、能否覆蓋所有可計算的算法、在復雜度上又有何代價，這些問題依然缺乏系統的數學刻畫。
換句話說，我們對“AI推理的邊界”缺乏一個可驗證、可量化的理論框架。
近日，arXiv 熱文《Quantifying The Limits of AI Reasoning:Systematic Neural Network Representations of Algorithms》直面了一個核心問題：在理想化的訓練條件下（無限完美數據與完美優化），神經網絡究竟能執行哪些類型的推理任務？
現有的通用逼近定理雖然證明了神經網絡可以逼近任意連續函數，但它們往往將函數視為“黑箱”映射，忽略了函數背后的算法結構與推理鏈條。這種忽視意味著，我們無法從逼近理論中直接推導出網絡在執行具體推理任務時的復雜度與可行性。
研究目標是通過引入電路復雜度的視角，將推理任務視為電路計算過程，并建立一種系統化的方法，將任意電路精確映射為ReLU前饋神經網絡。
這不僅能量化網絡的推理能力，還能揭示網絡規模與算法運行時間之間的關系，從而為“AI推理極限”提供一個可計算的度量標準。
研究團隊來自加拿大麥克馬斯特大學數學與統計系，并與向量人工智能研究院（Vector Institute）緊密合作。團隊成員在數學邏輯、計算復雜度、神經網絡理論等領域都有深厚積累，既具備嚴謹的理論功底，又熟悉AI前沿應用的需求。
這種跨學科背景，使他們能夠在抽象的數學框架與具體的AI推理任務之間架起橋梁。
1.相關研究與理論基礎
要理解這項工作的意義，必須先回顧通用逼近定理的歷史與局限。上世紀80年代末，Hornik、Cybenko、Funahashi等人的經典結果證明，具有足夠隱藏單元的前饋神經網絡可以在任意精度下逼近任意連續函數。
這一發現奠定了神經網絡表達能力的理論基礎，也為深度學習的興起提供了信心。然而，這類定理關注的是“函數映射”層面的能力——它們并不關心函數是如何被計算出來的，更不涉及計算過程的結構與復雜度。
圖1：比較：經典近似理論與我們的復雜性理論改進。
相比之下，電路復雜度理論則從另一個角度刻畫計算能力。它將算法視為由基本運算單元（門）組成的電路，研究在給定門集下實現某個函數所需的最小電路規模與深度。
不同類型的電路——布爾電路（處理邏輯運算）、算術電路（處理加法與乘法）、熱帶電路（處理最小值與加法）——對應著不同類別的推理任務。
在形式化表示上，這些電路的計算過程可以抽象為有向無環圖（DAG）。DAG的節點代表計算步驟，邊表示數據流動。輸入節點接收原始數據，計算節點執行基本運算，輸出節點給出最終結果。
這種結構化表示不僅揭示了算法的執行順序，也為分析推理鏈條提供了天然的工具。
有趣的是，這種“推理鏈”與大語言模型中的Chain-of-Thought（CoT）概念高度契合。
LLM在多步推理時，會生成一系列中間推斷步驟，逐步逼近最終答案；而在電路模型中，這些中間步驟正對應著DAG中的計算節點。由此，LLM的推理鏈可以被視為一種特殊的電路執行過程，這為將AI推理能力映射到電路復雜度框架中提供了理論基礎。
圖片
圖2：主要結果總結：給定可計算函數作為電路的任何（近似）表示，我們用一個基本的ReLU神經網絡（從預先指定的字典中選擇）替換每個計算節點，該網絡模擬相應的計算。
通過將通用逼近理論與電路復雜度結合，研究團隊為我們提供了一個新的視角：不再僅僅問“神經網絡能否逼近某個函數”，而是問“神經網絡能否高效地模擬計算該函數的算法過程”。這正是量化AI推理極限的關鍵所在。
2.研究方法與核心構造
這項研究的核心，是一套研究團隊稱之為“系統化元算法（Meta-Algorithm）”的構造方法。它的野心很大——無論你手里拿的是布爾電路、算術電路、熱帶電路，還是混合邏輯與算術的復雜計算圖，這個方法都能將它一步步“翻譯”成一個等價的 ReLU 前饋神經網絡，而且是精確模擬，不是近似。
實現的思路很直觀，先把算法抽象成一個有向無環圖（DAG），每個節點就是一個“門”（gate），執行某種基本運算。然后針對每種門類型，事先準備一個標準化的 ReLU MLP模塊作為“模擬器”。
接下來，通過一種被研究團隊形象地稱為“電路手術（Circuit Surgery）”的操作，把原電路中的節點逐一替換成對應的 MLP 模塊，并重新接好輸入輸出的連線。這樣，原電路的計算流程就被無縫嵌入到神經網絡的計算圖中。
這種“手術”有幾個關鍵要求：替換后的網絡必須保持原有的計算依賴關系（Graph Structure Preservation），也就是說，網絡的拓撲結構要和原電路的 DAG 一一對應。
同時，網絡的規?！簿褪巧窠浽蛥档臄盗俊驮娐返膹碗s度成比例（Complexity Mapping），實現空間復雜度與時間復雜度的直接映射。
為了讓這種映射在真實計算機上成立，研究團隊還引入了數字計算模型的細節?，F實中的計算不是在連續實數域上進行的，而是在有限精度的數值網格上運算。
技術論文中明確了模運算（modular arithmetic）和舍入機制（rounding scheme）的定義，并提出了“機器精度下的函數等價性”——如果兩個函數在給定精度的數值網格上輸出完全一致，就認為它們是等價的。這為后續的精確模擬提供了嚴格的判據。
3.主要理論結果
Theorem 1：通用推理（Universal Reasoning）
這是全文的基石性結論。
它斷言任意由特定門集 GG 構成的電路，都可以通過完全無缺陷的“電路手術”轉化為一個 ReLU 前饋網絡，并且在數字計算機上精確復現原電路的功能。
更重要的是，這個網絡的空間復雜度（神經元數量）與原電路的時間復雜度（門數量）同階，計算圖的形狀也與原電路一致。這意味著，神經網絡不僅能“算對”，還能“按原算法的節奏去算”，真正實現了推理過程的結構化保真。
Theorem 2：有限精度下的通用電路設計
如果說 Theorem 1 解決了“能不能模擬”的問題，Theorem 2 則進一步回答了“有沒有遺漏”的疑問。
它證明在有限精度的數值空間上，任何函數都可以由一個 ReLU MLP 精確實現。
這是一個數字計算版本的“超位定理”，與Kolmogorov–Arnold 超位定理在思想上相呼應——后者說任何多元連續函數都可以由單變量函數的疊加表示，這里則說任何有限精度函數都可以由一個通用編碼器網絡加上線性解碼實現。
與經典的通用逼近定理相比，這兩個結果的覆蓋面更廣。通用逼近定理只能保證在無限精度、連續域上的近似，而這里的構造不僅涵蓋了逼近，還涵蓋了推理任務的精確執行，包括邏輯運算、動態規劃、甚至有限步的圖靈機模擬。
換句話說，它不僅回答了“神經網絡能否學會某個函數”，還回答了“神經網絡能否原封不動地執行某個算法”。
圖片
圖3：定理2中構造的最壞情況近似值的說明。
這種從電路到網絡的系統化映射，讓“AI 推理能力”第一次有了可計算、可驗證的數學刻畫，也為未來在復雜推理任務中設計高效、可解釋的神經網絡架構提供了堅實的理論支撐。
4.應用案例分析
在理論框架奠定之后，研究團隊用一系列推論（Corollary）展示了這一方法在不同類型推理任務中的威力。這些案例不僅是數學上的“存在性證明”，更是對神經網絡推理邊界的一次次沖擊。
布爾函數實現復雜度優化（Corollary 1）
傳統上，某些布爾函數的神經網絡實現復雜度會呈現雙指數級增長，這幾乎讓直接模擬變得不可行。
研究團隊通過系統化元算法，將這種復雜度壓縮到單指數級，逼近已知的理論下界。這意味著，在可計算性邊界附近，ReLU 網絡的表達效率被顯著提升，尤其是在需要精確邏輯推理的任務中。
隨機化邏輯電路去隨機化（Corollary 2）
在經典計算理論中，隨機化布爾電路常被用來簡化某些問題的實現。但研究團隊證明，這些電路可以被等價的確定性 ReLU 網絡替代，且不損失功能。
這不僅是一次“去隨機化”的勝利，也為構建可驗證、可審計的推理網絡提供了路徑——畢竟，確定性意味著可重復性和可追溯性。
有限時間圖靈機模擬（Corollary 3）
更具沖擊力的是，研究團隊展示了如何用 ReLU 網絡精確模擬有限步運行的圖靈機，并保留顯式的推理鏈。
這種模擬不是黑箱式的，而是結構上對應原圖靈機的狀態轉移與符號操作，讓網絡的每一步計算都能被解釋為具體的算法步驟。
動態規劃與圖計算（Corollary 4）
在圖計算領域，研究團隊以全點對最短路徑（All-Pairs Shortest Path, ASP）問題為例，構造了一個立方復雜度的 ReLU 網絡實現。
這種實現不僅保留了動態規劃的遞推結構，還在網絡中顯式編碼了圖的拓撲信息，展示了神經網絡在結構化推理任務中的潛力。
圖4：幾何深度學習中圖形的極值示例。
推理能力蘊含通用逼近（Corollary 5）
最后研究團隊指出，如果一個網絡能夠執行上述推理任務，那么它在有限精度下也必然具備通用逼近能力。
換句話說，推理能力本身就涵蓋了函數逼近的能力——而且是精確的、非近似的。這為“推理優于逼近”的觀點提供了堅實的理論支撐。
5.理論意義與創新點
這項工作的意義，不僅在于提出了一個新的構造方法，更在于它建立了一個統一的理論框架，將電路復雜度、可計算性理論與神經網絡的表達能力緊密連接起來。
過去我們常用“通用逼近定理”來描述網絡的潛力，但那只是函數映射的視角；現在，我們有了一個能直接刻畫算法過程的工具。
這種方法的另一個亮點是推理可解釋性。由于網絡的計算圖與原算法的步驟一一對應，我們可以直接在網絡結構中“看到”推理鏈條。這對于需要審計、驗證或調試的高風險應用（如金融合規、醫療診斷）尤為重要。
在復雜度可量化方面，研究團隊明確了網絡規模與算法復雜度之間的關系，使得我們可以在設計階段就預測所需的計算資源。這種可預測性為工程實現和硬件部署提供了堅實的基礎。
最重要的是，這項研究超越了逼近理論的局限。它不再停留在“網絡能否逼近某個函數”的問題上，而是直接回答“網絡能否精確執行某個算法”。這為未來構建具備可驗證推理能力的神經網絡架構打開了新的大門，也為 AI 推理的可計算性研究提供了新的坐標系。
6.未來研究方向
這項研究雖然已經為“神經網絡能否精確執行算法”給出了堅實的理論答案，但研究團隊也清楚，這只是一個起點。未來的探索空間，既有數學上的深水區，也有工程落地的廣闊天地。
首先，是擴展到非歐幾里得與無限維輸入輸出的挑戰。當前的構造主要針對歐幾里得空間中的有限維向量輸入輸出，而現實中的許多推理任務——比如圖結構分析、流形上的信號處理、甚至函數空間上的算子求解——都天然處于非歐幾里得或無限維環境中。
如何在這些空間中定義“電路手術”，并保持計算圖的結構保真，將是下一步的關鍵。這不僅涉及到拓撲與幾何的嵌入問題，還可能引入譜圖理論、核方法等工具，為神經網絡的推理能力開辟新的維度。
其次，是將經典逼近構造（如小波、樣條）轉化為電路表示。小波分解、B樣條插值等方法在信號處理和數值分析中有著成熟的理論與高效的實現，如果能將它們系統化地轉化為電路，再映射到 ReLU 網絡，就能把這些“人類設計的高效基”直接注入到神經網絡的結構中。
這不僅可能帶來更緊湊的網絡規模，還能在特定任務上獲得更強的歸納偏置，讓網絡在訓練樣本有限的情況下依然保持高精度推理。
最后是結合幾何深度學習與算子學習的應用場景，幾何深度學習（Geometric Deep Learning）強調在圖、流形、群等結構化空間中進行學習，而算子學習（Operator Learning）則關注從函數到函數的映射，例如求解偏微分方程或模擬物理系統。
將本研究的“算法到網絡”映射方法與這兩類前沿方向結合，有望構建出既能保留推理鏈條、又能處理復雜結構化數據的通用推理網絡。例如，在分子模擬中，網絡可以直接嵌入化學反應的算法流程；在氣候建模中，網絡可以精確執行數值積分與邊界條件處理。
可以預見，這些方向的推進，將讓神經網絡的推理能力從“能做”走向“能解釋、能泛化、能遷移”，并最終在科學計算、工程設計、金融建模等高價值領域釋放出更大的潛力。（END）
