堆路由——SPR 的矩阵化设计

本文是一个概念记录。当前无法实现——需要验证的组件太多。但它代表一个方向。

一、问题

Transformer 的输出层做了这件事：

hidden h (256 维) → 矩阵 O ∈ R^{32000×256} → softmax → argmax → 词

每一步都在问全部 32000 个词「是不是你」。32000 次内积，哪怕上下文已经把候选范围压缩到几个词。

能不能不这样？

二、SPR：用排除替代打分

2.1 物理图像

想象一个巨大的投票箱，32000 个槽。Transformer 走到每个槽前问「像不像」。SPR 不这样——它站在箱子前面，只看第一个槽：「在左边还是右边？」「左边」。然后看左边的第二排：「在左上还是左下？」「右上」。逐层排除，15 步走到一个具体槽。

这 15 步从来不问「你有多像」，只问「在不在这个方向」。

2.2 树的掩码表示

每个内部节点存一个布尔掩码——一个 0/1 的向量，标记哪些词在这个子树里：

                  root (mask: 1111...1111  全 1，所有词都在)
                 /      \
        左节点(A组)      右节点(B组)
       mask: 前半=1      mask: 后半=1
       /        \        /         \
      ...       ...     ...        ...

查询从根开始。每到一个节点，hidden 的一个维度跟节点的比较规则做一次判定——「去左还是去右」。错了的那一侧的所有词，从此不再考虑。

核心： 树不做「打分排名」，做「逐级排除」。每步砍掉一半候选词。

三、堆 = 天然的矩阵

3.1 堆数组存储

二叉树存成数组堆——根在 H[0]，左子在 H[2i+1]，右子在 H[2i+2]：

H = [root, L1, R1, LL2, LR2, RL2, RR2, ...]
      ↑     ↑   ↑    ↑    ↑    ↑    ↑
     idx0  1   2    3    4    5    6

连续的地址空间——GPU 一笔读出来 H[idx]，O(1) 访问。32000 个内部节点，每个节点存一个 32000 位的掩码和一个比较规则，总共约 128MB——RTX 3090 的 24GB 装得下，还剩 200 倍空间。

3.2 推理 = 堆数组逐级查

def route(h):
    idx = 0
    for _ in range(K):        # K = log₂V ≈ 15
        node = H[idx]
        if h[某些维度] 满足 node.cmp:
            idx = 2*idx + 1   # 走左
        else:
            idx = 2*idx + 2   # 走右
    return leaf_word[idx]

每步：一次数组访问 + 一次比较 + 一次地址计算。15 步，不涉矩阵乘。

四、学习 = 堆调整

4.1 堆排序的类比

堆插入一个元素——先放最后，然后 percolate-up：每一步跟父亲比，比父亲小就交换，一直换到合适位置。

SPR 的学习也是 percolate：

**不需要梯度。**每个节点的掩码是一位比特——「这个词在不在这个子树里」。训练数据每出现一个新的（前缀，词）组合，就在相应节点的掩码上把那个词的位设成 1。没出现过的组合天然就是 0。

4.2 “不知道"的物理实现

前缀"哆啦A梦爱吃" → 沿树路径走到某个节点
  在此节点的掩码里: "铜锣烧"=1, "饭"=1
                    "樱木花道"=0, "孙悟空"=0
                    
掩码为 0 的词 → 从根开始就被排除 → 永远不可达

这不是「把概率设成 0」——是「从一开始就没有通路通往那个词」。

五、哈希碰撞

5.1 同路径异前缀

路径: root → L → RL → LLR
  德语 "die Katze" → 走这条路径
  英语 "the cat"   → 也走这条路径

两个不同语言的前缀在同一个节点上发生碰撞。该节点的掩码同时保持两个词的「可达」状态：

node[LLR].mask: ... "Katze"=1 ... "cat"=1 ...

碰撞不导致重组——只在该节点的掩码上多开一位。高频碰撞的节点自然拥有更大的孤岛。

5.2 孤岛

每个词的「孤岛」= 它的子树里所有掩码为 1 的词

已知知识 = 孤岛内的词
未知知识 = 孤岛外的词 → 从根开始就不可达

物理图像：不是「所有词的概率表」，而是一个连通图。你只能在当前孤岛里选词。通往岛外的路径不存在——不存在的东西不需要被否定。

六、与 Transformer 的关系

SPR 不是替代 Transformer——是替代 Transformer 的输出层：

Transformer (不变)
  ├── Embedding
  ├── Self-Attention (Q·K^T)        ← 保留
  ├── Cross-Attention               ← 保留
  └── FFN (hash 碰撞引擎)            ← 保留
       │
       └── hidden h
            │
            ▼
       SPR 输出层（堆数组）            ← 只换这里
            │
            └── 词

分工： FFN 负责「撞出语义」→ hidden 里已经有丰富的上下文信息。SPR 只负责「路由到正确的词」——15 次堆查找替代 32000 次 softmax。

七、当前状态

May the Code be with us.

License: GPLv3