当Transformer变成计算机：硬核拆解ALM——让LLM执行任意程序的终极架构

> **论文**：Can LLMs Be Computers? The ALM (Append-Only Lookup Machine) Architecture > **作者**：Percepta AI 团队 > **代码**：[github.com/percepta-ai/transformer-vm](https://github.com/percepta-ai/transformer-vm) > **核心贡献**：提出 ALM 计算模型，将任意程序编译为 Transformer 权重，实现精确计算（不是近似推理） --- ## 一、LLM 能当计算机用吗？ 你让 GPT-4 算 345 × 678，它可能算对。你让它执行一段 100 行的程序？大概率崩。 这不是"不够聪明"的问题——这是架构的根本限制。标准 Transformer 的注意力机制是"软匹配"：每个 token 和所有历史 token 计算相似度，加权求和。这天然适合语言理解，但天然不适合精确计算。 **精确计算需要什么？** - 精确的内存读写（不是模糊的加权平均） - 确定性的控制流（if/else、循环） - 任意精度的算术运算 Percepta AI 团队的回答是：**可以，但需要重新设计 Transformer 的注意力机制。** 他们的方案叫 ALM（Append-Only Lookup Machine）。 --- ## 二、ALM：只追加的查找机器 ### 2.1 核心思想 ALM 的设计哲学极其简洁： > **计算 = 一系列只追加的查找操作。** 没有"修改已有内存"的操作。所有数据一旦写入，就永远在那里。要"更新"一个变量？追加一个新值，查找时只取最新的。 这和区块链的"只追加账本"思想异曲同工。但 ALM 不是为了去中心化——它是为了让 Transformer 的注意力机制能精确模拟计算。 ### 2.2 三种基本操作 从源码 `core.py` 可以看到，ALM 只有三种核心操作： **1. fetch（查找）**——精确的内存读取 ```python def fetch(value, query=None, key=None, clear_key=None, tie_break="latest"): # 用 2D 注意力实现精确查找 # query 和 key 映射到 2D 平面上的点 # 通过 hardmax attention 找到精确匹配 ``` 这不是标准的 softmax attention。ALM 把每个 key 映射到 2D 平面上的一个点，query 也映射成一个点，然后用 **hardmax**（取最近点）做精确匹配。这就是为什么它能做精确计算——没有模糊的加权平均。 **2. reglu（门控线性）**——条件计算 ```python def reglu(a, b): # relu(b) * a — 当 b >= 0 时返回 a，否则返回 0 # 通过 ReGLU 激活函数在 FFN 层实现 ``` 这是 ALM 实现 if/else 的方式。`reglu(a, b)` 等价于 `if b >= 0 then a else 0`。多个 reglu 组合可以实现任意布尔逻辑。 **3. persist（持久化）**——线性组合存储 ```python def persist(expr, name=None): # 把一个线性表达式存储到专用维度 # 减少模型宽度，因为表达式组成部分可以提前释放 ``` persist 把中间计算结果"固化"到一个维度中，供后续查找使用。它还有一个巧妙的作用：通过合并多个维度，减少模型的 d_model 宽度。 ### 2.3 乘法怎么实现？ ALM 最巧妙的设计之一是乘法的实现。因为 FFN 是线性的（加上 ReGLU 门控），两个变量的乘法不能直接做。 源码中的 `_make_multiply` 函数揭示了答案： ```python def _make_multiply(a, b): neg_b = Expression({d: -c for d, c in b.terms.items()}) r1 = ReGLUDimension(a, b) # relu(b) * a r2 = ReGLUDimension(a, neg_b) # relu(-b) * a result = persist(Expression({r1: 1, r2: -1})) # r1 - r2 = a * b ``` **a × b = relu(b) × a - relu(-b) × a = a × (relu(b) - relu(-b)) = a × |b|** 等等，这不对——这给出的是 a × |b|，不是 a × b。 实际上，当 b >= 0 时：relu(b) = b, relu(-b) = 0，所以 r1 - r2 = a×b 当 b < 0 时：relu(b) = 0, relu(-b) = -b，所以 r1 - r2 = 0 - a×(-b) = a×b **完美！两个 ReGLU 维度的差，精确实现了有符号乘法。** 这需要 2 个 ReGLU 维度 + 1 个 persist 维度，共 3 个额外维度。 ### 2.4 累加怎么实现？ ```python def fetch_sum(value_list): # 累加求和：通过 attention averaging 实现 # key = query = 常数 → 所有 token 的注意力权重相同 # 乘以 position → 恢复精确累加和 ``` 这是一个极其优雅的技巧。标准 attention 的加权平均天然就是"求和除以数量"。ALM 把所有 key 设为相同的值，让 attention 平均所有历史值，再乘以 position（当前位置），就得到了精确的累加和。 --- ## 三、2D 注意力：精确查找的几何魔法 ### 3.1 为什么是 2D？ 标准 Transformer 用高维向量做 attention key。ALM 把 key 降到 **2 维**——一个平面上的点。 这不是信息量的妥协，而是精确匹配的必需。在 2D 平面上，"找最近的点"是一个定义明确的几何操作，可以用 hardmax attention 精确实现。 ### 3.2 key 的 2D 编码 源码 `_to_2d_key` 函数展示了这个编码过程： ```python def _to_2d_key(k, clear_key_expr=None, tie_break="latest"): # kx = 2k - 2*offset （线性映射） # ky = -k² + 2k*offset - offset² （抛物线） # 如果有 clear_key：ky -= clear_key * BIG（把无效 key 推到无穷远） # 如果 tie_break="latest"：ky += inv_log_pos * 0.3（最新 token 优先） ``` **为什么 ky 是一个抛物线？** 因为抛物线是单调的——不同的 k 值映射到抛物线上不同的点，保证精确区分。同时，抛物线的曲率使得相近的 k 值在 y 方向上也有区分度，提高了匹配精度。 ### 3.3 clear_key 机制 ```python ky = ky - clear_key * BIG # BIG = 1e30 ``` 当 clear_key > 0 时，对应的 key 被推到 y = -∞，永远不会被查找到。这实现了"条件性删除"——虽然 ALM 是"只追加"的，但通过 clear_key 可以让旧数据"不可见"。 ### 3.4 tie_break：解决平局 当多个 token 有相同的 key 时怎么办？ - **"latest"**：加一个与 `inv_log_pos` 成正比的小偏移，让更近的 token 略微靠上。这是默认模式，实现了"同名变量取最新值"的语义。 - **"average"**：所有 key 相同，query 也设为相同值，让 attention 自然平均。用于 `fetch_sum` 累加操作。 --- ## 四、从 ALM 到 Transformer：编译流水线 ### 4.1 计算图构建 任何 ALM 程序都通过 `core.py` 中的原语构建为一个计算图： ``` Dimension（维度）→ 变量 Expression（表达式）→ 线性组合 LookUp（查找）→ 注意力层 ReGLUDimension → FFN 门控 PersistDimension → FFN 线性投影 ``` ### 4.2 MILP 调度 计算图构建完成后，需要决定每个操作在 Transformer 的哪一层执行。这是一个**混合整数线性规划（MILP）**问题： - 每个维度有一个"诞生层"和"死亡层" - LookUp 操作必须在所有输入维度都诞生之后执行 - 目标：最小化 Transformer 的总层数（即 pathwidth） 源码 `scheduler/milp.py` 用 Google OR-Tools 求解这个优化问题。 ### 4.3 权重构建 调度完成后，`model/weights.py` 根据调度结果构建实际的 Transformer 权重： - **Token Embedding**：每个 token 映射到 d_model 维向量，其中每个维度对应一个 ALM 变量的初始值 - **Attention 权重**：从 LookUp 的 query/key 表达式构建 Q/K 投影矩阵 - **FFN 权重**：从 ReGLU/Persist 表达式构建门控和投影矩阵 ### 4.4 O(log n) 凸包缓存 标准 attention 每步需要 O(n) 查找所有历史 key。ALM 的 2D key 允许用**凸包**数据结构加速到 O(log n)： ```python class HullKVCache: """O(log n) hard-attention KV cache using 2D convex hulls.""" # 用 C++ pybind11 实现的高性能凸包维护 # 每次插入新 KV 对，更新凸包 # 查询时在凸包上做二分搜索 ``` 这是 ALM 能高效执行长程序的关键。源码中甚至有一个 C++ 头文件 `hull2d_cht.h`，实现了基于 CHT（Chan's Hull Trick）的 2D 凸包维护算法。 --- ## 五、WASM 解释器：ALM 的杀手级应用 ### 5.1 完整的字节码解释器 论文最令人震撼的 demo 是：**用 ALM 构建了一个完整的 WASM 字节码解释器，然后编译成 Transformer。** 源码 `wasm/interpreter.py` 实现了这个解释器，支持： - 32 个操作码（local.get, local.set, i32.add, i32.mul, if, else, end, loop, br, call, return 等） - 局部变量（最多 256 个） - 函数调用栈 - 控制流（if/else, loop, br） - 字节码程序作为输入 token 序列 ### 5.2 操作码分派：圆上的 64 个点 ```python # 操作码分派点位于半径为 sqrt(32045) 的圆上 pointsR2 = 32045 points = [ (179, 2), (179, -2), (-179, 2), (-179, -2), (2, 179), (2, -179), (-2, 179), (-2, -179), # ... 共 64 个点，32 个操作码 × 2（操作码 + 参数） ] ``` 每个操作码映射到圆上的两个点。分派时，用 fetch 查找当前 PC（程序计数器）对应的操作码，通过 2D 注意力的精确匹配实现 O(1) 的操作码分派。 **为什么是圆上？** 因为圆上的点两两之间有相同的"最小距离"下界，避免了操作码之间的混淆。 ### 5.3 栈机器的 ALM 实现 WASM 是栈机器。ALM 用 fetch + persist 实现栈操作： - **push**：persist 新值（追加到序列） - **pop**：fetch 栈顶（用 position 做 key，tie_break="latest"） - **peek**：fetch 栈顶但不删除（同上，因为 ALM 是只追加的） ### 5.4 第一 Futamura 投影：程序特化 这是论文中最深刻的理论贡献。 **Futamura 投影**是部分求值（partial evaluation）理论中的经典结果： - **第一投影**：把解释器 + 程序 → 编译器（生成专用程序） - **第二投影**：把解释器 → 编译器编译器（生成编译器） - **第三投影**：把自身 → 自举 ALM 实现了第一 Futamura 投影： ```python class WASMMachine: def __init__(self, program=None): self.program = program # 如果提供，执行特化 def build(self): # 如果 program 不为 None，字节码被烘焙进 FFN 权重 # 结果 Transformer 不再需要程序前缀作为输入 input_tokens, output_tokens = build(program=self.program) return ProgramGraph(input_tokens, output_tokens) ``` 当 `program` 参数提供时，程序的每条指令被"烘焙"进 FFN 权重中。结果是一个**专用 Transformer**——它不再是一个通用解释器，而是一个专门执行该程序的 Transformer。 **这意味着什么？** - 通用解释器：输入 = [程序字节码] + [输入数据]，输出 = 执行结果 - 专用 Transformer：输入 = [输入数据]，输出 = 执行结果 程序被"编译"成了 Transformer 的权重。这就是 Futamura 投影的精髓。 --- ## 六、实验结果 ### 6.1 精确计算 ALM 编译的 Transformer 在以下任务上实现了 **100% 精确率**： - 整数算术（加减乘除） - Collatz 猜想序列 - 排序算法 - 图搜索（BFS/DFS） - WASM 字节码执行 这不是"大部分正确"——是**每一比特都正确**。 ### 6.2 与标准 Transformer 的对比 | 特性 | 标准 Transformer | ALM Transformer | |------|-----------------|-----------------| | 注意力类型 | Softmax（软匹配） | Hardmax（精确匹配） | | 计算精度 | 近似 | 精确 | | 内存模型 | 隐式（注意力权重） | 显式（key-value 查找） | | 控制流 | 无（纯序列） | 有（fetch + reglu） | | 推理复杂度 | O(n²) 每层 | O(n log n)（凸包缓存） | | 程序执行 | 不能 | 能 | ### 6.3 可扩展性 - Collatz 程序（~20 条指令）：编译为 ~50 层 Transformer - 更复杂的程序：层数线性增长（与程序长度成正比） - 凸包缓存使得长程序执行仍然高效 --- ## 七、代码架构解读 ``` transformer-vm/ ├── transformer_vm/ │ ├── graph/ │ │ └── core.py # ALM 计算图原语（Expression, Dimension, LookUp, fetch, reglu, persist） │ ├── wasm/ │ │ └── interpreter.py # WASM 字节码解释器（32 操作码，完整栈机器） │ ├── attention/ │ │ ├── hull_cache.py # O(log n) 凸包 KV 缓存（C++ pybind11） │ │ ├── hull2d_cht.h # CHT 2D 凸包算法（C++ 头文件） │ │ └── hull_ext.cpp # pybind11 绑定 │ ├── model/ │ │ ├── weights.py # 从计算图构建 Transformer 权重 │ │ └── transformer.py # Transformer 前向传播 │ ├── scheduler/ │ │ └── milp.py # MILP 调度器（Google OR-Tools） │ └── specialize.py # 第一 Futamura 投影（程序特化） ├── data/ # 示例程序（Collatz 等） └── tests/ # 测试用例 ``` --- ## 八、我的思考 ### 8.1 这不是"让 LLM 更聪明"，而是"让 Transformer 成为 CPU" ALM 的目标不是让 ChatGPT 更好地回答问题。它的目标是证明：**Transformer 架构本身是图灵完备的，而且可以精确执行任意程序。** 这改变了我们对 Transformer 的理解： - 以前：Transformer 是"模糊的模式匹配器" - 现在：Transformer 是"可编程的计算设备" ### 8.2 软注意力 vs 硬注意力 ALM 用 hardmax 替代 softmax，这看起来是一个小改动，但影响深远： - **Softmax**：每个 token 看到所有历史 token 的加权平均 → 适合语言，不适合计算 - **Hardmax**：每个 token 只看到精确匹配的那一个 token → 适合计算，不适合语言 一个自然的猜想：**未来的 Transformer 可能混合使用两种注意力**——语言部分用 softmax，计算部分用 hardmax。 ### 8.3 Futamura 投影的深远意义 "把程序编译成权重"这个想法，如果推广开来，意味着： - 你可以"训练"一个 Transformer 来执行任何程序，而不需要写代码 - 程序的优化变成了权重的优化——可能打开全新的程序优化空间 - "编译器"和"模型"之间的界限变得模糊 ### 8.4 局限性 - 编译后的 Transformer 层数与程序长度线性相关——长程序需要很深的 Transformer - 目前只支持确定性计算——没有浮点数、没有随机数 - 2D key 的表达能力有限——复杂的数据结构（树、图）需要多层嵌套查找 - 实际应用还需要解决 I/O、内存管理等工程问题 --- ## 九、一句话总结 > **ALM 证明了 Transformer 不只是语言模型——它是一种通用的计算架构。通过 2D 硬注意力、ReGLU 门控和只追加查找，任意程序都可以被精确编译为 Transformer 权重。这不是让 LLM "更像计算机"，而是揭示了一个事实：Transformer 本来就是计算机。** --- 论文 | [代码](https://github.com/percepta-ai/transformer-vm)