GORGO: Maximizing KV-Cache Reuse While Minimizing Network Latency in Cross-Region LLM Load Balancing

§1 TL;DR #

GORGO 通过 additive cost model 联合优化 network latency、KV-cache prefix overlap 和 queue depth 来路由跨区域 LLM 请求，其集中式 proxy 变体实现 median TTFT 2.5× 优于 baseline。

§2 痛点 / 方法 / 结果 #

Q1 痛点 #

跨地理区域部署的 LLM 推理面临路由抉择：现有方案要么纯负载均衡（忽略 prefix cache），要么纯 prefix-similarity 路由（忽略跨区网络延迟）。当远端区域有更高 cache hit 但 RTT 达 281ms 时，追逐 cache overlap 反而恶化 TTFT。核心冲突：network latency 和 KV-cache similarity 不可独立优化。

Q2 方法 #

GORGO 提出 additive cost model（因各组件时序串行发生）：

$$\mathrm{Cost}(\text{region}) = \mathrm{NetworkLatency}(\text{peer}) + t_p \cdot \mathrm{PrefillCost}(\text{peer}) + \hat{q}_s \cdot \mathrm{QueueWaitTime}(\text{local})$$

核心技术壁垒: 将 prefix overlap 转换为时间量 $L_\text{hit} \cdot t_p$，使三个异构信号（ms 单位）可直接相加。$t_p$ 通过线性回归精确标定（$R^2 = 0.9863$），且 additive 结构对应真实串行 pipeline。

Q3 结果 #

• GORGO-proxy median TTFT: 224.55 ms（vs least-load 568 ms = 2.5×，vs prefix-trie 564 ms = 2.5×）
• GORGO-proxy P99 TTFT: 436 ms（vs least-load 18,115 ms = 41× improvement）
• GORGO-proxy throughput: 2.33 req/s（vs least-load 1.65）
• 但分布式 GORGO 牺牲 throughput（0.93 req/s）

§3 架构 / 方法图 #

§4 作者证明 #

符号表 #

方程物理意义 #

Cost model additive: network forwarding、residual prefill、queueing 在 serving pipeline 中串行发生，因此 TTFT ≈ 三者之和。Minimizing sum 直接最小化 TTFT。

Saved time = $L_\text{hit} \cdot t_p$: 已缓存的 prefix tokens 无需重新计算，节省的时间与 token 数线性相关。

Linear regression $\text{TTFT} = 150.72 + 0.0938x$: 验证 prefill 对 TTFT 的贡献是线性的（$R^2 = 0.9863$, N=87），证明 cost model 的 additive 假设成立。

6 项检查 #

1. 模型假设: prefill time 对 token 数线性 — 强 $R^2$ 支持
2. Additive 假设: 三组件串行 — pipeline 结构验证
3. Signal freshness: peer summaries 定期交换，非实时 — 承认 staleness 可能导致误估
4. No optimality proof: heuristic policy, 非 provably optimal scheduler
5. Generality: 假设各区域 per-token timing 相近 — 异构加速器未处理
6. Queue model: 线性近似，未建模 batch composition 对 $t_p$ 的动态影响

无形式化作者证明 — 仅实证（作者明确声明 "not intended to perfectly predict per-request latency"）

§5 实验与数据 #

实验配置 #

维度	配置
区域	3: US West Coast, Germany, Israel
硬件	每区域 8×A100
模型	Mistral-7B-Instruct-v0.3
运行时	SGLang (RadixAttention)
工作负载	WildChat + GuideLLM (concurrent, 10 in-flight, 60s)
LB 实现	Go (loadbalancer.go)

关键结果 #

GORGO-proxy vs baselines (median TTFT):

方法	Median TTFT	P99 TTFT	Throughput
Least-load	568 ms	18,115 ms	1.65 req/s
Prefix-trie	564 ms	20,595 ms	1.40 req/s
GORGO (distributed)	539 ms	1,207 ms	0.93 req/s
GORGO-proxy	224 ms	436 ms	2.33 req/s

线性回归标定: $t_p$ = 0.0938 ms/tok, base latency = 150.72 ms, $R^2$ = 0.9863 (N=87)。

关键观察 #

• 分布式 GORGO 在 median TTFT 上改进不大（539 vs 568），但 P99 提升 15×
• GORGO-proxy 同时获得最低 TTFT 和最高 throughput — 说明 latency-throughput tradeoff 是分布式协调的 artifact
• $t_p$ = 0.0938 ms/tok 意味着 1000-token cache savings 仅值 94ms，常不及跨区 RTT

§6 论证链 #

Step	论据	证据	结论
1	纯 cache-overlap 路由忽略网络代价	§2.4 motivating example: Israel 有 15% cache hit 但 TTFT = 378ms > Germany 0% hit 但 281ms	Cache hit 不等于 TTFT 最优
2	三信号可转换为同一单位 (ms)	$t_p$ linear regression $R^2=0.9863$; RTT directly measurable; queue × $t_p$	Additive cost model 物理合理
3	集中式 proxy 优于分布式	GORGO-proxy 224ms vs GORGO 539ms; proxy 有全局信息优势	Coordination overhead 被 centralization 消除
4	P99 TTFT 改进更显著	GORGO-proxy P99 = 436ms vs least-load 18,115ms	避免 pathological cross-region forwarding

§7 实现 cross-reference #

开源状态: 论文描述了实现但未明确给出开源 repo。

关键实现细节:

1. MaxHops guard: forwarding 有最大跳数限制，防止请求在区域间循环弹跳。
2. Prefix trie 非精确 KV state: LB 维护的 prefix index 是 lightweight approximation（hash → node mapping），非运行时精确 KV cache state，用于快速路由决策而非精确 cache hit 计算。

基础设施: SGLang status endpoint 暴露 queue state + KV-cache capacity + per-token compute time; GuideLLM 用于 benchmark workload generation; WildChat dataset 提供地理分布的用户 prompt。

[实现未公开]