機器之心報道
編輯：Panda、佳琪
毫無疑問，現在可說是自回歸大型語言模型（LLM）的時代，我們看到技術叠代，我們也看到套用頻出，但即便如此，也依然有人表示不看好。
唱衰自回歸範式的最著名人物應當是 Yann LeCun 無疑了。他甚至還曾給出過一個相當大膽的判斷：「 從現在起 5 年內，沒有哪個頭腦正常的人會使用自回歸模型。 」詳見機器之心報道【GPT-4 的研究路徑沒有前途？Yann LeCun 給自回歸判了死刑】。
Yann LeCun 在演講中表示自回歸 LLM 會走向末路（doomed）
但現在，DeepMind 和艾爾伯塔大學的一篇論文卻給出了截然相反的見解，其研究結果表明：無需外部幹預或修改模型權重，基於 Transformer 的語言模型的自回歸式解碼就可以實作通用計算。
論文標題：Autoregressive Large Language Models are Computationally Universal
論文地址：https://arxiv.org/pdf/2410.03170
具體來說，這篇論文研究的核心問題是：當使用無界限的思維鏈時，大型語言模型是否可以支持通用計算？
近期很多研究都已經證明，可以透過外部記憶來增強 LLM，從而透過提示來實作對通用圖靈機的模擬。但是，如果使用會將計算責任轉移到語言模型之外的外部控制機制（尤其是正規表式解析工具），則可能削弱這一結果。那無輔助的 LLM 是否能成為通用圖靈機呢？這一問題仍待解答。
DeepMind 的這項研究給出了肯定答案：無輔助 LLM 確實可以模擬通用圖靈機。不知道 Yann LeCun 會如何評價這一結果？
為了做到這一點，需要從一個更普適的視角來看待自回歸解碼，並且其要能處理任意長度的輸入字串。
該團隊研究了自回歸解碼的一種自然泛化，其中在處理每個連續的上下文之後，輸出的 token 都會被添加到序列末端 —— 只要輸入能放入上下文視窗中，則該過程就會簡化成標準的自回歸解碼。
不過，該團隊得到這一結果的過程比較復雜，涉及到一步步地演算推進：
-
首先，針對自回歸解碼，他們給出了一個更通用的視角，其可適用於長輸入字串的情況。
-
他們提出了一種擴充套件，可讓語言模型實作 Lag 系統的一種受限形式。而 Lag 系統則是一種最早的通用計算模型的一個變體。
-
他們又接著證明 Lag 系統不僅能將記憶體組織為迴圈佇列，還可以提供對記憶體存取的雙向控制。
-
在介紹了圖靈機的有限記憶體模擬的相關背景之後，他們又證明任何圖靈機都可由上下文長度為 2 的受限 Lag 系統模擬。他們指出，盡管 Lag 系統的通用性早為人知，但他們給出的證明更加直接，並能為後續證明提供支持。
-
之後，他們將此歸約技術套用於一種特定的通用圖靈機 U_{15,2}，得到了一個通用 Lag 系統，該系統由一組 2027 條產生式規則（production rule）定義，這些規則基於 262 個符號構成的字母表。
-
最後，他們開發了一條系統提示詞，可讓 gemini-1.5-pro-001 這個特定的 LLM 正確地在貪婪解碼下套用那 2027 條規則中的每一條。基於此，該團隊得出結論認為： 擴充套件了自回歸（貪婪）解碼的 gemini-1.5-pro-001 可以精確模擬 U_{15,2} 對任何輸入的執行情況，因此它是一台通用電腦。
下面我們將簡要介紹一下其證明過程，並將重點關註最後一步，更多詳情請參閱原論文。
自回歸解碼與 Lag 系統
語言模型表示的是在給定的輸入字串 s_1...s_n 上，下一個符號 s_{n+1} 的條件分布 p。任何此類模型都可以透過機率鏈式法則擴充套件為輸出序列上的條件分布。
從 (1) 式也能看出，這個過程是自回歸式的，也因此叫做自回歸解碼。演算法 1 總結了上下文長度為 N 的語言模型的確定式自回歸解碼。
該團隊給出的第一個關鍵觀察是：大型語言模型的自回歸解碼可以透過 Lag 系統復現出來。Lag 系統最早由 1963 年的論文【Tag systems and Lag systems】提出，這是通用計算的一種最早的形式模型 Tag 系統的一個簡單變體。
Lag 系統由一組有限的規則 x_1...x_N → y 組成，其中 N 是上下文的長度，x_1...x_N 表示要匹配的符號序列，y 表示相應的輸出。
對於確定性 Lag 系統，每個模式 x_1...x_N 都是唯一的，因此 Lag 系統定義了一個部份函式 L，其可將模式 x_1...x_N 對映成相應的輸出 y。Lag 系統的計算是透過對記憶體字串進行操作來定義的 —— 在每次叠代中，都會有一條規則與記憶體字串的字首匹配，然後結果被附加到字串後面，之後再刪除第一個符號；參見演算法 2。
圖靈機
形式上看，圖靈機 T 由一個元組 T = (Q, Γ, b, q_0, H, f) 組成，其中 Q 是一組有限的狀態，Γ 是一組有限的磁帶符號，b ∈ Γ 是唯一的「空白」符號，q_0 ∈ Q 是唯一的起始狀態，H ⊆ Q×Γ 是一組表示終止的配對的 (狀態，符號)，f : Q×Γ → Γ × Q × {−1, +1} 是一組有限的轉換規則，用於指定該圖靈機在每個計算周期中的操作。
該圖靈機可以存取單向無界的儲存磁帶，因此可以透過自然數 i ∈ N (i > 0) 來索引儲存位置，這樣 i = 1 處有一個最左邊的儲存位置，但沒有最右邊的儲存位置
圖靈機的執行定義如下。
磁帶用一個由有限數量的非空白符號表示的輸入進行初始化，其它所有位置均為空白，T 從狀態 q_0 開始，磁帶頭從指定位置 i_0 開始（預設 i_0 = 1）。
在每個計算周期開始時，T 處於某個狀態 q ∈ Q，磁帶頭位於某個位置 i > 0，當前正在從磁帶讀取符號 γ ∈ Γ。組合 (q, γ) 確定更新 f (q, γ) → (γ′ , q′ , D)，指定符號 γ′ 寫入當前記憶體位置 i，機器狀態 q 更新為 q′ ，磁帶頭移動到 i + D（即根據 D 的符號向左或向右一步）。假設機器永遠不會移出磁帶的左端。計算迴圈重復進行，直到機器遇到配置 (q, γ) ∈ H。不停機計算是可能的。
為便於後續證明，了解可以如何僅使用有限記憶體來模擬圖靈機的計算會很有用。演算法 3 描述了一種標準模擬策略，其中使用新的分隔符 # 來標記存取記憶體的末尾，從而可在必要分時配額外的空間。這使得可以模擬潛在的無限記憶體，而無需分配無限儲存空間。
用 Lag 系統模擬圖靈機
該團隊證明，任意圖靈機都可透過一個受限 (2, 2)-Lag 系統模擬。這是他們得到的第一個主要結果。該證明還意味著任何線性有界自動機都可以用一個受限 (2, 2)-Lag 系統模擬。
之前研究者已經證明 Lag 系統具有計算通用性，但原始的證明依賴於一種少有人知形式的寄存器機（register machine ）的簡化。這裏並不方便利用這個證明。於是，該團隊開發了一種將圖靈機直接簡化為 Lag 系統的方法，從而能在後續論證中利用小型通用圖靈機。
給定一個圖靈機 T = (Q, Γ, b, q_0, H, f)，可以這樣構建其對應的 Lag 系統：Lag 系統將使用字母表
其中 # 是分隔符符號，Q 是來自 T 的有限狀態集（使得空白符號不屬於 Q），Σ_left 和 Σ_right 是位置控制字母表。
也就是說，Lag 系統中的每個符號都是一個三元組，由記憶體符號、狀態符號和位置控制符號組成。
該團隊為該 Lag 系統設計了一些規則，使得其記憶體字串會跟蹤圖靈機模擬演算法 3 中局部變量的狀態。
具體而言，在每次叠代 k ∈ N 開始時，演算法 3 維護一組局部變量：m、n、q 和 i，其中 m 是一個表示當前磁帶內容的陣列、n 是 m 的當前長度、q 是 T 的控制器的當前狀態，i 是磁帶頭的當前位置。
為了映像這些局部變量的值，Lag 系統將維護一個記憶體字串 s，使得序列 m_1...m_{n−1}# 對應於 m，s 的長度為 n，q 對應於相同的控制器狀態，圖靈機磁帶頭的位置 i 由三元組第二個位置中唯一的非空白狀態符號 q 的位置表示。
具體來說，對於給定的圖靈機 T，透過演算法 4 確定的規則集定義相應的滯後系統 L。
這項研究結果表明：基於演算法 4 得到的 Lag 系統 L，演算法 2 可模擬給定圖靈機 T 在任意輸入 γ_1...γ_{n−1} 上執行演算法 3。
一個通用的 Lag 系統
由於論文的主要目標是證明當前的語言模型在擴充套件的自回歸解碼下是計算上通用的，最直接的證明方法就是看看這個模型是否能夠模擬一個已知的、計算上通用的系統。
從本質上來講，任何關於電腦通用性的討論，都要回到大名鼎鼎的「邱奇 - 圖靈」論題。邱奇和圖靈都有過這樣的猜想： 所有電腦制都可以由圖靈機來表達 。圖靈提出了通用圖靈機的概念，它能夠模擬任何計算過程。
鑒於語言模型的自回歸解碼與 Lag 系統在更新時具有類似的機制，因此，很自然地想要透過一個通用的 Lag 系統來證明其通用性。定理 7 為構建這樣一個通用 Lag 系統提供了明確的路徑。
使用語言模型模擬通用 Lag 系統
最後，要證明現有的 LLM 可以模擬通用 Lag 系統 L (U_{15,2}) 在任意輸入字串上的執行情況。該團隊的做法是開發一個特定的提示詞，以讓擴充套件過的自回歸（貪婪）編碼模仿 L (U_{15,2}) 的行為。
他們開發了一個提示策略，其中包含兩個元件：系統提示詞和滑動視窗提示詞。其中系統提示詞提供了完整的規則集，而滑動視窗提示詞會在輸入序列中附加下一個符號對（4 個 token）。
每次叠代過程中，下一個符號對都會附加到系統提示詞中並作為輸入提供給語言模型；然後，語言模型的輸出（2 或 4 個 token）會附加到序列的末尾，如圖 3 所示。
為了確保系統是確定性的，他們將溫度值設定為 0，並固定了定義語言模型行為的所有隨機種子。
為了允許語言模型為每個上下文視窗輸出可變數量的 token ，他們采用了擴充套件自回歸解碼，其中除了 262 個 token 對的基本字母表之外，還使用了一個隱式的隱含終止 token h。
最後，為了驗證擴充套件自回歸（貪婪）解碼是否確實能夠復制 L (U_{15,2}) 的行為，他們挑選了一個特定的 LLM：gemini-1.5-pro-001。幾番實驗之後，他們開發了一個系統提示詞，可讓模型正確執行那 2027 條規則中的每一條。他們將這個系統提示詞稱為 S_gemini。之後他們得出了最終結論。
從這個定理出發，根據「邱奇 - 圖靈」定理，可以得出結論： 在擴充套件自回歸（貪婪）解碼條件下，gemini-1.5-pro-001 是一台通用電腦。 重要的是，實作這一結果不需要引入任何擴充套件自回歸解碼之外的電腦制。
參考連結：
Yann LeCun 演講【From Machine Learning to Autonomous Intelligence】，https://www.youtube.com/watch?v=mViTAXCg1xQ
