Exact and Deterministic Patch Descriptor Retrieval via Hierarchical Normalization

Modern AI systems rely on high-dimensional embedding retrieval, typically using Approximate Nearest Neighbor (ANN) indexes like HNSW or IVF-PQ to achieve speed. However, these methods sacrifice exactness and determinism, leading to inconsistent results across different hardware or run orders. This paper asks: can we achieve significant speed-ups in patch descriptor retrieval while maintaining the exactness and reproducibility of an exhaustive full-vector search?

The author introduces Hierarchical Normalization (HN), a technique that replaces standard L2 normalization. It splits a 128-dimensional feature vector into a K-dimensional major component and a (128-K)-dimensional minor component, assigning them specific norms. Because the minor component's inner product is bounded by a constant alpha, the major component's similarity plus alpha provides an admissible upper bound on the full similarity. This allows for a two-phase search: a fast scan of the major component to identify candidates, followed by a selective, exact evaluation of only those entries that cannot be mathematically pruned.

• Exactness and Determinism: The proposed method is mathematically proven to return the exact same nearest neighbor as an exhaustive search, regardless of hardware, thread count, or run order.
• Efficiency: Using a cache-optimized Structure-of-Arrays (SoA) layout, the method achieves significant speed-ups (e.g., 13.7x on the trevi dataset) while requiring full evaluation for less than 1% of the database entries.
• Quality: By fine-tuning existing models (like HardNet) with HN, the system maintains high discriminative quality, with false positive rates (FPR@95) nearly identical to the original, unconstrained models.

This work provides a robust alternative to ANN for applications where result consistency is critical, such as A/B testing, safety auditing, and regression tracking. By shifting the burden of efficiency from approximate indexing to a mathematically grounded normalization scheme, the paper demonstrates that exact retrieval does not have to be prohibitively slow.