The Vector Search Challenge
The TIG vector search challenge has Innovators build algorithms that receive a database and query set of vectors. For each query vector, the algorithm must return a candidate database vector, such that the mean distance between the queries and the candidates is within some threshold. The database and query vectors are sampled from a mixture of Gaussians. Each instance of the TIG challenge is a new sampling of the database and query set.
Stat-filter High-Level Algorithm Flow
The Stat-filter algorithm has two main components, first a quantization is performed on all the vectors and then a MAD filter using the L2 norms of bit quantized vectors is applied before the search phase begins.
-
Quantization.
First the per-dimension min/max of the vectors is identified. Data shifting is applied, let \text{overall}\_\min be the minimum across all dimensions of all database vectors, if negative, a uniform shift is applied (every component of every vector gets \text{overall}\_\min subtracted from it). All data is now non-negative. By using the per-dimension min/max, the vectors are then quantized (each vector has its components in each dimension binned into 1 of either 4 or 16 bins, corresponding to 2-bit or 4-bit quantization.) By default 4-bit quantization is done, unless STATFILT_BIT_MODE=2, in which case 2-bit quantization is done.
-
MAD filter.
First the L2 norms of the quantized data are calculated. MAD is computed on quantized norms, not original norms! That is, MAD creates a length-based filter that rejects database vectors that are unlikely to be close to a query, based on their quantized L2 norms. What this means practically: the quantized database norms are sorted and then the median is found. The absolute deviations between the norms and the median is calculated for each database vector, and put into a list - the median of this list is then identified as a value called \text{mad}. A threshold is constructed via the formula
\text{threshold}= \text{scale} * \text{mad} * \text{MAD_SCALE_NORMAL}
For each query vector q and database vector p if
|\|q\|_2-\|p\|_2|>\text{threshold},
then when performing a search with q we will skip p. The two scaling terms are :
-
\text{MAD_SCALE_NORMAL}, which is set to 1.4826, which comes from the property that for a Normal distribution X \sim N(\mu,\sigma^2), if one defines MAD = \text{median}(|X - \text{median}(X)|) then \sigma \approx 1.4826 \times \text{MAD}. In the case of the submission X is the quantized L2 norm of a vector (which since we are in high dimensions is normal). Thus, the threshold effectively measures “how many standard deviations away from the median” a norm lies. This filtering makes sense due to the reverse triangle inequality.
-
The parameter \text{scale} adapts selectivity: for few queries (≤700) it is 0.20, giving fast but aggressive filtering (~80–90% removed), while for many queries (≥2500) it is 1.00, giving broader coverage (~50–60% removed) to preserve accuracy.
Brute Force Search. For each query, a GPU block computes the quantized dot product between it and non-filtered database vectors using bit-sliced operations. Each bit plane is compared using AND operations, then popcount tallies the matches. These counts are weighted by powers of 2 and summed to reconstruct the approximate dot product in quantized space. Each thread tracks its own top-K candidates, then all threads combine results to find the final top-K for exact reranking.
Performance
Here we evaluate the performance of the submission by testing it against other vector search algorithms. We stick to vector search algorithms that have a low build time. We test the algorithms on the fashion-mnist-784-euclidean dataset.
Two bar plots of stat_filter algorithm vs IVF-flat and IVF-PQ and Brute Force. On the left the total time algorithms took and on the right the recall (the proportion of candidate neighbours which were the true nearest neighbour). The submitted algorithm stat_filter achieves 0.95 recall, whilst being the fastest algorithm. We used the provided
SOTA repo to produce these results. We also point to the
evidence form which shows stat_filters performance against improved_search a previously high performing merged tig algorithm.
Claim of Novelty
According to the Advance Evidence Form, the claim of novelty relies on the following:
-
The method itself is entirely new,
-
The method represents a new combination of prior art,
-
The method applies known techniques in a novel way that produces a distinct technical effect.
As described above in the Stat-filter High-Level Algorithm Flow, the submission combines bit quantization with a Median Absolute Deviation (MAD) gating layer to eliminate low-probability candidate vectors before the costly distance computation stage of an Approximate Nearest Neighbour (ANN) pipeline. In the search phase, the method then applies an optimized brute-force approach, where a quantized dot product is used to efficiently search for approximate nearest neighbours. Within the ANN literature on filtering, this approach clearly belongs to the pre-filtering category: for each query, the database is filtered first, and search is performed only on the reduced set.
We now assess this method against the three points of novelty, noting that only one of these needs to be true in order to be considered “novel” (novelty being a requirement to be eligible for Advance rewards):
- Entirely new method Neither MAD filtering nor bit quantization are new in themselves, and bit quantization methods for ANN are well established . To the best of our knowledge, however, MAD filtering has not been applied in this specific way to ANN search. Similar examples of tasks for MAD are outlier detection or as a robust data scaling method . General filtering in ANN is also not new, with common examples including:
-
Metadata filters: restricting search to subsets of vectors based on attached scalar values
-
IVF methods: using cluster centroids for coarse partitioning (IVF-flat) or quantization (IVF-PQ)
-
Locality-Sensitive Hashing (LSH): bucketing vectors by random hash functions
-
New combination of prior art
To the best of our knowledge, there are no prior examples of combining bit-quantized MAD L2-norm filtering with bit-sliced similarity evaluation in this way for ANN search. However using bit-quantized vectors for distance calculations in itself is not a new combination.
-
Novel technical effect
The specific way these techniques are combined produces tangible technical benefits. MAD L2-norm filtering becomes significantly faster because it operates on quantized values, which in turn reduces the number of candidate vectors considered in the distance search. Since bit-sliced similarity itself requires bit quantization, the pipeline is tightly coupled, leading to improved efficiency overall. However as advised by the submitter when running the method on heavy-tailed distributions (like SIFT dataset) then STATFILT_MAD_SCALE must be 0. Any non-zero value will cause severe recall degradation. Hence when STATFILT_MAD_SCALE=0 the technical effect of the submission is only attributed to the quantization and bit-slicing, not the pre-filter.
The submitted evidence form reflects this analysis. It acknowledges that the method does not meet criterion (1) but makes a case that it qualifies for novelty under criteria (2) and (3).
Claim of inventiveness
Having established novelty, we now turn to inventiveness (or “non-obviousness”). The evidence from Granite Labs argues that the submission is non-obvious because a person of ordinary skill in the art (POSITA) would not naturally expect that combining a robust statistical measure from outside the ANN field with coarse quantization would yield state-of-the-art results.
Most existing ANN filters are based on mean statistics or clustering. In this context, the use of the Median Absolute Deviation (MAD) as a pre-filter is unconventional. MAD is typically used in outlier detection or robust scaling, but its application here to reject improbable candidates in a high-dimensional ANN setting is not an obvious choice. The method achieves two outcomes:
-
predictable speedups from filtering and low-precision computation, and
-
unexpectedly high recall, even after pre-filtering and quantized similarity evaluation.
The latter result strengthens the inventiveness claim. A POSITA might anticipate efficiency gains but would reasonably doubt whether accuracy could be preserved under such coarse approximations. The fact that the method demonstrates both efficiency and strong recall suggests that its effectiveness is not obvious from prior art.
Summary
The submission combines two well-known mathematical methods but applies them jointly to ANN search in a way that, to the best of our knowledge, has not previously been documented. The combination achieves clear technical benefits, as shown both in the evidence form and in our performance evaluations. Importantly, this method should not be directly compared to ANN algorithms that rely on pre-built or learned structures, since those approaches achieve faster query times at the cost of substantially higher build times.
