Workload-Aware Caching for Multi-Agent Systems
For developers of multi-agent systems, this work provides a practical caching method that significantly reduces latency without sacrificing accuracy, addressing a known bottleneck in agentic execution pipelines.
The paper proposes a workload-aware cache eviction policy for multi-agent systems that uses recomputation cost, DAG dependency count, and agent invocation frequency to prioritize cached entries. It reduces latency by up to 64.7% over uncached baselines and 31.1% over the next best finite-capacity baseline, approaching unbounded cache performance.
Multi-agent systems decompose complex tasks into directed acyclic graphs (DAGs) of specialized agent executions, creating natural opportunities for caching intermediate results across queries. However, existing cache eviction policies treat all cached entries uniformly based on access history, ignoring structural and workload signals uniquely available in agentic execution environments. We present a workload-aware eviction policy that combines three signals, namely recomputation cost, DAG dependency count, and agent invocation frequency, into a unified scoring function that retains the most valuable entries under memory constraints. Evaluated across three multi-agent benchmarks spanning diverse reuse regimes, our policy reduces latency by up to 64.7% relative to the uncached baseline and achieves on average a 31.1% latency reduction over the next best finite-capacity baseline, while approaching the performance of an unbounded cache and maintaining accuracy on par with or exceeding all competing finite-capacity methods. We further show that workload-aware content caching is complementary to other agentic system optimization methods, including plan-level caching and parallel agent execution, with each technique targeting a distinct efficiency bottleneck in multi-agent pipelines.