從 165 微秒到 1.18 微秒：一場資料結構手術讓 llama.cpp 推測解碼提速最高 140 倍

在一個癡迷於兆級參數模型與十萬 GPU 叢集的產業裡，本週最令人暢快的加速成果，卻來自幾乎堪稱老派的東西：一個雜湊表、一個排序過的向量，以及對 llama.cpp 如何複製它根本不需要複製的資料的仔細檢視。

9 月 26 日，Hayder Tirmazi 發表了一篇詳盡的文章，描述他對 llama.cpp 中 prompt lookup drafting（提示查找草擬）的四項最佳化。llama.cpp 是驅動本地 AI 生態系（包括 Ollama）的 C/C++ 推理引擎。這些修改合計將草擬一個推測 token 的延遲，從最大測試語料庫上的 165.48 微秒降到 1.18 微秒——大約 42 倍的提速。更精彩的是，像路人停下來幫忙推車一樣，資訊科學教授 Daniel Lemire 在此基礎上貢獻了第五項最佳化，把整體提速推到大約 140 倍。

模型權重沒有任何改變。沒有重新發明演算法。草擬 token 的接受率——最終與模型本來就會生成的內容相符的比例——基本保持不變。這是一場純粹的資料結構手術。

Prompt lookup decoding 到底是什麼

推測解碼（speculative decoding）是現代 LLM 推理大多數加速背後的技巧：與其讓大模型一次一個 token 慢慢生成，不如由一個便宜的「草擬」機制往前猜好幾個 token，再讓大模型用一次批次前向傳遞統一驗證。當猜測正確時，你用一次前向傳遞的成本得到多個 token。

Prompt lookup decoding——也稱為 n-gram speculation——是這個想法最便宜的版本。用 Tirmazi 的話說，它是「使用一個真的很蠢的草擬模型、也就是 n-gram 模型」的推測解碼。引擎只需看最後幾個 token，然後問：在這個模型已經見過的文字裡，接下來出現過什麼？

llama.cpp 維護三種 n-gram 快取來回答這個問題。context cache 追蹤當前 token 流中尺寸 1 到 4 的 n-gram。dynamic cache 累積先前執行——更早的對話、更早的連線——的統計資料。static cache 則是用 llama-lookup-create 工具從文字語料庫離線建置，在這次基準測試中儲存來自 WikiText-103 的 2-gram。草擬時會按優先順序查詢這些快取，並套用寫死的接受門檻——例如 context cache 要求 4-gram 至少出現過一次，且最常見的後繼 token 至少佔其中一半的比例。

這套機制幾乎免費，而這正是它的額外開銷如此重要的原因：每個草擬的 token 都要付出一次巢狀雜湊表查找的成本，而在 541 MB 的靜態語料庫上，這些查找耗費的成本遠超過應有的水準。

修正一：別再複製 map

第一個修改，Tirmazi 寫道，「與其說是最佳化，不如說幾乎是個 bug 修正」。內部的 n-gram map 在每個草擬步驟的多個地方被以傳值方式複製，而不是以傳址方式讀取。

僅僅移除這些複製，就讓草擬速度依語料庫大小提升了 4.5 到 25.6 倍。這個數字 quietly 控訴著：可以避免的額外開銷是多麼容易存活在廣泛使用的基礎設施裡——而在所有人都以為已經很快的程式碼中，還留有多少效能空間。

修正二：更好的雜湊表

n-gram 快取原本實作為巢狀的 std::unordered_map——這個容器慢出名已久，因為它用對快取不友善的鏈結串列桶來解決碰撞。Tirmazi 把外層 map 換成 Martin Ankerl 的 unordered_dense，並在發現預設 variant 在完整語料庫上會因最後一次向量倍增反而讓峰值記憶體增加 16% 之後，選擇了 segmented_map variant。後者以 4096 位元組為單位分段成長。

這一步的收益相對温和：靜態快取載入快 1.41–1.65 倍、草擬快 1.02–1.13 倍、記憶體省 7–11%。但它為接下來的結構性改動鋪好了路。

修正三：排序向量與無分支搜尋

真正的洞見來自於看清資料的形狀。對 WikiText-103 靜態快取做了一些街頭數學統計後發現：用於草擬的 2-gram 中，64% 只有一個後繼 token。為每個 n-gram 維護一個雜湊表，對只裝著單一（token, 計數）配對的條目來說是嚴重過度設計。但分佈又很重尾——少數高頻 2-gram 後面接著數千個不同的 token——所以普通向量會讓尾部的搜尋退化。

Tirmazi 的答案是：把後繼 token 存在排序過的 std::vector 裡，讓查找維持 O(log n)。然後他更進一步，重寫了二分搜尋本身。標準的 std::lower_bound 迴圈讓剩餘搜尋長度取決於每次比較的結果，這意味著 CPU 必等記憶體載入完成才能決定是否繼續。他的版本把長度與比較脫鉤——長度每次迭代確定性地減半，處理器可以在先前的載入還在途中的同時，讓多個搜尋並行推進。

成果：無靜態快取時草擬快 2.09 倍、有靜態快取時快 1.19–1.25 倍，峰值記憶體最多降低 1.97 倍。

修正四：建立在 binary fuse filters 上的不可變 map

靜態快取一旦建好就永不改變——這正是 Lemire 最近發表的 constmap 的完美應用場景：一個建立在 binary fuse filters 之上、從字串到整數的不可變映射。Tirmazi 把所有（token, 計數）配對打包進一個連續陣列，讓 constmap 回傳一個把 40 位元位置與 24 位元計數封裝在一起的 64 位元值。靜態快取檔案變成單一緩衝區，直接映射進記憶體，零反序列化。

數字在這裡變得戲劇性：在 541 MB 語料庫上，靜態快取載入時間從 3.76 秒降到 0.23 秒——最高快 16.12 倍。記憶體中的快取現在成本約等於檔案本身（467 MB 檔案對 463 MB 記憶體），峰值記憶體從 1.71 GB 降到 1.31 GB。

Lemire 的臨門一腳：先檢查門檻

文章發表後，Lemire 送出了一個進一步的 pull request，背後是一個優雅到近乎懶惰的觀察：llama.cpp 原本會先對 n-gram 的所有候選後繼 token 計算分數，然後才檢查它們能否通過接受門檻。但如果最高頻的後繼 token 都過不了機率門檻，其他候選也不可能過——所以全部跳過。同樣地，如果 n-gram 的總出現次數低於最低標準，就直接跳過整個計分。

這個重排讓有靜態快取時的草擬再快 4.2 倍、無靜態快取時再快 1.9 倍，把累積提速疊到大約 140 倍。

但書，以及為什麼它仍然重要

所有基準測試都在 Apple M4 Pro（14 核心、48 GB RAM）上執行，用 llama.cpp 的 llama-lookup-stats 工具重播 WikiText-103 測試文字，對象是 b11182 版，取三次執行的中位數，並假設 4096 token 的上下文——這套方法學借自當初引入靜態快取的上游 PR。

有一點但書必須明白說出：截至本文撰寫時，這些 pull request 存在於 Tirmazi 的 llama.cpp fork 上，尚未被上游合併，而伴隨的 Hacker News 討論串（69 分）也浮現了一些關於這些修改提案方式的摩擦。在這些改動進入正式版本之前，主流 llama.cpp 使用者還看不到這些數字。

不過，這堂課並不取決於合併狀態。當整個產業把資本傾注於越來越大的加速器時，本週本地推理最大的百分比增益卻來自一個拿著 profiler 的部落客：消除不必要的複製、讓資料結構符合資料的真實形狀，並重新思考一個 64 年歷史的演算法——二分搜尋——以適應現代的記憶體延遲。AI 效能的前線不只在資料中心。有時候，它就在你與模型之間的那層 C++ 裡。