Refix Caching 詳解：實現 KV Cache 的跨請求高效復用

作者：Se7en的架構筆記 2025-06-12 09:10:21

前綴緩存（Prefix Caching）是一種大語言模型推理優化技術，它的核心思想是緩存歷史對話中的 KV Cache，以便后續請求能直接重用這些中間結果。這樣可以顯著降低首 token 延遲，提升整體推理效率。Prefix Caching 尤其適用于多輪對話、長文檔問答等高前綴復用場景。

Prefix Caching 原理的講解視頻可以在這里觀看：https://www.bilibili.com/video/BV1jgTRzSEjS

本文是 vLLM 系列文章的第 3 篇，介紹 vLLM 中 Prefix Caching 的實現原理。

1 什么是 Prefix Caching

前綴緩存（Prefix Caching）是一種大語言模型推理優化技術，它的核心思想是緩存歷史對話中的 KV Cache，以便后續請求能直接重用這些中間結果。這樣可以顯著降低首 token 延遲，提升整體推理效率。Prefix Caching 尤其適用于多輪對話、長文檔問答等高前綴復用場景。

Prefix Caching 在大語言模型推理中的應用場景主要包括以下幾類：

圖片

Few-shot learning（少樣本學習）：多個請求都包含相同的 few-shot 示例部分，只是最后的問題不同。Prefix Caching 可以將這些 few-shot 示例的 KV Cache 復用，避免每次都重新計算相同的示例內容。
Self-consistency（自洽性）：對于同一個問題，先采樣多個不同的推理路徑（重復請求多次），然后選擇最一致的答案。這些請求都共享相同的前綴（問題部分），Prefix Caching 可以讓每次 decode 時都直接復用問題部分的緩存，只計算不同的答案部分。
Multi-turn chat（多輪對話）：多輪對話中，每一輪的對話都基于之前的聊天歷史。Prefix Caching 允許每一輪都復用之前聊天歷史的KV緩存，只對新增的問答部分進行計算。
Tree-of-thought（思維樹）：復雜推理任務中，一個問題會被分解成多個分支，每個分支下又有進一步的分支。每個分支都共享前面的搜索歷史作為前綴。Prefix Caching 可以讓所有分支共享公共的歷史部分緩存，只對各自獨立的分支內容做增量計算。

Prefix Caching 只會減少處理查詢（prefill 階段）的時間，而不會減少生成新 token（decode 階段）的時間。

2 PagedAttention 和 Prefix Caching 的關系

PagedAttention 主要解決 KV Cache 如何在 GPU 顯存中“按需分配”，通過分頁機制讓 KV Cache 可以非連續存儲和動態擴容，極大緩解內存碎片化問題，實現高效的內存管理。
Prefix Caching 則專注于“避免重復算”，即當多個請求有相同的 prompt 前綴時，只需計算一次并緩存其 KV，后續請求直接復用，顯著降低首 token 時延，尤其適合多輪對話和長 system prompt 場景。

維度	PagedAttention	Prefix Caching
關注點	高效管理 KV Cache 的內存分配與碎片化	復用請求間公共前綴的 KV Cache，減少重復計算
作用階段	整個推理過程，包括 prefill 和 decode 階段	prefill 階段（推理開始前處理 prompt）
是否涉及跨請求	主要用于單個請求內部的緩存管理	針對不同請求間的共享前綴
技術原理	受操作系統虛擬內存分頁啟發，將 KV Cache 分塊（block）動態分配和管理	通過哈希、基數樹等結構檢測和緩存相同前綴的 KV，跨請求復用
主要作用	解決 KV Cache 占用大、內存碎片嚴重、動態擴展難等問題，提升顯存利用率和吞吐量	避免對相同前綴重復計算，顯著降低首 token 延遲，提升多輪對話等場景效率
典型應用	任何高并發、長序列推理場景	長 system prompt、few-shot、對話歷史復用、多輪對話等

3 RadixAttention

論文 SGLang: Efficient Execution of Structured Language Model Programs 中提出通過 RadixAttention 來實現Prefix Caching。

圖片

上圖展示了采用 LRU 淘汰策略的 RadixAttention 操作示例，描繪了 Radix Tree（基數樹）在不同請求作用下的動態演化過程。這些請求包括兩個對話會話、一批 few-shot 學習查詢，以及一次自洽性采樣（self-consistency sampling）。樹的每條邊標注了一個子字符串或一段 token 序列，節點則通過顏色編碼以區分不同狀態：

綠色表示新添加的節點，
藍色表示當前時間點訪問到的緩存節點，
紅色表示已經被淘汰的節點。

具體步驟如下：

步驟(1)：Radix Tree 初始為空。
步驟(2)：服務器接收到用戶消息 "Hello"，并生成 LLM 回復 "Hi"。系統提示 "You are a helpful assistant"、用戶消息 "Hello!" 和模型回復 "Hi!" 被整合為一條邊，并連接到一個新節點。
步驟(3)：新的 prompt 到達，服務器在樹中找到了該 prompt 的前綴（即第一輪對話），并重用其 KV cache。新的對話輪次作為新節點追加進樹中。
步驟(4)：開啟新的對話會話。為了讓兩個會話共享系統提示，“b” 節點被拆分成兩個節點。
步驟(5)：第二個會話繼續，但由于內存限制，第 (4) 步中的 “c” 節點被淘汰。新的輪次被追加在 “d” 節點之后。
步驟(6)：服務器收到一個 few-shot learning 查詢，將其插入樹中。由于該查詢和現有節點沒有公共前綴，根節點被拆分。
步驟(7)：服務器收到一批新的 few-shot learning 查詢。它們共享相同的 few-shot 示例，因此將 (6) 中的 “e” 節點拆分以實現共享。
步驟(8)：服務器收到來自第一個對話會話的新消息。由于使用 LRU 策略，第二個對話的所有節點（如 “g” 和 “h”）被淘汰。
步驟(9)：服務器收到一個請求，要求對 (8) 中 “j” 節點的問題進行更多回答采樣，可能是用于自洽性采樣（self-consistency sampling）。為了騰出空間，第 (8) 步中的 “i”、 “k”、 “l” 節點被淘汰。

4 vLLM 中的 Prefix Caching

最初，vLLM 支持手動前綴緩存，用戶需通過 prefix_pos 參數顯式指定前綴邊界位置。

PR：https://github.com/vllm-project/vllm/pull/1669

從 v0.4.0 版本開始，vLLM 引入了自動前綴緩存（Automatic Prefix Caching），無需手動指定即可自動識別并復用共享前綴。

PR：https://github.com/vllm-project/vllm/pull/2762

4.1 在 vLLM 中啟用 Prefix Caching

4.1.1 環境準備

執行以下命令安裝 vLLM。

# 安裝 uv，管理 python 虛擬環境
curl -LsSf https://astral.sh/uv/install.sh | shsource$HOME/.local/bin/env# 安裝 GPU Driverwget https://cn.download.nvidia.com/tesla/565.57.01/NVIDIA-Linux-x86_64-565.57.01.runsh NVIDIA-Linux-x86_64-565.57.01.run --silent# 安裝 CUDA Toolkit（如 nvcc、include、lib64）sudo apt updatesudo apt install -y nvidia-cuda-toolkit# 創建 python 虛擬環境uv venv vllm-demo --python 3.12 --seedsource vllm-demo/bin/activate# 安裝 vLLMuv pip install vllm

4.1.2 離線推理（Offline Inference）

在 vLLM 中設置 enable_prefix_caching=True 可以啟用 Automatic Prefix Caching。下面這段代碼展示了 vLLM 的 Automatic Prefix Caching 功能：第一次生成關于 "John Doe 年齡" 的回答時，需要完整構建 KV Cache；而第二次詢問 "Zack Blue 年齡"，由于兩次問題共享相同的長表格前綴，vLLM 會自動復用已有緩存，從而顯著減少重復計算，加速生成過程。

import time
from vllm import LLM, SamplingParamsLONG_PROMPT = (    "You are a helpful assistant in recognizes the content of tables in markdown format. Here is a table as follows.\n# Table\n"    + """
| ID  | Name          | Age | Occupation    | Country       | Email                  | Phone Number   | Address                       ||-----|---------------|-----|---------------|---------------|------------------------|----------------|------------------------------|| 1   | John Doe      | 29  | Engineer      | USA           | john.doe@example.com   | 555-1234       | 123 Elm St, Springfield, IL  || 2   | Jane Smith    | 34  | Doctor        | Canada        | jane.smith@example.com | 555-5678       | 456 Oak St, Toronto, ON      || 3   | Alice Johnson | 27  | Teacher       | UK            | alice.j@example.com    | 555-8765       | 789 Pine St, London, UK      || 4   | Bob Brown     | 45  | Artist        | Australia     | bob.b@example.com      | 555-4321       | 321 Maple St, Sydney, NSW    || 5   | Carol White   | 31  | Scientist     | New Zealand   | carol.w@example.com    | 555-6789       | 654 Birch St, Wellington, NZ || 6   | Dave Green    | 28  | Lawyer        | Ireland       | dave.g@example.com     | 555-3456       | 987 Cedar St, Dublin, IE     || 7   | Emma Black    | 40  | Musician      | USA           | emma.b@example.com     | 555-1111       | 246 Ash St, New York, NY     || 8   | Frank Blue    | 37  | Chef          | Canada        | frank.b@example.com    | 555-2222       | 135 Spruce St, Vancouver, BC || 9   | Grace Yellow  | 50  | Engineer      | UK            | grace.y@example.com    | 555-3333       | 864 Fir St, Manchester, UK   || 10  | Henry Violet  | 32  | Artist        | Australia     | henry.v@example.com    | 555-4444       | 753 Willow St, Melbourne, VIC|| 11  | Irene Orange  | 26  | Scientist     | New Zealand   | irene.o@example.com    | 555-5555       | 912 Poplar St, Auckland, NZ  || 12  | Jack Indigo   | 38  | Teacher       | Ireland       | jack.i@example.com     | 555-6666       | 159 Elm St, Cork, IE         || 13  | Karen Red     | 41  | Lawyer        | USA           | karen.r@example.com    | 555-7777       | 357 Cedar St, Boston, MA     || 14  | Leo Brown     | 30  | Chef          | Canada        | leo.b@example.com      | 555-8888       | 246 Oak St, Calgary, AB      || 15  | Mia Green     | 33  | Musician      | UK            | mia.g@example.com      | 555-9999       | 975 Pine St, Edinburgh, UK   || 16  | Noah Yellow   | 29  | Doctor        | Australia     | noah.y@example.com     | 555-0000       | 864 Birch St, Brisbane, QLD  || 17  | Olivia Blue   | 35  | Engineer      | New Zealand   | olivia.b@example.com   | 555-1212       | 753 Maple St, Hamilton, NZ   || 18  | Peter Black   | 42  | Artist        | Ireland       | peter.b@example.com    | 555-3434       | 912 Fir St, Limerick, IE     || 19  | Quinn White   | 28  | Scientist     | USA           | quinn.w@example.com    | 555-5656       | 159 Willow St, Seattle, WA   || 20  | Rachel Red    | 31  | Teacher       | Canada        | rachel.r@example.com   | 555-7878       | 357 Poplar St, Ottawa, ON    || 21  | Steve Green   | 44  | Lawyer        | UK            | steve.g@example.com    | 555-9090       | 753 Elm St, Birmingham, UK   || 22  | Tina Blue     | 36  | Musician      | Australia     | tina.b@example.com     | 555-1213       | 864 Cedar St, Perth, WA      || 23  | Umar Black    | 39  | Chef          | New Zealand   | umar.b@example.com     | 555-3435       | 975 Spruce St, Christchurch, NZ|| 24  | Victor Yellow | 43  | Engineer      | Ireland       | victor.y@example.com   | 555-5657       | 246 Willow St, Galway, IE    || 25  | Wendy Orange  | 27  | Artist        | USA           | wendy.o@example.com    | 555-7879       | 135 Elm St, Denver, CO       || 26  | Xavier Green  | 34  | Scientist     | Canada        | xavier.g@example.com   | 555-9091       | 357 Oak St, Montreal, QC     || 27  | Yara Red      | 41  | Teacher       | UK            | yara.r@example.com     | 555-1214       | 975 Pine St, Leeds, UK       || 28  | Zack Blue     | 30  | Lawyer        | Australia     | zack.b@example.com     | 555-3436       | 135 Birch St, Adelaide, SA   || 29  | Amy White     | 33  | Musician      | New Zealand   | amy.w@example.com      | 555-5658       | 159 Maple St, Wellington, NZ || 30  | Ben Black     | 38  | Chef          | Ireland       | ben.b@example.com      | 555-7870       | 246 Fir St, Waterford, IE    |
""")defget_generation_time(llm, sampling_params, prompts):    # time the generation    start_time = time.time()    output = llm.generate(prompts, sampling_params=sampling_params)    end_time = time.time()    # print the output and generation time    print("-" * 30)    print(f"Output: {output[0].outputs[0].text}")    print(f"Generation time: {end_time - start_time} seconds.")    print("-" * 30)defmain():    # set enable_prefix_caching=True to enable APC    llm = LLM(model="deepseek-ai/deepseek-llm-7b-chat", enable_prefix_caching=True)    sampling_params = SamplingParams(temperature=0, max_tokens=100)    # Querying the age of John Doe    get_generation_time(        llm,        sampling_params,        LONG_PROMPT        + "Question: what is the age of John Doe? Your answer: The age of John Doe is ",    )    # Querying the age of Zack Blue    # This query will be faster since vllm avoids computing the KV cache of LONG_PROMPT again.    get_generation_time(        llm,        sampling_params,        LONG_PROMPT        + "Question: what is the age of Zack Blue? Your answer: The age of Zack Blue is ",    )if __name__ == "__main__":    main()

通過對比兩次生成時間，發現第二次生成時間顯著縮短，可以直觀感受到 Automatic Prefix Caching 帶來的性能提升。

------------------------------
Output: 29.
Generation time: 0.46364879608154297 seconds.
------------------------------
Adding requests: 100%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 1/1 [00:00<00:00, 180.41it/s]
Processed prompts: 100%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 1/1 [00:00<00:00,  7.95it/s, est. speed input: 13891.30 toks/s, output: 31.84 toks/s]
------------------------------
Output: 30.
Generation time: 0.13191604614257812 seconds.
------------------------------

4.1.3 在線推理（Online Serving）

在 GPU 后端中，v1 版本的 vLLM 默認啟用 Prefix Caching（v0 默認禁用），可以通過 --no-enable-prefix-caching 參數禁用 Prefix Caching。執行以下命令啟動 vLLM 服務提供在線推理：

vllm serve deepseek-ai/deepseek-llm-7b-chat

然后使用以下 Python 代碼請求在線推理服務，使用和前面離線推理相同的 prompt。

import time
import requestsLONG_PROMPT = (    "You are a helpful assistant in recognizes the content of tables in markdown format. Here is a table as follows.\n# Table\n"    + """
| ID  | Name          | Age | Occupation    | Country       | Email                  | Phone Number   | Address                       ||-----|---------------|-----|---------------|---------------|------------------------|----------------|------------------------------|| 1   | John Doe      | 29  | Engineer      | USA           | john.doe@example.com   | 555-1234       | 123 Elm St, Springfield, IL  || 2   | Jane Smith    | 34  | Doctor        | Canada        | jane.smith@example.com | 555-5678       | 456 Oak St, Toronto, ON      || 3   | Alice Johnson | 27  | Teacher       | UK            | alice.j@example.com    | 555-8765       | 789 Pine St, London, UK      || 4   | Bob Brown     | 45  | Artist        | Australia     | bob.b@example.com      | 555-4321       | 321 Maple St, Sydney, NSW    || 5   | Carol White   | 31  | Scientist     | New Zealand   | carol.w@example.com    | 555-6789       | 654 Birch St, Wellington, NZ || 6   | Dave Green    | 28  | Lawyer        | Ireland       | dave.g@example.com     | 555-3456       | 987 Cedar St, Dublin, IE     || 7   | Emma Black    | 40  | Musician      | USA           | emma.b@example.com     | 555-1111       | 246 Ash St, New York, NY     || 8   | Frank Blue    | 37  | Chef          | Canada        | frank.b@example.com    | 555-2222       | 135 Spruce St, Vancouver, BC || 9   | Grace Yellow  | 50  | Engineer      | UK            | grace.y@example.com    | 555-3333       | 864 Fir St, Manchester, UK   || 10  | Henry Violet  | 32  | Artist        | Australia     | henry.v@example.com    | 555-4444       | 753 Willow St, Melbourne, VIC|| 11  | Irene Orange  | 26  | Scientist     | New Zealand   | irene.o@example.com    | 555-5555       | 912 Poplar St, Auckland, NZ  || 12  | Jack Indigo   | 38  | Teacher       | Ireland       | jack.i@example.com     | 555-6666       | 159 Elm St, Cork, IE         || 13  | Karen Red     | 41  | Lawyer        | USA           | karen.r@example.com    | 555-7777       | 357 Cedar St, Boston, MA     || 14  | Leo Brown     | 30  | Chef          | Canada        | leo.b@example.com      | 555-8888       | 246 Oak St, Calgary, AB      || 15  | Mia Green     | 33  | Musician      | UK            | mia.g@example.com      | 555-9999       | 975 Pine St, Edinburgh, UK   || 16  | Noah Yellow   | 29  | Doctor        | Australia     | noah.y@example.com     | 555-0000       | 864 Birch St, Brisbane, QLD  || 17  | Olivia Blue   | 35  | Engineer      | New Zealand   | olivia.b@example.com   | 555-1212       | 753 Maple St, Hamilton, NZ   || 18  | Peter Black   | 42  | Artist        | Ireland       | peter.b@example.com    | 555-3434       | 912 Fir St, Limerick, IE     || 19  | Quinn White   | 28  | Scientist     | USA           | quinn.w@example.com    | 555-5656       | 159 Willow St, Seattle, WA   || 20  | Rachel Red    | 31  | Teacher       | Canada        | rachel.r@example.com   | 555-7878       | 357 Poplar St, Ottawa, ON    || 21  | Steve Green   | 44  | Lawyer        | UK            | steve.g@example.com    | 555-9090       | 753 Elm St, Birmingham, UK   || 22  | Tina Blue     | 36  | Musician      | Australia     | tina.b@example.com     | 555-1213       | 864 Cedar St, Perth, WA      || 23  | Umar Black    | 39  | Chef          | New Zealand   | umar.b@example.com     | 555-3435       | 975 Spruce St, Christchurch, NZ|| 24  | Victor Yellow | 43  | Engineer      | Ireland       | victor.y@example.com   | 555-5657       | 246 Willow St, Galway, IE    || 25  | Wendy Orange  | 27  | Artist        | USA           | wendy.o@example.com    | 555-7879       | 135 Elm St, Denver, CO       || 26  | Xavier Green  | 34  | Scientist     | Canada        | xavier.g@example.com   | 555-9091       | 357 Oak St, Montreal, QC     || 27  | Yara Red      | 41  | Teacher       | UK            | yara.r@example.com     | 555-1214       | 975 Pine St, Leeds, UK       || 28  | Zack Blue     | 30  | Lawyer        | Australia     | zack.b@example.com     | 555-3436       | 135 Birch St, Adelaide, SA   || 29  | Amy White     | 33  | Musician      | New Zealand   | amy.w@example.com      | 555-5658       | 159 Maple St, Wellington, NZ || 30  | Ben Black     | 38  | Chef          | Ireland       | ben.b@example.com      | 555-7870       | 246 Fir St, Waterford, IE    |
""")defget_generation_time(prompt):    url = "http://localhost:8000/v1/completions"    headers = {"Content-Type": "application/json"}    payload = {        "model": "deepseek-ai/deepseek-llm-7b-chat",        "prompt": prompt    }    start_time = time.time()    response = requests.post(url, jsnotallow=payload, headers=headers)    end_time = time.time()    print("-" * 30)    if response.status_code == 200:        result = response.json()        output_text = result["choices"][0]["text"]        print(f"Output: {output_text.strip()}")        print(f"Generation time: {end_time - start_time} seconds.")    else:        print(f"? Error {response.status_code}: {response.text}")    print("-" * 30)defmain():    get_generation_time(        LONG_PROMPT        + "Question: what is the age of John Doe? Your answer: The age of John Doe is "    )    get_generation_time(        LONG_PROMPT        + "Question: what is the age of Zack Blue? Your answer: The age of Zack Blue is "    )if __name__ == "__main__":    main()

輸出結果如下：

Output: 29.
Generation time: 0.4827253818511963 seconds.
------------------------------
------------------------------
Output: 30.
Generation time: 0.1334974765777588 seconds.
------------------------------

4.2 實現原理

vLLM 選擇了基于哈希的方法來實現 Prefix Caching。具體來說，vLLM 根據每個 KV block 內的 token 和該 block 之前前綴中的 token 來計算該 block 的哈希值：

Block 1                  Block 2                  Block 3
         [A gentle breeze stirred] [the leaves as children] [laughed in the distance]
Block 1: |<--- block tokens ---->|
Block 2: |<------- prefix ------>| |<--- block tokens --->|
Block 3: |<------------------ prefix -------------------->| |<--- block tokens ---->|

在上面的示例中，第一個 block 的 KV Cache 可以通過 token “A gentle breeze stirred” 唯一標識。第三個 block 則可以通過 block 內的 token “laughed in the distance” 以及前綴 token “A gentle breeze stirred the leaves as children” 唯一標識。

此前，vLLM 中的每個序列都維護著一個從邏輯 KV block 到物理 KV block 的映射。為了實現 KV block 的自動緩存，vLLM 還將邏輯 KV block 映射到它們的哈希值，并維護一個全局哈希表用于管理所有物理 KV block。這樣一來，所有具有相同哈希值的 KV block（例如不同請求之間共享的前綴 block）都可以映射到同一個物理 block，從而共享內存空間。這種設計實現了自動的前綴緩存，無需在 KV block 之間維護樹狀結構。

4.2.1 Block 的哈希值計算

在 vllm v1 中，一個 block 的哈希值由 3 個因素決定：

parent_block_hash：父 block 的哈希值。
cur_block_token_ids：該 block 中維護的 token ids。
extra_keys：用于確保該 block 唯一性的其他信息，例如 LoRA ID、多模態輸入的哈希值，以及在多租戶環境下用于隔離緩存的 cache salt 等。

BlockHashType( 
    hash((parent_block_hash, curr_block_token_ids_tuple, extra_keys)), 
    curr_block_token_ids_tuple, 
    extra_keys
)

4.2.2 數據結構

在 vLLM 中實現 Prefix Caching 的數據結構如下圖所示：

圖片

Block Pool：管理所有 KV Cache block，提供分配、釋放和緩存 block 的方法。Block Pool 包含所有的 KVCacheBlock，以及用于管理空閑塊的 FreeKVCacheBlockQueue，同時還通過 Cache blocks (cached_block_hash_to_block)（Dict[BlockHashType, Dict[block_id, KVCacheBlock]）維護哈希值與緩存 block 之間的映射關系。

classBlockPool:
    def__init__(self, num_gpu_blocks: int, enable_caching: bool):        # All kv-cache blocks.        self.blocks: list[KVCacheBlock] = [            KVCacheBlock(idx) for idx in range(num_gpu_blocks)        ]        # Free block queue that constructs and manipulates a doubly linked        # list of free blocks (including eviction candidates when caching is        # enabled).        self.free_block_queue = FreeKVCacheBlockQueue(self.blocks)        # {block_hash: {block ID: block}}. A cached block is        # a full block with a block hash that can be used for prefix caching.        # The cached block may be used by running requests or in the        # free_block_queue that could potentially be evicted.        # NOTE: We currently don't de-duplicate the blocks in the cache,        # meaning that if a block becomes full and is cached, we don't check        # if there is already an identical block in the cache. This is because        # we want to make sure the allocated block IDs won't change so that        # block tables are append-only.        self.cached_block_hash_to_block: dict[BlockHashType, dict[            int, KVCacheBlock]] = defaultdict(dict)

Free Block Queue（free_block_queue 屬性，FreeKVCacheBlockQueue 實例）：是一個由 KVCacheBlock 組成的雙向鏈表結構，用于維護所有空閑的 KV Cache block。隊列本身僅維護 head 和 tail 指針，每個 block 通過其 prev_free_block 和 next_free_block 字段鏈接。該結構支持以 O(1) 時間復雜度添加、刪除或移動任意位置的 block，便于高效實現 LRU 淘汰策略和資源調度。

classFreeKVCacheBlockQueue:
    def__init__(self, blocks: list[KVCacheBlock]) -> None:
        self.num_free_blocks = len(blocks)

        # Initialize the doubly linked list of free blocks.
        self.free_list_head: Optional[KVCacheBlock] = blocks[0]
        self.free_list_tail: Optional[KVCacheBlock] = blocks[-1]

當一個 block 被分配后再釋放時，會根據以下淘汰順序重新添加到隊列中（越靠前緩存越先被淘汰）：
最近最少使用（LRU）的 block 排在最前；
如果多個 block 的最后訪問時間相同（例如由同一個請求分配），那么**哈希 token 數更多的 block **排在更前。“哈希token數更多”在 vLLM 的中指的是在 block 鏈中位置更靠后的 block。在一個序列中：第一個塊的哈希只依賴于其自身的 token，第二個塊的哈希依賴于第一個塊的哈希和自身的 token，第三個塊的哈希依賴于第二個塊的哈希和自身的 token，以此類推。因此序列末尾的塊通常包含特定于當前請求的內容，復用價值較低序列開頭的塊（如系統提示）更可能在不同請求間共享。

Request blocks 以及 Block Pool 都維護在 KVCacheManager 類中。

a.req_to_blocks：Dict[req_id: List[KVCacheBlock]]，記錄一個請求下所有的 block。

b.req_to_block_hashes：Dict[req_id, List[BlockHashType]]，記錄一個請求下所有的 block 的 hash 值。由于只有滿塊才可以被計算 hash 值，因此相同請求下，可能存在 len(List[BlockHashType]) < len(List[KVCacheBlock]) 的情況。

classKVCacheManager:

    def__init__(
        self,
        kv_cache_config: KVCacheConfig,
        max_model_len: int,
        enable_caching: bool = True,
        caching_hash_algo: str = "builtin",
        num_preallocate_tokens: int = 64,
        log_stats: bool = False,
    ) -> None:        self.block_pool = BlockPool(self.num_gpu_blocks, enable_caching)        # Mapping from request ID to blocks to track the blocks allocated        # for each request, so that we can free the blocks when the request        # is finished.        self.req_to_blocks: defaultdict[str,                                        list[KVCacheBlock]] = defaultdict(list)        # Mapping from request ID to kv block hashes.        # This is to avoid recomputing the block hashes for each call of        # `get_computed_blocks` or `allocate_slots`.        self.req_to_block_hashes: defaultdict[            str, list[BlockHashType]] = defaultdict(list)        # {req_id: The number of cached blocks for this given request}        # This is used to track the number of cached blocks for each request.        # This is only used to track the RUNNING requests, we do not track the        # data for reempted ones.        self.num_cached_block: dict[str, int] = {}

4.2.3 操作

4.2.3.1 分配 Block

調度器為新請求分配 KV Cache block 的流程如下：

調用 kv_cache_manager.get_computed_blocks()：根據請求的 prompt tokens 進行哈希，并在緩存中查找對應的 Cache Blocks，獲取已計算的 block 序列。
調用 kv_cache_manager.allocate_slots()：執行以下步驟：

計算當前請求需要分配的新 block 數量；若可用 block 數不足，則直接返回；

“觸碰（touch）”已命中的緩存 block：即增加其引用計數，并將其從 Free Block Queue 中移除（如果當前沒有其他請求在用），這樣做是為了防止這些緩存 block 被淘汰。

通過彈出 Free Block Queue 的隊頭來分配新 block；如果該 block 是緩存 block，則同時會驅逐該 block，其他請求將無法再復用此 block。

如果新分配的 block 已經被 token 填滿，則立即將其添加到 Cache Blocks 中，以便在同一批次中的其他請求可以復用。

調度器為運行中的請求分配 KV Cache block 的流程如下：

調用 kv_cache_manager.allocate_slots()：執行以下步驟：

計算當前需要分配的新 block 數量；若可用 block 不足，則返回；
同樣從 Free Block Queue 的隊頭彈出 block；如果彈出的 block 是緩存 block，則同時驅逐該 block，避免其他請求再復用；
將 token ID 寫入已有 block 和新分配的 block 中的空槽位。如果某個 block 被填滿，則將其添加到 Cache Blocks 中以進行緩存。

4.2.3.2 釋放 Block

當一個請求結束時，如果其占用的 block 沒有被其他請求使用（引用計數為 0），則釋放這些 block。在本例中，釋放了請求 1 以及其關聯的 block 2、3、4 和 8。可以看到，釋放的 blocks 會按照逆序添加到 Free Block Queue 的尾部。這是因為請求的最后一個 block 通常哈希了更多的 token，更具請求特異性，不太可能被其他請求復用，因此應當優先被淘汰。

圖片

4.2.3.3 驅逐（LRU）

當 Free Block Queue 的隊頭 block（即最近最少使用的 block）仍處于緩存狀態時，必須將其驅逐，以防止被其他請求繼續使用。具體的驅逐過程包括以下步驟：

從 Free Block Queue 的隊頭彈出該 block，即要被驅逐的 LRU block；
從 Cache Blocks 中移除該 block 的 ID；
從 KVCacheBlock 移除該 block 對應的哈希值。

4.3 示例

在本示例中，假設每個 block 的大小為 4（即每個 block 可緩存 4 個 token），整個 KV Cache Manager 中共有 10 個 block。

時刻 1：緩存為空，一個新請求 Request 0（ABCD|EFGH|IJKL|MNO） 到來。分配了 4 個 block，其中 3 個已填滿并被緩存，第 4 個 block 部分填充，僅包含 3 個 token。所有 prompt tokens 都被調度。

圖片

Block 的哈希值不是只基于自己的 token，而是包含了完整的前綴路徑信息。例如，ID=2 的 hash 是 “A-L”，表示這是一個對 token A 到 L 的 prefix 路徑（前綴+當前塊）的唯一哈希標識。

時刻 3：Request 0 經過 2 次推理過程（1 次 prefill + 1 次 decode），達到下面這個狀態。Request 0 將 block 3 填滿，并請求一個新 block 以繼續 decode。此時將 block 3 緩存，并分配 block 4。

圖片

時刻 4：新的請求 Request 1（ABCD|EFGH|IJkl|mn） 帶著 14 個 prompt token 到來，其中前 10 個 token 與 Request 0 相同。可以看到，只有前兩個 block（共 8 個 token）命中緩存，因為第 3 個 block 僅匹配了其 4 個 token 中的前 2 個。Request 1 使用的 block 5 已經被 token 填滿，因此被緩存。

圖片

時刻 5：Request 0 已完成并被釋放。Block 2、3 和 4 按照逆序被添加到空閑隊列中（但 Block 2 和 3 仍處于緩存狀態）。Block 0 和 1 未被加入空閑隊列，因為它們仍被 Request 1 使用。

圖片

時刻 6：Request 1 推理完畢，同樣需要釋放掉相關資源。（原圖有誤，用紅筆做了修正）

圖片

時刻 7：Request 2（ABCD | EFGH | IJKL | 0-3 | 4-7 | 8-11 | 12-15 | 16） 帶著 29 個 prompt token 到來，其中前 12 個 token 與 Request 0 完全相同。此時，前 3 個 block（block 0 ~ block 2）可以命中緩存，因此在正式分配新 block 之前，會先被 touch 并從 Free Block Queue 中移除。隊列順序從原本的 7 - 8 - 9 - 4 - 3 - 2 - 6 - 5 - 1 - 0 更新為 7 - 8 - 9 - 4 - 3 - 6 - 5。剩余 5 個所需 block 將從 Free Block Queue 頭部依次分配，因此獲取了 block 7、8、9、4 和 3。由于 block 3 仍處于緩存狀態（哈希值 A–P），因此需要將其從緩存中驅逐。

這個例子可以幫助我們更好體會到不立刻驅逐 block、以及逆序 append block 的好處。

圖片

4.4 幾個注意點

4.4.1 只緩存完整的 block

在 vLLM 中只緩存完整的 block，假如一個 block 沒有被 token 完全填滿，那么這個 block 就不會被緩存。

# 假設 block_size = 4
# 請求的 token 序列如下：
tokens = ["A", "B", "C", "D", "E", "F", "G"]

# vLLM 會將 tokens 分成 KV blocks，每個 block 包含 4 個 token

# Block 0: ["A", "B", "C", "D"] ?  — 完整的 block，滿足 4 個 token，會被緩存
# Block 1: ["E", "F", "G"]      ?  — 只包含 3 個 token，未填滿，不會被緩存

4.4.2 哈希沖突

哈希鍵結構并不能 100% 避免沖突。從理論上講，不同的前綴 token 仍然有可能產生相同的哈希值。為了在多租戶環境中避免哈希沖突，建議使用 SHA256 作為哈希函數，而不是默認的內置哈希。自 vLLM v0.8.3 起已支持 SHA256，可通過 --prefix-caching-hash-algo 命令行參數啟用。但請注意，這會帶來一定的性能開銷：大約每個 token 增加 100–200 ns（對于 5 萬個 token，大約增加 6 ms）。

4.4.3 前綴相同才能復用緩存

只有前綴相同的部分才能復用緩存，中間某一段相同是無法復用的。

假設對于 req1:
ABCD | EFGH

假設對于 req2:
DCAB | EFGH

雖然兩者在 EFGH 部分的 token 內容完全一致，但 req2 不能復用 req1 的 EFGH block。這是因為 Transformer 的每一層都具有前向依賴性——每個 token 的表示不僅依賴它自身，還受到前面所有 token 的影響。因此，只要前綴不同，即使中間的 token 完全相同，其 KV 緩存結果也會不同，無法共享。

5 Prefix Cache Aware Routing

Prefix Caching 雖然能有效減少單個實例內部的 KV Cache 重復計算，但在多副本部署場景下，僅靠單實例的緩存復用遠遠不夠。即使多個請求具有相同前綴，仍可能被隨機分配到不同實例，導致每個實例都重復計算并緩存相同前綴。Prefix Cache Aware Routing 則是為了解決這個問題，它能根據請求前綴的匹配情況，智能地將請求路由到已有緩存的 worker，從而在集群層面實現更高效的 KV Cache 利用率。

目前，已經有不少項目實現了 Prefix Cache Aware Routing，例如：

vLLM Production Stack 支持通過 LMCache 實現 Prefix Cache Aware Routing。另外 vLLM Production Stack 還有一個提案 RFC: prefix-cache-aware routing 中，其中實現了兩種策略：基于 HashTrie 的匹配和基于 SimHash 的一致性哈希。其中，HashTrie 的方案在緩存命中率上表現更優。
SGLang 則采用了一種基于請求歷史構建 Radix Tree（基數樹）的緩存感知路由策略。
AIBrix 實現了一個分布式前綴緩存池，并對 vLLM 進行了定制化修改以支持從該緩存池加載緩存。在請求路由階段，它的 Prefix Router 能最大化模型服務器上的前綴緩存命中率。目前支持兩種策略：一種是類似 vLLM 的哈希匹配，另一種是類似 SGLang 的 Radix Tree 匹配。
KubeAI 使用了一種帶有負載邊界的一致性哈希算法（CHWBL），它會對請求前綴（可配置長度）進行哈希，但可能因此犧牲一部分精度。當服務器負載過高時，它還會觸發 "overflow" 策略將請求溢出到其他節點。
Gateway API Inference Extension EPP（End-point Picker）通過模擬模型服務器的緩存淘汰策略（如 LRU）構建一張所有后端服務器的近似前綴緩存索引表，用于指導后續請求的智能路由。關于 Gateway API Inference Extension 的詳細解釋可以參考：為 Kubernetes 提供智能的 LLM 推理路由：Gateway API Inference Extension 深度解析。

下圖展示了 Gateway API Inference Extension 的 Prefix Cache Aware Routing 的工作流程。

SGLang v0.4 為 LLM 推理引擎引入了具備緩存感知（cache-aware）能力的負載均衡器。該負載均衡器能預測各個 worker 的 prefix KV cache 命中率，并自動選擇匹配率最高的 worker。測試顯示其吞吐量最高提升 1.9 倍，緩存命中率改善達 3.8 倍，且工作節點越多優勢越顯著。下圖展示了緩存感知負載均衡器與傳統輪詢負載均衡器在數據并行中的差異。緩存感知負載均衡器會維護一個與 worker 實際基數樹近似的基數樹。該樹會進行惰性更新，幾乎沒有任何開銷。

圖片

SGLang Router 的主要特性包括：

多節點支持：支持在多臺機器上部署 worker，單個 Router 可連接分布式的多個 worker，便于水平擴展，同時在分布式環境中保持對緩存命中的感知能力。
感知緩存的路由機制：將請求優先發送到緩存命中率更高的 worker，并結合負載均衡策略避免負載不均。
免通信設計：worker 之間無需同步緩存狀態，Router 通過跟蹤請求歷史來近似推斷各個 worker 的緩存狀態，而不是直接查詢 worker 的實際緩存信息。
高性能實現：使用純 Rust 編寫，支持高并發，開銷極低，性能相比基于 Python 的方案提升達 2 倍。
獨立包形式發布：以 sglang-router 包發布，提供 Python 接口，并配有 CLI 工具，方便用戶快速上手使用。

SGLang Router 在分布式系統層面優化多 worker 環境中的緩存利用率，而核心的 prefix caching 則專注于單個 worker 內的計算重用。

使用方式如下，先安裝 sglang 和 sglang-router 包。

uv venv sglang-demo --python 3.12 --seed
source sglang-demo/bin/activate
uv pip install sglang[all]
uv pip install sglang-router

可以使用 sglang_router.launch_server 一起啟動 SGLang Router 和多個 worker。--dp-size 表示你要啟動多少個獨立的 worker 來進行數據并行（data parallel）。這里啟動了 2 個 worker，因此你的服務器上需要 2 個 GPU。

python -m sglang_router.launch_server \
--model-path deepseek-ai/DeepSeek-R1-Distill-Qwen-1.5B \
--dp-size 2 --host 0.0.0.0

如果是在多個節點上啟動 worker，然后在主節點上啟用 SGLang Router，可以使用 sglang_router.launch_router。

# 先分別啟動幾個 worker
# 在第一個窗口執行
python -m sglang.launch_server --model-path deepseek-ai/DeepSeek-R1-Distill-Qwen-1.5B --host 0.0.0.0 --port 30001 --base-gpu-id 0
# 在第二個窗口執行
python -m sglang.launch_server --model-path deepseek-ai/DeepSeek-R1-Distill-Qwen-1.5B --host 0.0.0.0 --port 30002 --base-gpu-id 1

# 啟動 SGLang Router
# 在第三個窗口執行
python -m sglang_router.launch_router \
--worker-urls http://localhost:30001 http://localhost:30002

再開啟一個窗口發送請求到 SGLang Router，反復發送多次請求：

curl -X POST http://localhost:30000/generate \
  -H "Content-Type: application/json" \
  -d '{"text": "What is the capital of France?"}'

可以看到請求始終落到其中一個 worker 上。（只會在一個 worker 的日志中看到請求信息）

[2025-06-08 21:06:35] Prefill batch. #new-seq: 1, #new-token: 7, #cached-token: 1, token usage: 0.00, #running-req: 0, #queue-req: 0
2025-06-08 21:06:35,733 - INFO - flashinfer.jit: Loading JIT ops: cascade
2025-06-08 21:06:35,741 - INFO - flashinfer.jit: Finished loading JIT ops: cascade
[2025-06-08 21:06:36] Decode batch. #running-req: 1, #token: 41, token usage: 0.00, cuda graph: True, gen throughput (token/s): 0.88, #queue-req: 0
[2025-06-08 21:06:36] Decode batch. #running-req: 1, #token: 81, token usage: 0.00, cuda graph: True, gen throughput (token/s): 122.53, #queue-req: 0
[2025-06-08 21:06:36] Decode batch. #running-req: 1, #token: 121, token usage: 0.00, cuda graph: True, gen throughput (token/s): 121.24, #queue-req: 0
[2025-06-08 21:06:36] INFO:     127.0.0.1:50554 - "POST /generate HTTP/1.1" 200 OK
[2025-06-08 21:06:38] Prefill batch. #new-seq: 1, #new-token: 1, #cached-token: 7, token usage: 0.00, #running-req: 0, #queue-req: 0
[2025-06-08 21:06:39] Decode batch. #running-req: 1, #token: 33, token usage: 0.00, cuda graph: True, gen throughput (token/s): 16.84, #queue-req: 0
[2025-06-08 21:06:39] Decode batch. #running-req: 1, #token: 73, token usage: 0.00, cuda graph: True, gen throughput (token/s): 122.95, #queue-req: 0
[2025-06-08 21:06:39] Decode batch. #running-req: 1, #token: 113, token usage: 0.00, cuda graph: True, gen throughput (token/s): 122.47, #queue-req: 0
[2025-06-08 21:06:39] INFO:     127.0.0.1:50554 - "POST /generate HTTP/1.1" 200 OK
[2025-06-08 21:06:41] Prefill batch. #new-seq: 1, #new-token: 1, #cached-token: 7, token usage: 0.00, #running-req: 0, #queue-req: 0
[2025-06-08 21:06:41] Decode batch. #running-req: 1, #token: 25, token usage: 0.00, cuda graph: True, gen throughput (token/s): 21.48, #queue-req: 0
[2025-06-08 21:06:41] INFO:     127.0.0.1:50554 - "POST /generate HTTP/1.1" 200 OK

在 SGLang Router 的日志上也可以看出，請求被轉發給了 worker 1。

[Router (Rust)] 2025-06-08 21:06:08 - INFO - ?? Initializing router on 127.0.0.1:30000
[Router (Rust)] 2025-06-08 21:06:08 - INFO - ?? Initializing workers on ["http://localhost:30001", "http://localhost:30002"][Router (Rust)] 2025-06-08 21:06:08 - INFO - ?? Policy Config: CacheAwareConfig { cache_threshold: 0.5, balance_abs_threshold: 32, balance_rel_threshold: 1.0001, eviction_interval_secs: 60, max_tree_size: 16777216, timeout_secs: 300, interval_secs: 10 }[Router (Rust)] 2025-06-08 21:06:08 - INFO - ?? Max payload size: 4 MB[Router (Rust)] 2025-06-08 21:06:08 - INFO - All workers are healthy[Router (Rust)] 2025-06-08 21:06:08 - INFO - ? Serving router on 127.0.0.1:30000[Router (Rust)] 2025-06-08 21:06:08 - INFO - ? Serving workers on ["http://localhost:30001", "http://localhost:30002"][Router (Rust)] 2025-06-08 21:06:08 - INFO - starting 32 workers[Router (Rust)] 2025-06-08 21:06:08 - INFO - Actix runtime found; starting in Actix runtime[Router (Rust)] 2025-06-08 21:06:08 - INFO - starting service: "actix-web-service-127.0.0.1:30000", workers: 32, listening on: 127.0.0.1:30000[Router (Rust)] 2025-06-08 21:07:08 - INFO - Before eviction - Used size per tenant:[Router (Rust)] 2025-06-08 21:07:08 - INFO - Tenant: http://localhost:30001, Size: 0[Router (Rust)] 2025-06-08 21:07:08 - INFO - Tenant: http://localhost:30002, Size: 0[Router (Rust)] 2025-06-08 21:07:08 - INFO - After eviction - Used size per tenant:[Router (Rust)] 2025-06-08 21:07:08 - INFO - Tenant: http://localhost:30001, Size: 0[Router (Rust)] 2025-06-08 21:07:08 - INFO - Tenant: http://localhost:30002, Size: 0[Router (Rust)] 2025-06-08 21:07:08 - INFO - Processed Queue: {"http://localhost:30002": 0, "http://localhost:30001": 3}[Router (Rust)] 2025-06-08 21:07:08 - INFO - Running Queue: {"http://localhost:30002": 0, "http://localhost:30001": 0}

6 總結

Prefix Caching 通過緩存并復用多個請求中相同前綴的 KV Cache，有效降低了大語言模型推理中的首 token 延遲和計算成本。與 PagedAttention 關注內存管理不同，Prefix Caching 專注于跨請求的計算復用，特別適用于多輪對話、few-shot 學習等場景。實現方式上，SGLang 采用基數樹（RadixAttention）方案，而 vLLM 則使用基于哈希的方法。在分布式部署環境中，Prefix Cache Aware Routing 進一步優化了集群級別的緩存利用率，通過智能路由將請求發送到緩存命中率更高的節點。

7 附錄

7.1 Few-shot learning

Few-shot learning 就是通過在 prompt 中給模型少量任務示例，讓模型在沒有專門微調的情況下，理解并完成新任務。

圖片

7.2 Self-consistency

Self-consistency 的概念來源于論文 Self-Consistency Improves Chain of Thought Reasoning in Language Models。

該方法基于這樣的假設：在復雜推理任務中，從問題到唯一正確答案通常存在多種不同的推理路徑。

其核心方案是用 self-consistency 解碼策略替代傳統的貪婪解碼。具體做法是：對語言模型進行多次采樣，生成多條不同的推理路徑（即重復請求多次），然后根據這些路徑的最終答案進行投票，選出最一致的答案作為最終輸出。

Self-consistency 策略認為復雜推理任務往往可以通過多條路徑獲得正確解，因此通過抽樣生成一個多樣化的推理路徑集合，并選取一致性最高的結果，有效降低了貪婪解碼帶來的隨機性。

Self-consistency 的核心流程如下：

Step 1：使用思維鏈（Chain-of-Thought）提示，引導模型進行逐步推理；
Step 2：對語言模型進行多次采樣，生成多個推理路徑；
Step 3：對不同路徑的最終答案進行投票，選擇一致性最高的答案輸出。

圖片

7.3 Chain of Thought

Chain of Thought (CoT) 是一種增強語言模型推理能力的技術，特別適用于需要多步推理的問題。通過在模型的提示中加入一系列的中間推理步驟，可以幫助模型進行復雜的推理任務，從而避免單純的“直接回答”模式。CoT 使得模型能夠理解并生成推理過程，而不是直接給出答案，從而提高其在復雜問題上的表現。

CoT 有兩種應用模式：

Few-Shot CoT

在 Few-Shot CoT 中，開發者給出一兩個示例，在示例中明確展示如何進行思維鏈的推理。通過這些示例，模型能夠學習如何通過逐步推理得出結論。

示例：

假設用戶詢問：“我想為朋友的生日挑選一束花。”

步驟1：理解問題，確定用戶的需求。
步驟2：列出可能適合生日的花種。
步驟3：根據花的象征意義、花朵的顏色和花期，篩選出推薦的花種。

這種逐步思考的過程可以讓模型根據需求生成符合用戶期望的推薦。

Zero-Shot CoT

在 Zero-Shot CoT 中，開發者直接告訴模型進行逐步推理。例如，通過提示“讓我們一步步地思考”，模型就能自動產生更清晰、合理的推理步驟，而不需要提前給出示例。

示例：

假設用戶詢問：“我想為我的女朋友購買一些花，她喜歡粉色和紫色的花。”
通過簡單的提示：“讓我們一步步思考”

模型就能給出以下推理過程：
步驟1：理解需求（粉色和紫色的花）。
步驟2：列舉適合的花種（例如粉色的玫瑰、紫色的蘭花等）。
步驟3：結合花的象征意義和花卉的實際情況（如價格、季節性等），給出推薦。

7.4 Tree of Thought

Tree of Thought (ToT) 進一步擴展了 CoT 的理念，特別適用于需要多步驟推理的復雜任務。與 CoT 不同，ToT 框架不僅要求生成思維鏈，而是生成多個思維路徑，并通過“思維樹”進行探索。每個思維步驟都具有多個備選方案，模型會在這些方案中搜索最優解。

示例：

假設用戶詢問：“我想為我的妻子買一束鮮花，但我不確定選擇哪種。她喜歡淡雅的顏色和花香。”
在 ToT 框架下，模型會按照以下步驟進行思考：

思維步驟1：理解需求（淡雅的顏色和花香）。
思維步驟2：列出候選花種：百合、玫瑰、紫羅蘭、桔梗、康乃馨。
思維步驟3：評估每種花是否符合要求（花香、顏色、花期等）。
思維步驟4：通過多條思維路徑篩選出最優選擇（如百合、紫羅蘭等）。
最終推薦：基于推理過程給出具體建議，例如：“考慮到您妻子喜歡淡雅的顏色和花香，我建議選擇百合或紫羅蘭，它們既符合顏色要求又有花香。”

CoT 與 ToT 的區別與聯系

CoT：專注于引導模型逐步推理，強調思考的過程，可以通過單一路徑進行推理并得出答案。
ToT：在 CoT 的基礎上，加入了多條推理路徑的選擇，使得模型能夠在多條思維路徑中搜索最優解。ToT 更適合處理復雜問題，尤其是需要多個選擇和深度探索的場景。

7.5 前綴樹（Trie）和基數樹（Radix Tree）

基數樹（Radix Tree）和前綴樹（Trie）的區別主要在于結構的緊湊性和節點的表示方式：

前綴樹（Trie） 是一種按字符逐層拆分的樹結構，每個節點只存儲一個字符，路徑上的字符連接起來表示字符串。它的層級深度通常等于字符串的長度，節點的子節點數較多（比如 26 個英文字母），空間利用率較低，但查找操作簡單直觀。Trie 這個術語來自于 retrieval。根據詞源學，trie 的發明者 Edward Fredkin 把它讀作 /?tri?/，不過，大部分人把它讀作 /?tra?/。

圖片

基數樹（Radix Tree） 也稱為壓縮前綴樹，是對 Trie 的空間優化。它將 Trie 中只有一個子節點的路徑節點合并成一個節點，節點上存儲的是一段字符序列（而非單個字符），從而減少樹的深度和節點數量，提高空間利用率。基數樹的邊可以表示多個字符，查找時按塊比較，適合處理長字符串和有長公共前綴的集合。

圖片

因此，基數樹可以看作是前綴樹的一種壓縮和優化版本，兼具 Trie 的前綴查找特性和更高的空間效率。

8 參考資料

圖解Vllm V1系列5：調度器策略（Scheduler）：https://zhuanlan.zhihu.com/p/1908153627639551302
LLM Load Balancing at Scale: Consistent Hashing with Bounded Loads：https://www.kubeai.org/blog/2025/02/26/llm-load-balancing-at-scale-chwbl/
SGLang Router for Data Parallelism：https://docs.sglang.ai/router/router.html
SGLang v0.4: Zero-Overhead Batch Scheduler, Cache-Aware Load Balancer, Faster Structured Outputs：https://lmsys.org/blog/2024-12-04-sglang-v0-4/
vLLM的prefix cache為何零開銷：https://zhuanlan.zhihu.com/p/1896927732027335111
Fast and Expressive LLM Inference with RadixAttention and SGLang：https://lmsys.org/blog/2024-01-17-sglang/
EP05-vLLM源碼講解直播筆記-Prefix Caching：https://kevincheung2259.github.io/2025/04/16/vLLM-EP05/
[Prefill優化][萬字]??原理&圖解vLLM Automatic Prefix Cache(RadixAttention): 首Token時延優化：https://zhuanlan.zhihu.com/p/693556044
圖解Vllm V1系列6：KVCacheManager與PrefixCaching：https://mp.weixin.qq.com/s/Ta7jh-2g7lAEiFOjcSJHVw
圖解大模型計算加速系列：vLLM源碼解析3，Prefix Caching：https://mp.weixin.qq.com/s/bAY4OGqQlEeBaITIwxQEuw
Prefix Cache Aware Proposal：https://github.com/kubernetes-sigs/gateway-api-inference-extension/issues/498
AIBrix v0.3.0 發布：KVCache 多級卸載、前綴緩存、公平路由與基準測試工具：https://mp.weixin.qq.com/s/1__uUX7xMoQ6q7HFXrP2Bw
大模型推理加速與KV Cache（五）：Prefix Caching：https://zhuanlan.zhihu.com/p/739669365
CoT系列-Self-Consistency(year 2022.Mar, Google)：https://zhuanlan.zhihu.com/p/609739922
PR [Experimental] Prefix Caching Support：https://github.com/vllm-project/vllm/pull/1669
PR Add Automatic Prefix Caching：https://github.com/vllm-project/vllm/pull/2762
SgLang代碼細讀-3.Cache：https://www.cnblogs.com/sunstrikes/p/18891538

責任編輯：武曉燕來源： Se7en的架構筆記

KV Cache 前綴緩存

成人免费xxxxx在线视频软件_久久精品久久久_亚洲国产精品久久久_天天色天天色_亚洲人成一区_欧美一级欧美三级在线观看