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

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.