Metadata Filtering

The previous lesson directed the query at the whole corpus, and the index only restricted where in that corpus to look. A retrieval request often does not arrive like this. The field crew asks for the records of a certain region, the help desk for the documents of a certain class, the audit for a certain period. This constraint is not a similarity question; it is an exact condition defined over metadata, and whether it is satisfied or not admits no degree.

There is no single correct order for combining the two procedures. If the filter is applied after the vector search, the search runs over the whole index and some of the results are eliminated. If it is applied before, the search runs only over the matching documents, but the index was built over the whole corpus and what it promises in the narrowed space is unclear. This lesson measures both orders and puts a third number beside them: the cost of applying the filter and not using the index at all. As the filter narrows, there comes a point at which this third option becomes both more accurate and cheaper.

• EV39. The corpus, the embedding procedure, the query set and the metadata layer are fictional; no real vector store or embedding endpoint is called. The seed is 20260218.
• EV40. The metadata is a single field in this lesson: every document is given a region code (from 1 to 16) derived from the seed. The filter is the condition region <= width; as the width gets smaller, the filter becomes more selective.
• EV41. The filter is exact: a document that does not match cannot enter the result at any similarity value. This is a different constraint from a similarity threshold.
• EV42. The correct answer at every width is the exhaustive search of the filtered set: comparison with all the matching documents and the first five. Recall is the ratio of the intersection of the procedure’s retrieved set with this five; if the number of matching documents is fewer than five, the denominator is that number.
• EV43. Post-filtering takes the first fetch results from the index and discards the ones that do not match. In-index filtering looks into the same buckets but never takes the non-matching documents into the candidate set.
• EV44. The index is built with the setting measured in the previous lesson: bucket-based index, 16 buckets, 2 probes. This setting gave a recall of 0.9500 without a filter and is the comparison baseline of this lesson.
• EV45. The comparison count is the number of cosine similarities computed in a single query: the representative count plus the number of candidates looked at. The filter itself is an equality test and is not included in this number.
• EV46. The candidate count is the number of documents that pass the filter inside the probed buckets; the breakdown of the neighborhood shows in this column.
• EV47. The two runs measure the same query set on two separate index builds. In the previous lesson this difference came out as 0.0100 without a filter; one finding of this lesson is that the difference grows together with the filter.

The filtered query itself was built and measured in the Advanced SQL and Search Engines and Text Retrieval courses of the Databases curriculum; the filtering procedure is not repeated here. The only thing added is what the filter does to the vector neighborhood.

The Space the Filter Narrows

The block below builds the corpus and the embedding simulator, adds the metadata layer on top, and prints the unfiltered baseline.

# FICTIONAL corpus, FICTIONAL embedding simulator and FICTIONAL metadata. No real endpoint.
SEED, M32 = 20260218, 0xFFFFFFFF
DIM = 32


def rng(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def next_value():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return next_value


def pick(u, w):
    t = 0.0
    for i, x in enumerate(w):
        t += x
        if u < t:
            return i
    return len(w) - 1


# ---- FICTIONAL semantic axis: each concept has a separate surface form on the document side and on the query side
CLASSES = ["tariff", "fault", "meter", "outage", "maintenance"]
CODE = {"tariff": "TR", "fault": "AR", "meter": "SY", "outage": "KS", "maintenance": "BK"}
CONCEPTS = {                     # concept: (label, document-side form, query-side form)
    "tier":             ("tariff", "tier threshold", "which band am i in"),
    "unit_rate":        ("tariff", "unit price", "fee per cubic metre"),
    "subscriber_type":  ("tariff", "subscriber type", "home or shop"),
    "switch":           ("tariff", "tariff switch", "changing plan"),
    "fault_code":       ("fault", "fault code", "error id"),
    "leak":             ("fault", "line leakage", "water escaping"),
    "pressure":         ("fault", "pressure drop", "weak flow"),
    "crew":             ("fault", "field crew", "who will be sent"),
    "index_value":      ("meter", "index value", "what the dial shows"),
    "reading":          ("meter", "reading procedure", "how it gets saved"),
    "replacement":      ("meter", "meter replacement", "new hardware"),
    "verify":           ("meter", "reading verification", "typed in wrong"),
    "planned":          ("outage", "planned outage", "announced stoppage"),
    "notice":           ("outage", "notice channel", "where i hear about it"),
    "duration":         ("outage", "outage duration", "how long it lasts"),
    "restoration":      ("outage", "service restoration", "when it comes back"),
    "periodic":         ("maintenance", "periodic maintenance", "regular checkup"),
    "valve":            ("maintenance", "valve inspection", "tap shutoff routine"),
    "filter_swap":      ("maintenance", "filter swap", "cleaning part"),
    "calibration":      ("maintenance", "calibration record", "gauge accuracy"),
}
KEYS = list(CONCEPTS)
COMMON = ["entry", "region", "term", "step", "form", "approval", "note"]

DOCUMENTS = []
for i in range(200):
    r = rng(SEED + 7919 * i)
    s = CLASSES[pick(r(), [0.22, 0.24, 0.20, 0.18, 0.16])]
    pool = [k for k in KEYS if CONCEPTS[k][0] == s]
    main = pool[int(r() * len(pool))]
    n = 2 + int(r() * 4)
    paragraphs, concepts = [], [main]
    for _ in range(n):
        y = pool[int(r() * len(pool))]
        concepts.append(y)
        o = COMMON[int(r() * len(COMMON))]
        paragraphs.append(f"{CONCEPTS[y][1]} for {o} is kept and written together with {CONCEPTS[main][1]}")
    DOCUMENTS.append({"code": f"{CODE[s]}{i + 1:03d}", "label": s, "main": main, "concepts": concepts,
                      "title": f"{CONCEPTS[main][1]} procedure", "paragraphs": paragraphs})


def doc_text(d):
    return d["title"] + " " + " ".join(d["paragraphs"])


def _to_concepts(m):             # the surface form is first mapped to a concept
    v = [0.0] * len(KEYS)
    dm = " " + m.lower() + " "
    for i, k in enumerate(KEYS):
        if CONCEPTS[k][1] in dm:
            v[i] += 1.0
        if CONCEPTS[k][2] in dm:
            v[i] += 1.0
    return v


PROJECTION = []
for i in range(len(KEYS)):
    r = rng(SEED ^ (i + 1) * 2654435761)
    PROJECTION.append([r() * 2 - 1 for _ in range(64)])


def embed(m, dim=DIM):           # the concept is then reduced to fewer dimensions
    v = [0.0] * dim
    for i, a in enumerate(_to_concepts(m)):
        if a:
            for j in range(dim):
                v[j] += a * PROJECTION[i][j % 64]
    n = sum(x * x for x in v) ** 0.5
    return [x / n for x in v] if n else v


def cosine(a, b):
    return sum(x * y for x, y in zip(a, b))


QUERIES = []                     # FICTIONAL query set: the query side is separate from the document side
for i in range(40):
    r = rng(SEED + 104729 * i)
    d = DOCUMENTS[int(r() * len(DOCUMENTS))]
    QUERIES.append({"text": f"{CONCEPTS[d['main']][2]} {COMMON[int(r() * len(COMMON))]}",
                    "label": d["label"], "concept": d["main"]})

K, PROBES = 5, 2
WIDTH = (16, 8, 4, 2, 1)
VEC = [embed(doc_text(d)) for d in DOCUMENTS]
QVECS = [embed(q["text"]) for q in QUERIES]
REGION = [1 + int(rng(SEED ^ (i + 1) * 40503)() * 16) for i in range(len(DOCUMENTS))]


def matching(g):
    return [i for i in range(len(VEC)) if REGION[i] <= g]


def truth(qv, g, k=K):           # correct answer: exhaustive search of the filtered set
    return sorted(matching(g), key=lambda i: -cosine(qv, VEC[i]))[:k]


def build_buckets(buckets, seed):
    r, representatives = rng(seed), []
    while len(representatives) < buckets:
        i = int(r() * len(VEC))
        if i not in representatives:
            representatives.append(i)
    members = [[] for _ in representatives]
    for i in range(len(VEC)):
        members[max(range(buckets), key=lambda c: cosine(VEC[i], VEC[representatives[c]]))].append(i)
    return representatives, members


def probed(qv, representatives, members):
    order = sorted(range(len(representatives)), key=lambda c: -cosine(qv, VEC[representatives[c]]))
    return [i for c in order[:PROBES] for i in members[c]]


def recall(found, correct):
    return len(set(found) & set(correct)) / max(1, len(correct))


REPS, MEMBERS = build_buckets(16, SEED)
full = sum(recall(sorted(probed(qv, REPS, MEMBERS),
                         key=lambda i: -cosine(qv, VEC[i]))[:K], truth(qv, 16)) for qv in QVECS)
print(f"corpus {len(DOCUMENTS)} documents , 16 regions , queries {len(QUERIES)}")
print("filter width " + " / ".join(str(g) for g in WIDTH)
      + " -> matching " + " / ".join(str(len(matching(g))) for g in WIDTH))
print(f"unfiltered baseline: bucket-based index (buckets 16 , probes {PROBES}) recall {full / len(QVECS):.4f} , "
      f"{len(REPS) + sum(len(probed(qv, REPS, MEMBERS)) for qv in QVECS) / len(QVECS):.1f}"
      f" comparisons , exhaustive search {len(VEC)}")

corpus 200 documents , 16 regions , queries 40
filter width 16 / 8 / 4 / 2 / 1 -> matching 200 / 101 / 52 / 27 / 18
unfiltered baseline: bucket-based index (buckets 16 , probes 2) recall 0.9500 , 47.2 comparisons , exhaustive search 200

The five widths narrow the corpus from 200 down to 18 documents. The unfiltered baseline is the line of the previous lesson: the index retrieves 0.9500 of the five that exhaustive search gives, with 47.2 comparisons. The question to ask is this: does this number still hold when a filter is added.

Applying the Filter Afterward

The combination that asks for the least work is to filter the result without changing the search at all. The index gives as many documents as the first fetch, the ones that do not match are discarded, and the first five of what remains are returned.

def post_filter(qv, g, fetch):
    upper = sorted(probed(qv, REPS, MEMBERS), key=lambda i: -cosine(qv, VEC[i]))[:fetch]
    return [i for i in upper if REGION[i] <= g][:K]


print("width recall(fetch 5) missing results recall(fetch 15) recall(fetch 50)")
for g in WIDTH[1:]:
    s, missing = [0.0, 0.0, 0.0], 0
    for qv in QVECS:
        d = truth(qv, g)
        for n, fetch in enumerate((5, 15, 50)):
            s[n] += recall(post_filter(qv, g, fetch), d)
        missing += len(post_filter(qv, g, 5)) < len(d)
    print(f"{g:>5} {s[0] / len(QVECS):>15.4f} {missing:>15} {s[1] / len(QVECS):>16.4f}"
          f" {s[2] / len(QVECS):>16.4f}")

width recall(fetch 5) missing results recall(fetch 15) recall(fetch 50)
    8          0.4450              37           0.8900           0.8900
    4          0.1950              40           0.6800           0.7600
    2          0.1050              40           0.3850           0.6250
    1          0.0900              40           0.2600           0.4750

The first column started from 0.9500 without a filter; it falls to 0.4450 at width 8 and to 0.0900 at width 1. The third column gives the reason: below width 4, forty of the forty queries return fewer results than the correct answer. The index gives five documents, the filter discards four or five of them, and either one result or none is left. There is no ranking problem here; the result box empties.

The known remedy is over-retrieval: taking fifteen or fifty documents instead of five and filtering after that. The last two columns show how much this helps. At width 8, going up to fifteen carries 0.4450 to 0.8900 and going up to fifty adds nothing. At width 1, retrieving fifty documents gives only 0.4750. Over-retrieval hits a ceiling, and that ceiling is the first column of the next section: the number of documents that pass the filter inside the probed buckets. Asking for fifty documents does not retrieve fifty documents if there are not that many suitable documents in the buckets.

Applying the Filter Inside the Index

The second procedure never takes the non-matching document into the candidate set. The same buckets are looked at, but only the ones that pass the filter are counted and ranked.

def in_index(qv, g, representatives, members):
    candidates = [i for i in probed(qv, representatives, members) if REGION[i] <= g]
    return sorted(candidates, key=lambda i: -cosine(qv, VEC[i]))[:K], len(candidates)


SECOND = build_buckets(16, SEED + 1)
print("width candidates recall comparisons exhaustive search two-build difference")
for g in WIDTH:
    a = b = 0.0
    total = 0
    for qv in QVECS:
        d = truth(qv, g)
        r1, n1 = in_index(qv, g, REPS, MEMBERS)
        a += recall(r1, d)
        b += recall(in_index(qv, g, *SECOND)[0], d)
        total += n1
    print(f"{g:>5} {total / len(QVECS):>10.1f} {a / len(QVECS):>6.4f} "
          f"{len(REPS) + total / len(QVECS):>11.1f} {len(matching(g)):>17}"
          f" {abs(a - b) / len(QVECS):>20.4f}")

width candidates recall comparisons exhaustive search two-build difference
   16       31.2 0.9500        47.2               200               0.0100
    8       15.7 0.8900        31.6               101               0.1300
    4        7.8 0.7600        23.9                52               0.0850
    2        4.0 0.6250        20.0                27               0.1250
    1        2.8 0.4750        18.8                18               0.1100

The candidates column is the breakdown of the neighborhood. Without a filter the index weighs 31.2 documents per query; at width 1 it is 2.8. The buckets were built over the whole corpus, and a bucket was filled by similarity, not by region. As the filter narrows, the number of documents left standing inside a bucket falls, and the index comes to the point of choosing among three documents where it should choose five results. This is why recall falls from 0.9500 to 0.4750.

The real decision is read in the last three columns. While the comparisons fall from 47.2 to 18.8, the exhaustive search column falls from 200 to 18. Without a filter the index did a quarter of the work of exhaustive search; at width 1 it does more work. The width 1 row says these two things side by side: the index gives 0.4750 with 18.8 comparisons, and the exhaustive search of the filtered set gives 1.0000 with 18 comparisons. Approximate search is both expensive and wrong here. The crossover is between width 2 and 1: at width 2 the index is still seven comparisons cheaper but leaves a recall of 0.6250, and at width 1 its cheapness is gone too. Below this point, skipping the index and scanning the matching documents from start to finish wins on both axes. The added scaffolding worsening the work is the second example of this lesson, and the cause is not that the index was built badly: the index was built unaware of the constraint the query would ask.

The last column adds an instability as well. Without a filter the difference between two index builds was 0.0100, that is, the threshold of the previous lesson. With a filter the difference is between 0.0850 and 0.1300, eight to thirteen times the threshold. The same corpus, the same query, the same setting; only which documents are the representatives changes. The recall measured in a setup that works with a narrow filter is the number of that setup and does not carry over when it is built again.

Summary

• The metadata filter is an exact constraint and is different from a similarity threshold; a document that does not match cannot enter the result at any similarity value.
• Applying the filter after the search empties the result box: at width 4 and below, forty of the forty queries return fewer than five results and recall falls from 0.9500 to 0.0900.
• Over-retrieval closes this loss partly but hits a ceiling; at width 8, retrieving fifty documents does not exceed the 0.8900 that retrieving fifteen documents gives.
• In in-index filtering the candidate count falls from 31.2 to 2.8 and recall from 0.9500 to 0.4750; because the buckets are filled by similarity, the filter empties the inside of the bucket.
• At width 1 the index gives 0.4750 with 18.8 comparisons and the exhaustive search of the filtered set gives 1.0000 with 18 comparisons; the threshold is around width 2, and below it the index loses on both axes at once.
• The difference between two index builds is 0.0100 without a filter and between 0.0850 and 0.1300 with one; the recall measured with a narrow filter depends on the build.

Next Step

In all the measurements of this lesson, the link between the query and the document was built from a single place: the angle of the embedding vectors. The filter narrowed this link but did not change it. Yet the corpus also contains documents that carry the words of the query exactly, and finding them needs no embedding at all; when a document code, a date or an error number is searched, semantic similarity passes by the side of what is searched. The next lesson measures keyword matching and embedding search separately on the same query set, then fuses the ranks of the two and counts what the fusion adds. The expected thing is that the whole is better than its parts; the measured thing is that on one query class the hybrid stays worse than both of them.