你在做一个本地大模型聊天服务，机器只有 2GB RAM；模型做了 4-bit 量化后，权重常驻内存仍占 1.35GB，剩余 650MB 要同时容纳激活值和所有在线会话的 KV cache。请求在线到达，每个请求 \(i\) 有提示长度 \(p_i\)、预计生成长度 \(g_i\)、优先级 \(w_i\)、软截止时间 \(d_i\)。prefill 可以任意切块，decode 只能按 token 逐步进行；任一请求可以在 token 边界抢占，但如果它的 KV 被驱逐到 SSD，恢复时要付出额外 I/O 延迟。假设你还能用一个轻量预测器估计每个请求的剩余输出长度和“未来还会不会继续生成”。
请设计一个在线方法，决定：1）哪些请求接入/拒绝；2）当前时刻先服务哪些请求；3）KV cache 如何驱逐/保留。你要说明目标函数、核心状态设计、复杂度、以及在未来请求分布未知时如何做鲁棒取舍；如果你认为精确最优不可在线求解，也要说明原因，并给出可落地的近似策略。
这是一个典型的在线多资源调度任务：同时受计算、内存、I/O 三重约束，还带截止时间和未知未来到达，精确最优通常不可在线求解；离线版本里也至少包含 0-1 knapsack / deadline scheduling 的子任务，因此我会把它拆成“接入控制 + 解码调度 + KV 驱逐”三层。
第一层是接入控制。对每个新请求先估一个总成本： \[ C_i = \alpha p_i + \beta \hat g_i + \gamma \cdot \text{swap\_cost}_i + \delta \cdot \text{deadline\_slack}_i^{-1} \] 再定义单位资源收益： \[ S_i = \frac{w_i}{C_i + \lambda M_i} \] 其中 \(M_i\) 是其峰值 KV 占用，\(\hat g_i\) 来自轻量预测器。在线时只接入当前边际收益高于阈值、且留有安全内存水位的请求；否则放入短队列或拒绝。这个阈值不是固定的，而是根据最近一段时间的 miss rate 和 SSD 带宽动态调大/调小，避免抖动。
第二层是解码调度。已接入请求中，我会用“截止时间优先 + aging”的策略：先按剩余 slack 排序，slack 很小的优先；但为了防止长请求饿死，再叠加一个 aging 项，等待越久，优先级越高。每次调度只在 token 边界抢占，batch 内尽量把 next-token 时间相近、KV 已热的请求放在一起，减少切换和 cache miss。对于 prefill，尽量切成小块，块与块之间重新评估是否继续接入，避免一个超长 prompt 把整机拖成 head-of-line blocking。
第三层是 KV 驱逐。这里不能用纯 LRU，因为“最近用过”不等于“未来最值钱”。我会给每个 KV block 一个保留分数： \[ R_j = \frac{P(\text{future use}\mid j)\times (\text{recompute cost} + \text{restore cost})}{\text{bytes}(j)} \] 驱逐时优先弹出 \(R_j\) 最小的块，也就是“单位字节未来价值最低”的块。对于 prompt 前半段、未来复用概率低且重算便宜的块，优先放到 SSD 甚至直接丢弃重算；对于临近生成尾部、下一 token 立刻会用到的块，尽量常驻 RAM。实现上用一个最小堆维护驱逐候选，更新代价是 \(O(\log n)\)。
如果要做短视窗内的更优决策，我会把未来 1-2 秒的候选请求展开成一个小型时间展开图，做 min-cost max-flow 或带容量约束的最短路近似；但在在线服务里，我更倾向于“窗口化贪心 + 动态阈值”，因为它足够稳定、易解释、可控。整体复杂度上，接入/驱逐/调度的主操作都能做到 \(O(\log n)\)；内存是 \(O(n_{\text{active}})\)。
工程上最重要的三点：一是留安全水位，不能把 650MB 用满，否则一旦 burst 到来会直接抖成超时风暴；二是把 SSD 带宽纳入决策，否则 I/O 会比计算先成为瓶颈；三是加公平性保护，例如对长会话加 aging 或配额，避免短请求把长请求永久挤掉。我的经验是，这类系统不是追求单点最优，而是追求在 miss rate、吞吐、p95 latency 之间稳定可控的 Pareto 点。
强答至少要覆盖四件事：先判断这是在线多资源调度/缓存任务，而不是单纯“写个 LRU”；明确目标函数里必须同时考虑优先级、截止时间、内存占用、swap 成本；说明为什么精确最优很难在线求解，并给出可落地的近似或分层策略；最后把复杂度说清楚，尤其是每次请求到达、每次 token 解码、每次 KV 驱逐的代价。
常见扣分点：只讲 EDF 不讲内存和 KV；只讲 LRU 不讲未来价值；忽略 SSD 读写开销和恢复代价；把未来长度当作已知；没有解释如何防止长请求饿死；复杂度只说“很快”不落到 \(O(\log n)\) 或更具体。出练习者通常会继续追问：如果 burst 很大怎么办、如果预测器偏差很大怎么办、如果 SSD 带宽减半怎么办、如何做公平性和稳定性保护。
- 如何证明该任务至少包含 NP-hard 子任务？
- 如果 SSD 带宽下降 50%，策略怎么改？
- 如何避免长请求被短请求饿死？