# llama.cpp-radixTree

**Repository Path**: frankPointer/llama.cpp-radix-tree

## Basic Information

- **Project Name**: llama.cpp-radixTree
- **Description**: llama.cpp 
- **Primary Language**: Unknown
- **License**: MIT
- **Default Branch**: radixTree
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2026-06-15
- **Last Updated**: 2026-07-28

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 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](README-UPSTREAM.md)。通用构建选项请参阅 [docs/build.md](docs/build.md)，完整的 `llama-server` API 请参阅 [tools/server/README.md](tools/server/README.md)。

## 功能概述

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

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

```text
输入 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` 分支：

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

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

```bash
git switch radixTree
git status --short --branch
```

## 构建

### Ascend CANN

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

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

使用 Release 模式构建 `llama-server`：

```bash
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 等后端仍按上游 [构建文档](docs/build.md) 编译。例如 CPU Release 构建：

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

## 启动服务

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

```bash
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
```

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

```bash
curl http://127.0.0.1:8080/health
```

日志中应包含以下信息：

```text
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：

```bash
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](tools/server/tests/radix/README.md)。

### 构建测试目标

```bash
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 模型，不会自动下载模型，也不在代码中保存机器相关路径：

```bash
export LLAMA_TEST_MODEL_FILE=/path/to/model.gguf
```

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

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

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

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

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

```bash
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 时，可以执行：

```bash
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：

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

更完整的场景、指标和单场景运行方式见 [tools/server/radix-bench/README.md](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。
- 故障注入触发一次恢复后写入故障，目标请求和后续缓存探针均正确回退并保持服务健康。

参考证据位于：

- [正确性证据](tools/server/tests/radix/evidence/README.md)
- [共享前缀主实验](tools/server/radix-bench/evidence/shared-prefix-main-summary.json)
- [共享关系实验](tools/server/radix-bench/evidence/shared-relations-summary.json)
- [并发实验](tools/server/radix-bench/evidence/concurrency-summary.json)
- [容量与 LRU 实验](tools/server/radix-bench/evidence/capacity-lru-512-summary.json)

共享前缀主实验在 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 |