LMCache前缀索引

本文比较 vLLM v1 的本地 Automatic Prefix Caching（APC）与接入 vLLM 的 LMCache 分块前缀索引。下文谈到“vLLM 命中 GPU、LMCache 从 CPU 等存储载回”时，前提是未启用 vLLM 的 KV 卸载。vLLM 当前也提供 OffloadingConnector，可把前缀 KV 卸载到 CPU、文件系统或对象存储，再按需载回。

文中的 token ID、哈希值、block ID 和分块大小是示意值。两边都用链式前缀哈希，但哈希值不能互用；能否复用还取决于对应 KV 是否已写入缓存、尚未被淘汰。

假设请求

{
  "model": "Qwen/Qwen3-8B",
  "messages": [
    {
      "role": "system",
      "content": "You are a helpful assistant."
    },
    {
      "role": "user",
      "content": "Explain KV cache."
    }
  ],
  "max_tokens": 100
}

首先经过 Qwen 的 chat template，大致变成：

<|im_start|>system
You are a helpful assistant.<|im_end|>
<|im_start|>user
Explain KV cache.<|im_end|>
<|im_start|>assistant

然后 tokenizer 把文本变成整数。以下整数只示意输出格式，不代表上述 Qwen 请求的实测编码结果：

[
  151644, 8948, 198,
  2610, 525, 264, 10950, 17847, 13,
  151645, 198,
  151644, 872, 198,
  8376, 14424, 8946, 13,
  151645, 198,
  151644, 77091, 198
]

所以 prompt 先转换成token IDs：

"Explain KV cache."
tokenizer 处理后的示意值：[8376, 14424, 8946, 13]

下面单独假设一个 prompt token 化以后得到 16 个 token：

T =
[101,102,103,104,
 105,106,107,108,
 109,110,111,112,
 113,114,115,116]

vLLM：假设 hash block size = 4

那么 vLLM 分成：

Block 0:
[101,102,103,104]

Block 1:
[105,106,107,108]

Block 2:
[109,110,111,112]

Block 3:
[113,114,115,116]

然后：

H0 = hash(
    NONE_HASH,
    (101,102,103,104),
    extra_keys
)

H1 = hash(
    H0,
    (105,106,107,108),
    extra_keys
)

H2 = hash(
    H1,
    (109,110,111,112),
    extra_keys
)

H3 = hash(
    H2,
    (113,114,115,116),
    extra_keys
)

vLLM 的 Block Hash 形式是：

BlockHash =
hash(
    parent_block_hash,
    curr_block_token_ids,
    extra_keys
)

LMCache

假设 LMCache：

chunk_size: 8

同样的：

[101,102,103,104,
 105,106,107,108,
 109,110,111,112,
 113,114,115,116]

LMCache 分成：

Chunk 0:
[101,102,103,104,105,106,107,108]

Chunk 1:
[109,110,111,112,113,114,115,116]

然后：

C0 = hash(
    NONE_HASH,
    (101,102,103,104,105,106,107,108),
    ()
)

C1 = hash(
    C0,
    (109,110,111,112,113,114,115,116),
    ()
)

和 vLLM 是一样的链式思想。

LMCache 当前 ChunkedTokenDatabase 源码就是：

prefix_hash = self._get_init_hash()

for token_chunk in token_chunks:
    prefix_hash = self._hash_tokens(
        token_chunk,
        prefix_hash
    )
    yield prefix_hash

而 _hash_tokens() 实际规范化成：

(
    prefix_hash,
    tuple(token_ids),
    tuple(extra_keys) if extra_keys is not None else ()
)

再 hash。上面的分块路径没有传入 extra_keys，因此取空元组。(GitHub)

所以：

vLLM
Hn = Hash(Hn-1, 当前 block 的 token IDs, extra_keys)

LMCache 的上述分块路径
Cn = Hash(Cn-1, 当前 chunk 的 token IDs, ())

这是同一种链式索引思路，不表示 Hn 和 Cn 是同一个哈希值。两者的分块粒度、哈希输入和默认算法均可能不同。

vLLM 的 H1

假设：

H1 = 0xA72F...

vLLM 内部大致维护：

cached_block_hash_to_block

0xA72F... : KVCacheBlock(block_id=137)

其中：

block_id = 137

表示：

GPU KV cache pool 中编号为 137 的 block。block_id 是缓存池索引，不是显存物理地址。

vLLM 的 KVCacheBlock 本身就有：

class KVCacheBlock:
    block_id: int
    block_hash: BlockHash
    ref_cnt: int

官方文档也明确说明缓存表本质上是：

hash key : block IDs

(vLLM)

所以这里：

token prefix
BlockHash H1
block_id = 137
vLLM KV block pool
GPU KV Cache

---

LMCache 的 C0

假设：

C0 = 0x83B142  # 示意值

LMCache 进一步构造：

CacheEngineKey(
    model_name="Qwen/Qwen3-8B",
    world_size=2,
    worker_id=0,
    chunk_hash=0x83B142,
    dtype=torch.bfloat16
)

LMCache 当前 CacheEngineKey 的字段包括：

model_name
world_size
worker_id
chunk_hash
dtype
request_configs
tags

这里的 world_size 是部署的 worker 总数，worker_id 是 worker 编号；tags 可由 request_configs 生成。示例中的 world_size=2 仅为假设，不能把它一概写成 TP 大小。

(GitHub)

然后：

CacheEngineKey
KV tensor

这份 tensor 可以存在：

CPU
Local Disk
Remote storage
其他 LMCache backend

同一个 prompt，经 tokenizer 得到 [101,102,...116]

vLLM 本地 APC：
切成 hash unit，计算 prefix chain hash H1
用 H1 定位 block_id，访问本地 KV block pool 中的 GPU KV

LMCache：
切成 chunk，计算 prefix chain hash C0
用包含 model_name、world_size、worker_id、C0、dtype 的 CacheEngineKey
定位 LMCache 后端中的 KV，例如 CPU、Disk 或 Remote

---

具体环境下

第一次：

{
  "model": "Qwen/Qwen3-8B",
  "messages": [
    {
      "role": "system",
      "content": "You are a helpful assistant."
    },
    {
      "role": "user",
      "content": "Here is a 10000-token document: [......]"
    },
    {
      "role": "user",
      "content": "Summarize chapter 1."
    }
  ]
}

假设最终：

10240 prompt tokens

第一次 prefill：

在 GPU 上计算，生成 10240 个 prompt token 的 KV

vLLM APC 会得到很多：

H0
H1
H2
...
H319

如果 hash unit 是 32 token，就是：

H0 = hash(NONE_HASH, tokens[0:32], extra_keys)
H1 = hash(H0, tokens[32:64], extra_keys)
...

LMCache chunk size 假设 256：

C0 = hash(NONE_HASH, tokens[0:256], ())
C1 = hash(C0, tokens[256:512], ())
...
C39

如果配置了 CPU 存储且写入成功，LMCache 把这些 KV chunk 存到 CPU：

Key(C0) : KV[0:256]
Key(C1) : KV[256:512]
...

---

第二次用户问：

{
  "model": "Qwen/Qwen3-8B",
  "messages": [
    {
      "role": "system",
      "content": "You are a helpful assistant."
    },
    {
      "role": "user",
      "content": "Here is a 10000-token document: [完全相同的文档]"
    },
    {
      "role": "user",
      "content": "What is the conclusion?"
    }
  ]
}

前面那篇 10000-token 文档完全一样。假设 chat template 和 tokenizer 生成的前缀 token ID 相同，vLLM 的额外哈希键也相同，LMCache 的模型、KV dtype、并行布局与缓存标签也不变，两边分别会算出与第一次请求一致的前缀哈希：

各自系统内，共享前缀的 hash 一样

后面的问题不同，因此命中到哪里还取决于两次请求的最长公共 token 前缀，以及 block 或 chunk 的边界；不能认为 10240 个 prompt token 都命中。

但是后续动作不同：

vLLM APC 命中

如果这些 GPU block 仍在本地缓存池中：

H0 : block 17
H1 : block 93
H2 : block 41
...

直接：

reuse GPU blocks

不重新 prefill 那部分。

LMCache 命中

即使对应 KV 已经不在 vLLM GPU block pool，只要 LMCache 曾写入且尚未淘汰：

C0 : CPU KV
C1 : CPU KV
...

LMCache 依然可以：

CPU / Disk / Remote
找到 KV chunk
load 到 GPU
交给 vLLM
处理未命中的 token，再继续 decode

如果整个 prompt 恰好都命中，当前 LMCache vLLM 连接器仍会重算最后一个 token 以获得 logits。(连接器源码)

vLLM 本地 APC 的 Block Hash：
“这段 prefix 对应本地 KV block pool 中的哪个 KV block？”

LMCache 的 Token Content Hash：
“这段 prefix 对应 LMCache 存储系统里的哪份 KV 数据？”

当前 LMCache 源码中的 TokenDatabase 会加载 vLLM 提供的哈希函数，并处理版本兼容。这不意味着两套索引的哈希值相同。(GitHub)