RebaseKV: Hiding Prefill Latency in Multi-Agent LLMs via Optimistic Cache Alignment

Multi-agent large language model (LLM) systems repeatedly invoke the same model over prompts that are largely overlapping but not prefix-identical. Consecutive agents often share the user question, prior agent responses, and common workflow structure, yet small changes in agent-specific instructions mutate the prompt prefix and prevent standard prefix-based KV cache reuse. As a result, each agent transition may require a full prefill before emitting the first token, creating a significant time-to-first-token (TTFT) bottleneck in latency-sensitive LLM applications. We introduce RebaseKV, a training-free serving architecture that reduces this bottleneck through Optimistic Cache Alignment. RebaseKV is motivated by a key asymmetry in LLM serving: the dichotomy between memory-bandwidth-bound autoregressive generation and compute-bound parallel processing. While the prefill phase can process many prompt tokens in parallel, autoregressive decoding advances sequentially and often underutilizes available compute. Instead of waiting for the next agent’s exact prompt cache to be fully materialized, RebaseKV begins foreground generation using context-misaligned cache states inherited from previous agents, while asynchronously constructing the exact cache for the new agent prompt in the background. Once the background cache is ready, RebaseKV aligns the foreground generation state with the exact prompt state and continues standard decoding from a context-consistent cache. This design avoids relying on complex deep-layer KV correction, online offset estimation, or selective layer rectification. Rather than making stale cache states permanently correct, RebaseKV uses them only as a temporary latency-hiding mechanism during the initial response prefix. We evaluate RebaseKV across multi-agent LLM workflows and report TTFT, end-to-end latency, and final-answer accuracy. Our results show that Optimistic Cache Alignment can substantially reduce perceived prefill latency while maintaining answer-level accuracy, offering a practical serving strategy for low-latency multi-agent LLM inference beyond exact prefix caching.