🤖 machine learning

Requests of a Feather Must Flock Together: Batch Size vs. Prefix Homogeneity in LLM Inference

本文介绍了 Feather，一种基于强化学习的前缀感知调度器，它利用轻量级的分块哈希树优化批处理大小与前缀同质性之间的权衡，通过降低 KV 缓存访问开销，相较于现有最先进调度器实现了 2 至 10 倍的大语言模型推理吞吐量提升。

原作者： Saksham Rathi, Preeti, Mythili Vutukuru

发布于 2026-05-08

📖 1 分钟阅读☕ 轻松阅读

原作者： Saksham Rathi, Preeti, Mythili Vutukuru

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在经营一个非常繁忙、高速运转的图书馆，其中一位图书管理员（GPU）正试图同时回答来自不同人（请求）的数千个问题。

在大语言模型（LLMs）的世界里，这位图书管理员每生成一个单词，都必须阅读一本巨大的“上下文”书（键值缓存）。该论文指出，当前组织这些问题的方式效率低下，因为它过于关注图书管理员一次回答了多少个问题，而不是这些问题有多相似。

以下是他们提出的解决方案 Feather 的故事，分解为简单的概念：

1. 问题：“拥挤的公交车”与“家庭团体”

目前，大多数系统试图将尽可能多的人塞进一辆公交车（一个“批次”）以提高行程效率。它们采用“先到先得”的规则。

问题所在： 如果你把 500 个陌生人塞进一辆公交车，他们都想前往 500 个不同的地方。司机不得不停靠 500 个不同的站点，不断改变方向。这既混乱又缓慢。
发现： 作者发现，如果你带上 100 个都住在同一条街上（共享一个“前缀”）的小团体，司机就可以沿着那条街直线行驶而无需停车。尽管公交车没有坐满，但行程要快得多，因为司机不必不停地转动方向盘。

关键洞察： 拥有一群前往同一目的地的小团体，比拥有一群前往不同目的地的大团体更好。这被称为前缀同质性（Prefix Homogeneity）。

2. 旧方法：“爬树者”

现有系统（如 SGLang）试图通过查看一棵巨大而复杂的家谱树（基数树）来寻找这些团体，看看谁拥有共同的祖先。

问题： 爬这棵树去寻找匹配项需要消耗计算机“大脑”（CPU）大量的时间和能量。事实上，爬树所花费的时间有时几乎与图书管理员实际回答问题所花费的时间一样长！这就像花了 10 分钟整理乘客，却只开了 10 分钟的车。

3. 解决方案："Feather"

作者构建了一个名为 Feather 的新调度器，解决了这两个问题。

第一部分：“分块哈希树”（CHT）—— 智能清单

Feather 不使用爬那棵巨大的家谱树，而是采用了一种巧妙的捷径。

类比： 想象一下，与其检查一个人姓名的每一个字母，你只需检查其地址的前几个“分块”。
工作原理： Feather 将长文本分割成小块（chunks），并为每个块分配一个独特的“指纹”（哈希值）。它维护一份简单的列表，记录当前正在使用哪些指纹。
优势： 它可以立即发现：“哦，这个新请求与车上已有的团体拥有相同的指纹。”它的速度如此之快，以至于“CPU 大脑”几乎不需要费神。这就像使用条形码扫描仪，而不是阅读整本书来检查车票。

第二部分：“强化学习”（RL）—— 智能调度员

Feather 不仅能找到相似的团体，还能学习何时停止往公交车上添加人员。

困境： 如果你继续往公交车上添加人员，最终可能不得不添加一个住在不同街道的人。如果你添加了他，整个团体就会变得杂乱无章，速度也会下降。
学习过程： Feather 就像一个聪明的调度员，通过试错学会了这一点：“如果我再加一个人，我们可能会失去速度。让我们在速度仍然很快时发出这辆车，然后等待下一组。”
结果： 它动态地决定启动批次的最佳时机，在让公交车坐满和保持所有人都在同一条街上之间取得平衡。

4. 结果：加速图书馆

当作者测试 Feather 时：

速度： 当人们提出相似的问题时，它使系统的速度比当前最佳方法快了 2 到 10 倍。
安全性： 如果所有问题都完全不同（没有共享街道），Feather 不会感到困惑；它的表现与旧方法一样好。
效率： 它减少了计算机内存中的“交通堵塞”，这意味着图书管理员不必为了取书而频繁地来回奔跑。

总结

Feather 是一种组织 AI 请求的新方法。它不是将尽可能多的请求塞进单个批次，而是将相似的请求分组在一起（就像一个家庭前往同一个目的地），并使用一种超快速、低能耗的方法来寻找这些团体。它学会了何时停止向团体中添加人员，以保持行程顺畅快速。

该论文声称，这种方法无需昂贵的新型硬件，仅通过更智能地组织“交通”，就能显著加快 AI 的响应速度。

技术摘要：同类请求必相聚

问题陈述

在大语言模型（LLM）推理的自回归解码阶段，内存带宽是根本瓶颈。每个生成的 token 都需要关注所有先前 token 的键值（KV）缓存，这意味着在每一步都需要在 GPU 显存中完整扫描 KV 缓存。虽然 prior 工作专注于最大化批处理大小以提高 GPU 利用率，但本文指出了一个关键却被忽视的权衡：前缀同质性。

在真实工作负载（例如少样本提示、系统提示、RAG）中，请求往往共享显著的前缀。现有的推理引擎（如 vLLM 和 SGLang）利用基数树或哈希结构来检测这些共享前缀并复用 KV 缓存，主要目的是减少内存占用。然而，当前的调度器优先考虑最大化批处理大小或最小化内存驱逐，而未考虑前缀异质性对内存访问模式的影响。

作者证明，异质批处理（包含具有不同前缀的请求）会破坏 GPU DRAM 访问的空间和时间局部性，导致带宽利用率低下和吞吐量降低。相反，前缀同质批处理（所有请求共享一个公共前缀）允许高效的硬件预取和缓存复用。本文认为，现有的调度器未能认识到，一个中等规模但同质的批处理，其表现可能优于一个更大但异质的批处理。此外，用于检测前缀共享的机制（例如基数树遍历）会产生巨大的 CPU 开销，通常与 GPU 执行时间相当甚至超过后者。

方法论

本文提出了 Feather，一种感知前缀的调度器，旨在优化批处理大小与前缀同质性之间的权衡。Feather 集成了两个主要组件：

1. 分块哈希树（CHT）

为了解决传统基数树遍历的高 CPU 开销，Feather 采用了一种名为分块哈希树（Chunked Hash Tree）的轻量级数据结构。

机制：请求不再通过逐 token 比较来表示，而是表示为固定大小 token 分块的累积哈希向量。
效率：CHT 维护活跃批处理的哈希“工作集”，以及一个按“缺失计数”（即活跃批处理尚未覆盖的分块数量）排序的等待请求最小堆。
复杂度：这使得调度器能够在 $O(\log W)$ 时间内识别出要添加到批处理中的最佳候选请求（其中 $W$ 是等待请求的数量），这比深度优先基数树遍历的 $O(W \times T)$ 或 $O(E)$ 复杂度有了显著改进。
操作：CHT 支持高效插入、查找最佳请求、将请求添加到活跃批处理以及移除已完成的请求，利用延迟堆更新和增量尖端维护来最小化开销。

2. 强化学习（RL）批处理策略

Feather 使用基于 RL 的策略来确定批处理形成的最佳停止点。

权衡：添加更多请求会增加 GPU 利用率（更大的批处理大小），但可能会稀释前缀同质性（降低内存局部性）。
状态与动作：调度器观察当前批处理大小、共享前缀深度的损失（ $\Delta$ ）以及共享新前缀深度的等待请求数量（ $w$ ）。它决定是添加另一个请求，还是停止并分发批处理。
策略：作者评估了三种策略：静态启发式、上下文多臂老虎机（UCB）和 Q 学习。目标是最大化奖励，定义为解码吞吐量。
适应性：RL 策略学会形成“恰到好处”的批处理——大到足以利用 GPU，又同质到足以最大化内存局部性。它能动态适应工作负载强度和前缀共享模式。

主要贡献

识别关键权衡：本文确立了前缀同质性是解码吞吐量比单纯批处理大小更强的决定因素。它表明，即使批处理中只有一个发散的请求，也会破坏局部性并将吞吐量降低近 2 倍。
量化 CPU 开销：作者揭示，最先进的检测机制（如 SGLang 中的基数树遍历）产生的 CPU 开销可占总延迟的 50–90%，实际上抵消了前缀复用的好处。
Feather 调度器：Feather 的设计与实现，将 CHT 数据结构与基于 RL 的批处理策略相结合。Feather 已集成到 vLLM 和 SGLang 中。
硬件无关性：与需要特定硬件调优的感知前缀注意力内核不同，Feather 在调度层运行，使其与现有的注意力内核和硬件配置兼容。

结果

评估在 NVIDIA RTX 6000 Ada 和 A100 GPU 上进行，使用了 Llama 3 8B、Qwen 和 LongChat 13B 等模型，涵盖多种工作负载（L-Eval、LongBench）。

吞吐量提升：在共享前缀范围从 1K 到 10K token 的工作负载中，与现有调度器（vLLM 的 FCFS、SGLang 的 LPM/DFS-W）相比，Feather 实现了 2–10 倍的端到端吞吐量提升。
前缀敏感性：在将 800 个请求分为 8 个前缀组的实验中，将它们处理为 8 个包含 100 个请求的同质批处理，其吞吐量几乎是处理为更大、异质批处理时的 2 倍。
开销降低：对于长序列，Feather 的 CHT 将前缀检测开销相比基于 DFS 的方法降低了高达 1000 倍。调度开销保持在 GPU 执行时间的 1% 以下，而基线方法则可能超过 GPU 执行时间。
鲁棒性：当工作负载缺乏前缀共享时，Feather 的表现与现状（FCFS）相当，确保在非共享场景下不会出现性能下降。
与内核的比较：尽管未修改内核本身，Feather 的表现优于或等同于专门的感知前缀注意力内核（如 PAT），证明调度级优化可以与内核级优化同样有效。

意义

本文声称，最大化批处理大小已不足以实现高效的 LLM 服务。现代解码阶段的主要瓶颈是内存带宽，而内存带宽深受访问局部性的影响。通过将重点从“最大化批处理大小”转移到“优化前缀同质性”，Feather 在不要求特定硬件内核修改的情况下解锁了显著的性能提升。

这项工作强调，发现共享前缀的成本（CPU 开销）一直是当前系统中的隐藏瓶颈。Feather 的轻量级 CHT 和自适应 RL 策略表明，动态平衡计算利用率和内存局部性是可行的，从而为真实世界的 LLM 推理工作负载带来吞吐量和延迟的大幅改善。作者计划通过将 Feather 贡献给 vLLM 和 SGLang 仓库来将其开源。