Chapter 17: Operating a Vector Store

00-START-HERE · 01-READING-ROUTES · 16_compression_and_index_economics · 18_classical_ir_you_are_expected_to_know This chapter prepares you to operate the retrieval layer of a Retrieval-Augmented Generation (RAG) system under deletion, growth, metadata, filtering, and natural-language constraints.

TL;DR

• HNSW supports online insertion. Deletion must preserve result exclusion and a usable search structure; tombstones plus a later rebuild are a common design, not the only possible implementation.
• Optimize rebuild cadence against comparable work costs, measured latency, and the applicable completion obligation. Include build, validation, propagation and concurrent-update catch-up time; inspect deleted nodes encountered during search, not only the already-clean result list.
• Sharding addresses per-node capacity, replication supplies additional serving copies, and key partitioning can reduce fan-out. Throughput and availability gains depend on load balance, routing and failure policy.
• Choose the database around durability, filtering, topology, writes, tenancy and operations. ANN is a small term in the worked latency scenario, not in every production workload.
• Hard filtering can exclude relevant evidence irrecoverably within that retrieval path. A product of metadata coverage and accuracy is a bound only under the stated query-conditioned equality-gate assumptions, not from global metadata averages alone.
• Choose filtering from matching-set size, actual ranked-candidate survival, concurrency and measured costs. The exact-scan and post-filter thresholds below belong to explicit models, not universal selectivity regimes.
• Validate model-extracted constraints without silently changing the user's intent. A fallback must restore relevant query terms, retain authorization, and be evaluated independently. Trusted tenant and ACL enforcement remains outside model control.

The story

Imagine a vast public library whose books are arranged by a walking map rather than by shelf number. The walking map is the vector index. Nearby books discuss similar ideas, and the librarian follows links from one shelf to the next to reach a useful answer. Adding a new book is manageable. The librarian walks the existing map, finds nearby shelves, and draws new links. Removing a book is harder because that book may be the bridge between two wings. The library can put a red sticker on a withdrawn book. That tombstone prevents the book from being handed to a reader while its search representation may still guide the librarian's route. The sticker does not erase the book or its copies. The library can build a clean map beside the old one, but must budget temporary capacity, validate it, and replay intervening changes before switching. When the collection outgrows one building, the director separates three decisions. Sharding distributes books; a broad question may still visit every building. Replication creates extra serving copies, with additional storage and synchronization. Partitioning uses a key such as tenant or region to skip buildings, provided the key is correct and the resulting traffic is balanced. Choosing the library building is not a race for the fastest hallway. The director must ask whether records survive a crash, whether catalog rules run before retrieval, whether the building is in the right region, and who answers the alarm at night. The hallway walk can be less than one millisecond, while a remote building or a reranking desk consumes tens or hundreds of milliseconds. The catalog has three kinds of labels. The registrar supplies system-of-record fields such as owner and permission. The document processor recovers structural fields such as heading and page. A model generates labels such as document type or summary. None is automatically complete or correct. A soft label can push the right book out of the final result list; a hard rule can exclude it before ranking even begins. Filtering is the gate at the reading room. A tiny admitted set can make a complete exact scan attractive. A broad predicate may leave enough results after global retrieval, but only if enough highly ranked items actually pass. Between those cases, filter-aware traversal can help avoid paths broken by masking. A preference such as recency should not silently become a validity rule; permissions remain mandatory. A reader may ask for last quarter's board deck without filling out a catalog form. An intake clerk can split the request into topic words and a proposed date-and-type predicate using the real schema, authorized value catalog, reference date, timezone and calendar convention. An absent value may mean a bad alias, a stale catalog, or a legitimate empty answer—not necessarily an extraction error. The clerk clarifies or makes an explicit, logged broadening fallback when appropriate. The library enforces permission independently on every path.

Decoder table

Core mechanics

Mathematical conventions

Storage is decimal unless a binary unit is named: $1\,\mathrm{kB}=10^3\,\mathrm B$, $1\,\mathrm{MB}=10^6\,\mathrm B$, $1\,\mathrm{GB}=10^9\,\mathrm B$, $1\,\mathrm{TB}=10^{12}\,\mathrm B$, and $1\,\mathrm{KiB}=2^{10}\,\mathrm B$. A configuration label written as KB needs its implementation-specific unit checked. Retain full precision until reporting; round required integer resources upward, but round a capacity limit downward. In the lifecycle model, $N$ is the fixed live population, $c$ is its replacement fraction per day, $T$ is in days, and $\lambda$ is queries per day. Resident population can exceed $N$. $\mathrm{efConstruction}$ and $\mathrm{efSearch}$ control retained candidate widths; neither equals a guaranteed expansion count or a distance-evaluation cap. Products of beam width and degree below are explicitly stipulated work proxies, not HNSW complexity identities. Build and query work must be converted to a common cost currency before comparing them economically. For HNSW memory, use the chapter-16 allocation model: four-byte neighbor identifiers, $2M$ base-layer slots, $M$ upper-layer slots, and $\Pr(\ell\ge j)=M^{-j}$ for $j\ge1$. Expected allocated link bytes are $\mathbb E[b_{\mathrm{link}}]=4(2M+M/(M-1))\,\mathrm B$. At $M=16$ this is approximately $132.266667\,\mathrm{B/vector}$. These are expected slot budgets, not populated degree counts or complete resident-memory measurements; identifiers, level records, allocators, payloads, caches and build scratch space are additional. $S_{\mathrm{sh}}$ counts shards, $R_{\mathrm{rep}}$ counts replicas per shard, $P_{\mathrm{part}}$ counts key partitions, and $S_{\mathrm{surv}}$ counts post-filter survivors. $R$ denotes a retrieval score, not a replication factor. For gold set $G_q$ and returned set $A_k(q)$, $\mathop{\mathrm{Recall}}\nolimits @k(q)=|G_q\cap A_k(q)|/|G_q|$ when $|G_q|\gt 0$, whereas $\mathop{\mathrm{Hit}}\nolimits @k(q)=\mathbf1[G_q\cap A_k(q)\ne\varnothing]$. They coincide for one gold item. Metadata bounds and extraction examples state which population and metric they use. A multiply-accumulate (MAC) counts as two nominal FLOPs here. Bandwidth and FLOP calculations omit filtering, gathers, heaps, memory hierarchy, network, contention and queueing unless stated. Component estimates do not add up to an end-to-end $p_{99}$ guarantee. Empirical source results remain reported inputs, not results proved by the arithmetic.

17.1 Static index, dynamic corpus: tombstones and re-indexing

Static assumptions and online insertion

• What changes: skip-list occupancy and HNSW height have distributional models, with characteristic height on the order of $\log_M N$ under the usual level law. They do not require an immutable corpus. HNSW supports insertion; IVF cells and PQ codebooks instead need their training distribution and drift monitored as the corpus changes.
• Online insertion: search using $\mathrm{efConstruction}$, select diverse neighbors, and update links. The parameter controls a candidate width, not a fixed number of visited nodes.
• Deletion latency: in the source's example, a request at 10:00 followed only by a midnight rebuild leaves $14\,\mathrm h$ without immediate serving exclusion. A read-time deletion check can close that serving gap without claiming physical erasure.
• Worked proxy: take $N=10^7$, $d=768$ fp32, $M=16$, $M_0=32$ and $\mathrm{efConstruction}=200$. Stipulate $200$ expansion-equivalents at $32$ tested neighbors each, so one insert is budgeted as $6{,}400$ distance evaluations. This is a planning proxy, not a bound implied by $\mathrm{efConstruction}$.
• With $c=0.02\,\mathrm{day^{-1}}$, replacing $2\times10^5$ live vectors daily gives $1.28\times10^9$ insert-proxy evaluations per day. Charging the same proxy to all $N$ insertions gives rebuild work $B=6.4\times10^{10}$ evaluations, so daily insert work is $2\%$ of that proxy rebuild. Upper layers, edge pruning, writes and scheduling are omitted.

Structural deletion: costs and connectivity risks

• Structural deletion removes a node and updates the references needed for a usable remaining graph. Logical exclusion, physical byte removal, and preservation of search quality are separate requirements.
• HNSW normally records outgoing adjacency. A reverse-edge index can locate incoming references quickly; without it they can be found by scanning outgoing edges, at potentially $O(|E|)$ work. Reverse storage is an efficiency choice, not a logical prerequisite for deletion.
• A toy budget of $32$ incoming base-layer identifiers at $4\,\mathrm B$ each adds $128\,\mathrm{B/vector}$, or $1.28\,\mathrm{GB}$ at $N=10^7$. Adding this to the expected forward-slot budget gives approximately $260.266667\,\mathrm{B/vector}$ rather than $132.266667\,\mathrm{B/vector}$. Incoming degree is not capped by the outgoing-slot limit; complete reverse maps need actual edge counts, upper layers and map overhead.
• For a repair scenario with $32$ affected in-neighbors and one $6{,}400$-evaluation proxy search per repair, work is $32\times6{,}400=204{,}800$ evaluations per deletion.
• At $2\times10^5$ deletions per day, that scenario costs $4.096\times10^{10}$ evaluations, exactly $64\%$ of the stipulated rebuild work. It is not a universal complexity law for supported deletion algorithms.
• Connectivity risk: diverse links can bridge regions. A local repair that misses the necessary replacement can disconnect useful routes or reduce ANN recall without an exception. This motivates verification of the chosen update algorithm; it does not prove that every in-place deletion must fail.

Tombstones and beam inflation

• A dense deleted-identifier bitmap suppresses marked identifiers while a tombstoned vector and its graph links may remain for navigation. Every serving path, replica and relevant cache must enforce the deletion state.
• At $10^7$ identifiers, the bitmap payload is $10^7/8=1.25\times10^6\,\mathrm B=1.25\,\mathrm{MB}$, approximately $0.003901\%$ of the $32.042667\,\mathrm{GB}$ scoped clean index. Bitmap size grows with retained identifiers unless slots are recycled.
• Candidate model: if a pre-exclusion candidate pool of width $\mathrm{ef}$ samples deleted nodes representatively with share $\phi_q$, its expected live count is $\mathrm{ef}(1-\phi_q)$. Search implementations that retain only live results can still traverse deleted nodes; their behavior is not described by simply subtracting dead slots from the final heap.
• Under that candidate-pool model, a planning width is $\lceil\mathrm{ef}_0/(1-\phi_q)\rceil$. Preserving an expectation does not guarantee recall, and $\mathrm{efSearch}$ is not a work cap.
• Churn model: hold the live population $N$ fixed, replace $Nc$ vectors per day, append replacements, retain deleted nodes, and do not recycle slots. Then after $t$ days,

• With representative deletion, the continuous width proxy is $\mathrm{ef}_0(1+ct)$. Stipulate clean work $Q_0=64\times32=2{,}048$ distance evaluations and the linear aging proxy $Q(t)=Q_0(1+ct)$. This is a work scenario, not a measured latency or recall law.

Rebuild economics and hard ceilings

• Model: rebuild work $B$ is constant, cleanup is instantaneous at cycle boundaries, $\lambda$ and $c$ are constant, and build/query evaluations have the same cost. Constant clean-query and daily-insertion costs do not change the minimizing period under these assumptions.
• Integrating the excess query work over a cycle gives

• For $B,\lambda,Q_0,c\gt 0$, $g''(T)=2B/T^3\gt 0$, so this is the unique continuous optimum. If $c=0$ or $\lambda=0$, this stale-query term supplies no finite economic optimum. Different per-evaluation costs require conversion to a common currency first.
• At $10\,\mathrm{QPS}$, $\lambda=864{,}000\,\mathrm{day^{-1}}$ and $T^*=\sqrt{3{,}616.898148\ldots}\,\mathrm{days}\approx60.140653\,\mathrm{days}$. At that optimum $cT^*\approx1.202813$ and $\phi\approx54.6035\%$.
• At $1{,}000\,\mathrm{QPS}$, $\lambda=86{,}400{,}000\,\mathrm{day^{-1}}$ and $T^*\approx6.014065\,\mathrm{days}$. A hundredfold traffic increase shortens this modeled optimum tenfold.
• Continuous work cap: $Q(T)/Q_0\le1.2$ gives $T\le10\,\mathrm{days}$ and $\phi\le1/6\approx16.6667\%$. The boundary work is $2{,}457.6$, not a certified integer operation count or latency percentile.
• Integer-width version: if the rule instead requires $\mathrm{ef}/64\le1.2$, then $\mathrm{ef}\le\lfloor76.8\rfloor=76$. With $\mathrm{ef}=\lceil64(1+cT)\rceil$, the cap becomes $T\le9.375\,\mathrm{days}$ and $\phi\le3/19\approx15.7895\%$. Rounding to $77$ would allow $20.3125\%$ width inflation.
• Deployment: an instantaneous-cleanup model can take the minimum of economic, measured-SLO and applicable completion ceilings. Real triggers must leave time for building, validation, propagation and replay of changes since the snapshot. The work cap is not itself a measured $p_{95}$ or $p_{99}$ ceiling.
• Legal scope: the source cites GDPR Article 17 and Article 12(3). One calendar month is a response-window provision, not a fixed $30$-day, exception-free physical-erasure clock. The example's $30$ days are a stipulated policy window; determine the applicable obligation separately.
• Illustrative binding choices: before other constraints and build lead time, low traffic is limited to $10$ days by the continuous work model, or $9.375$ days by the strict integer-width version. High traffic is limited to approximately $6.014065$ days by modeled cost. Tombstones alone do not erase vectors, text, replicas or backups.

Operational checks and exceptions

• Rebuild read proxy: $6.4\times10^{10}$ evaluations charged one $3{,}072\,\mathrm B$ vector read each imply $196.608\times10^{12}\,\mathrm B=196.608\,\mathrm{TB}$. At a sustained $50\,\mathrm{GB/s}$ this traffic takes $3{,}932.16\,\mathrm s\approx1.092267\,\mathrm h$, or approximately $0.7585\%$ of a six-day cycle. Cache reuse can reduce these DRAM reads; random accesses, graph work, writes and contention add costs. This is not a universal build floor or a measured rebuild duration.
• Feasibility: an hourly rebuild schedule cannot complete this particular read proxy serially within one hour. Parallel construction, another index/update design or lower build work may help, but changing $\mathrm{efConstruction}$ requires quality validation.
• Correlated deletion: global $\phi=5\%$ can coexist with a visited neighborhood at $90\%$ deletion. Measure deleted nodes encountered, traversal work, live-candidate yield and recall by query cohort; the final returned list should already contain no tombstones.
• Event triggers can supplement a calendar when churn is bursty. Use measured recall/latency and local deletion exposure, not an assumed global fraction alone.
• Tombstone-and-rebuild is one common HNSW pattern. Slot recycling and streaming-merge designs have different correctness, quality and capacity trade-offs. The source cites FreshDiskANN-style maintenance from Singh et al. (2021); the existence of a supported update path does not make arbitrary link inheritance safe.
• IVF-PQ deletion is implementation-dependent: finding an identifier may scan a posting list, while a maintained direct map and swap-delete can support constant-time entry removal. Batch compaction can cost more. Watch coarse-cell imbalance and codebook drift; a few-times-mean cell rule is a heuristic to validate.
• Blue-green capacity: the expected-slot budget is approximately $32.042667\,\mathrm{GB}$ for the live index and $64.085333\,\mathrm{GB}$ for two copies, before scratch space and payloads. Two copies do not fit in $64$ decimal GB. A separate builder, additional shards or rolling segments need explicit extra capacity.
• Cutover: replay inserts and deletions since the build snapshot, enforce tombstones on both generations, validate quality and authorization, then switch with a supported atomic mechanism. A pointer swap does not eliminate cache warmup or contention.
• Search dial: $\lceil\mathrm{ef}_0(1+ct)\rceil$ is a candidate-width heuristic under the stated churn model. Benchmark the actual search implementation and rebuild before the measured SLO or completion deadline is violated.
• Tight-deadline scenario: scaling the same read proxy from $10$ million to $500$ million vectors gives $54.613333\,\mathrm h$, not $50\,\mathrm h$ from rounding the smaller run to one hour. A stipulated $24$-hour physical-removal obligation needs a different supported workflow if this rebuild cannot meet it.
• Removing payload bytes and failing closed on lookup can prevent their return, but deleting a vector while leaving a graph node is not automatically navigation-safe: search may need that representation for distances. Reconnect, bypass, replace or rebuild using an algorithm that preserves the required invariant, and handle replicas, caches, logs and backups under the applicable policy.
• Source software examples: Lucene merge thresholds and hnswlib/FAISS deletion APIs are version- and configuration-specific. Numerical proximity between a reported $20\%$ merge default and the toy $16.6667\%$ tombstone cap does not validate the model or an SLO. Verify current behavior before deploying.

17.2 Sharding, replication, partitioning

Three distinct scaling axes

• Sharding distributes $N$ vectors over $S_{\mathrm{sh}}$ disjoint shards. Balanced data gives approximately $N/S_{\mathrm{sh}}$ vectors per shard; broad queries scatter to all of them.
• This addresses per-node memory and can parallelize work. If each shard's service capacity stays fixed and every query visits every shard, adding shards does not multiply user QPS. Smaller graphs, cache behavior and parallel execution can change the service point, so flat throughput is an assumption, not a scaling theorem.
• The characteristic-depth ratio at $N=10^8$ and $S_{\mathrm{sh}}=8$ is $\log_2(10^8/8)/\log_2(10^8)\approx0.887114$. That is approximately an $11.2886\%$ height reduction, not an $11.2886\%$ guarantee for query time.
• For independent, identically distributed branch latencies with CDF $F$, $\Pr(L_{\max}\le t)=F(t)^{S_{\mathrm{sh}}}$. If each branch exceeds a chosen threshold with probability $0.01$, the fan-out event probability is $1-0.99^{S_{\mathrm{sh}}}$, approximately $63.3968\%$ at $S_{\mathrm{sh}}=100$. Correlated branch delays change this result; a union bound remains available without independence.
• Replication creates $R_{\mathrm{rep}}$ serving copies per shard. Balanced routing to unchanged replicas can multiply capacity by $R_{\mathrm{rep}}$ and multiplies index storage by that factor. Synchronization, failure domains and service policy determine actual availability.
• Replication does not fix an oversized shard or make an individual search intrinsically faster. Hedging can reduce some tails while consuming extra capacity.
• Key partitioning routes a query to the matching corpus partition and can avoid $P_{\mathrm{part}}-1$ branches. Its benefit depends on correct keys, data balance and query balance. Missing keys may require broadcast; an incorrect routing key can exclude relevant authorized data.

Hashing, attributes, and hybrids

• A suitable hash gives expected identifier-count balance under its randomness assumptions. It is not skew-free: unequal item weights, hot keys, popular documents and uneven query distributions can still overload nodes.
• Hashing identifiers generally discards tenant locality. If each tenant spans all three shards, even a workload with $90\%$ tenant-keyed queries still needs fan-out $3$ unless another routing or filtering structure prunes shards.
• Attribute partitioning can reduce partitions touched, but can worsen data or traffic imbalance. Neither scheme universally minimizes load variance or query cost.
• In the source's staff scenario, one tenant owns $40\%$ of data and generates $60\%$ of queries. A hybrid can route small tenants directly and sub-shard the large tenant with separately provisioned serving copies.
• Budget the two routing paths, migrations, write synchronization and rebalancing when a small tenant becomes large. Measure weighted work and tail latency, not only vector counts.

Worked capacity example

• Corpus: $N=10^8$, $d=768$ fp32, HNSW $M=16$ and $128\,\mathrm{GB}$ usable RAM per node.
• Vector payload is $N(768)(4\,\mathrm B)=307.2\,\mathrm{GB}$. Base-layer slots add $12.8\,\mathrm{GB}$; expected upper-layer slots add approximately $0.426667\,\mathrm{GB}$.
• The scoped expected index budget is approximately $320.426667\,\mathrm{GB}$. Steady-state capacity alone gives $\lceil320.426667/128\rceil=3$ shards, before non-index overhead and skew.
• Balanced thirds contain $33{,}333{,}333$ or $33{,}333{,}334$ vectors, approximately $106.808889\,\mathrm{GB}$ per shard. If each node must hold old and new copies together, the corresponding capacity-only lower bound is $\lceil2(320.426667)/128\rceil=6$ shards. A separate temporary builder is an alternative with its own capacity bill.
• Service scenario: $16$ continuously occupied query slots at an $8\,\mathrm{ms}$ mean service time imply $16/0.008=2{,}000$ shard-QPS by the service-point model. This is not a measured tail-safe capacity guarantee.
• With $S_{\mathrm{sh}}=3$ and $R_{\mathrm{rep}}=1$, $6{,}000$ aggregate shard-QPS divided by fan-out $3$ gives $2{,}000$ user QPS if work is balanced. Independent identical branches need CDF probability at least $0.99^{1/3}\approx0.996655493$ at their allocated deadline for a $99\%$ maximum-branch success rate; allow network and merge time separately.
• With $S_{\mathrm{sh}}=3$ and $R_{\mathrm{rep}}=3$, nine machines can supply $6{,}000$ user QPS under the same assumptions, at approximately $961.28\,\mathrm{GB}$ of index copies. Fan-out remains $3$.
• Three balanced key partitions, one copy each and fan-out $1$, can supply $6{,}000$ keyed user QPS using approximately $320.426667\,\mathrm{GB}$. Routing skew, cross-partition requests and other overhead can reduce this.
• Let $f_k$ be the fraction routed to one partition and let all other requests touch all $P_{\mathrm{part}}$ partitions. Then $\mathbb E[F_{\mathrm{fanout}}]=f_k+(1-f_k)P_{\mathrm{part}}$. Under balanced per-node work, the aggregate capacity proxy is $P_{\mathrm{part}}q_{\mathrm{node}}/\mathbb E[F_{\mathrm{fanout}}]$.
• For $P_{\mathrm{part}}=3$ and $q_{\mathrm{node}}=2{,}000\,\mathrm{QPS}$, $f_k=0.9$ gives fan-out $1.2$ and $5{,}000$ user QPS; $f_k=0.5$ gives fan-out $2$ and $3{,}000$ QPS. Without balance, the bottleneck bound is $\lambda_u\le\min_j q_j/\Pr(\text{query touches node }j)$ for positive touch probabilities, rather than the aggregate ratio alone.

Operating rules

• Treat $\lceil\text{index bytes}/\text{usable node RAM}\rceil$ as a capacity-only lower bound, not a universal optimal shard count. Add payloads, scratch space, cache, skew, failure and rebuild headroom. Smaller shards can also help recovery, parallelism or hotspots.
• For eight independent identical branches, the CDF probability needed at the branch deadline is $0.99^{1/8}\approx0.998744497$, or approximately the $99.87445$th percentile. Merely adding component $p_{99}$ values or using a rounded-down branch percentile does not establish whole-query $p_{99}$.
• Consolidation, key routing or carefully budgeted hedged requests may help tail latency. Each changes capacity and must be tested under load.
• Choose replica count from the failure model, read/write quorum policy, zones, durability and recovery requirements. $R_{\mathrm{rep}}=2$ leaves one copy after one failure; $R_{\mathrm{rep}}=3$ can leave two while one is rebuilding. Neither number alone proves service availability or write safety.
• Shipping a common built segment simplifies replica agreement. Independently maintained replicas can also be correct with suitable ordered logs, consensus or reconciliation; deletion state must reach every serving path.
• Measure keyed share and per-partition traffic before partitioning. A $50\%$ keyed share is a workload heuristic, not a mathematical break-even point.
• Apply mandatory filters correctly within each shard and before an identifier is exposed. Merge candidates with compatible score semantics; differently calibrated compressed scores may require common rescoring.
• Sharding need not lose exact top-$k$: with a common metric and tie policy, consistent snapshot, all branches complete and each shard returning its exact local top-$k$, their union contains the exact global top-$k$. ANN misses, inappropriate local truncation, filters or timeouts can break that guarantee. A smaller graph alone does not prove higher ANN recall.

17.3 Choosing a vector database: no winner on all axes

Separate index choice from database choice

• Index choice selects an algorithm and representation for a measured recall, work, latency and memory point.
• Database choice adds durability, filters, updates, deletion, tenancy, network placement and operational ownership.
• Some public benchmarks isolate static index behavior; others include more of the system. Inspect the actual benchmark rather than assuming all measure only the index.
• Matching $M$ and $\mathrm{efSearch}$ is not enough to match recall or work. Build order, randomization, pruning rules, precision, normalization, filters, stopping rules, data distribution and load all matter.
• SIMD, layout and runtime can change performance substantially. A reported $2$–$3$-fold implementation difference is not a universal upper bound, and algorithm labels alone do not establish dominance.

Attribute the entire latency budget

• Target: $200\,\mathrm{ms}$ end-to-end retrieval $p_{99}$ before generation prefill. The following components are stipulated serial point estimates, not jointly measured percentiles.
• Take embedding $20\,\mathrm{ms}$, ANN $0.42\,\mathrm{ms}$ at $10^7$ vectors, and a top-$20$ cross-encoder using $110$ million parameters and $512$ processed tokens per passage.
• The forward-pass proxy is $2(1.1\times10^8)(512)(20)=2.2528\times10^{12}\,\mathrm{FLOP}$. At a stipulated sustained $20\times10^{12}\,\mathrm{FLOP/s}$ it gives $112.64\,\mathrm{ms}$. Attention effects, actual batching, hardware utilization and serving overhead require measurement.
• With vacuum light speed $c_0=299{,}792{,}458\,\mathrm{m/s}$ and refractive index $n=1.47$, propagation speed is approximately $2.039404\times10^8\,\mathrm{m/s}$. A $5{,}500\,\mathrm{km}$ one-way path gives a round-trip propagation time of approximately $53.9373\,\mathrm{ms}$; multiplying distance by $1.4$ gives approximately $75.5122\,\mathrm{ms}$. Actual route, equipment and queueing determine measured RTT.
• Use a separately stipulated $1\,\mathrm{ms}$ same-region hop or $75\,\mathrm{ms}$ cross-region hop. The unrounded serial proxies are $20+1+0.42+112.64=134.06\,\mathrm{ms}$ and $20+75+0.42+112.64=208.06\,\mathrm{ms}$. The second proxy exceeds the target, but neither sum establishes a measured $p_{99}$.
• ANN is approximately $0.3133\%$ of the same-region proxy. Doubling its speed saves $0.21\,\mathrm{ms}$, or $0.105\%$ of the $200\,\mathrm{ms}$ target. Moving from the $1$ to the $75\,\mathrm{ms}$ hop adds $74\,\mathrm{ms}$, or $37\%$ of that target; a $75\,\mathrm{ms}$ hop alone does not exceed $200\,\mathrm{ms}$.
• Tail-budget discipline: choose component bounds $b_i$ with $\Pr(L_i\gt b_i)\le\epsilon_i$ and $\sum_i\epsilon_i\le0.01$. Then $\Pr(\sum_iL_i\gt \sum_i b_i)\le0.01$ by a union bound, without an independence assumption. Include queueing, retries, network and merge work. Summing several component $p_{99}$ values does not supply this guarantee.

Trade-offs and Pareto comparisons

• Durability can add logging and synchronization; group commit and storage design change the latency trade-off.
• Horizontal scaling adds distributed routing and coordination. It does not inherently prevent exact global top-$k$; the local-exact merge conditions above are sufficient.
• GPU batching can trade throughput against waiting time. Low-latency behavior depends on the implementation and offered load.
• Managed services shift operational ownership, while placement, network and parameter visibility remain product-specific.
• Libraries, embedded stores, SQL extensions, search engines, distributed stores and fully managed services are useful architectural categories, not performance certificates.
• A Pareto-nondominated configuration is one for which no compared configuration is at least as good on every chosen objective and strictly better on one. Class labels and qualitative ratings do not by themselves establish a Pareto frontier.
• A static, unfiltered benchmark is insufficient evidence for dynamic filtered tenancy. Equally, an existing relational database is not automatically the wrong choice: measure memory headroom, transaction interference and the actual query planner.

Worked product example

• Workload: $20$ million chunks, $d=768$, $5{,}000$ tenants, $50\,\mathrm{QPS}$, a $200\,\mathrm{ms}$ retrieval $p_{99}$ target and $2\%$ daily replacement.
• In-process scenario: removing the network term gives a serial proxy of $133.06\,\mathrm{ms}$. Expected HNSW vector-plus-slot bytes at $M=16$ are approximately $3{,}204.266667\,\mathrm{B/vector}$, or $64.085333\,\mathrm{GB}$ total, before payloads and overhead.
• Equal-sized tenants would average $4{,}000$ chunks, a corpus share $s=0.0002=0.02\%$. This average does not describe a skewed tenant distribution or the pass probability among highly ranked candidates.
• Under an IID candidate-pass model, global top-$100$ gives $\mathbb E[S_{\mathrm{surv}}]=0.02$ and $\Pr(S_{\mathrm{surv}}\ge1)=1-(1-0.0002)^{100}\approx1.98033\%$. The modeled empty rate is approximately $98.01967\%$; semantic correlation can change it.
• A different-region service has a $208.06\,\mathrm{ms}$ serial proxy with the stipulated $75\,\mathrm{ms}$ hop. Index tuning cannot change physical distance, but the actual service must be benchmarked before declaring an SLO miss.
• A same-VPC SQL extension with a stipulated $0.5\,\mathrm{ms}$ hop gives $20+0.5+0.42+112.64=133.56\,\mathrm{ms}$ using the same ANN estimate. A B-tree-assisted selective path has its own search cost and need not retain the global ANN term. Co-resident payloads and operational familiarity do not remove index memory or OLTP interference.
• Truncating a suitable Matryoshka embedding to $d=384$ halves vector bytes, not graph bytes. The scoped expected budget becomes approximately $1{,}668.266667\,\mathrm{B/vector}$ and $33.365333\,\mathrm{GB}$. Only embeddings trained for this behavior should be treated as candidates for such truncation, and quality still needs evaluation.
• Daily insert proxy: $400{,}000(6{,}400)=2.56\times10^9$ evaluations. Daily clean-query proxy: $50(86{,}400)(2{,}048)=8.84736\times10^9$ evaluations.
• Their ratio is approximately $28.9352\%$. This compares stipulated distance-work units, not measured CPU utilization, write latency or the fraction of total operating cost. Deletes, pruning, persistence and rebuild work are additional.

Selection rules

• Keep an existing system when it meets measured workload and operational constraints, not merely because it is familiar.
• With $d=768$ fp32 and the expected $M=16$ slot budget, $64$ decimal GB holds at most $19{,}973{,}368$ vectors by this capacity arithmetic alone; same-node old-plus-new copies halve that to $9{,}986{,}684$. Actual safe limits are lower after payloads, random level variation, scratch space and headroom. The rough $20$-million-vector boundary does not mean $20$ million fits.
• Co-locate services when appropriate; data-residency obligations and failure-domain design may constrain placement.
• Check distance function, precision, dimension limits, filter semantics and update/delete behavior before comparing speed.
• Benchmark the actual corpus, tenant skew, filters, concurrency and background writes/rebuilds. A $10{,}000$-query exact-ground-truth comparison is a useful sample, not a universal recall or tail-latency certification. Use the authorized relevant universe and define ties and precision.
• Prefer managed operations when the team cannot safely own a stateful service; assess portability and migration paths separately. Choose a configuration against constraints before treating vendor rankings as answers.

17.4 Metadata: descriptive, structural, generated

Provenance determines failure

• Source vignette: a 2025 migration re-stamped $40\%$ of the corpus. A predicate on $\mathtt{ingested\_at}$ after the migration could admit a 2019 template as recently ingested. The source's eleven-month description belongs to that vignette, not to today's date. Ingestion date is not authorship or effective date.
• Descriptive fields come from a system of record: owner, path, MIME type, ACL and ingest timestamp. They are authoritative for their defined meaning when synchronization and validation are correct—not automatically complete, current or error-free.
• A correct ingest timestamp can be the wrong recency proxy. Marginal LLM-generation cost may be zero, but ingestion, storage, synchronization and auditing still cost work.
• Structural fields such as headings, pages, parent identifiers and reading order come from parsers or layout models. Both missing and wrong values occur; OCR without layout can leave a systematically undercovered slice.
• Generated fields such as type, entities, summary and context prefix come from a model. A wrong hard label can exclude relevant material and admit irrelevant material. Models can also abstain, fail or produce missing values; coverage is not automatically $100\%$.
• One call per chunk is the worked cost model, not a required implementation. Batching, shared document context and caching change costs; model, prompt and chunking changes require versioning and possible backfills.

Recall bounds require query-conditioned coverage

• For a query $q$, let $G_q$ be its relevant authorized gold set and $A_q$ the set admitted by the metadata predicate. Any result set drawn only from $A_q$ satisfies

• This is a set-recall bound. For multi-gold queries, $\mathop{\mathrm{Hit}}\nolimits @k$ can still equal $1$ when only one of several relevant chunks survives. Do not substitute query hit rate for the fraction of gold chunks admitted.
• Special equality model: assume one gold item per answerable query, a truly applicable single-value equality constraint, missing values rejected, and incorrect values unable to match that equality. Define $c_g=\Pr(\text{field present}\mid\text{query's gold item})$ and $a_g=\Pr(\text{field correct}\mid\text{present, query's gold item})$. Then $\Pr(\text{gold admitted})=c_ga_g$ and $\mathbb E[\mathop{\mathrm{Hit}}\nolimits @k]\le c_ga_g$.
• Global chunk coverage $c$ and accuracy $a$ need not equal $c_g$ and $a_g$. Relevance, class, tenant, format and query weighting can be correlated with errors. A corpus with $55\%$ field coverage can have all queried gold items inside that covered slice or all outside it.
• Two equality gates with query-conditioned admission probabilities $r_1$ and $r_2$ multiply only under independence on the relevant population. Generally their joint admission lies between $\max(0,r_1+r_2-1)$ and $\min(r_1,r_2)$. These are admission bounds, not a lower bound on retrieval recall.
• Range predicates, null-tolerant rules and multi-valued fields need their own gate analysis; a wrong value can sometimes still pass.
• A reranker cannot recover an item already excluded from its candidate universe. A soft label avoids that particular hard exclusion but can still push a relevant item out of the final top-$k$ or change ANN retrieval.
• A globally $92\%$-accurate classifier therefore does not impose exactly an $8\%$ loss on every filtered query. Measure query-conditioned confusion, coverage and end-to-end retrieval. Keep authorization tied to its trusted source regardless of its relevance effect.

Worked metadata example

• Corpus: $180{,}000$ documents and $2\times10^6$ chunks at $400$ tokens each give $8\times10^8$ tokens.
• Worked assumptions: $55\%$ of chunks, not merely documents, have correctly parsed headings; the other $45\%$ have null headings. Take $20$ heading values uniformly distributed among populated chunks. Gold-item coverage matches these proportions. Without these assumptions, the following counts and gates need not hold.
• A generated document-type audit of $300$ IID chunks with $276$ correct gives $\hat a=0.92$ and plug-in standard error $\sqrt{0.92(0.08)/300}\approx0.0156631$. The nominal Wald half-width is approximately $3.0700$ percentage points at $95\%$; the Wilson interval with $z=1.96$ is approximately $[88.3726\%,94.5654\%]$. Correlated chunks from the same documents require an appropriate clustered design.
• Strict heading equality admits $0.55/20=2.75\%$, or $55{,}000$ chunks. In the single-gold representative-coverage model its admission probability is $0.55$, an upper bound on hit rate rather than a measured recall.
• Admitting the chosen heading or a null admits $0.55/20+0.45=47.75\%$, or $955{,}000$ chunks. It removes the missing-heading exclusion in this idealized model, raising the admission probability to $1$, not guaranteeing retrieval recall $1$. The search space is $955{,}000/55{,}000\approx17.3636$ times larger.
• If correct heading coverage rises to $0.95$, the strict filter admits $0.95/20=4.75\%$, or $95{,}000$ chunks, with gold admission $0.95$ under the same assumptions.
• If a hard document-type gate has gold admission $0.92$ and is independent of the original $0.55$ heading gate, joint admission is $0.506$ and $49.4\%$ of gold items are excluded. Without that independence, the joint admission is bounded by $[0.47,0.55]$; a global classifier accuracy alone supplies neither result.
• Tagging $2\times10^6$ chunks at $500$ input and $30$ output tokens gives $10^9$ input and $6\times10^7$ output tokens. At $\$1$ and $\$5$ per million respectively, the bill is $\$1{,}000+\$300=\$1{,}300$.
• Embedding $8\times10^8$ source tokens at $\$0.02$ per million costs $\$16$; the stipulated tagging bill is $81.25$ times as large.
• The cited contextual-retrieval writeup reports $\$1.02$ per million document tokens, or $\$816$ at this scale. The numerical ratio is $1{,}300/816\approx1.59314$. Different prompts, rates, models, token denominators and caching prevent that ratio alone from proving why the bills differ.
• The same writeup reports a $49\%$ relative reduction in top-$20$ retrieval failure for its contextual embedding plus contextual BM25 setup. This is a scoped reported result, not a $49$-percentage-point recall gain or a guarantee for this corpus.

Operating rules

• Store ingestion, authorship and effective dates separately when the application needs them. Correct source semantics matter as much as population accuracy.
• Audit field coverage, class confusion, freshness and query-conditioned gold admission by tenant, format and query cohort before using a hard filter.
• Here a $300$-item IID audit has a nominal Wald half-width near $3.07$ points. Increasing to $1{,}000$ is not a compliance certificate. Even zero observed errors in $1{,}000$ IID trials leaves a one-sided $95\%$ binomial error-rate upper bound of $1-0.05^{1/1000}\approx0.2991\%$.
• Compare parser/layout improvements with model generation on the actual formats; do not assume either eliminates all errors.
• Source tenant and ACL fields from the permission system and verify synchronization. A hypothetical $8\%$ error over $2\times10^6$ chunks is $160{,}000$ mislabeled chunks; classifier accuracy is not an authorization design.
• Version generated metadata by model, prompt hash, schema and chunking policy. Make backfills and query behavior explicit while versions coexist.

17.5 Pre-filtering, post-filtering, and the over-filtering risk

Selectivity and placement

• Corpus selectivity is $s=|\{x\in C:P(x)=1\}|/N$. Its cardinality guides planners, but it need not equal the pass probability among the highest-scoring ANN candidates.
• Correctness first: enforce tenant, user and classification constraints on every path before exposing nonmatching identifiers or payloads. Internal graph navigation and safe result eligibility are different mechanisms.
• Recency and popularity are often preferences, but explicit date bounds and validity rules can be mandatory user constraints. Do not silently soften them or confuse them with access control.

Post-filtering arithmetic

• Post-filtering retrieves $K$ global candidates and removes predicate failures. Its success depends on the predicate's relationship to semantic rank, not only on corpus selectivity.
• IID model: if each of those candidates passes independently with known probability $s$, then $S_{\mathrm{surv}}\sim\mathop{\mathrm{Binomial}}\nolimits(K,s)$, $\mathbb E[S_{\mathrm{surv}}]=Ks$ and $\mathop{\mathrm{Var}}\nolimits(S_{\mathrm{surv}})=Ks(1-s)$. Actual ANN rankings need not satisfy either assumption.
• Exact model requirement for at least $k$ survivors with probability $0.99$ is

• This is a probability conditional on known model parameters, not a confidence interval for an unknown pass rate. Enough surviving candidates also does not by itself prove semantic recall.
• For small $s$, a Poisson approximation with mean $\mu=Ks$ gives $\Pr(\mathop{\mathrm{Poisson}}\nolimits(\mu)\ge10)=0.99$ at approximately $\mu=18.783117$. Thus $K\approx18.783117/s$ is a small-$s$ approximation, not a certified integer bound.
• The source's normal shortcut $\mu-2.33\sqrt{\mu}\ge10$ has boundary $\mu\approx20.566662$. It is a rough, uncorrected tail approximation at a small expected count, not the exact $99\%$ condition.
• Exact binomial evaluation gives minimum $K=18{,}779$ at $s=0.001$, and $K=1{,}874$ at $s=0.01$, for $k=10$ and target $0.99$. Each immediately smaller integer fails that model target.
• With a stipulated output-candidate budget $K_{\max}=512$, define $s_\star$ by $\Pr(\mathop{\mathrm{Binomial}}\nolimits(512,s_\star)\ge10)=0.99$. Then $s_\star\approx0.036336078$, or approximately $3.633608\%$. The old $4\%$ boundary was a normal-approximation heuristic, not a phase transition.
• Candidate count and search effort are distinct. HNSW APIs commonly require or arrange $\mathrm{efSearch}\ge K$, but the width is not a distance-evaluation bound. Larger candidate budgets can rescue the survivor probability at additional cost; they are not mathematically impossible below $4\%$.
• Alternative model: uniform sampling without replacement from a fixed corpus with exactly $sN$ matching items gives $S_{\mathrm{surv}}\sim\mathop{\mathrm{Hypergeometric}}\nolimits(N,sN,K)$ and variance $Ks(1-s)(N-K)/(N-1)$. This is not the binomial model or a guarantee about semantic ANN candidates.

Exact pre-filtering arithmetic

• Resolve the predicate using a suitable index or bitmap, then score all admitted vectors. Exhaustive scoring can recover the exact nearest neighbors within that admitted set under a specified metric, precision and tie policy; it does not guarantee semantic relevance or recover a wrongly excluded gold item.
• With fp32 payload, a one-pass read proxy is $4dsN$ bytes. A $5\,\mathrm{ms}$ allocation at sustained $20\,\mathrm{GB/s}$ moves $10^8\,\mathrm B$.
• For $d=768$, $4d=3{,}072\,\mathrm{B/vector}$, so the payload-only capacity bound is $\lfloor10^8/3{,}072\rfloor=32{,}552$ vectors for one query.
• With ten simultaneous queries receiving equal bandwidth shares, the corresponding bound is $\lfloor10^8/(10\cdot3{,}072)\rfloor=3{,}255$ vectors per query.
• At $N=10^7$, this means $s\le3.255\times10^{-4}$ for the stated payload-read bound. Rounding that upward to $3.3\times10^{-4}$ would admit counts that exceed it.
• These are necessary read-budget checks under the stated streaming/fair-share model, not sufficient latency guarantees. Predicate evaluation, scattered gathers, scoring, top-$k$ selection and contention also need time.

The filter-aware middle

• Under the stated payload and IID survivor models, $3.255\times10^{-4}\lt s\lt s_\star\approx0.036336078$ is a useful planning gap between two particular budget checks. It is not a universal optimality interval for filtered ANN.
• Naively refusing to traverse every nonmatching HNSW node restricts the search to an induced subgraph. That subgraph can be disconnected even when the original graph had useful routes.
• Filter-aware designs may use category-aware links, traversal through ineligible nodes, or multi-hop expansion to improve reachability while checking result eligibility separately.
• The source cites Filtered-DiskANN from Gollapudi et al. (2023), ACORN from Patel et al. (2024), and Qdrant payload-aware links as different construction/traversal patterns. Their precise algorithms and guarantees have conditions; do not infer navigability for every arbitrary predicate.
• Known-label edge construction shifts work to ingestion and maintenance. Multi-hop expansion adds query work and remains implementation- and predicate-dependent. Benchmark recall, candidate yield and tail latency for actual filter combinations.

Over-filtering and worked example

• Over-filtering applies a syntactically valid predicate to the wrong relevant universe: for example, $\mathrm{year}\ge2024$ may exclude a still-valid 2021 policy.
• Exact-neighbor recall evaluated only inside the admitted set cannot detect that semantic exclusion. Compare against labeled authorized relevant evidence, as well as exact search within the filtered set. Never drop ACL or tenant requirements to construct an evaluation baseline.
• Tenant scenario: $N=10^7$ and $5{,}000$ equal-sized tenants give $2{,}000$ chunks each. Assume the year clause passes $60\%$ within this tenant, leaving $1{,}200$ chunks and $s=0.00012$; a global year prevalence alone would not establish that conditional count.
• IID post-filter model with $K=100$: mean survivors are $0.012$ and $\Pr(S_{\mathrm{surv}}\ge1)=1-(1-0.00012)^{100}\approx1.1929\%$. The corresponding empty rate is approximately $98.8071\%$.
• For top-$10$ and probability at least $0.99$, exact binomial evaluation requires minimum $K=156{,}522$, or $1.56522\%$ of the corpus and approximately $305.707$ times the $512$-candidate budget. Under the different uniform-without-replacement model with exactly $1{,}200$ matches, the minimum is $155{,}884$. Neither count is a guarantee for ranked ANN output.
• Exact dot-product work for $1{,}200$ vectors is $921{,}600$ MACs, or $1{,}843{,}200$ nominal FLOPs, and $3{,}686{,}400\,\mathrm B=3.6864\,\mathrm{MB}$ of vector reads.
• At $10\,\mathrm{GFLOP/s}$ and an isolated $20\,\mathrm{GB/s}$ share, compute and payload reads each take $0.18432\,\mathrm{ms}$ in their separate proxies; adding them without overlap gives $0.36864\,\mathrm{ms}$ before omitted overhead. At a ten-way equal bandwidth share, the read term alone becomes $1.8432\,\mathrm{ms}$. Do not mix isolated and concurrent bandwidth assumptions.
• An HNSW scenario with $128$ expansion-equivalents and $32$ neighbor tests each has a $4{,}096$-distance work proxy. The parameter $\mathrm{efSearch}=128$ does not impose that upper bound. The exact scan's smaller stipulated work motivates a benchmark, not a universal latency comparison.
• At $s=0.01$, exact reads of $100{,}000$ vectors are $307.2\,\mathrm{MB}$ and take $15.36\,\mathrm{ms}$ at isolated $20\,\mathrm{GB/s}$. The IID post-filter requirement is $K=1{,}874$, approximately $3.66016$ times $512$.
• A configuration label of $10{,}000$ KB must have its version-specific unit checked. If it means $10{,}000\,\mathrm{KiB}=10{,}240{,}000\,\mathrm B$, it budgets $3{,}333$ vectors, approximately $2.3963\%$ above $3{,}255$. If it means $10{,}000\,\mathrm{kB}$, it budgets $3{,}255$. Numerical proximity to a planner default does not validate the latency model.
• For the cited $100$-million-vector IVF-PQ configuration, $64$ mean lists out of $262{,}144$ with $16$ code bytes per item give $390{,}625\,\mathrm B=390.625\,\mathrm{kB}$ of mean code traffic. The $307.2\,\mathrm{MB}$ full-vector read is $786.432$ times as large. These are differently scoped traffic estimates, not matched-quality latency or compression guarantees.
• A $400{,}000$-vector tenant has $1.2288\,\mathrm{GB}$ of fp32 payload and a $61.44\,\mathrm{ms}$ isolated read proxy at $20\,\mathrm{GB/s}$. This exceeds the $5\,\mathrm{ms}$ scan allocation, not necessarily the entire $200\,\mathrm{ms}$ retrieval target.
• Tenant-aware routing can retain authorization while using ANN inside the eligible subset. Five thousand tenants do not require five thousand physical graphs: shared filtered indexes, logical partitions and hybrid routing are alternatives with their own costs.
• The source's FunnelRAG comparison uses approximately $4{,}000$-token clusters, document-scale dense retrieval and approximately $100$-token passage ranking. Its reported roughly $40\%$ speed improvement is workload-specific; without a defined time-versus-rate metric it should not be restated as a $40\%$ latency reduction.