Our Bloom Filter Lied to Users for 8 Months — Every Dashboard Said It Was Fine

Day 18 — Bloom Filters: The False-Positive Rate Is a Gauge, Not a Constant

Somewhere in your agent pipeline there's probably a bloom filter, and it's getting worse at its job right now, while you read this, and nothing is telling you. If the last time anyone computed its false-positive rate was in a design doc before launch, you don't know what it's actually doing today — you know what it was doing then.

The ticket that looked like nothing

The report was almost forgettable: a user said our support agent confidently answered a question it had 'already answered' minutes earlier — except it hadn't, not for this user, not with this context. Support tagged it low-severity, wrong-answer, and moved on. I only pulled the thread at 2am because three more tickets with the same shape landed in the same hour, all from the same pipeline: the agent skipped a step it had no business skipping. Git blame on the skip logic pointed at a bloom filter that had been sitting there, untouched and unmonitored, for eight months — quietly labeled 'working fine.'

What the filter was actually for

It guarded one cheap-sounding, expensive question: have we already processed something like this? Before paying for a full LLM call or a downstream retrieval step, the pipeline hashed the incoming request and checked the filter. A miss meant definitely new — do the expensive work, then insert the hash. A hit meant probably already seen — skip the LLM call, serve the prior result instead. Same trick you'd reach for to dedupe in any high-throughput system. The difference here is that the 'expensive work' being skipped was a paid model call, and a false skip didn't just waste a cycle — it served a wrong answer with total confidence.

The design that looked fine on day 1

At launch, someone — probably me — sized the filter for expected load: bit array for roughly 10M items, k=7 hash functions, target false-positive rate around 1% at capacity. Nothing wrong with that math. It's textbook. The mistake was treating that 1% as a fact about the system, when it was really a fact about one specific (bits, hashes, item count) combination that only holds at one specific moment.

• ▹Bit array size (m) — set once at deploy time, then basically never looked at again
• ▹Hash function count (k) — tuned once for the target FP rate at the designed capacity
• ▹Expected FP rate — calculated once, dropped into a doc, never re-derived
• ▹Item count (n) — the one variable everyone quietly assumed would stay close to the original guess

Strip the bloom-filter specifics away and this is the real pattern: any component in an agentic pipeline where the tradeoff was 'calculated once' is a landmine with a very long fuse.

The slow drift nobody saw

Traffic grew — more agents, more sessions, more distinct request shapes — and the filter kept accepting inserts long past the capacity it was sized for. Bloom filters don't reject inserts when they're 'full'; they just keep flipping bits until the array saturates. As n crept past the design target, the false-positive rate didn't inch up, it ran: 1% to 15% to 45%, and by the time I was staring at logs at 2am, our best estimate had it north of 80%. Every step of that climb threw zero errors, crashed zero requests, failed zero health checks. The filter was doing exactly what a bloom filter is supposed to do — return 'maybe present' with a bounded error rate. The bound had just moved, and nobody was watching it move.

Why standard observability was blind to this

We had the usual triad — latency, error rate, throughput — and none of it flickered, because none of it measures this failure mode. A false-positive skip isn't an error from the pipeline's point of view: the request completes, fast, with a 200. The only thing that changed was correctness, silently, for a slice of traffic that never got logged as 'a judgment call happened here.'

• ▹No metric for 'estimated current false-positive rate' existed, so there was nothing to alert on
• ▹Latency actually improved as the FP rate climbed — skips are cheaper than real work, so a good-looking graph was actively hiding the problem
• ▹Error rate stayed flat, because a false-positive skip is a wrong answer wearing a success status code, not an error
• ▹Nobody owned the question 'is this probabilistic structure still honoring its design assumption' after launch

# The number everyone computes once at design time — and should be recomputing continuously
import math

def estimated_fp_rate(m_bits: int, k_hashes: int, n_items_inserted: int) -> float:
    """Standard bloom filter FP estimate, but fed LIVE n, not the design-time n."""
    return (1 - math.exp(-k_hashes * n_items_inserted / m_bits)) ** k_hashes

# Day 1: m=96M bits, k=7, n=10M (designed capacity) -> ~1.0% FP rate
print(estimated_fp_rate(96_000_000, 7, 10_000_000))

# Month 8: same m and k, n has grown 5x past the sizing assumption
print(estimated_fp_rate(96_000_000, 7, 50_000_000))  # ~83%, and climbing

# The fix: expose this as a gauge, tracking live insert count against capacity
def saturation_gauge(n_items_inserted: int, n_designed_capacity: int) -> float:
    return n_items_inserted / n_designed_capacity  # emit to Prometheus/Datadog every N inserts

The fix: treat the FP rate as a gauge you watch, not a constant you compute once

The fix had three parts, and none of them were clever. First, a resizing strategy: instead of one filter sized for a guess, rotate into a fresh filter — or a scalable/counting variant — once observed n approaches the sized capacity, so the FP rate resets instead of compounding forever. Second, a saturation gauge shipped to the same dashboards as latency and error rate: current n over designed capacity, plus the live-estimated FP rate derived from it, both wired to alerts. Third, the line that mattered most: the false-positive rate is a property of current state, not a design artifact. If you can't see it move, you can't know when it's already lied to a user.

• ▹Emit (n_inserted / capacity) and the derived FP rate as first-class metrics — not a one-time calculation in a doc
• ▹Alert on the saturation ratio, not just downstream error rate — the filter degrades long before anything else does
• ▹Rotate or resize ahead of saturation; don't wait for a ticket to tell you it already happened
• ▹Log what a bloom-filter hit caused the pipeline to skip, so a bad hit is at least reconstructable afterward

Zoom out and this is just Day 18's version of a pattern this whole series keeps circling back to: you're trading a small amount of bounded wrongness for speed or cost. Day 19 picks the same tradeoff back up wearing a different costume, at a different layer of the stack.

A bloom filter never tells you it's lying — that was the deal the moment you chose 'probably' over 'certainly.' Build the gauge before you need it. Not after the 2am ticket.

Extend your knowledge

• ▹Read the original Bloom (1970) paper for the core tradeoff, then compare it against a Scalable Bloom Filter or Cuckoo Filter — both exist specifically to handle unbounded/growing n without a manual rotation step
• ▹Running Redis? Look at RedisBloom — it exposes BF.INFO, which reports current capacity and item count, so a saturation gauge is nearly free to add
• ▹Instrument any probabilistic structure already in your stack today: emit n_inserted, capacity, and derived FP rate as a gauge, even before you've seen a hint of drift
• ▹Audit your agent pipeline for other 'computed once at design time, never revisited' tradeoffs — sampling rates, cache TTLs, rate-limit thresholds. The bloom filter pattern generalizes a lot further than bloom filters