PaperlayerView exact revision on arXiv

Source-linked AI summary

ALAS: Transactional and Dynamic Multi-Agent LLM Planning

Longling Geng, Edward Y. Chang

arXiv:2511.03094v1cs.MA

TL;DR

LLM planners can produce inconsistent, constraint-violating plans and struggle with long-range coordination, reactive updates, persistent state, and non-circular validation. ALAS combines validator-isolated planning, versioned execution logs, localized repair, explicit execution policies, and a canonical IR mapping to ASL and Argo. ALAS shows improved feasibility retention and stable makespan in disruption-aware job-shop scheduling suites (DMU, TA) with runtime perturbations under comparable token and latency budgets.

  • Problem

    LLM planners can produce inconsistent, constraint-violating plans and struggle with long-range coordination, reactive updates, persistent state, and non-circular validation.

  • Method

    ALAS combines validator-isolated planning, versioned execution logs, localized repair, explicit execution policies, and a canonical IR mapping to ASL and Argo.

  • Results

    ALAS shows improved feasibility retention and stable makespan in disruption-aware job-shop scheduling suites (DMU, TA) with runtime perturbations under comparable token and latency budgets.

  • Takeaways & Limitations

    Validator isolation, versioned logs, and localized repair provide a practical reliability design for dynamic multi-agent LLM planning within the evaluated scheduling scope.

  • Takeaways & Limitations

    The evaluated fault model covers transient and logical faults, while resource exhaustion and Byzantine behavior are out of scope.

Abstract

from arXiv · show

Large language models enable flexible multi-agent planning but remain fragile in practice: verification is often circular, state changes are not tracked for repair, and small faults trigger costly global recomputation. We present ALAS, a stateful, disruption-aware framework that separates planning from non-circular validation, records a versioned execution log for grounded checks and restore points, and performs localized repair that preserves work in progress. The validator operates independently of the planning LLM with fresh, bounded context, avoiding self-check loops and mid-context attrition. The repair protocol edits only the minimal affected region under explicit policies (retry, catch, timeout, backoff, idempotency keys, compensation, loop guards) defined in a canonical workflow IR that maps to Amazon States Language and Argo Workflows. On job-shop scheduling suites (DMU, TA) across five classical benchmarks, ALAS matches or exceeds strong single-LLM and multi-agent baselines, achieving 83.7% success, reducing token usage by 60%, and running 1.82times faster under comparable settings. A minimal reliability study shows that the validator detects injected structural faults with low overhead, and that localized repair contains runtime perturbations with a bounded edit radius and less makespan degradation than global recompute. Results indicate that the combination of validator isolation, versioned execution logs, and localized repair provides measurable efficiency, feasibility, and scalability for multi-agent LLM planning. Code and seeds will be released.

1 INTRODUCTION

ALAS treats multi-agent planning reliability as a systems problem, addressing circular verification, context degradation, and missing state with isolated validation, versioned logs, and localized repair. Its workflow architecture and disruption-aware evaluations target feasibility retention while preserving work in progress.

  • Motivation: Standalone LLM planners can produce incomplete or inconsistent plans, violate constraints, and struggle with long-range coordination and reactive updates.The introduction attributes these problems to circular verification, long-context information loss, decoding bias, and absent external state.
  • Approach: ALAS frames reliability as a systems property, combining validator isolation, versioned execution logging, and localized repair for transactional, dynamic planning.The architecture turns a high-level specification into a locally repairable workflow with explicit policies and audit-oriented execution records.
  • Architecture: The five-layer design spans workflow blueprinting, agent and IR construction, policy-controlled execution with localized repair, revalidation, and supervision.The canonical IR supports portability across ASL and Argo, while the operational loop uses policies and logs to contain faults.
  • Contributions: The contributions include bounded-blast-radius repair, engine-parity testing, deterministic replay, and fault-injection support alongside the five-layer architecture and canonical IR.The implementation is designed to preserve feasibility without costly global recomputation.
  • Evaluation: ALAS evaluates disruption-aware planning on DMU and TA job-shop scheduling suites, emphasizing feasibility retention and stable makespan under comparable token and latency budgets.The stated evidence focuses on runtime perturbations rather than perfect first-pass generation.

2 RELATED WORK

Prior work addresses LLM planning, multi-agent orchestration, workflow execution, and benchmarks, but reliable planning under dynamic, stateful disruption remains insufficiently covered. ALAS positions validator isolation, durable logs, explicit policies, and localized repair as its systems-level response.

  • Structural limitations: LLM planning research documents circular verification, long-context degradation, solution-space bias, error propagation, and missing persistent state.Self-reflection and structured validators help in narrow domains, while open-domain reliable revalidation remains limited.
  • LLM orchestration: Existing orchestration frameworks provide useful coordination, retries, branches, or state passing, but typically lack durable execution and complete policy semantics.ALAS contrasts conversation-centric frameworks with workflow-runtime integration that makes reliability contracts explicit.
  • Positioning: ALAS complements durable saga-style recovery by making planning reliability explicit through validator isolation, log-grounded checks, and localized repair.The comparison distinguishes execution-layer durability from planning-level reliability mechanisms.
  • Workflow standards: Workflow runtimes provide precise execution and recovery semantics, while ALAS uses a canonical IR to interoperate with Argo Workflows and Amazon States Language.The related-work discussion also identifies BPMN for documentation and Airflow as a Python-native option.
  • Benchmarks: Disruption-aware evaluation is limited, motivating DMU and Taillard job-shop suites with machine downtime and operation-delay perturbations.These benchmarks provide formal constraints, known bounds, and natural perturbation models for evaluating logs, validation, and repair.

3 ALAS ARCHITECTURE AND SPECIFICATION

ALAS specifies a five-layer, validator-isolated workflow that represents roles, constraints, policies, schemas, and logs in a canonical IR. Runtime execution records versioned state, validates short grounded slices, and repairs only affected neighborhoods before revalidation or controlled fallback.

  • Architecture: ALAS organizes planning reliability into workflow blueprinting, agent factory, runtime execution with localized repair, revalidation, and supervision.The five layers convert a high-level specification into a validator-isolated, locally repairable workflow.
  • 3.1 LAYER 1: WORKFLOW BLUEPRINTING: Workflow blueprinting builds a template from task input, constraints, and disruptions by defining roles, dependency edges, invariants, node specifications, repair bounds, policies, and versioned logs.The template is accepted only after structural, constraint, and repair-coverage checks by an independent validator.
  • 3.2 LAYER 2: AGENT FACTORY AND CANONICAL WORKFLOW IR: The canonical IR is engine-agnostic, explicitly encoding retry, catch, timeout, backoff, idempotency, compensation, loop guards, schemas, and logging references before mapping to ASL or Argo.Its stated goal is portability and reproducibility rather than introducing a new orchestration formalism.
  • 3.3 LAYER 3: RUNTIME EXECUTION AND LOCALIZED REPAIR: Runtime state maintains the workflow graph, assignment map, versioned log, and policy set; step updates can trigger retry, catch, or compensation.Agents execute in dependency order, while validators consume short log-grounded slices instead of planner context.
  • 3.3 LAYER 3: RUNTIME EXECUTION AND LOCALIZED REPAIR: Localized repair scopes the smallest affected neighborhood, applies minimal feasibility-restoring edits, validates the subplan, and commits a new log version or enlarges scope when necessary.The system revalidates until feasibility or the iteration budget is reached, then can fall back to global recomputation or retain the best feasible plan.
  • Policies and contracts: The specification separates planner, validator, repair, and optimizer contracts, with validation enforcing domain constraints and repair restricted to the selected neighborhood.The policy and fault model covers transient and logical faults, while resource exhaustion and Byzantine behavior remain out of scope.

4 EXPERIMENTAL EVALUATION

ALAS is evaluated for scalable, disruption-aware planning in job-shop scheduling across five classical benchmarks, comparing feasibility, optimality, repair behavior, and overhead against single-agent and multi-agent baselines. It achieves strong aggregate success and optimality while using localized repair to limit disruption.

  • Evaluation setup: The evaluation measures feasibility, efficiency, containment, and overhead under static plans, dynamic repairs, and runtime disruptions.The job-shop suite includes DMU, TA, ABZ, SWV, and YN, with machine breakdowns and duration shocks.
  • Main results: 83.7% aggregated success was achieved, with statistically significant gains over baselines on DMU, TA, and ABZ.The comparison covers five benchmarks and reports significance using paired tests.
  • Main results: 100% optimal rate was reached by the best ALAS variant per dataset across all five benchmarks.Table 4 reports optimal rates for multi-agent systems and ALAS variants.
  • LCRP mechanism: LCRP performs local edits after a breakdown, propagates delays through logged dependencies, and then applies bounded queue reordering with a work-in-progress penalty.In the illustration, the final makespan is 22 with one unit of WIP movement and minimal messaging.
  • Ablation study: Removing validation or repair sharply reduces optimal rates, whereas the full workflow reaches up to 99.0–98.2% across backbones.The ablation compares Full ALAS, No-Repair, and No-Validator variants under injected structural faults.

5 CONCLUSION

ALAS concludes that reliable multi-agent LLM planning requires isolated validation, versioned execution state, and localized repair rather than global recomputation. The framework combines these principles with a canonical workflow IR and explicit execution policies, while identifying formal guarantees, adaptive models, and stronger QA as future work.

  • Conclusion: ALAS addresses standalone LLM planning weaknesses through validator isolation, versioned execution logs, and localized cascading repair.The validator uses fresh bounded prompts, logs state transitions and causal links, and confines disruptions to minimal neighborhoods.
  • Supported scope: Across transportation, event coordination, and job-shop scheduling, ALAS reports high feasibility and strong efficiency while preserving work-in-progress under disruption.The conclusion states that ALAS outperforms single-LLM baselines and competitive heuristics within the evaluated scope.
  • Future work: Future work includes adaptive duration and arrival models, stronger formal guarantees for LCRP and validator soundness, and systematic red-team QA with static analysis.The stated agenda also includes broader optimization methods and online telemetry for adaptive repair.
  • Workflow IR and policies: The canonical IR makes retries, catches, timeouts, backoff, idempotency keys, compensation, and loop guards explicit and portable across ASL and Argo.Policies are attached to workflow nodes through policyRef and support auditability, replay, and cross-engine parity.

A.13 EXPERIMENTAL PROTOCOLS

The evaluation protocol compares ALAS with standalone and multi-agent JSSP approaches using standardized prompts, structured schedules, constraint validation, repair, revalidation, and makespan measurement. Experiments also include representative schedule visualizations and runtime logs documenting iterative repair behavior.

  • Protocol design: ALAS evaluation separates static schedule generation from validation, agent execution, runtime adaptation, and disruption-aware repair.Standalone LLMs produce an initial workflow template, while ALAS validates it, instantiates agents, logs runtime state, and triggers local repairs.
  • Visualization: Figure 4 visualizes optimized ALAS schedules across four JSSP instances with varying job and machine counts, including the larger TA72 instance in supplementary material.The charts are intended to show resource allocation and makespan behavior across different problem scales.
  • JSSP setup: JSSP prompts require a valid schedule, minimum makespan, sequential job precedence, and non-overlapping operations on each machine.The common query specifies jobs, operations, machines, durations, required output fields, and the two principal feasibility constraints.
  • Execution procedure: The workflow records schedule entries and makespan, validates constraints, applies cascading repair with queue reordering, and revalidates the repaired schedule.The documented execution path includes loading a schedule, finding violations, identifying affected operations, repairing precedence, and repeating validation.
  • Repair trace: Errors fell from 28 to 10 and then from 6 to 2 in later repair iterations, with makespan remaining 665.The repair log reports these reductions at iterations 3 and 5, while the run ultimately records remaining errors.

B.4 LLM HEURISTIC BASELINES (SAMPLED)

The sampled LLM baselines produce static schedules, while ALAS validates and refines templates through an isolated validator and bounded iteration cycle. The supplied passages describe the comparison setup and ALAS workflow, but do not provide benchmark outcome values.

  • LLM heuristic baselines: Standalone LLMs provide only Phase 1 static schedules, whereas ALAS adds validation, refinement, agent instantiation, and runtime adaptation.The sampled schedules are treated as Wtemplate; ALAS continues through later validation and execution layers.
  • ALAS validation: ALAS typically reaches a valid plan within up to 5 validation-replan iterations across all benchmark datasets.Figure 5 is identified as the visualization of error rate by repair iteration, but its values are not supplied here.
  • ALAS workflow: The architecture includes a canonical workflow IR, executable agent specifications, repair specifications, logging schemas, and converters or implementations for runtime execution.The supplied passages list discovery, matching, verification, and LLM-based generation as implementation routes, without reporting comparative performance values.
  • ALAS validation: ALAS validates workflow structure, constraints, and repair coverage with an independent validator before returning a validated Wtemplate.The validator uses bounded context and remains separate from the planner, preventing circular validation.

C.2.6 FACTORY DESIGN PATTERN IMPLEMENTATION

ALAS uses the Factory design pattern to separate agent specifications from implementations and support reusable, heterogeneous, and replaceable components. This lets implementation strategies evolve without changing meta-planning or runtime components.

  • Factory design pattern: The Factory pattern decouples agent specifications from implementation details while supporting heterogeneous technologies and runtime substitution.It also maintains a reusable repository of components for recovery or optimization.
  • Architectural consequence: The pattern enables ALAS to evolve its agent implementation strategies without modifying meta-planning or runtime components.The architecture is grounded in program synthesis, component-based software engineering, prompt engineering, and agent-oriented software engineering.
  • Factory optimization: Caching, component reuse, incremental refinement, and resource scaling reduce redundant implementation generation for recurring or similar agents.Incremental refinement uses delta-based generation rather than creating similar agents entirely from scratch.

D ALGORITHM, LEMMA, AND THEORY PROOFS

The theory section formalizes localized repair as a bounded-edit scheduling decision problem and establishes both operational complexity bounds and strong NP-hardness. The hardness result applies even when repair budgets are bounded in common formulations.

  • Complexity: LCRP’s worst-case per-run effort combines status updates, delay propagation, queue optimization, and cascading delays, with practical bounds improved by limiting swap evaluations.The supplied corollary gives O(J^2/M + JM) for single-operation jobs and O(SJOmax + JMOmax) for swap-limited implementations.
  • Decision problem: LCRP asks whether a schedule can be made feasible and kept within makespan K using at most R local edits.Allowed edits include insertion, movement, swapping, and reassignment from an initial schedule.
  • Hardness result: LCRP is strongly NP-hard by reduction from the standard Job-Shop Scheduling decision problem.The reduction uses the same jobs, machines, operation orders, processing times, and makespan bound, with a sufficiently large repair budget.
  • Hardness result: The decision problem remains NP-hard for bounded-edit variants, including formulations where the budget is small or matches the number of operations to place.This makes the hardness robust to common repair-budget formulations.
  • Complexity: Polynomial per-iteration costs do not make globally targeted repair easy, because deciding whether any repair reaches a global makespan target remains computationally intractable unless P = NP.This distinction separates operational effort for a repair run from the complexity of finding a repair meeting a global target.

E.2.1 STATE-SPACE ANALYSIS

The URS state-space analysis models passengers, vehicles, locations, timing, resources, objectives, and execution protocols as a dependency network. ALAS then transforms the abstract template into an adaptive execution workflow with concrete assignments and disruption handling.

  • State-space dimensions: The URS state space tracks four passenger requests, three vehicles, locations, travel times, capacity, arrival deadlines, and distance-minimization objectives.The example includes 10 km urban segments, 31–36 km airport routes, and airport arrivals between 08:45 and 09:00.
  • Network construction: The planning network represents passenger, vehicle, and location nodes connected by temporal, spatial, and capacity dependencies.Temporal constraints are derived backward from airport deadlines, while spatial edges represent routes and capacity edges represent feasible passenger groupings.
  • Agent assignment: Specialized agents divide route planning, scheduling, capacity management, temporal constraints, resource allocation, distance optimization, and passenger grouping.The agents coordinate task-specific, common, and edge-level aspects of the ride-sharing plan.
  • Validation and refinement: Validation checks temporal feasibility, vehicle capacity, passenger coverage, and resource allocation before iterative refinement adjusts compatible groupings and vehicle assignments.The final plan includes exact pickup times, routes, vehicle assignments, buffers, and contingency protocols for traffic or passenger delays.
  • Template-to-execution transition: Wexec resolves abstract roles into real drivers, passengers, vehicles, and real-time distances while adapting to traffic, availability, and delays.This transformation translates the structured Wtemplate into actionable real-time operations.
  • Reactive planning: Under a road closure, modular agents can update paths, arrival estimates, and vehicle allocation locally, whereas baseline LLMs lose vehicle-state consistency after partial execution.The contrast motivates reactive planning that preserves consistency during disruptions.

F.8 EXPERIMENT #1: SEQUENTIAL PLANNER WITH COMMON SENSE

ALAS’s sequential-planning experiment evaluates common-sense scheduling across realistic constraints and shows that standalone LLM errors persist even when feasible plans emerge after revision. The analysis attributes these failures to dependency tracking, stale iterative state, and context degradation, while ALAS maintains stronger scheduling efficiency and consistency.

  • ALAS and Gemini consistently generated feasible schedules, while the other standalone LLMs encountered significant challenges.
  • DeepSeek and Claude converged in two iterations, whereas GPT4o required three iterations and produced less efficient travel and load distributions.DeepSeek improved efficiency by having James wait at the airport; GPT4o and Claude introduced redundant travel or suboptimal pickup assignments.
  • Observations of errors in standalone LLMs: Initial standalone plans contained wrong travel-time estimates and implausible scheduling decisions, including premature cooking and leaving the airport without Emily.
  • Observations of errors in standalone LLMs: Overlapping dependencies and incomplete constraint resets caused cascading errors and stale-memory propagation across iterative revisions.The proposed remedy is to enumerate atomic dependencies, re-evaluate global constraints, and reset to a clean baseline for each iteration.

F.9 EXPERIMENT #2: REACTIVE PLANNER FOR FLIGHT DELAY

The flight-delay experiment tests whether planners can revise a schedule under a disruption while preserving family pickup and dinner constraints. ALAS remained feasible through stateful, conflict-aware local repair, whereas DeepSeek and Claude failed repeatedly.

  • ALAS generated a feasible reactive plan, while DeepSeek and Claude 3.7 failed under the flight-delay disruption.
  • DeepSeek and Claude failed in seven out of ten runs by violating pickup constraints, delaying Grandma’s pickup, or missing the dinner deadline.
  • ALAS repaired the disruption by updating persistent state, detecting conflicts, evaluating alternatives, and validating constraints.Its local reactive compensation protocol produced four distinct feasible plans.
  • ALAS’s reroute sends Michael directly to Boston Airport after collecting Emily, avoiding an unnecessary stop at home.The adjustment follows state-aware reasoning and preserves the downstream pickup schedule.

P OST 6:00 PM

After the flight delay, the original pickup plan becomes infeasible because the remaining time cannot accommodate Grandma’s trip before dinner. ALAS instead uses state history and compensation to reroute Michael and preserve a feasible reunion schedule.

  • James cannot pick up Grandma and return by 6:00 PM after arriving at 4:00 PM, while Michael and Sarah are also constrained by existing duties.
  • ALAS routes Michael directly from Emily’s pickup to Grandma’s house, trimming roughly 30 minutes of travel and enabling the on-time family reunion.

G.1 CASE STUDY 1: TRANSPORTATION SCHEDULING

The transportation case study evaluates ALAS on dynamic ride-sharing and family-coordination tasks with deadlines, cancellations, additions, and delays. Across these settings, ALAS improves efficiency and reactive feasibility while using a workflow-oriented design intended to support portability and runtime integration.

  • Transportation scheduling: 95.1±13.0 km versus 118.9±16.6 km for baseline LLMs, a 20% improvement with p < 0.01, while all models met ride-sharing deadlines.The comparison reports mean±sd over ten independent trials; Figure 7 shows the ALAS schedule.
  • Transportation scheduling: ALAS repaired every ride-sharing disruption successfully, while baseline LLMs commonly lost vehicle state, duplicated assignments, or ignored updated deadlines.
  • Event coordination: In the Family Reunion task, ALAS produced feasible schedules in all sequential runs, whereas baselines frequently violated hard constraints and required retries.Typical baseline errors included treating 60-minute trips as 30–45 minutes and scheduling cooking implausibly early.
  • Event coordination: Under a flight delay to 16:00, DeepSeek and Claude failed in 7/10 runs, while ALAS succeeded in all runs through logged state, conflict detection, alternative testing, and local revalidation.
  • Workflow interoperability: The canonical IR preserves retry, timeout, backoff, idempotency, compensation, loop-guard, and schema fields while mapping to Amazon States Language and Argo Workflows.Its stated purpose is portability and reproducibility rather than introducing a new orchestration formalism.
  • Workflow interoperability: ALAS combines Temporal as the primary control plane with Argo for stages requiring very large Kubernetes parallelism, GPU pools, or heavy artifact movement.Temporal handles workflow state, timers, signals, and local repair before resuming control after Argo execution.

H.7 IMPLEMENTATION ARCHITECTURE

The implementation architecture connects standards and workflow engines through the ALAS intermediate representation, with executable components demonstrated in a Temporal-based JSSP workflow. The example covers setup, execution, result inspection, and extensions toward validation and repair.

  • The architecture connects standards and engines through the ALAS IR.
  • The reference implementation runs a JSSP workflow whose activity computes a schedule and whose workflow returns a verdict with the result.The workflow invokes solve_jssp and returns a JSON object containing the domain, verdict, and scheduling result.
  • The demonstrated result is a passing JSSP run with makespan 10 and a four-operation schedule.The JSON output includes the domain jssp, verdict pass, makespan 10, and schedule entries for jobs J1 and J2.
  • The Temporal deployment separates the client, worker, and server, with the client starting the workflow and the worker executing workflow and activity tasks.The run is dispatched through task queue alas-jssp and can be inspected in the Temporal Web UI.
  • The example activity produces a naive sequential schedule by walking operations in order and assigning contiguous start and end times.The paper describes this activity as a placeholder for a real scheduler.
  • The implementation can be extended by replacing the naive activity, adding validation and repair branches, and persisting results with searchable workflow attributes.
Loading 2511.03094v1…