hero

「快 140 倍」聽起來像本地模型忽然換了一顆處理器。Hayder Tirmazi 的文章談的其實是另一件事：在 llama.cpp 的 prompt lookup decoding 中，從既有文字找出下一批候選 token 的程式路徑，原來有不少可以省掉的複製、配置與搜尋。這些改動確實讓草稿產生快得多；但草稿還得交給模型驗證。要讀懂這個數字，得先知道 lookup 怎麼選草稿、作者量了什麼，以及每一輪優化把成本從哪裡拿掉。

原文摘要

一個不用小模型的草稿模型

一般的 speculative decoding 由較便宜的草稿模型先猜幾個 token，再讓目標模型驗證；prompt lookup decoding（也稱 n-gram speculation）則用已出現文字的統計作草稿模型。假設語料中「of the」後面接過「city」六次、「war」三次、「year」一次，lookup 可以提議「city」。這只是候選，並非直接跳過目標模型的決定。所謂 n-gram，是一段連續的 n 個 token；快取記錄某段 n-gram 後面接著各個 token 的次數。官方 lookup 範例 README 列出的 ngram_min、ngram_max 控制要找多長的匹配，n_draft 控制命中後一次先提議多少 token。

llama.cpp 用三種來源不同的快取。context cache 記下正在處理的序列裡長度一至四的 n-gram，隨生成更新；dynamic cache 保留先前執行累積的統計，例如較早的對話；static cache 則由 llama-lookup-create 從固定語料建立長度二的 n-gram 統計。前兩者可以改，靜態快取載入後不再變動。三者都在找「這段後面通常接什麼」，卻不是同一份資料，更不能把大語料的命中等同模型已經接受草稿。

具體挑選從 context cache 的四個 token 後綴開始，依序試四、三、二、一；全都沒有合格候選，才以相同順序查 dynamic cache。對一個候選後繼 token，查前兩種快取時先計分：它在該快取的出現次數，若同時出現在 static cache 的對應二元後綴，乘上靜態次數的 100 倍；沒有靜態支持，權重就是一。取最高分者，但還得通過兩道門：這個 n-gram 後面出現 token 的總次數至少達到最低次數，且選出的 token 本身的出現次數至少占總次數的指定比例。加權分數不能代替後面那道原始計數比例檢查。

以原文採用的 llama.cpp b11182 設定為例，context cache 對長度一至四的最低總次數是（2、2、1、1），最低後繼比例是（0.66、0.5、0.5、0.5）；dynamic cache 分別是（4、3、2、2）與（0.75、0.66、0.66、0.66）。兩者都沒過關時，static cache 才單獨用二元後綴選出最常見後繼；它至少要出現兩次，且占該後綴全部接續的一半。再不合格，這一步就不提出草稿。這些門檻也解釋了為何「找到字串」與「能省下生成時間」之間還隔著統計篩選和模型驗證。

量測：重播文字，不是讓模型回答

作者先以 WikiText-103 訓練文字建立靜態快取，除了不使用靜態快取的 0 MB 對照組，也分別取前 25、50、100、200 MB，及完整約 541 MB 語料；再以 WikiText-103 的測試文字餵給 llama-lookup-stats。這個工具將檔案 token 當成「模型已輸出的文字」重播 lookup 迴圈，統計草稿與文字是否吻合、每個 drafted token 的草稿延遲、靜態快取載入時間和記憶體用量。它沒有讓目標模型真實生成回答，測得的匹配／接受率也不是某款模型在真實工作負載上的驗證接受率。

測試假設 4096-token context；硬體是 14 核、48GB 記憶體的 Apple M4 Pro。各項結果取三次執行的中位數，圖中的誤差線則是最小值與最大值。作者沒有改變 lookup 的選擇規則，因此重點是草稿延遲、載入與記憶體，另檢查接受率與原版幾乎相同。不同大小的語料不是裝飾：沒有 static cache 與載入大型 static cache，在建置成本、常駐記憶體及草稿路徑上都是不同情境。

第一刀：不要每猜一次就複製整張內層 map

原實作把 n-gram 快取做成兩層 std::unordered_map：外層從一段 n-gram 找到內層 map，內層再記錄各個後繼 token 的計數。作者發現草擬時多處把整張內層 map 複製一份，改成以參照讀取。這不是改預測策略，而是停止在熱路徑上重複搬資料。不同語料大小下，每個草稿 token 的延遲因此改善 4.5 至 25.6 倍；以完整語料為例，從 165.48 微秒降至 6.47 微秒。此步對載入時間與峰值記憶體並無同樣的改善，圖上有些數值還略增；不能拿 drafting 的收益冒充整份快取的收益。

第二刀：外層 hash 改成分段成長

移除複製後，作者把外層 map 換成 ankerl::unordered_dense::segmented_map。標準庫的 unordered_map 使用較不利於快取局部性的節點／鏈式結構；較密集的 hash map 有利於查找與載入。但這裡選 segmented_map 而非同套件的普通 map 是關鍵：後者將項目置於會倍增的大 vector，作者在完整 541 MB 語料上遇到最後一次擴容，使峰值記憶體反而達到當時基準的 1.16 倍。分段版本以 4096-byte 區段成長，避免單次搬出另一整份大陣列的峰值。

相對於「不複製 map」那一版，這一步的草稿速度再提升約 1.02 至 1.13 倍，靜態快取載入快 1.41 至 1.65 倍，記憶體用量改善約 1.07 至 1.11 倍。它說明資料結構的「平均操作較快」還不夠；建置大型快取時，擴容瞬間的記憶體尖峰也是要量的結果。

第三刀：小內層 map 用排序陣列，但不能只寫 lower_bound

外層換掉後，每個 n-gram 仍掛著一張內層 hash map。作者檢視 WikiText-103 的靜態快取：64% 的二元 n-gram 只有一種後繼，超過 99% 最多一百種，卻也有少數常見片段帶著大量不同後繼。為每個只有一筆資料的片段維持 hash map 很浪費；直接改成未排序陣列又會讓長尾片段線性掃描過慢。他選排序的（token、count）vector，以二分搜尋保住大量後繼時的查找效率。

第一版用標準 std::lower_bound，草稿反而只剩前一版的 0.89 倍速度。問題不在「二分搜尋複雜度錯了」，而在熱點上每輪比較取回記憶體資料後，還要據此決定剩餘長度和迴圈何時結束；頻繁查找長陣列時，這種相依性拖慢執行。作者改用固定迭代次數的二分寫法：搜尋範圍每次固定縮小，下一輪是否執行不靠本輪讀到的 token 值決定，只有基底指標隨比較結果移動。八筆資料固定走三輪，而非依目標位置走三或四輪。相對上一版，無 static cache 時草稿快約 2.09 倍，有 static cache 時快 1.19 至 1.25 倍；峰值記憶體最多降低到原來約一半，載入時間則大致相近。複雜度同為 O(log n)，實際延遲卻不能只靠大 O 推斷。

第四刀：不會再寫入的 static cache 不必裝成可變容器

排序 vector 還是得讓外層 map 指向各自的後繼。static cache 一旦建立就不再修改，於是作者把它的外層換成 Daniel Lemire 的 verified constmap，把全部（token、count）後繼接成一塊連續陣列。以「of the」為例，map 的值不是一張新的內層表，而是這段後繼在大陣列中的起始位置與筆數；兩者壓在一個 64-bit 值裡，高 40 bit 放位置、低 24 bit 放筆數。查一次 verified map 取得範圍，再沿用上一節的固定迭代二分搜尋找特定 token。序列化檔案由簡短表頭、連續後繼與 constmap 構成；載入時整份讀進 buffer，在其中開啟 map view，而不是重建大量小 map。

相對於排序 vector 版，541 MB 語料的快取載入從 3.76 秒降至 0.23 秒，峰值記憶體從 1.71 GB 降至 1.31 GB；靜態快取本體約用 463 MB，與約 467 MB 的檔案相近。各語料的載入改善為 6.32 至 16.12 倍，有 static cache 的草稿再快 1.06 至 1.20 倍，作者報告所有語料的接受率與排序 vector 版相同。前述四步累計，在作者的測試中最高約 42 倍的仍是「草稿延遲」，不是模型輸出速度。

後續更新：先看有沒有資格，再計算分數

文章更新記錄了 Lemire 提交到作者 fork 的另一個 PR。原本流程先算某個 n-gram 所有後繼候選的加權分數，才檢查最低總次數與後繼比例。新的 precheck 先排除總次數不達門檻的片段；再檢查最常見後繼的原始次數是否足以達到比例門檻。連最多的都不夠，其餘後繼也不可能夠，就沒必要替所有候選計分。這是提前排除不可能合格的案例，沒有把「不合格」偷偷改成「合格」。

作者稱這道預檢疊在原優化上，有 static cache 時草稿最高再快 4.2 倍，沒有時最高約 1.9 倍；對照最初實作，最高可達約 140 倍。這個最高值落在特定語料配置的 drafted-token latency 比較，不是六個語料檔都恰好快 140 倍，更不是端到端生成加速 140 倍。更新圖也單列了載入和峰值記憶體，沒有把 precheck 說成讓這兩項同幅度下降；PR 的存在亦不等於改動已合併進 llama.cpp 上游。

城武觀點

我贊成這種優化，反對把它的分母偷換。這篇最有價值的不是「140 倍」三個字，而是作者把一段常被當成免費的草稿路徑拆開量，甚至承認普通二分搜尋曾經變慢。可是一旦標題走進使用者的世界，草稿時間就被誤認成回答時間。應該並列四張帳：drafting latency、目標模型驗證與真實接受率、快取建置／載入／記憶體、使用者工作負載的端到端時間。若只公布前一張，誰握有語料與量測腳本，誰就能挑選最漂亮的分母；讀者卻得用自己的硬體、長對話與任務替後三張付帳。只有作者可控制的 benchmark 不能替使用者決定體感。真實模型與多種任務的 E2E 結果若也顯著改善，我會改口；在那之前，140 倍只能屬於草稿。

城武的未解檔案——草稿先抵達終點，回答還在驗票口。

來源