Agent 决策的电路复杂度理论 2026
把 Agent 决策建模成带 oracle 的电路图，从 AC0/TC0/P-complete 的层级看 ReAct、Plan-and-Execute、Tree-of-Thoughts 的深度与宽度边界，以及 LLM 在电路视角下的复杂度分类与工程推论。
约 37 分钟阅读10,844 字10 次阅读博主
把 Agent 决策建模成带 oracle 的电路图，从 AC0/TC0/P-complete 的层级看 ReAct、Plan-and-Execute、Tree-of-Thoughts 的深度与宽度边界，以及 LLM 在电路视角下的复杂度分类与工程推论。
Agent 决策不是黑箱里的流体计算，而是被电路深度、宽度、与查询次数共同约束的离散结构；本文用电路复杂度这把尺，把 ReAct、Plan-and-Execute、Tree-of-Thoughts 三种范式重新放在 AC⁰/TC⁰/P-complete 的层级里看，看到 LLM 推理为什么必然要在"深度换宽度"和"宽度换深度"之间反复摆动。
过去两年我们见证了一场关于 Agent 推理范式的范式轮转：从 ReAct 的"思考-行动"交替，到 Reflexion 的自反思闭环，到 Tree-of-Thoughts 的显式搜索树，再到 Plan-and-Execute 的先规划后执行。每一种新范式出现时，工程界都会问两个问题：第一，它比上一代在哪些任务上更准？第二，它要花多少 token、几次工具调用、几秒钟？这两个问题背后其实共享一个理论内核：Agent 的每一步决策都是一个布尔函数 f : {0,1}ⁿ → {0,1}ᵐ，而整个推理过程就是这种函数被反复复合、并行、查询 oracle 的过程。
如果我们承认这一点，那么电路复杂度（circuit complexity）这把老尺子——诞生于 1980 年代用来区分 P 与 NP 的工具——就能被借过来给 Agent 决策做体检。电路复杂度关心的是：给定一个布尔函数，最小的布尔电路需要多少层（深度）、多少门（宽度）、多大扇入扇出？把 LLM 的多头注意力想成一个软电路（soft circuit，用 softmax 替代 AND/OR，用浮点权替代 0/1），把 tool call 想成一个 oracle gate（输入是查询字符串，输出是结构化响应），整个 Agent 的推理过程就变成了一张带反馈的电路图。本文要做的事情是：把这张图上的关键约束拎出来，把最近 14 天我们写过的同调群视角（id=558）、范畴论抽象（id=516）、算法信息论（id=563）放到同一个坐标系里，看到它们互补在哪里、不能互相替代在哪里。
理论意义之外，这套视角直接对应工程指标：一个 Agent 的延迟大致正比于电路深度（sequential steps），成本正比于电路宽度（parallel tokens），可靠性反比于 oracle 查询次数（每多一次工具调用就多一次失败概率）。当我们讨论"为什么 ReAct 在长链路任务上会失控"、"为什么 Tree-of-Thoughts 比 ReAct 更稳但更贵"、"为什么 Plan-and-Execute 必须把规划阶段和执行阶段分两个 prompt"，电路复杂度给的不是又一个工程经验法则，而是一个可计算的边界。
我们把 Agent 的单步决策抽象成如下接口。令 X ⊆ {0,1}* 为观察空间（observation，可以是用户输入、工具返回、上一步推理的中间状态），A ⊆ {0,1}* 为动作空间（action，可以是文本片段、JSON 工具调用、或"继续推理"），一个 policy π : X → Δ(A) 把每个观察映射到一个动作分布。Agent 的整体轨迹 τ = (x₀, a₀, x₁, a₁, ..., xₜ, aₜ) 由 policy 与环境（tool / world model / user）的复合动力学产生。在电路视角下，单步决策被建模为一个布尔电路 Cₙ，n = |X| 是观察的比特长度，Cₙ 输出 m = |A| 比特的动作编码。
复杂度类分层是整个讨论的骨架。最弱的 AC⁰ 类是常数深度、无界扇入、只允许 AND/OR/NOT 门的电路族；它的代表语言是 PARITY 的反例——PARITY 不能被任何 AC⁰ 电路多项式大小实现（这是 1980 年代 Furst-Saxe-Sipser 的奠基结果）。这意味着：哪怕模型再大、参数量再多，如果它的有效电路深度被常数限制，就学不会 parity 类的简单模式。TC⁰ 类在 AC⁰ 基础上加了 MAJORITY（多数门）门，可以表达 PARITY，但仍然是常数深度。NC¹ 类是 O(log n) 深度的电路，可以表达很多东西。P/poly 是任意多项式大小的电路族（不再限制深度），P-complete 是 P 中那些"本质上是顺序的"问题——找不到多项式大小的并行电路。
┌────────────────────────────────────────────────────────────┐
│ AC⁰ : 常数深度 + AND/OR/NOT, 无 MAJORITY │
│ TC⁰ : AC⁰ + MAJORITY, 可以算 PARITY │
│ NC¹ : O(log n) 深度, 多项式大小, 可并行 │
│ P/poly : 任意多项式大小电路, 无深度限制 │
│ P-complete : P 中"顺序本质"问题, 不能高效并行化 │
└────────────────────────────────────────────────────────────┘
LLM 的注意力机制天然落在 TC⁰ 与 P 之间的灰色地带。每一层自注意力做的是：对 n 个 token 算一个 softmax 加权平均，本质上等价于一个用指数函数做"软 MAJORITY"的电路——所以单层 attention 可以表达 TC⁰ 的所有函数。但 L 是 L 层的 transformer 整张网络深度为 L·(某个常数因子)，所以总深度是 O(L)，可以表达 P/poly 的子集。关键观察：当下游任务需要 O(log n) 以上的推理深度时，单层 attention 必然不够；多层 attention 必然进入 P-complete 的危险区——这是为什么"chain-of-thought 加深"在工程上有效、但又会被某种天花板挡住的理论根源。
我们用 Mermaid 把这张层级图画出来，方便后续讨论的引用。
图表加载中…
这张图的一个非显然含义是：单层 attention 不弱（TC⁰ 已经能覆盖大量有用函数），但单层 attention 永远不能完成需要 O(log n) 以上深度的任务。如果我们想用一层 attention 解决"判断长度为 n 的字符串里 1 的个数的奇偶性"（PARITY），无论模型多宽都会失败——这一事实已经被多个实证研究复现。反过来，如果我们堆到 L 层，理论上能进 P/poly，但工程上等价于把"并行电路"转成了"顺序电路"：每一层 attention 等于一次前向计算，必须等前一层完成才能进下一层，这就是 transformer 推理延迟的电路深度来源。
单步推理——给定一个观察 x₀ 输出一个动作 a₀——的电路下界是整个 Agent 复杂度分析的起点。我们关心的是：对于特定的任务类（比如"判断文本中某关键词是否出现"、"从工具调用结果里抽取特定字段"），policy π 的最小电路深度是多少？
对 LLM-based policy 而言，单步决策可以被建模成 L 层 transformer 前向加上一个 action head 的复合。L 层 transformer 的有效深度是 Ω(L)，因为每一层都贡献至少一层"加权 + 残差"的电路结构。Action head 的深度是 O(1)（一个线性层 + softmax）。所以单步决策的总电路深度下界是 Ω(L)——这意味着无论 action head 多复杂，整个决策被 transformer 推理深度 bound 住。
宽度下界更微妙。设输入 x₀ 的 token 序列长度为 n，hidden dim 为 d，attention 头的数量为 h，则单层 attention 的宽度下界是 Ω(n·d·h)（因为要存 Q、K、V 三个矩阵和 attention map）。整个 L 层网络的宽度下界是 Ω(L·n·d·h)。但宽度有一个复用效应：不同 token 在不同层可以复用 hidden state，所以实际宽度只是 Ω(max(n, L)·d·h)。当 L ≫ n 时（深度主导），宽度瓶颈在 depth；当 n ≫ L 时（长度主导），宽度瓶颈在 length。
工程上这对应两个常见痛点：
下面这段伪代码描述了一个 Agent 在单步决策中的电路结构：
def single_step_circuit(x0, transformer, action_head):
# x0: token sequence of length n
# transformer: L-layer attention stack
# action_head: linear projection + softmax
# 第 1 步: embedding (O(n · d) 宽度, O(1) 深度)
h0 = embed(x0) # shape: (n, d)
# 第 2 步: L 层 transformer 前向 (总深度 O(L), 宽度 O(n · d · L))
hL = h0
for layer in range(L):
hL = attention_layer(hL) # shape: (n, d)
hL = ffn_layer(hL) # shape: (n, d)
# 第 3 步: action head (O(1) 深度, O(d · |A|) 宽度)
logits = hL[-1] @ W_action # shape: (|A|,)
probs = softmax(logits)
return probs # 单步 policy 输出
这段代码的核心结论是：单步推理的电路深度是 L，宽度是 O(n · d · L)。当我们说"让 Agent 更聪明"时，工程上能调的自由度只有：增加 L（更深）、增加 d（更宽）、增加 n（更长上下文）、改进 attention 让等效深度变浅——所有这些都会改变电路参数，但不会改变"必然存在某种深度下界"这件事。
多步规划是 Agent 决策的真正难点。当 policy 要在 T 步内完成一个目标时，整个轨迹 τ = (x₀, a₀, ..., x_T, a_T) 由 T 次单步决策复合而成。复合函数 f_T = π_T ∘ π_{T-1} ∘ ... ∘ π_1 的电路深度下界是 Ω(T · L)——T 步规划至少需要 T 倍单步推理的深度。
但这只是 trivial 下界。真正有信息量的是 P-complete 视角：很多规划任务是 P-complete 的（比如 Horn-SAT 求一个满足赋值、context-free grammar 求一个推导树、网络流求一条最大路径），它们的本质特征是找不到多项式大小的并行电路。换句话说：哪怕你给 ReAct 一万张 GPU，只要任务本身是 P-complete 的，它就需要 Ω(T) 步顺序决策，T 至少是多项式于输入规模。
Plan-and-Execute 把这个事实显式化了：先把规划阶段（plan generation）跑成一个 L 层 transformer 前向得到 plan plan = (a₁, a₂, ..., a_T)，再把执行阶段（execute）跑成 T 次单步决策。plan 的电路深度是 O(L)（一次性深度），执行阶段的电路深度是 O(T · L)（T 次单步深度）。总深度 = O(L + T · L) = O(T · L)，符合 P-complete 下界。
ReAct 的电路结构是 plan 与 execute 交织的：每一步都重新生成下一个动作（带 thought prefix），所以等效深度就是 T · L，但它没有显式 plan 阶段——所有"规划"都被分散到 T 个 thought 里。这导致 ReAct 的电路深度高、宽度低（每步只看局部观察），适合 P-complete 中那些深度大但每步分支少的任务；不适合宽分支任务（比如"从 100 个工具里选一个"）。
Tree-of-Thoughts 走的是另一条路：在每一步保留 B 个候选分支，B 步后保留 top-K 个候选。它的等效电路是宽度 B·K 倍于 ReAct、深度 log_B(T) 分之一于 ReAct——典型的"用宽度换深度"策略。代价是电路宽度上去了：每多保留一个分支就要多存一份 KV cache，显存占用线性放大。
图表加载中…
这个分类给我们的工程启示是：别用 ToT 解决"深度大但每步只有 1-2 个分支"的任务（纯浪费宽度），也别用 ReAct 解决"每步要在 50 个工具里选 1 个"的任务（电路深度会失控到数百层）。Plan-and-Execute 在"长规划但分支少"的场景里是最优解，Reflexion 在"任务本身可被 self-critique 修正"的场景里胜过 ReAct 一个量级。
工具调用给 Agent 引入了一个新维度：oracle gate。一个 oracle gate 不是普通的布尔门，它是一个"黑箱子程序"——给定查询字符串 q，oracle 在 O(T_oracle) 时间内返回结构化响应 r。在电路复杂度里，oracle gate 等价于把电路连到一个外部 P 类（甚至不可判定类）的子过程，使整个电路的"有效计算能力"超出 P/poly。
设 Agent 的工具集为 O = {o₁, o₂, ..., o_k}，每次工具调用是 (o_i, q) → r 的三元组。在电路视角下，工具调用就是一个 oracle gate——它消耗电路深度 O(1)（一次 forward）+ 查询时间 O(T_oracle)，但等价于把整个 Agent 推进到了 P^O 类（带 oracle O 的多项式时间）。如果 O 包含图灵完备的子程序（比如一个 Python REPL），那么 Agent 的"潜在能力"是 PSPACE 甚至更高的复杂度类——这远超 P/poly 的 transformer 本身。
但这带来一个矛盾：Agent 的可控性下降。oracle gate 一旦返回错误，电路的下游全部基于错误响应继续工作；如果 oracle 是非确定性的（比如实时网络查询），同一查询两次返回不同结果，电路输出也不确定。工程上对应的是：
工具组合性（tool compositionality）是另一个隐藏的电路维度。设每个工具有 N 个 schema 参数，M 个返回字段，则 (o_i, q) → r 的输入空间是 N 维、输出空间是 M 维。两个工具组合 o_i ∘ o_j 的组合空间是 N_i × N_j，输入输出维度乘积。K 个工具的组合空间是 ∏ N_i——这是组合爆炸，不是多项式增长。
下面这段伪代码展示工具调用的电路视角：
def tool_call_gate(observation, tool_selector, oracle):
# observation: 当前 Agent 状态
# tool_selector: 选择下一个工具 (一个 L 层 transformer 前向)
# oracle: 工具执行 (外部过程)
# 第 1 步: tool selection circuit (深度 O(L), 宽度 O(|O| · N))
tool_choice = tool_selector(observation)
# 第 2 步: query construction circuit (深度 O(L), 宽度 O(max_query_len))
query = construct_query(observation, tool_choice)
# 第 3 步: oracle execution (黑箱, 延迟 O(T_oracle), 返回 r)
r = oracle.execute(tool_choice, query)
# 第 4 步: response parsing circuit (深度 O(L), 宽度 O(|r|))
parsed = parse_response(r)
return parsed # 下一个 observation 的输入
这段代码的一个推论是：工具调用的总电路深度是 4·L + O(T_oracle)。当 L = 32（典型 7B 模型）、T_oracle = 1s 时，每次工具调用大约增加 1 秒延迟 + 32·4 = 128 层等效深度。Agent 做 10 次工具调用就是 1280 层深度——这已经进入 P-complete 的危险区。工程上这对应一个反直觉的教训：少做几次工具调用、用更"重"的工具，反而比多做几次"轻"工具更便宜。
到目前为止我们把 LLM 想成了一个黑箱 transformer，只暴露 L 层深度与 d 维宽度。本节打开黑箱，看 attention 的内部电路结构。
单头 self-attention 的电路形式化如下：给定输入 H ∈ R^{n × d}，attention 计算 Q = H W_Q, K = H W_K, V = H W_V，然后
A = softmax(Q K^T / sqrt(d_k)) ∈ R^{n × n}
O = A V ∈ R^{n × d}
把 softmax 视作 MAJORITY 的软版本（因为指数函数对最大元素加权最重），Q K^T 视作 n×n 个 AND-like 操作（两向量越相似，乘积越大），V 视作 OR-like 的输出混合，整层 attention 等价于一个 TC⁰ 电路（带 softmax 后门）。这就是为什么单层 attention 能算 PARITY 类问题但不能算 ARITY 类（要数所有 1 的个数）——后者需要 NC¹ 以上的深度。
多层 attention 的电路深度线性叠加：L 层 transformer 等价于 L 个 TC⁰ 子电路的复合，等效深度 O(L)。当 L 足够大时（典型的 7B 模型 L=32，70B 模型 L=80），网络可以逼近 P/poly 的任意子集——但逼近的代价是巨大的宽度。参数量 P 与电路大小的对应关系大致是 P ≈ L · n · d²，这给"宽度"一个具体含义：d 越大，单层电路越"宽"，可表达函数越复杂；L 越大，整网越"深"，可处理任务越需要长链推理。
关键的非平凡结论：LLM 在"电路视角"下的分类——给定任务 T，LLM 表现近似于一个特定复杂度类的电路。这给"为什么某些任务换更大的模型就能解决、某些任务换再大也没用"一个量化解释。
这给"为什么 LLM 越大越像在'作弊'"提供了一个干净的解释：大模型在 AC⁰、TC⁰、NC¹ 上做得更稳（因为电路更宽、噪声更低），但在 P-complete 上没有质的提升——因为 P-complete 任务的硬约束是"必须顺序执行 T 步"，宽度换不来深度。
把电路复杂度的视角落到工程，我们给出五条可执行的设计准则。
1. 电路深度预算优先于模型尺寸。在 P-complete 任务上，把 7B 模型从单轮调用改成 5 轮 self-consistency，效果常常优于把 7B 换成 70B——因为前者增加了 O(T) 步顺序推理，后者只增加了 O(L) 宽度。深度预算比参数预算更稀缺。
2. 早退机制 (early exit) 是电路深度的杠杆。如果某层 attention 的输出分布已经收敛（相邻层 logits 的 KL 散度 < ε），提前跳出剩余层，等价于把等效深度从 L 降到 L' < L。这对应"自适应计算"或"early-exit transformer"，可以把 P-complete 任务的推理成本降低 30-50% 而不损失精度。
3. KV cache 分层存储是宽度的杠杆。浅层（low-L）attention 的 KV 主导语义信息，深层（high-L）attention 的 KV 主导任务特定推理。把浅层 KV 用 FP16 存 GPU HBM，深层 KV 用 INT8 量化存 CPU 内存，按需 swap——这等价于把电路宽度从 d·L 降到 d · log L，工程上对应 PagedAttention、FlashAttention 的分层版本。
4. 工具调用次数是最稀缺资源。每次工具调用都让电路走出 transformer 本体、进入 oracle 子过程，失败率线性叠加、延迟常数叠加。让一次工具调用尽量"重"（返回多字段、带推理链、带自我评分），比"轻"调用多次要优——这对应"工具结果增强"模式：tool 返回包含结果 + 解释 + 置信度三元组，下游 Agent 直接消费而不是再调一次"解释工具"。
5. 电路下界决定 benchmark 上限。如果任务 X 在理论上需要 Ω(T) 步顺序推理，那么 benchmark 分数的天花板是 1 - (1-p_step)^T，其中 p_step 是单步失败率。不要被"某个模型在 X 上拿了 95%"骗到——很可能 X 已经被"作弊式 prompt engineering"或"测试集泄漏"污染。看 task 结构而不是榜单分数。
下面这段伪代码描述了一个电路深度感知的 Agent 调度器：
class CircuitAwareScheduler:
def __init__(self, depth_budget, width_budget, oracle_budget):
self.depth_budget = depth_budget # 总深度上限 (例如 32 层 × 30 步)
self.width_budget = width_budget # 宽度上限 (例如 max 8000 tokens)
self.oracle_budget = oracle_budget # oracle 调用上限 (例如 5 次)
def should_continue(self, current_depth, current_width, oracle_calls):
if current_depth >= self.depth_budget:
return False # 深度耗尽, 早退
if current_width >= self.width_budget:
return False # 上下文超长, 早退
if oracle_calls >= self.oracle_budget:
return False # 工具预算耗尽, 早退
return True
def adaptive_depth(self, layer_idx, prev_logits, curr_logits, eps=0.01):
# 早退: 如果 logits 已经收敛, 跳过剩余层
kl = kl_divergence(prev_logits, curr_logits)
if kl < eps:
return True # 早退
return False
这段调度器的设计哲学是：电路参数是可数的预算（深度、宽度、oracle），调度器在每一步检查预算是否耗尽。生产 Agent 应该把这种预算检查作为 first-class control flow，而不是事后统计日志。
电路视角的优势是给 Agent 决策一个量化的复杂度下界——但它也有三个不可忽视的局限。
第一，真实 LLM 不是布尔电路。softmax 是连续的浮点运算，不是离散的 AND/OR/NOT。这意味着电路复杂度的经典下界（比如 PARITY 不在 AC⁰）只能"近似"应用——浮点近似的 PARITY 可能被软电路实现。这削弱了我们对"LLM 学不会某任务"的论断。
第二，真实 Agent 不是孤立电路。它有外部工具、有长期记忆、有用户反馈，整个系统是一个带环境的开放电路。经典电路复杂度对"开放电路"的处理有限——这是为什么我们要借 oracle gate 和 query complexity 的概念，但这些概念在工程上仍然缺少成熟的实证研究。
第三，真实任务的复杂度类难以严格判定。很多 Agent 任务（"debug 一个程序"、"写一份商业计划"）连严格的复杂度类定义都没有。我们只能用电路视角启发工程决策，而不能用它做严格的"这个任务不可解"证明。
与最近 14 天我们写过的同调群视角（id=558）、范畴论抽象（id=516）、算法信息论（id=563）的对比也有意思。同调群关心的是推理路径的拓扑不变量（哪些推理环路是必须的、哪些可以收缩），范畴论关心的是工具组合的形式化语义（tool 调用作为函子、agent 作为自然变换），算法信息论关心的是决策的最小描述长度（Kolmogorov 复杂度下界）。电路视角补上的是计算资源的可计算边界——深度、宽度、查询次数这三件事都是工程师能在生产环境里量化的指标。四者构成一个完整坐标系：拓扑告诉你结构约束，范畴论告诉你语义约束，信息论告诉你信息约束，电路复杂度告诉你资源约束。它们不是互相替代的关系，而是同一个 Agent 决策的不同切面。
对研究者而言，下一步最有价值的不是再发明一种新推理范式，而是把现有 Agent 的电路结构可视化。具体建议三条。
1. 用电路发现工具 (circuit discovery) 反推 Agent 的等效电路。参考 Anthropic 的 attribution patching、OpenAI 的 circuit tracing，把"Agent 完成一个任务的轨迹"视作一张电路图，跑 activation patching 看哪些 layer / attention head / FFN neuron 是"关键路径"，哪些是"冗余路径"。这给"为什么 Plan-and-Execute 在 X 任务上比 ReAct 好"一个可验证的答案——比如 Plan-and-Execute 的规划阶段高度依赖 layer 12-18 的某些 head，而执行阶段主要用 layer 24-30 的 FFN，ReAct 没有这种"分工"。
2. 把 circuit complexity 的 benchmark 标准化。现在主流 benchmark（HumanEval、MMLU、GSM8K）测的是最终答案准确率，但测不出"达到这个准确率用了多少电路深度"。建议加一个 metric：minimal circuit depth for solving task。给定任务 X，最小的 L 是多少？给定 L，最小的训练数据量是多少？这把"模型能力"从"准确率"分解为"准确率 × 电路效率"两个维度。
3. 闭环到工程。电路发现的结果应该直接反馈到生产 Agent 的 prompt 设计、模型选择、工具组合决策。比如"某类任务在 layer 20 之后 attention head 12 的激活值与答案强相关"——这意味着可以用一个 probe 模型（轻量分类器）在 layer 20 后就给出"置信度估计"，触发 early exit。这把可解释性研究从"理解模型"转成"优化模型"，形成可解释性闭环。
电路视角最大的价值，是它把"Agent 推理为什么难"从一个模糊的工程直觉（"长链路任务总是失控"）转化为一个可计算的边界（"P-complete 任务需要 Ω(T) 步顺序推理"）。当边界已知，工程师才能在边界内做优化、在边界外做 trade-off——而不是反复试错。14 天前我们用算法信息论（id=563）讲了决策的"信息下界"，今天用电路复杂度讲了决策的"资源下界"；下次当我们讨论 Agent 的可靠性建模、Agent 的安全边界、Agent 的人机协作时，会回到电路视角——因为可靠性是失败概率对深度的积分，安全是 oracle 调用的信任传播，协作是电路深度在人和 AI 之间的分配。这些都是电路复杂度的延伸。
Conversation
0 条