llama.cpp Radix Tree Prompt Cache

本仓库在 llama.cpp 的 Host Prompt Cache 基础上增加了 Radix Tree 后端，用于在多个请求、会话和并发 Slot 之间保存并复用共享前缀的 KV Cache。本文面向部署和使用该功能的用户，说明如何构建、启动、调用并验证 Radix Tree Prompt Cache。

原版 llama.cpp 的项目介绍、模型支持和通用使用说明保留在 README-UPSTREAM.md。通用构建选项请参阅 docs/build.md，完整的 llama-server API 请参阅 tools/server/README.md。

功能概述

传统 Host Prompt Cache 以完整 Prompt 状态为单位保存 KV Cache。多个 Prompt 即使拥有相同前缀，也会分别保存对应状态。Radix Tree 后端按照 Token 前缀组织缓存，将公共前缀只保存一次，并在分叉处保存各自的后缀。

一次请求的主要处理流程如下：

输入 Prompt
  -> Token 化并查找最长公共前缀
  -> 从 Host Radix Tree 直接恢复命中的 KV 片段
  -> 仅 Prefill 未命中的后缀
  -> Slot 空闲后保存新增 KV
  -> 按共享前缀分裂 Radix 边并更新节点

该实现具有以下特点：

• 同一共享前缀可以被多个分支和并发请求重复命中，不会因一次读取而被消费。
• 压缩边只保存实际出现的 Token 区间，公共 KV 数据由不同终止节点共享。
• KV 通过结构化 Direct KV 接口提取、分段和恢复，不经过旧的完整状态 Blob 重组路径。
• 容量达到 --cache-ram 上限时按 LRU 淘汰终止节点，并保留仍被其他分支引用的公共前缀。
• Direct KV 恢复失败时清理已写入状态并回退到完整 Prefill，避免把部分恢复状态继续用于推理。
• OpenAI 兼容接口不变。工具调用经过 Chat Template 转换为文本 Token 后，可以沿用相同的缓存路径。

该功能主要适用于 System Prompt、工具定义、RAG 文档或多轮历史较长，并且后续请求会从这些内容继续分叉的工作负载。

分支说明

本仓库保留了上游基线、早期开发过程和当前发布版本三个分支：

分支	定位
master	保留原始上游 llama.cpp 基线，不包含本项目的 Radix Tree Prompt Cache 实现。
feature/prompt-cache-radix-tree	早期开发主分支，Radix Tree 的核心设计、主要实现过程和阶段性实验均在该分支完成，适合追溯功能演进。
radixTree	在主要功能基本完成后建立的发布分支，后续合入了必要的缺陷修复、测试工具、性能证据和部署文档，是当前推荐的部署与使用版本。

本文中的构建、启动和测试命令均以 radixTree 分支为准。

获取代码

Radix Tree 的发布代码位于 radixTree 分支：

git clone -b radixTree https://gitee.com/frankPointer/llama.cpp-radix-tree.git
cd llama.cpp-radix-tree

如果已经克隆仓库，请先确认当前分支：

git switch radixTree
git status --short --branch

构建

Ascend CANN

先安装 CMake、C/C++ 编译器和与设备匹配的 CANN Toolkit，并加载 CANN 运行环境。set_env.sh 的位置取决于本机安装目录：

source /path/to/ascend-toolkit/set_env.sh

使用 Release 模式构建 llama-server：

cmake -S . -B build \
  -DGGML_CANN=on \
  -DCMAKE_BUILD_TYPE=Release

cmake --build build --target llama-server -j

构建产物位于 build/bin/llama-server。启动日志中出现 CANN0 model buffer size 和模型层卸载信息，表示模型已使用 CANN 后端。

其他计算后端

Radix Tree Prompt Cache 位于 llama-server 层，不限定模型计算后端。CPU、CUDA、Metal 等后端仍按上游 构建文档 编译。例如 CPU Release 构建：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --target llama-server -j

启动服务

下面的示例使用 4 个 Slot、Unified KV 和 4096 MiB Host Prompt Cache。请根据模型上下文长度、并发量和主机内存调整参数：

MODEL=/path/to/model.gguf

./build/bin/llama-server \
  --model "$MODEL" \
  --alias local \
  --host 0.0.0.0 \
  --port 8080 \
  --ctx-size 8192 \
  --parallel 4 \
  --kv-unified \
  --n-gpu-layers 99 \
  --batch-size 2048 \
  --ubatch-size 512 \
  --cache-ram 4096 \
  --cache-radix-prompt on \
  --log-file /tmp/llama-server-radix.log

服务启动后可以检查健康状态：

curl http://127.0.0.1:8080/health

日志中应包含以下信息：

prompt cache radix backend is enabled by --cache-radix-prompt
idle slots will be saved to prompt cache and cleared upon starting a new task

--cache-radix-min-restore-tokens 不需要额外设置。默认值为 0，表示不启用最小恢复长度阈值。默认的空闲 Slot 保存与清理逻辑已经能够驱动 Host Cache 生命周期，也不需要增加其他保留空闲 Slot 的参数。

缓存模式

以下三个启动组合可用于部署或对照测试：

模式	启动参数	行为
No Cache	--cache-ram 0 --cache-radix-prompt off	关闭 Host Prompt Cache
Legacy	--cache-ram 4096 --cache-radix-prompt off	使用原有完整状态缓存
Radix	--cache-ram 4096 --cache-radix-prompt on	使用 Radix Tree Prompt Cache

--cache-radix-prompt on 只有在 --cache-ram 非零时才会生效。修改缓存后端需要重启服务器；缓存保存在当前服务器进程的主机内存中，服务器退出后不会保留。

Radix 后端默认关闭，因此不传 --cache-radix-prompt on 时仍保持 Legacy 行为。严格的 No Cache 对照还应在请求中设置 "cache_prompt": false，仓库内的 Benchmark 已自动完成这项设置。

调用接口

Radix Tree 不改变 llama-server 的 OpenAI 兼容 API。下面的请求显式启用请求级 Prompt Cache：

curl http://127.0.0.1:8080/v1/chat/completions \
  -H 'Content-Type: application/json' \
  -d '{
    "model": "local",
    "messages": [
      {
        "role": "system",
        "content": "You are a document assistant. Always answer from the supplied context."
      },
      {
        "role": "user",
        "content": "Summarize document A."
      }
    ],
    "cache_prompt": true,
    "temperature": 0,
    "max_tokens": 32
  }'

后续请求保持较长的 System Prompt、工具定义或文档前缀不变，只修改末尾问题，即可复用已保存前缀。cache_prompt 默认为 true，示例中显式填写是为了说明缓存行为。需要强制当前请求执行完整 Prefill 时可将其设置为 false；需要完全关闭 Host Prompt Cache 时，应在服务器启动时使用 --cache-ram 0。

响应 timings 中与缓存相关的主要字段为：

字段	含义
cache_n	本次请求直接复用的 Prompt Token 数
prompt_n	本次仍需执行 Prefill 的 Prompt Token 数
prompt_ms	服务端 Prompt Eval 时间
predicted_n	生成 Token 数
predicted_ms	服务端 Decode 时间

当相同或共享前缀请求中的 cache_n > 0 时，说明请求复用了已有 KV。该字段也可能包含活动 Slot 中的前缀复用；确认 Host Radix Restore 时，还应检查服务器日志中的 Radix loads 是否增加。日志会周期性输出 Radix 终止节点数、Host Cache 占用、unique tokens、logical tokens、保存/加载次数、淘汰次数和错误回退次数。

参数建议

• --cache-ram 的单位为 MiB，限制的是 Host Prompt Cache。容量应结合主机内存和预期工作集设置。
• 多请求部署建议显式设置 --parallel 和 --kv-unified。默认空闲 Slot 清理依赖 Unified KV 与非零 Host Cache。
• --ctx-size 应覆盖并发 Slot 的实际上下文需求。长共享前缀场景需要为多个同时恢复的请求预留足够 KV 容量。
• 对照不同缓存后端时，应固定模型、量化、构建类型、计算后端、Context、Slot、Batch、UBatch、Host Cache 容量和请求集合。
• 工具调用使用最终 Chat Template 生成的文本 Token 进行匹配。只要公共 System Prompt 和工具定义保持稳定，就可以复用相应前缀。

当前边界

• Radix Direct KV 路径当前面向纯文本 Prompt。
• 启用 Draft/Speculative Context 或使用多模态 Prompt 时，服务器会自动使用 Legacy Prompt Cache 路径。
• 缓存只在单个 llama-server 进程内有效，不在不同服务器实例之间共享，也不持久化到磁盘。
• 实际收益取决于共享前缀长度、分支数量、命中频率、Host KV 恢复成本和并发调度。无共享前缀的负载不会因 Radix Tree 自动获得加速。

正确性测试

项目新增的测试按实现层、真实模型层和 HTTP 服务层组织：

测试	入口	验证内容
Radix Tree 单元测试	tests/test-server-prompt-cache-radix.cpp	插入、压缩边分裂、最长前缀、LRU、容量限制和失败回滚
Direct KV Roundtrip	tests/test-server-prompt-cache-direct-roundtrip.cpp	KV 提取、分段、恢复、逐层字节对照和 logits 对照
生命周期测试	tools/server/tests/radix/test_radix_lifecycle.py	功能开关、路由、空闲 Slot 保存和后续恢复
CANN Smoke	tools/server/tests/radix/test_qwen_cann_smoke.py	CANN 设备、模型卸载、Unified KV、4 Slot 和真实请求
HTTP Token 等价性	tools/server/tests/radix/test_radix_http_token_equivalence.py	No Cache 确定性、Full Prefill 与 Radix Restore 的逐 Token 对照
异常与回退	tools/server/tests/radix/test_radix_http_fallback.py	Direct KV 写入后故障、完整 Prefill 回退及后续缓存可用性

详细说明位于 tools/server/tests/radix/README.md。

构建测试目标

cmake --build build --target \
  llama-server \
  test-server-prompt-cache-radix \
  test-server-prompt-cache-direct-roundtrip \
  -j

python3 -m pip install -r tools/server/tests/requirements.txt

测试使用本地 GGUF 模型，不会自动下载模型，也不在代码中保存机器相关路径：

export LLAMA_TEST_MODEL_FILE=/path/to/model.gguf

运行 CPU 结构、Direct KV 和生命周期测试：

tools/server/tests/radix/run_correctness.sh cpu

在上述测试基础上增加 CANN 部署和 HTTP Token 等价性测试：

tools/server/tests/radix/run_correctness.sh cann

异常回退测试使用独立的故障注入构建。故障注入默认不进入正常 Release 二进制：

cmake -S . -B build-radix-fault \
  -DGGML_CANN=on \
  -DCMAKE_BUILD_TYPE=Release \
  -DLLAMA_SERVER_RADIX_TEST_FAULT_INJECTION=on

cmake --build build-radix-fault --target \
  llama-server \
  test-server-prompt-cache-radix \
  test-server-prompt-cache-direct-roundtrip \
  -j

LLAMA_TEST_BUILD_DIR="$PWD/build-radix-fault" \
  tools/server/tests/radix/run_correctness.sh fault

测试的完整日志、HTTP JSON 和 JUnit XML 默认写入 /tmp/llama-radix-correctness-<UTC timestamp>/。可以通过 LLAMA_TEST_EVIDENCE_DIR 指定其他输出目录。

性能与内存测试

tools/server/radix-bench/ 提供独立冷启动的 No Cache、Legacy 和 Radix 对照工具。每次运行分为 Warmup、默认 Slot Cleanup 和 Measurement 三个阶段，只有 Measurement 请求进入 TTFT 和吞吐统计。

主实验使用 Qwen3 8B Q8_0 时，可以执行：

MODEL=/path/to/Qwen3-8B-Q8_0.gguf \
MODES="no-cache legacy radix" \
REPEATS=5 \
  ./tools/server/radix-bench/run_suite.sh \
  tools/server/radix-bench/scenarios/shared-prefix-main.json

默认结果保存在 tools/server/radix-bench/results/。该目录保存本地完整 JSON 和服务器日志，并已从 Git 跟踪中排除。

现有场景包括：

场景	作用
shared-prefix-main.json	多文档、多问题、4 Slot 共享前缀主实验
exact-reuse.json	多个并发请求复用同一个完整 Prompt
no-sharing.json	验证没有公共前缀时的行为
prefix-512/1024/2048/4096.json	改变共享前缀长度
concurrency-1.json	1 Slot、客户端并发 1
concurrency-4.json	4 Slot、客户端并发 4
capacity-lru-512.json	512 MiB 容量压力、热点刷新与 LRU 淘汰

Benchmark 自身的纯 Python 单元测试不需要模型或 NPU：

python3 -m pytest tools/server/radix-bench/test_rag_bench.py -q

更完整的场景、指标和单场景运行方式见 tools/server/radix-bench/README.md。

参考测试结果

仓库保留了 Qwen3 8B Q8_0、Ascend 910B3 环境下的精简参考证据。它们用于证明测试路径和结果可复查，不代表所有模型和硬件上的固定性能。

正确性参考运行包括：

• Radix Tree 结构测试 17/17 通过。
• Direct KV 对 36 层、72 个 Cell 进行单段和多段恢复，元数据、Cell、K 字节和 V 字节差异均为 0。
• 16、32、64 Token 前缀的 Direct Restore logits 最大绝对差均为 0，argmax 一致。
• CANN Smoke 将 37/37 层卸载至 Ascend 910B3，并完成 Unified KV、4 Slot 请求。
• HTTP 对照每组执行 50 个请求并生成 1600 Token；No Cache A/B 以及 Full Prefill/Radix Restore 的不同 Token 位置均为 0。
• 故障注入触发一次恢复后写入故障，目标请求和后续缓存探针均正确回退并保持服务健康。

参考证据位于：

• 正确性证据
• 共享前缀主实验
• 共享关系实验
• 并发实验
• 容量与 LRU 实验

共享前缀主实验在 4 Slot、4 路客户端并发下执行 5 次独立冷启动，以下为运行级中位数：

模式	Cache Hit	Host Cache End	TTFT P50	TTFT P95	Throughput
No Cache	0%	0 MiB	586.9 ms	787.5 ms	5.094 req/s
Legacy	95%	3033.8 MiB	1401.7 ms	3590.4 ms	1.958 req/s
Radix	100%	953.0 MiB	222.0 ms	347.4 ms	16.531 req/s

该结果只对应仓库中的固定共享前缀工作负载。评估其他部署时，应使用同一模型、相同服务器配置和独立冷启动重复实验重新测量。

目录索引

路径	内容
tools/server/server-prompt-cache-radix.h/.cpp	Radix Tree 数据结构与 LRU/容量管理
tools/server/server-task.h/.cpp	Host Prompt Cache、Direct KV 保存/恢复和统计
tests/test-server-prompt-cache-radix.cpp	Radix Tree 主机侧单元测试
tests/test-server-prompt-cache-direct-roundtrip.cpp	Direct KV 结构和 logits 测试
tools/server/tests/radix/	服务器级正确性测试与参考证据
tools/server/radix-bench/	性能、并发和容量 Benchmark