Reproducing Variance: Caching in Agentic LLM Pipelines

TL ; DR
When running experiments on agentic workflows – especially agents with multiple parallel LLM calls, caching breaks because LLMs are non-deterministic. What these workflows need is a caching mechanism that supports two contradictory behaviors: reproducibility and variance. We designed a cache key that encodes each LLM call’s position inside the pipeline to make it resistant to changes in the pipeline’s execution order. The result is cleaner and broader experiments: you can change one prompt and use cached results for the rest; A/B-test any component against identical upstream outputs; and run best-of-N inference without multiple branches collapsing to the same answer.

Caching in a non-deterministic world

You don’t need us to tell you that agents are difficult to evaluate due to some core characteristics. They’re:

• Complex (many processes, often parallel)
• Dynamic (their course of action is determined on the fly by LLMs)
• Long-running (sessions can take minutes or hours)
• Expensive

Caching, then, becomes go-to recourse for managing evaluation experiments. 

But here’s the catch (sorry): 

Caching was built for a deterministic world – same input, same output, every time. As non-deterministic entities, LLMs don’t play by these rules. You call the same model with the same prompt and you actually expect a different result. So much so that you can even control the degree of difference via temperature. 

And yet most of our engineering toolbox carries that deterministic assumption baked in. When you apply these constructs to LLMs without rethinking them, things break in ways that don’t look broken at first.

That’s exactly what happened in our research lab. Our algorithm developers – who were running agent evals – started reporting that “the cache is broken.” When our team of software engineers took a look, we understood that what was missing was a way to guarantee both reproducibility and variance in the cache for every run of an agent eval. So we built it. This blog details that path from problem to solution. 

Reproducing variance: Defining the problem

When we’re building and testing agents in our lab, we work with Maestro to optimize them at runtime. At inference time, it can utilize best-of-N sampling: generating N independent attempts at a task and returning the best one, so that the accuracy of the agent output isn’t degraded by the noisiness of any single LLM call. In addition to improving agent accuracy, that approach has also been instrumental for generating indicators of agent performance, such as variance estimations or the metric _Success@K_, as demonstrated in our previous post on how we topped the SWE-bench leaderboard. 

So it was concerning when we started getting messages like “the cache is broken!!” Looking closer, it became clear that the problem was more nuanced than that: Researchers were expecting reproducibility from the cache – but because of LLMs’ non-deterministic nature, running the same agent again recomputes – but doesn’t reproduce – results. So we were seeing things like:

When re-running an experiment, expecting unchanged prompts to be cached (cache hits) and the experiment to run quickly – but then getting different results (cache misses).

Expecting variance (cache misses) when running an experiment for success@K, but then getting the same result (cache hits). 

What our researchers needed was a mechanism that supports two different cache behaviors – reproducibility and variance – within the same pipeline, selectively deciding when to reuse results and when to recompute. If we could build that, we could unlock how to reproduce a best-of-N run.  

Diagramming contradictory cache behavior

To reproduce a best-of-N agent run, it would be ideal if we could just toggle on / off reproducibility.  

Reproducibility can be shown in the simplest example of caching behavior is two LLM calls with the same prompt – we can achieve that by turning on the cache toggle.

Another characteristic of an agentic workflow that we get for free here is LLM call composability – when the output of one LLM call is the input of another:

Best-of-N sampling, on the other hand, necessitates variance even within a single run. Here, every new Generate branch must miss; if two branches return the same result, it can’t really be said that the agent tried N times. 

So we’d have to toggle off reproducibility to get this variance – but then we still haven’t reproduced our best-of-N run. Our task is to solve the seemingly paradoxical question: How do you reproduce a best-of-N run when needed? If we could pull it off, it would look something like this:

Designing the cache key

At this point, it was clear that a simple on/off toggle wouldn’t be enough to achieve that delicate combination of reproducing variance. We would need to use the LLM API settings/parameters to design a cache key – the string attached to the LLM call which determines which calls share results and which don’t – that could fulfill those contradictory conditions. 

The cache key is significant because, besides a workable on/off toggle for reproducibility, it’s the only lever we have left available to affect the cache behavior.

Two core assumptions shaped our solution design:    

• We can attach a cache key to each LLM call
• A cache hit requires both the prompt and the cache key to match

For this process, we’ll refer to the “write me a poem” LLM call as the “generation” step, and the “Is <poem> a valid Haiku” as the “validation” step.

Attempt 1: Using the step name for the cache key

If we set it up so that the cache key just uses the step name, all three Generate branches can share the same key. So when reproducing, Generate₂ hits Generate₁’s cached result and so on. Three branches, one answer. This indicates that our cache key is not specific enough: We need a way to distinguish between the three different Generate calls.

Attempt 2: Step name + counter

One natural fix for making it easy to distinguish between calls: number each call as it finishes. Run 1 works perfectly – each generation branch receives a number. In the next run we can reuse the gen_0, gen_1, and gen_2 keys to reproduce this variance

Where this breaks is when we compose LLM calls on top of each other. Consider the following pipeline:

After the following run, the cache would now look like this:

The assignment of the key val_0 to the prompt containing poem 1 occurred only because its LLM call finished first. When we retrieve from cache, we might end up assigning the prompt containing poem 1 with the key val_1. In that case it will look like:

The cache will always spit out whichever key finishes first. But the finish order is unpredictable, so we need a cache key that can stay independent of that order, so that the prompt-response pairing survives no matter what sequence each prompt finishes in.

The fix: Encode graph position, not execution order

The breakthrough came when we realized that the cache key has to encode the composition the same way as the prompt does. The cache key for each point in the agent loop encodes where it sits in that flow: which step, which branch (run index), and which upstream outputs were consumed.

Now, when encoding this positionality, we can see that gen_0, gen_1, are now distinct: two different LLM calls, two different results. And when reproduced, the key val(gen_0) matches the prompt containing poem 1 regardless of finish order. As cache keys for validate and fix inherit their upstream identity, the whole branch stays correctly wired. We were finally getting closer to our original mapping of what reproducing a best-of-N run should look like. 

One more layer: Nested fan-outs

Before, we looked at generation branches that produce just one subsequent validation step. But what if each generation branch “fans out” to multiple validation steps in parallel? We would need a way to reproduce that behavior in order, preserving all of our lessons from previous attempts about timing and encoding positionality. 

Using the same counters as before we get: 

But this “global” way of counting the val keys creates the same timing inconsistency we had before! How can we ensure that val_0 and val_1 always land on gen_0 and never on gen_1?

To achieve this, the key index must be kept local – scoped to its upstream parent, rather than a global counter.

Lessons for cache keys that handle reproducibility and variance 

Rules for cache key construction

Through the attempts above, we can deduce three rules for constructing cache keys that support best-of-N, reproducibility, and nested fan-outs:

Rule 01: Every node’s key should include its step name
Two different steps (Generate vs. Validate) must never collide.

Rule 02. Every node’s key includes a run index, scoped locally to its upstream parent
Two “fan-out” (or parallel) branches of the same step should be assigned different indices (gen_0, gen_1). The index is determined by graph structure, never by execution order.

Rule 03: Every node’s key includes the keys of its upstream dependencies
val_0(gen_0) and val_0(gen_1) are different keys because they inherit different parents. This is recursive; the key of any node encodes the full path from the root of the graph.

When applied, these three rules produce keys like:

In practice, the implementation is small. Each step builds its key and passes it to the LLM provider, which then handles cache lookup and storage:

def run_step(step_name, run_index, upstreams, prompt):
    if upstreams:
        parent_keys = ",".join(u.cache_key for u in upstreams)
        cache_key = f"{step_name}_{run_index}({parent_keys})"
    else:
        cache_key = f"{step_name}_{run_index}"

    result = llm_call(prompt, cache_key=cache_key)
    return Output(value=result, cache_key=cache_key)

Naming cache keys

The cache key that we just constructed can, of course, have as many prefixes and suffixes as you need. In our case we wanted to add the experiment name, as a seed to that key:

experiment_v3::gen_0
experiment_v3::val_0(gen_0)
experiment_v3::fix_0(val_0(gen_0))

Remember: a cache hit requires both the key and the prompt to match. By designing a cache key that allows you to change both the experiment name (controls the key) and the component’s code (controls the prompt), we’re able to get at the constellation that we need. For example, we can recompute identical full pipelines N times by having different experiment names. Alternatively, if we spotted a bug in an experiment we already ran, we can just change a component and have all previous calculations retrieved from the cache, saving valuable time and money. 

With control over the experiment name and the component’s code, we’re able to produce three kinds of scenarios:

1. Reproduce. Run the experiment again with exactly the same parameters:

2. A/B test. Run the experiment again, but swap the content of just one step: 

This kind of test can allows for the following:

• Generate hits – same key, same prompt. 
• Validate misses – same key, but different prompt. 
• Fix misses – same key, but its input changed.

3. Fresh run. Change the experiment name: 

In this scenario, all keys change, so there are no matches and every step recomputes.

Cache key design: Implications for agent evaluations

With these design patterns in place, changing one prompt means that only LLM calls from that point onwards will actually run, and LLM calls that happen before it would be loaded from cache.

That means:

• You can A/B test any component against identical upstream outputs
• Best-of-N gives you N genuinely independent branches, not N copies of the same cached result 
• And every cached step is an LLM call you don’t pay for; at scale that means turning experimentation from something you have to ration into part of the daily loop

Caching is one of the most powerful tools we have for making agentic workflows fast, reproducible, and cheap to iterate on. But the non-deterministic nature of LLMs breaks the assumptions that traditional caching relies on, so bridging that gap takes more than a key-value store. It takes a deliberate design that respects the non-determinism at the core of these systems.