SPR Echo Test
echo test：问一个结构，“你能把输入原封不动还给我吗？”
1. echo test 是什么
训练一个翻译模型之前，先问它一个更简单的问题：你能不能表示"输入等于输出"？
如果连这个都做不到——连"我是我"都学不会——那"我是你"（翻译）就更无从谈起。
echo 就是自映射：f(x) = x。它是任何结构的起点测试。
2. hash map echo（最简形式）
hash_map = {}
for token in tokens:
hash_map[token] = token # encoder: token → 存自己
e_hat = hash_map[token] # decoder: token → 取自己
assert e == e_hat # echo 成立
零参数、零训练。token 自己就是 key，也是 value。 不是 arr[i]=i（靠位置），是 hash_map[key]=key（靠自身）。这就是自映射的最纯粹形式——连位置这个变量都省了。
hash map 的本质是纯粹的知识保存——不计算、不变换、不压缩。echo test 恰恰只需要这么多：找到一个结构 + 一个 encoder，能把自身信息不丢失地存下来。hash map 做到了，所以它通过了 echo test。
echo 的底层机制是自碰撞。 hash(token) 把 token 映射到一个桶，查的时候同一个 token 再次算 hash，落在同一个桶，桶里存的恰好是它自己。自己撞见自己——这就是 echo。hash 冲突不是 bug，是 echo 的保证：只要 hash 函数是确定性的，自碰撞就天然成立。下一步的挑战不是"保存"，是"变换"——翻译任务不是把自己还给自己，是把自己变成另一种语言。
2.1 hash_map echo 的三个威胁
碰撞覆盖。 自碰撞是自己撞自己——但别人也能撞你。
hash_map[A] = A
hash_map[B] = B ← hash(B) == hash(A)，A 被覆盖！
查 hash_map[A] → B ← echo 失败
不可压缩。 每个 token 独占一个桶。语义相近的 token 不能共享同一个桶——即使"猫"和"猫咪"在语义空间里紧挨着。hash_map 的桶是身份制的，不是语义制的。V 个 token = V 个桶，零压缩。
不可泛化。 一个新 token 来了——hash 函数没把它映射到任何已存在的桶。hash_map 只能 echo 训练时见过的 token。没见过 = 无桶 = echo 失败。
2.2 增大 hash key 空间能解决吗？
碰撞威胁可以——d=512 的 key 空间巨大，碰撞概率指数级下降。但压缩和泛化威胁不能。原因不在 key 空间大小，在 hash 算法本身：hash_map 的算法是身份映射——每个 token 的 key 是它自己，天生一 key 一桶，和 key 大小无关。key 再大，算法没变，身份制还是身份制。
压缩是 hash 算法的问题，不是 key 空间的问题。 hash_map 算法 = identity(token)，天然不可压缩。SPR 堆算法 = semantic_route(token)，天生可压缩——两个语义相似的 token 走同一条路径，共享同一个桶。改变算法，不是改变 key 的维度。
这三条威胁正好是 SPR 堆要解决的：
| 问题 | hash_map | 增大 key 空间 | SPR 堆 |
|---|---|---|---|
| 碰撞 | 覆盖，echo 死 | 缓解（概率降低） | 算法决定——路由到叶子，共享不覆盖 |
| 压缩 | 算法限制——身份制 | 无效——算法没变 | 算法使能——语义路由，L 叶存 V token |
| 泛化 | 算法限制——查表 | 无效——算法没变 | 算法使能——相似 token 走同路径 |
hash_map 是一个完整的身份存储系统——echo test 只需要这个。但任何需要压缩或泛化的任务，身份存储不够——需要语义路由。
3. 邻接矩阵 echo
Transformer 的 Self-Attention 是一个 T×T 的邻接矩阵——每个位置对其他所有位置的关注权重。
邻接矩阵[i, j] = softmax(Q_i · K_j) / √d 的权重
echo 的目标：让这张矩阵退化为单位阵——每个位置只看自己。
初始（随机）：每行近似均匀分布，每个词分散关注所有词
训练后： 对角线 → 1，其余 → 0，每个词只关注自己
训练过程：MSE(input, output) 的梯度反向传播，推着 W_q 让 Q_i 只靠近 K_i，W_k 配合 W_q 移动，邻接矩阵从均匀收敛到对角。
4. 堆 echo
堆没有邻接矩阵的概念。堆的 echo 表达为：整句从根开始，递归分裂，每层算哈希。
整句 → Hash(整句) = 根节点
│
├─ 前半组 → Hash(前半组) = 左子
│ ├─ Hash(前1/4组)
│ └─ Hash(后1/4组)
└─ 后半组 → Hash(后半组) = 右子
├─ Hash(前1/4组)
└─ Hash(后1/4组)
每一层的哈希值编码的是当前 token 组的语义。 根节点存整句语义，左子存前半句语义，越往下语义越细。这不是每个 token 独立走路由——是整句从根劈下去，递归算哈希。
这样做的好处：两个语义相似的句子——比如"猫在睡觉"和"cat is sleeping"——根哈希相近（整体语义一致），往下才分叉（语言差异）。哈希碰撞发生在各层节点的哈希值里——同一个 token 组的语义压缩进了同一个节点向量。
这就是一棵语义 Merkle 树。 每个节点 = 子树内所有 token 的语义聚合。信息不在叶子里——在每层节点的哈希向量中。路径是什么？路径是 token 从整句到自身上下分裂的轨迹。
实现方式：手工设定每个节点在当前深度维度的阈值 H[i]，让路由具有确定性。
做了两层：
| 深度 | 用哪个维度 | 阈值怎么设 |
|---|---|---|
| 0 (根) | dim 0 | 手算中位数，dim0 < median → 左，≥ median → 右 |
| 1 | dim 1 | 同。对左子树的 token 算 dim1 中位数 |
| 2 | dim 2 | 同上，逐层递进 |
本质是多维排序分桶——每个深度轮换一个维度当比较键，阈值是该维度在当前子树内的中位数。到最后叶子，一颗子树叶存一个 token 的 embedding。
验证断言：
| # | 断言 | 验证方式 |
|---|---|---|
| 1 | 同 token 走两次到同叶子 | 跑两次对比路径 |
| 2 | 叶子存的值 = token embedding | assert torch.allclose |
| 3 | 叶子数 ≤ token 数（桶的分辨率够） | 统计叶子命中分布 |
5. 何时需要训练
echo test 不需要训练——手工设阈值就够了。树的路由策略是确定性排序，不是概率分布。什么时候才需要训练？
| 情况 | echo | 训练 |
|---|---|---|
| token 能靠已知维度排序分开 | 手工，通 | 不需要 |
| token 的语义空间复杂，排序分不开 | 可能需要 | 训练 H[i] 自适应路由 |
| 要替换 NMT decoder 做翻译 | 不够 | 必须训练 |
STC 方案（直通估计器——前向 sign，反向恒等）是这个训练的候选剂，但不是 echo test 的内容。
6. 三种结构统一
| hash map echo | 邻接矩阵 echo | 堆 echo | |
|---|---|---|---|
| 路由方式 | key → value | Q·K^T → softmax | 投影 ≤ H[i]? → 左/右 |
| 参数 | 0 | W_q, W_k, W_v, W_o | H[i]（标量阈值） |
| 控制什么 | 键值对 | 边权（T×T 矩阵） | 分叉条件（D-1 个阈值） |
| 训练 | 0 步 | 梯度下降 | echo 手设，变换才训练 |
| echo 态 | hash_map[k]=k | Attn ≈ I | 路由确定，叶子 = 自己 |
7. 实验验证
代码：spr_echo_test.py，约 80 行，纯 numpy，不训练。
配置
- V=100 个随机 token，d=8 维
- 深度 D=4，15 个内部节点，16 片叶子
- 每个深度轮换一个维度当比较键
- 阈值 H[i] = 当前子树 token 在该维度的中位数
结果
Deterministic : 100/100
Prefix collisions: 4632
=== Node hashes ===
root : [-0.07, 0.162, 0.125] ← 整句语义哈希
left : [-0.133, 0.088, -0.034] ← 前半组语义哈希
right : [-0.012, 0.231, 0.271] ← 后半组语义哈希
=== Collision groups ===
(0,1,1,1): 28 tokens ← 树最深的路径偏斜
(0,0,0,0): 17 tokens
...
10 unique paths / 16 possible
解读
- 确定性 100% — 递归分裂是确定性的，同一组 token 每次劈分结果一致，echo 成立
- 根/左子/右子哈希不同 — 根存的是整句语义，左子存的是前半组的语义，右子存后半组——分层编码成立
- 4632 次前缀碰撞 — token 在上级节点共享哈希（同组聚合），往下才分叉
- 路径不是每个 token 的独立路线 — 是整组分裂的产物。token 的"哈希"就是它在树中的位置
结论
语义递归分裂树的 echo 成立。根哈希编码整句语义，逐层分裂往下细化。哈希碰撞天然发生——同一组的 token 在上级节点共享哈希向量。下一步：把分裂规则从"投影劈半"换成语义相似的 token 自然聚在同一组——让"猫"和"cat"走到同一子树。
8. 参数化：全局共享 H
RNN 有一个关键变量 W_hh——从 h1 到 h5 都用同一个参数，每步更新状态。树的哈希也应该是这样：
Hash(root, 3 tokens) ← H(H(H(t1,t2,t3)))
/ \
Hash(left, 2 tokens) Hash(right, 1 token)
/ \
Hash(t1) Hash(t2)
每层用的都是同一个 H。参数数 = H 的大小。树深了参数不涨。
不是每节点独立参数。是整个树共享一个全局哈希参数 H，就像 RNN 的 W_hh 穿遍所有时间步一样，H 穿遍树的所有深度。
9. 训练路径：短句起步
树的深度由句子长度决定——log₂(n) 次分裂。短句意味着浅树。这是天然的课程学习路径。
3 token, depth=2 → 基案验证
4 token, depth=3 → 扩一层的归纳
...
n token → 通用
这是一个数学归纳问题：基案 N=3 走通，假定 N 走通，验证 N+1。
10. 形态统一：与 TF 的对应
TF 的美妙在于形态统一——矩阵进矩阵出：
输入 (B, T, d_model) → [Self-Attention + FFN] × N → 输出 (B, T, d_model)
树要同样美，需要树进树出——输入是一组 token 构成的子树，输出是以这个组为根的子树。全局参数 H 每层复用，和 TF 的 W_q/W_k/W_v 每层复用完全对应。
TF 用邻接矩阵（Q·K^T）连接所有 token；树用递归分裂连接组内 token。一个是对应到全连接图，一个是对应到递归树——两种数据结构、同一种"形态统一"的审美。
11. 待解：哈希运算是什么？
TF 的哈希运算定义清楚：softmax(Q·K^T/√d) × V。树的哈希运算还是一片空白——我们知道全局参数 H 在每层复用，但 H 具体对一组 token 做什么运算，是未定义的。
三种候选方向：
| 方案 | 运算 | 对应 | 复杂度 |
|---|---|---|---|
| A. 投影聚合 | hash(G) = mean(H @ token_i) |
W_q/W_k/W_v 投影步 | O(d²) |
| B. RNN 串行 | hash(G) = RNN_step(H, token_i) |
RNN W_hh 展开 | O(n·d²) |
| C. 组内 Attention | hash(G) = softmax(HQ·HK^T) @ HV |
完整 Self-Attention | O(n²·d²) |
B 是自然候选——“RNN 树"的本意。C 太重——每个组内都做一次全连接 Attention 就失去了树的稀疏优势。A 太轻——没有组内交互，只是压缩。这最后一公里留到 SPR-007 解决。
License: GPLv3 本文《SPR》系列采用 GPLv3 协议开源发布。