acceptodds
Under review as a conference paper at ICLR 2027

Millisecond-Level Tool-Call Prediction for LLM Agent Cache Acceleration

Abstract

LLM agents complete tasks by iteratively invoking external tools, and every call exposes hundreds of milliseconds of network and execution latency. We propose a graph neural network (GNN) next-tool-call predictor that drives cache prefetching: each prediction costs milliseconds on CPU with zero LLM tokens, meeting both the latency budget and the context-sensitivity requirement of online prefetching. Existing predictors satisfy only one of the two. Millisecond trajectory-statistics predictors (k-gram mining, smoothed Markov chains) fit the budget but read only historical call patterns, never the conversation, so they cannot tell apart the next calls implied by the same tool sequence under different intents. Context-aware LLM speculators model the dialogue, but each step costs seconds of GPU inference and every extra candidate needs a fresh generation, making a full-candidate ranking within budget—a prerequisite of tiered prefetching—impossible. Our predictor runs on a global tool graph of tool and semantic-state nodes whose transition edges embed statistical transition probabilities; the conversational state (request, executed calls with truncated results, current user message) is encoded by a single sparse BM25 encoder into a context vector, the historical tool-embedding sequence by a GRU into a state vector, and both are injected into a relational graph convolutional network (R-GCN). Candidates are scored by a context-aware node head and a conditional edge head, additively fused with a Markov prior as low-frequency fallback, and the top-K tools receive tiered prefetch. On public agent trajectories, our method attains 80.20±1.61% and 84.89±0.49% top-1 on the two τ-bench retail actors (GPT-4o and Claude 3.5) of Speculative Actions and 65.39±10.17% on APIGen-MT, corresponding to 1.79–2.09× cache speedup. Ablations validate the fusion design: transition statistics, Markov prior, and context-conditioned GNN together adapt to both prediction regimes.

Primary area:
foundation or frontier models, including LLMs
Keywords:
tool call prediction, cache prefetching, graph neural network, LLM agent acceleration, boundary conditions

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_rWVpOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how to predict the next tool an LLM agent will call, so that the system can prepare this tool early and hide its latency. The authors build a global tool graph with tool nodes and semantic state nodes, and the transition edges store counts from training trajectories. The session text is encoded by BM25, the past tool sequence is encoded by a GRU, and both vectors are added into every layer of a two-layer R-GCN. A node head, an edge head with transition statistics, and a Markov prior are summed to rank the candidates, and the top tools receive tiered prefetch. On two τ-bench retail sets and APIGen-MT, the method reports 65% to 85% top-1 accuracy and 1.79x to 2.09x simulated speedup, and it beats rerun k-gram, smoothed Markov, and LLM speculator baselines. Ablations on ToolBench and τ-bench study the role of the transition features and of each input source.

Critical strengths

Strength 1. The paper targets a real gap in agent serving. Count-based predictors are fast but ignore the conversation, while LLM speculators read the conversation but cost seconds per step. The proposed model ranks all candidates with context at 18 ms and with no LLM calls, which makes tiered prefetch possible, and this is the main reason I see value in the work.

Strength 2. The evaluation is more careful than is common in this area. The authors rerun the baselines on the same test split, give the LLM competitors full history, and also compare methods inside the same Markov candidate set in Table 3. This in-set test shows a gain of 20 to 25 points over counting, which supports the claim that context helps beyond the previous tool.

Critical weaknesses

Weakness 1. The speedup claims rest on a simulator with fixed savings of 60% and 20% and a fixed 50 ms penalty, not on measured tool latencies. Under these rules, the speedup is mostly a direct function of top-1 accuracy, so it adds little new evidence about real benefit. In addition, the model predicts only tool names and not arguments, so it is unclear what heavy prefetch can actually do in practice compared with PASTE or Speculative Actions, which run full calls.

Weakness 2. Several design choices seem to be tuned on the test data. Section 3.4 says the best epoch is chosen by AUC on the evaluation split, which appears to be the shared test set, and Table 6 shows that early stopping alone adds 5.4 points. The window k, the learning rate, the truncation length, and the vocabulary repair also have large effects, and with only three seeds and a standard deviation of 10.17 on APIGen, I think the reported margins may be optimistic.

Questions for authors

Is the evaluation split used for epoch selection and early stopping the same as the test split in Table 2? If it is, what are the results when a separate validation split is used for selection?

What exact operations does heavy prefetch perform when only the tool name is known and the arguments are not? (Suggestion) How do the speedups change when measured tool latencies from a real serving system are used?

BUTTONInstruct is listed in Table 1, and ToolBench appears only in the ablations. Why are their main top-1 accuracy and speedup results not reported in Table 2?

Reviewer_samdOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper presents CT-GNN, a lightweight GNN framework for predicting future tool calls to accelerate LLM agent execution through cache prefetching. The method combines BM25-based conversational context encoding, GRU-based tool sequence modeling, and relational graph convolution over a global tool graph, incorporating transition statistics and a Markov prior to rank candidate tools. The predicted tools are used for tiered prefetching to reduce tool execution latency. Experiments on public agent trajectories from τ-bench and APIGen-MT compare CT-GNN against statistical predictors, LLM-based speculators, and tool-planning baselines. The authors report top-1 prediction accuracies of 80.2%, 84.9%, and 65.4% across three evaluation settings, with an average CPU prediction latency of 18.1 ms per step and simulated cache speedups of 1.79–2.09×.

Critical strengths
  • This work addresses a practically relevant problem of reducing tool execution latency in LLM agents. The proposed lightweight GNN-based predictor achieves promising next-tool prediction accuracy with low CPU inference overhead (18.1 ms per step). The experiments also provide useful comparisons against statistical and LLM-based predictors, with ablations demonstrating the benefits of incorporating conversational context and transition statistics.
Critical weaknesses
  • The reported 1.79–2.09× cache speedups are based entirely on a synthetic latency simulator, which assumes fixed latency reductions of 60% and 20% for heavy and light prefetching, respectively. However, the proposed model only predicts tool names rather than complete tool calls with arguments, raising questions about how much actual tool execution can be accelerated through such prefetching. Without e2e measurements on a real agent-serving system, the practical acceleration benefits remain largely unvalidated.
  • Section 3.4 explicitly states that candidate-ranking AUC is evaluated on the "evaluation spli" after each epoch for checkpoint selection and early stopping. However, the paper does not clearly distinguish this split from the final test set used to report the results in Table 2. If the same evaluation instances are used for both model selection and final reporting, the reported prediction accuracy and simulated speedups may be optimistically biased.
Questions for authors
  • Could the authors clarify whether a separate validation split was used for early stopping, and confirm that the final reported results were obtained on an untouched test set?
Reviewer_3GXsOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes CT-GNN (Conditional-Transition Graph Neural Network), a lightweight next-tool-call predictor for LLM agent prefetching. It injects session context (BM25) and tool-sequence features (GRU) into a relational graph convolution over a global tool graph, then combines node and edge scores, explicit transition-statistics features, and a Markov prior to rank retrieved candidates. The authors report roughly 18.1 ms per step on CPU, measured on τ\tau-bench, with zero LLM tokens, providing a signal for tiered prefetching without GPU inference. They report top-1 tool-name accuracies of 80.20%, 84.89%, and 65.39% on two τ\tau-bench retail actor datasets (GPT-4o / Claude 3.5) and APIGen-MT, respectively, together with simulated cache speedups of 1.79–2.09× under a synthetic latency and preparation model. The paper also includes a boundary-condition analysis (context-conditioned vs. near-Markovian regimes) and a reverse evaluation of GTool as a prefetcher.

Critical strengths

The paper targets a useful accuracy–latency tradeoff between inexpensive transition-counting baselines and the additional inference cost of LLM-based speculators. CT-GNN combines conversational context with millisecond-level CPU prediction without requiring access to the agent's internal model states, and the motivation is sound. The ablation studies show that the components do not contribute uniformly: in the ToolBench restricted-candidate ablation (Table 5), explicit transition-statistics features change the gap relative to Markov from −8.0 pp to +1.0 pp, while adding the Markov prior without these features narrows the gap to −2.1 pp. This decomposition of “what actually matters” is more informative than aggregate accuracy alone.

Critical weaknesses
  1. The contribution of graph modeling and the comparison with graph-based planners need clearer support. GNN4Plan (NeurIPS 2024) already uses GNN representations for graph-constrained retrieval of tools corresponding to LLM-decomposed steps. Section 2.1 distinguishes long-horizon planning from online prefetching, but provides only a brief architectural comparison and no GNN4Plan-style experimental baseline. CT-GNN also restricts its candidates through semantic retrieval and graph expansion (§3.4), so the distinction is not simply constrained selection versus unrestricted ranking. More directly, the current ablations do not isolate the contribution of graph message passing from context and transition-statistics inputs using a matched non-graph predictor. The GTool reverse evaluation is informative, but its APIGen result does not by itself establish the claimed necessity of online step-by-step prediction (§4.4 and §5): feedback availability and the reported token-budget truncation are not separately controlled. The conclusion should be limited to the evaluated one-shot configuration unless a controlled comparison isolates the effect of online feedback updates.
  2. The acceleration claim depends on unvalidated preparation and timing assumptions. The simulator assigns 60% latency savings to a heavy hit, 20% to a light hit, and a 50ms penalty to a wrong heavy target (§3.4). Tool-name prediction can plausibly enable the connection and sandbox preparation described in the paper, but the paper does not establish that these fixed savings are attainable within the available preparation window. Although the GTool comparison explicitly waives inference cost, the manuscript does not provide a sufficiently complete, unified timing model to reconstruct how predictor execution, unfinished preparation, and inference-cost waivers are handled across all methods. The authors acknowledge the synthetic model in Section 5, but the current evidence establishes a model-dependent cache benefit rather than the reported magnitude of practical agent acceleration.
Questions for authors
  1. Which preparation operations can be completed using only the predicted tool name, and what measured savings support the assumed 60% and 20% reductions? Please specify the available preparation window and how predictor latency, unfinished preparation, incorrect predictions, and any inference-cost waivers enter the speedup calculation for each method.
  2. On τ\tau-bench and APIGen-MT, how does CT-GNN compare with a lightweight non-graph predictor using the same BM25 context, tool history, transition statistics, candidate set, and training protocol? A matched ablation would help quantify the additional benefit of graph message passing. A GNN4Plan-style baseline would also help clarify the architectural contribution, provided its adaptation, online inputs, and any LLM decomposition cost are specified.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.