[BUG] bftree-spherical quantization shows recall 0

[snash4]

Actual Behavior

I am using graph-index-build-bftree-spherical-quantization based on benchmark example to build an index on Ada dataset. Tried different configurations, it shows Recall 0

Ls,   KNN,    Avg cmps,   Avg hops,   QPS - mean(max),             Avg Latency,             p99 Latency,   Recall,   Threads
=============================================================================================================================
 50,    50,   1821.4697,    60.7184,   1361.5 (1399.9),   36914.7us (37347.6us),     82491.0us (83761us),        0,        56
100,    50,   2886.2495,   110.5933,     810.8 (816.8),   61367.2us (62271.0us),   133940.4us (136886us),        0,        56

Example Code

This is the conf file.

{
    "search_directories": [
        "https://github.com/ssd2/nash/anndata/ada/"
    ],
    "jobs": [
        {
            "type": "graph-index-build-bftree-spherical-quantization",
            "content": {
                "build": {
                    "data_type": "float32",
                    "data": "ada_002_1000000_base_vectors.bin",
                    "distance": "squared_l2",
                    "max_degree": 64,
                    "l_build": 50,
                    "insert_retry": null,
                    "start_point_strategy": "medoid",
                    "alpha": 1.2,
                    "backedge_ratio": 1.0,
                    "num_threads": 56,
                    "multi_insert": null
                },
                "search_phase": {
                    "search-type": "topk",
                    "queries": "ada_002_1000000_query_vectors_10000.bin",
                    "groundtruth": "https://github.com/ssd2/nash/anndata/ada/ada_new_gt10",
                    "reps": 5,
                    "num_threads": [
                        56
                    ],
                    "runs": [
                        {
                            "search_n": 50,
                            "search_l": [
                                50,
                                100 
                            ],
                            "recall_k": 10
                        }
                    ]
                },
                "seed": 42,
                "num_bits": 2,
                "pre_scale": "reciprocal_mean_norm",
                "transform_kind": "null",
                "vector_store_config": {
                    "cb_size_byte": 67108864,
                    "leaf_page_size": 4096,
                    "cb_max_record_size": null,
                    "cb_min_record_size": null,
                    "read_promotion_rate": null,
                    "scan_promotion_rate": null,
                    "cb_copy_on_access_ratio": null,
                    "read_record_cache": null,
                    "cache_only": null
                },
                "neighbor_store_config": {
                    "cb_size_byte": 67108864,
                    "leaf_page_size": 4096,
                    "cb_max_record_size": null,
                    "cb_min_record_size": null,
                    "read_promotion_rate": null,
                    "scan_promotion_rate": null,
                    "cb_copy_on_access_ratio": null,
                    "read_record_cache": null,
                    "cache_only": null
                },
                "quant_store_config": {
                    "cb_size_byte": 67108864,
                    "leaf_page_size": 4096,
                    "cb_max_record_size": null,
                    "cb_min_record_size": null,
                    "read_promotion_rate": null,
                    "scan_promotion_rate": null,
                    "cb_copy_on_access_ratio": null,
                    "read_record_cache": null,
                    "cache_only": null
                }
            }
        }
    ]
}

Dataset Description

Please tell us about the shape and datatype of your data, (e.g. 128 dimensions, 12.3 billion points, floats)

• Dimensions: 1536
• Number of Points: 1M
• Data type: float32

Your Environment

• DiskANN version (or commit built from): Commit 3aa44ac

Additional Details

The similar configuration works on Sift 100k dataset.
But on wikipedia-cohere dataset (768 dim), it again shows Recall 0

[hildebrandmw]

Yeah, this seems to be broken. I tried a few of the more obvious fixes and that didn't seem to work, so I'm going to have to dig a bit deeper. Thanks for reporting!

[hildebrandmw]

Here's something to try. By default cb_max_record_size appears to be 1952, which isn't big enough for wikipedia-sized full-precision vectors. For some reason ... bf-tree decided to use a boolean to indicate whether or not the insert succeeds and doesn't mark their insert function as #[must_use], so diskann was ignoring this.

I was able to get wikipedia to return reasonable recall with "cb_max_record_size": 4096.

You may also want to apply the following patch

diff --git a/diskann-bftree/src/provider.rs b/diskann-bftree/src/provider.rs
index 6d7fc90e..1421ff08 100644
--- a/diskann-bftree/src/provider.rs
+++ b/diskann-bftree/src/provider.rs
@@ -847,7 +847,7 @@ impl<'a, T> QuantAccessor<'a, T>
 where
     T: VectorRepr,
 {
-    pub(crate) fn new(
+    pub(crate) fn search(
         provider: &'a BfTreeProvider<T, QuantVectorProvider>,
         query: &[T],
     ) -> ANNResult<Self> {
@@ -861,6 +861,20 @@ where
         })
     }

+    pub(crate) fn insert(
+        provider: &'a BfTreeProvider<T, QuantVectorProvider>,
+        query: &[T],
+    ) -> ANNResult<Self> {
+        let computer = provider.quant_vectors.insert_computer(query)?;
+        Ok(Self {
+            provider,
+            computer,
+            element: (0..provider.quant_vectors.quantizer.bytes())
+                .map(|_| u8::default())
+                .collect(),
+        })
+    }
+
     fn get_distance(&mut self, id: u32) -> Result<f32, AccessError> {
         self.provider
             .quant_vectors
@@ -1317,7 +1331,7 @@ where
         _context: &'a DefaultContext,
         query: &'a [T],
     ) -> Result<Self::SearchAccessor, Self::SearchAccessorError> {
-        QuantAccessor::new(provider, query)
+        QuantAccessor::search(provider, query)
     }
 }

@@ -1336,6 +1350,15 @@ where
     fn prune_strategy(&self) -> Self::PruneStrategy {
         *self
     }
+
+    fn insert_search_accessor(
+        &'a self,
+        provider: &'a BfTreeProvider<T, QuantVectorProvider>,
+        _context: &'a DefaultContext,
+        query: &'a [T],
+    ) -> Result<Self::SearchAccessor, Self::SearchAccessorError> {
+        QuantAccessor::insert(provider, query)
+    }
 }

 impl<T, B> MultiInsertStrategy<BfTreeProvider<T, QuantVectorProvider>, B> for Quantized
diff --git a/diskann-bftree/src/quant.rs b/diskann-bftree/src/quant.rs
index e56d63b1..053d815b 100644
--- a/diskann-bftree/src/quant.rs
+++ b/diskann-bftree/src/quant.rs
@@ -93,6 +93,24 @@ impl QuantVectorProvider {
         Ok(QuantQueryComputer(inner))
     }

+    pub fn insert_computer<T>(&self, query: &[T]) -> ANNResult<QuantQueryComputer>
+    where
+        T: VectorRepr,
+    {
+        let query_f32 = T::as_f32(query).into_ann_result()?;
+        let inner = self
+            .quantizer
+            .fused_query_computer(
+                &query_f32,
+                QueryLayout::SameAsData,
+                false,
+                GlobalAllocator,
+                ScopedAllocator::global(),
+            )
+            .map_err(|e| ANNError::log_sq_error(e))?;
+        Ok(QuantQueryComputer(inner))
+    }
+
     /// Create a distance computer for the underlying schema
     pub fn distance_computer(&self) -> ANNResult<DistanceComputer> {
         self.quantizer

and use

"transform_kind": {
    "double_hadamard": "same"
},

instead of "null" for best results.

I'll open a PR with these fixes after the weekend.

Thanks again for reporting this!