TL;DR
ANNEAL is a neuro-symbolic framework that enables LLM agents to permanently fix recurring operational errors by automatically patching their symbolic process knowledge graphs instead of modifying model weights or prompts. By combining constrained LLM generation with rigorous symbolic guardrails and canary testing, it eliminates recurring holdout failures entirely while providing strict safety and rollback guarantees.
What Problem Does This Paper Address?
Current LLM-based agents are surprisingly good at episodic recovery. If a tool call fails or a precondition isn't met, frameworks like ReAct or Reflexion allow the agent to retry or use verbal reflection to find an alternate workaround within that specific run.
However, these agents suffer from a form of amnesia: they don't structurally learn from their mistakes. Because their underlying process knowledge—such as operator schemas, preconditions, and constraints—remains completely unchanged, they will repeatedly stumble into the exact same failure modes when faced with similar tasks in the future.
While existing self-evolving methods attempt to address this by updating prompts, maintaining vector memories, or fine-tuning weights, these approaches are prone to catastrophic forgetting, lack precision, and rarely provide the strict governance guarantees (like auditability and deterministic rollbacks) required for safe enterprise deployment.
Methods
ANNEAL bridges this gap using a neuro-symbolic architecture that treats the LLM not as an unconstrained decision-maker, but as a highly regulated code generator designed to repair a Process Knowledge Graph (PKG).
The core architecture relies on three main pillars:
- Failure-Driven Knowledge Acquisition (FDKA): When an execution failure occurs, ANNEAL localizes the responsible operator using a responsibility scoring mechanism. It serializes the failure trace into a structured JSON prompt and tasks the LLM with synthesizing a typed patch (e.g., adding a missing precondition or refining an effect) under a strict, closed JSON schema.
- Comprehensive Governance Envelope: Before any proposed patch is committed to the rule pool, it must survive a multi-layered validation pipeline:
- Multi-dimensional Scoring: Evaluates the patch based on plausibility (log-probability alignment), consistency (verified via fast symbolic heuristics or Z3 SMT solvers), utility (counterfactual replay over past failure traces), and risk.
- Hard Symbolic Guardrails: Enforces deontic (value-based) and causal constraints to veto potentially unsafe or ambiguous edits.
- Canary Testing: Runs the patched operator through sandboxed scenarios to catch distributional mismatches before deployment.
- Beta-Bernoulli Trust Scoring: Tracks the empirical success rate of the patch over time, triggering an automatic deterministic rollback if its reliability drops below a set threshold.
- Metacognitive Arbitration: A stage-aware control loop monitors token-level uncertainty and violation probabilities to dynamically route tasks through fast (S1), deliberative (S2), or verify-before-act pathways under explicit computational budgets.
Datasets
The authors evaluated ANNEAL across 27 multi-seed runs spanning four distinct, challenging planning domains:
- Travel Planning: 25 tasks involving "Policy Flips" (blackout dates, loyalty restrictions), "Tool Drift" (API schema changes), and out-of-distribution entities.
- Travel Stochastic: A variant of the travel domain injecting transient noise and compound policy shifts.
- E-commerce: 25 tasks covering order processing, payment validation, and inventory management with forced tool-schema drift.
- IT Service Management (ITSM): An untuned transfer domain consisting of 25 tasks spanning access provisioning, patch deployment, and credential resets.
Additionally, they developed a dedicated Governance-Stress Benchmark featuring fixed order-placement tasks designed to force security-sensitive authentication schema migrations.
Key Insights and Ideas
- Episodic Success $\neq$ True Adaptation: High overall success rates can mask persistent underlying faults. The authors show that baselines like Reflexion achieve high episodic success through clever within-episode workarounds but leave the core failure unresolved. ANNEAL introduces a structural ratchet effect: once a symbolic patch is committed, that specific failure mode is structurally blocked from recurring.
- The LLM as a Constrained Patch Generator: Rather than letting the LLM freely generate actions or modify prompts, ANNEAL restricts its output to a strict symbolic schema. This keeps the agent's evolution completely auditable, predictable, and reversible.
- Defense-in-Depth Gating: No single validation mechanism is foolproof. By combining SMT solvers (for logical consistency), causal guardrails (for safety), and empirical canary testing (for environment alignment), ANNEAL ensures that different layers catch distinct failure modes that others might miss.
Key Results
- Zero Recurring Failures: In holdout stress tests, ANNEAL's committed patches reduced holdout target-failure rates to 0% across all evaluated settings. In contrast, ReAct, Reflexion, and text-memory baselines retained 72% to 100% holdout failure rates on recurring faults.
- High Task Success Rates: ANNEAL achieved 94.7% to 100% task success across all four evaluation domains, outperforming ReAct in complex environments like E-commerce (94.7% vs 78.7%).
- Crucial Components: Ablation studies revealed that removing the FDKA pipeline completely eliminated structural repairs and caused task success rates to drop by up to 26.7 percentage points. Removing metacognitive arbitration dropped success by 4.7 percentage points under stochastic noise.
- Flawless Governance Gating: On the governance-stress benchmark, ANNEAL achieved 100% decision accuracy, successfully escalating all six security-sensitive schema edits to human review rather than silently committing them.
Limitations and Future Work
- Operator-Level Constraints: FDKA is currently limited to operator-level modifications (schemas, preconditions, effects). It cannot yet perform broader workflow restructuring, constraint-level edits, or synthesize entirely novel operators for completely unseen fault classes.
- Cross-Sibling Transfer: Patches are tied to specific content-addressed keys. If a sibling operator uses renamed fields or a different schema hash, the patch will not automatically generalize to it, requiring separate patches for each sibling.
- Long-Horizon Scaling: While evaluated on horizons of up to 15 tasks, benchmarking ANNEAL under genuinely long-horizon planning scenarios—such as deep dependency chains or multi-day compound shifts—remains an open direction for future research.
Summary updated