Retrieval-Augmented Generation (RAG) Questions
Grounding language-model outputs in external knowledge at inference time. Covers document ingestion, chunking and embedding, sparse, dense and hybrid retrieval (BM25, score fusion, contrastive training of retrievers), vector search and approximate-nearest-neighbour index engineering (HNSW, IVF, product quantization, filtering, updates, sharding), re-ranking with cross-encoders, and context assembly with prompt templates and citations. Also covers reducing hallucination through verification and abstention, evaluating retrieval-augmented systems, and production concerns such as freshness, access control, prompt injection through retrieved documents, deletion and privacy, caching, cost, and weighing retrieval against fine-tuning. Generic LLM evaluation and release gates, the craft of prompts beyond retrieved-context templates, attention internals, parameter-efficient fine-tuning, model serving and distributed inference engineering, database indexes, and whole-product ML system design are covered elsewhere.
Explain index freshness and document versioning in a RAG pipeline. For a knowledge base updated hourly, outline a strategy to incorporate updates with minimal disruption to queries and to support point-in-time retrieval.
Sample Answer
Direct answer
A chunk is a passage-sized piece of a document, the unit that is indexed and retrieved. An embedding is the list of numbers (a vector) a model computes to represent a chunk's meaning so that similar text can be found; computing one costs model time, so re-embedding a chunk (computing its vector again) is the expensive step to avoid. Index freshness is the delay between a change in the source documents and that change being visible in retrieval results. Document versioning means keeping old versions addressable instead of overwriting them. For a knowledge base updated hourly I would not rebuild the index each hour. I would apply incremental upserts (insert or update by key) at the chunk level, using content hashes so only changed chunks are re-embedded. I would write them into a versioned store where every chunk row carries valid_from and valid_to timestamps, and publish each hourly batch as one atomic snapshot so a running query never sees half an update. Point-in-time retrieval is then a filter: "rows whose validity interval contains time t".
Mechanism, in the order it happens
- Detect change. Each hour, list changed source documents (a change feed, meaning a log or API that reports which documents were added, edited or deleted since a given time, or else a scan of modified-time stamps). Treat deletions as changes too.
- Re-chunk and hash. Re-chunk each changed document and compute a content hash per chunk (a fixed-length fingerprint of the text; equal text gives an equal hash). Chunks whose hash is unchanged keep their existing embedding. Only new hashes are embedded. In the program below, editing one chunk of a six-chunk document re-embeds 1 chunk.
- Write new rows, close old ones. For an updated document, set
valid_to = nowon its current rows and insert new rows withvalid_from = nowandversion + 1. For a delete, only close the rows. Nothing is overwritten, so history stays queryable. - Publish atomically. The hour's writes become visible together by advancing a snapshot pointer (one common pattern is an alias, a stable name that points at one index copy: queries always read through the name
kb_live; the hourly batch is loaded into a second copy,kb_v42, whilekb_livestill points at the currentkb_v41; then a single small switch repointskb_livetokb_v42, so a query sees all of the batch or none of it. Whether an engine offers this, and under what name, has to be checked for the engine you choose). A query reads the snapshot id once, at the start, and uses it for the whole request, including retrieval, citation display and any follow-up fetch. - Serve. Live queries filter
valid_to is null. Point-in-time queries filtervalid_from <= t < valid_to. - Compact. Compaction is a background job that physically removes or merges rows that are no longer needed. Old versions beyond the retention window are dropped in a background job, so an index serving 500,000 current chunks is not forever carrying every historical row.
Worked example, run
The program keeps the validity interval on each row and searches with BM25 (a keyword-scoring function: a higher score means a better keyword match, the number has no meaning on its own and is only comparable between rows scored for the same query) over the rows visible at a given time. This small store is a stand-in for whatever vector or hybrid index you run; the interval logic is what matters. Times are minutes since midnight.
import os
os.environ["OMP_NUM_THREADS"] = "1"
import hashlib
from rank_bm25 import BM25Okapi
# Versioned chunk store: every row has valid_from / valid_to (minutes since midnight). valid_to None = still current.
rows = []
def ingest(t, doc_id, text):
for r in rows:
if r["doc"] == doc_id and r["valid_to"] is None:
r["valid_to"] = t
ver = 1 + sum(1 for r in rows if r["doc"] == doc_id)
rows.append(dict(doc=doc_id, ver=ver, text=text, valid_from=t, valid_to=None))
def delete(t, doc_id):
for r in rows:
if r["doc"] == doc_id and r["valid_to"] is None:
r["valid_to"] = t
def visible(as_of):
return [r for r in rows if r["valid_from"] <= as_of and (r["valid_to"] is None or as_of < r["valid_to"])]
def search(query, as_of, k=2):
vis = visible(as_of)
bm = BM25Okapi([r["text"].lower().split() for r in vis])
scores = bm.get_scores(query.lower().split())
order = sorted(range(len(vis)), key=lambda i: (-scores[i], vis[i]["doc"]))
return [(vis[i]["doc"], vis[i]["ver"], round(float(scores[i]), 3)) for i in order[:k] if scores[i] > 0]
hm = lambda h, m: h * 60 + m
ingest(hm(8, 0), "refunds", "refund window is 30 days after purchase")
ingest(hm(8, 0), "shipping", "standard shipping takes five days")
ingest(hm(8, 0), "legacy", "legacy plan refund rules apply to old accounts")
for i, t in enumerate(["password reset steps", "invoice download guide", "api rate limits table",
"mobile app install help", "team seats and roles", "data export formats"]):
ingest(hm(8, 0), f"misc{i}", t)
ingest(hm(10, 0), "refunds", "refund window is 14 days after purchase") # hourly update
delete(hm(11, 0), "legacy") # document withdrawn
q = "refund window days"
for label, t in [("09:30", hm(9, 30)), ("10:30", hm(10, 30)), ("11:30", hm(11, 30))]:
print("as of", label, search(q, t, k=1), search("legacy plan", t, k=1))
# A reader pins its snapshot time when the request starts, so a write at 10:00 cannot change a running answer.
pinned = hm(9, 59)
ingest(hm(10, 0) + 1, "refunds", "refund window is 7 days after purchase") # arrives mid-request
print("pinned reader at 09:59:", search(q, pinned, k=1))
assert search(q, pinned, k=1)[0][1] == 1 # fails if the store rewrites history
# Embedding cost of an hourly update: chunk-level content hashes.
def chunk_hashes(chunks):
return [hashlib.sha256(c.encode()).hexdigest() for c in chunks]
old = ["intro", "plans", "refund 30 days", "contact", "faq", "legal"]
new = ["intro", "plans", "refund 14 days", "contact", "faq", "legal"]
changed = sum(a != b for a, b in zip(chunk_hashes(old), chunk_hashes(new)))
print("chunks re-embedded for this edit:", changed, "of", len(new))
total, change_rate = 500_000, 0.02
print("hourly changed chunks:", int(total * change_rate), "vs full rebuild:", total)
Output:
as of 09:30 [('refunds', 1, 3.167)] [('legacy', 1, 2.588)]
as of 10:30 [('refunds', 2, 3.167)] [('legacy', 1, 2.588)]
as of 11:30 [('refunds', 2, 3.178)] []
pinned reader at 09:59: [('refunds', 1, 3.167)]
chunks re-embedded for this edit: 1 of 6
hourly changed chunks: 10000 vs full rebuild: 500000
What the output shows. At 09:30 the refund article is version 1 and the legacy article is visible. After the 10:00 update the same query at 10:30 returns version 2 of the refund article and version 1 is still reachable if you ask for 09:30, which is the point-in-time behaviour. At 11:30 the legacy article has been withdrawn, so the "legacy plan" query returns nothing. The pinned reader that started at 09:59 still sees version 1 even though a newer version was written during its request, and the assert in the program fails if the store ever rewrites history in place. One detail: the refund article scores 3.167 at 09:30 and 10:30 but 3.178 at 11:30 although its text is identical. BM25 weights each word by how rare it is among the rows being searched, and withdrawing the legacy article changes both the row count and how many rows contain each word. "Refund" is now in 1 of 8 rows instead of 2 of 9, so it counts as rarer and weighs more; "window" and "days" weigh slightly less because the collection is smaller, and the average row length shifts too. These effects partly cancel, so the total moves only slightly. Nothing is wrong; keyword scores depend on the rows visible at that moment. The last two lines are the cost argument: at an assumed 500,000 chunks and 2 percent hourly change (assumptions, not measurements), an incremental update touches 10,000 chunks, a full rebuild 500,000.
Trade-offs and failure modes
- Visibility lag versus disruption. Batching hourly means a change can wait up to an hour. If some documents must be searchable within minutes (a policy withdrawal), give them a fast path: a small "recent" index searched alongside the main one and merged into it on the hourly cycle.
- Deletes are the dangerous operation. A deleted or access-revoked document that stays retrievable is worse than a stale one. Close the row in the same snapshot and make deletes a high-priority path with an alarm if the delete is not visible within the stated time.
- Mixed embedding versions. If the embedding model changes, old and new vectors are not comparable. Build the new index in the background under a new alias, evaluate it against the old one on the labelled set, then switch the alias. Never mix vectors from two models in one index.
- Consistency with caches and citations. Anything downstream that stores answers must key on the snapshot or document version (a cache of previous answers, for example). A citation should record the document id and version it was retrieved from, so "what did the user see at 10:30" is answerable.
- Storage and compaction cost. History multiplies rows. Keep full history only as long as audit or point-in-time requirements demand.
- Common mistake: rebuilding the whole index in place each hour. Queries during the rebuild see missing or duplicate documents, and cost scales with corpus size instead of change size.
Monitoring
Track end-to-end freshness (time from source change to first retrieval hit, measured with a canary document: a test document you edit on purpose on a schedule and time until the edit shows up in search results), the number of chunks re-embedded per run, snapshot publish failures, and the age of the oldest unapplied change.
You need to index PDFs and scanned documents (OCR noise) into a vector store. Outline preprocessing steps to improve retrieval quality: OCR cleanup, layout-aware chunking, table extraction, and metadata enrichment. Mention tools and heuristics.
Sample Answer
Direct answer
Retrieval quality on messy PDFs is decided before any embedding is computed. Work in this order: decide per page whether it has a real text layer (the machine-readable characters embedded in the file) or needs OCR (optical character recognition, turning page images into text), clean the OCR output, rebuild reading order (the sequence in which a human would read the blocks of the page) and structure, chunk along that structure instead of at fixed lengths, convert tables into text that keeps each cell attached to its row and column header, and attach metadata (document, page, section, table title) to every chunk. Then measure retrieval on a labelled question set so each step earns its place.
Step by step
- Triage each page. A born-digital PDF (one created directly by software, not scanned) has an embedded text layer; a scan is only an image. Extract the text layer when it exists and OCR only the pages without one (or where the layer is garbage). Deskewing (rotating a slightly tilted scan until the text lines are horizontal) and removing speckle before OCR often helps scans. Keep the OCR engine's per-word confidence if it provides one, and flag low-confidence pages for review.
- OCR cleanup. Typical defects and the heuristic for each. The first two are cheap and touch most pages, so do them first; the vocabulary correction is the riskiest, so do it last and conservatively:
- Repeated headers, footers and page numbers: drop lines that recur on most pages. They add the same words to every chunk, which wastes tokens and can dilute keyword scores.
- Words hyphenated across line breaks (
agree-thenment): join when a hyphen ends a line and the next line starts lowercase. - Ligature glyphs (
fi: one character that prints the two letters f and i together) and Unicode variants: normalise to plain letters. - Character confusions (
rnread asm,lread as1,Oread as0): correct against a domain vocabulary with fuzzy matching (accept the closest vocabulary word when its string similarity is above a cut-off), and be conservative, because a wrong "fix" of a part number or a name is worse than noise. Never auto-correct tokens that contain digits. - Two-column pages read across the gutter: use a layout-analysis step (a model or rule set that finds columns, headings, tables and figures on the page image) to detect columns and order blocks column by column.
- Layout-aware chunking. Split on headings, list items and paragraph boundaries, keep a heading with its body, and only then enforce a token limit (a maximum chunk size) with a small overlap (the last few words of one chunk repeated at the start of the next, so a sentence cut at the boundary survives in one of them). Prefix each chunk with its heading path so a chunk that says "within sixty days" also says which clause it belongs to.
- Table extraction. A table flattened into a stream (
Uptime Credit 99.9% 0% 99.0% 10%) loses which value belongs to which header. Extract the grid with a table-aware tool, then store each row as a sentence (Uptime 99.0%, Credit 10%) with the table title. For wide tables, repeat the headers in every row chunk; keep the original table or image reference in metadata so the generator or a human can look at it. - Metadata enrichment. Store document id, title, page, section path, table title, document date, language, OCR confidence and access label. Use them to filter at query time (restrict to one contract, drop superseded versions) and to build citations. Optionally add a short LLM-written summary or a list of likely questions per chunk, treated as a retrieval aid and checked, since it can add errors.
- Tools, as examples. An OCR engine such as Tesseract, a PDF text and table library such as pdfplumber or Camelot, and a layout-detection model for complex pages. Choose by measuring on your own documents.
Worked example
The program builds a three-page "contract" with the defects above, as hand-written OCR-like text (a stand-in for real OCR output), and compares two pipelines with BM25 (rank_bm25 0.2.2; a keyword scorer that rewards query words that are rare overall and frequent in a short chunk) as the retriever: fixed 14-word windows over the raw text versus cleanup plus heading and table aware chunks. Each of six questions is paired with an anchor string that appears cleanly in its gold chunk, and the metric is the rank of the first chunk containing the anchor. Recall@1 is the share of questions whose gold chunk is ranked first; MRR (mean reciprocal rank) averages 1 / rank of the gold chunk over the questions, so rank 2 scores 0.5 and a miss (rank 99 below) scores almost 0. The raw text is the three pages exactly as written in the pages list: headers and Page N lines on every page, agree- and ment on two lines, terrnination, the fi ligature and the table as | separated lines. Six questions is far too few to estimate a real improvement; the point is to show the mechanism and the measurement method.
import os
os.environ["OMP_NUM_THREADS"] = "1"
import re, difflib
from collections import Counter
import numpy as np
from rank_bm25 import BM25Okapi
# Three scanned pages as OCR returned them (hand-written noisy stand-in for real OCR output).
pages = [
["ACME Cloud Services Agreement - Confidential", "1. Termination",
"Either party may terminate this agree-", "ment with thirty days written notice. Refunds are issued",
"within sixty days of termina-", "tion.", "Page 1"],
["ACME Cloud Services Agreement - Confidential", "2. Service Levels",
"Table 1: Uptime credits", "Uptime | Credit", "99.9% | 0%", "99.0% | 10%", "95.0% | 25%",
"The final credit is applied to the next invoice.", "Page 2"],
["ACME Cloud Services Agreement - Confidential", "3. Data Retention",
"Customer data is retained for ninety days after terrnination", "and is then deleted from all systems.",
"Backups are purged within one hundred eighty days.", "Page 3"],
]
def strip_repeated(pages):
cnt = Counter(l for p in pages for l in set(p))
rep = {l for l, c in cnt.items() if c >= 2 or re.fullmatch(r"Page [0-9]+", l)}
return [[l for l in p if l not in rep and not re.fullmatch(r"Page [0-9]+", l)] for p in pages]
VOCAB = ["termination", "agreement", "retention", "deleted", "invoice", "final", "refunds", "customer"]
def fix_word(w):
w = w.replace("fi", "fi").replace("fl", "fl")
core = w.rstrip(".,;:"); tail = w[len(core):] # keep trailing punctuation out of the vocabulary match
m = difflib.get_close_matches(core.lower(), VOCAB, n=1, cutoff=0.85)
return (m[0] if m and m[0] != core.lower() else core) + tail
def clean_lines(lines):
text = "\n".join(lines)
text = re.sub(r"-\n([a-z])", r"\1", text) # de-hyphenate across a line break
text = text.replace("\n", " ")
return " ".join(fix_word(w) for w in text.split())
def layout_chunks(pages):
chunks, doc = [], "ACME Cloud Services Agreement"
for pno, lines in enumerate(strip_repeated(pages), 1):
sec, buf, table = None, [], []
def flush():
if buf:
chunks.append({"text": f"{doc} | {sec} | " + clean_lines(buf), "page": pno})
buf.clear()
i = 0
while i < len(lines):
l = lines[i]
if re.fullmatch(r"[0-9]+\. .+", l):
flush(); sec = l
elif l.startswith("Table"):
flush(); title = l
hdr = [h.strip() for h in lines[i + 1].split("|")]
j = i + 2
while j < len(lines) and "|" in lines[j]:
row = [c.strip() for c in lines[j].split("|")]
chunks.append({"text": f"{doc} | {sec} | {title} | " + ", ".join(f"{h} {v}" for h, v in zip(hdr, row)), "page": pno})
j += 1
i = j - 1
else:
buf.append(l)
i += 1
flush()
return chunks
def naive_chunks(pages, size=14):
words = " ".join(l for p in pages for l in p).split() # raw OCR, no cleanup
return [{"text": " ".join(words[i:i + size]), "page": 0} for i in range(0, len(words), size)]
tok = lambda s: re.findall(r"[a-z0-9]+(?:\.[0-9]+)?%?", s.lower()) # "days." and "days" are the same token; "99.0%" stays whole
# each query is paired with an anchor string that sits in the gold chunk and is spelled cleanly even in the raw OCR text
queries = [
("how many days notice to terminate the agreement", "thirty days"),
("how long are refunds issued after termination", "within sixty"),
("what credit if uptime is 95.0%", "25%"),
("credit for 99.0% uptime", "10%"),
("how long is customer data retained after termination", "ninety days"),
("when are backups purged", "one hundred eighty"),
]
def evaluate(chunks, name):
bm = BM25Okapi([tok(c["text"]) for c in chunks]); ranks = []
for q, ans in queries:
order = np.argsort(-bm.get_scores(tok(q)), kind="stable")
r = next((k + 1 for k, i in enumerate(order) if ans.lower() in " ".join(chunks[i]["text"].lower().split())), None)
ranks.append(r if r else 99)
hit1 = np.mean([r == 1 for r in ranks]); mrr = np.mean([1 / r for r in ranks])
print(f"{name:14s} chunks={len(chunks):2d} answer-rank per query={ranks} recall@1={hit1:.2f} MRR={mrr:.3f}")
evaluate(naive_chunks(pages), "raw+fixed")
lc = layout_chunks(pages)
evaluate(lc, "cleaned+layout")
for k, c in enumerate(lc):
print(f"chunk {k}: page {c['page']}:", c["text"])
nv = naive_chunks(pages)
print("raw window that ends the retention sentence:", [c["text"] for c in nv if "backups" in c["text"].lower()])
print("raw window that starts with the cut phrase's tail:", [c["text"] for c in nv if "eighty" in c["text"].lower()])
bm = BM25Okapi([tok(c["text"]) for c in lc])
print("query 1 BM25 scores, rank 1 and rank 2 chunk ids:", [(int(i), round(float(bm.get_scores(tok(queries[0][0]))[i]), 2)) for i in np.argsort(-bm.get_scores(tok(queries[0][0])), kind="stable")[:2]])
Output:
raw+fixed chunks= 8 answer-rank per query=[2, 1, 1, 1, 1, 99] recall@1=0.67 MRR=0.752
cleaned+layout chunks= 6 answer-rank per query=[2, 1, 1, 1, 1, 1] recall@1=0.83 MRR=0.917
chunk 0: page 1: ACME Cloud Services Agreement | 1. Termination | Either party may terminate this agreement with thirty days written notice. Refunds are issued within sixty days of termination.
chunk 1: page 2: ACME Cloud Services Agreement | 2. Service Levels | Table 1: Uptime credits | Uptime 99.9%, Credit 0%
chunk 2: page 2: ACME Cloud Services Agreement | 2. Service Levels | Table 1: Uptime credits | Uptime 99.0%, Credit 10%
chunk 3: page 2: ACME Cloud Services Agreement | 2. Service Levels | Table 1: Uptime credits | Uptime 95.0%, Credit 25%
chunk 4: page 2: ACME Cloud Services Agreement | 2. Service Levels | The final credit is applied to the next invoice.
chunk 5: page 3: ACME Cloud Services Agreement | 3. Data Retention | Customer data is retained for ninety days after termination and is then deleted from all systems. Backups are purged within one hundred eighty days.
raw window that ends the retention sentence: ['terrnination and is then deleted from all systems. Backups are purged within one hundred']
raw window that starts with the cut phrase's tail: ['eighty days. Page 3']
query 1 BM25 scores, rank 1 and rank 2 chunk ids: [(4, 3.59), (0, 3.33)]
What the run shows:
- With raw text and fixed windows, the retention question (
terrninationis misspelt in the raw text) still finds its chunk, but the last question fails because a fixed 14-word window cut the phrase "one hundred eighty" across two chunks: the window printed first ends at "one hundred" and the one printed next begins with "eighty" (rank 99 is the placeholder for "never retrieved"). - Cleanup did four visible things in the printed chunks: the repeated header and the
Page Nlines are gone,agree-+mentis joined,terrninationis corrected toterminationandfinaltofinal. The six questions do not isolate those steps, though. Their anchors are spelled cleanly in the raw text, so the two rows differ mainly in where the chunk boundaries fall (the cut "one hundred eighty" above), and a six-question set cannot show that any one cleanup step helps. To test a step, switch that one step off and re-run the same evaluation on questions that use the damaged words. - With cleanup and structure-aware chunks, five of six questions rank the gold chunk first. The first question ranks it second in both pipelines: the tokenizer keeps stop words, and the short "final credit" sentence (chunk 4 in the cleaned set) is the only chunk containing "to" and "the", two words of the question, so BM25 scores it 3.59 against 3.33 for the gold chunk 0. Dropping stop words or adding a vector retriever would address that; structure alone does not fix everything.
- The tokenizer matters to the comparison. If it left punctuation attached to words, "days." and "days" would count as different tokens and the raw text would look worse than it is; here punctuation is split off, so the difference between the two rows is not a tokenizer quirk.
- The page 2 table became three row chunks (chunks 1, 2 and 3: 99.9%, 99.0% and 95.0%), each tied to the table title and its column headers, plus chunk 4 for the sentence after the table, instead of a stream of numbers. Page 1 became chunk 0 and page 3 chunk 5, so the six chunks are all printed.
Trade-offs and common mistakes
- Aggressive cleanup can destroy evidence (identifiers, legal numbers). Keep the raw text next to the cleaned text and index the cleaned one.
- Layout-aware chunks vary in size; very long sections still need a token cap, and very short ones may need merging with a neighbour.
- Row-per-chunk tables suit lookup questions ("what credit at 95%") but not "summarise the table"; keep a table-level chunk as well when both are needed.
- OCR noise can hurt exact-term search and embedding search; measure both retrievers on the cleaned and the raw text rather than assuming.
- Mistake: tuning chunk size on a handful of queries. Build a labelled set from real questions first, then compare pipelines on it.
A large ANN index must support frequent inserts, updates and deletes while keeping query latency low. What update strategies would you consider and what are the trade-offs between in-place online updates and batch rebuilds?
Sample Answer
Direct answer
There are three update strategies, and production systems combine them. In-place online updates change the live index with every write: freshest, but the index structure slowly gets worse and writes compete with queries. Batch rebuild builds a clean index from the source data on a schedule: best structure, but stale between rebuilds and expensive. A write log plus a small side index keeps the main index untouched: new writes go to an append-only log and a small searchable buffer that every query also scans, so they are visible at once, and a periodic rebuild folds the log into the main index. Its price is extra work per query that grows with the buffer, which is why the rebuild exists. The blue-green swap, listed third below, is not a separate strategy: it is how a rebuilt index goes live without downtime. I would recommend log plus buffer plus a periodic rebuild swapped in blue-green, because it gives bounded freshness without letting the main index decay.
The options, with what each costs
An ANN index (approximate nearest neighbour: a structure that finds close vectors without comparing against all of them) is built for a fixed set of vectors. Mutation breaks that assumption in different ways depending on the structure:
- Incremental add and delete in place. Adding a vector to a graph index means linking it to its neighbours; adding it to an IVF index (inverted file: vectors grouped into cells around k-means centroids, a query scans only the nearest cells) means putting it in the nearest cell. A delete is usually a tombstone (a mark that hides the row from results; the row is still read, and space is reclaimed later). Costs: writes take locks or compete for CPU with queries, so tail latency rises during write bursts; tombstones accumulate, so scans waste work; and the structure was shaped by the data it first saw, so it degrades when the data distribution moves. In an IVF index a cell is the group of vectors closest to one centroid (a centre point found by k-means), and in-place inserts leave the centroids frozen, never moving them. Drift means the new vectors come from regions of space the old data did not cover. A new vector then lands in whichever old centroid is nearest, even if that centroid is far away, so some cells swell and mix unrelated vectors, and a query that scans a fixed number of cells spends its budget on those big mixed cells while the neighbours it wants may sit in cells it does not pick. The "largest cell" column in the run below shows it on this seed (1345 rows for in-place against 1045 after a rebuild), but cell size alone is a weak signal because k-means cells are uneven even after a rebuild; the dependable symptom is lower recall at equal work, which the comparison tables show.
- Periodic full rebuild. Retrain and rebuild from the source of truth. Costs: CPU and time proportional to the whole corpus, writes since the last build are invisible, and you need a place to build it.
- Blue-green traffic shift (how a rebuild or merge goes live; it combines with options 2 and 4). Keep the live version ("blue") serving, build a new version ("green") on the side from a snapshot plus the log, check it, shift traffic gradually (for example 1, 10, 100 percent), and keep blue for fast rollback. Cost: both versions are resident at once, so peak storage is about double, and you need to replay any writes that arrived during the build.
- Append-only write log with periodic rebuild (the log-structured approach). Every write is appended to a durable log with a sequence number. A small delta index (often just brute-force scanned, since it is small) holds recent upserts and a set of deleted ids. A query searches the main index and the delta, drops deleted ids, and merges by score. A background job rebuilds the main index from the log, then swaps.
Consistency, freshness and write throughput
- Freshness is the time from a write being accepted to it appearing in results. With a delta buffer it is the time to append and make the buffer searchable; with only batch rebuild it is up to the rebuild interval plus build time.
- Write throughput is limited in the delta design by the cost of scanning the buffer on every query. The buffer is searched by brute force, so its size is paid per query. Merging it into the main index is the lever: smaller buffer, cheaper queries, more frequent merges.
- Consistency: give every write a sequence number and have a query record the highest sequence it has seen, so a reader can ask for read-your-writes ("wait until the index has applied sequence N"). In the swap, the green version must replay the log up to the sequence at which traffic moves, otherwise writes made during the build appear to vanish. Deletes need the most care: a deleted id must be filtered out at query time until the main index has been rebuilt without it, otherwise a deleted (or access-revoked) document can still be returned.
A computed comparison
Stand-ins: the index below is a small from-scratch IVF built with scikit-learn 1.5.2 k-means, not a production engine, and the data are synthetic Gaussian clusters. The first 12000 vectors are indexed; 12000 more arrive later from different cluster centers (the content drifted). Search effort is fixed at 3 cells per query. Work is counted as distance computations per query, not seconds. Recall@10 is measured against exact brute force; in the first table the log-plus-buffer rows use an exact answer over the rows that exist at that point, so they are not on the same data as rows A and C and should not be compared with them. A second table, printed after the first, puts all three strategies on the same corpus and the same exact answer at three moments (500, 2000 and 12000 new rows present), and that is the table to compare. The column dist/query is the average number of distance computations per query.
import os
os.environ["OMP_NUM_THREADS"] = "1"
import numpy as np
from sklearn.cluster import KMeans
rng = np.random.default_rng(0)
d, ncell, k, nprobe = 32, 40, 10, 3
def mixture(centers, n):
return (centers[rng.integers(0, len(centers), n)] + rng.normal(size=(n, d))).astype("float32")
old_centers = rng.normal(size=(ncell, d)) * 0.8
new_centers = rng.normal(size=(ncell, d)) * 0.8 # the content topics drift: new regions of space appear
X_old = mixture(old_centers, 12000)
X_new = mixture(new_centers, 12000) # inserted later, online
X_all = np.vstack([X_old, X_new])
Q = np.vstack([mixture(old_centers, 100), mixture(new_centers, 100)])
def exact(Xs, Q, k):
d2 = (Q**2).sum(1)[:, None] - 2 * Q @ Xs.T + (Xs**2).sum(1)[None, :]
return np.argsort(d2, axis=1)[:, :k]
truth = exact(X_all, Q, k)
def assign(Xs, C):
d2 = (Xs**2).sum(1)[:, None] - 2 * Xs @ C.T + (C**2).sum(1)[None, :]
return d2.argmin(1)
def search(Xs, cell, C, Q, nprobe, extra_ids=None):
"""IVF search; extra_ids are rows in an unindexed delta buffer that are always scanned (brute force)."""
found, ops = [], 0
for q in Q:
cd = ((C - q) ** 2).sum(1)
cells = np.argsort(cd)[:nprobe]
ids = np.where(np.isin(cell, cells))[0]
if extra_ids is not None:
ids = np.union1d(ids, extra_ids)
ops += len(ids)
dd = ((Xs[ids] - q) ** 2).sum(1)
found.append(ids[np.argsort(dd)[:k]])
return found, ops / len(Q)
def recall(found):
return np.mean([len(set(f) & set(t)) / k for f, t in zip(found, truth)])
# the index was trained on old data only
km0 = KMeans(ncell, n_init=1, random_state=0).fit(X_old)
C0 = km0.cluster_centers_
print("strategy recall@10 dist/query largest cell")
# A. in-place: new vectors go into the nearest EXISTING cell, centroids never move
cellA = assign(X_all, C0)
f, ops = search(X_all, cellA, C0, Q, nprobe)
print(f"A in-place, frozen centroids {recall(f):9.3f} {ops:10.0f} {np.bincount(cellA).max():12d}")
# B. write log + brute-force delta: old rows indexed, new rows in a small buffer scanned every query
for delta in (500, 2000, 12000):
cellB = np.concatenate([km0.labels_, np.full(len(X_all) - len(X_old), -1)])
extra = np.arange(len(X_old), len(X_old) + delta) # only the first `delta` new rows exist yet
present = np.arange(len(X_old) + delta)
# ground truth must be over the rows that exist at this point
tr = exact(X_all[present], Q, k)
found, ops = [], 0
for q in Q:
cells = np.argsort(((C0 - q) ** 2).sum(1))[:nprobe]
ids = np.union1d(np.where(np.isin(km0.labels_, cells))[0], extra)
ops += len(ids)
dd = ((X_all[ids] - q) ** 2).sum(1)
found.append(ids[np.argsort(dd)[:k]])
rec = np.mean([len(set(a) & set(b)) / k for a, b in zip(found, tr)])
print(f"B log + delta buffer of {delta:5d} rows {rec:9.3f} {ops/len(Q):10.0f} {np.bincount(km0.labels_).max():12d}")
# C. rebuild: retrain centroids on everything, reassign (this is the new version of a blue-green swap)
kmC = KMeans(ncell, n_init=1, random_state=0).fit(X_all)
f, ops = search(X_all, kmC.labels_, kmC.cluster_centers_, Q, nprobe)
print(f"C full rebuild {recall(f):9.3f} {ops:10.0f} {np.bincount(kmC.labels_).max():12d}")
# storage during a blue-green swap: both versions are resident until traffic has moved
n_all = len(X_all)
bytes_per_vec = d * 4
print(f"\nblue-green swap: live index {n_all*bytes_per_vec/1e6:.2f} MB + new version {n_all*bytes_per_vec/1e6:.2f} MB "
f"= {2*n_all*bytes_per_vec/1e6:.2f} MB (2.0x) until the old version is dropped")
# same corpus, same ground truth for all three strategies: old rows plus the first `delta` new rows exist
print("\nSame corpus and same ground truth for every row (old rows + the first `delta` new rows)")
print("delta strategy recall@10 dist/query")
for delta in (500, 2000, 12000):
Xp = X_all[: len(X_old) + delta]
trp = exact(Xp, Q, k)
rec = lambda found: np.mean([len(set(f) & set(t)) / k for f, t in zip(found, trp)])
f, ops = search(Xp, assign(Xp, C0), C0, Q, nprobe) # A: new rows join the nearest old cell
print(f"{delta:5d} A in-place, frozen centroids {rec(f):9.3f} {ops:10.0f}")
extra = np.arange(len(X_old), len(Xp)) # B: old index untouched + buffer scanned every query
f, ops = search(Xp, np.concatenate([km0.labels_, np.full(delta, -1)]), C0, Q, nprobe, extra_ids=extra)
print(f"{delta:5d} B log + delta buffer {rec(f):9.3f} {ops:10.0f}")
kmP = KMeans(ncell, n_init=1, random_state=0).fit(Xp) # C: retrain on everything present
f, ops = search(Xp, kmP.labels_, kmP.cluster_centers_, Q, nprobe)
print(f"{delta:5d} C full rebuild {rec(f):9.3f} {ops:10.0f}")
Output:
strategy recall@10 dist/query largest cell
A in-place, frozen centroids 0.703 2256 1345
B log + delta buffer of 500 rows 0.786 1513 545
B log + delta buffer of 2000 rows 0.862 3013 545
B log + delta buffer of 12000 rows 0.934 13013 545
C full rebuild 0.818 2040 1045
blue-green swap: live index 3.07 MB + new version 3.07 MB = 6.14 MB (2.0x) until the old version is dropped
Same corpus and same ground truth for every row (old rows + the first `delta` new rows)
delta strategy recall@10 dist/query
500 A in-place, frozen centroids 0.733 1064
500 B log + delta buffer 0.786 1513
500 C full rebuild 0.731 946
2000 A in-place, frozen centroids 0.714 1219
2000 B log + delta buffer 0.862 3013
2000 C full rebuild 0.735 1129
12000 A in-place, frozen centroids 0.703 2256
12000 B log + delta buffer 0.934 13013
12000 C full rebuild 0.818 2040
What the run shows, on this synthetic drift only:
- A (in-place, centroids frozen) put every new vector in an existing cell. At similar work (2256 distance computations per query) recall is 0.703, and one cell grew to 1345 rows. The cells no longer describe the data.
- C (full rebuild) retrained the centroids and gave recall 0.818 at 2040 computations per query, with the largest cell at 1045. So at about the same work, with 12000 drifted rows present, the rebuild bought roughly 0.12 recall in this setup; that is the cost of not rebuilding. The second table shows the rebuild pays only once drifted rows are a large share of the corpus: with 500 new rows present C scores 0.731 against 0.733 for A, and with 2000 it scores 0.735 against 0.714.
- B (log plus delta buffer) keeps the old index unchanged and brute-forces the recent rows. Per-query work grows with the buffer (1513, 3013, 13013 for buffers of 500, 2000 and 12000 rows), which is why the buffer must stay small and be merged on a schedule.
- Side by side on the same data (second table). With 500 new rows present, A scores 0.733 for 1064 computations per query, B 0.786 for 1513 and C 0.731 for 946. With 12000 present, A is 0.703 for 2256, B is 0.934 for 13013 and C is 0.818 for 2040. So B has the best recall at every size because it scans the new rows exactly, and it pays for that in work per query: at 12000 rows it does about 6.4 times the work of C (13013 against 2040) for 0.116 more recall. B is therefore not a free win over a rebuild; what it buys is that new rows are searchable immediately, with the main index untouched, while the rebuild is still being prepared. C is cheap per query and is the only option here that restores clean cells, but its recall in this toy is limited because the search effort is fixed at 3 cells and 40 cells must cover 80 true clusters (40 old, 40 new); the table shows the trade between work and recall, not a ranking to carry to production.
- Blue-green needs double the storage while both versions exist (3.07 MB twice for this toy set; the same 2.0x factor applies to a real index, plus the build's working memory).
Recommendation and what would flip it
Use log plus delta buffer for freshness, a scheduled rebuild (trigger on buffer size, tombstone fraction, or a drop in measured recall against an exact sample, whichever comes first), and a blue-green swap with rollback. Flip to pure in-place updates if the data distribution is stable, writes are modest and the engine handles deletes by repairing its graph. Flip to nightly batch rebuild only if staleness of hours is acceptable to the product.
Common mistakes
- Treating a delete as done when the row is tombstoned but still returned by a stale replica or the unmerged buffer.
- Rebuilding on a fixed timetable and never measuring recall, so drift goes unnoticed.
- Forgetting that blue-green needs the log replay, and the extra storage.
- Quoting freshness as an average; the tail (the slowest writes to become visible) is what users notice.
That is every published Retrieval-Augmented Generation (RAG) question for Data Engineer so far. Browse the other topics in this category, or practice this one interactively.