Repository navigation
Make graph-index tests independent of graph connectivity #216
Description
Problem
HNSW-RaBitQ and SymphonyQG do not guarantee that every point is reachable. A
multi-threaded or unseeded build occasionally leaves a point with no incoming edge
(in-degree 0), and then no search can return it. Tests that expect every point to be found
therefore fail now and then in CI, although nothing is broken.
Seen so far:
HnswConstructionTest.ParallelConstructionProducesSearchableIndex
(tests/unit/rabitqlib/index/hnsw_test.cpp, 8 construction threads) failed in CI run
41220054028:
the nearest result for point 2 was point 24. Since 671c6f1 it checks aggregate self-recall
(at least 99%) instead of every point.- The
qgcase oftest_indexes_accept_unaligned_build_and_query_arrays
(tests/python/test_array_alignment.py) builds an unseededSymqgIndex(65, 32)and
searches withk=len(data), so all 65 points must be reachable. About 0.15% of random
seeds give a graph that cannot reach every point; the rate is the same on 0.7.2.
Tests with the same pattern (an exact match for every point after a multi-threaded or
unseeded build) that have not failed in CI yet:
tests/python/test_thread_counts.py::test_build_and_search_thread_countsforhnswandqg
withbuild_threads0 or the maximum: a parallel build (theqgcase also unseeded), then
expected_ids[:, 0] == np.arange(len(data)).HnswAddTest.ParallelAddKeepsLabelsAndTheGraphinhnsw_test.cpp(8 threads for
construction andadd, thenresults[i][0].second == ifor every point).
Task
Audit the graph-index tests in tests/unit/rabitqlib/index/ and tests/python/ and make each
one deterministic while keeping what it checks:
- If the test checks exact results, bytes or every point (as the alignment test does), build
with a fixed seed and one thread, which makes HNSW and SymphonyQG construction
reproducible. - If the test is about parallel construction or thread counts, keep the threads and check an
aggregate instead (self-recall above a threshold, as 671c6f1 does), or compare searches on
the same graph only.
For the alignment test: with SymqgIndex(65, max_degree=32, ef_construction=32, seed=s) and
add(data, num_threads=1), aligned and unaligned inputs saved identical bytes and identical
k=5 results for 20 seeds × 3 offsets. Compare those, as the IVF and HNSW cases already do,
and drop the k=len(data) search.
Note for the test migration (#214): the 0.7 build defaulted to one thread, but add
defaults to all CPUs, so a migrated test that omits num_threads=1 becomes parallel and can
start failing this way.
Done when
- No graph test asserts that every point is found after a multi-threaded or unseeded build.
- Each changed test passes in a loop (for example 1,000 runs, or with
ctest --repeat until-fail:1000for C++) on a machine with several cores. - The changed tests still fail when the behavior they check breaks (for example a corrupted
unaligned copy, or a search that returns wrong IDs).
Setup and checks: contribution guide
(Python changes,
C++ changes).
Activity
gouyt13 commentedon Nov 12, 2026
More measurements on the
qgcase oftest_indexes_accept_unaligned_build_and_query_arrays, on main at 2f5fedf (extension built from 0354810; no binding changes since), Linux, 96 CPUs, Python 3.13.The test fails on main at about the rate given above. Running
test_concurrent_indexes.py,test_thread_counts.pyandtest_array_alignment.pytogether, 2 of 400 pytest runs failed, oneqgcase each (1,200qgcases in total). A version migrated to the 0.8 API for #214 failed in 7 of 1,100 runs. Every failure had the reported symptom: one ID missing from thek=65result, padded with0xFFFFFFFF.Outside the test, I could not reproduce an unreachable graph with the same data, parameters and calls (
SymqgIndex(65, max_degree=32, ef_construction=32),add(data, num_threads=1),search(queries, k=65, ef=65)):buildand 0.8add, 20,000 each)seed=7, one build per fresh process, aligned input and unaligned input at offsets 1–3A seeded single-thread build is therefore deterministic across processes and input alignment, and for this data far fewer than 0.15% of seeds give an unreachable graph. The test failures do not look like a property of the seed alone. I have not found what else in the pytest run triggers them.
Next step: when the
qgassertion fails, recordindex.seedand rebuild that seed in a fresh process. If that graph reaches every point, the cause lies outside graph construction, for example in the search.Dropping the
k=len(data)search, as proposed above, removes the failing assertion. Given these results, it is not clear that a fixed seed alone would prevent the failure.gouyt13 commentedon Nov 12, 2026
Seen in CI on #227:
test_indexes_accept_unaligned_build_and_query_arrays[2-qg]failed in the cp311 manylinux x86-64 wheel tests (job), with the same symptom: one ID missing from thek=65result, padded with0xFFFFFFFF. The rest of the suite passed (1 failed, 1109 passed, 2 skipped). #227 changes this case only to the 0.8 API: the constructor withef_construction=32, thenadd(num_threads=1). The failing assertion is unchanged.This case was the 12th test in the pytest process. Before it, only the six k-means tests in the same file and five IVF/HNSW alignment cases ran, and no threaded index tests. A preceding threaded test is therefore not needed to trigger it.
test(python): stop requiring every graph point in two tests
gouyt13 commentedon Nov 12, 2026
#227 fixes two of the Python cases listed above. Both had failed in its CI before the fix: the
qgalignment case, andtest_build_and_search_thread_counts[18446744073709551615-l2-hnsw], where one point missed itself.test_array_alignment.py: as proposed above, theqgcase builds withseed=42and one thread, and aligned and unaligned inputs must save identical bytes and return identicalk=5results. Thek=len(data)search is removed, and the exact-distance check runs on thek=5results.test_thread_counts.py: IVF still requires every point to find itself. HNSW and SymphonyQG require a self-recall@1 of at least 95%, so up to 4 of the 96 points may miss. Searches on the same graph must still agree across thread counts. Locally, 6,000 graph builds on 96 CPUs and 8,000 parallel builds restricted to 4 CPUs had no misses, so the only miss observed is the one from CI.The two changed test files passed 1,000 repeated local runs (96 CPUs), with no failures. They still check what they are for: a corrupted unaligned copy changes the saved bytes, and wrong IDs from a multi-threaded search differ from the single-thread results. This follows from what the tests compare; I did not mutation-test them.
Still open here:
HnswAddTest.ParallelAddKeepsLabelsAndTheGraphinhnsw_test.cpp, and the audit of the other graph tests intests/unit/rabitqlib/index/andtests/python/.gouyt13 commentedon Nov 12, 2026
Fixed by #228, which finishes the audit of the graph tests in
tests/unit/rabitqlib/index/andtests/python/. #227 had already fixed theqgalignment case andtest_thread_counts.py. No graph test now requires every point after a multi-threaded or unseeded build.test_large_dimensions.py;test_symqg.py, the shared fixture and the rebuild case;test_portable_indexes.py;test_hnsw.pycases whoseaddused the Python default of every CPU.HnswAddTest.ParallelAddKeepsLabelsAndTheGraph, listed above, keeps its exact check, as does the Python parallel-build test.The changed tests passed 1,000-run loops on 96 CPUs and restricted to 4 CPUs, with no failures. They also passed the full CI matrix, including arm64, macOS and Windows.
Still unexplained: the failure of the old
qgalignment assertion described above. It failed about 0.2% of the time inside pytest, and never in separate processes. That assertion is gone, so it no longer affects CI. If a graph search turns out to miss reachable points, it will need its own issue.