llama.cpp 提示詞查找解碼快取重構，加速上看140倍
jadidbourbaki/llama.cpp（fork of ggerganov/llama.cpp） · 2026-09-25～2026-09-26
llama.cpp 的提示詞查找解碼（prompt lookup decoding）拿掉了 n-gram 快取每次 drafting 時的隱性複製與雜湊查找開銷，改用連續記憶體結構取代原本要價高昂的 std::unordered_map 巢狀結構。這一連串修改是部落格作者 jadidbourbaki 在自己 fork 的 jadidbourbaki/llama.cpp 上，以一系列尚未合併回上游的 PR 完成，最後一棒是 Daniel Lemire 提交的臨界值預檢 PR #12，時間落在 2026 年 9 月 25 日至 26 日。
背景：drafting 每一步都在重建雜湊表
提示詞查找解碼是推測解碼（speculative decoding）的一種簡化版本：不用真的草稿模型，而是直接查前 n-1 個 token 在語料庫裡最常接哪個字，猜對就省一次大模型前向傳播。問題出在 common/ngram-cache.cpp 的 drafting 迴圈：每次猜測都會把 common_ngram_cache_part 這個 map 整份複製一次，而不是傳參考。疊加上 std::unordered_map 本身鏈結串列式的碰撞處理——桶內元素散落在堆積各處，逐一走訪時 CPU 幾乎每一步都要重新抓一條 cache line，這種「著名地慢」的存取模式，正是後面幾個 PR 要換掉它的原因。優化前，541 MB 語料庫下光是 drafting 就要 165.48 µs/token（PR #2 基準測試，Apple M4 Pro），靜態快取載入更要 5.3 秒；語料愈小，複製開銷占比雖然沒那麼誇張，但 0 MB（空快取）情境下仍要 8.54 µs/token，可見多餘的複製連在最小案例裡都不是能忽略的固定成本。
核心改動：三層優化疊加
PR #2「read ngram cache parts by reference instead of copying」把三處複製改成 const 參考，drafting 直接快4.5x 到 25.6x：0 MB 語料從 8.54 µs/token 降到 1.89 µs/token（4.5x），541 MB 語料從 165.48 µs/token 降到 6.47 µs/token（25.6x），語料愈大改動效益愈明顯；準確率變化「at most 0.15 percentage points」，幾乎不影響猜測命中率。
中間再接兩個結構性替換。PR #5 把外層 map 換成 flat hash map（ankerl::unordered_dense），drafting 再快 1.02x 到 1.13x，載入時間快 1.41x 到 1.65x，記憶體用量降 1.07x 到 1.11x；PR #10 則把內層 map 換成排序陣列，drafting 快 1.19x 到 2.09x，尖峰記憶體降到 1.97x——理由是「64% of 2-grams have one follower」，也就是六成四的 2-gram 只有唯一一個後繼詞，用雜湊表存這種近乎一對一的資料等於殺雞用牛刀，排序陣列配二分搜尋反而更省記憶體又不掉速度。
接著 PR #7「back the static ngram cache with a constmap」把靜態快取換成唯讀的 fastconstmap（vendor 進 vendor/constmap，來源 lemire/fastconstmap），541 MB 語料的載入時間從 3756 ms 降到 233 ms，即「6.32x to 16.12x faster」，同一語料的記憶體用量從 1707 MB 降到 1308 MB，靜態快取本身「1.83x to 2.13x less」，尖峰記憶體「up to 1.30x lower」，drafting 延遲也順帶從 4.78 µs/token 降到 3.98 µs/token。最後 PR #12「Skip parts that can't pass the thresholds」在既有 constmap 之上加一道門檻預檢，直接跳過不可能通過的部分：541 MB 語料下 drafting 從 constmap 版本的 4.29 µs/token 再降到 1.18 µs/token（約 3.64x），對照最初上游基準的 165.48 µs/token，等於整條鏈路疊加起來快了約 140 倍。
| 階段 | 541 MB 語料 drafting 延遲 | 對上游基準倍數 |
|---|---|---|
| 上游基準（優化前） | 165.48 µs/token | 1x |
| PR #2（消除 map 複製） | 6.47 µs/token | 約 25.6x |
| PR #12（+ 門檻預檢，含 Lemire 貢獻） | 1.18 µs/token | 約 140x |
影響範圍：誰該檢查什麼
這串 PR 目前全部停在 jadidbourbaki 自己的 fork，還沒有合併回 ggerganov/llama.cpp 上游，狀態都是 open。正在用 llama.cpp 內建 lookup / --draft 系列做 speculative decoding 的部署，如果想拿到這些數字，短期只能自己 cherry-pick 這幾個 commit（1d43724、51acb8d、b90b281、f764f32 等），或盯著上游何時吸收。
受影響最大的是用大型靜態語料庫（例如 WikiText-103 規模、內部程式碼庫）做 prompt lookup 的場景：PR #2 自己的表格顯示，0 MB 語料只快 4.5x，541 MB 語料卻快到 25.6x，corpus 愈大，原本每次 drafting 都要複製一份 map 的開銷愈驚人，優化後的加速比也跟著愈高；反過來說，如果服務端一直跑的是小型或空的 n-gram 快取，這一輪重構帶來的效益會相對有限，評估時不能只看「約 140x」這個最亮眼的數字。
另外要注意 PR #7 引入了新的靜態快取檔案格式，並改動了 llama-lookup-create 產生的快取檔案，一旦真的合併上游，既有的靜態快取檔需要用新版工具重新產生，不能直接沿用舊檔；vendor/constmap（即 lemire/fastconstmap）也是新加的第三方依賴，做原始碼審查、供應鏈或授權盤點時要一併列入清單。所有基準數字目前只在 Apple M4 Pro（macOS 26.5.1）的 CPU 路徑上量過，其他硬體架構或 GPU 後端搭配 lookup decoding 的實際加速比，原始 PR 都「未說明」，上生產環境前建議先用自己的語料庫與硬體複測一輪，再決定是否要提前 cherry-pick 這幾個尚未合併的 commit。