ANNEAL: Adapting LLM Agents via Governed Symbolic Patch Learning

Safayat Bin Hakim, Keyan Guo, Wenkai Tan, Alvaro Velasquez, Shouhuai Xu, Houbing Herbert SongarXiv 2026 · arXiv

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).

Figure 2: ANNEAL system architecture. (a) Instructions compile into HTN plans via the Process Knowledge Graph (PKG); the metacognitive controller M monitors uncertainty u (token-level entropy) and violation probability pviol (logistic heuristic over precondition gaps), and arbitrates between S1 (fast), S2 (deliberative), and VERIFY (precondition check) pathways under budget B. (b) When a failure persists, FDKA proposes a typed patch ∆o that flows through six stages—localization, proposal, scoring, guardrail, canary, commit—under governance (provenance, trust, deterministic rollback).

The core architecture relies on three main pillars:

  1. 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.
  2. Comprehensive Governance Envelope: Before any proposed patch is committed to the rule pool, it must survive a multi-layered validation pipeline:
  3. 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.
  4. Hard Symbolic Guardrails: Enforces deontic (value-based) and causal constraints to veto potentially unsafe or ambiguous edits.
  5. Canary Testing: Runs the patched operator through sandboxed scenarios to catch distributional mismatches before deployment.
  6. 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.
  7. 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.
Figure 1: ANNEAL adaptation cycle. User requests hotel booking; execution fails due to policy violation. FDKA localizes the responsible operator, synthesizes a precondition patch, validates through scoring and guardrails, and commits. Replan with updated operator succeeds. Complete cycle: <2 minutes, no model retraining.
  • 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

Abstract

LLM-based agents can recover from individual execution errors, yet they repeatedly fail on the same fault when the underlying process knowledge--operator schemas, preconditions, and constraints--remains unrepaired. Existing self-evolving approaches address this gap by updating prompts, memory, or model weights, but none directly repair the symbolic structures that encode how tasks are executed, and few provide the governance guarantees required for safe deployment. We introduce ANNEAL, a neuro-symbolic agent that converts recurring failures into governed symbolic edits of a process knowledge graph without modifying foundation model weights. Its core mechanism, Failure-Driven Knowledge Acquisition (FDKA), localizes the responsible operator, synthesizes a typed patch through constrained LLM generation, and validates the proposal via multi-dimensional scoring, symbolic guardrails, and canary testing before commit. Every accepted edit carries full provenance and deterministic rollback capability. Across four domains and 27 multi-seed runs, ANNEAL is the only evaluated system that commits persistent structural repairs--strong baselines such as ReAct and Reflexion achieve high episodic recovery yet retain 72--100% holdout failure rates on recurring faults, whereas ANNEAL reduces these to 0% in the tested recurring-failure settings. Ablation confirms that removing FDKA eliminates all structural repairs and drops success rate by up to 26.7 percentage points. These results suggest that governed symbolic repair offers a complementary paradigm to weight-level and prompt-level adaptation for persistent fault elimination.
BibTeX
@misc{hakim2026anneal,
  author = {Safayat Bin Hakim and Keyan Guo and Wenkai Tan and Alvaro Velasquez and Shouhuai Xu and Houbing Herbert Song},
  title = {{ANNEAL: Adapting LLM Agents via Governed Symbolic Patch Learning}},
  year = {2026},
  eprint = {2605.16309},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.16309},
}
Figure