摘要：ChatGPT 能写出红黑树代码，是否意味着数据结构与算法已经过时？恰恰相反——翻开 vLLM 的源码，PagedAttention 用操作系统经典的分页思想将 KV Cache 碎片率从 60-80% 压到不足 4%；Sequoia 推测解码用动态规划构造最优 Token 树，实现 4 倍推理加速；HNSW 图算法支撑着每一个 RAG 系统的向量检索。LLM 不是 DS&A 的终结者，而是放大器：它能替你写代码，但不能替你理解为什么 PagedAttention 能让单张 H100 的并发数从十几跳到上百。本文从五个生产实测案例出发，拆解数据结构与算法在大模型推理、检索、生成全链路中的核心作用——带你从"调 API"跃迁到"理解它为什么快"。

---

目录

• 一、"八股文"真的没用了吗？
• 二、KV Cache 的虚拟内存革命：PagedAttention
• 三、推测解码：动态规划与树结构加速推理
• 四、向量检索的图算法：HNSW
• 五、Tokenizer 的前缀树：BPE 与 Trie
• 六、为什么 LLM 是 DS&A 的放大器而非终结者
• 七、避坑指南
• 八、摘要总结

---

一、"八股文"真的没用了吗？

“LeetCode 还有必要刷吗？GPT-5.6 两秒钟就能写出一段能过 90% 测试用例的 DP 代码。” —— 这是 2026 年开发者社区最常被提起的困惑。

答案是：LLM 能替你写代码，但不能替你理解为什么快。 更好的问题应该是——你的 LLM 应用到底跑在哪一层？

三个层级，三种对 DS&A 的需求

层级 1：调 API（如 openai.chat.completions.create）
    不需要 DS&A —— 你只是在发送 HTTP 请求。

层级 2：组合 API（如 RAG + Function Calling + 多轮对话）
    基础 DS&A —— 你需要管理 Token 预算、设计检索策略。

层级 3：自建推理系统（如 vLLM + FlashInfer + 自研推测解码）
    深度 DS&A —— 每个比特的内存管理都影响吞吐和成本。

本文聚焦于层级 3——即大模型基础设施本身用到的数据结构与算法。这不是面试造火箭、工作拧螺丝的知识，而是每一个 vLLM、SGLang、FlashInfer 的源码中真实存在的设计决策。以下四个案例均来自 2024-2026 年 MLSys/ICLR/SOSP 等顶会论文或头部开源项目的生产代码。

---

二、KV Cache 的虚拟内存革命：PagedAttention

2.1 问题：60-80% 的显存被浪费

Transformer 自回归生成时，每个 token 的 Key 和 Value 向量必须被缓存（KV Cache），供后续 token 的注意力计算复用——如果不缓存，每一步都需要重新计算所有历史 token 的 K/V，计算量为 O(n²)。

朴素方案的问题不在 KV Cache 的总大小，而在分配方式。 在 PagedAttention 出现之前（vLLM 论文，SOSP 2023），推理引擎为每个请求预留一块连续显存，大小等于"最大上下文长度 × 每 token 的 KV 大小"。实际请求很少达到最大长度，结果为：

┌─────────────────────────────────────────────────────┐
│  请求 A：预留 128K tokens 空间（~4GB）               │
│  ████████░░░░░░░░░░░░░░░░░  实际只用 8K（浪费 ~94%） │
│                                                     │
│  请求 B：预留 128K tokens 空间（~4GB）               │
│  ██████░░░░░░░░░░░░░░░░░░░░░  实际只用 6K（浪费 ~95%）│
│                                                     │
│  结果：大量显存被预留但未被使用的"空洞"占据          │
│  实际有效利用率：20–40%，典型并发数远低于理论值      │
└─────────────────────────────────────────────────────┘

这是一个计算机系统领域最古老的问题——内存碎片，答案也是操作系统教科书中最经典的方法：分页。

2.2 方案：页表 + 块管理器

PagedAttention 将 KV Cache 切分为固定大小的块（默认 16 tokens/块），通过页表（Block Table） 映射逻辑块到物理块，允许非连续物理存储：

请求的 KV Cache： [T0...T15] [T16...T31] [T32...T47]
                       │           │           │
                       ▼           ▼           ▼
物理 HBM：         Block #7    Block #42    Block #3
                     ┌──┐        ┌──┐        ┌──┐
                    │░░│       │  │       │  │
                     └──┘        └──┘        └──┘

Block Table（请求的页表）:
  Logical Block 0 → Physical Block 7
  Logical Block 1 → Physical Block 42
  Logical Block 2 → Physical Block 3

效果对比（基于 vLLM 论文报告的典型场景）：

分配方式	碎片率	典型利用率	并发能力提升
连续分配（朴素）	60-80%	20-40%	基线
PagedAttention	<4%	>96%	数倍于基线（取决于负载分布）

这个设计的巧妙之处还不止于此。因为同一批请求往往共享前缀（如相同的 System Prompt），Prefix Caching 允许这些请求的 Block Table 的前几个逻辑块指向相同的物理块——请求只需在分支点之后分配新块。例如 100 个用户都使用相同的 System Prompt，其 KV Cache 只存一份。当某个请求的实际对话内容与共享前缀分叉时，使用 Copy-on-Write（操作系统经典机制）为该请求分配新的物理块。

2.3 数据结构设计：块管理器

"""
PagedAttention 块管理器的核心数据结构（简化版）
参考：vLLM BlockManager 源码 (vllm/core/block_manager.py)
"""
from dataclasses import dataclass
from typing import List, Dict, Optional


@dataclass
class PhysicalBlock:
    """物理块：16 tokens 的 KV 向量存储在 HBM 的某个位置"""
    block_id: int
    ref_count: int = 0        # 引用计数（共享块管理）
    is_free: bool = True


class BlockTable:
    """单个请求的页表：逻辑块 → 物理块映射"""
    def __init__(self):
        self.mappings: Dict[int, int] = {}  # logical_id → physical_id

    def append(self, physical_id: int):
        self.mappings[len(self.mappings)] = physical_id

    def get_physical_ids(self) -> List[int]:
        return [self.mappings[i] for i in sorted(self.mappings)]


class BlockManager:
    """
    全局块管理器，模拟操作系统的物理内存管理。

    核心操作：
    1. allocate(batch_size) — 为一组请求分配新块
    2. free(physical_ids) — 释放块（引用计数减 1，归零时回收）
    3. copy_on_write(src_bt, fork_point) — 当请求分支时拷贝页表
    """
    def __init__(self, num_blocks: int):
        self.blocks: List[PhysicalBlock] = [
            PhysicalBlock(i) for i in range(num_blocks)
        ]
        self.free_list = list(range(num_blocks))
        self.block_size_tokens = 16

    def allocate(self, num_blocks: int) -> List[int]:
        """从空闲链表分配 N 个物理块（模拟操作系统的 first-fit 分配器）"""
        if len(self.free_list) < num_blocks:
            raise MemoryError(
                f"Out of GPU blocks: need {num_blocks}, free {len(self.free_list)}"
            )

        allocated = []
        for _ in range(num_blocks):
            bid = self.free_list.pop(0)
            self.blocks[bid].is_free = False
            self.blocks[bid].ref_count = 1
            allocated.append(bid)
        return allocated

    def free(self, physical_ids: List[int]):
        """释放物理块，归零引用计数后回收到空闲链表"""
        for bid in physical_ids:
            blk = self.blocks[bid]
            blk.ref_count -= 1
            if blk.ref_count <= 0:
                blk.is_free = True
                blk.ref_count = 0
                self.free_list.append(bid)

    def fork_block_table(
        self, parent_bt: BlockTable, fork_at_logical: int
    ) -> BlockTable:
        """
        Copy-on-Write 分叉页表：
        - fork_at_logical 之前的块：共享（引用计数 +1）
        - fork_at_logical 及之后的块：分配新物理块
        """
        child_bt = BlockTable()

        for i in range(fork_at_logical):
            pid = parent_bt.mappings[i]
            self.blocks[pid].ref_count += 1
            child_bt.mappings[i] = pid

        for i in range(fork_at_logical, len(parent_bt.mappings)):
            [new_pid] = self.allocate(1)
            child_bt.mappings[i] = new_pid

        return child_bt

知识映射： 如果你理解操作系统的虚拟内存（页表、TLB、Copy-on-Write），那么 PagedAttention 就是把同一套思想应用到 GPU 显存管理。vLLM 的作者在 SOSP 2023 论文中直接引用了这个类比——这不是巧合，是知识迁移。

---

三、推测解码：动态规划与树结构加速推理

3.1 问题：自回归是线性、验证是并行

LLM 生成 token 的本质瓶颈：每生成一个 token 需要一次完整的前向传播，而一次前向传播可以并行验证任意多个 token。推测解码（Speculative Decoding）利用这个不对称性：用小模型或模式匹配快速生成 N 个候选 token，然后大模型一次性验证，接受匹配的、丢弃不匹配的。

核心问题转化为：给定每个位置"被接受"的概率，构造什么样的 Token 树能让期望通过 token 数最大化？

3.2 Sequoia：用动态规划构造最优 Token 树

Sequoia（Chen et al., 2024，发表于 ICML 2025）将推测解码的树构造问题形式化为一个最优子结构问题：

• 输入：草稿模型为每个位置预测的 top-k token 及其概率
• 目标：构造一棵 token 树，使得被大模型验证后验证通过的期望 token 数最大
• 约束：树的节点数（总推测量）不超过预算 K

Sequoia 证明这个子问题满足最优子结构：以任一节点为根的子树的最优构造，仅取决于该子树内的概率分布，与树的其他部分无关。因此可以用动态规划在 O(K²) 时间构造全局最优树：

DP[t][n] = 以位置 t 的 token 为根、预算 n 个节点的子树的最大期望通过 token 数

转移方程：
DP[t][n] = p(t) × (1 + max over valid partitions { Σ DP[child_i][n_i] })
           where Σ n_i = n - 1, n_i assigned to subtree of child_i

其中 p(t) 是 token t 被主模型接受到的概率

实际效果（Sequoia 论文报告数据，Llama2-7B, A100）：

方法	推测机制	加速比
朴素自回归	无推测	1.0×
链式推测（SpecInfer 风格）	固定长度链	~1.8-2.0×
并行 top-k 展平（SpecTr 风格）	无结构展平	~2.0-2.5×
Sequoia DP 最优树	动态规划构造最优树结构	最高 4.04×

3.3 SuffixDecoding：后缀树实现零模型开销推测

Snowflake 在 2025 年提出的 SuffixDecoding 走了另一条路：不用草稿模型，而是用后缀树（Suffix Tree）缓存历史请求的 token 序列，直接做模式匹配。

"""
SuffixDecoding 的后缀树核心（简化实现）
参考：Snowflake ArcticInference 源码
"""
class SuffixTreeNode:
    """后缀树节点"""
    def __init__(self):
        self.children: Dict[int, 'SuffixTreeNode'] = {}  # token_id → 子节点
        self.count: int = 0  # 该子序列在历史中出现的次数
        self.depth: int = 0  # 从根到该节点的 token 数


class SpeculativeSuffixTree:
    """基于后缀树的自适应推测解码"""

    def __init__(self, max_nodes: int = 100_000):
        self.root = SuffixTreeNode()
        self.node_count = 0
        self.max_nodes = max_nodes

    def insert_sequence(self, token_ids: List[int]):
        """将一条已生成的 token 序列插入后缀树（插入所有后缀）"""
        for start in range(len(token_ids)):
            node = self.root
            for tid in token_ids[start:]:
                if tid not in node.children:
                    if self.node_count >= self.max_nodes:
                        self._evict_lru()  # 简化实现中此处为 pass，见下方说明
                    node.children[tid] = SuffixTreeNode()
                    self.node_count += 1
                node = node.children[tid]
                node.count += 1
                node.depth = max(node.depth, len(token_ids) - start)

    def lookup(self, context: List[int]) -> List[int]:
        """
        给定当前生成的 token 序列作为上下文，
        在后缀树中匹配已出现过的相同后缀 → 沿频率最高路径续写。

        注意：后缀树存的是所有后缀，路径方向为原始序列方向。
        查找时从上下文末尾向前逐 token 匹配（即匹配最长后缀）。
        """
        node = self.root
        matched_len = 0
        # 从上下文末尾开始匹配最长后缀
        for tid in context:
            if tid in node.children:
                node = node.children[tid]
                matched_len += 1

        # 沿频率最高的子节点贪心扩展推测序列
        draft = []
        current = node
        while current.children and len(draft) < 10:
            best_tid = max(current.children, key=lambda t: current.children[t].count)
            draft.append(best_tid)
            current = current.children[best_tid]

        return draft

    def _evict_lru(self):
        """LRU 淘汰：移除访问频率最低的叶子节点"""
        pass  # 简化实现，生产代码需维护按时间排序的队列

SuffixDecoding 的性能数据（论文报告，SWE-Bench Agent 场景）：

SuffixDecoding 在 SWE-Bench 上实现 5.3× 总加速比，分别比基于模型的 EAGLE-2 和无模型的 Token Recycling 快 2.8× 和 1.9×。

方法	总加速比	额外 GPU 开销	依赖草稿模型？
无优化	1.0×	—	—
EAGLE-2（基于模型）	~1.9×	有	是
Token Recycling（无模型）	~2.8×	无	否
SuffixDecoding	5.3×	无（CPU 后缀树）	否

知识映射： 推测解码的树结构优化 = 数据结构课上的最优二叉搜索树 + 算法课上的动态规划。Snowflake 的工程师之所以能做到 5.3 倍加速，不是因为 LLM 能力更强，而是因为他们把后缀树和频率统计这两个传统算法的老工具用到了新战场。

---

四、向量检索的图算法：HNSW

4.1 问题：如何在亿级向量中毫秒级找到最近邻？

RAG 系统每一步检索都在做同一件事：给定一个查询向量 q（768-4096 维），在百万至十亿级向量库中找到最相似的 k 个。暴力搜索需要 O(N × D) 次浮点运算——10 亿 × 1024 维 = 一次查询触及 4 万亿次浮点计算。即使 SIMD 优化，单次也需 ~40 秒。

近似最近邻（ANN）算法 接受 <5% 的精度损失，换取毫秒级的查询速度。2026 年生产环境的主力算法是 HNSW（Hierarchical Navigable Small World）。

4.2 HNSW 的数据结构

HNSW 是跳表（Skip List）在高维向量空间的推广。它构建了一个多层图结构：

Layer 2 (顶层，稀疏)        ●─────●           ← 长距离跳跃，快速定位区域
                              ╱ ╲
                             ●   ●
                             │   │
Layer 1 (中间层)        ●───●───●───●       ← 中等密度
                         ╲ ╱ ╲ ╱ ╲ ╱
                          ●   ●   ●
                          │╲  │  ╱│
Layer 0 (底层，全连接)  ●─●─●─●─●─●─●─●─●  ← 所有点都在，精确局部搜索

搜索过程：

1. 从顶层入口点开始，贪心向最近邻移动
2. 到达当前层的局部最优后，下降到下一层
3. 重复直到 Layer 0，找到真实最近邻

时间复杂度：O(log N) —— 类比跳表的对数级查找。

4.3 索引选型的工程权衡

HNSW 不是银弹。不同场景有不同最优选择（基于 Milvus 2026 年生产数据）：

索引类型	数据结构	内存倍数	查询延迟(p95)	召回率@10	最佳场景
FLAT	暴力扫描	1.0×	>1s	100%	<10万向量，原型
IVF_FLAT	倒排文件（聚类）	1.05×	50-100ms	95-99%	通用生产
HNSW	多层小世界图	1.5-2.0×	<20ms	98-99%	延迟敏感、高精度
IVF_SQ8	倒排+标量量化	0.3×	30-80ms	93-97%	成本敏感、大规模
DiskANN	图+磁盘存储	0.08×	10-50ms*	95-98%	>10 亿向量，NVMe

*DiskANN 的延迟取决于 SSD 的随机读取性能。

"""
HNSW 索引的构建核心（简化版）
展示跳表思维在高维空间的推广
"""
import numpy as np
import heapq

class HNSWIndex:
    """HNSW 近似最近邻索引 — 跳过完整的内存管理，聚焦算法本质"""

    def __init__(self, dim: int, M: int = 16, ef_construction: int = 200):
        self.dim = dim
        self.M = M                          # 每层每个节点最多 M 条边
        self.ef_construction = ef_construction  # 构建时的搜索宽度
        self.layers: Dict[int, List] = {}   # {layer: [node_ids]}
        self.vectors: Dict[int, np.ndarray] = {}
        self.entry_point: int = None
        self.max_layer: int = 0

    def _random_layer(self) -> int:
        """随机分配层数（指数衰减，跳表的经典概率分配）"""
        # 类似跳表中通过抛硬币决定新节点的层数
        r = np.random.random()
        return int(-np.log(r) * (1 / np.log(self.M)))

    def _search_layer(
        self, query: np.ndarray, entry: int, ef: int, target_layer: int
    ) -> List[tuple]:
        """在单层图的最近邻搜索（贪心 + 候选集扩展）"""
        visited = {entry}
        candidates = [(self._dist(query, self.vectors[entry]), entry)]
        results = [(self._dist(query, self.vectors[entry]), entry)]

        while candidates:
            dist, node = heapq.heappop(candidates)
            # 如果当前最差结果比候选的最近距离还近 → 终止
            if len(results) >= ef and dist > results[0][0]:
                break

            for neighbor in self.layers[target_layer].get(node, []):
                if neighbor in visited:
                    continue
                visited.add(neighbor)
                neighbor_dist = self._dist(query, self.vectors[neighbor])
                heapq.heappush(candidates, (neighbor_dist, neighbor))
                heapq.heappush(results, (neighbor_dist, neighbor))

        return results[:ef]

    def _dist(self, a: np.ndarray, b: np.ndarray) -> float:
        return np.linalg.norm(a - b)

    def query(self, q: np.ndarray, k: int = 10) -> List[tuple]:
        """从顶层入口开始，逐层下降搜索"""
        current = self.entry_point
        # 从最高层向第 1 层逐层下降
        for layer in range(self.max_layer, 0, -1):
            results = self._search_layer(q, current, ef=1, target_layer=layer)
            current = results[0][1]  # 贪心：每层只取最近邻居作为下一层入口
        # Layer 0：全精度搜索（ef 应显著大于 k 以保证召回率）
        results = self._search_layer(q, current, ef=max(k, self.ef_construction // 4), target_layer=0)
        return results[:k]

知识映射： HNSW = 跳表层数分配（抛硬币） + 贪心局部搜索 + 候选集扩展。如果你理解跳表为什么能做到 O(log N)，HNSW 的直觉就立刻浮现——多维空间的跳表。

---

五、Tokenizer 的前缀树：BPE 与 Trie

5.1 BPE 背后的贪心算法

Byte Pair Encoding（BPE）是 GPT 系列 Tokenizer 的核心。它的本质是一个贪心合并算法：

算法：BPE 训练
输入：语料文本，目标词表大小 V
输出：合并规则列表（子词单元集合）

1. 将语料中所有文本切分为单个字符（或字节）
2. 统计所有相邻符号对的频率
3. while 当前词表大小 < V:
     a. 找到频率最高的相邻符号对 (a, b)
     b. 在所有出现位置将 "a b" 合并为 "ab"
     c. 将 "ab" 加入词表
     d. 更新相邻符号对频率统计
4. 返回合并顺序列表

关键数据结构：优先队列（最大堆）维护合并对频率。 这不是什么高深的 AI，就是经典的 Huffman 编码变体——同样的贪心合并思想，只是 Huffman 按频率最小合并构建二叉树，BPE 按频率最大合并构建子词词表。

5.2 推理时：Trie 加速 Tokenization

训练完成后，BPE 的合并规则被固化为一个 Trie（前缀树），推理时在 O(L) 时间内完成分词（L 为输入长度）。真正的工程优化在于：Trie 的每个节点预存了从根到该节点的 token ID，这样匹配成功时无需回溯拼接。

"""
BPE Tokenizer 推理时的 Trie 数据结构
"""
from typing import Dict, List

class BPETokenTrie:
    """基于 Trie 的 BPE 分词推理"""

    def __init__(self):
        self.root: Dict[str, object] = {"children": {}, "token_id": None}
        # 注册所有子词 token
        # 例如 token "play" → id 1234 会在 Trie 中建立路径 p→l→a→y

    def add_token(self, token: str, token_id: int):
        node = self.root
        for ch in token:
            if ch not in node["children"]:
                node["children"][ch] = {"children": {}, "token_id": None}
            node = node["children"][ch]
        node["token_id"] = token_id  # 叶子节点存储 token ID

    def tokenize(self, text: str) -> List[int]:
        """
        最长匹配分词：从当前位置开始沿 Trie 贪心前进，
        在不能继续时取最近一个有效 token ID
        """
        tokens = []
        i = 0
        while i < len(text):
            node = self.root
            last_match_id = None
            last_match_pos = i

            j = i
            while j < len(text) and text[j] in node["children"]:
                node = node["children"][text[j]]
                j += 1
                if node["token_id"] is not None:
                    last_match_id = node["token_id"]
                    last_match_pos = j

            if last_match_id is None:
                # 找不到任何匹配 → 退化为字节级 token
                last_match_id = ord(text[i])
                last_match_pos = i + 1

            tokens.append(last_match_id)
            i = last_match_pos

        return tokens

---

六、为什么 LLM 是 DS&A 的放大器而非终结者

以上四个案例有一个共同特征：LLM 让老算法产生了新价值，而不是替代它们。

经典 DS&A	LLM 时代的新应用	增益
分页/虚拟内存（1960s）	PagedAttention KV Cache 管理（vLLM, SOSP 2023）	碎片率 80%→<4%，并发提升数倍
动态规划（1950s）	Sequoia 推测解码 Token 树构造（Chen et al., ICML 2025）	推理加速最高 4.04×
后缀树（1973）	SuffixDecoding 零开销草稿生成（Snowflake, 2025）	推理加速 5.3×（SWE-Bench）
跳表（1990）	HNSW 亿级向量检索（Malkov et al., TPAMI 2018）	查询延迟 >1s→<20ms
贪心 + 优先队列	BPE 词表训练（Sennrich et al., 2016）	词表压缩 10×+
Trie（前缀树）	Tokenizer 推理 + vLLM Prefix Caching 块级共享	O(N²)→O(N)；同前缀复用
Copy-on-Write（1970s）	vLLM BlockTable fork：前缀请求共享物理块	同 System Prompt 只存一份

一个合成案例：自建高性能 RAG 系统需要的 DS&A 知识图谱

用户查询
   │
   ▼
┌─────────────┐
│ Tokenizer    │ ← BPE Trie：O(L) 分词
└──────┬──────┘
       ▼
┌─────────────┐
│ Embedding    │ ← 查找表（Lookup Table）：矩阵乘法
└──────┬──────┘
       ▼
┌─────────────┐
│ 向量检索     │ ← HNSW 多层图：O(log N) 最近邻
└──────┬──────┘
       ▼
┌─────────────┐
│ 重排序       │ ← 堆 / 优先队列：top-k 选择
└──────┬──────┘
       ▼
┌─────────────┐
│ LLM 推理     │ ← PagedAttention：页表管理 KV Cache
│             │ ← 推测解码：DP 构造 Token 树 / 后缀树模式匹配
└──────┬──────┘
       ▼
┌─────────────┐
│ 流式输出     │ ← 滑动窗口 + Token 预算管理
└─────────────┘

整条链路上的每一个性能关键点，都是一个经典 DS&A 问题在大模型时代的重演。

核心认知：LLM 是一个"需求放大器"——它把原来只在小规模数据上跑的算法，推到了毫秒级、十亿级、并发数百请求的极端场景。在这种情况下，O(N²) vs O(N log N) 的差距不再是一个面试题的得分差距，而是你的 H100 集群能否跑得动的生死线。

---

七、避坑指南

坑	现象	根因	解法
HNSW 内存爆炸	RAG 系统从 10 万向量扩展到 1000 万后 OOM	HNSW 需要 1.5-2× 额外内存存图结构	100 万+ 向量用 IVF_SQ8（0.3×），千万级用 DiskANN
Prefix Cache 不命中	同一批请求因为微小差异（如带不同 user_id 的 System Prompt）导致无法共享前缀	vLLM 的 prefix caching 匹配的是从序列起始位置开始的连续 token 序列，任一 token 不同即断链	将可变部分（用户 ID、时间戳）放在 System Prompt 末尾或单独字段，保持前缀纯净
推测解码树爆炸	Token 树节点数超预算，GPU 验证时间反超自回归	树宽度与深度乘积失控	用 Sequoia DP 做预算约束的最优树构造
PageAttention 块大小选错	小请求的最后一个块平均只用了 25%	块大小固定 16 tokens	短文本场景可用 token-level 粒度（块大小=1）的 FlashInfer
Tokenizer Trie 回溯开销	中文分词时 Trie 深度低、宽度大、查找慢	CJK 字符集 Trie 宽度 ~20000	使用 SentencePiece 的 unigram 模型替代 BPE，或对 CJK 做特殊前缀编码
LLM 生成代码直接上生产	AI 写的 DS&A 代码"看起来对"但性能差 100×	LLM 不知道生产数据规模	AI 生成 → 理解算法 → 性能测试 → 人工优化（四步法）

---

八、摘要总结

"八股文"之所以叫八股文，不是因为它没用，而是因为面试时考生只在纸上作答——没有规模的压强。LLM 时代的核心变化是：规模压强把 O(N²) 和 O(N log N) 的差距从面试题的 20 分变成了 H100 集群月账单的 2 万美元。 PagedAttention 用操作系统的分页思想将 KV Cache 碎片率从 80% 压到 4%；Sequoia 用动态规划逼近推测解码的最优树；SuffixDecoding 用后缀树在 SWE-Bench 场景实现 5.3 倍推理加速；HNSW 把跳表推广到高维空间支撑每秒百万次向量检索。从虚拟内存到 DP、从 Trie 到 Copy-on-Write——这些"老八股"没有被 LLM 淘汰，反而因为 LLM 的出现，第一次在真实产品中展现了它们的全部威力。LLM 不是 DS&A 的终结，而是它最好的放大器。你能走多远，取决于你底层的"八股文"有多深。

参考来源：

• vLLM: Efficient Memory Management for LLM Serving with PagedAttention (SOSP 2023)
• Sequoia: Scalable and Robust Speculative Decoding (ICML 2025)
• SuffixDecoding: Extreme Speculative Decoding for Agentic Workloads (2025)
• FlashInfer: Efficient Attention Engine for LLM Serving (MLSys 2025)
• SeKV: Resolution-Adaptive KV Cache (UBC/Microsoft, 2026)
• HNSW: Efficient and Robust Approximate Nearest Neighbor Search (TPAMI 2018)
• Milvus: How to Cut Vector Database Costs by Up to 80% (2026)
• ANN Algorithms Behind Fast Vector Retrieval (Mixpeek, 2026)
• 大模型中的数据结构和算法：Token到KV缓存全链路 (腾讯云, 2026)
• PagedAttention Deep Dive (JM Román, 2026)