SGLang-Prefix Prompt Cache设计
Paper
SGLang: Efficient Execution of Structured Language Model Prpgrams
Motivation
多轮对话中，由于Prompts存在大量相同前缀，因此 Prefix prompt cache 的复用就显得很重要：需要考虑：efficient prefix search,reuse,insertion,eviction已经对应的cache aware scheduing。
Key Points
SGLang采用了 prefix tree 的数据结构来进行Cache的数据存储，基础特点：
- 前缀压缩：相同前缀的多个键只存储一次，减少重复存储。
- 动态扩展：支持增删查操作，适应符号集合或规则的动态变化。
- 快速查询：查找复杂度接近 O(k) ，其中 k 是键的平均长度。
- 稀疏存储：仅存储有效路径，优化内存占用。
另外，Scheduling策略上，以匹配的prefix-length作为最高优先级。
VLLM结合PA和Prefix Cache，通过 hash(prefix tokens + block tokens) 来定义对应的KV Block，通过hash-mapping的方式来实现prefix-cache和physical block的mapping：
Statistics
multi-call 下的性能收益： 