Two nearly identical queries produce completely different retrieval results. How would you assess retrieval instability?

Production incident (illustrative): A financial-policy RAG assistant answers “Can contractors claim meals on international trips?” with the current contractor travel policy, but answers “Are meal expenses reimbursable for contractors traveling abroad?” using a superseded employee FAQ. A second incident appears when the exact same query alternates between the current policy and a stale replica's result list. Both look like “unstable retrieval,” but the causes—and remedies—are different.

Core principle: First distinguish semantic paraphrase sensitivity (different wording, same intended facts) from identical-request run-to-run variability (unchanged query, different outcomes). Then separate *benign neighbor reorderings* from failures in authorized evidence recall, policy versions, citations, and answer correctness. Approximate nearest-neighbor (ANN) search need not return byte-identical rankings; retrieval quality and security invariants are what matter.

1. Contain and define the incident

• Keep mandatory tenant, ACL, document-version and effective-date constraints enforced, even if a looser search appears to stabilize answers. Temporarily use a trusted authorized exact/BM25 lookup for high-stakes policy questions when required evidence is missing; otherwise abstain.
• Record both raw questions and their normalized/rewritten forms, model/revision, embedding input role, full query vector hashes, active index alias, vector name, filters, top-k, ANN effort, query timestamp, request routing, shard/replica ID, index generation, fusion settings, reranker version, response candidates and citations.
• Verify the pair is actually meaning equivalent. “May employees claim meals?” versus “May contractors claim meals?” is not a paraphrase; legal negation, geography, dates, role and exceptions materially change the authorized answer.
• Define the answer-bearing eligible chunks, source version and relevancy labels *before* tuning. Two different chunks can both be correct evidence; low identifier overlap alone does not establish harmful instability.

2. Controlled experiment: two axes, not one

• Paraphrase axis: create meaning-equivalent pairs preserving actor, scope, negation, year, entity IDs and information need. Hold corpus snapshot, ACL, index configuration and read replica fixed; compute one stable embedding per variant and compare first-stage and end-to-end results.
• Repeatability axis: submit the identical query vector and exact same serialized search request 20–50 times to the same replica, then repeat across replicas and during controlled indexing. This isolates query-embedding variation from ANN, index mutations and routing effects.
• Production axis: run across different time windows, client versions, shards, load and cache states. Differences appearing only here can indicate refresh lag, replica divergence, background segment optimization, changing aliases, time-sensitive filters or concurrency-dependent timeouts.
• Change one factor at a time: compare raw-versus-rewritten question, old-versus-new embedding model, ANN-versus-exact, lexical-versus-dense, filter on/off only in authorized test fixtures, fusion on/off and reranker on/off.
• Preserve fixed query IDs, versions, eligible source sets and exact-search baselines. Without a frozen corpus and filter policy, natural ingestion or authorization changes may be mistaken for retrieval instability.

3. Metrics: stability is not identical to relevance

• Top-k Jaccard similarity: |A_k ∩ B_k| / |A_k ∪ B_k|. Measures set overlap, ignoring rank; useful for paraphrase pairs and repeat runs. Low Jaccard can still be harmless if both sets contain relevant evidence.
• Rank-sensitive overlap: use rank-biased overlap (RBO) or measured top-rank agreement to distinguish one swapped low-ranked neighbor from replacement of the most important citation. Treat score ties as a separate bucket.
• Relevant-document consistency: measure whether each semantically equivalent query hits at least one authorized correct chunk at k; also track pairwise *both-success*, one-success, neither-success. This directly captures whether paraphrasing loses necessary evidence.
• Quality: labelled Recall@k, nDCG@k, MRR, citation support, answer-equivalence and unsafe/superseded-source hit rate. Compare metrics across query phrasing variants, query types and tenants.
• ANN approximation gap: compare approximate top-k to exact/flat nearest neighbors over the same filtered corpus for each query vector. ANN Recall@k reveals search-index error; it does not prove the semantic encoder ranks the right document.
• Embedding sensitivity: compute cosine similarity between the paired query embeddings *only inside the same model space*, then inspect exact nearest-neighbor ranks. High query cosine similarity does not guarantee identical top-k near decision boundaries.
• Confidence and sample size: bootstrap at the intent-group level, not independently over correlated paraphrases; report uncertainty and query-class breakdown. Never treat arbitrary Jaccard thresholds as universal release gates.

4. Root-cause decision tree

• Same raw request, different query vector hash: inspect nondeterministic rewriting, chat-history contamination, embedding model/router changes, stochastic normalization, hidden metadata and stale cache keys.
• Same vector, different exact results on frozen snapshots: inspect corpus/ACL/replica mismatch, distance-metric config, score ties/tie-breaking, version changes, inconsistent filters, shard errors and client request differences.
• Same exact reference, ANN rankings change: inspect HNSW approximation, hnsw_ef/num_candidates, segment compaction, quantization/rescoring, indexed-only semantics, background updates and replica index generations. Qdrant explicitly warns ANN ranking can shift between requests and offset pagination can repeat/skip IDs.
• Identical request stable on each replica but varies across replicas: compare update propagation, read consistency, shard routing, optimizer readiness and effective document versions. Qdrant describes how default single-replica reads can “blink” while replicas converge and supports stronger read consistency and version-specific read affinity.
• Paraphrase results differ even for exact kNN: suspect query representation, domain vocabulary, negation handling, concept disambiguation, truncated query text or insufficient paraphrase robustness of the embedding model—not HNSW graph behavior.
• Dense is stable, hybrid or reranked outputs differ: audit BM25 analyzer/rewrites, dynamic fusion weights, candidate-depth limits, RRF, deduplication, random tie resolution, reranker input truncation and result caching.
• Differences only under production load: check timeouts, partial shard responses, connection pooling, retry routing, caches and index updates. Determine whether the system returns incomplete candidates as successful responses.
• Differences are only score-tied IDs near rank k: likely benign top-k boundary variance, unless they remove a crucial source; use stable secondary sorting for exact deterministic paths when supported, without claiming ANN can always guarantee stable ranking.

5. Numerical worked example: stability versus correctness

• Use 100 business intents, each represented by two expert-validated equivalent questions (200 searches), one known authorized policy-answer target per intent. Every variant is tested on the same index snapshot.
• At baseline, 62/100 pairs retrieve valid evidence for both phrasings, 28/100 pairs succeed for only one phrasing, and 10/100 pairs fail for both. Thus both-success rate = 62%; at-least-one-success rate = 90%; per-query success is (2×62 + 28) / 200 = 152/200 = 76%. The gap between 90% and 62% exposes paraphrase sensitivity invisible in single-query evaluation.
• For one pair, top-5 ID sets are A={P1,P2,P3,P4,P5} and B={P1,P6,P7,P8,P9}. Their intersection has 1 ID and union has 9, so Jaccard@5 = 1/9 ≈ 0.111. If P1 is a valid current policy paragraph and both cite P1, set instability does not imply an answer failure; if B cites an expired FAQ instead, it is harmful.
• A controlled repeated-query test holds the same query vector and backend filter fixed for 20 requests. The assigned replica returns an identical top-5 for 19/20 trials, but another replica with lagging policy updates returns different results in 15/20 trials. The exact numbers are illustrative; diagnose replica lag independently instead of claiming intrinsic ANN randomness.
• Using a verified updated replica and tuning the ANN candidate budget, repeat-run consistency improves, but paraphrase pairwise both-success remains below the target, indicating encoder/retriever sensitivity remains unresolved.
• A benchmarked semantic-representation improvement plus carefully controlled lexical/dense candidate fusion raises both-success to 84/100 pairs, one-success to 12/100, and neither-success to 4/100. Per-query correct-evidence success becomes (2×84 + 12)/200 = 180/200 = 90%. Pairwise both-success improves 22 percentage points (62% → 84%).
• Suppose search p95 rises from 140 ms to 220 ms due to added candidate depth and reranking. Accept only after testing capacity, semantic relevance, evidence citations, authorization, and latency SLOs. These counts are *illustrative*, not measured MachinoAI traffic.

6. Engineering solution by identified failure mode

• Deterministic replay harness: log immutable query-vector fingerprints, normalized query, request parameters, target collection generation, shard/replica mapping, source/filter snapshot and candidates. Run a fixed, rate-limited reference benchmark periodically.
• Read-path consistency: for genuinely stale replicas, repair replication/index readiness, route to sufficiently current peers, and select an appropriate supported consistency setting. Do not use stale-replica results for policy/ACL changes or delete-sensitive answers.
• ANN tuning: benchmark hnsw_ef or per-shard num_candidates, quantization and rescoring against exact retrieval, while monitoring Recall@k and p95/p99. Qdrant exposes exact=true; Elasticsearch documents per-shard num_candidates. Higher effort may improve overlap but costs CPU/time.
• Representation fixes: evaluate paraphrase-robust multilingual/domain embeddings; preserve original intent and all hard entities in rewrites. If encoder changes, re-embed documents into a matching versioned vector space and switch query encoder and index coherently.
• Candidate aggregation: consider BM25/dense fusion for domain-specific terms and a sufficiently wide, reproducible candidate pool. Use a deterministic, stable reranker where available. Do not average unrelated raw similarity scores.
• Evidence-aware outputs: canonicalize equivalent source versions and document aliases for quality metrics; require current, authorized evidence and consistent citations rather than identical neighbor IDs.
• Operational rollout: shadow evaluate changes on an intent-grouped golden set, canary across replicas and query types, gate on pairwise both-success, Recall@k, unsafe citations, latency and error rate, then promote with a tested rollback bundle.

7. Trade-offs and common mistakes

• Forcing exact search: improves reproducibility and diagnostic confidence but may be too slow/costly for millions of vectors. Apply to bounded diagnostic subsets or targeted, security-critical requests.
• Increasing ANN effort: improves approximation accuracy in many settings but cannot repair a poor semantic embedding or lossy query rewrite.
• Stronger consistency: reduces stale-replica disagreement but adds replica work, latency or availability trade-offs; document the business need.
• Query rewriting/paraphrase expansion: sometimes improves coverage but risks changing dates, negation, roles or source scope and increases computation. Do not rewrite away mandatory filters.
• RRF and rerankers: may stabilize relevant evidence but can obscure whether the dense encoder, lexical branch, or fusion caused the original change. Keep branch-level traces.
• Cache pinning/read affinity: can reduce visible blinking but may hide stale data rather than solve replication lag. Verify freshness and delete/ACL propagation first.
• Comparing only top-k overlap: penalizes equivalent valid chunks and may reward a consistently wrong retrieval. Pair overlap with labelled relevance and version-aware citation correctness.
• Ignoring near-ties: tiny score differences can reorder boundary results harmlessly; do not overreact to a changed 10th neighbor if supported answers and ACLs are stable.

8. Prevent recurrence

• Build a meaning-equivalent paraphrase evaluation suite covering domain synonyms, active versus expired policies, negative constraints, invoice IDs, multilingual variants, short/long queries and time-effective source versions. Validate equivalence with knowledgeable reviewers.
• Monitor both-success per intent, one-sided paraphrase failures, Jaccard@k/RBO, ANN exact-reference recall, relevant-citation consistency and unauthorized/superseded-result rates; segment by model version, corpus generation, tenant, query class and replica.
• Add same-vector repeatability smoke tests across replicas, before and after index optimization, node upgrades, high ingest rates and consistency-mode changes.
• Alert on sudden disparity between paraphrase variants, stale replica/document citations, growing non-deterministic rewrite rates, unexpected partial shard responses or model/alias drift.
• Make each retrieval release auditable: pin versions, corpus/filter snapshot, embedding contract, index settings, fusion/reranker configuration and success thresholds. Rehearse regression rollback without resurrecting deleted records.
• Require causal diagnosis before adopting multi-query consensus or deeper search; recent paraphrase-stability research finds that diversity/consensus can improve coverage, but simple per-query adaptive weighting may show little benefit.

Interview takeaway: For two similar questions producing different evidence, test repeatability and paraphrase robustness separately. Freeze the query vector and corpus to identify backend/index/replica instability; compare validated meaning-equivalent queries to isolate semantic sensitivity. Judge fixes using *authorized relevant evidence and citation consistency*, not top-k identity alone.

Research references

• Qdrant, Search API, exact search, ANN ranking stability: https://qdrant.tech/documentation/search/search/
• Qdrant, Read consistency and replica affinity: https://qdrant.tech/documentation/scaling/consistency-guarantees/
• Elasticsearch, kNN num_candidates and per-shard merging: https://www.elastic.co/docs/reference/query-languages/query-dsl/query-dsl-knn-query
• Mandiga et al., *Paraphrase-Induced Retrieval Instability: Systematic Measurement and the Limits of Inference-Time Mitigation* (2026): https://aclanthology.org/2026.uncertainlp-main.34/