挑战精度冗余：近似计算的工程哲学与实践

1994 年 10 月，在弗吉尼亚州林奇堡学院，数学教授托马斯·尼塞利正在计算孪生素数倒数之和。奔腾处理器计算出的结果是 1 / 824633702441，和另一台机器的计算结果对不上。调查到最后才发现，FPU 除法器中的一个查找表缺失了 1066 个条目中的 5 个。受影响的除法运算大约占百亿分之一，最终英特尔公司拨款 4.75 亿美元用于修复该处理器。这笔资金用于硬件维修，也推动了对 “精度” 的合同定义：浮点除法必须按照 IEEE 754 标准执行，否则必须告知用户除法结果不符合精度要求。

工程中还有三类常见的精度取舍：创建包含 40 亿个 URL 的黑名单，只判断名单上的项目是否 “可能存在”；从 6.5 TB 日志中估计唯一用户数量，也就是回答 “有多少个唯一用户”；让一个大模型在 24 GB 显存里容纳 128K 上下文。

这三个问题分别关心成员资格、基数和上下文保留，但处理方法相近：先确定结果需要多精确，再把不必保留的精度换成空间、延迟、能耗或吞吐。

下文假定读者了解概率、哈希、浮点数和 SQL 聚合。文章按六个问题展开：

存什么：用摘要替代事实。
数怎么写：用位表示换取算术速度。
怎么算：用采样和统计推断替代全量执行。
拿什么算：让电路和随机性承担误差。
算什么：把精度分配给模型中真正敏感的部分。
何时停：识别不能近似的边界，并准备精确回退。

0. 精确性为什么有价格#

近似计算的验收条件可以先固定下来：目标、误差、方向、回退，以及数字适用的条件。后文虽然会更换对象，这几项仍然适用。

0.1 satisficing 是受约束的满意解#

Herbert Simon 在 1956 年提出 bounded rationality（有限理性），并用 satisficing 描述一种实际决策：不枚举全部候选项，而是在约束下找到第一个满足要求的方案。继续搜索也要花时间、内存和电力，所谓“最优”只有在这些成本不重要时才值得追求。

近似计算把这种决策形式化。一个可审计的近似结果至少应说明五件事：

目标：要估计的是集合成员、基数、聚合值，还是模型输出。
误差：允许绝对误差、相对误差，还是按任务指标衡量的性能下降。
方向：错误是只能产生假阳性，还是正负误差都可以接受。
回退：超过置信范围时，是否重新采样、全量计算或交给精确路径。
数字规范：正文里的数字是哪个工艺、分布和基线下的量级，换条件后是否需要重测。

例如，黑名单预筛可以接受 “可能命中后再查一次”，但不能把真正的恶意 URL 判成不存在。先写清楚错误方向，算法选择才有意义。

0.2 von Neumann：从不可靠组件构成可靠系统#

1952 年，晶体管发明还不到五年，von Neumann 在 Caltech 讲座上发表了《从不可靠的组件合成可靠的机体》。他的判断是，在组件近似独立且正确率高于随机阈值等条件下，冗余和投票可以把不可靠组件组合成可靠系统。晶体管后来变得足够可靠，这个问题沉寂了几十年；纳米尺度下，电压、漏电和数据搬运再次成为成本，这个问题又回到工程实践中。

先写近似契约

在实现之前先写出：输入分布、输出定义、误差指标、置信度、错误方向、监控指标和精确回退。若其中一项无法回答，算法还没有进入可上线状态。

1. 概率数据结构：把错误推向安全的一侧#

第 1 层从存储内容入手：用摘要回答特定查询，省去保存完整事实的空间。概率数据结构还会把可能出现的错误类型写进接口语义。

1.1 布隆过滤器的参数是误差预算#

布隆过滤器由长度为 $m$ 的位数组和 $k$ 个哈希函数组成。插入 $n$ 个元素后，任意一位仍为 0 的概率为

(1 - 1/m)^{kn}.

因此，不在集合中的元素发生假阳性的概率为

p = \left(1 - (1 - 1/m)^{kn}\right)^k \approx \left(1 - e^{-kn/m}\right)^k.

固定 $m$ 和 $n$ 时，令 $k=(m/n)\ln 2$ 可以得到近似最优点。此时 $p\approx 2^{-k}$ ，反过来有 $k\approx-\log_2p$ ，每个元素需要的位数为

\frac{m}{n}\approx\frac{-\ln p}{(\ln 2)^2}.

如果目标误判率为 $0.01\%=10^{-4}$ ，则 $k\approx13.3$ ，实现时取 13 或 14 个哈希探针，每个元素约需 19.2 bit。100 亿个元素只计算位数组需要约 24 GB；工程实现还要为分片、哈希种子、并发更新和版本切换留出空间，因此不能把这个数直接当作线上内存承诺。若直接保存每条 64 字节的 URL 原文，光数据内容就约 640 GB，哈希表的桶、指针和装载因子还会继续增加开销。

布隆过滤器的接口语义是“否定答案可靠，肯定答案待确认”：返回“没有”时，元素一定没有插入；返回“可能有”时，调用方必须访问原始集合或另一层索引。它不支持删除，除非改用计数布隆过滤器；计数器会增加内存和溢出处理。

LevelDB、RocksDB 和 Cassandra 都会在读取 SSTable 前查询布隆过滤器，以跳过注定失败的磁盘读。过滤器不负责重建索引、处理容量过载，也不负责命中后的精确查找；这些仍由存储系统的其他部分完成。

1.2 HyperLogLog 用随机前缀估计基数#

如果把均匀哈希看成抛硬币，哈希值开头连续几个零就是连续抛出同一面的长度。看到一次很长的连续序列，说明背后大概抛过很多次；HLL 只记每个桶里最长的那次。

哈希值的前 $b=\log_2m$ 位选择寄存器，剩余部分的前导零位置 $\rho(w)$ 更新该寄存器的最大值 $M[j]$ 。

估计器写成

E=\alpha_m m^2\left(\sum_{j=1}^{m}2^{-M[j]}\right)^{-1},

其中 $m\ge128$ 时，常用偏差修正常数为

\alpha_m\approx\frac{0.7213}{1+1.079/m}.

其标准误差约为 $1.04/\sqrt m$ 。取 $m=2048$ 时，寄存器本身约为 1.5 KB，理论标准误差约 2.3%。生产库还会针对小基数和大基数使用线性计数、范围修正或稀疏编码；不能只套用上面的渐近公式。

HLL 使用调和平均，是因为每个寄存器的 $2^{M[j]}$ 是一个偏斜的局部估计，直接做算术平均会让少数极端寄存器产生较大偏差。调和平均可以降低这种偏差，却不会自动消除异常值：哈希不均匀、寄存器实现错误和输入分布变化仍会破坏估计。应使用固定种子、独立样本和离线精确计数持续校准。

HLL 可以把查询工作从扫描全部历史数据改为合并小型寄存器数组。一篇 BigQuery HLL 案例报告记录了扫描量从 6.5 TB 降到 16.25 GB、耗时从数小时降到 7 秒的结果。迁移到其他数据库或数据分布时，仍需重新测量。

1.3 Count-Min Sketch：只会多报的计数器#

布隆过滤器回答“有没有”，Count-Min Sketch（CMS）回答“出现了多少次”。在更新值为非负数时，它把每次更新同时写入多行哈希桶，查询时取这些桶的最小值；碰撞只会把计数推高，因此结果不会低估真实频率。这个错误方向很适合统计热点、限流和 DDoS heavy hitter，却不适合需要精确扣减的账务计数。

两种结构提供不同的下界保证：布隆过滤器返回“没有”时答案可靠，CMS 的计数不会低估真实频率。选择摘要结构时，应先确定调用方能承受哪一种错误，再比较空间和吞吐。

如果必须支持删除，可以考虑 Cuckoo Filter。它存储指纹，支持动态插入和删除；它与布隆过滤器的实现不同，还要处理踢出、装载率和扩容。

2. 数值算法：重新解释浮点数的位#

第 2 层改变数的表示方式。同一个值采用不同的位表示，会走上不同的算术路径，也会带来不同的硬件成本。

2.1 快速平方根倒数及其历史#

这段代码因《雷神之锤 III 竞技场》源码而流行，但直接归功于 John Carmack 并不准确。公开史料把类似实现追溯到更早的 SGI 图形开发和图形程序员共享的代码；具体历史仍有争议。

快速平方根倒数算法把单精度浮点数的位模式暂时当作整数，先生成一个对数尺度上的初值，再用牛顿迭代修正：

1
float fast_rsqrt(float x) {
2
    uint32_t bits;
3
    memcpy(&bits, &x, sizeof bits);
4
    bits = 0x5f3759dfu - (bits >> 1);
5
    memcpy(&x, &bits, sizeof x);
6

7
    float half = 0.5f * x;
8
    x = x * (1.5f - half * x * x);
9
    return x;
10
}

代码中的 memcpy 避免了通过不兼容指针类型读取浮点位模式时违反 C 严格别名规则。常数 0x5f3759df 利用了浮点指数与对数的近似关系：整数右移相当于除以二，常数用于补回指数偏置并减小初始误差。舍入模式、误差目标和输入范围不同，合适的候选常数也会变化。

一次牛顿迭代通常能把相对误差降到约千分之几，两次迭代还会继续降低误差；具体数值取决于输入区间和测试方式。现代 CPU、GPU 已提供 RSQRTSS、RSQRTPS、VRSQRTE 等近似指令，通常更容易向量化、验证和维护。这个算法现在仍适合用来观察数值表示、误差和硬件指令之间的关系。

低精度 RMSNorm 也是硬件研究的对象。RMSNorm 要计算均方根的倒数，与平方根倒数共享近似目标。若把算法移植到定点或神经形态芯片，还需重新验证溢出、缩放和梯度误差，公式相似并不能说明性能一定会改善。

2.2 对数数制把乘法换成加法#

对数数制（LNS）存储 $X=\log_2|x|$ 和符号位。乘法直接变成定点加法：

\log_2(|x y|)=\log_2|x|+\log_2|y|.

加法则更复杂。假设 $X\ge Y$ ，则

\log_2(2^X+2^Y)=X+\log_2(1+2^{Y-X}).

最后一项需要查找表或近似函数；减法还要处理接近相等时的灾难性消减。LNS 适合乘法密集、动态范围大、可以接受非均匀误差的内核。选择数制时要测完整算子链的误差和面积，单独比较一个乘法器没有意义。

更常见的位表示取舍是 bfloat16：它保留和 FP32 一样的 8 位指数，尾数缩短到 7 位。神经网络通常更容易受动态范围溢出影响，对尾数末几位的精度要求相对低，因此 BF16 成为训练和推理中的实用折中。选数制时，关键是误差是否落在任务敏感的方向上。

3. 数据库：用统计推断替代全量计算#

前两层的错误通常影响单次查询或算术操作。数据库的近似结果还会进入报表、告警和后续决策，因此 AQP 需要同时向调用方提供置信度和停止条件。

数据库里的近似查询处理（AQP）把“精度”写成一个可验证的概率承诺：对精确结果 $\Theta$ 、估计结果 $\widetilde\Theta$ 和误差规格 $(\epsilon,\delta)$ ，希望满足

\Pr\left(\left|\frac{\widetilde\Theta-\Theta}{\Theta}\right|\le\epsilon\right)\ge1-\delta.

当 $\Theta$ 可能为 0 时，应改用绝对误差，或预先声明分母下界。这个细节决定了“95% 置信区间”究竟在保证什么。

3.1 采样计划必须包含先导成本#

块采样先读取少量数据估计方差，再决定最终样本量。PilotDB 将这个过程放进数据库无关的中间层：先执行 pilot query，推导采样方差和连接关系，再生成满足误差规格的候选计划，最后交由数据库成本模型选出计划。正式执行前还要估算所需样本量。

如果先导查询扫描了大量数据，AQP 可能把成本从最终查询转移到了估计阶段。上线时应把总耗时拆成先导、采样、聚合和重试四项，并记录实际覆盖率；只报告采样阶段的速度会夸大收益。

3.2 适合采样的聚合类型有限#

SUM、AVG 和 COUNT 可以利用均值、方差和中心极限定理构造区间。MIN、MAX 依赖尾部极值，样本遗漏一个极端值就可能产生无法接受的偏差；COUNT DISTINCT 则更适合 HLL 一类专门的基数摘要。高度选择性的过滤、稀疏大组和复杂连接也需要专门的抽样理论。

Elasticsearch 在 9.4 的 ES|QL 近似查询中加入了显式的 approximation 选项，返回近似聚合及其误差描述。查询结果应说明是否带有形式化保证，调用方再据此判断它能否用于告警、排序或人工探索。

4. 硬件：把错误预算交给电路#

软件可以重试查询、重新生成缓存，或者回到全量计算。电路流片后，电压和噪声会成为器件本身的一部分，因此错误预算必须在出厂前确定。

4.1 PCMOS 的能量曲线#

概率性 CMOS（PCMOS）降低供电电压或改变噪声工作点，让逻辑门以概率 $p$ 输出正确结果。Palem 的理论结果常把相对确定性开关的潜在节省写成

\Delta E\approx kT\ln(1/p),

这里的 $\Delta E$ 表示理论上的节省项，PCMOS 门的总能耗还要计入电容、噪声幅度、漏电、延迟、负载和工艺。 $p$ 接近 1 时，允许错误带来的节省也趋近于零，追求最后几个百分点的正确率可能需要付出不成比例的能量。

PCMOS 适合音频、视频、传感器和部分科学计算，因为这些应用的最终质量指标本来就是统计量。2004 年的建模和后续芯片实验报告了能效收益，但“降低正确率 1.3% 就提升 300%”这类数字必须绑定器件、工艺、频率和应用，不能脱离实验条件使用。

4.2 随机计算用比特流表示数值#

随机计算用长度为 $N$ 的比特流中 1 的比例表示数值。两个独立概率流通过 AND 门相乘：

P(A\land B)=P(A)P(B).

代价是估计噪声。对伯努利比特流，比例估计的标准差约为

\sqrt{p(1-p)/N},

标准误差按 $1/\sqrt N$ 下降。要把误差缩小一半，需要约四倍长度。相关性会让乘法偏离上述公式，相关性管理和随机数生成器往往比 AND 门本身更关键。

在低精度神经网络中，硬件可以用较少的逻辑门换取更长的时间序列。公开实验在短比特流上取得了可用的分类准确率，但数据集、网络结构、随机流相关性和基线必须与结果一起记录；单独的“92%”无法支持工程决策。

5. 大模型：寻找精度的冗余位置#

大模型需要把精度预算分配给参数、激活和缓存。问题也从单个数的误差扩展到哪些层、哪些 token、哪些缓存位置值得保留更多位。

5.1 QAT 关注损失对权重的敏感度#

设原权重为 $w$ ，量化权重为 $w_q$ 。在 $w_q$ 附近对损失作一阶展开，可以得到

L(w)-L(w_q)\approx \nabla L(w_q)^T(w-w_q).

如果保留二阶项，还要考虑 Hessian 对不同方向的放大作用。单纯最小化 $\|w-w_q\|_2$ 并不等价于最小化任务损失：梯度或曲率大的权重更敏感，应使用更细的量化网格；平坦方向可以使用更低位宽。GPTQ、AWQ 和混合精度分配都采用了类似的判断，但它们使用的校准数据、误差近似和硬件约束并不相同。

量化感知训练（QAT）把量化噪声放进训练前向路径，让优化器适应离散权重。直通估计器处理了舍入不可导的问题，但没有消除分布偏移。训练数据、激活范围和部署内核需要保持一致，离线损失预测才有机会对应线上结果。

5.2 KV-cache 的误差会沿时间展开#

自回归解码每生成一个 token，就把新的 Key 和 Value 写入缓存。缓存量随序列长度线性增长，量化误差也会通过后续注意力反复参与计算。一次只做整句前向的困惑度测试可能读不到真实的缓存误差，因此评估必须在逐 token 解码、目标上下文长度和真实 batch 下进行。

近期的 KVarN 论文把 Hadamard 旋转和 K、V 两个轴的方差归一化组合起来，报告了 2-bit KV-cache 在 MATH500、AIME24 和 HumanEval 等基准上的改进。论文结果与 vLLM 实现的吞吐、显存和模型版本应分开记录。一个 2-bit 方法在某些模型上有效，也不能推出所有模型都能安全使用 2-bit。

5.3 混合精度是一个分配问题#

实践中可以把精度预算分成三类：

权重：静态、可离线校准，通常最容易压缩。
激活：受输入分布影响，异常值和动态范围决定量化难度。
KV-cache：随请求长度增长，既影响容量，也影响每一步解码的带宽。

低于 4 bit 后，量化噪声可能超过微调或校准能够修正的范围。FP8 在许多通用场景中是更保守的折中，但仍受硬件指令和缩放策略影响。小模型的冗余较少，可能比大模型更早出现精度断崖，因此不能只按参数量选择位宽。

一套可执行的精度分配流程是：用真实请求采样每层敏感度，在固定显存和吞吐约束下求解位宽分配，再用任务指标和逐 token 解码回归验证。所有层统一使用同一位宽通常最容易实现，但未必是最优方案。

5.4 投机解码：便宜的先猜，昂贵的确认#

还有一种近似针对“下一步该算什么”，数值精度保持不变。小模型先起草一段 token，大模型并行验证；不接受的 token 被拒绝，接受率由草稿模型和目标模型的分布决定。正确实现的拒绝采样可以保持目标模型的输出分布，速度收益来自减少大模型解码轮数。

投机解码与布隆过滤器都把便宜路径放在昂贵路径之前，由前者提出候选，后者确认结果。这样可以推迟昂贵计算，而不必降低数值精度。

6. 边界：什么不能近似#

前面各层说明了可以把误差放在哪里。这里看必须守住的边界。

1991 年海湾战争期间，Dhahran 的 Patriot 电池连续运行约 100 小时。一个用 24 位定点数表示的 0.1 秒时钟在换算时不断截断，累计误差让雷达门偏移约 0.34 秒，最终没有拦住来袭的 Scud，造成 28 人死亡。美国 GAO 的调查报告把问题归为软件缺陷和运行时间假设没有被纳入设计。

五年后，Ariane 5 Flight 501 在起飞约 37 秒后失控。沿用 Ariane 4 的惯性参考软件把一个超出预期范围的浮点值转换为 16 位整数，触发处理器异常，备用系统又使用了同样的软件。ESA 的调查资料记录了这次失败的时间线。这个系统没有“允许 1% 误差”的余地，输入范围和异常处理都属于验收条件。

系统需要在越界时停下来。金融对账的金额、库存扣减和权限判定通常需要精确状态；风控黑名单预筛、市场趋势、用户聚类和蒙特卡洛风险估计可以使用近似，但要记录抽样概率、随机种子、置信区间和精确复核路径。可观测性也一样：Trace 采样率为 $p$ 时，直接统计样本数会低估真实请求量；对每条样本使用 $1/p$ 权重，才可能得到无偏估计，高方差场景还需要分层采样或保留关键错误样本。

把近似方案放进生产前，可以逐项回答下面的问题：

输入是否满足算法假设，例如哈希独立、采样随机、随机流独立。
误差指标是否和业务指标一致，绝对误差、相对误差和任务准确率不能混用。
误差方向是否可接受，是否存在必须零漏报的分支。
监控是否能发现分布漂移、容量过载和置信区间失效。
是否存在可负担的精确回退，以及回退触发后会不会形成重试风暴。
结果是否向调用方暴露了近似状态、误差界和版本信息。

大模型也有必须精确的任务。即使总体准确率很高，短字符串奇偶校验、计数和格式约束仍可能出现离散错误。BF16、INT8 或 INT4 的选择不能只看平均困惑度；关键任务需要更高精度或独立校验。

程序验证也需要选择误差方向。抽象解释用 over-approximation，多报潜在错误也不能漏掉真实错误；fuzzer 和 sanitizer 报出的通常都是真的，但不承诺已经找完。布隆过滤器属于同一类设计。密码学的要求更严格：SHA-256 少一位就会改变摘要，碰撞风险不能当作可接受的近似误差。

结语：把 “足够好” 写进接口#

各层都能看到同一套接口：便宜的候选机制，加上昂贵的确认机制。布隆过滤器位于原始集合之前，AQP 把停止条件交给调用方，迭代精修用高精度残差检查低精度解，投机解码让小模型起草、大模型验证。候选路径可以出错，确认路径需要守住约定。

回到开头的三个场景：黑名单用约 24 GB 的位数组过滤大多数查询，命中后回到原始集合；SQL 用采样计划控制成本，用 HLL 保存去重状态，并把误差说明带出查询结果；大模型让层敏感度决定位宽，再用逐 token 解码回归验证 KV-cache。它们节省的资源不同，但都要回答三个问题：错误会在哪里出现，谁来承担，越界时怎么停。

精度可以当作预算使用。把位宽花在不敏感的位置，可能换来空间、延迟或能耗；在必须精确的边界上省下来的，往往只是一次事故的准备金。

参考资料#

Simon, H. A. (1956), “Rational choice and the structure of the environment”：Psychological Review, 63(2), 129–138，有限理性与 satisficing 的经典来源。
von Neumann, J. (1956), “Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components”：1952 年 Caltech 讲座，收入 Automata Studies。
Pentium FDIV 缺陷的技术复盘：缺失查找表项、触发概率与召回代价。
Bloom, B. H. (1970), “Space/Time Trade-offs in Hash Coding with Allowable Errors”：Communications of the ACM, 13(7), 422–426，布隆过滤器的原始论文。
Cormode, G. & Muthukrishnan, S. (2005), “An improved data stream summary”：Journal of Algorithms, 55(1), 58–75，Count-Min Sketch 原论文。
Fan, B. et al. (2014), “Cuckoo Filter: Practically Better Than Bloom”：CoNEXT 2014, 75–88，支持删除的近似成员查询结构。
Flajolet, P. et al. (2007), “HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm”：DMTCS Proceedings, 127–146，HLL 估计器、偏差修正与误差分析。
BigQuery HLL 案例报告：一个包含扫描量、Slot 和耗时基线的工程案例。
Kang, D. et al. (2025), “PilotDB: Database-Agnostic Online Approximate Query Processing”：技术报告，带先导查询和先验误差保证的 AQP 方案。
Fast approximate Elasticsearch ES|QL：ES|QL 9.4 的近似聚合设计说明。
Probabilistic System-on-a-Chip Architectures：PCMOS 的概率正确率与能量设计背景。
Muller, L. K. et al. (2026), “KVarN: Variance-Normalized KV-Cache Quantization”：arXiv<2606>.03458，KV-cache 方差归一化与低比特评估。
Leviathan, Y. et al. (2023), “Fast Inference from Transformers via Speculative Decoding”：ICML 2023, PMLR 202，草稿模型与验证模型的分布保持加速。
Patriot 软件故障的 GAO 调查报告：运行时长没有进入误差预算的案例。
ESA 的 Ariane 5 Flight 501 调查资料：输入范围和异常处理假设失效的案例。
近似计算综述：术语、软件与硬件技术：近似计算的术语和技术分类综述。

目录

tsukimi 示例博客