代码随想录

# 数据结构与算法在大模型时代有什么用 — 专栏规划

录友们学完算法最常问的就是："学这些有什么用？"

大模型的爆发给了这个问题最好的回答——从推理优化到向量检索，从搜索采样到 Agent 规划，数据结构与算法无处不在。

本专栏梳理大模型技术栈中用到数据结构与算法的核心知识点，每个按"你学过的算法 → 大模型里的应用 → 为什么需要它"来讲解。

# 一、推理优化（最直接的关联）

# KV Cache

  • 生成第 t 个 token 时，前 t-1 个 token 的 K、V 向量不需要重新算
  • 本质：空间换时间，用缓存避免重复计算
  • 对应算法：哈希表缓存、记忆化搜索（DP 中的 memo 数组）
  • 问题：序列越长，缓存越大 → 引出 PagedAttention

# PagedAttention（vLLM）

  • KV Cache 显存碎片问题：不同请求长度不同，预分配浪费、动态分配碎片化
  • 借鉴操作系统虚拟内存分页：把 KV Cache 切成固定大小的 block，用页表映射
  • 对应算法：链表管理空闲块、LRU 淘汰、碎片整理（类似磁盘整理）
  • 为什么重要：让 vLLM 的吞吐量比 HuggingFace 原生推理高 24 倍

# 连续批处理（Continuous Batching）

  • 传统批处理：等一个 batch 全部生成完才处理下一批，短序列被长序列拖慢
  • 连续批处理：某个请求生成完毕立刻填入新请求，类似生产者-消费者模型
  • 对应算法：调度算法（Shortest Job First 的变体）、队列管理
  • 类比：医院叫号 vs 批量看病

# 投机解码（Speculative Decoding）

  • 小模型（draft model）快速生成 k 个候选 token，组成一棵树
  • 大模型（verify model）一次前向传播验证这 k 个 token，接受正确的、拒绝错误的
  • 对应算法：树的构建 + 回溯（被拒绝处回溯，换路径重新搜索）
  • 为什么重要：自回归解码是串行的，投机解码用树结构把串行变并行

# 闪存注意力（FlashAttention）

  • Self-Attention 计算需要 O(n²) 的中间矩阵 S，显存是瓶颈
  • FlashAttention 用分块计算（Tiling）：把 Q、K、V 切成小块，在 SRAM 中计算完再写回 HBM
  • 对应算法：分治思想，大问题拆小问题，减少 IO 次数
  • 类比：外部排序中归并排序的思路——数据太大放不进内存，分块处理

# 二、搜索与采样（算法直接上场）

  • 每一步保留得分最高的 k 条路径（beam width = k），而不是所有路径
  • 对应算法：限宽的 BFS，本质是贪心 + 队列
  • 和 Dijkstra 的关系：Dijkstra 保证最优，Beam Search 不保证，但空间从 O(b^d) 降到 O(k·d)
  • 为什么不用 DFS：生成文本需要全局最优感，DFS 容易陷入局部
  • Beam Search 的变种：Diverse Beam Search（加入多样性惩罚，类似模拟退火中的随机扰动）

# Tree of Thoughts（ToT）

  • 把思维链建模成一棵搜索树，每个节点是一个推理状态
  • 对应算法：DFS + 剪枝 + 回溯
  • BFS 版本：每层评估所有候选，选最优的展开下一层
  • DFS 版本：深度优先探索一条路径，不行就回溯
  • 和回溯算法的映射：评估函数 = 剪枝条件，状态转换 = 递归展开

# Graph of Thoughts（GoT）

  • ToT 的扩展：思维不是树而是图，允许合并不同的推理路径
  • 对应算法：DAG + 拓扑排序，多路径汇合就是合并节点
  • 例子：先分别推理出两个子方案，再把优点合并成最终方案

# Top-k / Top-p 采样

  • Top-k：从概率最大的 k 个 token 中采样 → 取前 k 大元素，小顶堆 O(n log k)
  • Top-p（nucleus sampling）：选累积概率达到 p 的最小 token 集合 → 前缀和 + 二分查找
  • 温度（Temperature）：调整概率分布的锐度，本质是对 logits 做缩放
  • 为什么不用贪心（argmax）：贪心生成重复且无趣，采样引入随机性让输出更多样

# Agent 规划与搜索

  • ReAct 模式：Thought → Action → Observation 循环，本质是状态机
  • 多步工具调用：每次调工具得到新信息，更新状态再决策 → BFS/DFS 搜索状态空间
  • 规划算法：蒙特卡洛树搜索（MCTS）在 Agent 中的应用，AlphaGo 同款

# 三、RAG 与向量检索（工业界最热门）

# HNSW（分层可导航小世界图）

  • 向量近似最近邻（ANN）检索的核心算法
  • 结构：多层图，底层包含所有点，上层逐步稀疏（类似跳表的结构）
  • 查询：从顶层贪心向下搜索，每层找最近邻 → 贪心 + 图遍历
  • 对应算法：跳表（多层索引）、贪心搜索、图的 BFS
  • 为什么不用精确搜索：高维空间精确最近邻是 O(n)，ANN 用 O(log n) 换可接受的误差

# 乘积量化（Product Quantization, PQ）

  • 把高维向量切成 m 段，每段独立聚类（K-Means），用聚类中心 ID 代替原始向量
  • 对应算法：哈希 + 分桶，用离散编码近似连续值
  • 距离计算：查表求和，避免浮点乘法 → 空间压缩 8-64 倍
  • 类比：邮编系统——用几个数字近似代表地理位置

# 倒排索引

  • 传统关键词检索的基础：从关键词到文档列表的映射
  • 对应算法：哈希表，key 是词，value 是倒排链表（有序数组，支持交并集）
  • 多关键词查询：多个有序链表求交集 → 多指针归并（类似归并排序的 merge 步骤）
  • RAG 中的混合检索：向量检索（语义）+ 关键词检索（精确）→ 两路结果做融合排序

# 向量数据库的索引结构

  • IVF（倒排文件索引）：先聚类，查询只搜最近的几个簇 → 分桶 + 剪枝
  • HNSW：图索引，见上
  • DiskANN：磁盘友好的图索引，类似 LSM-Tree 的思路（磁盘顺序写 + 内存缓存）
  • 对应算法：B+ 树（传统数据库索引）的演进，核心都是减少 IO 次数

# 四、模型架构本身

# Self-Attention 的复杂度问题

  • 标准 Attention：O(n²) 时间、O(n²) 空间，n 是序列长度
  • 对应算法：复杂度分析——为什么 O(n²) 不可接受？n=128K 时中间矩阵 16G
  • 稀疏 Attention：只计算部分 token 对的注意力 → 用滑动窗口 + 全局 token 的混合策略
  • 线性 Attention：用核函数近似 softmax → 用 O(n) 换 O(n²) 的近似解

# 位置编码（RoPE）

  • 为什么需要位置编码：Self-Attention 是排列不变的（和集合一样），需要注入位置信息
  • RoPE：用旋转矩阵编码相对位置 → 复数乘法 = 旋转 = 坐标变换
  • 对应数学：欧拉公式、极坐标变换
  • 长度外推：NTK-aware 插值、YaRN → 类似数值分析中的插值方法

# Mixture of Experts（MoE）

  • 每层有 N 个专家（前馈网络），路由器只选 top-k 个激活
  • 对应算法：哈希路由 + Top-k 选择（小顶堆）
  • 负载均衡：加辅助损失防止所有 token 都走同一个专家 → 类似哈希表的均匀分布问题
  • DeepSeek MoE 的细粒度：更多小专家 + 更灵活路由 → 搜索空间更大

# 多头注意力（Multi-Head Attention）

  • Q、K、V 投影到 h 个子空间，分别计算 Attention 再拼接
  • 对应算法：分治——把高维问题拆成多个低维子问题，并行求解再合并
  • GQA（分组查询注意力）：多组共享 K、V → 在质量和效率间取折中，类似缓存共享

# 五、Tokenization

# BPE（Byte Pair Encoding）

  • GPT 系列的分词算法
  • 过程：统计所有相邻字节对频率，反复合并最高频的对，直到词表达到目标大小
  • 对应算法：贪心算法 + 优先队列（每次取频率最高的对）
  • 实现：用优先队列维护所有 pair 的频率，合并后更新相邻 pair → O(n log n)
  • 类比：哈夫曼编码也是贪心 + 优先队列，不过哈夫曼是自底向上建树，BPE 是逐步合并

# Trie（前缀树）

  • SentencePiece 中的核心结构
  • 用途：给定一个字符串，快速查找最长匹配的 token
  • 对应算法：Trie 查找，O(L) 时间，L 是 token 最长长度
  • 和前缀树的应用场景一样：搜索框自动补全、拼写检查、IP 路由表

# Unigram 模型

  • SentencePiece 的另一种模式：从大词表开始，逐步删减低频 token
  • 对应算法：贪心删减 + Viterbi 解码（动态规划求最优分词路径）
  • Viterbi 解码：dp[i] = min(dp[j] + cost(word[j:i]))，本质是最短路径问题

# 六、Agent 与工具调用

# ReAct 模式

  • 循环：思考（Reasoning）→ 行动（Acting）→ 观察（Observation）
  • 对应算法：状态机，三个状态循环转移，直到输出"最终答案"
  • 和 BFS 的关系：每次 Action 是一次状态转移，Observation 是转移结果
  • 挑战：死循环（状态重复）→ 需要访问集合去重（哈希表判重），类似 BFS 中的 visited 数组

# 多 Agent 协作

  • 多个 Agent 各自负责子任务，有依赖关系 → 任务图是 DAG
  • 对应算法：拓扑排序决定执行顺序，并行执行无依赖的节点
  • 例子：调研 Agent → 写作 Agent → 审核 Agent，调研和审核可以并行，写作依赖调研
  • MapReduce 思想：大任务拆成子任务并行处理（Map），再合并结果（Reduce）

# 记忆机制

  • 短期记忆：上下文窗口 → 滑动窗口，先进先出
  • 长期记忆：外部数据库 → 向量检索（见第三章）
  • 记忆淘汰：上下文太长需要裁剪 → LRU 缓存淘汰，保留最近/最相关的
  • 记忆压缩：对历史对话做摘要 → 有损压缩，保留关键信息

# 规划算法在 Agent 中的应用

  • MCTS（蒙特卡洛树搜索）：选择 → 扩展 → 模拟 → 回溯，四步循环
  • 对应算法：树搜索 + 随机采样 + UCB 公式（探索与利用的平衡）
  • 和 AlphaGo 的联系：AlphaGo 用 MCTS 搜索棋局，Agent 用 MCTS 搜索行动方案

# 七、训练相关

# 自动微分与计算图

  • 前向传播：沿 DAG 拓扑序计算每个节点的值
  • 反向传播：沿 DAG 逆拓扑序计算梯度 → 拓扑排序 + 链式法则
  • 对应算法：DAG 的拓扑排序、链式法则 = 动态规划（子问题的梯度被复用）
  • 梯度累积：多个小 batch 的梯度求和再更新 → 等价于大 batch，空间换时间

# 分布式训练

  • 数据并行：每个 GPU 拿不同数据，梯度同步 → AllReduce
  • AllReduce 的 Ring 版本：GPU 排成环形，分步传递梯度 → 环形通信 + 归约
  • 对应算法：树形归约（Reduce-Scatter）+ 树形广播（All-Gather）
  • 流水线并行：模型按层切分到不同 GPU，微批次流水执行 → 流水线调度
  • 张量并行：矩阵乘法按行列切分到不同 GPU → 分块矩阵乘法

# 混合精度训练

  • FP16 做前向和梯度计算，FP32 维护主权重
  • 对应算法：精度与效率的权衡，用低精度近似加速，高精度兜底防止溢出
  • 梯度缩放：乘以一个缩放因子防止 FP16 下溢 → 动态调整缩放因子（类似学习率调度）

# 检查点（Checkpointing）

  • 训练中定期保存模型状态，故障后从最近检查点恢复
  • 对应算法：检查点/回滚机制，和数据库的 WAL（预写日志）思路一致
  • 激活重计算：不保存中间激活，反向传播时重新算 → 用时间换空间，和 KV Cache 的空间换时间正好相反
上次更新：: 4/22/2026, 9:10:06 AM

评论

验证登录状态...