Rethinking the Role of Tool Graph Memory in Multi-Turn Tool Use
Uiji Hwang, Richeng Xuan and Taeuk Kim (Hanyang University and Tencent Hunyuan) test tool graph memory, which stores past tool-to-tool transitions to guide which tool an agent calls next, and find that it rarely helps and that its gains come from extra LLM calls.
Ask this paper
Scope. The evaluation covers nine models and two multi-turn tool-use benchmarks.
Main result. Tool graph memory seldom improves significantly over baselines, and where it does, it costs more than twice the LLM calls.
Ablation. The memory's suggested next tool is often wrong, and random guidance or no guidance keeps most of the gain. The improvement comes from the extra computation, not from the stored transitions.
Remaining failures. Even when the correct next tool is suggested, many episodes still fail, for example by giving up without calling any tool.
Better alternative. Storing the same experience as textual insights outperforms tool graph memory with almost no extra LLM calls, which suggests memory works better as a soft prior than as a prescribed next action.
Abstract
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.