Your Vector DB Is Answering Yes/No Questions at Semantic-Search Prices

Day 15 — Bloom Filters: The Cheap 'Have I Seen This?' Check Before You Pay for Semantic Search

Here's a smell worth knowing: if your RAG ingestion pipeline embeds a chunk and queries the vector DB just to find out it's a duplicate, you're running a semantic search to answer a question with exactly two possible answers. A Bloom filter answers 'definitely not seen this before' for close to nothing, and only forwards the maybe-cases to the expensive machinery.

The cost story

Picture a re-ingestion pipeline that re-crawls docs on a schedule — support articles, changelogs, scraped pages, whatever feeds the RAG index. Every chunk takes the same path: embed it, query the vector index for nearest neighbors, decide if it's a near-duplicate of something already indexed, then skip or insert. That's an embedding call plus a vector-DB round trip, per chunk, every time. Someone eventually pulls the logs and notices most of those lookups come back 'yes, already indexed, skip it.' You've been paying full semantic-search prices — latency and dollars — to reject things you already knew about.

Name the actual question

The pipeline is asking two different questions and treating them as one. 'Have I encountered this exact or near-exact chunk before?' is a membership test — a set lookup. 'What does this chunk mean, and what's semantically related to it?' is a similarity search. Only novel content needs the second question answered. The first question doesn't need meaning at all. It needs a fast, cheap 'have I seen this token stream before' — a problem that was solved decades before embeddings existed.

The mechanism, just enough to use it

A Bloom filter is a fixed-size bit array plus k independent hash functions. Insert an item: run it through all k hashes, flip those bit positions to 1. Check an item: hash it the same way, look at those same k positions. Any bit still 0 means the item was definitely never inserted. All bits 1 means it was probably inserted — probably, because other items' hashes can collide into the same bits. That asymmetry is the entire design: a structure cheap enough in memory and time to give you a hard 'no' and a soft 'maybe.'

# pseudocode — the gate goes before the embedding call, not instead of it
if not bloom.might_contain(chunk_hash):
    bloom.add(chunk_hash)
    index_new_chunk(chunk)          # definitely novel, skip the vector check entirely
else:
    # maybe seen — only now do we pay for the expensive path
    vector = embed(chunk)
    if not vector_db.near_duplicate_exists(vector):
        bloom.add(chunk_hash)
        index_new_chunk(chunk)
    # else: confirmed duplicate, discard

The skew, made concrete

In a re-crawl-heavy pipeline, most of what hits this gate is exactly what you'd guess: exact re-fetches of unchanged pages, near-duplicate boilerplate (nav bars, footers, the same disclaimer for the hundredth time), repeated tool-call outputs sitting in an agent's memory log. All of it gets a hard 'definitely not seen' and never touches the embedding model. What still has to hit the vector index is the actually novel content — the new paragraph, the changed section — plus the filter's own false positives, which stay rare if you size the bit array correctly. In a mature re-ingestion pipeline, that ratio is often lopsided enough that people are genuinely surprised how much of their vector-search bill was membership-checking, not meaning.

The honest limit — a design decision, not a caveat

A Bloom filter can lie in exactly one direction: it can say 'maybe present' about something never inserted (false positive), but it can never say 'definitely absent' about something that was inserted (no false negatives). Don't treat that as a flaw to work around — it's the property you're paying for. You size the bit array and pick k against your target false-positive rate: bigger array, more hash functions, fewer maybe-cases leaking through to the expensive path, more RAM spent to get there. You are explicitly choosing how much wasted vector-search cost you'll still eat versus how much memory the filter costs you. There's no setting where you get zero false positives and zero memory cost — pick your point on that curve on purpose, not by accident.

Where this generalizes

RAG ingestion is just one instance of a pattern that shows up everywhere in agent systems: any 'have I done this already' gate. An agent checking whether it already called a tool with these exact arguments this session. A memory system checking whether it already stored this fact. An orchestrator checking whether a sub-task was already dispatched. All of these are membership tests hiding behind infrastructure built for similarity. The fix has the same shape every time: a cheap, deterministic pre-check — a Bloom filter, a hash set, a cache key — sitting in front of the expensive semantic or stateful operation, not replacing it.

Day 15 placement

This filter sits in front of the expensive layer — it never replaces the vector index, the LLM judge, or whatever's doing the real semantic work downstream. The pattern that actually matters here is bigger than Bloom filters: cheap check before costly call. That's the thread tomorrow's concept picks up.

Extend your knowledge

• ▹Read Bloom's original 1970 paper's core idea, summarized in any standard algorithms text — the bit-array-plus-k-hashes mechanism hasn't changed in 56 years, only where it gets applied.
• ▹Look at how counting Bloom filters or Cuckoo filters add deletion support — worth knowing if your agent memory needs entries to expire, which a plain Bloom filter can't do.
• ▹Check whether your vector DB (pgvector, Pinecone, Weaviate, Qdrant) or your RAG framework already exposes a dedup/ingestion-cache hook — plenty of teams build this gate from scratch before checking if it's already a config flag.
• ▹If you're building agent memory, look at how existing frameworks handle 'seen tool-call' or 'seen fact' caching — most either do nothing and re-pay every time, or over-solve it with a full vector lookup where a hash set or Bloom filter would do the job.