The Short Answer
Almost every vector search engine is approximate. It walks a fraction of the index rather than comparing your query against every stored vector, and the fraction it walks can differ from one run to the next, so the tail of your result list moves while the top few stay put. That is the usual cause.
Four other things produce the same symptom: an index still absorbing writes, several replicas that each built their own graph, scores that tie at the fourth decimal place, and a query vector that quietly stopped being the same vector. They leave different fingerprints, so you can tell them apart in about ten minutes, and the fixes have nothing in common.
Start by measuring how much the results move. A result set that reshuffles positions 40 through 50 is normal behaviour for approximate search. A result set where the top three change is something else.
First, measure the variation
Run the same query twenty times and record three numbers. Guessing from two runs and a screenshot is how people end up tuning the wrong parameter.
Do this against a frozen copy of the data if you can. Measuring during an active ingest mixes two causes and you will chase the wrong one.
Cause 1: approximate search skips most of your index by design
This is where the majority of run-to-run variation comes from, and it is a deliberate trade. Comparing a query against ten million vectors is expensive, so approximate nearest neighbour algorithms visit a small, guided subset.
In a graph index like HNSW the search enters at one node and greedily walks toward your query, keeping a beam of candidates whose width is
ef_search. Two things
there are not fixed: the entry point can vary, and the graph itself was built with
randomised level assignment, so its shape depends on the order the vectors were
inserted. In an IVF index the vectors are grouped into cells and nprobe decides
how many cells get scanned. A vector sitting near a cell boundary is found or missed
depending on which cells the query lands closest to.Both indexes are honest about this: recall at 10 of 0.95 means one slot in twenty is a vector the search did not reach. Run it again with a slightly different beam and a different slot goes missing.
The fingerprint. Variation lives in the tail, the top few results are stable, and raising
ef_search or nprobe visibly shrinks the spread while raising latency.
If turning those dials does nothing, your cause is somewhere below.Cause 2: the index is still changing underneath the query
Search engines do not rebuild an index on every write. They append to small segments, then merge segments in the background, and a delete usually writes a tombstone that survives until the next compaction. During all of that, the structure your query traverses differs from one minute to the next.
Newly ingested content has its own visibility delay. The pipeline has to extract, embed, and then insert into the index before a vector can be returned at all, which is covered in index freshness and incremental updates. Run a query during that window and the answer legitimately changes as the work lands.
The fingerprint. The variation tracks ingest activity. Pause writes, wait for compaction to settle, and rerun: if the spread collapses, this was it. Result counts that drift upward across runs point the same way.
Cause 3: your replicas are not the same index
Three replicas behind a load balancer look like one search engine and are three separately constructed graphs. HNSW construction is order dependent and randomised, so two replicas fed identical vectors in a different order produce different graphs with the same recall and different blind spots. Each misses about 5% of the true neighbours, and they do not miss the same 5%.
Your client is then routed to whichever replica is least busy, which makes replica choice a hidden input to your query.
The fingerprint. Address one replica directly, or enable session affinity, and rerun the twenty-query harness. Variance that vanishes under pinning and returns without it is replica divergence. This one is usually acceptable in production, and the right response is to know it is happening.
Cause 4: near-ties, unstable sorts, and float drift
Similarity scores crowd together. In a catalogue of one thousand near-identical parts, ranks 5 through 25 can sit inside a window of 0.002, and any tiny numerical difference reorders them.
Several things supply that difference. Sorting on score alone leaves tied entries in whatever order the heap produced, which is not a defined order. Floating point addition is not associative, so a dot product accumulated in a different order gives a slightly different last bit. On a GPU the reduction order depends on batch shape, so the same vector pair can score differently in a batch of 8 and a batch of 64.
The fingerprint. The ids move, the score distribution does not, and the same items keep swapping places with each other rather than leaving the list. The fix is small: sort on the tuple of score and a stable document id, so equal scores always resolve the same way.
Cause 5: the query stopped being the same query
Before blaming the index, confirm the vector going into it is identical. This cause is the easiest to rule out and the one people check last.
Things that change a query vector without anyone editing the query text: an embedding model version rolled forward, a tokenizer update, a change in text normalisation, image preprocessing that resizes with a different filter or re-encodes a JPEG, truncation at a different token limit. Things downstream that change the ordering after retrieval: a cross-encoder or listwise reranker, an LLM stage with temperature above zero, query expansion that generates its own terms.
The fingerprint. Hash the query vector on each run and compare. If the hashes differ, the index is innocent and nothing you tune there will help. If the hashes match but a reranking stage sits behind retrieval, pull the pre-rerank candidate list and test its stability separately.
Telling them apart in one pass
| What you observe | Likely cause | Cheapest check |
| Tail moves, top 3 stable | Approximate search | Raise ef_search or nprobe, remeasure overlap |
| Variation follows ingest | Index still merging | Pause writes, wait for compaction, rerun |
| Stable when pinned to one node | Replica divergence | Address one replica directly |
| Same items swap places, scores identical | Unstable sort on ties | Add a document-id tiebreak |
| Query vector hash differs per run | Model or preprocessing drift | Hash the vector before it reaches the index |
| Only changes after a deploy | Model version or config rolled | Diff the deployed model and index settings |
Which of these is a bug and which is the deal you signed
Approximate search is the deal. You bought sublinear latency by giving up the guarantee that you see every vector, and the correct response is to pick a recall target, measure against exact search, and budget for the rest.
Replica divergence is usually the deal too. If it matters for a specific workflow, pin that workflow rather than rebuilding your topology.
Unstable sorts are a bug and a cheap one. Query drift is a bug and an expensive one, because it silently changes what every historical relevance measurement means. Index churn is expected during ingest and worth investigating if it never settles.
What to change, cheapest first
1. Add a deterministic tiebreak. Sort by score, then by a stable id. Minutes of work, removes a whole class of symptom. 2. Pin the embedding model version and the preprocessing path. Treat a model upgrade as a reindex and schedule it like one. Switching embedding models without re-embedding everything covers the migration, and embedding space geometry covers why the old and new vectors cannot share a space. 3. Over-fetch, then truncate. Ask for 50 and return 10. The boundary churn moves to rank 50 where nobody looks. 4. Raise the search effort until recall meets the target. Measure recall at your k against a brute-force baseline on a sample, then set
ef_search or nprobe
to the smallest value that reaches it. Methodology is in
evaluating multimodal retrieval.
5. Keep an exact-search baseline. A few thousand vectors scanned brute force give
you ground truth to compare against whenever the question comes up again.
6. Quarantine reads during large rebuilds, or serve from the previous index
version until the new one is fully built and warmed.If you are working through a broader relevance problem rather than a stability one, debugging bad retrieval results covers the ranking side, and filtered vector search covers what happens when a filter shrinks the candidate pool before the search runs.
Doing this on Mixpeek
A retriever is a declared pipeline, so the stages a query passes through are recorded rather than assembled at call time. The execution trace for a query shows which stages ran and what each returned, which turns "the results changed" into a question you can answer by comparing two traces.
Extractor and model versions are pinned per collection, so a model does not roll forward underneath an index that was built with the previous one. Re-extraction is an explicit operation with a cost attached rather than a silent background change.
Compare the embedding and reranking models available on models, read how vectors are stored and served on MVS, and see per-query and per-extraction costs on pricing. For the storage engine trade-offs behind all of this, best vector databases compares the options, and hybrid search fusion covers what happens to stability when you combine two rankings.
Frequently Asked Questions
Is it normal for a vector database to return different results for the same query?
Yes, within limits. Approximate indexes trade exactness for speed, so a small amount of movement in the lower ranks is expected behaviour. Overlap at 10 above 0.9 across repeated runs on a settled index is normal. Below that, or any movement in the top three, points at one of the other four causes.
Does setting a random seed make approximate search deterministic?
It helps and it does not finish the job. A seed can fix the entry point and the randomised level assignment at build time, which makes a single-node, read-only index reproducible. It does nothing about concurrent writes, segment merges, replicas that built their own graphs, or float accumulation order on a GPU.
Will exact search remove the problem entirely?
Exact search removes cause 1 and leaves the other four. Brute force still has to sort tied scores, still reads an index that may be changing, and still depends on the query vector being identical. It is a useful ground-truth baseline on a sample, and it gets expensive fast as a production path.
How much result variation is acceptable in production?
Set it from the workflow rather than from a general rule. A discovery feed can tolerate a reshuffled tail and often benefits from one. A compliance review that has to reproduce what a reviewer saw six months ago cannot tolerate any, and needs the result set stored rather than recomputed. Write the target down as overlap at k and top-1 stability, then measure against it.
Does this affect video and image search differently from text?
The mechanism is identical and the near-tie problem is worse. Adjacent video frames produce almost identical embeddings, so a single scene can fill many positions in the result list with scores separated by thousandths, and any of the causes above will reorder them. Deduplicating by scene or shot before ranking removes most of the visible instability.
My results only change after a deploy, never between runs. What does that point at?
Cause 5, almost always. A deploy is when model versions, preprocessing libraries, index parameters and client defaults all move at once. Diff the embedding model identifier and the index configuration between the two releases before looking anywhere else.