acceptodds
Under review as a conference paper at ICLR 2027

Norm-Aware Residual Hashing for Fast Nearest Neighbor Search

Abstract

Approximate nearest neighbor (ANN) search in high-dimensional spaces plays an important role in modern AI applications. To reduce the cost of high-dimensional distance computations in ANN search, binary hashing represents vectors as compact binary codes and uses inexpensive Hamming distances to select candidates. However, we observe that vectors in several real-world datasets are concentrated within a narrow angular region. When such vectors are encoded, the resulting bits can be imbalanced and have low entropy, limiting the ability of binary codes to distinguish true neighbors from other candidates. Our experiments further show that more balanced bits alone do not ensure accurate L2 candidate ranking, since Hamming distance does not capture vector lengths. We propose Norm-Aware Residual Hashing (NARH), a mean-centered binary distance estimator designed to address these limitations. Our key idea is to center vectors before encoding to reduce angular concentration and make their directions more distinguishable. Since centering changes angles but preserves Euclidean distances, NARH uses angles estimated from centered binary codes and each vector's distance to the center to estimate original squared Euclidean distances. We further extend the estimator to inverted-file search with a separate mean for each posting list, using precomputed center projections to reduce expensive query-time projection computations. Our analysis provides a high-probability bound on squared-distance estimation error in terms of code length and residual norms, and a sufficient condition for preserving pairwise rankings. Experiments on four real-world datasets show that NARH reduces bit imbalance, improves recall at fixed reranking budgets, and achieves better search performance than binary hashing baselines based on random projection and Iterative Quantization (ITQ).

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
approximate nearest neighbor search, binary hashing, distance estimation, similarity search, vector retrieval, high dimensional data

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_F4dwOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Real-world datasets often exhibit directional concentration, causing random-hyperplane binary hashing to produce imbalanced, low-entropy bits that fail to distinguish true neighbors, and the authors show that high bit entropy alone is insufficient for accurate L2 ranking because candidate scoring must also account for vector lengths. They propose Norm-Aware Residual Hashing (NARH), which subtracts a shared center (global mean for SCAN, list-local means for IVF) before hashing to broaden angular distributions, then estimates original squared Euclidean distances by combining centered-code angle estimates with residual norms via the translation-invariant identity. They extend NARH to IVF efficiently by precomputing projected centers and using A(q−cj)=Aq−AcjA(q-c_j)=Aq-Ac_j, and they derive a finite-bit error bound plus a pairwise order-preservation condition. Experiments on arXiv, MSong, GIST, and Tiny5M show NARH improves recall over random-projection and ITQ baselines in both SCAN and IVF, with residual-norm scoring proving essential even when bit entropy is already near one.

Critical strengths
  • The paper provides a clean, well-controlled demonstration that bit entropy is not a sufficient proxy for L2 ranking quality, using identical codes with only the scoring rule changed. For my overall assessment, this is the paper's most defensible contribution: regardless of whether NARH's centering is novel, the paper substantiates that "high entropy alone is insufficient for L2 candidate ranking" with direct evidence, and that norm-aware scoring is necessary even when codes are already balanced.
  • The IVF integration is a genuinely useful engineering contribution that makes list-local centering practical at scale. Even if the centering idea itself is inherited, the paper demonstrates a concrete, low-overhead way to operationalize it inside a standard inverted-file index.
Critical weaknesses
  • The paper never isolates the contribution of centering from the contribution of norm information, so its central claim, that reducing directional concentration improves L2 candidate ranking, is not established. This is consequential because the entire method rests on the premise that mean-centering broadens angular distributions and thereby produces more discriminative codes. But the paper's own experiments show that residual norms alone can produce very large gains even without NARH's centering: with identical ITQ codes (which use a different centering scheme), switching from Hamming to residual-norm scoring raises GIST Recall@20 from 0.60090 to 0.92865. A "no centering + residual-norm scoring" control is conspicuously absent. Without it, the observed gains cannot be attributed to centering rather than to the explicit use of vector lengths, which the paper itself notes varies across real datasets.
  • The paper does not clarify its relationship to RaBitQ at D=1D = 1, leaving its novelty relative to a closely related method undefined. This is consequential because RaBitQ already uses the same core ingredients, subtracting a center, computing residual norms, and applying the translated L2 identity σ2(q,x)=‖q−c‖2+‖x−c‖2−2‖q−c‖‖x−c‖cos⁡θc\sigma^2(q,x) = ‖q−c‖^2+ ‖x−c‖^2 − 2‖q−c‖‖x−c‖\cos\theta_c, and provides theoretical guarantees for its estimator. The paper acknowledges the inspiration ("Inspired by RaBitQ's residual formulation") but never analyzes whether NARH is simply a special case of RaBitQ with a different center choice and a Hamming-based angle estimator. In particular, the paper does not compare against RaBitQ under the same 1-bit-per-dimension regime with matched centers, nor does it state what NARH provides that RaBitQ does not.
Questions for authors
  • The paper compares NARH against Hamming ranking, showing that norm-aware scoring matters, but it never reports a "no centering + residual-norm scoring" condition. If such a control yields recall close to NARH, then centering is not the source of the gains, and the paper's stated mechanism is unsupported. If the gap is large, centering's independent value is established. Either outcome would materially change how I weigh the paper's central claim.
  • The current IVF comparison uses different code lengths, budgets, and center choices. A matched comparison, same center, same bits per dimension, same reranking budget, would clarify whether NARH is a distinct method or effectively RaBitQ's D=1D = 1 case with mean centering. This directly affects the novelty assessment.
  • The paper states it uses original, unnormalized vectors. If the four main datasets have substantial norm variation, the gains may be driven mainly by norm information rather than by directional concentration. Reporting the distribution of ‖x‖‖x‖ and the correlation between norm variation and recall gain would clarify this. This is consequential because it tests the alternative explanation for the results.
  • Section 5.3 says cjc_j is the list mean, while Appendix B.3 refers to K-means centroids as the mean baseline. If these coincide, the query residual norm can be reused from list selection; if not, the reported QPS may already include an additional per-list distance computation. Clarifying this affects the interpretation of the complexity claim and the QPS numbers.
  • Does the paper's claim that "higher bit entropy alone does not ensure accurate L2 candidate ranking" hold across all four datasets, or only on GIST? The ITQ comparison is reported in detail for GIST (0.60090 vs. 0.66465) and referenced in Appendix F.5 for the full set. If the pattern is GIST-specific, the general claim is weaker than presented. Confirming whether the entropy-vs-recall mismatch appears on arXiv, MSong, and Tiny5M would affect how strongly I treat this as a general finding.
  • The ANN background and motivation occupy more space than necessary for a venue where readers are already familiar with hashing-based retrieval. The paper spends roughly the first two paragraphs restating well-known material, storage and Hamming comparison costs, SIMD acceleration, the data-independent vs. data-dependent taxonomy, and the standard Charikar collision-probability identity. None of this is in dispute, and none of it is needed to set up the contribution.
  • First, if the centering step is standard preprocessing, then Figure 1 does not illustrate a contribution; it illustrates a known property. Presenting it as the paper's main idea overstates the novelty. Second, and more importantly, it reinforces the concern from the previous discussion: the paper treats centering as the mechanism that drives the gains, but centering is so common that its presence cannot by itself distinguish NARH from prior work. What would distinguish NARH is not centering, but the specific combination of centering with a Hamming-based angle estimate and a residual-norm distance reconstruction, and even there, RaBitQ already occupies much of that space. The paper does not make this distinction explicit.
12 comments
AuthorsOpenReview ↗

Author Response to Reviewer F4dw (Part 1/2)

We sincerely thank you for your thorough review and constructive questions (section and appendix numbers in our responses refer to our initial submission).

[Response to W1 & Q1] We apologize for not making our baseline definition clear enough in Section 7.1: SCAN-Direct in the paper is already this exact "no centering + norm-aware scoring" control. Without centering (c=0c=0), each vector's residual relative to the origin is the vector itself (x−0=xx-0=x) with norm ∥x∥2\|x\|_2, so SCAN-Direct (Equation 4: δ^02(q,x)=∥q∥22+∥x∥22−2∥q∥2∥x∥2cos⁡(πHB(q,x)/B)\widehat{\delta}_0^2(q,x)=\|q\|_2^2+\|x\|_2^2-2\|q\|_2\|x\|_2\cos(\pi H_B(q,x)/B)) is directly our norm-aware estimator (Equation 7) evaluated at c=0c=0.

Comparing SCAN-Direct with SCAN-Residual (NARH) at the same reranking budget (B=d,L=1000B=d, L=1000) therefore isolates the independent effect of mean-centering while holding norm-aware scoring fixed (please also see the full ablation table in our response to Reviewer iaGS, W2 & Q2). Across all four datasets, centering yields substantial recall gains: for example, Recall@20 increases from 0.90990 to 0.99215 (+8.2 percentage points) on arXiv and from 0.85700 to 0.98260 (+12.6 percentage points) on GIST (as well as 0.88870 to 0.96500 on MSong and 0.54340 to 0.78160 on Tiny5M). We will revise Section 7.1 to state this role of SCAN-Direct explicitly.

[Response to W2 & Q2] While both methods use the translated Euclidean distance identity, NARH is distinct from RaBitQ's D=1D=1 case: NARH maps both database and query residuals to binary codes and estimates residual angles directly via symmetric Hamming distance (XOR + POPCNT). In contrast, instead of mapping queries to binary codes, 1-bit RaBitQ retains more query information, achieving higher estimation accuracy at the cost of slower code-scanning computation (please also see our response to Reviewer iaGS, W1 & Q1, regarding RaBitQ).

The table below compares them under a strictly matched IVF setting with the same 4,096 K-means centers cjc_j, 1-bit/dim code length B=dB=d (RaBitQ pads MSong from 420 to 448 bits), nprobe=128n_{\mathrm{probe}}=128, and reranking budget L=100L=100:

Dataset (B=dB=d)IVF-Residual (NARH) RecallIVF-RaBitQ (1-bit) RecallIVF-Residual (NARH) QPSIVF-RaBitQ (1-bit) QPS
arXiv (768)0.908050.985101,1931,019
MSong (420)0.918150.994702,2142,163
GIST (960)0.813700.948751,2721,165
Tiny5M (384)0.570700.880201,092721

Under identical parameters, NARH achieves higher QPS on all four datasets, but with lower recall: at L=100L=100, 1-bit RaBitQ already reaches high recall, whereas NARH requires a larger LL to reach comparable recall, which reduces its QPS (e.g., on Tiny5M at nprobe=128n_{\mathrm{probe}}=128, increasing LL to 1000 and 2000 raises NARH's recall to 0.87535 at 687 QPS and 0.92240 at 490 QPS). This extra reranking cost is the main overhead that makes NARH slower than RaBitQ in many cases.

[Response to Q3] Both SCAN-Direct and SCAN-Residual incorporate vector norms in candidate scoring; the difference is that SCAN-Residual applies mean-centering while SCAN-Direct does not, and centering brings clear recall gains (as shown in W1 & Q1). To test whether these improvements persist without original norm variation, we unit-normalized all database and query vectors (x~=x/∥x∥2\tilde{x}=x/\|x\|_2) across all four datasets and recomputed exact L2 ground truth. The table below reports the original ∥x∥2\|x\|_2 distribution alongside unit-normalized Recall@20 (B=d,L=1000B=d, L=1000; CV = SD/Mean, the coefficient of variation; pp = percentage points):

DatasetRaw ∥x∥2\|x\|_2 (Mean ±\pm SD, CV)Unit SCAN-DirectUnit SCAN-Residual (NARH)
arXiv1.00±0.001.00 \pm 0.00 (0.000)0.910150.99215 (+8.2 pp)
MSong80.95±43.8980.95 \pm 43.89 (0.542)0.792200.97910 (+18.7 pp)
GIST2.51±0.702.51 \pm 0.70 (0.278)0.784750.97750 (+19.3 pp)
Tiny5M1.29±0.361.29 \pm 0.36 (0.282)0.446300.77690 (+33.1 pp)

Even when all vectors have unit length, directional concentration remains present on all four datasets, and SCAN-Residual continues to achieve large recall gains over SCAN-Direct (+8.2 to +33.1 pp). These results show that substantial gains persist after removing original vector-length variation, indicating that the improvements cannot be explained solely by variation in original norms.

AuthorsOpenReview ↗

Author Response to Reviewer F4dw (Part 2/2)

[Response to Q4] Thank you for catching this wording inconsistency. In our IVF-Residual implementation, cjc_j is set directly to the K-means coarse centroid of list jj (as described in Appendix B.3; Section 5.3 wrote the list-mean formula to motivate list-local centering conceptually, and we will align Section 5.3 with Appendix B.3). Accordingly, our experiments directly reuse the squared distance ∥q−cj∥22\|q-c_j\|_2^2 already computed during coarse list selection (as noted in Appendix E.2, the O(nprobed)O(n_{\mathrm{probe}} d) term applies only when cjc_j differs from the coarse centroid, such as the median-center ablations in Appendix B.3).

[Response to Q5] The table below reports mean per-bit entropy / Recall@20 (B=d,L=1000B=d, L=1000) across all four datasets (where Ham denotes Hamming ranking):

DatasetUncentered RP (Ham)SCAN-ITQCentered RP (Ham)Median-ThreshSCAN-Residual (NARH)
arXiv0.5522 / 0.910050.9998 / 0.968300.9998 / 0.972301.0000 / 0.971450.9998 / 0.99215
MSong0.4704 / 0.702400.9686 / 0.706250.9723 / 0.833501.0000 / 0.831100.9723 / 0.96500
GIST0.5132 / 0.664650.9980 / 0.600900.9987 / 0.653351.0000 / 0.652500.9987 / 0.98260
Tiny5M0.4945 / 0.360300.9983 / 0.480000.9989 / 0.510601.0000 / 0.511850.9989 / 0.78160

Across all four datasets, SCAN-ITQ and Centered RP (Ham) substantially raise bit entropy (to 0.97-1.00), and Median-Threshold (Appendix F.6) pushes entropy to 1.0000, yet their recall gains remain limited (and even drop on GIST). They still leave substantial recall gaps relative to norm-aware SCAN-Residual across all datasets, confirming that high bit entropy alone is not sufficient for accurate L2 candidate ranking.

[Response to Q6] Thank you for pointing this out. We agree that the introductory review of general ANN, binary hashing taxonomy, and standard collision identities takes more space than needed, and we will condense the opening paragraphs of Section 1, which will also free space for the ablations and RaBitQ/PQ comparisons moved from the appendix.

[Response to Q7] While centering itself is a well-known operation (for instance, ITQ zero-centers data before learning rotations, whereas standard random-hyperplane LSH hashes uncentered vectors directly), prior binary-hashing work typically treats it as routine preprocessing rather than analyzing how directional concentration narrows pairwise angles, causes bit imbalance, and alters angles after centering so that Hamming ranking alone remains inadequate for L2 search. Figure 1 was intended to illustrate this geometric mechanism, but we agree that showing centering in isolation can give the misleading impression that centering itself is our main contribution. As our ablations in W1 & Q1 and Q5 show, neither centering alone (Centered RP (Ham), SCAN-ITQ) nor our uncentered norm-aware baseline (SCAN-Direct) suffices; what defines NARH is coupling centering (global in SCAN and list-local in IVF) with symmetric Hamming-based angle estimation and residual-norm L2 reconstruction, and we will revise Figure 1 and Section 1 to present both this geometric diagnosis and the complete pipeline. Relative to RaBitQ, which also centers residuals and uses the translated L2 identity, instead of mapping queries to binary codes, RaBitQ retains more query information and incurs higher code-scanning cost, whereas NARH maps both database and query residuals to binary codes for simpler Hamming-based scanning (XOR + POPCNT) and flexible code lengths BB; we will make this distinction explicit in the main paper (please also see W2 & Q2 above and our response to Reviewer iaGS, W1 & Q1).

We will revise the paper to reflect all of these updates and upload the revised manuscript before the end of the rebuttal period.

Thank you very much for the authors' careful and conscientious response, as well as the extensive additional experiments. I truly appreciate the effort reflected here.

However, I am afraid I remain somewhat unsatisfied with the comparison between the current work and RaBitQ. I would sincerely hope the authors could provide a more detailed derivation clarifying why RaBitQ at 1 bit cannot be reduced to the form of NARH through a simple transformation (To be more specific about my concern: RaBitQ at 1 bit does not require a lookup table.). Specifically, a rigorous argument, rather than an intuitive or high-level statement, would be very helpful in understanding the fundamental distinction the authors claim. Without such a derivation, it remains difficult for me to assess whether the proposed design offers a genuinely necessary alternative to RaBitQ's 1-bit formulation.

Reviewer_VPT2OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the problem of representing vectors as fixed-length binary codes for efficient ANN search. The authors' first contribution identifies a crucial limitation of previous binarization strategies in the literature, namely that they result in concentrated vector representations that make it difficult to identify the true nearest neighbors to a given query. They then propose NARH, a mean-centered estimator designed to address the issue of imbalanced concentration of real-world binarized representations. Finally, the authors experimentally validate the efficacy of NARH on 4 million-scale ANN datasets where they show improved search quality over binary hashing baselines.

Critical strengths
  1. The paper is well-written and identifies a clear problem with prior work on binary hashing: that binary representations tend to concentrate leading to imbalance that makes it difficult to perform efficient sublinear search. The NARH approach is thus well-motivated and the authors' experiments demonstrate that it helps address this precise problem. I think the diagnosis of this imbalance is problem is a critical strength of this paper.
Critical weaknesses
  1. I think the quality of the experimental validation in the current version of the paper is a critical weakness. The authors only benchmark their method on million-scale datasets, but I think it is critical to understand how the method performs on 10M, 100M, or 1B scale datasets such as those in Big ANN benchmarks since that is where efficiency becomes a primary concern for ANN systems. Secondly, the authors do not explicitly compare NARH to quantization methods like RabitQ even though NARH shares many conceptual and operational similarities to RabitQ such as mean centering. I think broadening the experimental evaluation to include state of the art quantization baselines like RabitQ would be very informative from a scientific perspective.
Questions for authors
  1. Is there a reason the authors do not include quantization methods like RabitQ in their experimental comparison alongside NARH? I understand the focus of this paper is on binarized representations, but my understanding is that binary representations are only a means to an end for efficient search and RabitQ provides a similar strategy for achieving efficiency. If, for example, RabitQ is more efficient than NARH, I think that would be a very interesting scientific finding to report since it gives us a better understanding of how vector quantization methods compare.
1 comment
AuthorsOpenReview ↗

Author Response to Reviewer VPT2

We sincerely thank you for your positive assessment of our problem diagnosis and constructive suggestions on large-scale evaluation and quantization baselines.

[Response to W1 (10M- and 100M-scale evaluation on BIGANN)] To evaluate NARH beyond the million-scale datasets in our submission (up to 5M on Tiny5M), we benchmarked BIGANN-10M (N=10M,d=128N=10\text{M}, d=128, raw SIFT vectors, B=128B=128 bits, K=20K=20) in both SCAN and IVF (4,096 lists), as well as BIGANN-100M (N=100M,d=128N=100\text{M}, d=128) in IVF (16,384 lists), on AWS EC2 instances. Because raw SIFT vectors lie in the non-negative orthant (∥μ∥2=344.2\|\mu\|_2=344.2), uncentered binary codes suffer severe bit imbalance:

  1. SCAN (BIGANN-10M). Global centering raises mean bit entropy from 0.7095 to 0.9996. Below is Recall@20 across budgets LL:
Budget LLUncentered RP (Ham)SCAN-DirectSCAN-Residual (NARH)
1000.212400.212800.32855
5000.417750.417650.57990
10000.520700.519800.68840
30000.684400.685350.83485
100000.835250.837150.93705

Because raw SIFT norms vary very little, SCAN-Direct stays close to Uncentered RP (Ham), whereas SCAN-Residual improves recall by +10.0 to +16.9 percentage points (and outperforms Centered RP (Ham), e.g., 0.68840 vs. 0.66750 at L=1000L=1000).

  1. IVF (BIGANN-10M, 4,0964,096 lists, nprobe=128n_{\mathrm{probe}}=128). List-local centering in IVF-Residual yields even larger gains inside IVF clusters; below is Recall@20:
Budget LLIVF-DirectIVF-Residual (NARH)
1000.224950.50785
5000.444400.78685
10000.558050.87070
20000.674650.93085

Across L≤2000L \le 2000, IVF-Direct stays below 0.68 recall, whereas IVF-Residual improves recall by +25.6 to +34.3 percentage points.

  1. Comparison with RaBitQ (BIGANN-10M, packed SIMD). In SCAN (B=128B=128), Recall@20 (single-threaded QPS) comparing SCAN-Residual with 1-bit SCAN-RaBitQ is as follows:
Budget LLSCAN-Residual (NARH)SCAN-RaBitQ (1-bit)
1000.32855 (38.7)0.61310 (25.4)
5000.57990 (38.3)0.89795 (25.4)
10000.68840 (37.3)0.95675 (24.9)
30000.83485 (34.9)0.99300 (23.9)
100000.93705 (28.4)0.99950 (20.7)

Because symmetric Hamming scanning (XOR + POPCNT) scans the 10M codes ~1.5x faster than SCAN-RaBitQ, SCAN-Residual reaches 0.93705 recall at 28.4 QPS (L=10000L=10000), faster than SCAN-RaBitQ at ≥0.90\ge 0.90 recall (0.95675 at 24.9 QPS, L=1000L=1000), whereas SCAN-RaBitQ reaches >0.99>0.99 recall with a smaller LL. In IVF (4,0964,096 lists, nprobe=128n_{\mathrm{probe}}=128) at L=2000L=2000, IVF-Residual achieves 0.93085 recall (501 QPS) versus 0.99310 (378 QPS) for 1-bit IVF-RaBitQ (scanning faster at fixed LL, while RaBitQ reaches comparable recall with a smaller LL).

  1. BIGANN-100M (IVF, 16,38416,384 lists, nprobe=128n_{\mathrm{probe}}=128). Scaling further to N=100MN=100\text{M} (d=128,B=128d=128, B=128), at L=5000L=5000 the Recall@20 is 0.66705 for IVF-Direct, 0.94075 (177.9 QPS) for IVF-Residual (NARH), and 0.98560 (101.7 QPS) for 1-bit IVF-RaBitQ: NARH substantially improves recall over IVF-Direct and achieves faster scanning speed than RaBitQ at equal LL, while RaBitQ attains higher accuracy.

[Response to W1 & Q1 (Comparison with RaBitQ and PQ)] In our submission, we placed the RaBitQ and PQ comparisons in Appendix C while keeping Section 7 focused on binary-hashing baselines (Direct and ITQ). We fully agree that including these quantization baselines in the main paper provides valuable scientific insight, and we will move the RaBitQ and PQ comparisons into Section 7. Briefly, NARH clearly outperforms classical PQ and remains competitive with its accelerated variant PQ4-FastScan. Compared with 1-bit RaBitQ, instead of mapping queries to binary codes, RaBitQ retains more query information and uses batch-packed SIMD lookup tables to accelerate computation, achieving higher accuracy per bit and needing a smaller reranking budget LL, which makes it faster in many batched IVF settings. In contrast, NARH maps both database and query vectors to binary codes (XOR + POPCNT), giving it a lighter scanning stage (though with higher reranking cost) and decoupling code length BB from dd, which offers advantages in SCAN, certain direct-POPCNT IVF settings, and flexible code lengths. For detailed comparisons across all datasets and settings, please refer to our responses to Reviewer iaGS (W1 & Q1) and Reviewer F4dw (W2 & Q2).

We will revise the paper to incorporate the BIGANN-10M/100M benchmarks and main-text RaBitQ/PQ comparisons, and upload the revised manuscript before the end of the rebuttal period.

Reviewer_iaGSOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Norm-Aware Residual Hashing for approximate nearest neighbor search. It combines mean-centered binary codes with residual norms to estimate Euclidean distances, and evaluates the method in exhaustive scanning and inverted-file search.

Critical strengths
  1. The paper identifies and analyzes the effects of directional concentration and bit imbalance on binary hashing.

  2. The experiments include controlled analyses of centering and scoring, as well as comparisons with stronger ANN methods in the appendix.

  3. The paper is generally clear and well organized.

Critical weaknesses
  1. The main paper focuses on Direct and ITQ, whereas the appendix shows that NARH is not consistently faster than RaBitQ at comparable recall, leaving its practical advantage over modern alternatives unclear.

  2. ITQ is primarily compared using Hamming ranking, while NARH additionally uses residual norms; the appendix shows that adding norm-aware scoring to the same ITQ codes substantially improves recall, complicating attribution of the reported gains.

Questions for authors
  1. In which practical settings does NARH offer a clear advantage over RaBitQ or PQ in terms of recall, query speed, memory, and index construction cost?

  2. Could the authors move the same-code ITQ scoring comparison into the main paper and clarify how much of the gain comes from the encoder versus the scoring rule?

1 comment
AuthorsOpenReview ↗

Author Response to Reviewer iaGS

We sincerely thank you for your constructive feedback and insightful questions, which greatly help us improve our paper (section and appendix numbers below refer to our initial submission).

[Response to W1 & Q1] Our work focuses on binary hashing, represented by random-projection hashing (Direct) and Iterative Quantization (ITQ), which maps both database and query vectors to binary codes and ranks candidates via native Hamming operations (XOR + POPCNT). Despite their simplicity and hardware universality, these methods often yield low recall. Our goal is to understand the key factors behind this and show that addressing them substantially improves search efficiency while preserving simple Hamming-based execution. Compared with PQ and RaBitQ, NARH's practical trade-offs and advantages are as follows:

  1. PQ. PQ and its accelerated variant PQ4-FastScan are widely adopted in modern vector databases. NARH clearly outperforms PQ in search speed, construction cost, and memory footprint, while remaining competitive with PQ4-FastScan. On arXiv (B=dB=d), for example, NARH uses half the code memory of PQ8, builds faster without training (13.0s vs. 16.5s), and reaches 915 QPS at ≥98%\ge 98\% recall, compared with 103 QPS for PQ8 (8.9x faster) and 653 QPS for PQ4-FastScan (1.4x faster). Full results across all datasets are reported in Appendices C, F.3, and F.4.

  2. RaBitQ (search speed). Instead of mapping queries to binary codes, RaBitQ retains more query information and uses batch-packed SIMD lookup tables to accelerate computation, outperforming NARH in many IVF settings. However, NARH still achieves close high-recall performance with a small gap on datasets such as arXiv and GIST (e.g., retaining ~93% of RaBitQ's QPS at 99.25% recall on arXiv, Appendix C). In exhaustive scan (SCAN-RaBitQ vs. SCAN-NARH, both with packed SIMD enabled), where code scanning dominates query time, SCAN-NARH (B=dB=d) runs faster on arXiv, MSong, and GIST (e.g., 123 vs. 80 QPS on arXiv, 1.54x, and 223 vs. 151 QPS on GIST, 1.47x, at ≥98%\ge 98\% recall).

    Moreover, as noted in the RaBitQ paper (Gao & Long, 2024), this lookup-table acceleration "requires the quantization codes to be packed in a batch, which is feasible in some certain scenarios only." When batch-packed layout optimization is disabled in IVF so both score candidates directly via POPCNT, NARH needs one XOR + POPCNT pass instead of multiple bit-plane passes: at ≥98%\ge 98\% recall, it achieves higher QPS on arXiv and GIST (719 vs. 575 QPS, 1.25x, and 475 vs. 369 QPS, 1.29x), though it is not faster on MSong and Tiny5M, where NARH's short binary codes (B=dB=d) incur larger estimation error and require a larger reranking budget LL, offsetting the speedup in the scanning stage.

  3. RaBitQ (code-length flexibility). RaBitQ's minimum code length equals the vector dimension (B=dB=d), whereas NARH decouples code length BB from dd to support tighter memory budgets (such as B=d/2B=d/2); evaluations across different code lengths are reported in Appendices F.1 and F.2.

We will also move the key PQ and RaBitQ comparisons into Section 7 of the main paper.

[Response to W2 & Q2] Yes, we will move both the same-code ITQ scoring comparison and the centering/scoring ablation from the appendix into Section 7. The table below reports Recall@20 (B=d,L=1000B=d, L=1000) across random projection (RP) and ITQ variants (where Ham denotes Hamming ranking) to clarify how the encoder and the scoring rule each contribute:

DatasetUncentered RP (Ham)Centered RP (Ham)SCAN-Residual (NARH)SCAN-ITQSCAN-Residual-ITQSCAN-Direct
arXiv0.910050.972300.992150.968300.984350.90990
MSong0.702400.833500.965000.706250.850000.88870
GIST0.664650.653350.982600.600900.928650.85700
Tiny5M0.360300.510600.781600.480000.765900.54340

Starting from Uncentered RP (Ham), mean-centering alone (Centered RP (Ham)) improves recall on three datasets, but the gain is limited and recall even drops slightly on GIST (0.66465 to 0.65335) because Hamming distance ignores residual norms. Adding residual-norm information via our scoring rule brings substantial further gains across all datasets (+2.0 to +32.9 percentage points, pp), corresponding to SCAN-Residual (NARH). Applying the same scoring rule to fixed ITQ codes (SCAN-ITQ to SCAN-Residual-ITQ) also yields large improvements (+1.6 to +32.8 pp), validating our norm-aware scoring rule; meanwhile, when both account for norms, ITQ underperforms RP on all four datasets (by 0.8 to 11.5 pp), which is one reason we adopt RP as our default binary mapping. Finally, SCAN-Direct applies our scoring rule without centering and remains well below SCAN-Residual (by 7.6 to 23.8 pp), demonstrating the necessity of centering.

We will revise the paper to reflect these updates and upload the revised manuscript before the end of rebuttal period.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.