论文：Can LLMs Be Computers? The ALM (Append-Only Lookup Machine) Architecture 作者：Percepta AI 团队 代码：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（查找）——精确的内存读取

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（门控线性）——条件计算

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（持久化）——线性组合存储

def persist(expr, name=None):
    # 把一个线性表达式存储到专用维度
    # 减少模型宽度，因为表达式组成部分可以提前释放

persist 把中间计算结果"固化"到一个维度中，供后续查找使用。它还有一个巧妙的作用：通过合并多个维度，减少模型的 d_model 宽度。

2.3 乘法怎么实现？

ALM 最巧妙的设计之一是乘法的实现。因为 FFN 是线性的（加上 ReGLU 门控），两个变量的乘法不能直接做。

源码中的 _make_multiply 函数揭示了答案：

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 累加怎么实现？

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 函数展示了这个编码过程：

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 机制

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)：

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 个点

# 操作码分派点位于半径为 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 投影：

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 的对比

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 本来就是计算机。

论文 | 代码