TurboQuant 学习路径：论文 → 技术 → 数学 #
一、必读论文（按学习顺序） #
阶段 1：量化基础 #
| 论文 | 年份 | 核心内容 | 与 TurboQuant 的关系 |
|---|
| Product Quantization for Nearest Neighbor Search (Jégou et al.) | 2011 | PQ 算法，将向量空间分解为子空间独立量化 | PolarQuant 的分组量化思想来源 |
| Optimized Product Quantization (Ge et al.) | 2013 | OPQ，引入正交变换优化 PQ | 旋转矩阵预处理的先驱 |
| Additive Quantization for Extreme Vector Compression (Babenko & Lempitsky) | 2014 | AQ/LPQ，码本优化 | 理解量化误差分析 |
阶段 2：JL 变换与随机投影 #
| 论文 | 年份 | 核心内容 |
|---|
| Locality-Sensitive Hashing Scheme Based on p-Stable Distributions (Datar et al., LSH) | 2004 | LSH 基础 |
| Similarity Estimation Techniques from Rounding Algorithms (Charikar, SimHash) | 2002 | Sign-random-projection，1-bit 哈希 |
| The Fast Johnson-Lindenstrauss Transform (Ailon & Chazelle) | 2006 | FJLT，快速 JL 实现 |
阶段 3：LLM KV Cache 压缩 #
| 论文 | 年份 | 核心内容 | 必读原因 |
|---|
| KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache (Liu et al.) | 2023 | 非对称量化，Key/Value 不同精度 | TurboQuant 的主要对比 baseline |
| H2O: Heavy-Hitter Oracle (Zhang et al.) | 2023 | 动态稀疏化，保留重要 token | 理解 KV 缓存瓶颈的另一种思路 |
| StreamingLLM (Xiao et al.) | 2023 | Attention Sink 现象 | 长上下文建模的基础 |
| QuaRot: Outlier-Free 4-Bit Inference in Rotated LLMs (Ashkboos et al.) | 2024 | 旋转消除异常值，在线量化 | 与 TurboQuant 思路最接近 |
阶段 4：TurboQuant 原文 #
| 论文 | 会议 | 状态 |
|---|
| TurboQuant: Towards Ultra-Fast Quantization for LLM KV Cache and Vector Search | ICLR 2026 | 待发表（2026年3月博客发布） |
| PolarQuant: Polar Quantization for Vector Compression | AISTATS 2026 | 待发表 |
| Quantized Johnson-Lindenstrauss Transform | 伴随论文 | 待发表 |
二、关键技术栈 #
1. 向量量化技术 #
标量量化 (Scalar Quantization)
├── 均匀量化: x_q = round((x - z) / s)
├── 非对称量化: per-channel/per-token scaling
└── 对称量化: zero-point = 0
矢量量化 (Vector Quantization)
├── PQ: x → [x_1, ..., x_m] → argmin_c ||x_i - c||
├── OPQ: x → R·x → PQ (含旋转)
└── 残差量化: x → c_1 + c_2 + ... (级联)
2. Johnson-Lindenstrauss 实现技术 #
1
2
3
4
5
6
7
8
| # 标准 JL: y = (1/√k) · R · x
# R ∈ R^{k×d}, R_{ij} ~ N(0,1)
# 稀疏 JL (Achlioptas): R_{ij} ∈ {+1, 0, -1} with prob {1/6, 2/3, 1/6}
# Fast JL (Ailon-Chazelle):
# y = P·H·D·x
# D: random signs, H: Hadamard, P: subsampling
|
3. 在线量化 (Online Quantization) #
- 动态范围估计: 运行时分桶统计 min/max
- 逐 token/逐通道量化: 不同粒度的 scaling
- 异常值处理: 旋转平滑 (QuaRot)、CLIPPING
4. CUDA/GPU 优化（工程实现） #
- Bit-packing: 将多个低位整数打包到 32/64-bit 寄存器
- Vectorized load/store: 128-bit/256-bit 内存访问
- Warp shuffle: 减少 shared memory 使用
三、数学知识清单 #
1. 线性代数（必备） #
| 概念 | 具体内容 | 应用场景 |
|---|
| 正交矩阵 | R^T R = I, 保范性 | |
| 极坐标/球坐标 | x = r · x̂, r = | |
| Hadamard 变换 | H_n = H_1 ⊗ H_{n-1} | 快速旋转 |
| 奇异值分解 (SVD) | X = UΣV^T | 分析数据分布、PCA 预处理 |
| 内积与角度 | <x, y> = | |
2. 概率论与随机过程（核心） #
| 概念 | 具体内容 | 应用场景 |
|---|
| 集中不等式 | Hoeffding, Chernoff, Bernstein bounds | JL 变换误差分析 |
| 亚高斯随机变量 | P( | X |
| 高维几何 | Concentration of measure on sphere | 理解高维向量分布 |
| 随机矩阵理论 | 特征值分布、Marchenko-Pastur law | 分析旋转后数据 |
关键公式 - Hoeffding 不等式：
P(|(1/m)∑X_i - E[X]| ≥ t) ≤ 2exp(-mt^2/2)
用于证明：m 维 QJL 投影足够大时，估计误差指数级小。
3. 信息论 #
| 概念 | 具体内容 | 应用场景 |
|---|
| 熵 (Entropy) | H(X) = -∑ p(x)log p(x) | 量化比特数下限 |
| 率失真理论 | R(D) = min I(X;X̂) | 最优量化理论极限 |
| 量化误差 | MSE, l2 distortion, inner product distortion | TurboQuant 优化目标 |
4. 优化理论 #
| 概念 | 具体内容 | 应用场景 |
|---|
| Lloyd-Max 量化器 | 最优标量量化的迭代算法 | 理解最优量化 |
| k-means / 矢量量化 | 码本学习 | PQ/AQ 训练 |
| 凸优化 | 拉格朗日对偶、KKT条件 | 约束优化问题 |
四、推荐学习路线图 #
Week 1-2: 基础夯实
├── 线性代数复习（3Blue1Brown 视频 + 正交变换）
├── 概率论（高维几何、集中不等式）
└── 读 Product Quantization 论文
Week 3-4: 进阶技术
├── 深入 JL 变换（FJLT 论文）
├── 学习 SimHash/LSH
└── 读 KIVI 论文 + 代码实现
Week 5-6: LLM 量化专题
├── 读 QuaRot 论文（与 TurboQuant 最接近）
├── 理解 KV Cache 内存分析
└── 实现简单的 KV 量化 demo
Week 7+: TurboQuant 深入
├── 研究 PolarQuant 的极坐标递归变换
├── 推导 QJL 的无偏估计证明
└── 阅读官方代码（发布后）
五、代码资源预习 #
必看的开源实现 #
Faiss (Facebook AI): faiss::IndexPQ, faiss::IndexOPQ
QuaRot: https://github.com/spcl/QuaRot
KIVI: https://github.com/jy-yuan/KIVI
数学工具库 #
- NumPy/SciPy: 矩阵运算、SVD、Hadamard 变换
- JAX: 自动微分（理解梯度流）
- PyTorch:
torch.quantization 模块
六、自测问题 #
在开始阅读 TurboQuant 之前，确认你能回答：
- 为什么高维随机向量几乎正交？（高维几何）
- 证明：随机投影保持内积期望不变
- PQ 和 OPQ 的区别是什么？量化误差来自哪里？
- KV Cache 的内存复杂度是多少？为什么需要压缩？
- 旋转矩阵如何帮助消除量化异常值？
如果这些问题都能回答，你就具备了理解 TurboQuant 的数学基础！