大语言模型的计算能力

大模型是有穷自动机

非确定型有穷自动机（NFA）的定义

非确定型有穷自动机是一个 5 元数组 $Q,\Sigma,\delta,q_0,F$，其中

1. $Q$ 是一个有穷集合，称为状态集。
2. $\Sigma$ 是一个有穷集合，称为字母表。
3. $\delta:Q\times\Sigma_\varepsilon\rightarrow \mathcal{P}(Q)$ 是转移函数。
4. $q_0\in Q$ 是起始状态。
5. $F \subseteq Q$ 是接受状态集。

大模型是 NFA 的证明

令 $q_0 =\varepsilon$ 为初始状态，大语言模型的预测函数记为

$$ \phi:{s_0s_1s_2…s_{n-1}}\rightarrow s_n,s_i \in \Sigma $$

取 $\delta$ 为：

$$ \begin{equation} \delta(q,\sigma) = \left \{ \begin{array}{ll} q \circ\sigma & \sigma \neq \varepsilon \\ q\circ\phi(q) & \sigma = \varepsilon \end{array} \right. \end{equation} $$

也就是将 $Q$ 设置为已经拥有的上文，连续预测下一个字符（若当前是输入过程，则只需要简单的叠加到状态集，不需要预测的过程）。这描述了大语言模型下的“Next Token Prediction” 范式。也就是说这个范式下的一切模型（无论是 Transformer 还是 其他的什么算子进行这种模式的预测），都跳不出这个基本的范式。

即当前的大模型无论如何提升自己的能力，其计算能力也不过是一个有穷自动机。

直接得到的重要启示是：

除了大模型，我们还需要新的范式来解决 AGI 问题。仅靠提升模型规模，注定有很多事情做不到。

额外的说明

有穷自动机是做不出基础四则运算的计算器 ¹ 的。这也意味着大模型的推理能力是不存在的。

我们认为的推理能力，不过是在有限状态空间下的穷举，例如上文中的 $\{0^n\#1^n\}$ 这个例子。更大的模型可以通过训练模拟出更长的匹配，但是从“压缩比”的角度看，终究是没有能掌握这个规律，而是通过空间换时间的方式将更多的答案在训练的过程中记住。

所以可能又回到了最初的问题——大模型是不是必须要足够大？继续增加大模型的规模还可以进一步提升泛化性，在类似这样的原本有穷自动机解决不了的问题上缓存更多的答案，“假装”大模型是可以解决它的。但这不是我们想要的答案。

Agent + LLM 可以成为完备图灵机

While 循环的图灵完备性

编程语言 WHILE 语义 (Semnatik):

• 一个 while 程序 $P$ ,通过传递 $k$ 个参数,返回一个结果, 即 $f:\mathbb{N}^k\rightarrow\mathbb{N}$
• 其他未定义的参数可以在程序里被调用,但是必须设定为 $0$
• WHILE 程序的结果在结束结束后通过 $x_0$ 传达
• 对于一个 WHILE 程序,有三种运行模式:
  • 变量赋值: $x_i=x_j+c,c\in{0,1,−1}$
  • $P_1$;$P_2$ ( $P_1$,$P_2$ 是两个任意程序程序),先运行 $P_1$ ,再运行 $P_2$
  • WHILE $x_i \neq 0$ DO $P$ END 意思是, $P$ 程序将一直被运行,直到 $x_i$ 等于 0

定理：编程语言 WHILE 是图灵完备的

证明: 我们将受限 RAM(Registermaschine)(只有 LOAD,STORE,CLOAD,CADD,CSUB 功能的 RAM) 中的每一步都用 WHILE 程序来代替计算 ²，由于受限 RAM 是图灵完备的,所以 WHILE 也是图灵完备的。

Agent 的基本范式

Agent 的基本范式恰好就是一个 While 程序，其 Python 描述如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

@dataclass
class ReAct(ABC):
    thought: Optional[str] = None
    action: Optional[str] = None

    def __post_init__(self):
        self.obs = self.run() # 获取执行 Action 的结果

    @abstractmethod
    def run(self) -> str:
        """
        执行Action
        """
        pass

    @classmethod
    @abstractmethod
    def parse(cls, text: str) -> "ReAct":
        """
        从大模型返回的文本解析成 ReAct 的实例
        """
        pass

    @property
    @abstractmethod
    def done(self) -> bool:
        """
        终止条件
        """
        pass

    @abstractmethod
    def __str__(self) -> str:
        """
        从 ReAct 中抽取信息形成新的 Prompt
        """
        pass

act = ReAct()
acts = []
while not act.done:
    acts.append(act)
    prompt = get_prompt(acts)
    act: ReAct = ReAct.parse(llm.call(prompt)) # 调用大模型，并将 response 解析成 ReAct 的实例

其中，存储和变量有两种选择：可以保存在函数 get_prompt 中（这意味着更多的人工控制设定），也可以保存在 ReAct 中（这意味着让大模型在上下文中自行决定保存哪些信息）。

所以，Agent 的基本范式是图灵完备的。

典型的几个 Agent 流程：

1. ReAct 获得反思推理能力
2. BabyAGI 基础的计划任务 Agent
3. Reflexion 长期记忆和短期记忆（短期记忆就符合上述流程）
4. AutoGPT 第一个全能 Agent

都可以转化到上述的范式中，进而获得更强大的计算能力（通用图灵机）。

突破的方向——可训练的 Agent

如果想获得更强的计算能力，需要提升的不仅仅是 LLM，而是结合了 Agent 后的整体系统。所以微调（fine tuning）和对齐（Alignment）更应该在整合了一个可学习的 Agent 之后进行。

另外，基础的预训练模型或许并不需要特别的大（当然，越大性能越好的结论不变，但与其记更多的数据不如记更多的规律），而需要把更多的训练工作后置到集成了 Agent 之后进行，这样才有可能将有穷自动机无法识别的模式学习出来。

这是通往 AGI 之路吗

到今天为止，其实我们也没有一个关于智能的合理定义。

但至少今天人能够完成的一切，都没有可以超出图灵机范式的计算能力，所以图灵机的计算能力可以当作今天人类的极限。

AGI 可以定义为:

如果以这个定义来看，那么当下的 Agent + LLM 在理论上已经可以到达人类能够触达的一切天空了。