KV Cache 内存池管理
P6084. KV Cache 内存池管理
场次:2026年10月23日-AI方向 · 来源:CodeFun2000 P6084
题目描述
大语言模型自回归生成时,历史 token 的 Key 与 Value 会缓存在 KV Cache 里,后面每一步解码直接复用,不必重算。序列越长,KV Cache 占的显存越多,而且是线性增长。
工程上通常先把显存切成一堆等大的块(Block)集中管理,这套机制叫内存池(Memory Pool):Block 一次分配好,每个 Block 装固定条数 token 的 KV 数据。
内存池中有 个等大的 Block,每个 Block 能容纳 条 token 的 KV 数据。
现有 个推理请求,第 个请求要处理 条 token(输入长度与生成长度之和),它占用的 Block 数为 。
决策规则
- 请求按给定顺序逐个到达。
- 对每个请求可以选择接受或拒绝:
- 接受:被接受请求占用的 Block 总数最终不能超过 ;
- 拒绝:该请求不占用任何资源。
- 允许在后续决策中撤销先前已接受的请求(释放它占用的 Block),以换取更好的整体结果。
- 请求一旦被拒绝,就不能再次考虑。
- 请求之间不允许重排,必须按到达顺序逐个决策。
优化目标
在接受的请求占用 Block 总数不超过 的前提下,使被接受的请求数量最多。
输入格式
第一行三个整数 、、,相邻两数之间用一个空格分隔。
第二行 个整数,依次是 。
其中:
- :内存池中的 Block 总数;
- :每个 Block 能容纳的 token 条数;
- :请求数量;
- :第 个请求要处理的 token 条数。
输出格式
输出一个整数,表示最多可接受的请求数量。不要输出多余的空格或空行。
数据范围
若某个请求需要的 Block 数超过 ,它一定无法被接受。
请求顺序不能改变,但后续决策中可以撤销先前的选择。
建议设计时间复杂度优于 的算法。
时间限制:C/C++ ms,其他语言 ms。
内存限制:C/C++ MB,其他语言 MB。
示例
示例 1
输入:
4 8 3
20 6 11输出:
2说明:
三个请求的 Block 需求依次为 、、。只接第 1 个请求,它独占 3 个 Block,剩下 1 个 Block 哪个请求都放不下,只能接受 1 个;跳过它、改接第 2 与第 3 个请求,占用 个 Block,可以接受 2 个。三个请求全接需要 个 Block,超过上限 ,所以最多接受 2 个。
示例 2
输入:
6 9 4
7 22 13 10输出:
3说明:
每个 Block 装 9 条 token,四个请求的 Block 需求如下:
| 请求 | 长度 | Block 数 |
|---|---|---|
| 1 | 7 | 1 |
| 2 | 22 | 3 |
| 3 | 13 | 2 |
| 4 | 10 | 2 |
挑选需求最小的三个请求(第 1、3、4 个),占用 个 Block,不超过 6,共接受 3 个;四个全接受需要 个 Block,超过上限,所以最多接受 3 个。
解题思路
每个请求其实只有一个数:它要几个 Block
长度 与 Block 数之间是向上取整的关系:
need = (length + k - 1) // k # 等价于 ceil(length / k),且全程是整数写 length // k 会在 不是 的整数倍时少算一个 Block( 得 而不是 ),一步错到底。有了这个数,长度本身再也不参与后面的讨论——每个请求就剩一个「占几个 Block」的价钱。
撤销权把「顺序」这条约束抹掉了
题面写了两条看起来很强硬的规定:请求不能重排、被拒绝的就不能再考虑。但又允许撤销已接受的请求,而且容量约束只落在「被接受请求占用的 Block 总数最终不超过 」。
这两条合起来的效果是:最终的接受集合可以是任意一个总价不超过 的子集。
- 属于目标集合的请求,到达时接受它;不属于的,到达时拒绝(反正本来就不打算要)。
- 中途可能因为「先收了个大的」而装不下后面的请求,这时把大的撤销掉、换成后来的小请求即可。
于是顺序、到达时刻、撤销动作都不影响最终能挑出哪些请求。问题化简成一句话:
从 个价钱里挑出尽量多个,使它们的总价不超过 。
贪心:挑最便宜的那几个
拿到这句化简,答案就出来了:把所有需求升序排好,从最小的开始往背包里塞,塞不下为止。
正确性靠交换论证,两句话:
- 若某个方案能接受 个请求,那么这 个需求之和一定不小于「最小的 个需求之和」——把其中任意一个换成更便宜的,总价只会下降。所以「最小的 个装得下」是「 个可行」的必要条件。
- 反过来,最小的 个装得下时,直接取这 个就是可行方案。
于是可行性对 单调:能接受 个就一定也能接受 个(丢掉最贵的那个)。从小到大累加,第一次超过 时停下的位置就是答案。
need = sorted((int(x) + k - 1) // k for x in data[3:3 + n])
used = 0
cnt = 0
for c in need:
if used + c > m: # 升序遍历,后面的只会更贵,直接停
break
used += c
cnt += 1单个请求超过 的情况不需要单独判断:累加到它时 used + c > m 必然成立(used 非负),循环就在那里停下,它不会被计入。
也可以按题面流程在线做:大顶堆 + 撤销
如果不想依赖「撤销把顺序抹掉」这一步推理,可以直接照着题面的流程写:请求一个个到达,能装就装;一旦总占用超过 ,就撤掉当前占用最大的那个请求。
要撤最大的,就要能从「已接受集合」里快速取出最大值——用一个大顶堆存已接受请求的 Block 数。
heap = [] # 存负数,Python 的 heapq 是小顶堆
used = 0
for i in range(n):
c = (int(data[3 + i]) + k - 1) // k
if c > m: # 单个就装不下,直接拒
continue
heapq.heappush(heap, -c)
used += c
if used > m: # 超了就撤掉最占地方的那个
used += heapq.heappop(heap) # 弹出来是负数,加上就是减回去它为什么能给出答案,靠一条不变式:每处理完一个请求,堆里装的都是「个数最多的那类集合里、总占用最小的一个」。
- 新请求进来,若加入后不超 ,个数加一,显然还是「个数最多」;
- 若超了,就从堆里弹掉最大的。弹出的那个要么就是刚加进来的(退回它,占用回到加入之前),要么不小于它(减掉的比加进来的多,占用只会更小),两种情况都不会再超 ;而个数回到加入之前的值——也就是「不加这个请求时能达到的最大个数」,这个值不会因为「多了一个更便宜的选择」而变差。
这条不变式同时说明了在线版和排序版给出同一个答案:两者都在求「总价不超过 的最大可选个数」。
完整代码实现
版本一:排序 + 从小到大累加
import sys
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
m, k, n = int(data[0]), int(data[1]), int(data[2])
# 每个请求占 ceil(len / k) 个 Block
need = sorted((int(x) + k - 1) // k for x in data[3:3 + n])
used = 0
cnt = 0
for c in need:
if used + c > m: # 升序,后面的只会更贵,可以停
break
used += c
cnt += 1
print(cnt)
if __name__ == "__main__":
solve()版本二:按题面流程在线决策(大顶堆 + 撤销)
import heapq
import sys
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
m, k, n = int(data[0]), int(data[1]), int(data[2])
heap = [] # 已接受请求的 Block 需求,存负数当大顶堆
used = 0 # 已接受的 Block 总数
for i in range(n):
c = (int(data[3 + i]) + k - 1) // k
if c > m: # 单个请求就装不下,永远不会被接受
continue
heapq.heappush(heap, -c)
used += c
if used > m: # 超了就撤销最占地方的那个
used += heapq.heappop(heap)
print(len(heap))
if __name__ == "__main__":
solve()示例推演
示例 1:三个请求、四个 Block
、,三个长度 折算成 Block 数是 。
按题面流程(大顶堆)走一遍:
| 步骤 | 到达需求 | 加入后 used | 是否超限 | 堆内需求 | 被接受个数 |
|---|---|---|---|---|---|
| 1 | 3 | ,不动 | 1 | ||
| 2 | 1 | ,不动 | 2 | ||
| 3 | 2 | ,撤掉最大 | (撤掉 3,used 变 ) | 2 |
最后堆里是 ,个数 。
按排序版走一遍:需求升序是 。 装下(used=1), 装下(used=3), 装不下()→ 停,答案 。
两种走法得到同一个集合 :第 1 个请求先被接受、又被撤销,换成了第 2、3 个。这就是题面里「撤销先前已接受的请求」那句话的实际用途。不撤销的写法(「能装就装、超了就拒」)在这一组数据上恰好也能得到 ——它收下第 1、2 个请求,正好占满 个 Block——所以这条规则很容易被忽略,样例也测不出来。
示例 2:四个请求、六个 Block
,长度 折算成 。升序排列后是 :
| 累加 | used | 与 比较 | 计数 |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| ,停 | 3 |
答案 ,对应原顺序里的第 1、3、4 个请求。四个全接受要 个 Block,超过上限 ,所以这已经是上界。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 枚举所有子集 | ,只能用来验证小数据 | ||
| 大顶堆在线撤销 | 一趟扫描,每个请求至多进堆一次、出堆一次 | ||
| 排序 + 从小到大累加(最优) | 一次排序加一趟累加,不需要堆,常数最小 |
两版的渐进复杂度相同, 时排序与堆的操作都只有 次量级。排序版少一个堆的开销,代码也短;在线版的好处是读一个决策一个,内存里只留已接受的那部分需求,并且与题面描述逐句对得上。
易错点总结
1. 不敢撤销,只做「能装就装」
把流程写成「used + c <= m 就接受,否则拒绝」,全程不回退。示例 1 恰好还能得 (第 1、2 个请求刚好凑满 个 Block),看起来没问题;换成 、需求 就暴露了:先收下 ,后面两个 都装不下,答案 ,而正确做法是撤掉 、收下两个 ,答案 。这类错误的特征是答案偏小:需求之间的落差越大,漏掉的请求就越多。
2. 堆的方向搞反
heapq 是小顶堆,要取「占用最大」必须存负数:heappush(heap, -c),弹出后用 used += heapq.heappop(heap) 加回去(负数相加就是减)。若直接存正数、超限时 heappop 弹出的是最小需求,占用非但没降下来,还会把刚收下的小请求扔掉:、需求 的数据上依次得到 、、,答案 。更隐蔽的写法是 used -= heapq.heappop(heap) 配正数堆——那会减掉最小值,used 依然超限,之后每个请求都被判超限。
3. 排序版的判据写成 used + c >= m
>= 会把「正好塞满」的请求也判成装不下:、需求 时第一次 2+2 >= 4 成立,直接 break,输出 ,而正确答案是 (正好占满 个 Block 是合法的)。官方两组样例都不会走到「恰好等于 」这一步,所以这个 off-by-one 在样例上看不出来。