Probabilistic Kernel Function for Fast Angle Testing

This paper introduces deterministic, projection-based probabilistic kernel functions for fast angle testing in high-dimensional spaces that eliminate asymptotic assumptions and achieve 2.5x–3x higher query throughput than HNSW in approximate nearest neighbor search.

The Gist

Imagine you are running a massive library with billions of books, but instead of titles, every book is represented by a complex, multi-dimensional "fingerprint" (a vector). You have a query book, and you want to find the 10 most similar books in the entire library as fast as possible. This is the Approximate Nearest Neighbor Search (ANNS) problem.

The challenge? The library is so big, and the fingerprints so complex, that checking every single book one by one would take forever. You need a "speed filter" to skip the books that definitely aren't similar, so you only do the heavy lifting on the promising ones.

This paper introduces a new, smarter speed filter called KS (Kernel Function for Speed), which makes finding these similar books 2.5 to 3 times faster than the current best methods.

Here is the breakdown of how it works, using simple analogies:

1. The Old Way: The "Gaussian Guess"

For a long time, the best way to filter books was to use a technique called CEOs (Concomitants of Extreme Order Statistics).

• The Analogy: Imagine you have a giant, invisible net made of random strings (projection vectors) floating in the air. To see if two books are similar, you throw them into the net. If they land in the same "hole" or get caught by the same string, they are likely similar.
• The Problem: The old method used strings made of "Gaussian" material (like random, fluffy cotton). The math behind this method relied on a dangerous assumption: "If we throw enough strings (infinity), the math works perfectly."
• The Reality: In the real world, we can't throw infinite strings. We have to use a limited number. Because the old math relied on that "infinity" assumption, it wasn't always accurate when the number of strings was small, leading to missed books or wasted time checking the wrong ones.

2. The New Way: The "Structured Compass"

The authors realized the "fluffy cotton" (Gaussian distribution) wasn't the secret sauce. The real secret was the angle between the book and the string.

• The Analogy: Instead of random cotton strings, imagine you build a perfectly structured compass with needles pointing in specific, evenly spaced directions.
• The Innovation: They designed a new "Kernel Function" (a mathematical rule) that uses these structured needles.
  • No More "Infinity" Assumption: Their math works perfectly even with a small number of needles. It's like having a compass that works just as well with 4 needles as it does with 400.
  • The "Reference Angle": They realized that the closer your needle is to the book you are looking for, the more accurate the guess. They built their compass specifically to minimize the gap between the needle and the book, making the guess much sharper.

3. Two Superpowers

The paper proposes two specific tools (Kernel Functions) for two different jobs:

• Tool 1 (KS1): The "Better Comparator"

  • Job: "Is Book A more similar to the Query than Book B?"
  • How it helps: It replaces the old "Gaussian" method in tasks like finding the "Maximum Inner Product" (finding the most relevant ad for a user).
  • Result: It's slightly more accurate than the old way, meaning you find the right books with fewer mistakes.

• Tool 2 (KS2): The "Super Fast Gatekeeper"

  • Job: "Is Book A similar enough to even bother checking?"
  • How it helps: This is the big winner. It is used in Graph-based search (like the popular HNSW algorithm). Imagine a maze where you are trying to find the exit. The old gatekeepers (PEOs) would stop and think for a long time at every intersection to decide which path to take.
  • The KS2 Magic: The new gatekeeper is lightning fast. It looks at the intersection and instantly says, "No, that path is a dead end," or "Yes, go that way!" without doing the heavy math.
  • Result: Because it skips so many dead ends so quickly, the whole search process becomes 2.5 to 3 times faster (measured in Queries Per Second) while still finding the correct books.

4. The "Cross-Polytope" Secret Sauce

How did they build this perfect compass?

• The Analogy: Instead of throwing darts randomly at a board (Gaussian), they arranged the darts in a specific geometric shape called a Cross-Polytope (think of a 3D star or an octahedron).
• Why it works: This shape covers the space much more evenly. It ensures that no matter where your "Query Book" is, there is always a "Needle" very close to it. This minimizes the "Reference Angle" (the gap), making the prediction incredibly precise.

Summary: Why Should You Care?

If you use AI for recommendations, search engines, or image recognition, this paper offers a way to make those systems significantly faster and cheaper without losing accuracy.

• Old Method: Like using a random net to catch fish. It works if you wait forever, but it's messy and slow in practice.
• New Method (KS): Like using a high-tech, structured sonar that knows exactly where to look. It's deterministic, requires fewer resources, and gets you to the answer 3x faster.

The authors have even made their code open-source, so developers can start using this "super-compass" to speed up their own AI applications today.

Technical Summary

1. Problem Statement

The paper addresses the challenge of similarity search in high-dimensional Euclidean spaces, specifically focusing on angle testing. While exact angle computation (cosine similarity) has a cost of $O(d)$, which is prohibitive for high dimensions, many applications only require probabilistic decisions rather than exact values. The authors define two core problems:

1. Angle Comparison (Problem 1.1): Given a query $q$ and two data vectors $v_1, v_2$, determine if $\langle q, v_1 \rangle > \langle q, v_2 \rangle$ with high probability, using a kernel function with computational cost $o(d)$.
2. Angle Thresholding (Problem 1.2): Given a threshold $\theta$, determine if the angle between $q$ and $v$ is less than $\theta$ (i.e., $\langle q, v \rangle > \cos \theta$) with high probability, again with $o(d)$ cost.

Limitations of Existing Approaches:
Current state-of-the-art methods, such as CEOs (Concomitants of Extreme Order Statistics) and PEOs (used in graph-based ANNS like HNSW), rely on random projection vectors drawn from a Gaussian distribution. These methods depend on a theoretical lemma (Lemma 1.3) that assumes the number of projection vectors $m \to \infty$. In practice, $m$ is finite, leading to theoretical gaps and suboptimal performance because the Gaussian distribution does not guarantee the smallest "reference angle" (the angle between the query and the best-matching projection vector).

2. Methodology

The authors propose a new framework based on Probabilistic Kernel Functions that eliminates the need for asymptotic assumptions ($m \to \infty$) and leverages a deterministic structure for projection vectors.

A. Core Concept: Reference Angles

Instead of relying on Gaussian randomness, the authors introduce a reference angle $\psi$, defined as the angle between the query vector $q$ and its "reference vector" $Z_S(q)$ (the projection vector in a set $S$ that has the maximum inner product with $q$).

• Key Insight: The accuracy of angle estimation depends primarily on the magnitude of this reference angle $\psi$. A smaller $\psi$ yields higher accuracy.
• Deterministic Structure: The authors design the set of projection vectors $S$ to minimize the expected reference angle, rather than relying on random Gaussian sampling.

B. Proposed Kernel Functions

Two kernel functions are defined for the two problems:

1. $K^1_S(q, v)$ (for Comparison): $K^1_S(q, v) = \langle v, Z_{HS}(q) \rangle$.
   • Here, $H$ is a random rotation matrix, and $Z_{HS}(q)$ is the projection vector in the rotated set $HS$ closest to $q$.
2. $K^2_S(q, v)$ (for Thresholding): $K^2_S(q, v) = \langle Hq, Z_S(Hv) \rangle / A_S(Hv)$.
   • This incorporates the reference angle information $A_S(\cdot)$ (the inner product with the reference vector) to normalize the estimation, allowing for precise thresholding.

C. Configuration of Projection Vectors ($S$)

To minimize the reference angle, the authors propose two specific structures for the set $S$ (replacing random Gaussian vectors):

1. Antipodal Projections ($S_{sym}$): Generates points on the sphere in pairs of antipodal points. This ensures symmetry and allows for faster computation (halving the evaluation time).
2. Multiple Cross-Polytopes ($S_{pol}$): Constructs $S$ using rotated cross-polytopes (generalized octahedrons). Since the vertices of a cross-polytope provide the optimal covering for $m=2d$, rotating and combining multiple such structures creates a highly efficient covering of the sphere, minimizing the worst-case reference angle.

D. Applications

• $KS_1$: A projection technique based on $K^1_S$ to improve CEOs for Maximum Inner Product Search (MIPS).
• $KS_2$ Test: A new probabilistic routing test for similarity graphs (like HNSW). It replaces the PEOs test, using the inequality derived from $K^2_S$ to skip exact distance calculations for neighbors that are unlikely to be the nearest neighbor.

3. Key Contributions

1. Theoretical Advancement: The paper provides non-asymptotic theoretical guarantees. Unlike previous works requiring $m \to \infty$, the proposed kernel functions satisfy probability guarantees for finite $m$ based on a deterministic relationship between the reference angle and the projection value (Lemma 4.2 and 4.3).
2. Optimal Projection Structures: The authors demonstrate that Gaussian distributions are suboptimal for projection vectors. They propose $S_{sym}$ and $S_{pol}$, which achieve smaller reference angles and higher estimation accuracy.
3. New Routing Test ($KS_2$): A simplified, more accurate routing test for graph-based ANNS that requires fewer stored constants than PEOs, leading to smaller index sizes.
4. Comprehensive Analysis: The paper establishes the relationship between the number of levels ($L$) in the product-quantization-like structure and the reference angle, showing that increasing $L$ significantly improves accuracy.

4. Experimental Results

The authors evaluated their methods on six high-dimensional real-world datasets (Word, GloVe, SIFT, Tiny, GIST).

• Comparison with CEOs ($KS_1$ vs. CEOs):

  • $KS_1$ achieved a slight but consistent improvement in recall rates (up to 0.8%) over standard CEOs across various datasets and probe settings.
  • The $S_{pol}$ configuration generally outperformed $S_{sym}$, validating the benefit of cross-polytope structures.

• ANNS Performance ($HNSW + KS_2$):

  • Throughput: $HNSW + KS_2$ achieved 2.5× to 3× higher Query-Per-Second (QPS) compared to the standard HNSW.
  • State-of-the-Art Comparison: It outperformed the previous best graph-based approach, HNSW+PEOs, by 10% to 30% in QPS while maintaining or improving recall.
  • Index Size: The $KS_2$ test required fewer stored scalars than PEOs, resulting in a 5% reduction in index size.
  • Robustness: The method showed superior performance across different recall levels, particularly in the 0.75–0.85 recall range where routing efficiency is critical.

5. Significance

This paper makes a significant contribution to the field of high-dimensional similarity search by:

• Bridging Theory and Practice: It resolves the theoretical limitation of existing random projection methods (dependence on $m \to \infty$) by introducing a deterministic, reference-angle-based framework.
• Optimizing Graph Search: By providing a faster and more accurate routing test ($KS_2$), it significantly accelerates the most popular class of ANNS algorithms (HNSW), making large-scale vector search more efficient without sacrificing accuracy.
• Redefining Projection Strategies: It challenges the long-standing reliance on Gaussian distributions for projection vectors, proving that structured, geometrically optimized sets (like cross-polytopes) yield superior results for angle testing tasks.

In summary, the proposed Probabilistic Kernel Functions offer a theoretically sound and practically superior alternative to existing random projection techniques, delivering substantial speedups in real-world similarity search applications.