Cheaper Index Construction: Two Bits per Dimension
The index-construction task of the SISAP 2026 Indexing Challenge scores the time to build the index as well as the time to search it. We made a single distance computation eight times smaller, which halves the build — and then spent four tenths of a second buying back the accuracy that costs. Third place out of fourteen teams.
The SISAP Indexing Challenge is an open competition for similarity search: the organizers set the datasets, every submission is run under the same conditions, and time is only counted above a fixed accuracy. Our overview of this year’s challenge Time to Celebrate! First Place in Vector Search at the SISAP 2026 Indexing Challenge covers all three tasks and how the field came out. This one is about the task where building the index counts too.
What we entered with is the Dynamic Exploration Graph, the index behind our own search. We have written about it here before, in Dynamic Exploration Graph: Fast Search in Evolving Catalogs — the post to read first if the terms below are new, since it explains what a proximity graph is and why ours is built to absorb insertions and deletions while it is being searched. The open source implementation is deglib, and that is what both submissions are built on.
One thing all tasks have in common: approximate nearest neighbor search trades a small amount of accuracy for a large gain in speed, so every task sets a minimum for that accuracy and measures time second. The measure is recall: the share of the true nearest neighbors a search actually finds. At a recall of 0.80, eight of ten items are true nearest neighbors, and no submission can buy speed by returning worse ones.
What the task asks
Task 1 turns the usual arrangement inside out. It embeds 6.4 million Wikipedia passages with BGE-M3 into 1024 normalized dimensions and asks for the 15 nearest neighbors of every single one of them. There is no separate query set, because the collection queries itself, and the time to build the index counts toward the score, which makes construction most of the work.
Two bits per dimension
Our lever was to make distance computations cheap while the graph is being built. Instead of comparing full-precision vectors, we compare them in a two-bit form: of every vector, keep the dimensions with the largest magnitudes, and of those keep nothing but the sign.
That idea is not ours. Equi-Voronoi Polytopes (EVP) were introduced at SISAP 2025 by Connor, Dearle and Claydon and used in that year’s challenge by another team. A submission does not have to take first place for its ideas to be worth having, and this one looked exactly like the lever a task dominated by build time responds to. Whether it would survive contact with our graph was genuinely open until we measured it.
What the codes give up
The name says what the price is. Every vector is replaced by the nearest vertex of a polytope whose cells all cover the same amount of the sphere the vectors live on; so the space is divided into cells, and what is compared afterwards are the cells, not the vectors. The query is quantized the same way, and two vectors that share a cell become the same code, however far apart they were.
There is a second reason the codes cannot be the last word, and it is arithmetic rather than geometry. Comparing two codes means counting: how many of the kept dimensions agree in sign, minus how many conflict. The result is a whole number, so for a 1024-dimensional vector the comparison has only a few hundred possible outcomes, and vectors at genuinely different distances routinely land on the same one. Connor, Dearle and Claydon argue that this is close enough to gather the right candidates; it is plainly not enough to order them. The measurements said the same. On its own the two-bit form builds the index in less than half the time, but then misses too many true neighbors; recall drops to 68 percent, well below the 80 percent the task requires. What made it work was to treat its answers as candidates rather than results: search on the EVP form, then recompute the shortlist with the precise vectors — 16-bit floats, the form the index keeps anyway — and reorder it. The coarse form decides who gets a precise look; the precise form decides the order.
Search coarse, rerank precise
What that costs is a shortlist of fifty candidates per vector and one pass of precise arithmetic over them; what it buys is the recall that quantization gave away. On a 200,000-vector subset, where a full-precision run still clears the recall bar and can serve as a reference, both sides of that trade are easy to read off: the build halves, and the reranking pass costs four tenths of a second.
The result, and the entry that beat it
That was enough for third place, and not for more.
The winning entry, PiPNN, is built for exactly this shape of problem, and its trick is that it never searches the graph to find candidates. It repeatedly assigns vectors to groups around randomly chosen leaders, small enough that dense matrix arithmetic can produce all the distances inside a group in one go, and large enough to overlap, so that vectors in more than one group tie the local results together. The candidate edges that come out are then thinned down to a fixed number per vector.
What makes that fast is not a cleverer rule for choosing edges, but what the rule is offered. Feeding it from blocks of dense arithmetic instead of from a graph search is the whole difference, and it only works because the dataset is complete before the first line of work. There is no incremental mode.
That is the honest reason for the gap, and also the reason it does not worry us. Our index is built for a catalog that keeps moving: task 1 measures one pass over a dataset that is finished, while our embedding pipeline produces the opposite situation, where vectors keep arriving and the index has to stay connected and searchable while they do. A batch builder is genuinely faster at the bulk build; it just has to redo it. We entered task 1 anyway, out of scientific curiosity about how far the approach can be pushed — and the quantization work it produced is useful well beyond this benchmark.
Key Takeaways: Cheaper Builds for Growing Catalogs
The quantization step is the part that outlives the benchmark. It makes every distance computation during construction eight times smaller, and construction cost is exactly what grows when a catalog grows.
While static batch processing excels in benchmarks, our approach proves we can deliver high-speed, cost-efficient index construction without sacrificing the dynamic adaptability that fast-growing e-commerce catalogs demand.
The other task we entered needed a different kind of change — the same index, but a geometry it was not built for: how we got the problem back into Euclidean space Winning the Search Task with A Different Geometry.
References
Our submission paper: Hezel, Barthel, Schilling, Schall, Moelle and Jung, Fast and Efficient Approximate Nearest Neighbor Search for High-Dimensional LLM Embeddings (arXiv:2607.20957), with the full method and all measurements.
Our code: Visual-Computing/sisap26-deglib, the submissions for both tasks.
The challenge: SISAP 2026 Indexing Challenge, tasks and datasets, and the leaderboard with every team’s results.
The index itself: our earlier post Dynamic Exploration Graph: Fast Search in Evolving Catalogs.
The conference: SISAP 2026, the 19th International Conference on Similarity Search and Applications, Brno, 14–16 October 2026.
Related Posts
Winning the Search Task with A Different Geometry
