二进制量化与 RaBitQ

一句话定义

二进制量化把每维压到 1 bit（32 倍压缩），距离退化为汉明距离——可用 XOR + popcount 在单条 CPU 指令级批量计算；新一代方法（RaBitQ 类）用带缩放因子的有符号编码给出理论误差界，让"1 bit 存储 + int8/float 精排"成为高维嵌入的主流压缩组合。

为什么重要

1536/3072 维的现代嵌入把内存账（kp-026）推到临界点，而 1 bit 是压缩的物理终点。传统二值化（直接 sign 或 LSH）召回损失大到不可用，长期只停留在学术兴趣；RaBitQ（2024）第一次给 1-bit 量化装上了理论误差界，配合"二进制粗排 + 残差精排"的两段式管线，工业界（pgvector 的 bit 类型、Qdrant 二进制量化、Cohere int8/binary 嵌入输出）迅速落地——这是 2024 年以来量化方向最重要的进展。

前置知识

kp-012（PQ——量化-查表-精排的完整范式）、kp-003（度量）、kp-026（内存账——收益兑现处）。

核心概念

• 二值化（naive binary）：每维取符号得 ±1；随机方向上cosθ 与位一致率有单调对应，但量化误差随维度累积、排序噪声大。
• 汉明距离：两二进制串不同位的个数；popcount(A XOR B) 一条指令处理 64 bit，768 维仅需 12 次操作——这是二进制路线速度的来源。
• RaBitQ：不直接存符号位，而是存"随机旋转后的有符号归一化码 + 每向量缩放因子"，使量化后的内积成为真内积的无偏估计且误差有可证明的界（随维度按 1/√d 收敛）。
• 两段式管线：二进制全量粗排（超快超省）→ top 候选用 int8 残差或 float 原始向量精排——把理论界兑现为可用召回。
• 残差（residual）：原始向量与二进制重构向量的差，用 int8 存储后精排成本远低于全量 float。

原理与机制

为什么"naive 二值化不行、RaBitQ 行"：直接取符号等价于把向量投影到超立方体顶点，方向量化噪声在 d 维累加后，内积估计的误差足以打乱中后段排序——实测召回显著低于 int8。RaBitQ 的三步改造：先施加随机正交旋转（打散维度相关性，误差正态化），再以有符号格点编码（不是朴素 sign）逼近方向，最后为每个向量估计并存储缩放因子校正模长损失。结果：内积估计无偏、方差有界，排序稳定性接近 int8 但存储只有 1 bit/维。

工程组合拳（现代高维嵌入的典型配置）：

存储: binary(1bit×d + 缩放因子) ≈ 32×压缩          ← 全量粗排
      + int8 残差(可选)                            ← 精排, ~4×压缩
计算: popcount 汉明粗排 → 取 top-N' → 残差/浮点精排 top-k
例: 1亿×1536d: fp32 587GB → binary 18GB(+残差~37GB) 仍省一个量级

与 PQ 的关系：PQ 是"分段矢量量化"（信息论上更优），RaBitQ 是"全局标量量化+理论校正"（实现更简单、SIMD 更极致）；两者可以叠加（二进制粗排 + PQ 精排）。选型直觉：超高维（≥1024）优先二进制组合，中低维 int8/PQ 已足够。

公式或模型

汉明距离: H(a,b) = popcount(a XOR b)
一致率-角度关系(naive): cosθ ≈ 1 - 2H/d  (仅粗排序用)
RaBitQ 误差(定性): |⟨q,x⟩ - ⟨q,x̂⟩| ≤ C‖q‖·ε_d,  ε_d ∝ 1/√d  ← 维度越高越准

图示

naive:    x → sign(x)                        噪声累积, 排序崩
RaBitQ:   x → 随机旋转 R → 有符号格点编码 + 缩放因子 c
          ⟨q,x⟩ ≈ c · (码本点积)   无偏 + 误差界随 d 收敛
管线:     binary 全量 popcount 粗排 ──top-N'──► int8/float 精排 ──► top-k

实例或案例

1 亿条 1536 维（OpenAI 系嵌入）知识库：fp32 需约 590 GB 内存（kp-026 账本）。方案：binary 全量（约 19 GB）+ int8 残差精排（约 37 GB），总内存 60 GB 以内，popcount 粗排把每查询计算量降一个量级，自建评测 recall@10 损失控制在 1~2 个点内——原本需要内存型高配集群的库，缩到两台普通节点。这代表了当前高维场景"量化组合拳"的标准收益形态。

直观类比

naive 二值化像"把照片打印成纯黑白两色"——轮廓还在、细节全毁；RaBitQ 像"黑白打印但每张照片附一张曝光补偿卡（缩放因子）"，加上用彩色笔（int8 残差）只修补重点区域——大部分信息用最便宜的纸，关键细节才用彩印。

常见误区

1. "二进制量化 = 取符号位"——naive 取符号的召回损失不可接受；可用方案必须带旋转/缩放校正与精排（RaBitQ 类），否则只是压内存不保检索。
2. "压缩 32 倍就省 32 倍钱"——残差、精排计算与索引结构同样占资源；账要按"binary+残差+图"合计口径算（kp-026 纪律）。
3. "低维向量也该上二进制"——误差界随维度收敛，低维（<256）二进制相对 int8 的优势不明显，先 int8（kp-011）。
4. "理论界=工程保证"——界是排序稳定性的上界，具体召回仍取决于数据分布；上线前必须过 kp-025 评测。

自测题

1. 为什么 popcount 让二进制路线在计算端也占优？

答：汉明距离等于 XOR 后数 1 的个数，现代 CPU 一条指令处理 64 位，1536 维仅约 24 次位运算，远快于浮点点积的数千次乘加。

2. RaBitQ 相对 naive sign 的三处关键改造？

答：随机正交旋转（打散相关性）、有符号格点编码（优于单纯符号）、每向量缩放因子（校正模长）——共同造就无偏估计与误差界。

3. 二进制粗排 + int8 残差的内存账怎么列？

答：全量 binary ≈ d/8 字节/向量 + 每向量缩放因子；残差 ≈ d×1 字节（int8）；合计约为 fp32 的 1/6~1/10，粗排阶段则只用 binary 部分。

与其他知识点的关系

kp-012 的 PQ 是矢量量化对照系；kp-011 的 int8 是本方案精排段的载体；kp-026 是收益兑现的账本；kp-033 将其放入量化趋势的大图。

延伸阅读

Gao & Long, "RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search"（2024）——1-bit 量化误差界的原始论文；其续作 Extended RaBitQ 扩展到多比特档位。