Source-linked AI summary
Rethinking the Role of Tool Graph Memory in Multi-Turn Tool Use
Uiji Hwang, Richeng Xuan, Taeuk Kim
TL;DR
Whether tool graph memory consistently benefits multi-turn tool-use agents remains unclear. The paper evaluates it across models and benchmarks, measures its costs, and compares it with situation-level insight memory. Tool graph memory rarely improves significantly and its gains are costly, while insight memory outperforms it with almost no extra LLM calls.
Problem
It remains unclear whether tool graph memory's next-tool guidance consistently benefits agents across multi-turn interactions.
Source: §1 · p. 1Method
The paper evaluates tool graph memory across models and benchmarks, measures its computational cost, analyzes its gains and failure modes, and compares it with insight memory distilled from the same episodic experience.
Source: §1 · p. 1, §4.2 · p. 4Results
Tool graph memory rarely improves significantly over the base agent, while insight memory outperforms it in most settings with almost no extra LLM calls.
Source: §1 · pp. 1–2, §5 · p. 4Takeaways & Limitations
Situation-level semantic cues appear more useful than direct next-tool prescriptions for multi-turn tool use.
Source: §5 · pp. 4–5The analysis targets tool graph memories whose nodes are tools and edges are transitions, not richer graphs representing states, arguments, or other entities.
Source: Limitations · p. 5
Abstract
from arXiv · showhide
Large language model (LLM) agents solve complex tasks by calling external tools over multiple turns. Recent work has proposed tool graph memory, which stores past experience as tool transitions to guide subsequent selection. However, it remains unclear whether this component consistently improves agents' tool use or undermines it. We evaluate tool graph memory on nine models and two benchmarks, finding that it seldom improves significantly over baselines, and that its gains, where present, cost over twice the LLM calls. The memory's guidance is often incorrect, and random or no guidance retains most of the gain, implying that the benefit stems from extra computation rather than the memory itself. Moreover, even with the correct next tool suggested, many failures remain, such as giving up without a tool call. Storing the same experience instead as textual insights outperforms tool graph memory with almost no extra LLM calls. This suggests that memory serves better as a soft prior than as a prescription of the next tool, leading to a more effective and generalizable solution.
1 Introduction
Tool graph memory represents prior experience as tool transitions to guide next-tool selection, but whether that guidance consistently benefits multi-turn agents remains open. The paper evaluates its effectiveness and cost, examines where gains come from, and compares next-tool suggestions with situation-level guidance.
1 Introduction
- Tool graph memory encodes past experience as transitions between tools and provides step-level guidance for choosing the next tool.The paper asks whether this guidance consistently benefits agents across multi-turn interactions.Source: §1 · p. 1
- The evaluation tests consistency across model families, sizes, and benchmarks, measures LLM-call and token costs, and analyzes gains and unresolved failure modes.It also characterizes guidance needed beyond next-tool suggestions.Source: §1 · p. 1
- Across models and benchmarks, tool graph memory rarely improves significantly over the base agent, and H-EPM's gains require substantially more LLM calls and tokens.Random or no suggestions retain most of the improvement, while encouraging more tool calls yields comparable gains.Source: §1 · pp. 1–2
- Even with gold-standard next tools, failures persist when agents give up without calling a necessary tool or call before prerequisites are met.The paper therefore examines situation-level guidance through insight memory, which outperforms tool graph memory in most settings with almost no extra LLM calls.Source: §1 · p. 2
2 Limited Benefit of Tool Graph Memory
Tool graph memory stores prior tool transitions and offers next-tool suggestions, while this section evaluates its performance and cost against memory-free agents. Neither ToolNet nor H-EPM consistently improves over Base, and H-EPM's gains come with substantially higher inference cost.
2.1 Tool Graph Memory
- ToolNet represents tools as nodes and weighted directed transitions as edges, presenting successors of the previous tool with transition weights as preferences.H-EPM retains the full tool set and combines weighted transitions with context summaries attached to edges; its suggestions depend on the current summary or transition weights.Source: §2.1 · p. 2
- The paper calls the candidate tools supplied by ToolNet and H-EPM “next-tool suggestions,” the guidance of tool graph memory.H-EPM can suggest tools based on matching stored contexts or, absent a summary, the highest transition weights.Source: §2.1 · p. 2
2.2 Experimental Settings
- The evaluation compares memory-augmented agents with Base on ToolSandbox and the multi-turn BFCL-v4 subset using nine open-weight models from 2B to 120B parameters.Each method is run three times, with mean and standard deviation reported.Source: §2.2 · p. 2
2.3 Experimental Results
- H-EPM outperforms Base in most settings, but its gains are reliable in only four; ToolNet underperforms Base in most cases, including all nine BFCL-v4 models.ToolNet has a statistically significant gap in 12 cases (p < 0.05).Source: §2.3 · p. 2
- On ToolSandbox, H-EPM averages 2.72× as many LLM calls and 2.21× as many tokens as Base, while neither method offers a better performance–cost trade-off than Base.ToolNet uses fewer tokens than Base but is not notably better in any setting.Source: §2.3 · pp. 2–3
3 Origin of Tool Graph Memory’s Gains
The analysis finds that H-EPM’s gains are not primarily explained by its tool suggestions: agents often succeed despite incorrect suggestions, and more tool calls appear to account for much of the improvement. A simple instruction to keep trying tools achieves comparable gains at lower inference cost.
3.1 Manual Analysis of Successful Scenarios
- On successful scenarios, H-EPM suggested the correct tool in only 30% of decisive turns, while agents called the necessary tool themselves in another 50%.The remaining 20% were insufficient-information cases.Source: §3.1 · p. 3
3.2 Ablation Study
- Across conditions, scenarios flipped from failure to success showed larger increases in tool calls; under H-EPM, they made about twice as many calls as Base.This pattern motivates the hypothesis that attempting more tool calls, rather than tool-graph guidance, accounts for much of the gain.Source: §3.2 · p. 3
- Base + instruction adds almost no LLM calls and outperforms H-EPM on two of three models, supporting comparable gains at much lower inference cost.The instruction encourages trying available tools before giving up, without a tool graph.Source: §3.2 · p. 3
4 Towards Better Memory Structure
Even when the correct next tool is supplied, failures persist beyond tool selection, motivating situation-level guidance. Insight memory distills such guidance from episodic summaries and generally outperforms tool graph memory with lower inference cost.
4.1 Lessons from Tool Graph Memory
- Under oracle suggestions, tool-selection errors fall to 4% of failures, while call-necessity, dependency, and argument errors account for the rest.The remaining failures concern what to do in a situation rather than which tool to call next.Source: §4.1 · p. 4
4.2 Insight Memory
- Insight memory is built by clustering H-EPM episodic summaries, distilling situation-specific advice, and adding relevant insights to the prompt at each turn.It uses the same episodic experience as tool graph memory but provides guidance in a different form.Source: §4.2 · p. 4
- Insight performs best in most settings, has significant gains over Base in more settings than either tool graph memory, and keeps LLM calls close to Base.It uses fewer tokens than H-EPM across models and recovers most scenarios where H-EPM degrades.Source: §4.2 · p. 4
- Combining Insight with H-EPM performs worse than Insight alone on seven of nine models and requires 2.68× as many LLM calls.Insight plus instruction performs best among conditions without the correct next tool on all three tested models.Source: §4.2 · p. 4
5 Conclusion
The conclusion argues that next-tool prescriptions do not provide all the guidance agents need in multi-turn tool use. Situation-level semantic guidance from the same experience performs better than tool graph memory at almost no additional LLM calls.
5 Conclusion
- Random or absent tool suggestions retain most of tool graph memory’s gains, and correct suggestions still leave failures such as not calling a needed tool.Insight memory instead distills situation-level guidance from the same experience and outperforms tool graph memory at almost no additional LLM calls.Source: §5 · p. 4
- The results suggest semantic memory offers a better performance–cost trade-off by informing decisions rather than prescribing the next tool.The conclusion frames this as a supported implication of the reported outcomes.Source: §5 · p. 5
Limitations
The analysis focuses on tool graphs whose nodes are tools and whose edges are transitions; broader graph memories are outside its target scope. Insight memory is deliberately lightweight, and the explanatory analyses are narrower than the overall evaluation.
Limitations
- The analysis targets tool-node, tool-transition graphs, not graph memories that also represent states, arguments, or other entities.The authors suggest situation-level insights may help richer graph memories, but those are beyond the analysis’s scope.Source: Limitations · p. 5
- Insight memory was kept lightweight rather than optimized, using an untrained encoder and standard K-means with K chosen by silhouette score.Its construction adds clustering and LLM-based extraction to episodic summaries as a one-time offline cost; richer experience and other extraction strategies remain for future work.Source: Limitations · p. 5
- The overall evaluation spans two benchmarks and multiple models, but the ablations and manual analyses focus on three ToolSandbox models.Those models were selected to cover two larger gains and one decrease; the qualitative pattern was consistent across them.Source: Limitations · p. 5
A.1 Benchmarks and Evaluation
The evaluation uses ToolSandbox and multi-turn BFCL-v4 tasks with specified success criteria and held-out test sets. A GPT-4.1 user-simulator variant also compares memory methods with Base on ToolSandbox.
A.1 Benchmarks and Evaluation
- ToolSandbox has 1,032 scenarios across 34 tools and 11 domains; a scenario succeeds when its milestone score exceeds 0.55.The 825/207 training/test split is used for evaluation.Source: §A.1 · p. 7
- BFCL-v4’s multi-turn subset contains 800 tasks across eight APIs, with 160 held-out test tasks and correctness checked at every turn.All four variants of 40 tasks are held out so no underlying task is shared with training.Source: §A.1 · p. 7
- With GPT-4.1 as the user simulator for construction and evaluation, Insight scores highest on both Qwen3-8B and gemma-4-E4B-it, while ToolNet and H-EPM are not significantly above Base.Table 3 covers 207 ToolSandbox scenarios; its Δ values are computed against Base before rounding.Source: §A.1 · p. 7, Table 3 · p. 7
A.2 Implementation Details
The implementation builds memories from training rollouts and uses the agent model for H-EPM’s additional calls and insight extraction. Insight memory clusters episodic summaries, distills cluster-level guidance, and retrieves relevant insights during each model call.
A.2 Implementation Details
- H-EPM adds a summarization tool whose calls count as LLM calls; training memories use three rollouts per scenario, retaining the highest-scoring or shortest tied rollout.H-EPM’s additional calls and insight extraction use the agent model itself.Source: §A.2 · p. 7
- The agent models span nine open-weight systems from Qwen, Gemma, Mistral, and gpt-oss, from 2B to 120B parameters, plus GPT-4.1 and GPT-5.1 frontier models.The open-weight models use greedy decoding and are served with vLLM on a single NVIDIA H200 GPU.Source: §A.2 · p. 7
A.3 Insight Memory Details
- Insight memory uses H-EPM episodic summaries, including failed trajectories, to distill what to do and avoid for each cluster; its experience source differs from tool graph memory’s successful trajectories.Summaries are available for 7%–26% of ToolSandbox training scenarios, depending on the model.Source: §A.3 · p. 7
- Summaries are embedded and K-means clustered, with K selected by silhouette score; the agent model extracts insights from each cluster using the Figure 4 prompt.K is chosen from 15 candidates between 5 and 150, subject to clusters averaging more than three summaries.Source: §A.3 · p. 7, Table 4 · p. 8, Figure 4 · p. 8
- At each model call, the five most recent messages are matched to summaries, and insights from the clusters of the two closest summaries are added to the system prompt.Source: §A.3 · p. 7
B Full Results
The full-results appendix presents performance, significance, pass-rate, and cost views, alongside frontier-model results. It also measures the latency of insight retrieval separately from end-to-end generation.
B Full Results
- Tables 5–8 cover frontier-model scores, per-model scores with significance tests, pass rates, and inference costs; Figure 5 plots LLM calls per scenario relative to same-model Base.The figure’s Average bars give ratios of the nine-model averages.Source: B Full Results · p. 8, Table 5 · p. 8, Figure 5 · p. 8
- Insight retrieval’s full path has a median latency of 15–17 ms per turn and p95 latency of 29–39 ms across the three measured models.The measurements cover 1,295–1,494 turns per model and isolate retrieval overhead rather than end-to-end latency.Source: B Full Results · p. 8
- Embedding accounts for nearly all retrieval latency, compared with median LLM-call latencies of 0.4–1.1 seconds in the same runs.Source: B Full Results · p. 8
C.1 Manual Analysis
The analyses examine when suggestions help or mislead, how tool-call changes relate to outcomes, and which failures persist despite an oracle. They also show examples of insight memory recovering degraded scenarios across failure modes.
C.1 Manual Analysis
- On Mistral-Small-3.2-24B, authors manually inspected full trajectories for each of three run pairs per scenario, labeling suggestion correctness and whether the next call followed it; this yielded 30 improved scenarios (86 turns) and 15 degraded scenarios (43 turns).Source: §C.1 · p. 10
- In insufficient-information cases, an irrelevant tool call may still count as success when it is not a minefield, although the agent should recognize the task cannot be completed.Source: §C.1 · p. 10
C.2 Control Conditions
- Table 10 details the control-condition components, which the authors verified against logged requests for every run.Source: §C.2 · p. 10, Table 10 · p. 11
C.3 Tool Calls in Flipped Scenarios
- D is positive in all 27 comparisons of added tool calls in helped versus both-fail scenarios, and every comparison remains significant after Holm correction.The analysis excludes insufficient-information scenarios and tests whether the difference is greater than zero.Source: §C.3 · p. 11, Table 9 · p. 11
D Failure Analysis and Insight Memory
- Failure analysis assigns at most two dominant modes per scenario: call necessity, tool selection, dependency, and argument, in that decision order.Scenarios differing only in the final reply are excluded.Source: D Failure Analysis and Insight Memory · pp. 11–12
D.1 Oracle Failure Classification
- With oracle tools, failures persist in all dependency cases and most call-necessity and argument cases, even when the correct tool is suggested.The classification excludes 10 failures attributable only to the final reply.Source: §D.1 · p. 12, Table 11 · p. 12
D.2 Examples of Failure Modes
- For ToolNet on Mistral-Small-3.2-24B, seven degraded scenarios fail by call necessity and two by argument; five call-necessity cases omit a required tool.Source: §D.2 · p. 12
D.3 Insight Examples
- Insight memory recovers 22 of 29 scenarios degraded by H-EPM across all four failure modes, with examples addressing missing content, timestamp bounds, and date assumptions.Source: §D.3 · p. 12
D.4 Additional Analyses
Additional analyses find that Insight memory + H-EPM failures often involve following suggestions to unrelated tools or giving up, and that moving the insight block does not remove the degradation. ExpeL performs similarly to Insight and above both tool graph memories; the authors also describe their use of AI assistants.
D.4 Additional Analyses
- Failures when Insight memory succeeds but Insight memory + H-EPM fails most often involve unrelated-tool suggestions or giving up after suggestions.The recurring modes are tool selection and call necessity; none is attributed to an insight alone.Source: §D.4 · p. 12
- Moving the insight block after the suggestion line still leaves Insight memory + H-EPM below Insight memory alone.The result indicates that the degradation does not depend on where the block is injected.Source: §D.4 · p. 12, Table 12 · p. 12
- ExpeL performs similarly to Insight and above both tool graph memories on ToolSandbox.Unlike Insight, ExpeL injects its full rule set and two few-shot trajectories per task, while Insight retrieves insights from matching clusters.Source: §D.4 · p. 12, Table 15 · p. 14
E Use of AI Assistants
- The authors used AI assistants to check code, write plotting scripts, and polish the writing; they reviewed the output and take responsibility for the paper.Source: E Use of AI Assistants · p. 14