Is Tool Graph Memory Overrated? Multi-Turn Tool Calling Study Reveals the Truth

Tool Graph Memory: A Component with High Hopes but Mediocre Performance

When large language model (LLM) agents execute complex tasks, they often need to call external tools across multiple turns. To help agents choose tools more "intelligently," researchers proposed Tool Graph Memory — storing past experience as a tool transition graph to guide subsequent tool selection. The idea sounds reasonable: remember which tool combinations worked before, and reuse them directly when similar tasks arise.

But a recent study throws cold water on this approach. The research systematically evaluated Tool Graph Memory across nine models and two benchmarks, finding that it rarely significantly outperforms baselines; even when it does improve results in certain scenarios, the cost is more than double the number of LLM calls.

This means we may have been paying excessive attention to a component with limited effectiveness and high costs.

Tool Graph Memory's "graph" refers to a graph structure where nodes represent tools and directed edges represent historical transition relationships of "moving from tool A to tool B within a task." Such memory is typically automatically extracted and accumulated by agents from historical task trajectories, forming an ever-expanding directed graph; when a new task arrives, the system retrieves the most frequent or highest-scoring successor tools in the graph based on currently called tools as recommendations. It belongs to a type of "experiential memory" or "episodic memory," and unlike parametric knowledge, it is an externally retrievable store. Such structures were widely borrowed in early agent frameworks (such as ReAct and Reflexion-based tool calling schemes), because graph structures naturally suit expressing compositional dependencies and calling sequences between tools, and are also convenient for path retrieval and recommendation. Its implicit assumption is: there exist stable transition patterns in tool usage, and these patterns are transferable across tasks. This paper's critique targets precisely this assumption.

Where Do the Gains Come From? Random Guidance Also Captures Most Benefits

The most striking finding in the study is the decomposition of "gain sources."

If Tool Graph Memory truly provides effective guidance, its suggestions should be more valuable than random suggestions. But experimental results show the opposite: random guidance, or even no guidance at all, retains most of the performance gains. This anomalous phenomenon points to an awkward conclusion — the benefits of Tool Graph Memory mainly come from extra computation, not the memory content itself.

In other words, the agent running a few more rounds and calling the model a few more times may itself improve performance, with little relation to whether tool transition graphs were stored. This is a typical case of "computation for performance," and Tool Graph Memory just happens to come with this computation process.

Worse, the guidance given by memory is often wrong. When the guidance itself is unreliable, its help to the agent becomes even more questionable.

Random guidance serves here as a key control condition: providing the agent with tool suggestions randomly drawn and unrelated to the current task, with all other processes identical to Tool Graph Memory. If performance gains are largely retained under random guidance, it indicates that the gains do not stem from the "correctness" of suggestions, but from the additional reasoning steps and tool-calling rounds triggered by the act of being guided. This phenomenon is called compute confound in evaluation — the method being evaluated often consumes more tokens or more rounds than the baseline, making performance differences unattributable to the method itself. Therefore, rigorous agent research needs to match compute budgets (such as limiting maximum call counts or token counts), or at least report call counts and latency. This paper uses two control groups — random guidance and no guidance — precisely to disentangle the contribution of "memory content" from that of "extra computation," which is the core of its methodological value.

Even with Correct Next-Tool Prediction, Failures Persist

The study also reveals a deeper problem: failures do not occur only at the tool selection stage.

Experiments show that even when the system correctly suggests the next tool to call, many tasks still fail. Failure modes include giving up directly, not initiating any tool calls, and more. This indicates that the bottleneck in multi-turn tool use is not just "which tool to choose," but also involves more complex decisions such as whether the agent is willing to act and how to orchestrate multi-step processes.

Designing memory as prescriptive instructions (prescription) of "which tool to use next" may have been the wrong direction from the start. What agents need may not be precise next-step instructions, but more flexible prior knowledge.

Prescription and soft prior are two different ways of using memory. Prescription directly tells the model "the next step must call tool X," equivalent to imposing constraints in the decision space; soft prior only provides倾向性 hints, such as "in similar situations, tool X is usually helpful," with the final decision still made by the model combining the current context. When memory is injected as prescription, if the recommendation does not match the current subtask, the model may be forced to execute invalid calls, or even abandon the entire task due to instruction conflicts — this is one possible mechanism behind the experimental observation that "correct next-tool prediction still fails." The deeper reason is that the bottleneck in multi-turn tool use lies not only in tool selection, but also in decisions such as whether to initiate action, how to orchestrate multi-step processes, and when to terminate. Soft prior preserves the model's autonomy in these aspects, and thus better adapts to the uncertainty of real tasks.

Textual Insights Outperform Graph Memory: Almost No Extra Calling Cost

Since Tool Graph Memory performs poorly, is there a better alternative?

The study gives a simple yet effective answer: storing the same experience as textual insights performs better than Tool Graph Memory, and adds almost no extra LLM calls.

This comparison is compelling. The same past experience, stored and expressed differently, yields better results at lower cost. The advantage of textual insights is that they are more flexible and general — they do not hard-require what to do next, but provide a soft reference, letting the model judge for itself based on the current situation.

This points to a key design principle: memory is better suited as a soft prior rather than a prescription of the next tool. Soft priors allow the model to flexibly adjust in specific situations, while hard prescriptions may mislead the model when inapplicable.

Implications for Agent Memory Design

The significance of this study goes beyond refuting a specific method; it provides a methodological example for evaluating memory mechanisms.

When we introduce some memory or retrieval mechanism into an agent, we need to strictly distinguish: does the performance improvement come from the memory content, or from extra computational overhead? Only through control experiments such as random guidance and no guidance can we isolate the true contribution of memory.

At the same time, the study reminds us to pay attention to the form of memory expression. For storing experience, a structured tool transition graph sounds more "intelligent," but textual insights are反而 more effective and economical. This may mean that in agent design, simplicity and flexibility often outperform complex structured representations.

For developers building multi-turn tool calling systems, the practical value of this study is: before investing resources in implementing Tool Graph Memory, try storing experience in text form first — you may achieve better results at lower cost.

One-line Summary

Research shows Tool Graph Memory has limited gains and doubled costs, with benefits mainly from extra computation; textual insights are better.

Paragraph Summary

This study systematically evaluated Tool Graph Memory across nine models and two benchmarks, finding it rarely significantly outperforms baselines and brings more than double the LLM calling cost. Through random guidance and no-guidance controls, the study reveals that performance gains mainly come from extra computation rather than memory content, and the guidance given by memory is often wrong. Even with correct next-tool prediction, tasks still frequently fail, indicating that the bottleneck is not only tool selection but also whether to act and multi-step orchestration. The study further shows that storing experience as textual insights outperforms Tool Graph Memory and adds almost no calling cost. The conclusion is that memory should serve as a soft prior rather than prescriptive instructions for the next tool.