- 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 , 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 , 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 , 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 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 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 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
Author Response to Reviewer F4dw (Part 2/2)
[Response to Q4] Thank you for catching this wording inconsistency. In our IVF-Residual implementation, is set directly to the K-means coarse centroid of list (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 already computed during coarse list selection (as noted in Appendix E.2, the term applies only when 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 () across all four datasets (where Ham denotes Hamming ranking):
| Dataset | Uncentered RP (Ham) | SCAN-ITQ | Centered RP (Ham) | Median-Thresh | SCAN-Residual (NARH) |
|---|---|---|---|---|---|
| arXiv | 0.5522 / 0.91005 | 0.9998 / 0.96830 | 0.9998 / 0.97230 | 1.0000 / 0.97145 | 0.9998 / 0.99215 |
| MSong | 0.4704 / 0.70240 | 0.9686 / 0.70625 | 0.9723 / 0.83350 | 1.0000 / 0.83110 | 0.9723 / 0.96500 |
| GIST | 0.5132 / 0.66465 | 0.9980 / 0.60090 | 0.9987 / 0.65335 | 1.0000 / 0.65250 | 0.9987 / 0.98260 |
| Tiny5M | 0.4945 / 0.36030 | 0.9983 / 0.48000 | 0.9989 / 0.51060 | 1.0000 / 0.51185 | 0.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 ; 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.
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=0), each vector's residual relative to the origin is the vector itself (x−0=x) with norm ∥x∥2, so SCAN-Direct (Equation 4: δ02(q,x)=∥q∥22+∥x∥22−2∥q∥2∥x∥2cos(πHB(q,x)/B)) is directly our norm-aware estimator (Equation 7) evaluated at c=0.
Comparing SCAN-Direct with SCAN-Residual (NARH) at the same reranking budget (B=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=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 cj, 1-bit/dim code length B=d (RaBitQ pads MSong from 420 to 448 bits), nprobe=128, and reranking budget L=100:
Under identical parameters, NARH achieves higher QPS on all four datasets, but with lower recall: at L=100, 1-bit RaBitQ already reaches high recall, whereas NARH requires a larger L to reach comparable recall, which reduces its QPS (e.g., on Tiny5M at nprobe=128, increasing L 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) across all four datasets and recomputed exact L2 ground truth. The table below reports the original ∥x∥2 distribution alongside unit-normalized Recall@20 (B=d,L=1000; CV = SD/Mean, the coefficient of variation; pp = percentage points):
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.