tazarov
commented
4 weeks ago @naddeoa,
you are right in your observation about the determinism of HNSW, which Chroma relies on for vector storage and search. The HNSW uses RNG for constructing initial connections. It is normally controlled via the random_seed index parameter. However, experimentation shows that index construction still has a level of randomness (it can be mitigated though).
Yet you may be wondering why would an index that has been initialized return different results for the same query and the answer lies in how Chroma creates and persist HNSW indices. Short overview here. The gist is this - if your dataset is >=100 and <1000 (100 and 1000 are defaults in Chroma that can be changed, hnsw:batch_size and hnsw:sync_threshold), then the HNSW index gets reinitialized every time you either recreate the DB from scratch or you restart the DB.
Here's some code to reproduce your observation in a more concise maner:
import numpy as np
import hnswlib
# init dataset of 1000 items
labels = [i for i in range(1000)]
vectors = np.random.uniform(-1, 1, (1000, 384))
# utility functions
def create_index(space='cosine', dim=384, search_ef=10):
index = hnswlib.Index(space=space, dim=dim)
index.init_index(
random_seed=42,
max_elements=1000,
ef_construction=100,
M=16,
)
index.set_ef(search_ef)
return index
def insert(index, labels, vectors):
index.add_items(vectors, labels)
def query(index, vector, k=10):
return index.knn_query(vector, k=k)
results = []
# create 100 indices of 1000 elements each with EF search = 10 (default in Chroma)
for i in range(100):
index = create_index(search_ef=10)
insert(index, labels, vectors)
search_labels = query(index, vectors[0])[0].tolist()[0] #query by the first vector from the data set and only get the labels of the vectors in the index as those are easier to work with than actual vectors
results.append(search_labels)
# Check the query results for all 100 indices and report discrepancies
last_result=None
for r in results:
if last_result is None:
last_result = r
else:
if last_result != r:
print('Different results', last_result, r)The above code simulates 100 runs, and then queries with the same vector, then compares and reports on discrepancies in the results. As you'll observe, if you run it there will be discrepancies reported most of the time, but sometimes there won't be any.
To mitigate this RNG behavior, HNSW offers search_ef or simply ef, which controls how many nearest neighbors to explore during the KNN search. The parameter defaults to 10, but can be changed via collection metadata at creation and post-collection creation time. Bumping this number will give you the consistency in results you want. It is difficult to say how to determine its value, but experimentation shows that higher values usually yield consistent results more frequently.
For instance, take the above code and change the search_ef to 1000 (aka the elements in the index), and you'll get consistent results most of the time (I'd like to say 100% of the time, but I haven't run that many experiments to be all that confident):
results = []
for i in range(100):
index = create_index(search_ef=1000)
insert(index, labels, vectors)
search_labels = query(index, vectors[0])[0].tolist()[0]
results.append(search_labels)
last_result=None
for r in results:
if last_result is None:
last_result = r
else:
if last_result != r:
print('Different results', last_result, r)
naddeoa
atroyn
What happened?
Minimal repro here: https://github.com/naddeoa/chromadb_determinism_issue. Check that out and run
make install run(with poetry installed)The same query will yield different results between database loads. As long as the database is loaded the query results are consistent, but if you unload the database (just let the script end and restart it) then you'll randomly get different results. For example, the following are two sample runs using the repro code that differ. Nothing changed in the database (besides the apparent mutations that chromadb always does even though I'm only reading, which makes things very hard to reason about).
My chroma instance was created with roughly the following code, using the same chromadb version (0.5.5)
I'm precomputing embeddings using my own encoder (
sentence-transformers/all-MiniLM-L6-v2for this repro still though) so I'm not using any documents and I'm querying by embedding values. There isn't really any mention ofdeterminismin the chromadb docs so I'm not sure what I should be expecting.Versions
Chromadb 0.5.5, python 3.10.12
Full dependencies exported from poetry lock file: https://github.com/naddeoa/chromadb_determinism_issue/blob/master/requirements.txt
Relevant log output
No response