PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Hu Wei

arXiv:2604.11378v1cs.AIeess.SY

TL;DR

The paper addresses structural weaknesses in Agent Loops, where opaque single-step decisions leave dependencies, recovery, and plan history difficult to control. It proposes Structured Graph Harness, an explicit static-DAG design with immutable plan versions and separated planning, execution, and recovery. The paper’s conclusions are theoretical: it supplies a scheduler framework, design analysis, formal guarantees, and a future validation protocol, not empirical evidence.

  • Problem

    Agent Loops rely on opaque single-ready-unit LLM scheduling, causing implicit dependencies, unbounded recovery choices, and mutable execution history that complicates verification and auditing.

  • Method

    Structured Graph Harness represents control flow as an explicit static DAG with immutable plan versions, separated planning, execution, and recovery layers, and strict recovery escalation.

  • Results

    The paper provides a scheduler-theoretic continuum, a 70-system trade-off analysis, a formal node-state model with termination and soundness guarantees, and a seven-group experimental protocol.

  • Takeaways & Limitations

    The design trades competitive parallelism, recursive expansion, and parent-chain rollback for greater controllability, verifiability, and implementability.

  • Takeaways & Limitations

    The proposed benefits remain theoretical because the paper provides no experimental validation, and the static-DAG assumption does not fit exploratory, dynamically evolving, or creative tasks.

Abstract

from arXiv · show

The dominant paradigm for building LLM based agents is the Agent Loop, an iterative cycle where a single language model decides what to do next by reading an ever growing context window. This paradigm has three structural weaknesses: implicit dependencies between steps, unbounded recovery loops, and mutable execution history that complicates debugging. We characterize the Agent Loop as a single ready unit scheduler: at any moment, at most one executable unit is active, and the choice of which unit to activate comes from opaque LLM inference rather than an inspectable policy. This perspective places Agent Loops and graph based execution engines on a single semantic continuum. We propose SGH, Structured Graph Harness, which lifts control flow from implicit context into an explicit static DAG. SGH makes three commitments: execution plans are immutable within a plan version, planning execution and recovery are separated into three layers, and recovery follows a strict escalation protocol. These choices trade some expressiveness for controllability, verifiability, and implementability. Our contributions are fourfold: a scheduler unified framework that applies classical scheduling theory to LLM agent execution and identifies challenges introduced by non deterministic LLM nodes; a trade off analysis of controllability, expressiveness, and implementability across 70 surveyed systems; a formal specification including a node state machine with termination and soundness guarantees; and an attributable experimental framework with a seven group design for future validation. This is a position paper and design proposal. We provide a theoretical framework, design analysis, and experimental protocol, not a production implementation or empirical results.

1 Introduction

The paper argues that Agent Loops conceal dependencies, recovery, and plan changes inside opaque single-step LLM decisions. It proposes Graph Harness as an explicit DAG-based design that improves inspectability and bounded control while sacrificing some expressiveness.

  • Motivation: 60% of surveyed open-source projects—42 of 70—adopt the Agent Loop pattern, while recent variants still leave control flow implicit and execution without a stable commitment.The survey result motivates treating the weaknesses as structural rather than exceptional.
  • Motivation: Agent Loops use a single opaque LLM decision to select each next unit, leaving dependencies implicit and execution policy difficult to inspect.The framework characterizes this as single-ready-unit scheduling and contrasts it with graph executors that can expose multiple eligible units.
  • Proposed design: Graph Harness lifts control flow into a static DAG with immutable plan versions, separate planning, execution, and recovery layers, and bounded recovery escalation.These commitments make dependencies, dispatch structure, and recovery behavior explicit rather than context-dependent.
  • Framework: The scheduler-theoretic framework compares agent systems by ready-set cardinality and policy explicitness, applying classical scheduling concepts while identifying nondeterministic LLM outputs and reasoning errors as additional challenges.The paper builds on classical DAG scheduling literature [Topcuoglu et al., 2002, Cormen et al., 2009] but emphasizes LLM-specific validation and reasoning problems.
  • Analysis and evaluation plan: The design analysis surveys 70 systems to examine trade-offs among controllability, expressiveness, and implementability, including the prevalence of failure loops in graph/flow systems.The paper also proposes a seven-group protocol to isolate design decisions, but the experiments remain future work.
  • Motivating example: The motivating DAG can dispatch independent searches and reads in parallel, but its benefits require correct planning, fully known dependencies, and correct node execution.The example reports six scheduling rounds for Graph Harness versus eleven serial turns for an Agent Loop under ideal conditions.

2 Related Work

Related systems increasingly structure LLM-agent coordination through graphs, scoped contexts, or workflow abstractions, but they differ in scheduling explicitness, runtime flexibility, and recovery guarantees. Graph Harness combines scheduler-theoretic analysis with deterministic multi-ready-unit scheduling, immutable plan versions, bounded recovery, and mechanisms for nondeterministic LLM nodes.

  • Agent Loop Paradigm: The scheduler-theoretic framework formalizes expressiveness–controllability trade-offs using ready-set cardinality and policy explicitness, applying classical scheduling ideas to LLM execution.The contribution is the application of scheduling theory to nondeterministic LLM nodes rather than a new classical DAG scheduler.
  • Plan-Then-Execute and Separated Architectures: TDP isolates sub-goal execution histories in scoped contexts and reports up to 82% lower token consumption, but remains a single-ready-unit scheduler in this framework.Graph Harness instead makes the plan itself a scheduling structure with multiple simultaneously dispatchable units.
  • Graph-Based Agent Orchestration: LangGraph prioritizes runtime flexibility and dynamic restructuring, while Graph Harness prioritizes verifiable traces and bounded failure handling for workflows whose dependencies can be articulated beforehand.The paper presents these as complementary design points rather than an empirical performance ranking.
  • Graph-Based Agent Orchestration: The framework deliberately restricts expressiveness, including dynamic topology and recursive expansion, to maximize controllability and verifiability.This design fixes topology for a plan version and excludes tasks requiring runtime structural adaptation.
  • Classical DAG Scheduling: Graph Harness addresses LLM-specific execution challenges through contract-based validation, recovery for reasoning failures, and side-effect-aware bounded retries.Unlike classical workflow engines, LLM nodes can hallucinate or misinterpret inputs, produce different outputs across invocations, and require validation beyond compile-time type checks.
  • Graph-Based Agent Orchestration: Graph Harness combines multi-ready-unit scheduling, deterministic policy, immutable plan versions, and bounded recovery, whereas prior systems generally provide these properties only in isolation.LangGraph provides multi-ready-unit scheduling without guaranteed plan immutability or bounded recovery, while TDP remains single-ready-unit and lacks escalation invariants.

3 A Scheduler-Unified Framework

The framework models LLM agent execution as scheduling systems distinguished by ready-set cardinality, policy explicitness, and determinism. It classifies Agent Loops and graph executors on this continuum and proposes testable but currently unvalidated predictions about parallel scheduling and recovery.

  • Execution-system model: Execution systems are formalized as tuples whose state, ready-set function, policy, outcomes, and transitions describe how executable units become eligible, selected, and updated.A node is ready when it is marked ready and all predecessors have executed; transitions recompute the ready set after success or failure.
  • Single-ready-unit schedulers: An Agent Loop is a non-deterministic single-ready-unit scheduler: each step exposes one action, while identical contexts may yield different actions.When |U| ≤1, scheduling choice is effectively delegated to the process producing the next unit, namely LLM inference.
  • Multi-ready-unit schedulers: Multi-ready-unit schedulers have states with |U| > 1, making policy a genuine design choice among ordering, priority, and parallel-dispatch strategies.Graph-based executors operate in this regime, where different policies can produce different traces from the same ready set.
  • Scheduler continuum: The scheduler continuum varies along ready-set cardinality, policy explicitness, and policy determinism, providing an analytical classification rather than a theorem.Planner augmentation can increase policy explicitness without changing ready-set cardinality; graph execution reaches the multi-ready-unit regime.
  • Theoretical predictions: The framework predicts benefits from multi-ready-unit scheduling, greater gains as task complexity increases, and recovery benefits mainly on failure-prone tasks.These predictions are proposed as falsifiable guidance for future experiments, not as empirically established results.

3.5 Why Unification Matters

The scheduler framework makes agent systems comparable through ready-set size and policy characteristics, while the worked example shows how explicit graph structure adds parallelism, alternatives, bounded recovery, and auditability. The paper presents these as framework implications and illustrative behavior, not empirical validation.

  • Analytical benefits: The framework compares Agent Loops and graph executors by asking whether deterministic multi-ready-unit scheduling improves performance and by how much.It characterizes expressiveness through available ready-set configurations and controllability through explicit state and a functional policy.
  • Concrete execution comparison: In the motivating task, Graph Harness exposes independent searches, reads, and fix/documentation work for parallel dispatch, whereas the Agent Loop processes them sequentially.The DAG contains independent search nodes, alternative patches, and parallelizable documentation and fix/test paths.
  • Concrete execution comparison: The alternative-patch join makes “try either patch” structural: after Fix A fails, successful Fix B satisfies the dependency and prevents a wasted retry.This behavior also enables bounded recovery and records the failure, success, and skip in the audit trail.
  • Concrete execution comparison: Graph execution enforces dependencies structurally, so analysis waits for both file reads, while plan-versioned state transitions provide an audit trail absent from the mutable Agent Loop history.The example contrasts DAG-computed readiness and recorded plan versions with context-dependent ordering and implicit plan revision.
  • Step-count comparison: The example requires 11 sequential Agent Loop turns but 10 Graph Harness node dispatches across 6 scheduling rounds, including 4 rounds with parallel dispatch.The passage states that wall-clock time is reduced proportionally to available parallelism.

3.7 Planning Failures and Their Consequences

Planning errors can violate dependencies, waste parallelism, trigger unnecessary recovery, or inflate execution overhead. Graph Harness detects some failures through validation and recovery, but several planning mistakes require a new plan version.

  • Dependency errors: Missing dependencies cause incomplete inputs and contract-validation failures when dependent nodes execute before required results exist.The recovery protocol is triggered rather than allowing the system to proceed silently.
  • Dependency errors: Spurious dependencies reduce ready-set cardinality and eliminate valid parallelism, wasting time without necessarily compromising correctness.An unnecessary edge can reduce |U| from 2 to 1, turning independent work into sequential execution.
  • Branch selection: Incorrect join semantics can force repeated retries and escalation when a task needs any successful branch but the plan requires all branches.A wrong all-of join for patch selection may repeatedly retry an infeasible patch before escalating to patch generation and replanning.
  • Granularity: Over-decomposition adds node, serialization, and coordination overhead, while under-decomposition hides parallelism and makes error attribution harder.Graph Harness cannot automatically merge over-decomposed nodes or recover under-decomposed parallelism without replanning.
  • Planning failures: Graph Harness combines structural validation, contract validation, and recovery replanning, but cannot correct every planning error without a new plan version.Structural validation catches cycles, unreachable nodes, and inconsistent joins; contract validation catches missing dependencies and incorrect inputs.
  • Scheduler behavior: The worked example reaches ready-set cardinalities of 2 and 3, uses an any-of join to cancel the losing patch, and avoids recovery when one patch succeeds.Scheduling is determined by DAG topology and node states rather than LLM inference.

4 Design Principles and Trade-offs

The design prioritizes controllability and verifiability for tasks whose dependency structure can be specified in advance, accepting reduced expressiveness and flexibility. Survey observations motivate immutable plans, bounded recovery, and side-effect-aware scheduling.

  • Trade-offs: Across 70 surveyed systems, graph and flow frameworks showed high expressiveness but low controllability and high implementation risk, whereas Agent Loops were easy to implement but lacked structural guarantees.The survey’s categories are summarized in Table 7, with approximate percentages and sensitivity analysis within ±10%.
  • Principle 1: Controllability First: Graph Harness targets high controllability for verifiable engineering tasks rather than the expressiveness frontier.The design prioritizes predictability and verifiability when benefits are uncertain.
  • Principle 1: Controllability First: Graph Harness excludes competitive parallelism, recursive expansion, and parent-chain rollback because these features introduce nondeterminism into scheduling or state transitions.These restrictions define an expressiveness boundary for the target task class rather than a universal boundary.
  • Principle 2: Stable Commitment: Immutable plans and versioned history support attribution, predictability, and pre-execution verification, but dynamic structural changes require a new plan version.The paper reports more reliable reconstruction of execution history for versioned-history systems, while noting that this observation is qualitative and may not generalize.
  • Principle 3: Bounded Recovery: Bounded recovery uses explicit triggers, bounded scope, and strict escalation to prevent both infinite retries and premature replanning.Recovery proceeds from retry to patch to replan, and lower-level options must be exhausted before escalation.
  • Principle 4: Side Effects: Side-effect classification imposes stricter scheduling and retry constraints on writes, deletions, and notifications, reducing parallelism while avoiding safety violations.Read-only operations can be retried more freely than high-impact operations.

5 Execution Commitment and the Static Graph Model

Graph Harness treats an execution plan as an immutable static DAG and separates planning, execution, and recovery into distinct layers. This structure makes scheduling, validation, attribution, and auditability inspectable before and during execution.

  • The Execution Plan as Commitment: An execution plan consists of nodes, directed edges, node configurations, and an output contract, with its topology fixed for each plan version.A new topology can arise only through a controlled replan that creates the next plan version.
  • The Execution Plan as Commitment: The immutable plan invariant makes execution traces attributable, ready sets predictable, and plans verifiable before execution begins.Validation can check cycles, unreachable nodes, and unsatisfiable dependency constraints without mid-execution structural changes.
  • Static Graph Model: A static DAG guarantees acyclicity, finite execution, and topological scheduling for the target task class.Acyclicity prevents circular dependencies, fixed node count bounds execution steps, and topological order constrains scheduling.
  • Three-Layer Separation: The planner produces a validated DAG, the runtime executes it without modifying its topology, and the recovery layer diagnoses failures and selects actions independently.The runtime computes ready sets and records observations but does not decide how failures are handled.
  • Context Partition: Execution and diagnostic contexts are disjoint during node execution, preventing failure history from becoming implicit input to later execution steps.Diagnostic information can enter execution only through a new plan version produced by the planner.

6 Node State Machine and Recovery Protocol

The node state machine and bounded recovery protocol provide progress, termination, contract enforcement, and controlled escalation under explicit assumptions. Reliability remains conditional on the correctness of validation, especially for semantic or LLM-based checks.

  • Termination and Progress: A finite DAG with bounded execution guarantees that some node can either become ready or transition to a terminal state whenever non-terminal work remains.Acyclicity prevents deadlock cycles among blocked nodes.
  • Termination and Progress: Under a finite valid DAG, finite timeouts, and bounded retry budgets, Graph Harness terminates with probability 1 and every node reaches a terminal state.The guarantee relies on bounded execution, finite node count, state transitions, and terminal-state stability.
  • State Machine: Contract validation guards the transition to executed, so outputs that fail their contract instead become retryable failures or terminal failures.This enforces output-contract satisfaction by construction at the state-machine level.
  • Conditional Soundness: The system’s correctness is bounded by validation reliability: syntactic checks are highly reliable, while semantic and LLM-based validation can have substantially lower reliability.Under independent validation errors, the probability that all outputs are truly correct is bounded by the product of per-node validation reliabilities.
  • Conditional Soundness: Side-effect classification, human review, and downstream contract checks mitigate—but do not eliminate—the validation gap.The validation gap is an inherent limit of LLM-based execution systems.
  • Recovery Protocol: Recovery follows a strict three-level escalation order, requiring lower-level actions to be exhausted before patching or replanning.The invariant makes full replanning the last and most disruptive recovery option.

7 Join Semantics and Scheduling Constraints

Graph Harness defines explicit all-of and any-of joins for static-DAG scheduling, while excluding first-of joins to preserve controllability and avoid complex cancellation semantics.

  • All-of Join: All-of joins enter the ready set only after every predecessor reaches terminal success, keeping dependency satisfaction explicit.A successor remains pending between the first and second predecessor completions.
  • Any-of Join: Any-of joins dispatch eligible candidates in deterministic order, make the successor ready after the first success, and skip remaining candidates.If all candidates terminate unsuccessfully, the join fails.
  • Excluded First-of Join: First-of joins are excluded because loser cancellation requires compensation protocols, commit points are ambiguous, and ready sets become nondeterministic.Such mechanisms are possible but add substantial implementation complexity and new failure modes.
  • Expressiveness Boundary: The supported joins define Graph Harness’s expressiveness boundary within a static DAG.The boundary can be expanded only by explicitly relaxing design principles and accepting controllability trade-offs.

8 Attributable Experimental Framework

The framework proposes seven controlled groups that isolate planning, scaffolding, graph scheduling, patch recovery, and replanning gains, but reports a protocol for future validation rather than completed experiments.

  • Scope: The paper provides an experimental protocol, not completed empirical results; validating its predictions requires a prototype and curated benchmarks.The stated contribution is theoretical and methodological rather than empirical validation.
  • Experimental Design: Seven experimental groups isolate each design contribution by comparing adjacent configurations along the scheduler continuum.The design includes an augmented-Agent-Loop baseline and adds one feature at a time.
  • Controlled Variables: The study holds task set, model, tools, timeout, and token budget constant while measuring success, time, token cost, dispatched nodes, and recovery behavior.It also records plan versions for groups with replanning.
  • Attribution: Adjacent contrasts attribute gains to information, planning, scaffolding, graph scheduling, patch recovery, and replanning, while G6−G0 estimates the combined gain.The graph contrast specifically moves from single-ready-unit to multi-ready-unit scheduling.
  • Metrics and Task Tiers: The framework evaluates effectiveness, efficiency, stability, observability, and attribution across task tiers with different dependency complexity.Simple tasks test whether structural overhead outweighs controllability benefits.
  • Decomposition Limits: The additive gain decomposition may confound structural effects with planning-by-structure interactions, so gains should be estimated across planning-quality levels.Stable Ggraph values across those levels would indicate negligible interaction.

9 Discussion

The discussion presents Graph Harness as a controllability-oriented design for verifiable engineering tasks, with possible parallelism benefits for only a subset of workloads and no empirical validation yet.

  • Scope: Graph Harness is intended for tasks with articulable dependencies and checkable outcomes, rather than as a universal architecture for LLM agents.Exploratory, creative, and dynamically evolving tasks fall outside its stated target class.
  • Parallelism: Approximately 30–40% of surveyed agent tasks showed some natural parallelism, so multi-ready-unit scheduling is expected to help mainly that subset.The estimate comes from manual inspection of 70 open-source projects and remains approximate.
  • Validation Status: The paper’s predictions remain theoretical because no prototype or benchmark experiments have yet validated them.Empirical validation is identified as ongoing future work.
  • Recovery: The three-level recovery protocol turns failure handling from an unbounded LLM choice into a bounded, auditable process.The paper presents this as a formal protocol while acknowledging related escalation patterns in classical fault tolerance.
  • Error Propagation: Static DAGs can propagate planning errors across parallel executions, increasing wasted time and tokens even though contract validation can mitigate incorrect inputs.The balance between parallel efficiency and error-propagation cost is task-dependent and untested.
  • Planner Dependence: Graph Harness makes planner failures observable and attributable but does not guarantee correct plans or strategically optimal decompositions.Independent measurement of Gplan is proposed to separate planning quality from scheduler effects.

10 Limitations

Graph Harness trades broad expressiveness for controllability, introducing boundaries around competitive parallelism, dynamic decomposition, planner dependence, and implementation overhead.

  • Applicability Boundary: Graph Harness excludes open-ended exploration, dynamic goal evolution, and competitive parallel trial-and-error because their dependencies cannot be fully specified in a static DAG.These exclusions define the architecture’s applicability boundary.
  • Competitive Parallelism: First-of semantics are omitted because cancellation and partial-result handling require complex, nonstandard compensation protocols.Conditional nodes can approximate try-all-take-first behavior without cancellation efficiency.
  • Fixed Overhead: On simple 1–3-step tasks, DAG validation, state tracking, and layered recovery may add cost without proportional success-rate improvement.The proposed response is routing simple tasks to a lightweight loop and complex tasks to Graph Harness if experiments confirm H4.
  • LLM Dependence: Although scheduling policy is removed from the LLM, plan generation and failure diagnosis remain LLM-dependent quality bottlenecks.The architecture exposes these failures as auditable plan versions and recovery decisions but does not eliminate them.
  • Future Extensions: Relaxing constraints through speculative execution, recursive expansion, or rollback would increase expressiveness while sacrificing some controllability.The companion evolutionary architecture is proposed to study when such relaxations are safe.

11 Conclusion

Graph Harness unifies LLM agent execution with scheduler theory and makes controllability the organizing design goal. Its explicit commitments and seven-group evaluation protocol define a principled, auditable direction, but validation remains future work.

  • Graph Harness formalizes Agent Loops and graph executors through ready-set cardinality, making their structural differences precise and comparable.Agent Loops have |U| ≤1, whereas graph executors have |U| ≥1.
  • Its four design principles trade expressiveness for predictability, auditability, bounded recovery, and safety.The sacrificed capabilities include competitive parallelism, dynamic plan modification, ad-hoc recovery, and unrestricted dispatch.
  • The proposed experimental framework decomposes performance gains into planning, scaffold, graph, patch, and replan effects for independent hypothesis testing.The protocol can test whether graph structure contributes beyond planning, but only after prototype execution.
  • Graph Harness is deliberately less expressive than unrestricted agent architectures, with each excluded capability tied to an explicit and selectively relaxable design principle.This establishes a transparent expressiveness boundary rather than claiming universal optimality.

A Formal Specifications

The appendix specifies how plans are validated, how node readiness changes under join semantics, and how the 70-project survey was constructed and classified. It also documents representative projects and reproducibility materials.

  • A.1 Complete State Transition Table: The node state-transition specification is provided as a complete table for nodes v ∈ V.The appendix identifies this artifact as Table 15.
  • A.2 DAG Validation Algorithm: Plans are rejected before execution unless they satisfy acyclicity, reachability, join consistency, contract well-formedness, and side-effect consistency checks.A rejected plan requires the planner to generate a corrected plan before execution begins.
  • A.3 Join Semantics: Formal Properties: Under all-of joins, executed predecessors can only preserve or enlarge the ready set, whereas any-of joins may shrink it after one candidate is selected.This captures the difference between requiring every predecessor and accepting one alternative path.
  • A.5 Survey Methodology: Projects were classified by scheduler type, planning, recovery, context management, and implementation complexity, with mixed systems categorized by their execution-layer pattern.Two independent reviewers achieved κ = 0.84, and boundary-project sensitivity changed category percentages by at most ±10%.
  • A.5 Survey Methodology: The classification distinguishes Agent Loop, event-driven, state-machine, graph/flow, and hybrid execution patterns.The operational definitions identify whether dispatch is governed by context inference, external events, explicit states, graph topology, or combinations.
  • A.6 Representative Projects: Nine representative projects span all five categories, multiple languages, application domains, and architectural philosophies, while the complete project list is supplied for reproducibility.Table 16 presents the representative subset, and supplementary material contains the remaining projects and classifications.

A.4 Survey Limitations

The 70-project survey is qualitative evidence rather than quantitative proof because selection and interpretation were not fully objective. Its findings may also fail to generalize beyond the field state observed in April 2026.

  • The survey is not peer-reviewed and should be interpreted as qualitative evidence rather than quantitative proof.This scope boundary applies to the reported survey patterns.
  • Project selection was subjective and not based on systematic sampling.The sampling process therefore limits claims about representativeness.
  • Manual classification of failure loops, debugging success, and related qualitative metrics may vary across reviewers.The authors explicitly note that different reviewers could reach different conclusions.
  • Because the survey reflects the field as of April 2026, its patterns may not generalize to newer systems.The authors identify formalizing the survey with a more rigorous methodology as future work.
Loading 2604.11378v1…