拼多多 AI Infra 提前批一面：前缀和算法题与推测解码深挖

《面试题目》

1. 算法题：给定一个数组，可以删除一段连续区间，使剩余元素之和能够被 K 整除，求最少删除多少个元素。
   • 能否使用双指针？为什么？
   • 双指针是否具备所需的单调性？
   • 如何使用前缀和完成 O(n²) 解法？
   • 被删除区间需要满足什么取模条件？
   • 如何使用前缀和取模与哈希表优化到 O(n)？
   • 哈希表应该保存最早还是最近出现的位置？
2. 推测解码：Speculative Decoding 的基本原理是什么？Draft model 和 Target model 分别负责什么？如何保证输出分布与目标模型一致？树状候选草稿如何生成？候选未命中后如何处理？树的深度、宽度与 fan-out 如何设置？提前生成更多候选是否会增加额外成本？草稿长度与系统性能为什么不一定是单调关系？调度策略如何设计？使用了什么框架实现？与其他推测解码方案有什么区别？项目的性能提升和实验结果如何？
3. 大模型推理框架：了解哪些主流推理框架？vLLM 的主要优化点是什么？Continuous batching 的工作原理？大模型推理为什么经常受访存限制？KV Cache 的作用和显存开销怎么算？PagedAttention 解决了什么问题？Block table 如何管理 KV Cache？FlashAttention 为什么能够加速？Tiling 和在线 Softmax 的作用是什么？FlashAttention 本质上减少了哪些操作？
4. 求职方向：是否有实习经历？为什么选择大模型推理方向？更偏向科研、工程还是业务落地？希望从事哪类技术工作？对未来岗位有什么期待？

《参考解析》

算法题：前缀和 + 取模哈希，O(n)

设 P[i] = a[1] + … + a[i]（P[0] = 0），删除区间 (l, r] 后剩余和是 P[n] - (P[r] - P[l])。要求它被 K 整除，等价于

P[l] ≡ P[r] - P[n]  (mod K)

也就是「被删区间的和 ≡ 总和 mod K」。所以枚举右端点 r，只需要知道满足该余数的最小的 l，代价是删除 r - l 个元素。用一个哈希表记录每个余数最早出现的下标（因为固定 r 时 r - l 随 l 变小而变大，取最早的就是最优），r 从小到大扫一遍，先查表（此时表里只有 ≤ r 的下标，天然满足 l ≤ r），再把 P[r] 的余数按「不存在才写入」补进表里。整体 O(n) 时间、O(min(n, K)) 空间。

双指针不成立，因为这里要的是取模相等的精确条件，不是「和越大/越小」这种单调关系：余数在模 K 意义下是循环的，窗口右扩或左缩都不能保证「更接近目标」，数组里存在负数时连区间和的单调性都没有。O(n²) 的写法就是枚举所有 (l, r)，用前缀和 O(1) 判断 (P[n] - P[r] + P[l]) % K == 0，取最小长度。边界别忘了：若 P[n] % K == 0（K = 1 必然如此），答案是 0，即不删任何元素。

推测解码：分布一致性靠「接受-拒绝」而不是近似

Draft model（小模型）自回归地一次生成 γ 个候选 token，Target model（大模型）用一次前向并行验证这批候选。逐位置比较两个分布：以 min(1, p(x) / q(x)) 的概率接受草稿 token；一旦某个位置被拒绝，就从残差分布 norm(max(0, p - q)) 重新采样一个 token，并丢弃该位置之后的全部草稿。这套接受-拒绝规则能严格保证最终输出分布等同于目标模型单独解码的分布，是「无损加速」，而不是用质量换速度——这一点是面试官必问的。

树状草稿（Medusa / SpecInfer 一类）在同一位置扩展多个候选形成树，用树形 attention mask 一次验证整棵树，最终接受从根出发的最长匹配路径。取舍在于：树更深更宽能提高至少命中一条路径的概率，但被拒绝的分支纯属浪费算力，验证阶段的注意力开销也随候选块长度增长；同时草稿越长，draft 与 target 分布偏差累积越严重，接受率下降。所以草稿长度与端到端加速不是单调关系，通常存在最优的 γ（常见 3~8），超过后 speedup 饱和甚至倒退。工程上还要考虑 draft 与 target 的调度（同卡还是分卡、draft 是否要单独批处理）、候选块与 continuous batching 的配合，以及用接受率、平均接受长度、每 token 延迟这几个指标做实验对照。

vLLM 与 KV Cache：把显存从「碎片」变成「分页」

自回归解码每一步都要用到历史 token 的 K、V，KV Cache 的作用就是避免每步对全部历史重算。它的显存开销可以按公式估：2（K 和 V）× 层数 × KV 头数 × head_dim × 序列长度 × dtype 字节数。以 Llama-2-7B fp16 为例，2 × 32 × 32 × 128 × 2B = 0.5MB/token，一条 4K 上下文的请求就是 2GB 量级——所以推理的瓶颈经常是访存而不是算力：每生成一个 token 都要把全部权重和 KV 从 HBM 读一遍，算术强度低，GPU 计算单元大量空转。

vLLM 的核心优化是 PagedAttention：把 KV Cache 切成固定大小的 block，用 block table 维护「逻辑块 → 物理块」的映射，序列在显存里不再要求连续。这带来三个好处：内部碎片从「按最大长度预留」的浪费降到块内少量浪费（官方报告显存浪费低于 4%），相同前缀可以共享物理块（并行采样、beam search 用 copy-on-write），以及不同序列的块可以自由拼接进同一批次。配合 continuous batching（迭代级调度，每个 iteration 都能让新请求加入、完成的请求退出，而不是等整批跑完）和 chunked prefill、prefix caching，把 GPU 利用率拉起来。

FlashAttention：不落 HBM 的精确注意力

标准注意力要把 L × L 的分数矩阵写回 HBM 再做 softmax，显存和 IO 都是 O(L²)。FlashAttention 的做法是 tiling + 在线 Softmax：把 Q、K、V 分块载入 SRAM，在片上算块内分数、用「运行时最大值 m 与运行和 l」边算边归一化并累积输出，全程不物化完整分数矩阵。它是精确计算（不是近似），减少的是 HBM 读写量和显存占用，把注意力从访存受限推向接近计算受限；反向传播时用重算（activation recomputation）替代保存中间矩阵，用算力换显存。同一条思路还能解释面试常问的另一个点：连续两个逐元素算子（如 X = A∘B、Y = X + C）如果不融合，每个算子都要把输入输出全量读写 HBM 两遍，融合成一个 Kernel 就能省掉中间张量的往返流量，这也是算子融合在推理里收益明显的原因。