Aug 7, 2026

答案是如何被找到的：猜想、验证与更正

~/ 随笔#算法#LLM#思考

1. Aside: 开始之前

案例：一道算法题

Minimum XOR Split

Given an integer $n$ , find an integer $x$ such that:

\begin{gathered} 1 \le x \le n\\ The\ value\ of\ (n - x)\ \oplus\ x\ is\ minimized \end{gathered}

Output the minimum possible value of:

(n - x) \oplus x

伟大探索

第一反应：打表

异或不是加减乘除，没有从小就熟悉，因此第一反应就是打表。

朋友在做的时候产生了相同的想法，总结出了两个规律：

偶数的结果一定是： $0$
奇数的结果：似乎有点规律，但是最后很可惜有些误差，没能通过所有样例。

n:   1  3  5  7  9 11 13 15 17 19 21 23 25 27 29 31...
ans: 1  3  1  7  1 3  1  15 1  3  1  7  1  3  1  31...

直觉与证明

有趣的直觉

直接令 $x = n >> 1$

然后试了几个数字，发现刚好符合，然后写了个程序进行验证，多试了一些比较大的数字，依旧符合。

OK，现在找到了似乎正确的解法了。

不太严格的证明

对于每一位都是 $1$ $1$ 的正整数
- 无论拆成两个什么数，异或的结果一定是原本的值
对于偶数（以 $0$ $0$ 结尾）
- 一定能拆成两个一样的数，异或结果为 $0$

找到最低位的 $0$ ，在此之前的一长串二进制数能被分成两个相同的数加起来，其后的二进制位全为 $1$ ，因此无论怎么拆，异或的结果均为 $1$

总结

一个很有意思的现象

面对一道做过的题，我们可以从记忆里取出一个现成解法
但面对一道从未见过的题，答案通常不是一下子完整地出现在脑海中

更常做的事情

从题目条件和几个样例里寻找线索，先形成一个可能正确的猜想
再用更多样例、反例、复杂度分析和证明去检查它。
- 如果猜想失败，就根据失败的位置修改它，然后进入下一轮。

node_01猜想
从约束、样例与经验中生成候选解。
node_02验证
用证明、反例与实验检查候选解。
node_03反馈
定位候选解与事实之间的偏差。
node_04更正
保留有效部分，提交下一轮猜想。

这让我开始怀疑

在很多未知问题中，真正重要的或许不是直接得到答案，而是建立一个高效的 “提出候选答案—验证候选答案” 的循环。

算法题中的 “直觉” 并不是毫无根据地猜
数据范围会暗示可以接受的时间复杂度
题目中的单调性、局部性和对称性会让某些算法浮现出来
过去做过的相似问题，也会帮助我们缩小搜索范围

因此，猜想的价值并不是保证我们第一次就正确，而是把巨大的搜索空间压缩到少数几个值得验证的方向。

2. 投机解码：让便宜的模型先提出候选

Speculative Decoding

LLM & assistant model

LLM 中类似的过程变成了一种推理系统 Speculative Decoding
自回归大模型通常需要逐个生成 token，每一步都要运行一次模型。
投机解码引入了一个更快的 draft model，也常被称为 assistant model
- 它先连续生成多个候选 token
- 再由较大的 target model 并行计算这些位置
- 按照接受规则保留或拒绝候选
这个类比有一条重要边界：
- target model 验证的是候选 token 是否符合目标模型的分布
- 并不是在判断它是否符合客观真理
- 这里的“验证”是一种计算过程，而不是事实核查。

Speculative Decoding

这样做的关键在于，提出候选和验证候选的成本并不相同。小模型虽然没有大模型可靠，却可以便宜地探索几个可能的后续；大模型也不需要重新逐个提出这些 token，而可以一次检查多个位置。标准的投机采样通过更正的拒绝采样保持 target model 的输出分布，因此获得的不是“降低质量换速度”，而是在目标分布不变的前提下减少解码延迟。

提出一个尝试 $\to$ 小模型（eazy）
验证猜想得到答案或更正 $\to$ 大模型（hard）

当直觉足够准，问题的解决就十分迅速。

3. NP：验证答案和寻找答案之间的距离

3.1 NP 入门：先读懂几个词

从“输入规模”开始

多项式时间

算法的运行时间通常会随着输入变大而增长
计算机科学常用 $n$ $n$ 表示输入规模
- 排序问题中， $n$ 可以是待排序数字的个数
- 图问题中， $n$ 可以是顶点和边的数量
如果运行时间可以写成 $n^k$ 的量级，其中 $k$ 是常数，就称为多项式时间

多项式时间就能很快…吗?

多项式时间不保证程序在现实中一定很快
- 但它给出了一个重要边界：输入扩大后，计算量仍以相对可控的方式增长

什么是判定问题？

答案只有“是”或“否”

旅行商问题（Traveling Salesman Problem, TSP）的判定
- 是否存在一条经过所有城市、并且总长度不超过 $B$ 的路线？
“最短路线是多少”是一个优化问题
- 增加一个长度上限 $B$ 后，它就变成了可以回答“是/否”的判定问题
- P、NP、NP-complete 等概念首先都是对这类判定问题进行分类。

P 和 NP

这几个字母是啥？

P：存在一个算法，可以在多项式时间内直接求出“是”或“否”
NP：当答案为“是”时，如果有人给出一份候选证明，我们可以在多项式时间内检查它
这份可以被快速检查的候选证明通常叫作证书（certificate）
需要特别注意：
- NP 不是 Non-Polynomial（非多项式时间）的缩写
- 是 Nondeterministic Polynomial Time
所有 P 问题也都是 NP 问题,目前仍不知道是否有 $P=NP$

NP-complete 和 NP-hard

NP-complete：问题属于 NP，并且至少和 NP 中所有问题一样难
NP-hard：至少和 NP 中所有问题一样难，但它本身不一定属于 NP，也不一定是判定问题
如果任何一个 NP-complete 问题存在多项式时间算法，那么所有 NP 问题都能在多项式时间内求解

P、NP、NP-hard 与 NP-complete 的文氏关系图 — 常见教材示意（假设 P ≠ NP）：P 包含于 NP，NP-complete 是 NP 与 NP-hard 的交集。

3.2 证书：寻找与验证的距离

Certificate & Verification

“找到”与“验证”

计算复杂性理论中的 NP 讨论的是一类判定问题
对于答案为“是”的实例，如果有人提供一个长度合适的证书
- 我们可以在多项式时间内检查这个证书
- 但从零开始找到它，可能仍需要在巨大的组合空间中搜索

旅行商问题的判定版本

是否存在一条经过所有城市、并且总长度不超过 $B$ 的路线？

如果别人给出一条具体路线
- 可以检查它是否经过所有城市
- 可以计算总长度是否不超过 $B$
验证一个候选路线是直接的，寻找它却可能很昂贵

4. 概率算法：当完整验证仍然昂贵

随机算法

随机数也可以是算法的一部分

确定性算法在输入相同的情况下
每次都沿着相同的路径执行
随机算法则会在运行过程中主动使用随机选择
因此同一个输入的执行过程可能不同。

引入随机性并不等于“随便猜一个答案”。算法仍然需要给出可以分析的正确性和复杂度保证，只是这些保证可能带有概率。

两种常见类型

Las Vegas 算法
- 输出一定正确
- 运行时间可能因为随机选择而变化
Monte Carlo 算法
- 运行时间有明确上界
- 允许一个可以计算并控制的错误概率

Freivalds 算法属于 Monte Carlo 算法。它不会把正确的矩阵乘法误判为错误，但有很小的概率把错误结果暂时当成正确，这叫作单侧错误（one-sided error）。

Freivalds' Algorithm

用概率换取更低的验证成本

验证也不总是便宜的
有时我们愿意接受一个很小的错误概率，换取更低的验证成本
Freivalds 算法就是一个很漂亮的例子

为了验证三个矩阵是否满足 $AB=C$ ，可以随机选择一个向量 $r$ ，检查：

A(Br)=Cr

如果等式不成立
- 原来的矩阵乘法一定有问题
如果等式成立
- 原来的矩阵乘法以较高概率是正确的
多次选择独立的随机向量重复检查
- 可以继续降低漏掉错误的概率

概率正确不是随便猜

当 $AB \ne C$ 时，Freivalds 算法进行一轮随机检查却没有发现错误的概率最多为 $\frac{1}{2}$ 。如果独立重复检查 $k$ 轮，仍然漏掉错误的概率最多为：

\Pr\left(\text{false accept}\right) \le \left(\frac{1}{2}\right)^k

例如重复 $20$ 轮，漏掉错误的概率最多约为百万分之一。随机算法的可信度来自这种可以证明的概率上界，而不是来自“感觉应该没问题”。

Freivalds' Algorithm

概率算法并不是 NP 定义的一部分，但它为同一条主线增加了一个新问题：当验证本身也有成本时，我们应该怎样在速度、确定性和可信度之间取舍？

5. 从验证回到实践

实践与反馈

自洽还不够

一个想法内部再自洽，如果无法解释现实、无法经受实验和工程环境的反馈，它仍然需要被更正
算法中的反例、系统中的 benchmark、科学中的实验
- 都在迫使猜想与实际结果相遇
实践的意义不仅是确认我们对了
- 也包括暴露我们错在什么地方

有限验证的边界

代码通过几个测试，不等于算法对所有输入都正确
一次 benchmark 只能说明系统在特定硬件、负载和参数下的表现
数学证明、形式化验证和可重复实验
- 都是为了让不同场景中的“验证”更加可靠

实践是反馈回路的一部分

“实践是检验真理的唯一标准”给这条思考链补上了最后一环：
实践不是简单地为猜想盖章，而是让猜想接触现实，并把偏差重新送回下一轮更正。

6. 人“学”AI…？

6.1 把日常实践变成训练

Train Your Intuition

如果把学习类比成 AI 训练

训练数据：做过的题、写过的程序、读过的代码，以及现实中真正处理过的问题
前向计算：遇到新问题时，根据已有经验快速提出一个候选答案
损失（loss）：候选答案与测试结果、反例或现实反馈之间的偏差
反向传播：复盘错误发生在哪里，以及哪一步判断依赖了错误的假设
参数更新：保留有效模式，修正无效经验，让下一次判断更接近事实

人脑当然不会真的执行梯度下降，但“参数”可以作为一个有用的比喻：我们过去积累的模式、偏好、判断规则和注意力分配，共同影响着下一次会先想到什么。

Dataset Matters

训练量并不等于训练质量

如果只反复处理同一种问题，人也会像模型一样产生过拟合
- 熟悉的题型做得很快，条件稍微变化就失效
如果反馈含糊或错误，就像使用了带噪声的标签
- 错误经验可能被不断强化，最后变成自信但不可靠的“直觉”
更好的实践需要有意识地增加样本多样性
- 主动寻找反例
- 改变数据规模和边界条件
- 比较多种解法
- 在不同环境中重复验证

直觉并不是突然出现的灵感，更像是大量经验被压缩后的快速检索：它能迅速缩小候选范围，却不能代替后续验证。

直觉是候选生成器，不是正确性证明

好的直觉让我们更容易提出一个值得验证的答案，而不是保证答案一定正确。实践的目的也不是把人训练成永远不犯错，而是让错误更早暴露、反馈更容易理解，并让每一次修正真正影响下一次判断。

因此，获得直觉的过程可以写成：经验输入 → 主动预测 → 实践反馈 → 复盘偏差 → 更新经验。循环次数足够多、反馈足够真实、样本足够多样时，我们才会逐渐拥有看似“第一眼就知道方向”的能力。

6.2 从训练回到验证循环

Guess, Verify, Refine

它们并不属于同一个层次

算法证明
投机解码
NP 与概率算法
实践与工程反馈

这些概念并不完全相同，但它们都让我注意到同一个结构：

面对未知问题，我们不必等待一个完整答案凭空出现。可以先提出一个有根据的候选答案，再主动寻找能够验证或推翻它的证据，并根据反馈继续更正。

一个值得保留的能力

不要求第一次猜对
提出一个值得验证的猜想
设计足够可靠、足够便宜的验证方式
根据证据持续更正下一轮候选

仍然没有想清楚的问题

如果验证本身和寻找答案一样昂贵，该怎么办？
如果验证者也可能出错，又应该由谁来验证验证者？
AI 能不能不仅生成候选答案，还能主动寻找反例来更正自己？

阅读材料

Charlie Chen 等，Accelerating Large Language Model Decoding with Speculative Sampling
Harvard CS125，Nondeterministic P
Hao Ji 等，Gaussian Variant of Freivalds’ Algorithm for Efficient and Reliable Matrix Product Verification