🤖 AI

Workload-Aware Caching for Multi-Agent Systems

This paper introduces a workload-aware caching policy for multi-agent systems that leverages recomputation cost, DAG dependency count, and agent invocation frequency to significantly reduce latency and approach unbounded cache performance while maintaining accuracy across diverse benchmarks.

Original authors: Anas Mohamed, Kaizan Haque, Azal Ahmad Khan, Chetan Sharma, Shuwen Ge, Ali Anwar

Published 2026-07-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anas Mohamed, Kaizan Haque, Azal Ahmad Khan, Chetan Sharma, Shuwen Ge, Ali Anwar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where solving a single complex problem isn't done by one super-smart brain, but by a team of specialized robots working together. In the field of artificial intelligence, this is called a "multi-agent system." Instead of one giant computer trying to do everything at once, you have a "planner" robot that breaks a big task—like analyzing a financial report or watching a movie—into a series of smaller steps. It then sends these steps to different "worker" robots: one might be an expert at reading text, another at spotting shapes in images, and a third at doing math. They pass their results down the line, like a relay race, until the final answer is ready.

The problem is that these robots are slow and expensive to run. Every time they do a step, it takes time and computer power. If you ask two slightly different questions, the robots often end up doing the exact same boring steps over and over again, like re-reading the same page of a book just because the question changed by one word. To fix this, engineers use "caching," which is like a sticky note on a fridge. If the robots have already done a step, they stick the answer on the note so they don't have to do it again. But here's the catch: the fridge (computer memory) is small. If you keep adding sticky notes, you have to throw some away. The big question is: which notes should you keep, and which should you toss? If you throw away the wrong one, you waste time re-doing a hard step. If you keep the wrong one, you run out of space for the useful stuff.

This is where a new study by researchers from the University of Minnesota, Google, and IIT Guwahati comes in. They realized that the old ways of deciding what to throw away were too simple. Traditional methods, like "Least Recently Used" (LRU), act like a strict librarian who only cares about when a book was last touched. If you haven't touched a book in an hour, they throw it out, even if that book contains the secret recipe for a cake you're about to bake. The researchers argue that in a team of robot workers, you need a smarter strategy. You shouldn't just look at when a note was used; you need to look at how hard it was to write, how many other robots need that note to finish their jobs, and how often that specific type of robot is being asked to work right now.

The team proposed a new "workload-aware" system that acts like a savvy manager. Instead of just checking a clock, this manager looks at three things before tossing a sticky note:

Recomputation Cost: How much time and energy would it take to redo this step? If a robot spent 8 seconds doing a complex math problem, that note is precious. If it spent 0.3 seconds on a simple lookup, it's easier to replace.
Dependency Count: How many other robots are waiting for this result? If one note is the foundation for four other steps, it's a "hub" and shouldn't be thrown away. If it's just a dead-end note that no one needs, it's safe to toss.
Agent Frequency: How busy is this specific type of robot? If the "image reader" robot is being called 120 times while the "text summarizer" is only called 20 times, the manager knows to keep the image notes safe because the workload is clearly focused on images right now.

By combining these three signals into a single score, the system decides which notes to keep. The researchers tested this idea on three different types of challenges: answering questions about slide presentations, digging through multi-page PDF documents, and analyzing video clips. They found that their smart manager was much better at keeping the right notes than the old, simple methods.

The results were impressive. In the best cases, their system cut the time it took to get an answer by up to 64.7% compared to having no cache at all. Even when compared to the next-best smart system, they still saved an average of 31.1% in time. Perhaps most importantly, they showed that it's not just about how many times you hit the cache (the "hit rate"), but what you keep in there. Their system was so good at keeping the expensive, important notes that it performed almost as well as if the team had an infinite amount of memory, all while using a fixed, limited amount of space.

The study also checked if this new method played well with other tricks, like having robots work in parallel or reusing entire plans. They found that these techniques are like different tools in a toolbox; they don't fight each other but actually help each other out. The workload-aware caching handles the "don't re-do the hard math" problem, while parallel execution handles the "let's do two things at once" problem. Together, they make the whole team of robots much faster and more efficient.

In short, the paper suggests that by giving the cache manager a little bit of "common sense" about the work being done—knowing which steps are expensive, which are central to the plan, and which are currently popular—we can make AI teams significantly faster without needing more expensive computers. It turns a simple storage problem into a smart resource management game, ensuring that the most valuable work is never lost to a crowded fridge.

Technical Summary: Workload-Aware Caching for Multi-Agent Systems

Problem Statement

Multi-agent systems (MAS) are increasingly decomposing complex tasks into Directed Acyclic Graphs (DAGs) of specialized agent executions. While this architecture enables sophisticated reasoning, it introduces significant efficiency challenges. Redundant computations occur frequently when different queries share common computational patterns (e.g., retrieving financial statements for different companies or parsing similar document structures).

Traditional cache eviction policies, such as Least Recently Used (LRU) or Least Frequently Used (LFU), treat all cached entries uniformly based solely on access history. This approach fails to account for three critical signals unique to agentic environments:

Structural Importance: The topological position of a node within a DAG (i.e., how many downstream tasks depend on it).
Computational Cost: The heterogeneity in recomputation costs across different agent types (e.g., an 8-second OCR operation vs. a 0.3-second lookup).
Workload Patterns: The frequency of specific agent invocations across a query stream, which indicates the likelihood of future reuse.

Consequently, standard policies may evict high-value, expensive-to-recompute nodes in favor of recently accessed but structurally insignificant or cheap-to-recompute entries, leading to suboptimal latency and resource utilization.

Methodology

The authors propose a workload-aware eviction policy that integrates these three signals into a unified scoring function to determine which entries to retain under memory constraints.

1. Scoring Function

The policy assigns a "keep score" to each cached task $t_i$ based on:
$\text{score}(t_i) = w_{dep} \cdot D(t_i) + w_{cost} \cdot \tau(t_i) + w_{freq} \cdot f(a(t_i))$

Where:

$D(t_i)$ (Dependency Count): The number of downstream tasks that consume the result of $t_i$ . A higher count indicates broader utility across the DAG.
$\tau(t_i)$ (Recomputation Cost): The observed execution time of the task. This ensures expensive operations are protected from eviction.
$f(a(t_i))$ (Agent Invocation Frequency): The cumulative count of invocations for the specific agent type $a$ across the processed workload. This prioritizes agents central to the current workload focus.
$w$ weights: Non-negative weights ( $w_{dep}, w_{cost}, w_{freq}$ ) that balance the contribution of each signal.

2. Implementation

The system maintains cached entries in a min-heap ordered by this keep score. When the cache capacity is exceeded, the entry with the lowest score (fewest dependents, lowest cost, least frequent agent) is evicted. This allows the system to make principled eviction decisions that minimize the expected cost of future cache misses.

Key Contributions

The paper outlines four primary contributions:

C1: Workload-Aware Eviction Policy: A novel policy for MAS that combines recomputation cost, DAG dependency count, and agent invocation frequency to optimize cache utility.
C2: Empirical Evaluation: Comprehensive testing across three diverse benchmarks (SlideVQA, MP-DocVQA, VideoMME) demonstrating consistent improvements in latency, throughput, and accuracy over standard baselines.
C3: Eviction Quality Analysis: Evidence that the quality of eviction decisions (avoiding expensive misses) is a primary driver of latency gains, often more so than raw hit rates in heterogeneous workloads.
C4: Agentic Optimization Study: An investigation showing that workload-aware caching is complementary to other optimization techniques, specifically plan-level caching and parallel agent execution.

Experimental Results

The policy was evaluated against standard baselines (LRU, LFU, FIFO, ARC) and an uncached baseline across three benchmarks with varying reuse regimes.

Latency Reduction: The workload-aware policy reduced latency by up to 64.7% relative to the uncached baseline. On average, it achieved a 31.1% latency reduction compared to the next best finite-capacity baseline (LFU).
Performance vs. Unbounded Cache: Despite operating under a fixed memory budget (50% of the working set), the policy approached the performance of an unbounded cache, achieving latency within 1.8% to 3.4% of the theoretical upper bound on SlideVQA and MP-DocVQA.
Throughput: The system achieved up to a 2.84× improvement in throughput over the uncached baseline.
Accuracy: The policy maintained accuracy on par with or exceeding all competing finite-capacity methods, avoiding the accuracy degradation seen in semantic caching approaches (like GPTCache) that rely on approximate matches.
Eviction Cost Analysis: The study revealed that while hit rate differences were sometimes modest, the cost of evicted items was significantly lower with the proposed policy. Other methods frequently evicted expensive nodes (e.g., frame extraction), whereas the workload-aware policy preserved them, resulting in lower overall query latency.

Significance and Claims

The paper claims that the significance of this work lies in shifting the paradigm of cache management from access-history-based heuristics to structure- and cost-aware decision making.

Quality over Quantity: The authors argue that in heterogeneous agentic workloads, the quality of what is kept in the cache is as critical as the hit rate. By selectively retaining expensive and structurally central nodes, the policy converts moderate hit rate advantages into substantial latency savings.
Complementarity: The work demonstrates that workload-aware content caching addresses a distinct bottleneck (redundant node-level recomputation) compared to plan-level caching (planning overhead) and parallel execution (scheduling). These techniques are mutually reinforcing and can be combined for further efficiency gains.
Generalizability: The approach is robust across different model families (Qwen2.5 and Mistral) and diverse workload structures, from high-reuse document analysis to low-reuse video understanding.

The authors conclude that as multi-agent systems scale, leveraging signals unique to DAG-based execution environments—specifically topology, cost, and workload patterns—is essential for efficient resource utilization.