推理模型在求解复杂问题时通常需要展开一棵推理树，节点代表子目标，边代表推理步骤。树的很多分支并不新鲜，同一子问题可能在左侧分支已经被证明或否定，右侧分支又重复计算一次甚至多次。重复计算带来的开销累积起来非常可观。以带等式的逻辑推理为例，如果规则集包含交换律、结合律，同一条表达式可能以不同文本形式出现，未做归一化的系统会把它当成新目标重新推导。
缓存的核心是把子问题与结果绑定。当推理器遇到一个子目标时，先计算该子目标的特征键，去缓存中查找；命中则直接返回保存的证明路径、赋值或失败标记；未命中才继续搜索，并在得出结果后写回缓存。这种机制类似于动态规划中的记忆化搜索，但推理缓存的难点在于子问题可能不是完全相同，而是等价。例如，要证明 A 且 B 和证明 B 且 A 在经典逻辑中是同一件事，如果缓存键只记录文本，就会漏掉复用机会。
引入缓存后，复杂度收益非常明显。假设推理树每个节点平均分叉为 b，深度为 d，最坏情况下要展开 b 的 d 次方个节点。若存在大量重复子问题，缓存命中可以把重复子树合并，计算规模可能降到不同子问题的数量。在等式推理、类型推导和规划任务的许多基准测试中，简单记忆化即可将求解时间从秒级降到毫秒级，前提是键规范化足够精确，不会把不同结果误判为相同。
一、推理缓存的核心思路：从重复计算到结果复用
这一机制已经触及核心：推理系统需要识别哪些子问题值得复用，并以可控成本维护结果。缓存的粒度可以很粗，例如整个目标是否被证明过；也可以很细，例如只缓存某个变量的部分赋值是否仍然满足约束。粒度越细，命中率往往越高，但键的计算和存储开销也越大。实际系统通常先从粗粒度开始，再根据命中统计逐步细化。
缓存与推理器的交互位置也很关键。最理想的位置是在搜索循环的入口处拦截每个子目标，这样无论子目标来自哪个分支，都能先经过缓存。如果只在顶层查询缓存，而分支内部的递归调用不经过缓存，收益会大打折扣。因此，缓存模块应当作为推理器内部的一个横切组件，而不是外部包装器。
二、缓存键的规范化：让等价子问题走到同一个入口
缓存键设计直接决定命中率。直接拿原始字符串当键最省事，但对语法变体、变量重命名、操作数顺序都非常敏感。变量重命名是典型问题：目标 P(x) 与 P(y) 在约束中可能是同一个目标，但 x 和 y 只是局部占位符。标准化方案可以先对自由变量做 alpha 转换，再对可交换操作符排序操作数。经过标准化后，等价表达式被映射到同一规范形式。
哈希键通常采用规范形式字符串的哈希值，或者结构化键的多级组合。需要处理哈希碰撞：哈希值相同但规范形式不同时，必须比较完整键。也就是说，缓存不能只存哈希值映射结果，还要保存规范形式用于碰撞校验。为保证性能，可以把较短哈希和规范形式一起存储，查找时先按哈希桶定位，再比较规范形式。
一个最简单的实现如下：
def norm_key(goal, ctx):
# goal: 子目标表达式对象
# ctx: 上下文中的变量绑定
goal = alpha_normalize(goal, ctx)
if is_commutative(goal.op):
goal = sort_operands(goal)
# 生成稳定文本形式的规范键
return canonical_text(goal)
cache = {}
def solve(goal, ctx):
key = hash(norm_key(goal, ctx))
slot = cache.get(key)
if slot and slot["norm"] == norm_key(goal, ctx):
return slot["result"]
result = infer(goal, ctx)
cache[key] = {"norm": norm_key(goal, ctx), "result": result}
return result
这段代码反复调用 norm_key 看起来有些冗余，但目的是把哈希查找和精确碰撞校验分开。命中时需要比较规范形式，否则不同的子问题可能因为哈希碰撞返回错误结果。生产环境还会把规范形式提前计算一次，避免重复归一化。
三、作用域隔离与失效控制：避免脏缓存
缓存结果能不能跨上下文复用，取决于子问题的依赖范围。全局知识库中的引理通常可以长期缓存，因为引理一旦证明，真值不随当前目标变化。但带有局部假设的结果不能写进全局缓存，比如在反证法分支里假设非 P 后得到的结论，离开该分支就失效。作用域常见的做法是给缓存条目附加上下文标识：全局作用域、会话作用域、步骤作用域。查找时先匹配作用域，再匹配键。
失效策略同样关键。推理规则库升级后，旧规则推导出的结果可能不再成立，此时需要清空或标记旧缓存。一种简单做法是维护全局知识版本号，每次规则库更新版本号加一，缓存条目记录创建时的版本号，读取时发现版本不一致就视为未命中。更细粒度的方案是依赖追踪：记录每个缓存结果依赖了哪些规则和事实，当依赖项变化时只失效相关条目。
还需要处理随机性和概率推理。对于带温度采样的大模型推理，同一个问题多次采样结果可能不同，缓存如果无条件复用会降低多样性。此时缓存键需要加入采样参数、随机种子或解码策略；或者只缓存中间隐状态而不是最终文本，让输出层继续基于缓存状态采样。这个区分在符号推理和大模型推理中都很重要。
四、工程实现：LRU淘汰、并发安全和命中统计
内存不可能无限增长，尤其是长时间运行的推理服务。缓存需要设置上限，并用 LRU 或 LFU 策略淘汰不常用条目。Python 中可以用 OrderedDict 实现简单 LRU，Go 中常用带锁的 map 加上双向链表。除了容量淘汰，还可以按条目大小设置内存配额，例如每个缓存条目记录结果序列化后的字节数，总内存超过阈值时先淘汰体积大且最近未命中的条目。
并发环境下的缓存必须保证查找与写入的原子性，否则可能出现多个线程同时计算同一子问题，反而增加负载。优化方案是单飞（singleflight）：当某个键未命中时，只允许一个执行单元真正计算，其他线程等待该结果。示例代码如下：
import threading
class MemoCache:
def __init__(self, maxsize=10000):
self.data = {}
self.lock = threading.Lock()
self.cond = threading.Condition(self.lock)
self.inflight = {}
def get_or_solve(self, key, solver):
with self.lock:
if key in self.data:
return self.data[key]
if key in self.inflight:
while key in self.inflight:
self.cond.wait()
return self.data[key]
self.inflight[key] = True
try:
result = solver(key)
with self.lock:
self.data[key] = result
return result
finally:
with self.lock:
del self.inflight[key]
self.cond.notify_all()
这段代码里，inflight 字典登记正在计算中的键；后续请求进入等待，计算完成后广播唤醒。还可以在写入时检查 maxsize 并执行淘汰。命中率统计同样重要：total_requests 和 hit_count 定期输出，用于判断键规范化是否有效。命中率低不一定说明缓存没用，可能是键太窄或失效太频繁，需要调整规范化策略。
五、缓存收益、风险与适用边界
缓存收益在长链条推理中尤其明显。例如一个规划系统需要反复判断从状态 S 能否到达目标 G，状态 S 可能通过不同路径到达，缓存后第二次遇到同一状态直接返回可达性结果。数学定理证明中，引理库本质上是持久化缓存：证明一次，后续直接引用。大模型推理中缓存提示前缀的 KV 状态也是类似思路，相同的系统提示词和对话前缀不重复计算。
风险主要来自错误复用和内存膨胀。缓存键规范化如果过度合并，例如把本不等价的子问题映射到同一键，会返回错误结论，导致整个推理链条静默失败。为此，测试阶段可以加入一致性校验：对缓存命中的结果做轻量级验证，确认前提条件和变量约束仍然满足。也可以使用可验证缓存，将证明对象或赋值回放，失败时丢弃缓存。
适用边界需要判断。若子问题重复率低、单次计算很便宜、或者结果变化频繁，缓存带来的收益可能抵不上键计算和存储开销。更合适的场景是子问题计算成本高、重复率高、结果具有引用透明性。设计推理缓存时，建议先通过日志统计重复键数量和计算耗时占比，再决定缓存粒度和淘汰策略。