跳出 BPE 的局部最佳解：用 Convex Optimization 重新思考 Tokenization
大多數人把 tokenizer 當成模型訓練前的固定工序，但這篇新論文提醒我們：tokenization 本身其實就是一個近似最適化問題。當研究者把它從 BPE 這類貪婪法，重寫成可鬆弛、可求界的 convex optimization 問題後，tokenizer 不再只是工程習慣，而開始變成能被系統性設計與驗證的模型基礎設施。
在大型語言模型（LLM）的建構流程中，tokenization 是一個基礎卻常被忽略的關鍵環節。然而，一篇名為《Tokenisation via Convex Relaxations》的論文，其核心價值遠不止於提出 ConvexTok 這個新演算法。更重要的是，它成功地將 tokenization 這個長期依賴經驗法則與工程慣例的領域，提升到一個可以被嚴謹優化、量化驗證，並視為基礎設施設計問題的層次。這項研究為我們提供了一把前所未有的「尺」，讓我們首次能夠衡量當前 tokenizer 距離理論「最佳解」的距離，並在更根本的層次上進行系統性的設計與取捨，為 AI 系統的效率與可靠性奠定新基礎。
Tokenization 的「最佳解」為何如此難以捉摸？
目前，幾乎所有主流的 LLM（例如 GPT 系列或 Llama 系列）都採用 Byte-Pair Encoding（BPE）或其變體作為 tokenization 演算法。BPE 源於一種資料壓縮演算法，其核心思想非常直觀：它會貪婪地（greedily）迭代合併語料庫中最高頻的 token pair，直到詞彙表達到預設的大小。這個方法簡單有效，也成為了業界的 de-facto standard。
然而，「貪婪」的本質也正是 BPE 的侷限。它在每一步都做出局部最佳（locally optimal）的決策，卻無法保證最終產生的詞彙表是全域最佳（globally optimal）的。論文中舉了一個簡潔的例子：
- 假設我們的資料集是
{abc, abd, abe, bc, bd, be}。 - BPE 會先看到
ab出現了 3 次，是最頻繁的 pair，於是優先將其合併為新 token<ab>。這一步節省了 3 個 token 的長度。 - 但在這之後，剩餘的合併選項（例如合併
bc）都只能再節省 1 個 token 的長度。 - 一個更佳的全域策略，其實是合併
<bc>、<bd>、<be>這三個 token。每個組合都出現了 2 次，總共能節省 6 個 token 的長度，優於 BPE 的決策。
這個例子清楚地揭示了問題：尋找一個在給定詞彙表大小下，能最大化壓縮率（即產生最短 token 序列）的 tokenization 方案，本質上是一個 NP-hard 的組合優化問題。這也是為什麼過去的研究者與工程師們，多半滿足於 BPE 或 Unigram Language Model 這類雖非最佳、但已足夠好用的 heuristic 方法。
從組合問題到線性規劃：ConvexTok 如何突破限制？
這篇論文的核心技術貢獻，在於巧妙地繞過了 NP-hard 的正面對決。作者們運用了稱為「多面體技術」（polyhedral techniques）的數學工具，將這個離散的組合問題，轉化為一個連續的優化問題。
整個流程可以這樣理解：
首先，他們將「選擇哪些 byte-substrings 組成詞彙表」這個問題，形式化成一個整數規劃（Integer Program, IP）問題。在 IP 中，每個決策變數都必須是整數（例如 0 或 1），代表一個潛在的 token「被選入」或「不被選入」詞彙表。
接著，他們對這個 IP 進行「鬆弛」（relaxation），將其變為一個線性規劃（Linear Program, LP）問題。最關鍵的差異在於，LP 允許決策變數是連續的實數。也就是說，一個 token 可以是「0.7 成被選入詞彙表」。
雖然「部份的 token」在物理世界沒有意義，但這個經過 convex relaxation 的問題，可以在多項式時間內被現有的 solver 高效地求解，找到一個精確的（或非常接近的）連續解。
最後，再透過設計好的捨入（rounding）策略，將這些包含「部份 token」的連續解，轉換回一個由 0 和 1 組成的離散解，從而建構出一個實際可用的 tokenizer。這個基於 convex optimization 的方法，作者們稱之為 ConvexTok。
我們距離「最佳」的 Tokenizer 有多遠？
ConvexTok 的價值不僅在於它本身是一個性能優越的 tokenizer。更重要的是，在求解 LP 的過程中，它同時提供了一個最佳解的「下界」（lower bound）。
這是一個非常強大的特性。它意味著我們第一次有能力去「證明」（certify）任何一個 tokenizer（無論是 BPE、Unigram 還是 ConvexTok 自己）距離理論上的最佳壓縮率有多接近。過去我們只能說 A 比 B 好，但無法回答「A 距離完美有多遠？」。現在，這個問題有了量化的答案。
論文的實驗結果顯示，在常見的詞彙表大小下，ConvexTok 產生的 tokenizer 在壓縮率上，距離理論最佳解的差距通常在 1% 以內。這是一個驚人的發現，它告訴我們，儘管 tokenization 是個 NP-hard 問題，但透過 LP relaxation 找到的解，品質已經非常高。
實驗數據也表明，ConvexTok 在多項內在指標（intrinsic metrics）上，如壓縮率（bits-per-byte, BpB）和詞彙使用率，都穩定優於 BPE。而在下游任務的表現上，雖然結果不若內在指標那樣一致，但也經常超越 BPE。
把 Tokenization 當成基礎設施來設計，有何意義？
我認為，這篇論文《Tokenisation via Convex Relaxations》最重要的啟示，是促使我們重新思考 tokenization 在 AI 系統中的定位。
長期以來，我們把它當作一個前處理步驟，選用 BPE 這樣的標準演算法，調整一下詞彙表大小，然後就將其視為一個固定的黑盒子。但 ConvexTok 的框架告訴我們，tokenization 本身就是一個值得被嚴謹設計的基礎設施問題。我們可以：
- 明確定義優化目標：我們的目標是最大化壓縮率？還是提升 downstream task 的表現？或是其他指標？不同的目標函數會引導出不同的最佳解。
- 量化評估與權衡：有了最佳解的下界，我們可以量化評估不同演算法的 trade-offs。例如，論文發現 BPE 在不同訓練資料集之間的穩定性（stability）比 ConvexTok 更高。這就是一個具體的工程取捨：我們願意為了追求更高的壓縮率，犧牲多少穩定性？
- 系統性地探索新方法：這個框架為未來的研究開了一扇門。我們可以探索不同的鬆弛技術、設計更精巧的捨入策略，或是將更複雜的約束（例如多語處理的公平性）納入優化模型中。
總結來說，ConvexTok 的出現，不僅僅是演算法工具箱裡多了一個選項。它提供了一套語言和框架，讓我們能將 tokenization 從一個仰賴經驗法則的「手藝活」，轉變為一個有理論支撐、可系統性優化的「工程學科」。這對於建構更高效、更可靠、也更可詮釋的 AI 系統，無疑是至關重要的一步。
延伸閱讀
- Neural Machine Translation of Rare Words with Subword Units (Sennrich et al., 2016): 介紹 BPE 應用於 NLP 的經典論文。
- Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (Kudo, 2018): 介紹 Unigram Language Model tokenizer 的原始論文。
- Convex Optimization (Boyd & Vandenberghe, 2004): 凸優化領域的權威教科書。
我是江中喬，一位具有 TPM 與產品管理背景的 AI 系統建構者，目前專注於 AI 認知增強系統與多 Agent 協作架構的設計與實踐。