PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning from Failures: Heterogeneous Graph Memory for Small Language Model Tool-Using Agents

Jiaxing Li, Lei Song, Rui Dong, Youyong Kong

arXiv:2609.28003v1cs.LG

TL;DR

Flat memory may omit the causal context and safety conditions needed for reliable tool use in stateful tasks. FRESH structures successful and failed experience in a heterogeneous graph, and experiments on τ-Bench and AppWorld report consistent improvements in task completion and tool-use reliability across models.

  • Problem

    Flat memory does not explicitly preserve which observations actions require, why actions failed, or how to repair them, leaving a gap in reliable experience reuse.

    Source: Introduction · p. 2

  • Method

    FRESH organizes successes and failures in a heterogeneous graph of tasks, actions, errors, repairs, and execution conditions, then retrieves relevant experience for frozen models.

    Source: Introduction · p. 2

  • Results

    FRESH consistently improves task completion and tool-use reliability across τ-bench and AppWorld and across different small and medium-sized models.

    Source: Introduction · p. 2, Conclusion · p. 7

  • Takeaways & Limitations

    The findings support using structured failure knowledge as execution guidance for tool use in the evaluated benchmarks.

    Source: Conclusion · p. 7

    The execution hints are distilled only from training and development trajectories and should be treated as guidance, not task-specific ground truth.

    Source: Instantiated AppWorld Prompt · p. 13

Abstract

from arXiv · show

Small and medium-sized language models offer cost-effective executors for tool-using agents, making them attractive for local and large-scale deployment. However, in long-horizon and stateful environments, they often make structural errors such as missing required observations, performing premature writes, repeating failed calls, and violating action preconditions. These errors can lead to incorrect state updates, policy violations, and costly or irreversible consequences, making reliable tool execution a critical deployment challenge. Existing fine-tuning approaches require substantial data and computation, while flat memory may retrieve failed actions without preserving their causal context or safety conditions. In this paper, we propose FRESH, a Failure-aware Retrieval framework over Experience-Structured Heterogeneous graphs, which transforms historical successes and failures into structured external experience for tool-using agents. By explicitly modeling the dependencies among tasks, actions, errors, repairs, and execution conditions, FRESH helps frozen language models reuse reliable strategies, avoid recurring failures, and make safer decisions in stateful tool interactions. Experiments on $\tau$-Bench and AppWorld with multiple open-source models show that FRESH consistently improves task success and tool-use reliability over no-memory agents and representative memory-based baselines.

Introduction

FRESH organizes past successes and failures into structured external experience to help frozen small and medium-sized language models use tools more reliably in stateful settings. Its graph-based retrieval and action checks preserve the dependencies and conditions needed to reuse experience safely.

Introduction

  • Small and medium-sized models can skip required observations, repeat ineffective calls, lose intermediate state, or write before preconditions are met, risking policy violations and irreversible consequences.Reliable stateful tool use also requires sufficient evidence, state maintenance, error recovery, and safe state-changing operations.Source: Introduction · p. 1
  • FRESH addresses the limits of extra interaction and repeated fine-tuning: extra turns can repeat unproductive strategies, while adaptation to changing tools and policies requires substantial data and computation.External experience enables reuse while keeping the language model frozen.Source: Introduction · pp. 1–2
  • Flat or success-oriented memories can obscure action dependencies, failure causes, repairs, and write-action preconditions, leading agents to reuse failed actions or copy unsafe writes.Figure 1 contrasts flat trajectory memory with FRESH’s structured experience graph.Source: Figure 1 · p. 1, Introduction · p. 2
  • FRESH consistently improves task completion and tool-use reliability over no-memory, prompting, retrieval, trajectory, and experience-memory baselines on τ-bench and AppWorld.The evaluation covers multiple open-source small and medium-sized models.Source: Introduction · p. 2
  • FRESH models tasks, tools, actions, observations, errors, repairs, and execution conditions in a heterogeneous graph that distinguishes verified strategies from unsafe behaviors.It retrieves and ranks a relevant subgraph, then compresses the experience into guidance on what to do, avoid, check, or repair.Source: Introduction · p. 2
  • A lightweight policy and precondition gate checks risky actions against live observations and graph-derived constraints before execution, without modifying the underlying language model.The external scaffold is inspectable and updateable.Source: Introduction · p. 2

Related Work

Related work moves from tool-use methods toward stateful benchmarks, while memory and adaptation approaches reuse experience but leave execution dependencies and safety conditions under-modeled; FRESH addresses this with structured retrieval and checks.

benchmarks

  • BFCL, tau-bench (Yao et al. 2024), and AppWorld (Trivedi et al. 2024) test stateful tool use beyond syntactically valid calls.Reliable interaction also requires preserving state, satisfying action dependencies, recovering from errors, and avoiding unsafe or premature operations.Source: benchmarks · p. 2

Experience memory and agent adaptation

Method

FRESH builds a heterogeneous graph from successful and failed tool-use experiences, then uses retrieved guidance and a policy/precondition gate to help a frozen executor act safely. The graph and retriever remain frozen on held-out test tasks.

Problem Setup

  • The method targets interactive tasks in which agents use external tools that may retrieve information, change persistent state, or complete multi-application workflows, improving a fixed executor without updating its language-model parameters.Training uses successful and failed trajectories, while evaluation feedback includes task success and action metrics on τ-bench and task pass rate and evaluator-test completion on AppWorld.Source: Problem Setup · p. 3

Overall Framework

  • FRESH separates offline experience learning from test-time execution, combining a graph of tasks, tools, actions, observations, errors, preconditions, outcomes, and repairs with retrieved guidance for a frozen executor.The guidance includes recommended actions, patterns to avoid, conditions to check, and repair strategies.Source: Overall Framework · pp. 3–4

Policy / Precondition Gate and Self-Evolution Loop

  • The gate checks proposed actions against preconditions, live observations, and policies, allowing, revising, blocking, or transferring them; during development, feedback updates memory utility and adds failures, repairs, and preconditions.The graph and retriever are frozen for evaluation.Source: Overall Framework · p. 4, Policy / Precondition Gate and… · p. 5

Failure-Aware Experience Graph Induction

  • The experience miner normalizes trajectory data and assigns action-level credit, linking failed actions to their causes, missing preconditions, and repairs while retaining verified actions as useful evidence.Typed graph relations capture dependencies such as calls, requires, guards, fails_because, and fixed_by, separating unsafe actions from the warnings and repairs they yield.Source: Failure-Aware Experience Graph Induction · p. 4

Heterogeneous Graph Retriever Training

  • The retriever uses task-and-context queries and sparse recall to form candidate subgraphs, then feedback-supervised, relation-aware GNN ranking favors verified actions, useful preconditions, and repairs over failures.Sparse recall limits GNN computation to a task-relevant region; training optimizes the retriever while keeping the executor language model frozen.Source: Heterogeneous Graph Retriever Training · pp. 4–5

Test-time Graph-Conditioned Execution

  • At test time, FRESH compresses retrieved graph nodes into a compact prompt that removes task-specific identifiers and irrelevant observations while preserving actionable dependencies for the frozen executor.The executor conditions its candidate action on the current history and this compact memory sheet.Source: Test-time Graph-Conditioned Execution · p. 5

Experiments

FRESH improves tool-use performance across τ-bench and AppWorld, with ablations and analyses attributing its reliability to structured failure-aware experience and showing a favorable reliability–efficiency balance. The experiments also examine frozen-model backbones, memory baselines, and the organization of FRESH’s experience graph.

Experimental Setup

  • τ-bench (Yao et al. 2024) evaluates stateful, policy-constrained Airline and Retail interactions using passk for k ∈1, 2, 3, 4; AppWorld (Trivedi et al. 2024) measures split-specific Pass Rate and execution steps.AppWorld evaluates long-horizon API interactions across multiple software applications.Source: Experimental Setup · p. 5

Baselines.

SLM Backbones.

  • Experiments use frozen Llama-3.2-1B-Instruct, Qwen3-8B (Yang et al. 2025), and Gemma-4-26B-A4B (Team et al. 2026) backbones, with FRESH relying on external structured experience and retrieval.The models represent lightweight, intermediate, and relatively capable tool-use executors.Source: SLM Backbones · p. 5

Performance on τ-bench and AppWorld

  • FRESH achieves the highest overall performance across three executors on τ-bench and the highest AppWorld task-completion rate on both splits, with the fewest steps on Test-N.It also maintains competitive execution efficiency on Test-C; Qwen3-8B has the best average performance despite some baselines leading on individual τ-bench metrics.Source: Performance on τ-bench and AppWorld · pp. 5–6, Table 1 · p. 6, Table 2 · p. 6

Ablation Study

  • The ablation study finds the full FRESH performs best, with the policy gate most helpful on Airline and the learned HGNN retriever particularly important on AppWorld.Removing failure memory also consistently degrades performance, indicating failure causes and repair patterns complement successful trajectories.Source: Ablation Study · p. 6, Figure 3 · p. 7

Reliability–Efficiency and Robustness Analysis

  • FRESH offers a favorable balance of reliability, resource efficiency, and challenge robustness, with strong challenge retention and a comprehensive profile on τ-bench Airline and AppWorld Test-C.The no-memory agent is resource-efficient but less reliable, while existing memory methods generally improve only some evaluation dimensions.Source: Reliability–Efficiency and Robustness… · p. 7, Figure 4 · p. 7, Figure 5 · p. 7

Experience Graph Visualization

  • The experience graph links task-centered clusters of tools, actions, observations, outcomes, and reasoning, jointly representing successful and failed trajectories with typed error-cause and repair relations.Cross-task connections let related tasks share tools, repair strategies, and execution conditions, supporting retrieval of dependencies and failure-recovery evidence as well as semantically similar experience.Source: Experience Graph Visualization · p. 7

Conclusion

FRESH structures successful and failed tool-use trajectories as heterogeneous graph memory, then retrieves operational guidance and gates risky actions. Experiments on τ-bench and AppWorld show improved task completion and tool-use reliability across small and medium-sized models, often with fewer unnecessary execution steps.

Conclusion

  • FRESH consistently improves task completion and tool-use reliability across small and medium-sized models on τ-bench and AppWorld, often reducing unnecessary execution steps.Source: Conclusion · p. 7
  • FRESH converts successful and failed trajectories into structured experience distinguishing verified actions, failure patterns, repairs, and execution preconditions.Source: Conclusion · p. 7
  • A graph-aware retriever supplies compact operational guidance, while a lightweight policy and precondition gate constrain risky actions before execution.Source: Conclusion · p. 7

Appendix · Illustrative Example of Failure-Aware Graph Induction

The appendix uses an airline cancellation trajectory to show how FRESH turns a failed interaction into structured memory that preserves useful actions while encoding failure causes, missing conditions, and repairs. This memory can guide later cancellation requests with reusable Do, Avoid, Check, and Repair guidance.

Illustrative Example of Failure-Aware Graph Induction

  • The example normalizes a conditional cancellation request and its tool interaction, including a booking lookup followed by a cancellation rejected because eligibility was unverified.The interaction leaves the database state unchanged.Source: Illustrative Example of Failure-Aware… · p. 9
  • FRESH retains the successful booking lookup as a verified read while marking the premature cancellation as a failed write, rather than labeling every action incorrect.The cancellation is unsafe because eligibility and user confirmation were not verified; the failure-aware graph preserves the useful read and suppresses the unsafe write.Source: Illustrative Example of Failure-Aware… · p. 9
  • The miner extracts an error, a precondition, and a repair: verify eligibility, check booking status and fare rules, obtain confirmation, then follow a read–check–confirm–write sequence.If cancellation is not permitted, the guidance says to offer an allowed alternative or transfer the task.Source: Illustrative Example of Failure-Aware… · p. 9
  • Typed graph relations record which step succeeded, why the write failed, which condition was missing, and how to repair the failure, unlike a temporal trajectory chain.The example links verified actions to observations, failed actions to errors, preconditions to actions, and repairs to their supporting conditions.Source: Illustrative Example of Failure-Aware… · p. 9
  • The induced memory represents the request as a task with cancellation intent and policy constraints, and the successful lookup as a verified action-observation pair recommended for reuse.The failed action becomes a negative sample and an Avoid pattern, while the missing eligibility check becomes a retrieved Check condition.Source: Illustrative Example of Failure-Aware… · p. 9
  • For a new cancellation request, the retriever can rank the verified read, missing precondition, and repair above the premature write, then serialize them as Do, Avoid, Check, and Repair guidance.The guidance retrieves current booking state first, requires fare-rule, status, and user-confirmation checks, and offers an allowed alternative or task transfer if cancellation is not permitted.Source: Illustrative Example of Failure-Aware… · p. 9

Datasets and Benchmarks

The evaluation uses τ-bench’s Airline and Retail tasks and AppWorld’s multi-application tasks, with held-out test data excluded from experience-graph construction and retriever selection. It defines benchmark-specific success measures and reports additional execution diagnostics.

τ-bench

  • τ-bench evaluates policy-constrained, multi-turn interactions in Airline and Retail; 20 Airline and 40 Retail tasks are reserved for held-out evaluation from fixed disjoint splits.The original benchmark has 50 Airline and 114 Retail tasks; the remaining tasks are used for training and development trajectories, graph construction, and hyperparameter selection, with no held-out trajectory used to update the graph or HG-Retriever.Source: Datasets and Benchmarks · p. 10
  • Each τ-bench test task runs four times; passk measures successful completion across k sampled trials, and success requires the evaluator-specified final database state and actions.pass1 reflects average task success, while larger k measures stricter execution consistency.Source: Datasets and Benchmarks · p. 10

AppWorld

  • AppWorld contains 750 tasks across 250 scenarios and nine simulated applications; its Test-C split requires an API from an application unseen during training.The official partition has 105 training, 60 development, 168 Test-N, and 417 Test-C tasks; Test-C tests API understanding and cross-application generalization. (Trivedi et al. 2024)Source: Datasets and Benchmarks · p. 10
  • For AppWorld evaluation, the graph and HG-Retriever are frozen before Test-N and Test-C; reported measures include task-level Pass Rate, execution steps, action proxies, prompt-token usage, and inference cost.The experience graph is constructed using only training and development splits; Pass Rate is the proportion of tasks satisfying official state-based evaluation tests.Source: Datasets and Benchmarks · p. 10

Details on Baselines

FRESH is compared with baselines spanning no-memory execution, prompting, semantic retrieval, trajectory reuse, and experience learning under matched evaluation conditions. The baselines differ in how they represent and retrieve prior experience, including whether they preserve execution dependencies and safety conditions.

Details on Baselines

  • Comparisons match training and development trajectories, held-out task splits, executor backbone, interaction budget, and system instructions; retrieval methods also match FRESH’s memory count and prompt budget where applicable.Method-specific hyperparameters are selected on the development split.Source: Details on Baselines · p. 10
  • No Memory uses only the frozen executor, current interaction history, domain policies, and tool schemas, without historical trajectories or external experience.Train-Text instead provides every test task the same fixed prompt of historical experience, without task-specific retrieval (Brown et al. 2020).Source: Details on Baselines · p. 10
  • Vector-RAG retrieves semantically similar independent text memories, while Trajectory Replay retrieves and replays task-relevant complete trajectories as demonstrations (Lewis et al. 2020; Zhao et al. 2024).Vector-RAG lacks typed dependencies and graph reranking; replayed trajectories can include task-specific identifiers, irrelevant observations, and failed actions.Source: Details on Baselines · p. 10
  • ReasoningBank retrieves compact textual reasoning memories distilled from successful and failed interactions, but does not explicitly encode action dependencies or execution preconditions.Source: Details on Baselines · p. 10
  • Mem0 extracts and consolidates concise long-term memories from the shared historical trajectory pool, then retrieves them semantically under the same context-budget constraint as FRESH.Source: Details on Baselines · pp. 10–11
  • H-EPM combines episodic memory with procedural tool-transition knowledge, primarily modeling successful regularities rather than FRESH’s failure causes, repairs, write preconditions, and risky-action constraints.Source: Details on Baselines · p. 11

Details on SLM Backbones

The evaluation uses three frozen, instruction-tuned open-source backbones spanning lightweight to relatively capable executors. FRESH improves execution through external experience organization rather than language-model updates.

Evaluation setup

  • All methods use the same decoding configuration, context limit, tool schemas, execution-step limit, and benchmark-specific system prompt within each frozen backbone.External memories are placed in a dedicated memory block without changing the user request or tool definitions.Source: Details on SLM Backbones · p. 11

Llama-3.2-1B-Instruct

  • Llama-3.2-1B-Instruct is the lightweight executor used to test whether structured external experience can compensate for weak long-horizon state tracking, planning, and error recovery.Source: Details on SLM Backbones · p. 11

Qwen3-8B

  • Qwen3-8B (Yang et al. 2025) serves as the intermediate-capacity executor, with stronger instruction following and reasoning than the 1B model while remaining practical for local or moderately resourced deployment.Source: Details on SLM Backbones · p. 11

Evaluation scope

  • FRESH improves execution across all three backbones solely through external experience organization, without updating language-model parameters.The backbones span lightweight, intermediate-capacity, and relatively capable executors.Source: Details on SLM Backbones · p. 11

Gemma-4-26B-A4B

  • Gemma-4-26B-A4B is the relatively capable executor for examining whether failure-aware graph memory helps models with stronger planning and tool-use capabilities.Source: Details on SLM Backbones · p. 11

Example of an Instantiated FRESH Prompt

A real Retail exchange episode illustrates how an instantiated FRESH prompt combines retrieved strategies and action patterns with live-state checks and policy gates. Entity identifiers are anonymized, repeated low-ranked candidates are omitted, and no operational instruction is manually added or modified.

Retrieved Success Strategy

  • The prompt advises gathering missing account facts, choosing tools from live observations, and taking one targeted check or repair per observation instead of entering open-ended loops.After repeated turns, it recommends summarizing known facts, the latest observation, and the unresolved blocker before taking one verified action, asking a targeted question, or transferring the task.Source: Example of an Instantiated FRESH Prompt · p. 12

Policy/Precondition Gate

  • Before a risky exchange write, verify ownership, order status, policy eligibility, and user confirmation; treat database mismatches as signs the sequence may be incomplete or inconsistent with live state.The prompt says to rely on current policies and live tool observations, and never let a retrieved success path bypass preconditions.Source: Example of an Instantiated FRESH Prompt · pp. 12–13

Verified Tool/Action Pattern

  • The example records exchange_delivered_order_items as a successful verified action pattern, with confidence 0.67.The prompt cautions against reusing historical exchange actions until identifiers, item variants, payment method, and eligibility are verified against current state.Source: Example of an Instantiated FRESH Prompt · p. 13

Policy/Precondition Gate

  • When information is missing, the prompt directs the agent to revise its plan to a read action or targeted question, and to allow risky writes only after live facts and explicit confirmation are verified.The example is instantiated from Retail Task 5, Trial 0; entity identifiers are anonymized and repeated low-ranked candidates omitted.Source: Example of an Instantiated FRESH Prompt · pp. 12–13

Instantiated AppWorld Prompt

The instantiated AppWorld prompt combines training- and development-derived execution guidance with the live Spotify task, while treating current instructions, API documentation, and observations as authoritative. It emphasizes verifying state before completing the task.

Prompt reconstruction

  • The prompt is reconstructed from a successful AppWorld Test-N episode using the same task specification, training graph, R-GCN checkpoint, and prompt-construction code.Credentials are anonymized and repetitive API documentation is omitted.Source: Instantiated AppWorld Prompt · p. 13

Memory usage constraints

  • FRESH hints are execution guidance, not task-specific ground truth; memory must not override live instructions, API documentation, or observations.The prompt also prohibits copying historical identifiers or credentials and recommends using memory to choose a verification step rather than replaying a full trajectory.Source: Instantiated AppWorld Prompt · p. 13

Verified success patterns

  • For Spotify queue management, authenticate, inspect the queue and liked songs, make required changes, verify the queue and player state, then complete the task.The example request is to remove all liked songs from the queue and start the player.Source: Instantiated AppWorld Prompt · pp. 13–14

Failure patterns and completion preconditions

  • Avoid repeating credential lookups, inspecting downloaded songs for a liked-song task, broad cleanup before checking the queue, or completion before verification.Before completion, confirm all liked songs are removed, unrelated queue entries remain unchanged, and the player has started.Source: Instantiated AppWorld Prompt · p. 14

Related papers

Loading 2609.28003v1…