Retrieval Non-Determinism: Why One Run Is a Sample, Not a Measurement

EvalMonitoringAdvanced21 min

By: Anacodic Team

TL;DR — A retrieval pipeline that fans out to several sources is a random variable, not a function. Each source can time out, rate-limit, or return partial results independently, so the same query run twice returns different evidence — and this happens at temperature zero, because the variance is in the network and the quotas, not in the sampler. A single run cannot see it: at n=1 the observed minimum equals the observed maximum by construction, so the pipeline looks perfectly deterministic. The consequence is that any benchmark number from one run is one draw from a distribution nobody has characterised, and an improvement smaller than the run-to-run spread is not an improvement. The boundary condition is independence — once sources share a rate limiter, a cache, or a gateway, failures correlate and the spread is wider than an independent model predicts.

1. Simple explanation

Ask a pipeline the same question twice and you expect the same answer. For a single vector store at temperature zero, that is roughly true. For anything that fans out to multiple sources, it is not.

Each source is a separate network call with its own quota, latency, and failure mode. One is rate-limited and returns HTTP 429 for the next sixty seconds. One is slow and gets cut by a timeout. One is fine. The pipeline collects whatever came back, ranks it, and answers — and because a failed source is usually caught and turned into an empty list rather than an exception, nothing anywhere records that the question was answered from three sources instead of four.

So the result is a sample. Run it again and a different subset of sources answered, so a different set of documents was ranked, so a different answer came out. Not because the model sampled differently, but because the evidence differed.

Analogy — counting cars at a junction with four traffic cameras. Each camera is up most of the time and occasionally offline for maintenance. You count 200 cars this morning and 160 tomorrow. Nothing changed about the traffic; one camera was down. If you report "200 cars" from a single morning's count, you are reporting camera uptime as though it were traffic volume — and if you only ever count once, every camera looks permanently online, because you have no second observation to disagree with the first.

2. Diagram

  A FUNCTION                        A RANDOM VARIABLE
  ----------                        -----------------
  query -> [ one index ] -> docs    query --+--> catalog A   (95% up) --+
           same in, same out                +--> catalog B   (90% up)  +--> rank
                                            +--> partner API (70% up)  +     |
                                            +--> web index   (60% up) -+     v
                                                                           docs
                                       any subset may be missing, silently


  WHAT YOU SEE, BY NUMBER OF RUNS         (measured, §5)

   runs   mean    min  max   thin<=3   empty
   ----   -----   ---  ---   -------   -----
      1   12.00    12   12     0.0%    0.0%   <- looks DETERMINISTIC
      6   10.33     5   12     0.0%    0.0%      min == max, by construction
     30   10.10     5   12     0.0%    0.0%
    200    9.65     3   12     1.0%    0.0%   <- the floor finally appears


  THE SIX RUNS A HUMAN ACTUALLY LOOKS AT

    [ 12, 12, 12, 12, 9, 5 ]
       ^^^^^^^^^^^^^^
       four identical runs, then it moves.
       Test three times, conclude "stable", ship.


  ONE RUN vs A FAILURE MODE OF RATE p

    p = 5%   ->  a single run misses it 95% of the time;  58 runs for 95% coverage
    p = 10%  ->  missed 90% of the time;                  28 runs
    p = 17%  ->  missed 83% of the time;                  16 runs
    p = 30%  ->  missed 70% of the time;                   8 runs

3. How it works

3.1 The variance is not in the model

It is worth separating the two sources of non-determinism, because the usual mitigation addresses the wrong one.

Source of variance	Mechanism	Fixed by temperature 0?
Sampling	the model draws from a distribution over tokens	yes, largely
Retrieval	a source timed out, rate-limited, or returned partial results	no

Setting temperature=0 makes generation reproducible given the same context. It does nothing about the context differing between runs. Teams that set temperature to zero, observe that two runs still differ, and conclude the model is "still random" are usually looking at retrieval variance and tuning the wrong knob.

3.2 Why the failure is silent

The standard, and correct, pattern for a parallel fan-out is to isolate each source so one failure cannot take down the query:

  for each source:
      try:    docs += source.search(query)
      except: docs += []          # a failed source contributes nothing

This is good engineering and it is also why the variance is invisible. A failed source becomes an empty list, indistinguishable from a source that legitimately had no matches. The request returns HTTP 200 with a normal latency and a slightly thinner set of documents. Error rate does not move. Latency does not move. The only signal that moved is the per-source document count, which is usually not recorded.

The minimum viable instrumentation is therefore one line: record the document count per source on every run, not just the total. Without it, retrieval variance is unmeasurable after the fact, because the runs you would want to compare did not keep the field that distinguishes them.

3.3 Why n=1 cannot detect it, arithmetically

For a single run, the observed minimum, maximum, and mean are all the same number, and the observed variance is zero. This is not a limitation of the tooling; it is what one sample means. A pipeline observed once is indistinguishable from a deterministic one.

Worse, small n is actively misleading rather than merely uninformative. In the measured run in §5, the first four runs returned an identical 12 documents before the fifth returned 9 and the sixth returned 5. A team that tested three times and saw three identical results would have concluded, reasonably, that the pipeline was stable.

The number of runs needed to see a failure mode of rate p at least once, with 95% confidence, follows directly from the probability of missing it every time:

  P(miss it in n runs) = (1 - p)^n
  n = log(0.05) / log(1 - p)

For a 1-in-6 failure (p ≈ 0.17) that is 16 runs. For a 1-in-20 failure, 58. Any "we tested it a few times" claim about a fan-out pipeline is a claim about nothing.

3.4 Reporting a number that survives this

Three changes make a benchmark honest under variance, and they cost almost nothing:

Report the spread, never the mean alone. Minimum, maximum, and the rate of thin or empty results. In §5, the mean drifts from 12.00 to 9.65 as runs increase while the minimum drops from 12 to 3 — and the minimum is what a user experiences on a bad day.
Define "passing" over repeated runs. A question counts as answered if it is answered in at least k of n runs. State k and n, and justify k — it encodes how much flakiness you are willing to call success.
Compare improvements against the spread. If run-to-run variation spans 5 to 12 documents, a change that moves the mean from 9.6 to 10.1 has demonstrated nothing. The comparison has to be distribution against distribution, not point against point.

Where this stops applying. All of the above models sources as failing independently. They frequently do not. Several sources behind one API gateway share its rate limit; several behind one HTTP client share its connection pool and timeout budget; a shared cache makes consecutive runs correlated rather than independent, which makes repeated runs look more stable than the system is. Under correlation the true spread is wider than an independent model predicts, and the quantity worth measuring shifts from "how often does one source fail" to "how often do several fail together".

4. The math

4.1 Documents retrieved as a random variable

Let source i contribute n_i documents when it answers, and answer with probability p_i, independently. Let X_i be the indicator that source i answered. Total documents:

  D = sum_i  n_i * X_i

  E[D]   = sum_i  n_i * p_i
  Var[D] = sum_i  n_i^2 * p_i * (1 - p_i)
  min(D) = 0                       (every source fails)
  max(D) = sum_i n_i               (every source answers)

The expectation is the number a single run tends to look like. The variance is the number that decides whether any two runs are comparable, and it is the one nobody computes.

4.2 Probability of a thin result

For a threshold t below which there is too little evidence to answer:

  P(D <= t) = sum over subsets S of sources
                where sum_{i in S} n_i <= t
                of   prod_{i in S} p_i * prod_{i not in S} (1 - p_i)

This is exponential in the number of sources and is almost always easier to estimate by simulation than to evaluate — which is what §5 does.

4.3 Runs needed to observe a rare failure

  P(never observing it in n runs) = (1 - p)^n

  n = log(alpha) / log(1 - p)          alpha = tolerated miss probability

4.4 Worked example

Four sources: (4, 0.95), (3, 0.90), (3, 0.70), (2, 0.60) as document count and availability.

  E[D] = 4(0.95) + 3(0.90) + 3(0.70) + 2(0.60)
       = 3.80 + 2.70 + 2.10 + 1.20
       = 9.80 documents

  max(D) = 4 + 3 + 3 + 2 = 12
  min(D) = 0

The measured mean over 200 runs in §5 is 9.65, against the predicted 9.80 — close, as it should be. But note what the expectation conceals: the same simulation observed a run returning 3 documents. A pipeline reported as "retrieves about 10 documents" also returns 3 sometimes, and the summary statistic contains no trace of it.

Now the run budget. Suppose a thin result occurs on 17% of runs:

  n = log(0.05) / log(1 - 0.17) = log(0.05) / log(0.83)
    = (-2.996) / (-0.186)
    ~ 16 runs

Sixteen runs for a 95% chance of observing the failure once. Characterising its rate to within a few percentage points takes hundreds. This is the arithmetic that makes "we ran it a few times and it looked fine" an empty statement.

5. Real code

"""Fan-out retrieval over flaky sources: one run is a sample, not a measurement."""
import random, statistics

SOURCES = {            # name: (docs it can contribute, probability it answers)
    "catalog_a": (4, 0.95),
    "catalog_b": (3, 0.90),
    "partner_api": (3, 0.70),   # rate-limited
    "web_index": (2, 0.60),     # slow, often times out
}

def one_run(rng):
    """Query every source in parallel; a failed source contributes nothing."""
    return sum(n for n, p in SOURCES.values() if rng.random() < p)

def campaign(runs, seed=7):
    rng = random.Random(seed)
    return [one_run(rng) for _ in range(runs)]

for runs in (1, 6, 30, 200):
    obs = campaign(runs)
    zeros = sum(1 for x in obs if x == 0)
    thin = sum(1 for x in obs if x <= 3)          # too little to answer from
    print(f"runs={runs:4}  mean={statistics.mean(obs):5.2f}  "
          f"min={min(obs):2}  max={max(obs):2}  "
          f"thin(<=3)={thin/runs:5.1%}  empty={zeros/runs:5.1%}")

print()
obs6 = campaign(6)
print("the six runs a human would actually look at:", obs6)

# how often does a single run miss a failure that happens with probability p?
print()
print("chance a SINGLE run misses a failure mode of rate p:")
for p in (0.05, 0.10, 0.17, 0.30):
    print(f"  p={p:.0%}  ->  missed {1-p:.0%} of the time;  "
          f"need {int(round(__import__('math').log(0.05)/__import__('math').log(1-p)))} runs "
          f"for a 95% chance of seeing it once")

thin_rate = sum(1 for x in campaign(200) if x <= 3) / 200
assert 0.0 < thin_rate < 1.0, "the thin-result rate must be a real fraction"
assert min(campaign(200)) < statistics.mean(campaign(200)), "the mean hides the floor"

# Output:
#   runs=   1  mean=12.00  min=12  max=12  thin(<=3)= 0.0%  empty= 0.0%
#   runs=   6  mean=10.33  min= 5  max=12  thin(<=3)= 0.0%  empty= 0.0%
#   runs=  30  mean=10.10  min= 5  max=12  thin(<=3)= 0.0%  empty= 0.0%
#   runs= 200  mean= 9.65  min= 3  max=12  thin(<=3)= 1.0%  empty= 0.0%
#
#   the six runs a human would actually look at: [12, 12, 12, 12, 9, 5]
#
#   chance a SINGLE run misses a failure mode of rate p:
#     p=5%  ->  missed 95% of the time;  need 58 runs for a 95% chance of seeing it once
#     p=10%  ->  missed 90% of the time;  need 28 runs for a 95% chance of seeing it once
#     p=17%  ->  missed 83% of the time;  need 16 runs for a 95% chance of seeing it once
#     p=30%  ->  missed 70% of the time;  need 8 runs for a 95% chance of seeing it once

The runs=1 line is the article in one row: the minimum equals the maximum and the spread is zero, because a single observation has no spread to report. The second assert states the claim that matters — the mean sits above the floor, so reporting the mean alone hides the bad days.

6. Real-world example

A team shipped an internal research assistant that queried four sources in parallel and synthesised an answer with citations. Before launch they ran their twenty-question evaluation set, scored 18 of 20, recorded the number, and released it.

Complaints were intermittent and therefore dismissed for several weeks: a user would report a thin or unhelpful answer, an engineer would run the same question, get a good answer with six citations, and close the ticket as not reproducible. The dashboards agreed with the engineers — error rate flat, p95 latency flat, no exceptions.

The cause surfaced only when someone added per-source document counts to the run artifacts and looked at a week of traffic. Two of the four sources were answering far less often than assumed: one was rate-limited during business hours because the whole fleet shared a single API key's quota, and one was timing out on roughly a fifth of calls. On a good run four sources answered and the assistant looked excellent. On a bad run two answered, there was just enough evidence to produce a fluent answer, and the result was thin but not obviously broken.

Re-running the twenty-question set thirty times instead of once turned 18/20 into a range: between 11 and 19 questions answered, with a median of 16. The original 18 was real and was also close to the best case. Nobody had been dishonest; they had drawn one sample and written it down as a property of the system.

Two details are worth carrying. The shared API key made the failures correlated — several sources degraded together during business hours — so the spread was worse than an independent model would predict. And the fix that mattered most was not better retry logic; it was recording per-source counts, which turned an unreproducible complaint into a measurable quantity.

7. Interview questions companies actually ask

Q1. You set temperature to 0 and the same query still returns different answers. What is happening? Almost certainly retrieval variance rather than sampling variance. Temperature controls the token sampler, so it makes generation reproducible given identical context, and it has no effect on whether every source answered on this particular call. In a parallel fan-out, a rate-limited or timed-out source is typically caught and turned into an empty list, so the context differs between runs while nothing logs that it did. Check per-source document counts across runs before touching any model parameter.

Q2. Why can't you detect this from error rate and latency dashboards? Because the standard failure-isolation pattern converts a source failure into an empty result, not an exception. The request succeeds, returns 200, and completes in normal time with slightly less evidence. Error rate and latency are both blind to it by construction. The signals that do move are per-source document count and the rate of thin or empty results, and neither is recorded by default.

Q3. Your evaluation set scored 18/20. What is wrong with that sentence? It omits how many times it was run. If the pipeline fans out to flaky sources, 18/20 is one draw from a distribution, and the same suite re-run thirty times can easily span a much wider range with a lower median. A defensible report gives the number of runs, the median, the minimum, and the rate of empty results — and if a comparison is being made, it compares distributions rather than two point estimates.

Q4. How many runs do you need? It depends on the rate of the thing you want to observe, and the arithmetic is n = log(alpha) / log(1 - p). For a 95% chance of seeing a 1-in-6 failure at least once, that is about 16 runs. For a 1-in-20 failure, 58. Note the asymmetry: seeing a failure once is cheap, while estimating its rate to within a couple of percentage points needs hundreds of runs, which is why most teams should be reporting a spread over tens of runs rather than claiming a precise failure rate.

Q5. You improved the mean from 9.6 to 10.1 documents retrieved. Did you improve anything? Not demonstrably, if run-to-run variation spans 3 to 12. A 0.5 shift in the mean is well inside that spread, so the two configurations are indistinguishable on this evidence. Either run enough iterations that the difference clears the noise, or change the metric to something less noisy — for instance the rate of thin results, which is often the quantity you actually care about and which moves more decisively than an average does.

Q6. What is the minimum instrumentation to make this measurable? One field: document count per source, written to the run record on every request, rather than only the total. Everything else — spread, thin-result rate, which source degraded, whether failures correlate — can be reconstructed from that field after the fact. Without it, the runs you would need to compare have already discarded the thing that distinguishes them, and no amount of later analysis recovers it.

Q7. Your sources sit behind one gateway that enforces a shared rate limit. What changes? Independence fails, so the analysis in this article understates the spread. Failures now arrive in bursts — several sources degrade together when the shared quota is exhausted — which both widens the tail and makes consecutive runs correlated, so repeated runs launched back to back look more stable than the system is. Space the runs out, and shift the metric from per-source availability to the joint event: how often did two or more sources fail on the same request.

8. When to use / tradeoffs

Report a distribution rather than a point estimate when:

the pipeline queries more than one external source
any source is rate-limited, paginated, or on a shared quota
a benchmark number will be published, compared, or used to decide a rollout
the system is allowed to answer from partial evidence

Situation	Why a single run breaks	Do instead
Comparing two configurations	the difference is often smaller than the spread	run both repeatedly; compare distributions, state the spread
A user reports an unreproducible bad answer	your one retry probably hit a good run	look at per-source counts on their run, not a fresh one
Sources share a key, gateway, or cache	failures correlate; independence understates the tail	measure joint failures; space runs apart to break cache correlation
Estimating a failure rate, not just seeing it	tens of runs bound the existence, not the rate	hundreds of runs, or instrument production and read it off traffic
Single local index, no network	variance really is near zero here	a single run is fine; do not pay for repetition you do not need

Honest limits. The model in §4 assumes sources fail independently with fixed probabilities, and both halves of that are usually false: availability varies by time of day, and shared infrastructure correlates failures, so a real system's spread is wider than this arithmetic predicts. The simulation in §5 is seeded, which makes the article reproducible and also means the specific numbers are one realisation — re-seeding moves them, and the qualitative claim, not the digits, is the finding. Document count is used throughout as a proxy for evidence quality, which it is not: four highly relevant documents beat nine weak ones, so a stable count can still hide a quality swing. And the run-budget formula assumes independent, identically distributed runs, which back-to-back requests against a cached source are not.

A fan-out retrieval pipeline is a random variable, not a function; the same query returns different evidence on different runs.
The variance lives in quotas, timeouts, and network, not in the sampler — so temperature=0 does not address it.
Failure isolation turns a dead source into an empty list, so error rate and latency stay flat. The failure is silent by design.
At n=1 the spread is zero by construction, and small n is actively misleading: the measured example returned four identical runs before moving.
n = log(alpha) / log(1 - p) — about 16 runs to see a 1-in-6 failure once; hundreds to estimate its rate.
Report min, max, and thin/empty rate, define passing as "answered in ≥ k of n runs", and compare distributions rather than points.
Minimum instrumentation is one field: document count per source, per run.
The boundary: independence. Shared keys, gateways, and caches correlate failures and widen the tail beyond what this model predicts.

RAG Monitoring: Your Error Rate Will Not Tell You Anything — which signals catch which failure, and why the usual dashboards miss this one
RAG Evaluation: Attributing Failure and Sizing the Eval Set — building the question set whose scores this article tells you how to report
Grounding and Abstention by Design: Refusing Before You Generate the Wrong Answer — what the pipeline should do on the runs that come back thin
RAG Cost Optimization: Find the Step That Runs Forty Times — why repeated runs are affordable, and which stage dominates the bill
Scaling RAG: Many Tenants, One Code Path — shared quotas across tenants, the usual source of correlated failure
Multi-Index RAG: Merging Several Retrievers Into One Answer — the fan-out architecture this variance is a property of
Retrieval Techniques — what each source contributes when it does answer
Backtesting, Baselines & Sensitivity Analysis — the general discipline of knowing your floor before reading a score

Resources

Dean, Jeffrey & Barroso, Luiz André. The Tail at Scale. Communications of the ACM, 56(2), 2013. The canonical treatment of why latency and availability variance dominates any system that fans out to many components, and the source of the hedged-request and tied-request patterns.
Barroso, Luiz André & Hölzle, Urs & Ranganathan, Parthasarathy. The Datacenter as a Computer, 3rd edition. Morgan & Claypool. Chapter 2 covers tail latency and correlated failure in request fan-out.
Nygard, Michael T. Release It!, 2nd edition. Pragmatic Bookshelf. The Circuit Breaker, Timeout, and Bulkhead patterns — and the reason a caught exception becomes an invisible empty result.
Amazon Builders' Library — Timeouts, retries, and backoff with jitter: https://aws.amazon.com/builders-library/timeouts-retries-and-backoff-with-jitter/ Why naive retries synchronise and turn independent failures into correlated ones.
Google SRE Book, Chapter 22, Addressing Cascading Failures: https://sre.google/sre-book/addressing-cascading-failures/ The shared-quota mechanism behind the correlated-failure boundary in §3.4.

← Previous: Scaling RAG: Many Tenants, One Code Path