From Agent Loops to Structured Graphs: A Scheduler-Theoretic Framework for LLM Agent Execution #

Hu Wei | 2026-04 | https://arxiv.org/abs/2604.11378 Category: agent | Tags: framework, scheduling, dag, position-paper, agent-runtime Read: 2026-04-18

Core Contribution #

将 LLM agent 的执行系统统一为一个 scheduler 模型 $\mathcal{E}=(\mathcal{S},\mathcal{U},\mathcal{P},\mathcal{O},\Delta)$，用 ready-set 基数 $|\mathcal{U}|$ 把 Agent Loop 和 graph-based executor 放到同一条连续谱上，并据此提出一个牺牲表达力换可控性的静态 DAG 执行框架 Structured Graph Harness (SGH)。

Summary #

Motivation：主流 LLM agent 采用 Agent Loop——单个 LLM 不断读取增长中的 context window 决定下一步。作者指出这个范式有三个结构性缺陷：(1) 步骤依赖是隐式的、不可验证的；(2) 失败恢复没有边界语义，LLM 可以无限 replan；(3) 执行计划可被 LLM 静默重写，事后无法构造忠实的 audit trail。作者在 70 个开源 agent 项目中观察到 60% 都是 Agent Loop 变体，问题不是个例。

Method：作者把所有 agent 执行系统形式化为 $(\mathcal{S},\mathcal{U},\mathcal{P},\mathcal{O},\Delta)$ 五元组，关键观察是：Agent Loop 是 $|\mathcal{U}|\le1$ 的 single-ready-unit scheduler，$\mathcal{P}$ 是 LLM 推理这个 "不可检查的非确定策略"；而 graph executor 则可以达到 $|\mathcal{U}|\ge 1$。基于这个视角，作者提出 SGH——把控制流从 context 里 "拉" 到一个显式静态 DAG 里，并做三个设计承诺：(1) plan 在单个 version 内不可变；(2) planning / execution / recovery 三层严格分离；(3) recovery 遵守三级严格升级协议 local_retry → local_patch → request_replan，跳级禁止。同时形式化了节点状态机（10 个状态，证明了有界终止和 conditional soundness），以及 all_of / any_of join 语义（显式排除 first_of 竞争性并行）。

Results：这是一篇 position paper + design proposal，没有实现也没有实验数据。主要 "结果" 是：(1) 一个可比较 Agent Loop / LangGraph / Airflow / TDP 等 70 个系统的统一框架；(2) 四条设计原则和明确的牺牲/收益表；(3) 状态机的 termination 和 soundness 证明；(4) 一个七组对照的实验 protocol (G0–G6)，把总增益分解为 $G_{\text{plan}}, G_{\text{scaffold}}, G_{\text{graph}}, G_{\text{patch}}, G_{\text{replan}}$ 五个可归因分量。

Key Findings #

• Agent Loop 的本质局限不是 "提示不够好"，而是 $|\mathcal{U}|=1$ 的 scheduler 结构——加 planner、加 reflection 都改不了这一点，只有显式 DAG 才能让 $|\mathcal{U}|\ge 1$。
• OpenAI parallel tool calls / 异步操作虽然有 $|\mathcal{U}|>1$，但策略仍然非确定（LLM 决定哪些并行），不构成 "结构性并行"。
• 70 个项目调研中 graph/flow 系统的 failure-loop 行为明显更常见（4 个里有 3 个），state-machine 系统几乎没有；作者把这个归因于 unbounded recovery 而非 graph 本身。
• Soundness 不是绝对的。Contract validation 的正确率 $p_v$ 对 syntactic check 接近 1，对 LLM-based semantic check 可能远低于 1，因此 $\Pr[\text{all correct}]\ge \prod_v p_v$ 的 validation gap 不可消除，只能通过 side-effect 分类 + human-in-the-loop 缓解。
• 明确排除 first_of 竞争性并行、递归子图展开、parent-chain rollback、动态拓扑修改——这些能力每一个都对应 violate 某条设计原则，不是疏忽。
• 自嘲式坦白：如果 planner 生成的是一条线性链（无 parallel branch），SGH 就退化为 single-ready-unit scheduler，多出来的价值只剩 bounded recovery + 审计 + context 隔离。作者估计 60-70% 任务其实是线性的。

Limitations #

• 纯理论文章，无 prototype，无 benchmark 结果。所有 "graph gain > 0" 都是 theoretical prediction。
• 静态 DAG 假设对 exploratory / creative / 未知 root-cause 的调试任务天然不成立。
• 多就绪单元并行会放大 planner 的错误：一旦 DAG 错了（漏依赖 / 伪依赖 / 粒度错），会在多个并行分支上同时浪费 token。
• Cold start：没有可复用 DAG 模板的新任务里，planner 要从零构造 DAG，其收益可能被摊销不掉。
• 实现复杂度高：粗估 3300–6500 行生产级代码，是 Agent Loop 的 10 倍。
• 调研方法论本身不严格（70 个项目是主观挑选、人工分类、κ=0.84 的两人评审），论文多处自承 "qualitative evidence"。

Infrastructure Impact #

• Algorithm: 不直接影响模型训练，但给 agent 训练数据合成提供一个结构化视角——节点级 trace + plan version 可作为高质量 SFT / RL 数据格式。
• Kernel: N/A——论文不涉及 GPU kernel。间接影响：多就绪单元并行会提高对多请求并发推理吞吐的需求，偏好 continuous batching + prefix cache 友好的 serving。
• Framework: 这是 framework 层的核心工作。对 vLLM/SGLang 的启示是：agent serving 需要把每个 node 看成独立 request，对 plan-level 的 KV / prefix cache 复用要有显式接口，同时支持多 ready node 并发调度。
• LLM: 不要求模型改动，但对 LLM 的 output contract / structured output / function calling 稳定性提出更高要求——contract validation 失败直接触发 recovery。
• Agent: 本论文的主战场。提供了一个把 LangGraph / CrewAI / Claude Code / OpenAI Codex agent 放在同一坐标系里量化比较的语言，把 "是否可审计 / 是否有界 / 是否可并行" 变成可测量的设计轴。
• Cluster: N/A。
• Hardware: N/A。
• Code: 提出了一个可实现的 3300-6500 行参考架构，对想写结构化 agent runtime 的工程团队是一个蓝图。

---

Deep Analysis (agent) #

时代定位 (Era Positioning) #

2025-2026 年 agent 领域正在经历从 "Agent Loop 野蛮生长" 到 "Graph orchestration 沉淀" 的拐点：LangGraph / AutoGen / CrewAI / AFlow / TDP / DynTaskMAS 都在往 graph 结构靠，但各家都只解决局部问题（LangGraph 要灵活，TDP 要 context 隔离，DynTaskMAS 要并行）。此时缺一个 能把这些系统放在同一尺度上比较的理论框架——这就是本文的时机位。它不是一个新系统，而是一个 命名和坐标系，相当于把 "为什么 Agent Loop 不够用" 从工程直觉升格为 $|\mathcal{U}|\le1$ 的形式化命题。

约束推导 (Constraint Derivation) #

作者实质上在做一个 "为什么不可 X" 的穷举：

• 为何不可继续用 Agent Loop？ $|\mathcal{U}|\le 1$，无法表达并行、无法保证 dependency、recovery 由 LLM 自由决定导致 failure loop（survey 中 Agent Loop 项目普遍无 recovery 上限）。
• 为何不可用 LangGraph/AFlow 这种动态图？ 动态图允许 runtime add_node/add_edge，plan mid-execution 就被改写，audit trail 变成移动目标。survey 观察到 versioned-history 系统调试成功率显著更高，即使作者承认 κ 低。
• 为何不可支持 first_of 竞争性并行？ 两个原因：(a) loser cancellation 需要 compensation protocol 回滚副作用，引入新失败模式；(b) commit-point 歧义——A 先成功但 B 可能质量更高，语义不明确。
• 为何不可递归子图展开？ $|V|$ 无界，ready set 不可预测，违反 bounded termination。
• 为何不可 parent-chain rollback？ 违反 plan invariant（immutable within version）。

这些约束最终 "挤" 出了 SGH 的设计空间：静态 DAG + all_of/any_of + 三级 recovery + plan versioning。每个排除都映射到某条原则，不是任意选择。

可行性矩阵（简化版，基于论文 Table 6/7）：

Approach	Multi-ready	Deterministic $\mathcal{P}$	Bounded recovery	Immutable plan	LLM-aware
Agent Loop	✗	✗	✗	✗	✗ (隐式)
Plan-and-Act	✗	✗	✗	部分	部分
TDP	✗	✗	✗	mutable	部分
LangGraph	✓	semi	✗	mutable	部分
Airflow/Luigi/Prefect	✓	✓	✓	✓	✗
SGH	✓	✓	✓	✓	✓

SGH 是唯一同时满足五列的位置。

破局 (Insight) #

"Agent Loop 不是一种特别的架构，它就是 $|\mathcal{U}|=1$ 的一种 scheduler"——这个 reframing 是全文的 aha moment。一旦换上 scheduler 视角，经典 DAG scheduling 半个世纪的积累（list scheduling、Kahn 拓扑、HEFT、critical path、2-1/m 近似比）立刻可以被复用到 agent 执行上。类比：相当于有人指出 "你们讨论的并不是'agent怎么思考'，而是'下一个该执行哪个单元'——这本质是一个 OS scheduler 问题，而你们把它交给了一个 opaque 的 LLM。"

核心技术壁垒 (Core Technical Barrier) #

全文最硬核的一块不是 DAG 本身（这是 1960 年代的东西），而是 "在非确定 LLM 节点 + contract 验证不可靠"这两个约束下，如何仍然证明 bounded termination 和 conditional soundness。Theorem 6.2 的证明思路是：每个节点有 $\tau_v$ 超时 + $b_v$ 重试预算 + terminal state 绝对不可逆，把无限循环的可能性结构化地关进了 $\sum_v \tau_v\cdot(b_v+1) + \sum T_{\text{human}}$ 这个上界。Theorem 6.3 的 validation gap $\Pr\ge \prod p_v$ 则诚实地把 "contract 验证错误" 这个通常被业界忽略的失败模式显式写进了正确性 bound 里。这个 "bounded termination 可证 + validation gap 公开" 的组合，是把 SGH 和那些只在 README 写 "we handle retries" 的 graph 框架区分开的核心壁垒。

质疑假设 (Challenge Assumptions) #

• 假设 1：planner 能识别任务的并行结构。作者自己在 §9.3 坦白 30-40% 任务才有 "natural parallelism"，其余 60-70% 是线性链。这意味着 $G_{\text{graph}}$ 在一般 workload 上可能远小于作者暗示的水平。笔者也不是十分确定 作者估计 30-40% 这个数字本身——这基于 70 个仓库的人工看（κ=0.84），仓库集合本身有选择偏差（偏向 coding agent）。
• 假设 2：plan-version immutable 是可审计性的必要条件。实际上 event sourcing + append-only log 也能做到 "mutable plan + full audit"，只是需要额外存储。作者排除 mutable plan 更像是工程取舍而非理论必然。
• 假设 3：all_of / any_of 足以覆盖工程任务。作者在 §9.9 自己承认 report 节点的 all_of 过度序列化；实际上 LLM agent 面对的很多场景天然是 streaming / incremental 的，DAG 粒度无法轻易表达。
• 假设 4：contract validation 可独立做好。syntactic 验证 $p_v\approx 1$ 没问题，但 semantic 验证其实也是 LLM 在做——用一个 LLM 验证另一个 LLM 的输出，independence 假设可能不成立。

设计绑定批判 (Design Binding Critique) #

SGH 强制绑定了以下前提：

1. 任务依赖可在规划时完全枚举——violates 则必须走 Level 3 replan，成本极高。
2. 存在可靠的 contract 语言（JSON schema + semantic checker）——没有 schema 的任务（如 "写一段有趣的故事"）无法被 SGH 保护。
3. 副作用可分类——Principle 4 依赖 side-effect level，但现实中 tool 的副作用往往模糊（一个 run_shell 可以 read-only 也可以 rm -rf）。
4. 存在一个比 executor 更强的 planner——planner 必须强到能识别并行，否则 SGH 退化。这和 "用弱模型做 executor + 强模型做 planner" 的成本优化思路冲突。

如果任务是长期 open-ended（比如 autonomous research），上面任何一条都不成立，SGH 不适用。

拆解 (Deconstruction) #

一个任务在 SGH 下的完整生命周期：

1. Planner Layer 接收 task intent，生成静态 DAG $\Pi=(\text{id}, \text{version}, V, E, \sigma, \kappa)$，附带每节点 config（action、retry policy、side-effect level）和 plan-level output contract。
2. DAG Validation：检查 acyclicity (Kahn)、reachability、join consistency (any_of 必须有 $\ge 2$ 候选)、contract well-formedness、side-effect consistency。
3. Runtime Layer 开始迭代：计算 $\mathcal{U}(\mathcal{S})=\{v\mid s_v=\text{ready}\land \forall(u,v)\in E: s_u=\text{executed}\}$。
4. 用确定性策略 $\mathcal{P}$（默认拓扑顺序）并发分发所有 ready 节点，每节点 pending → ready → running。
5. 节点执行完毕，contract validation $\kappa_v$ 通过则 running → executed，否则 running → failed_retryable 或 failed。
6. Recovery Layer 收到 failure report：先查 recovery_state[v]；pristine 时只允许 attempt_retry，retried 后才能 attempt_patch，patched 后才能 request_replan——跳级在 API 边界被直接拒绝。
7. 所有节点 terminal 后，plan version 完成。若触发 replan，生成 new plan version $v+1$，旧状态保留在 $\mathcal{C}_{\text{diag}}$ 里。

实践上下文 (Deployment Context) #

• 最适合：software engineering agent（bug fix、feature impl、code review）、data analysis pipeline（query → transform → report）、ops 场景（incident response）。这些任务的依赖可以 upfront 讲清楚。
• 不适合：deep research agent（结构是 emergent 的）、creative writing、open-ended 探索、根据中间 observation 才能决定下一步的调试。
• 服务栈位置：SGH 是 agent runtime 层，下面套 vLLM/SGLang/TRT-LLM 这种 LLM serving，上面可以是 AutoGen/LangChain 这种 app framework。它替代的是 AgentExecutor / LangGraph 这层。
• 硬件偏好：多 ready 单元并发执行意味着 serving 侧要吃 prefix cache（节点间共享 system prompt）、continuous batching、function calling 结构化输出。不对 GPU 架构有特殊要求。

生态影响追踪 (Ecosystem Influence) #

这篇是 2026-04 的 position paper，暂无下游采用记录。它的潜在影响路径有两条：(1) 作为学术语言被后续 graph agent 论文引用，把 "scheduler continuum" 变成标准坐标；(2) 作为工程参考，被 Claude Code / Codex / Devin 这些需要可审计性的 coding agent 借鉴 "plan versioning + three-level recovery"。值得关注的是作者自己指出的 companion paper（Evolutionary Graph Architecture），如果出来会是真正的实验验证。

---

1. Agent Architecture #

• Agent type: single agent runtime，但 planner / executor / recovery 是三个独立 "component layer"（不是多 agent，只是责任分层）。
• Core loop: 不是 ReAct 也不是 plan-then-execute，是 plan-commit-then-dispatch——生成 immutable DAG → 拓扑调度 → 失败按三级升级。
• Memory mechanism: 严格的 $\mathcal{C}_{\text{exec}} \cap \mathcal{C}_{\text{diag}}=\emptyset$ 分区。执行 context 只含输入、可见 artifact、runtime state、budget；diagnostic context 只给 recovery 层，含失败历史、planner annotation、旧 plan version。论文的洞察是：用失败历史做下一步输入是 agent 失败的根源，因为它把 recovery 决策和 execution 逻辑耦合了。
• Tool use protocol: 每个节点包一个 tool call（LLM inference、function call、code exec），节点 output 必须满足 contract $\kappa_v$。Contract 默认是 JSON schema + field 存在 + 类型 check 这种 syntactic；semantic check 建议用 test suite 或另一次 LLM call。
• When to use tools: 不由 LLM 决定——由 DAG 结构决定。节点被规划时就绑定了 action，runtime 不允许偏离。这是和 ReAct 最本质的区别。

Figure 1: Motivating example — bug-fix DAG #



What it shows: 一个 Python bug fix 任务被分解为 10 个节点的 DAG：search_auth / search_utils 并行（蓝色 wave 1），各自触发 read_auth / read_utils 并行（绿色），汇合到 analyze，再扇出到 fix_A / fix_B / update_docs 三路并行，fix_A / fix_B 用 any_of join 接到 run_tests，最后 run_tests 和 update_docs 用 all_of 接到 report。

Why it matters: 这是全文唯一的 "soul diagram"。它同时展示了三个 SGH 核心能力——structural parallelism（搜/读两波并行，$|\mathcal{U}|=2$ / $3$）、alternative paths（any_of 让 fix_A/fix_B 任一成功即可，不用无脑重试）、explicit all_of dependency（analyze 必须等两个 read 都完成）。作者把同一任务在 Agent Loop 下跑成 11 轮串行，在 SGH 下跑成 6 个 scheduling round，直接把 "graph gain" 可视化出来。

Detailed description: 两个入口节点 search_auth / search_utils 无 predecessor。它们分别连接到 read_auth / read_utils，形成两条独立链。两条链在 analyze 用 all_of 合流。analyze 扇出到 fix_A / fix_B（都标 any_of——论文意思是它们是 run_tests 的 any_of candidates，不是 analyze 的子节点语义），同时扇出到 update_docs。fix_A / fix_B 的 any_of 边汇合到 run_tests，run_tests 和 update_docs 的 all_of 汇合到 report。论文标注了两次 $|\mathcal{U}|$ 扩张：第一波 searches 并行 ($|\mathcal{U}|=2$)，第二波 fix+docs 并行 ($|\mathcal{U}|=3$)。

2. Planning & Reasoning #

• Planning granularity: 节点级 DAG。作者承认 granularity 本身是 "the planner 必须平衡的设计决策"——粒度太粗丢失并行（under-decomposition），太细引入 serialization overhead（over-decomposition）。
• Backtrack / revise: 显式禁止 mid-execution plan modification。任何结构变化必须走 Level 3 replan 生成 plan version $v+1$，旧 version 的 trace 完整保留。
• Reasoning approach: 论文不规定 planner 内部用什么；建议可以是 LLM、template、hybrid。重点是 planner 输出要通过 DAG validation（acyclicity + reachability + join consistency + contract well-formedness + side-effect consistency）。
• Ambiguity handling: 不处理。SGH 假设 task 的 dependency 可 upfront 枚举；若不能，作者明确让用户选 LangGraph 这种 dynamic system（§9.7）。
• Plan quality evaluation: 通过 $G_{\text{plan}}=\text{Perf}(\text{G2})-\text{Perf}(\text{G1})$ 间接度量——把 "有 planner 无 graph" 和 "无 planner" 对比。但论文无实验数据。

3. Tool & Environment Interface #

• Tools: paper-agnostic，任意 tool。每 node 通过 NodeConfig 绑定一个 action。
• Tool description format: NodeConfig + 输出 contract $\kappa_v$。Contract 建议 JSON schema + validation rule。
• Error handling: 三级升级协议，见下面 Figure 4。
• Environment: 静态 DAG 内部。tool 是否幂等由 node 的 side-effect level 标记，高副作用不能 speculative 并行。
• Sandboxing: 靠 side_effect_level 和 waiting_human 状态。高副作用节点可要求人工审批，超时 $T_{\text{human}}$ 自动 cancel。

4. LLM Backbone Requirements #

• Base model: 不规定，G0 baseline 建议 GPT-4 / Claude 3.5 级别。planner 对 "能识别并行" 有较高要求——作者估计 WorfBench 显示 sequence-vs-graph planning gap 15% (§2.5)，所以 planner model 要强。
• Fine-tuning: 不需要特殊 SFT/RL。Contract validation 对 structured output 的稳定性要求高，所以 function calling / JSON mode 必须可靠。
• Prompt format: planner 的 prompt 决定了 DAG 质量，但论文不提供具体 template。
• Context window: 显著短于 Agent Loop，因为每个节点只看 $\mathcal{C}_{\text{exec}}$（inputs + visible artifacts），失败历史被隔离在 $\mathcal{C}_{\text{diag}}$ 里不进入 prompt。这是对长 context 消耗的直接优化——TDP 报告过 82% token 削减（§2.2），SGH 继承这个思路。
• Latency: 多 ready 单元并发 → 在相同 wall-clock 内调用更多 LLM 请求 → 对 serving 侧的并发能力要求高。

5. Evaluation #

• Benchmarks: 无。论文是 position paper，只设计了 7 组对照 protocol，未执行。
• Metrics（protocol 里定义的）: Success rate、wall-clock time、token cost、node count、recovery action count、plan version count。
• Baseline comparisons（protocol 里定义的）:
• G0: SOTA Loop（Claude Code / Codex agent mode）
• G1: Naive Loop（单步 LLM、无 planner）
• G2: Planner Loop
• G3: Structured Loop（scaffold, $|\mathcal{U}|=1$）
• G4: GH-Core（$|\mathcal{U}|\ge 1$, 无 recovery）
• G5: GH+Patch（Level 1+2 recovery）
• G6: GH+Replan（Level 1+2+3 recovery）
• Failure analysis: 论文 §3.7 列了 planning 失败的 5 种模式：missing dep / spurious dep / incorrect branch selection / over-decomp / under-decomp。前两种 runtime 能捕获（contract violation），后三种只能靠 replan。
• Human evaluation: 不涉及。

Figure 2: The scheduler continuum #



What it shows: 从左到右排列 5 种 agent 执行范式——Naive Loop → Parallel Loop → Planner Loop → Structured Loop → Graph Harness。每种标注 $|\mathcal{U}|$ 和 policy 类型。

Why it matters: 这张图是 "scheduler continuum" 理论的视觉载体，也是作者最想传播的概念图。它把 Agent Loop（1-ready，non-det）、parallel tool calls（$\ge 1$-ready 但 non-det）、加 planner / scaffold 的系统（仍然 1-ready）、和真正的 SGH（$\ge 1$-ready + det）放在同一条轴上，让读者一眼看出：加 planner、加 scaffold 只在 policy 轴上前进，只有真正的 graph 才能跨进多 ready 单元的象限。这直接支撑了 §3.4 的核心论点。

Detailed description: 图中 5 个方块横向排列，下方标注 "Policy explicitness and determinism" 方向。左起：Naive Loop（$|\mathcal{U}|=1$, Non-det, Sequential）、Parallel Loop（$|\mathcal{U}|\ge 1$, Non-det, Parallel calls）、Planner Loop（$|\mathcal{U}|=1$, Non-det, Planner）、Structured Loop（$|\mathcal{U}|=1$, Semi-det, Scaffold）、Graph Harness（$|\mathcal{U}|\ge 1$, Det, Graph）。注意 Parallel Loop（OpenAI tool_calls）被单列出来，强调它虽然并行但策略仍不显式。

6. Multi-Agent #

N/A — SGH 是 single-agent runtime 架构，只是把 planner / executor / recovery 三个 role 分层而已。论文 §2.3 讨论过 AutoGen / CrewAI 的 multi-agent，但作者归类它们为 $|\mathcal{U}|=1$ 或 semi，并认为 multi-agent 本质上仍可以被 scheduler 框架描述——"agent count" 不是 SGH 关心的轴。

7. Infrastructure Impact #

Layer	影响
Algorithm	不直接涉及训练。间接：plan-version trace 可作为高质量 agent SFT/RL 数据格式。
Kernel	不涉及。多 ready 并发对 serving 侧意味着要吃 prefix cache（节点间共享 system prompt）、continuous batching。
Framework	核心影响层。serving 需要把每个 node 看成独立 request，且支持 plan-level 共享 prefix；agent framework 需要提供 DAG validator、state machine 实现、recovery 升级状态机、append-only WAL、token-bucket rate limiter。
LLM	对 function calling / JSON mode / structured output 的稳定性要求高，因为 contract validation 直接决定 retry 行为。模型规模上 planner ≫ executor 是自然的分层。
Cost	相比 Agent Loop：token 消耗因 context 隔离而降低（参照 TDP 82% 削减），但节点数多 + 并发 LLM 调用 → peak QPS 更高、总 tokens 不一定少。对 task-level 成本的影响是任务依赖的。

8. Production Readiness #

• Reliability: 论文无数据。理论上 bounded termination（Theorem 6.2）保证 $\le\sum_v \tau_v(b_v+1)$ 时间终止；failure-loop 被 Level 3 replan 上限阻断。
• Safety: Principle 4 强制 side-effect classification；high side-effect node 不能 speculative 并行，可走 waiting_human 状态做审批。
• Observability: plan version + append-only WAL + diagnostic context 三件套。作者宣称这是 Graph Harness 相对 LangGraph 的最大实用优势——"failure attribution via plan-version-audited traces"（Table 2）。
• Scalability: §9.10 列了具体实现路径——incremental ready-set 更新 O(|E_new|)、token-bucket rate limiting、WAL 持久化、Raft/Paxos leader election。作者估算生产级实现 3300-6500 LOC，是 Airflow (50K+) 的 1/10。

Figure 3: Three-layer separation #



What it shows: planner / runtime / recovery 三层的接口关系：planner 产出 $\Pi$ 给 runtime，runtime 执行不改 $\Pi$，failure 往上报到 recovery，recovery 决定 recovery action 或 request_replan 回到 planner。

Why it matters: 这张图把 Principle 2（stable commitment）变成一张架构图。读者能立刻看出：runtime 不接触 plan 结构，只消费；recovery 不接触 runtime 内部，只看 failure report 和 diagnostic context；planner 不接触 runtime 实时状态。这是 SGH 相对 LangGraph（runtime 可改图）、TDP（planner 可动态加 task）的本质区别。

Detailed description: 三个矩形垂直排列——顶部 Planner Layer（generates $\Pi$）、中部 Runtime Layer（executes $\Pi$ without modification）、底部 Recovery Layer（diagnoses failures, selects recovery action）。三条有向边：Planner → Runtime 传 $\Pi$；Runtime → Recovery 传 failure report；Recovery → Planner 传 "request replan" 请求（仅在 Level 3 时触发）。关键是 Runtime → Planner 没有直接边——runtime 不能把中间结果 push 回 planner 做动态 replan。

9. Impact on AI Infra #

• 长期 stateful 会话：SGH 把 agent execution 变成一个 plan-version-scoped 的长会话，对 serving 层来说意味着要支持 plan-level KV cache 复用 + 多 node 并发调度。普通 LLM serving 假设 request 独立，SGH 打破了这个假设。
• 对模型能力的推动：planner 的质量直接决定 $G_{\text{graph}}$，所以会推动 "planning-specialized" 模型（类似 o1-preview / DeepSeek-R1 的 reasoning traces）被用作 planner layer。
• 对 serving 的新要求：不仅要高吞吐，还要支持 heterogeneous concurrency（同一 plan 内不同 node 可能跑不同 model / tool），这和现在按 model-id 分 serving pool 的做法需要抽象统一。
• 基础设施蓝图：论文 §9.10 给出的清单（incremental scheduler + WAL + Raft + rate limiter）其实就是一个 "agent runtime OS" 的雏形，未来可能会形成类似 Airflow / Temporal 但 LLM-native 的独立 category。

Figure 4: Node state machine #



What it shows: 10 个状态的节点状态机，4 个 terminal 态 {executed, failed, cancelled, skipped} 用灰色标注；转移边标注 trigger 条件（deps met / dispatch / success / timeout / retry / exhausted / dep lost / sibling done / transient err / structural err）。

Why it matters: 这是 SGH termination 证明的基石。Theorem 6.2 的证明完全基于这张图的结构——terminal state 无出边（absorbing）+ 每个非 terminal 态必有一条通往 terminal 的路径 + $\tau_v$/$b_v$ 有限。如果这张图里任何一个 terminal 态加了出边，bounded termination 就破。论文把这张图当作 "formal object" 来证明，而不仅仅作图示。

Detailed description: 节点初始 pending → 条件 deps met → ready → 条件 dispatch（被 $\mathcal{P}$ 选中）→ running。running 有 4 条出边：success → executed（terminal，但被 contract validation 守护）；transient err → failed_retryable（budget>0 可回到 pending 走新一轮，exhausted 则 → failed）；structural err → failed（terminal）；need human → waiting_human（resume → ready 或 timeout → cancelled）。ready 有 2 条额外出边：dep lost → blocked（→ pending 当 dep 恢复）；sibling done（any_of join）→ skipped（terminal）。failed_retryable 也可因 any_of sibling 完成而 → skipped。

关键细节 #

• Recovery API 是 SGH 可控性的"机械护栏": recovery layer 只暴露 attempt_retry(v) / attempt_patch(v, cfg) / request_replan(reason) 三个入口。每个入口在 API 边界 check recovery_state[v]——跳级调用会被直接拒绝。作者对比 Rust 的 unsafe 块：只要实现尊重 API 边界，invariant 就不可能被违反。
• any_of join 的"loser skip"语义很微妙: 当某个候选成功后，剩余 pending / ready / running / failed_retryable 的 sibling 会被强制转 skipped；已经 terminal 的保留原状态。这避免了做真正的 mid-execution cancellation（会触发 compensation 问题），但代价是 loser 继续跑到自然结束。
• Validation gap 的实用影响: 如果用 LLM 做 semantic validation 且每个节点 $p_v=0.95$，10 个节点链的 $\Pr[\text{all correct}]\ge 0.95^{10}\approx 0.6$——即使所有节点都"通过"，仍有 40% 的隐性错误概率。这解释了为什么 SGH 把 human-in-the-loop (waiting_human) 设计成第一等公民，而不是边缘 feature。

一句话总结 #

Scheduler 视角下，Agent Loop 和 LangGraph 只是 $|\mathcal{U}|$ 轴上的不同点；SGH 用"静态 DAG + 三级 recovery + plan versioning"把 agent 执行从一个 non-det, unbounded, unauditable 的 loop 改造成一个 det, bounded, auditable 的 scheduler，代价是放弃竞争性并行和动态拓扑。