Probabilistic Kernel Function for Fast Angle Testing
Authors: Kejing Lu
Chuan Xiao
Yoshiharu Ishikawa
Venue: ICLR 2026 Oral (2026)
Keywords: Randomized algorithm
Locality Sensitive Hashing
Directional statistics
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We propose two probabilistic kernel functions for angle testing, which can be used to accelerate vector-based similarity search.

Abstract: In this paper, we study the angle testing problem in the context of similarity search in high-dimensional Euclidean spaces and propose two projection-based probabilistic kernel functions, one designed for angle comparison and the other for angle thresholding. Unlike existing approaches that rely on random projection vectors drawn from Gaussian distributions, our approach leverages reference angles and adopts a deterministic structure for the projection vectors. Notably, our kernel functions do not require asymptotic assumptions, such as the number of projection vectors tending to infinity, and can be theoretically and experimentally shown to outperform Gaussian-distribution-based kernel functions. We apply the proposed kernel function to Approximate Nearest Neighbor Search (ANNS) and demonstrate that our approach achieves a 2.5x--3x higher query-per-second (QPS) throughput compared to the widely-used graph-based search algorithm HNSW. Our code and data are available at https://github.com/KejingLu-810/KS.

Published as a conference paper at ICLR 2026
PROBABILISTIC KERNEL FUNCTION FOR FAST ANGLE TESTING
Kejing Lu', Chuan 2., and Yoshiharu Ishikawa"
Yamanashi University, k. r.r.kkyymmaasshii..... .ac. ip
OOska University, chuanx istt osa.a-u.ac. Nagoya University, ishikawaei www.eewwwiinggaauu.a.a. nagoyauu.as. jP
ABSTRACT
In this paper, study the angle testing problem in the context of similarity search in nigh-dimensional Euclidean spaces and propose two projection-basee based probabilistic kernel functions, one designed for angle comparison and the other for angle thresh- olding. Unlike existing approaches that rely on random projection vectors drawn from Gaussian distributions, our approach leverages reference angles and adopts a deterministic structure for the projection vectors. Notably, our kernel functions do not require asymptotic assumptions, such as the number of projection vectors tending to infinity, and can be theoretically and experimentally shown to outperform coussian-distriuutee
kernel functions. We apply the proposed kernel func- tion to Approximate Nearest Neighbor Search (ANNS) and demonstrate that our approach achieves a 2.5x-3x higher query-per-secome (QPS) throughput compared to the widely-used graph- search algorithm HNSW. Our code and data are ctw. http://ttwa..ooooe/enngeoo/ 810/KS
available at
INTRODUCTION
Vector-based similarity search is core problem with broad applications in machine learning, data mining, and information retrieval. It involves retrieving data points in a high-dimensional space that are most similar to a given query vector based on specific similarity measure. This task is central to many downstream applications, including nearest neighbor classification, recommendation systems, clustering, anomaly detection, and retrieval- -augmentee generation (RAG). However, the high dimensionality of modern datasets makes efficient similarity search particularly challenging, highlighting the need for fast and scalable vector computation techniques.
Among the various similarity measures for high-dimensional vectors, the l, norm, cosine similarity, and inner product are the most commonly used in practice. As discussed in Yan et al. (20T8)) Dai et al.) (2020): [u et al. 2024), is often possible to pre-compute and store the norms of vectors in advance, allowing these measures to be reduced to the computation of the cosine of the angle between two normalized vectors, thereby highlighting the central role of angle computation. On the other hand, in many real-world scenarios, we are not concerned with the exact values of the angles but rather with the outcome- which one is greater of angle comparison, which is referred to angle testing: Given query vector and data vectors U1, U2, on the sphere gd-1, typical operations include comparing (q, 01) and (q, 02), determining whether (q. v) exceeds certain threshold. These operations, however, require computing exact cosines of angles, which has a cost of ((d) per comparison and becomes expensive in high dimensions. To address this, we aim to design a computationally efficient probabilistic kernel function K that can approximate these comparisons with reduced cost and high success probability. More precisely, we focus on the following two problems:
Problem 1.1. (Probabilistic kernel function for comparison) ) Design a probabilistic kernel function K: Sd-1 x gd-1 RV with computational cost (d), where RV denotes the set of random variables, such that, for any data vectors U1, U2 E Sd-1 and query q E Sd-1 satisfying {g, v1) > {q, U2), we 0.5.
have Pr|K( (q, v1) > K (q, U2)] > 1 e, where Problem 1.2. (Probabilistic kernelfunction for thresholding Given a axixed angle threshold O E (0, T). design a probabilistic kernel function K; gd-1 x 8d-1 - RV with computational cost of df) such that

---

Published as a conference paper at ICLR 2026
for any q. U1. U2 E sd-1 with angles Φ1 < 0 between q and vi, and 02 8 between and v2 have Pr[K(q. v1) > cos 8| 2 1 11-66 61. and Pr|K (q. v2. > cos 0| < 6g where 61, E2 I 0.5.
One of the main goals of this paper is to design appropriate K's to solve the above two problems. Before proceeding, we note that much work has focused on the estimation of (q, v), such as Johnson- Lindenstrauss (JL.) bound (Johnson al. 1984) and quantization-basee techniques (Jégou et al. [001]]
Ge al. 2014, Martinez et al.) 2018 Gao & Long, 2024; Guo et al. 2020). In contrast, the defined problems focus on comparing (g. v) with another inner product a threshold, necessitating a distinct
theoretical analysis centered on probabilistic decision-making Beyond the theoretical perspective, these two problems also give rise range of practical applications. The goal of Problem 1.1 aligns with that of the maudom-projectiinn
based technique CEOs (Pham) (02T) under cosine similanity (we postpone the general case of inner product to Sec. (). allowing the designed kernel function to be applied to tasks where CEOs is effective, such Maximum Inner Product Search (MIPS) (Pham 202I), filtering of NN candidates (Pham & Liu 2022). DBSCAN (Xu & Pham 2024). and more. Notably, the goal of Problem 1.2 jis similar to that of the graph-based ANNS approach PEOs (Lu et al., 2024), making the corresponding kernel function well suited for probabilistic routing tests in similarity graphs, which have demonstrated significant performance improvements over baseline graphs such as
HNSW (Malkov & Yashunin (020). In Sec. 6 we will further elaborate on the applications of these two probabilistic kernel functions.
Despite addressing different tasks, all the techniques (Pham 2021
Pham & Liu 2022 Xu & Pham
2024| Lu al.] 2024) mentioned above use Gaussian distribution to generate projection vectors and built upon a common statistical result, as follows.
Lemma 1.3. (Theorem I in in ( Given two vectors v, q on sd-1, and m random vectors {u: 1 ~ (0, Id), lel Umax = arginax un !q uil. As m goes to infinity, we huve:
v
Umax
N (sgn(qq T Umaxx qTov uo 1nm, 1 v)))
Lemma 1.3 builds the relationship between angles and corresponding projection vectors. Actually, Mmmxx can be viewed as an indicator of the cosine of the angle between q and v.. More specifically, the larger 2² mmax is, the more likely is that q' v is large. On the other hand, all e "u," 's can be computed beforehand during the indexing phase and v Umax can be easily accessed during the query phase, making K (q. v) = v Umax a suitable kernel function for various angle testing problems, e.g..
Problem 1.
However, Lemma 1.3 has a significant theoretical limitation: Relationship ( relies on the assumption that the number of projection vectors m tends to infinity. Since the computational cost of evaluating projection vectors grows with m. m cannot be very large in practice. Moreover, since Pham & Liu (2022) y Xu & Pham 2024)) Lu et al. (2024) all used Lemma 1.3 to derive their theoretical results, these results are also affected by this limitation, and the impact of m becomes even harder to predict in these applications.
The starting point of our research is to overcome this limitation, and we make the following two key observations. (1) The Gaussian distribution used in Lemma 1.3 is not essential. Instead, the only factor determining the estimation accuracy of q v is the reference angle, that is, the angle between q and Umax (2) By introducing a random rotation matrix, the reference angle becomes dependent on the structure of the projection vectors and is predictable.
Based on these two observations, we design new probabilistic kernel functions to solve Problems and The contributions of this paper are summarized as follows.
(1) The proposed kernel functions K} and K3 (Eq. 2 and Eq. (3) rely on a reference-and wawpnnee-agge-a-aaee probabilistic relationship between angles in digh-dimensioonl spaces and projected values. Compared with Eq. ( the new relationship (Relationship (4) deterministic without dependence on asymptotic condition. By theoretical analysis, we show that the proposed kernel functions are effective solvers for
the Problems [.] and 1.2
(see Lemmas 4.3 and 5.1)
(2) By Lemmas
4.3 we find that, the smaller the reference angle is, the more accurate the kernel functions are. To minimize the reference angle, we study the structure of the configuration of projection vectors (Sec.5)). We propose
structures (Alg. and Alg, (2) that perform better than purely random projection (Alg. 3 in Appendix). We establish the relationship between the reference angle and the proposed structures (Lemma B.T and Fig. 5 Appendix).
2

---

Published as a conference paper at ICLR 2026
(3) Based on K we propose a random- -orilooo-rrooctiionnn technique KS1 which can be used for CEOs-base'
tasks (Pham 2021 1 Pham & Liu 2022 Xu & Pham 2024). Based on K3, we introduce a new routing
test called the KS2 test which can be used to accelerate the graph-based Approximate Nearest Neighbor
Search (ANNS) Lu at
2024) (Sec. 6).
(4) We experimentally show that KS1 provides a slight accuracy improvement (up 0.8%) over CEOs. For ANNS, we show that HNSW+KS2 improves the query-per-second (QPS) by 2.5x - 3x over HNSW and by 10% 30% over the state-of-the-art approach HNSW+PEOs (Lu et 2024), ) along
with 5% reduction in index size.
2 RELATED WORK
Due to space limitations, we focus on random projection techniques that are closely related to this work. An illustration comparing the proposed random projection technique with others be found in Sec. C22 and Fig. qin Appendix. Since the proposed kernel function is also used in similarity graphs for ANNS, a comprchensive discussion of ANÑS solutions is provided in Appendix CC3
In nigh-dimensional Euclidean spaces, the estimation of angles via random-projection techniques, especially Locality Sensitive Hashing (LSH) (Indyk & Motwani 1998 Andoni & Indyk 2005) 2008).
has relatively long history. A classical LSH technique is SimHash Charikar] 2002)) whose basic idea to generate multiple hyperplanes and partition the original space into many cells such that two vectors falling into the same cell are likely to have a small angle between them. (Andoni et al. (2015) proposed a different I.SH method called Falconn for angular distance, whose basic idea is to find the closest or furthest projection vector to the data vector and record this projection vector hash value, leading to better search performance than SimHash. Later, |hhm (20II) employed Concomitants of Extreme Order Statistics (CEOs) to identify the projection with the largest or smallest inner product with the data vector, as shown in Lemma 1.3] and recorded the corresponding maximum or minimum projected value obtain more accurate estimation than using hash value alone (Pham & Liu 2022).
Due to its ease of implementation, CEOs has been employed in several similarity search tasks (Pham) 2021 Andoni et al. 2015) Xu & Pham 2024). as mentioned in Sec. Additionally, CEOs has been used to accelcrate similarity graphs, which are among the leading structures for Approximate Nearest Neighbor Search (ANNS). By swapping the roles query and data vectors in CEOs, Lu al. (2024) introduced a space- paneccppaiiioninng technique and proposed the PEOs test, which can be used to compare the objective angle with fixed threshold under probabilistic guarantees. This test was incorporated into the routing mechanisms of similarity graphs and achieved significant search performance improvements over original graph structures like HNSW (Malkov & Yashunin 2020) and NSSG (Fu et al. 2022).
TWO PROBABILISTIC KERNEL FUNCTIONS
In Sec. we aim to propose probabilistic kernel functions for Problems I.I and 1.2 First, we introduce some notation. Frequently used symbols in this paper are listed in Table in Appendix. Let i be the ambient vector space. Define H E (O(d) C Rddde as a random rotation matrix, where (O(d) denotes the special orthogonal group of d x d rotation matrices)) Let S [U1, U2..... Um] E dx m be an arbitrary fixed set of m points on the unit sphere gd-1 For any vector u E Sa-i define the reference vector of with respect S as Z (v) = argmax.es (u, v). Let As(v) denote the inner product with the reference vector with respect to v, that is, As(D) = (v, Zz(v)). Let HS = denote the rotated configuration of S. Next, we introduce two probabilistic kernel functions (::)) and K3 as follows, where ()(.,)) corresponds to Problem 1.1 and K3(-,)) corresponds to Problem
= {Hu: u E 5}
(g v) = (v, ZHs(g)) K3 v) (Hq, Z. (HH)) (H)(
v. E S
(2)
u.gest
Remarks. (1) (Exploitation of reference angle) In the design of existing projection techniques such as CEOs (Pham 2021), Falconn (Andoni al. 2015), Falconn++ (Pham & Liu| 2022). etc., only the reference vector Zs(-) is utilized. In contrast, our kernel functions defined in Eq. ( and Eq.
Nooe that the definition here differs from that in Andoni et al. 2015), where the so-called random rotation matrix actually matrix with i.i.d. Gaussian entries.
3

---

Published as a conference paper at ICLR 2026
incorporate not only the reference vector Z-) but also the reference angle information As(+) (although the reference angle is not explicitly shown in Eq. (2). its influence will become clear in Lemma(4.2). In fact, the reference angle plays central role, is the key factor controlling the precision of angle estimation (see Lemma(4.2).
(2) (Generalizations of existing works) These two kernel functions can also be regarded gener- alizations of CEOs and PEOs respectively in a certain sense. Specifically, if S is taken as a point set generated via a Gaussian distribution and (1) is replaced by the reference vector having the maximum inner product with the query, then K 8 g, v) equals the indicator v Umax used in CEOs. structure as that of PEOs, ( (g. v) is similar to the indicator of PEOs. In addition, Eq. (3) reduces to the estimator in Gao& & Long 2024) when S is taken be the hypercube with scalar quantization.
Similarly, we remove the term As(Hv) v) and take S to be the same ppace-partitionns
(3) (Configuration of projection vectors) Although we do not currently require any specific properties of the configuration of S, is clear that the configuration of impacts both K (g(q. v) and K (q. v). We will discuss the structure of S in detail in Sec.5) Notably, we will see that neither the hypercube adopted Gao & Long (2024) nor the Gaussian distribution adopted in Pham (2021) [u al. (0244) provides the optimal configuration for projection vectors.
ANALYSIS OF PROBABILITY GUARANTEES
In Sec. we show that the proposed probabilistic kernel functions K3S and K3 satisfy the probability guarantees of Problem I.I and Problem 1.2
respectively. Before proceeding, we first provide
definition that will be used to establish property of K3.
Definition 4.1.
Let Φ1, 02 E (0, and let 0 e (0, T) be an arbitrary angle threshold. probabilistic kernel function K(g, 2) is called angle-sensitive when it satisfies the following two conditions:
If 8 S cos Φ1 {q, v). then PP| [[K (q. v) 2 cos A| 2 p0()).
(2) (q. v) = cos Φ2 < cos then [g, v) 2 cos c < P2(22).
where p2(02) a strictly decreasing function in 22 and p1 (Φ1) p2( when Φ1 62.
The definition of the angle-sensitive property is analogous to that of the pcclity-sensstivv hashing property. The key difference is that the approximation ratio used in LSH is not introduced here, as the angle threshold is explicitly defined, and only angles smaller than @ are considered valid.
We are now ready to present the following two lemmas for K3S and K3, which demonstrate that they serve as effective solutions Problems) 1.1 and 1.2
respectively.
Lemma 4.2. Let 2 3 and (q, be arbitrary pair of normalized vectors with angle & (0, m). The conditional CDF of Kg(q, v) can be expressed as follows:
d 2 d
F FK3(G,,)) As(g) = cos xb) T,
(4)
2
where vi E (0, t = 1 + #-cos di cos
2sin sin a 1, denotes the regularized incomplete Beta function and E [cos( + v), (o (b ]-]
(2) Let q. 01 and u2 be three normalized vectors on $d-1 such that (g. v2) > (g. v22). The probability (
P[K] (q, 01) Kg(g 22
(q) cos Vi increases vú decreases in (0, T). In particular, when
E (0, n 7/2). P[K (g, U1
> (g(g. v2) As(q) = cos b/ > 0.5, that is, K} satisfies the probability
guarantee in Problem
1.I
Lemma 4.3. Let v/ E (0, 22)). that is, As(v) = cos v (0, 1), and d > 3. Then K3 is an angle- sensitive function. Precisely, K3 satisfies the probability guarantee in Problem 1.2 where E = 0.5
and E2 = Iv d-2 d-2
2 < 0.5, where t' =
cos 0 cos d
2 sin tan
Remarks. (1) (Discussion on boundary values) When o = 0 o = n, K3 and K3 take fixed values rather than being random variables, and when v = 0 v obtained. Therefore, probability analysis in these cases is meaningless. Additionally, in Lemma 4.3
the exact value of (q. v) can be directly
adopt the following convention: p2 p2()) Of t' < 0.
4

---

Published as a conference paper at ICLR 2026
Algorithm 1 Configuration of S via antipodal projections
Input: L is the level; dl = La' is the data dimension; mn the number of vectors each level Output: S.g (m, L). which is represented by mL sub-vectors with dimension d'. for porl= 1 to L do
Generate 2 points i..d. on ons" s
along with their antipodal counterparts Scale the norm of all m points in this iteration to 1 1/vL, and collect the vectors after scaling
(2) (Deterministic relationship for angle testing) Lemma 4.2 establishes relationship between the objective angle & and the value of the function K3. Notably, after computing Zs(+), the value of reference angle A-(.) can be obtained automatically. Besides, as will be shown in Sec. [ with reasonable choice S, the assumption As(+) > 0 can always be ensured. Hence, Eq. (4) essentially describes deterministic relationship. In contrast to the asymptotic relationship of CEOs, Eq. provides an exact relationship without additional assumptions.
(3) (Effectiveness of kernel functions) The above two lemmas show that, with reasonable construc- tion of S such that the reference angle is small with a high probability, K3 and K3 can effectively address the corresponding angle testing problems. The smaller the reference angle is, the more effective K3 and K3 become.
(4) (Gaussian distribution suboptimal) The fact that a smaller reference angle is favorable justifies the utilization of (s(.) and also implies that the Gaussian distribution is not an optimal choice for configuring S, since in this case, the selected reference vector with the largest inner product with the query or data vector is not guaranteed to have the smallest reference angle.
5 IMPLEMENTATION AND COMPLEXITY ANALYSIS
We discuss how to configure S, and then analyze the complexity of K3 and K3. Based on the discussion in Sec.[4] we observe that small reference angles are preferred. Thus, given m, our goal is to construct set S of m points on gd-1 denoted by Sm, such that As.. (-) is maximized. Due to the effect of the random rotation matrix !I, the optimal configurations denoted by S. and S can be obtained either in the sense of expectation or in the sense of the worst case, respectively:
S m
argmax
{E ((Ett(8--)(As(s)))
(5)
S=(1 Mem CCB4-
S
arg max
min wES
max (u,, v),
(6)
S= S= (ug CC
Isi5m
where U(S--11) denotes the uniform distribution on the sphere. By the definitions of S. and S", they correspond to the configurations that achieve the largest expected value and the largest worst-case value of As(w), respectively. On the other hand, finding the exact solutions for 5m and S closely related to the best covering problem, which is highly challenging and remains open in the general case. To the best of the authors' knowledge, the optimal configuration S is only known when configurations of St one relies
m + 3 (Borodachov et al., al.) 2019). In light of this, we provide on random antipodal projections (Alg. T). and the other is built using multiple poostppol (A (Alg. (2) Each has its own advantages. Alg. I eenables the estimation of reference angles, while Alg. 2 can empirically produce slightly smaller reference angles and is more efficient for projection computation.
Before proceeding into the details of algorithms, introduce quantity (SS) as follows.
J(S)- Beeuggr-y((s((i]]
By definition, J(S) denotes the expected value of As(v) w.r.t. S (which equals the cosine of the reference angle when v E Sd-1). This quantity is consistent with our theory, as a random rotation applied to v or q in Eg. 2 and Eq. (3). Based on the previous discussion, for fixed m, J(S) is maximized when S = Sm. which is hard to compute. Thus, we take N to be sufficiently large and let UI.N,..., UN be vectors drawn independently and uniformly from USS-))). Let JiSS, N) = D (//, By the law of large numbers, can approximate J(S) by J(S, N) when N is sufficiently large.
Now, we ready to explain Alg. Tand Alg. 2 as follows.
5

---

Published as a conference paper at ICLR 2026
Algorithm 2 Configuration of S via multiple cross-polytope
Input: L is the level; d = Ld'' is the data dimension; m = 2d' + b; R the maximum number of iterations Output: Spa (m, L). which is represented by mL sub-vectors with dimension d'
Generate N points randomly and independently on ad' where N is a sufficiently large number
for = 1 to R do
for t to a do
Generate a random rotation matrix H E R" xd" and rotate 2d' axes in RR" using H Collect the 2d' vectors of the pross-po after rotation
b 0 then
1 Repeat the above itcration and select 6/2 antipodal pairs from the rotated cross cross- polytope
For the generated sd" compute J(S, N) and keep the configuration with the largest value, denoted by
Smix
for [ == to Lo do
Generate a random rotation matrix H/ E xd''
xa' and rotate the configuration Smax using H
10
11
Scale the norm m points this iteration 1/vT. and collect the vectors after scaling
(1) (Utilization of antipodal pairs and cross-polytopes) We use the antipodal pair or the cross- polytope as our building block for the following three reasons. (i) Since all the projection vectors are antipodal pairs, the evaluation time of projection vectors can be halved. (ii) Both two structures can ensure that the assumption As(v) 0 holds, such that the condition in Lemma 4.3 jis always satisfied. (iii) The result in Borodachov (2022) shows that, for m = 2d, under mild conditions, the 2d vertices of cross-polytope can be proven have the smallest covering radius, that is, the smallest reference angle in the worst case. Although the results in the case m. > 2d are unknown, we can rotate the fixed cross-polytope in random directions to generate multiple prossppooysspes until we obtain m vectors, which explains the steps from to 7 in Alg. 2
(2) (Selection from random configurations) We can generate such m points in the above way many times, which forms multiple S's. By the discussion above, we can use J(S, N) approximately evaluate the performance of (S), and thus, among the generated S's, we select the configuration Spol corresponding to the maximal J(S, N). This explains steps 2 and 8 in Alg. 2
(3) (Accuracy boosting via multiple levels) Increasing m can lead to smaller reference angle. The analysis in Lu al. (2024) shows that, for certain angle- thee-thhessolding problems requiring high accuracy, an exponential increase in m, rather than a linear one, can be effective. Therefore, similar to to et al.] (2024), we use product-quantizztiin-- like technique (Jégou al., 2011) to partition the original space into L subspaces (levels), which is adopted in Algs. from these L subspaces, we can virtually generate m normalized projected vectors. As will be shown in Lemma B.I the introduction of L can significantly decrease the reference angle, and L can also control the trade-off between query accuracy and efficiency.
By concatenating equal-length sub-vectors
(4) (Fast projection computation via ceatti-croos--olytopee In Eq. and Eq. we need to compute H Su the indexing phase. If the projection time is a concern practice, we can use the Fast Johnson-Lindenstraus transformation to accelerate this process. Specifically, we use Alg 2 with R When = 1, the cost of computing HSv is (max(dd (d, m) log d). When 1, the cost of computing H Sv can be reduced to Od d + mL log dd L)).
By Alg. I and Alg. 2 we obtain structures Ssym (m, L) and Spo L) virtually containing m projection vectors. For Ssym(m, T.). we can actually establish deterministic relationship be- tween J(SSym(m, I)) and (m, I.) (see Lemma B. in Appendix). On the other hand, in practice, (m, L)) is often slightly larger than J (S (m, L)). will be shown in Table
With Sym (m, L) and (mo,m,, L). we are ready to present a complexity analysis of the two proposed functions, showing that they satisfy the complexity requirement in Problem [.] and Problem 1.2
Lemma 5.1. In the indexing phase, for fixed dataset D size the complexities of K3S and K3
are (nmdd and O (nd d + nmd), respectively. In the query phase, K2 requires ((md)- time for random projection, and for each spends Od d + md) time for random projection and random rotation, and for each u E D, it spends (T.)-mime for computing K3 K2 v), where I, & d. Particularly, i Spa(m, L.) with R =1,
D. it spends O(1)-time for computing K3(g, v). while K2

---

Published as a conference paper at ICLR 2026
the complexities of K's and K'3 in the indexing phase can be reduced (mmxx(d m) log d) and O Ond d + nmL log(d/ L)), respectively, where m greater than d L by user-speciffcation.
APPLICATIONS TO SIMILARITY SEARCH
6.1 IMPROVEMENT CEOS-BASER TECHNIQUES
As for Kg. we can use it to improve CEOs, which is used for MIPS and further applied to accelerate LSH-based ANNS (Andoni al. 2015) and DBSCAN (Xu & Pham 2024). Since CEOs was originally designed for inner products, we generalize K} to Kÿ as follows to align with CEOs:
(8) is easy to see that, with two minor modifications, that is, replacing v gd-1 with E Rd and replacing x with || | in Eq. 4 4.2 holds. Therefore, K3. can be regarded as a reasonable kernel function for inner products. Then, we can apply Ky to the algorithm in Pham (202)) Pham & 2022): (022)) & Pham 2024). We only need to make the following modification. In these algorithms, the random Gaussian matrix, which denotes the set of projection vectors, can be replaced by S or Spol. with the other parts unchanged. This substitution does not change the complexity of the original algorithms. To distinguish this projection technique based on K from CEOs, we refer to it as KS1 (see Alg. for the projection structure of KS1). In the experiments,
KY qq. v) || (v, (H))
E Sd-1
will demonstrate that KS1 yields slight improvement recall rates over CROs, owing to a smaller reference angle.
6.2 A NEW PROBABILISTIC TEST IN SIMILARITY GRAPH
2024) proposed probabilistic routing and used in similarity graphs to accelerate ANNS. Let disl(.,-) be the distance function for ANNS. Each node in the similarity graph represents a data vector. The definition of probabilistic routing is as follows.
Lu et al.
Definition 6.1 (Probabilistic Routing (Lu et al. (0244)). Given a query vector node in the graph, an error bound c, and distance threshold ö, for an arbitrary neighbor w of such that dist w. q) 8, if a routing algorithm returns true for w with probability of at least 1 - e, then the algorithm is deemed to (6, e -routing.
Lu et al. (2024) proposed (6, eo-rttning test called PEOs test. Based on K3. we propose a new routing test for la distance, called the KS2 test, as follows (see Sec. C.I and Fig. 3in Appendix for more details).
L qi T w/( 2 As(e) [
| 11/2
Σ
(9)
|||||
E IRd is the query, v is the visited graph node, w is the neighbor of v, and e w v. r is the threshold determined by the result list of graph search. qi, e; denote the i-th sub-vectors of and e, respectively (1 < i < L). un denotes the j-th sub-vector of the i-th subspace of u. u²(a denotes the reference vector of e, among all ( $ S m). In our experiments, was set to 5256, L).
During the traversal of the similarity graph, we check the exact distance from graph node to only when Ineq. (9) satisfied; otherwise, we skip the computation of w for efficiency. complete graph-based algorithm equipped with the KS2 test can be found in Alg. 7 By Lemma 4.3 and the same analysis in Lu et al. (0024), we can easily obtain the following result.
Corollary 6.2. The praph-based search equipped with the KS2 test 9 is (6, -routig test.
Comparison with PEOs. Since PEOs also uses a Gaussian distribution to generate projection vectors in subspaces, CEOs does, and does not make use of the reference- angle information, the estimation in Ineq. (9) is more accurate than that of the PEOs test. In addition, the proposed test has two advantages: (1) Ineq. 9 is much simpler than the testing inequality in the PEOs test, resulting in higher evaluation efficiency: (2) Ineq. (9) requires fewer constants to be stored, leading to a smaller index size compared to that of PEOs.
Complexity analysis. For the time complexity, for every edge e, the computation the LHS of Ineq. (9) requires J. lookups in the table and L. additions, while the computation of the RHS of
7

---

Published as a conference paper at ICLR 2026
Table 1: Comparison of recall rates (%) for k-MIPS, 10. The number of projection vectors is
2048. Top-5 projection vectors are probed. Probe @ means top-n points were probed on each probed projection vector. Results are averaged over 10 runs to reduce the bias introduced by random projection.
Dataset Method
Probe I0
Probe 100
Probe IK
Probe IOK
CEOs(2048)
34.106
71,471
90.203
98.182
Word
KSI (2048, 1))
34.167
71.679
90.265
98.195
KSI pol (2048, 1))
34.395
72.078
90.678
98.404
CEOs(2048)
1.773
6.920
24.166
63.545
GM
KSI(S (2048, 1))
1.792
7.015
24.456
64.041
KSI (2048, 1))
1.808
7.071
24.556
64.355
(204x)048)
2.070
6,904
21.082
54,916
GloVe2M
KSI smm (2048, 1))
2.064
6.928
21.182
55.240
KSI (2048, 1))
1.996
6.979
21.262
55,394
Ineq. (9) requires two additions and one multiplication. By using SIMD, we can perform the KS2 test for 16 edges simultaneously. For the space complexity, for each edge, need store L bytes to recover qi "a[[a)- along with two scalars, that is, As(e) w|l tolll((21)) /2]|e]]) and As(e)/|le||, which are quantized using scalar quantization to enable fast computation of the RHS of Incq. (9)
EXPERIMENTS
All experiments were conducted on PC equipped with an Intel(R) (eon(R) Gold 6258R CPU @ 2. 70GHz. KSI and KS2 were implemented in C++. The ANNS experiments used 64 threads for indexing and single CPU thread for searching. We evaluated our methods on six high-dimensional real-world datasets: Word, GloVe1M, GloVe2M, Tiny, GIST, and SIFT. Detailed statistics for these More experimental results can be found in Appendix D
datasets are provided in Appendix D.1
7.1 COMPARISON WITH CEOS
As demonstrated in Sec. 6.1 1 the results of CEOs are directly used to accelerate other similarity search processes (Pham & Liu 2022: Xu & Pham 2024). In this context, we focus solely on the improvement of CEOs itself. We show that KS1, equipped with the structures Symmm, 1) and (mo, (m, 1), can slightly outperform CFOs(m) on the original task of CEOs, that is, k-MIPS, where denotes the number of projection vectors and was set to 2048, following the standard configuration of the original CEOs. Since the only difference among the compared approaches is the configuration of the projection vectors, we use a unified algorithm (see construction of projection structure Alg. and MIPS query processing input compare their recall rates. From the results in Table. [ we observe that: (1) in most cases, KSI with the two proposed structures achieves slightly better performance than CEOs, supporting claim that smaller reference angle yields a more accurate estimation, and (2) Spel generally achieves higher recall rate than S verifying that a configuration closer to the best covering yields better performance. Since the gain of KSI over CEOs originates from only one difference, that is, the distribution of the generated projected vectors (Gaussian vs. more diverse distribution on the unit sphere), this result supports our claim that the Gaussian distribution is suboptimal.
Alg. 6 in Appendix) with the configuration of projection vectors
7.2 ANNS PERFORMANCE
We chose ScaNN (Guo et al., 2020). HNSW MMakovv & Yashunin, 2020 and HNSW+PEOs LLu
et al. (024)) as baselines, where ScaNN is a of art quantization- based approach that performs better than IVFPQFS, and HNSW (Lu et al. 2024) is a -fate-of-the-att graph-based approach that outperforms FINGER (Chen et al. 2023) and Glass Zilliz 2023). Like HNSW+PEOs KS2 is implemented on HNSW, dubbed HNS W+KS2. DiskANN (Subramanya et al. 2019)) is excluded because it is orthogonal to KS2 and focuses on optimization for external storage. ADSampling (Gao & Long 2023) excluded because it is designed for a non- SOM- environment. The parameter settings of all compared approaches and additional experimental results can be found in Appendix
8

---

Published as a conference paper at ICLR 2026
14000
5000
7000
12000
5000
14TA
6000
10000
4000
8000
3000
9
4000
6000
3000
4000
2000
2000
1000
1000
0.75
0.50
0.85
0.90
0.95 1.00
0.70
0.75
0.80
0.85
0.90 0.95
0.70
0.75
0.50
0.85 0.90
0.95
Rocali@10
Recali@10
Recall@10
(a) STFT-
(b) GloVe M-angular
(c) Word-E2
10000
10000
5000
HEDA FSin-02
8000
8000
4000
6000
6000
3000
4000
4000
2000
2000
2000
1000
0
0.75
0.80
0.85
0.90
0.95
1.00
0.85 0.70 0.
0.80 0.85 0.90 0.95
1.00
0.3
0.7
0.9
1.0
Recalla10
Recal 1010
Recall@10
(d) Glo
(e) Tiny-L2
(1) GIST-
Figure I: Recall-QPS evaluation of ANNS. k= 10.
(1) Index size and indexing time. Regarding indexing time, after constructing the HNSW graph, we require additional 42s, 164s, 165s, 188s, 366s, and 508s to align the edges and build the KS2 testing structure on Word, VeMM. GIST, Ge2M, SIFT, and Tiny, respectively. This overhead is less than 25% of the graph construction time. In practice, users can reduce the parameter efc to shorten indexing time while still preserving the superior search performance of HNSW*KS2. As for the index size, it largely depends on the parameter L, which will be discussed later.
(2) Query performance. From the results in Fig. we make the following observations. (i) Except for Word, HNSW*KS2 achieves the best performance among all compared methods. In particular, HNSW*KS2 accelerates HNSW by a factor of 2.5 to 3, and is 1.1 to 1.3 times faster than HNSW+PEON demonstrating the superiority of KS2 over PEOs. (ii) Compared with ScaNN, the advantage of HNSW+KS2 is especially evident in the recall region below 85%, highlighting the effectiveness of the routing test. On the other hand, in the high-recall region for Word, ScaNN outperforms HNSW+KS2 due to the connectivity issues of HNSW.
(3) Impact of L. The only tunable parameter KS2 L. Generally speaking, the larger L is, the larger the index size is. On the other hand, larger L can lead to a smaller reference angle and yield better search performance. Hence, L can be used to achieve different trade-offs between index size and search performance. In Fig. 2 we show the impact of L on index size and search performance. From the results, we have the following observations.
(i) The index size of HNSW is slightly smaller than that of MINSW+PEO due to the storage of fewer scalars. (ii) When d' = d/ L is around 16, HNSW+KS2 achieves the best search performance. This is because a larger L also leads to longer testing time and d' 16 is sufficient to obtain a small enough reference angle.
CONCLUSIONS
In this paper, we studied two angle-testing problems in high-dimensional Euclidean spaces: angle comparison and angle thresholding. To address these problems, we proposed two probabilistic kernel functions that are based on reference angles and are easy to implement. To minimize the reference angle, we further investigated the structure of the projection vectors and established relationship between the expected value of the reference angle and the proposed projection vector structure. Based on these two functions, we introduced the KS1 projection and the KS2 test. In the experiments, showed that KS1 achieves a slight accuracy improvement over CEOs, and that HNSW+KS2 delivers better search performance than the existing state-of-the-art ANNS approaches.

---

Published as a conference paper at ICLR 2026
Additiona Cost())
1.40
50
Additional Costri)
-5
100
Additionaal
30
20
15
80
20
10
HESA-185
EETA-ES
40
8
10
14
16
12
16
20
24
28
12
20
28
(a) SIFT-&2
(b) Word-L2
(c) GIST-F2
16000
8000
7000
12000
5000
4000
8000
4000
6 3000
3000
4000
1000
2000
1000
2000
0.70 0.75 0.80 0.05
1.00
0.70
0.75
0.50
0.85
0.30
0.3
0.7
Recall@11
Recall@10
Recall@10
(d) SIFT-
(e) Word-f2
GIST-42
Figure 2: Impact of I. (See Appendix| D.4 for other datasets). k= 10. The y-axis of the upper figures denotes the additional index cost (%) of +POS compared to the original HNSW.
ACKNOWLEDGEMENTS
This work is supported by JSPS Kakenhi JP22H03594, JP23K17456, JP23K55157, JP23K28096, JP25H01117, JP25K2122,, and JST CREST JPMJCR22M2.
REFERENCES
Alexandr Andoni and Daniel Beaglehole. Learning hash robustly, guaranteed. In /CML, pp. pp. 599-618.
2022.
Alexandr Andoni and Piotr Indyk. E2lsh manual. http::/weeb.l...eb//nooo/// 2005.
LSH
Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM, 51(1):117-12 2008.
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, and Ludwig Schmidt. Practical and optimal LSH for angular distance. NeurlPS, pp. 1225- 1233, 2015.
Artem Babenko and Victor S. Lempitsky. Efficient indexing of billion-scale datasets of deep descriptors. In CVPR, pp. 2055-2063, 2016.
Dmitry Baranchuk, Dmitry Persiyanov, Anton Sinitsin, and Artem Babenko. Learning to route in similarity graphs. In ICML, pp. 475-484, 2019.
Sergiy Borodachov. Optimal antipodal configuration of 2d points on a sphere in rd for coverings. In arxiv, 2022.
Sergiy V. Borodachov, Douglas P. Hardin, and Edward B. Saff. Discrete Energy on Rectifiable Sets. Springer Monographs in Mathematics. Springer, 2019.
Moses Charikar. Similarity estimation techniques from rounding algorithms. In John H. Reif (ed.),
STOC, pp. 380-388, ACM, 2002.
Patrick H. Chen, Wei-Cheng Chang, Jyun- Yu Jiang, Hsiang- Fu Yu, Inderjit S. Dhillon, and Cho-Jui Hsich. FINGER: fast inference for graph-based approximate nearest neighbor search. In WWW, pp. 3225-3238 ACM, 2023.
Ryan R. Curtin, Parikshit Ram, and Alexander G. Gray. Fast exact max max-kernel search. Staristical Analysis and Data Mining, 7(1):19,, Srrnaary-December 2014.
10

---

Published as a conference paper at ICLR 2026
Xinyan Dai, Xiao Yan, Kelvin Kai Wing Ng. Jiu Liu, and James Cheng. Norm-explicit quantization: Improving vector quantization for maximum inner product search. In pp. 51-58, 2020.
Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading out graph. PVLDB, 12(5):461 474, 2019.
Cong Fu, Changxu Wang, and Deng Cai. High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility. IEEE Trans. Pattern Anal. Mach. Intell., 44(8):4133 4150, 2022.
Jianyang Gao and Cheng Long. High-dimensionn approximate nearest neighbor search: with reliable and efficient distance comparison operations. Proc. ACM Manag. Data, 102:137:11133:27,2000
Jianyang Gao and Cheng Long. Rabitq: Quantizing high- nigh-dimensional vectors with a theoretical error bound for approximate nearest neighbor search. Proc. ACM Manag. Data, 2(3):167, 2024.
Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization. IEEE Trans.
Pattern Anal. Mach. Intell, (664)):744755,2244
Yutong Gou, Jianyang Gao, Yuexuan Xu, and Cheng Long. Symphonygg: Towards symphonious integration quantization and graph for approximate nearest neighbor search. Pruc. ACM Manag. Data, 3(1):80:1-80:26 2025.
Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Accelerating large-scale inference with anisotropic vector quantization. In ICML, pp. 3887-3896, 2020.
Gaurav Gupta, Tharun Medini, Anshumali Shrivastava, and Alexander J. Smola. BLISS: A billion scale index using iterative re-partitioning. In KDD, pp. 486-495. ACM, 2022.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In STOC, pp. 604-613, 1998.
William B Johnson, Joram Lindenstrauss, et al. Extensions of lipschitz mappings into hilbert space. Contemporary mathematics, 26(199206))1)))) 1984.
Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell, 33(1):117-128, 2011.
Yifan Lei, Qiang Huang, Mohan Kankanhalli, and Anthony Tung. Sublinear time nearest neighbor search over generalized weighted space. In ICMI, pp. 3773-3781, 2019.
Wuchao Li, Chao Feng, Defu Lian, Yuxin Xie, Haifeng Liu, Yong Ge, and Enhong Chen. Learning balanced tree indexes for large-scale vector retrieval. In KDD, pp. 1353-1362. ACM, 2023.
Kejing Lu, Chuan Xiao, and Yoshiharu Ishikawa. Probabilistic routing for graph-based approximate nearest neighbor search. In ICML, pp. 33177-33195, 2024.
Yury A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Trans. Pattern Anal. Mach. Intell, 42(4):824 836, 2020.
Julieta Martinez, Shobhit Zakhmi, Holger H. Hoos, and James J. Little. Lsq++: Lower running time and higher recall in multi nolti-codebook quantization. In ECCV, pp. 1008,22,2200 2018.
Javier Alvaro Vargas Muñoz, Marcos André Gonçalves, Zanoni Dias, and Ricardo da Silva Torres. Hierarchical clustering- based graphs for large scale approximate nearest neighbor search. Pattern Recognit., 96, 2019.
Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang. and Jianliang Xu. Efficient approximate nearest neighbor search in multi-dimensional databases. Proc. ACM Manag. Data, 1(1):54:1-544 2023.
Ninh Pham. Simple yet efficient algorithms for maximum inner product search via extreme order statistics. In KDD, pp. 1339-1347,220 2021.
11

---

Published as a conference paper at ICLR 2026
Ninh Pham and Tao Liu. Falconn++: A locality-sensitie filtering approach for approximate nearest neighbor search. In NeurlPS, pp. 51186-31198 31198, 2022.
Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnaswamy, and Rohan Kadekodi. Rand-nsg: Fast accurate billion-point nearest neighbor search single node. In NeurIPS, pp. 13748-13758, 2019.
Jiadong Xie, Jeffrey Xu Yu, and Yingfan Liu. Graph based k-nearest neighbor search revisited. ACM Trans. Database Syst., 50(4):14:1-144:: 2025.
Haochuan Xu and Ninh Pham. Scalable DBSCAN with random projections. In NewrlPS, 2024.
Xiaoliang Xu, Mengzhao Wang, Yuxiang Wang, and Dingeheng Ma. Two-stage routing with optimized guided search and greedy algorithm proximity graph. Knowl. Based Syst, 229:107305, 2021.
Xiao Yan, Jinfeng Li, Xinyan Dai, Hongzhi Chen, and James Cheng. Norm-ranging LSH for maximum inner product search. In NeurIPS, pp.
2018.
Mingyu Yang, Wentao Li, Jiabao Jin, Xiaoyao Zhong, Xiangyu Wang, Zhitao Shen, Wei Jia, and Wei Wang. Effective and general distance computation for approximate nearest neighbor search. In ICDE, pp. (099-11100 2025.
Zilliz. Graph library for approximate similarity search. httpps://githbb.com// / pyglass 2023.
12

---

Published as a conference paper at ICLR 2026
A
NOTATIONS
2 lists the main notations used in this paper.
Table 2: Frequently used notations.
Notation
Explanation
Dataset
n
Size of Dataset
d
Data dimension
Data vector in D
gd-1
d - dimensional sphere
q
Query
The number of projection vectors Error rate
6
S
Fixed set of points gd-1
И
Random rotation matrix
Zs(v)
argmax, uss (u, v)
As(u)
(v, (u)
L
The number of space partitions
Edge in similarity graph
Neighbor vector connected by edge e
||e||
Length edge
7
Threshold determined by the result list of graph search i-th sub-vectors of (1 I i S L), e. respectively
qi.
j-th sub-vector the subspace u, where 1 S S and S S m Reference vector of e; among all (u))'s & S m)
B PROOF OF LEMMAS
B. PROOF LEMMA 4.2
Proof: (1) For the first statement, due to the existence of random rotation matrix H/ and symmetry, only need to prove the following claim:
Claim: Let and be two vectors on gd-1 such that the angle between & and is d. Let C be spherical cross-sections defined as follows.
C = {u E gd-1; (u, q) = cos v
(10)
If u is vector randomly drawn from C, the CDF (v, u) is 1e - ا22) wheret _
-ocos d cos ei 2si @
Proof of Claim: Without loss of generality, we can rotate the coordinate system so that
01, ,0) Rd
(11)
Then, by the definition of u, u can be written as follows
u (cos v sin vi w)
(12)
where w E Sd-2 1 is unit vector in the subspace orthogonal to q. Similarly, v can be expressed as follows.
(cos Φ, sin Φ 17)
(13)
where n gd-2 is fixed and corresponds the projection of a onto the orthogonal subspace of q- Then (v, u) can he written as follows.
X = (v, u) cos &i cos v + sin dsin W
(14)
where W (w, m)) is random variable. A well-known fact says that W is related to the Beta distribution as follows.
W +1
d 2
T
Beta
(15)
2
2
13

---

Published as a conference paper at ICLR 2026
Therefore, have
cos cos 1o
S Fx(x) 2 P( S 2 sin Φ sin eb
(16)
Thus, = where t = +
I cas cos
(2) For the second statement, due to the existence of random rotation matrix H and symmetry, we only need prove the following claim.
Claim: Given three normalized vectors v1, and q, let (g. #1) be larger than (g. 02) Let C' be the spherical cross-section defined the proof of statement 1, and u be normalized vector drawn randomly from C. As & decreases, (u, 01) > (u,, 02)] increases.
Proof of Claim: For cos v q + sin 1b w', where w' a random normalized vector, taking u's inner products with and v2, we obtain:
(U1, u) = cos vp (11, ②) + sin a (01,w").
(17)
(U2, u) = cos v (02, ? + sin v (02 w').
(18)
Then, have
PlKu. v1) > (u, 22)l + P[ w² (02, w²) Ag cot ub]
(19)
where A, = (v2, 9) - (u1. q) < 0 and the threshold Ag cot v is naturally set to when e = π 7/2. As s decreases, cot ih increases, making Ag cot v smaller. Since (vi, w²) (v2, w²) is random variable due to the existence of w', the probability that it exceeds a given threshold increases as the threshold decreases. Thus. as z decreases, the probability that the above inequality holds increases.
B.2 PROOF LEMMA
We consider the following four cases based on the value of (g, v).
Case 1: 0 < (g. v) <.
Let be random vector drawn randomly from spherical cross-section C' defined as follows.
C' {u sd-1; (u, cos v
(20)
Next, we construct a simplex with vertices O, A, B, C as follows. We use O to denote vector v, where O denotes the origin. Then we can build a unique hyperplane H' through point A and perpendicular v. We extend and u along their respective directions to OB and OC such that B and C' are on H' Then, only need to prove the following claim.
Claim: Let O, A, B, C be four points in IRd. OA is perpendicular AB, and O is perpendicular to AC. The angle between O. and OC's is vh, and the angle between OA and O is c. If the angle between AB and AC is a, then cos where denotes the angle between OB and OC, can be expressed as follows.
cos cos Φ cos & + sin @ y cos a.
(21)
This claim can be easily proved by elementary transformations. Since AB is fixed and AC follows the uniform distribution of sphere in dd cos a and cos 3 are random variables. Therefore, we have the following equalities.
P(K3(q,)) 2 cos f| = PP(cos 3 2 cos 1 cos vb]
cos 0 cos d = PP(cos a 2 sin ø tan vp
(22)
We further consider the following two cases.
Case 1': cos & 2 cos 0.
Pg 2 cos P|cos 2 0] = 1/2.
(23)
Case 2": cos e cos O.
14

---

Published as a conference paper at ICLR 2026
Algorithm 3 Configuration of S via random projection
Input: L is the level; d La'' the data dimension; m the number of vectors each level Output: Sum (m, L). which is physically represented by mL sub-vectors with dimension d' for lorl= 1 to L do
Generate ma points randomly and independently on sd'-1
Scale the norm of all m points in this iteration to 1/v L and collect the vectors after scaling
By the properties of Beta distribution discussed in the proof of Lemmal 4.2 and the property of symmetry of incomplete regularized Beta function, we have
- 2 d -
I P[K3((q v) 2 cos Ie
(24)
2
@- where L' 1/2 siin & tan s F (, v) 2 cos 0] is increasing in vb On the other hand, is easy to see that P[ v) 2 cos strictly decreasing
Moreover, since tan strictly increasing in & when & (0, 2)
when (0, Hence, Lemma 4.3in Case is proved.
Case 2: (q, v) = 0.
In this case, without loss of generality, define q, v follows.
(0, 1, .0) E8
(25)
v = (1, 0, ,0) E
(26)
u = (cos ub, sin 3 w) sd-1
w U(S
(27)
Therefore, we have
P P v) 2 cos 0 Plcos a cos 0 tan vp]
(28)
which is consistent with - 2 in Case 1. The following analysis similar to that in Case 1.
Case 3: -1 < () < 0.
Instead of and u. we consider = and u, and construct the simplex based on q. -1 and u as in Case 1. Then, with the reverse of sign, we finally obtain an equation similar to Eq. (21) except with replaced by π - a. The following analysis is similar to that Case
Case 4: (q, v) = 1 or (g. v) 1.
In this case, (g. u.) = cos v and the conclusion trivial.
B.3 ESTIMATION OF (Saym (m, L))
As discussed in Sec 5 for Ssy (m, L), we can establish a relationship between J J( L)) and (m, L) as follows.
r(4)
Lemma B.1. Suppose that d is divisible by L,, and d = Ld', where d' 2 3. Let Ca
VFT d'
f(w) car " and F(y) 1- dt. We have
(S (m, L)) mVL 1 ((()))
S (F())m--((() dy.
(29)
The RHS of Ineq.
29 actually denotes (SSnn) where San is the configuration of purely random projections (see Alg. for more detail). A numerical computation of the RHS of Ineq. 22 is shown in
Fig. Appendix.
Proof:
First, we introduce an auxiliary algorithm Alg. which relies on purely random projection.
The structure S produced Alg. iis denoted by Smn We then present the following claim.
Claim: J(Symmm L)) > J( (m. L)).
To prove this claim, we introduce the following definition.
15

---

Published as a conference paper at ICLR 2026
Definition B.2. (Stochastic order) Let X and Y be two real-valued random variables. We say that X <st Y, iffor all E R, the CDFs of X and Y satisfy Fx > (t)
Let L 1 and fix m. We use X to denote the random variable As... (v), where is drawn randomly from $d-1, and Y to denote A (v). Clearly, X E [[1,1] and Y [0, 1]. We have the following:
P(Y
> P(X >) t) t (0.1).
(30)
This can be easily proved, since when the angular radius is less than π 7/2, the two spherical caps corresponding to the antipodal pair do not overlap. Therefore, we have X <st Y and R[x] E[Y]
This completes the proof of the claim.
Then we only need to focus on [S L)) and prove that it equal to the RHS of Ineq. 29 Let
= [un, " Un.] E IRd be a vector drawn randomly from gd-1, where is assumed to be divisible by Land d Ld'. L (v) be the subspace-normaalzed vector w.r.t. V. That is,
21
22
r =
(31)
VLle
VL
Let T(d, (w,rz(m)) For every i, let w:/l|uil E sd'-1, Then we select m vectors from gd' randomly and independently. Suppose that, among generated vectors, w is the vector having the smallest angle to ue, and we use (d', m) to denote (w, uz). Since the choice of w for every uy is independent of the value of (d,, L). we have the following result:
[[)s(b)] = (d, L)) x (d', m)]]
(32)
For [E] L)], since (1 || | ...., | 122 follows Dirichlet distribution with parameters (2. d 2T. 2T each || marginally follows Beta distribution with parameters 2L
d(L-1))
2L
Then by the properties of Beta distribution, have
[[T(d, L.] = VT. r (
(33)
((
Next, we consider [d" m)]. Because of the rotational symmetry of the sphere, the distribution of the inner product Z (u, v) (for fixed v and uniformly random u) depends only on the dimension d'. It has the following density on [-1,1]
fz(2) Car (1 - 22) =
=²)=²²
(34)
Let ..,..., Zm be i.i.d. copies of Z (u, v). Then:
Y max 21, Zm)).
(35)
The cumulative distribution function (CDF) of Z is:
Fz(2) (z)
(36)
Thus, the CDF Y Ydd,, (m) is:
Fy(y) = PIY 2 = =F>())",
(37)
and the corresponding density is:
(v = dy
F2) mFZ(y) (02(())m((zz)))) fz(v).
(38)
Therefore, have the following result.
E| / (f m [ FF2())m (z)
(39)
Combining the previous results, we get the following result.
T d+L
(
J(Sran (m,, L)) mvT
21.
yF 1- ()) dy.
(40)
26
16

---

Published as a conference paper at ICLR 2026
R[1]
R[2]
a[efs]
Result List (sice efs)
g
Projected cted
(ist(q.Rle/s))
A,(e))
T(et)
rst,
e.
Output
Yest Calk. Dist
Input
> 0?
Pruned
Dataset
summ
A,(e')
T(ee)
rst,
Projection Table
Figure 3: An illustration of the KS2 test.
h(v) h(q)
u
q
(a) Falconn
(b) CEOs (Falconn++)
(c) KS1 (proposed one)
Figure 4: An illustration of Falconn, CEOs, and the proposed structure KS1.
C SUPPLEMENTARY MATERIALS
C.I EXPLANATION OF ROUTING TEST IN INEQ. 9
According Ineq.
there three core terms II, and III, where I Σí.
qi T
"e Il As(e),
Here, I/II is exactly the kernel function K3; the computation of depends on PQ (Jégou al. 2011) 1.. III denotes the threshold for K3 and is explained in the original paper of PEOs (see the routing test Eq. (9) Lu et al. (2024)).
and III || /2
c
C.2 ILLUSTRATION OF RANDOM PROJECTION TECHNIQUES FOR ANGLE ESTIMATION
An illustration is shown in Fig. In this figure, represents a query and is data vector, For Falconn, q and are mapped to the same vector, they are considered close. For CEOs and KS1, the inner product v u. where u is the projection vector closest to is computed to obtain more accurate estimate q v. The key difference between CEOs and KS1 lies in the structure of the projection vectors. While CEOs uses projection vectors sampled from a Gaussian distribution, KS1 employs more balanced structure which all projection vectors lie the surface of sphere. By applying a random rotation matrix and constructing spherical cross- section centered at q, establish the required statistical relationship between q u and q v.
C.3 ANNS AND SIMILARITY GRAPHS
As one of the most fundamental problems, approximate nearest neighbor search (ANNS) has seen
surge of interest in recent years, leading to the development of numerous approaches across different
paradigms. These include tree-based methods (Curtin al. 2014), hashing-basee methods (Andoni
Indyk 2008 Lei et al. 2019 Andoni Andoni & Beaglehole 2022 Andoni et al. 2015 Pham & 2022).
vector quantization -VQ)-based methods (Jégou et al. [00 |001 1 Ge et al. 2014 Babenko & Lempitsky
2016 Guo et al. 2020). learning based methods (Gupta et al. (2022] Li et al.
beased
2023). and graph-based
methods (Malkov Yashunin, 2020) 2020 Subramanya et al. 2019: et al. 2019 2002
Gao & Long
2023 Peng al. 2023 Xie
2025
Yang et.
2025
17

---

Published as a conference paper at ICLR 2026
Algorithm 4 Graph-based ANNS with routing
Input: Query q. # results K, graph index G
Output: K-NN q
R + an ordered list of of R] S efs
P + { cntry node Up E G //G//aaa priority queue
while P * 0 do
P.pop(): foreach unvisited neighbor of
[R] cfs then oc; clse 4- R.efss] 5 4- dist q): if RRoutingTest(
10
6)= true then :rut
if dist u, q) < ô then
R.push( u); p.uus(uu):
13 return ({ [ R(]
Among these, graph-baser methods are widely regarded as the state-of-the-as Currently, three main types of optimizations are used to enhance their search performance: (1) improved edge-selection strategies, (2) more effective routing techniques, and (3) quantization of raw vectors. These approaches are generally orthogonal to one another. Since PEOs belongs to the second category, we briefly introduce several highly relevant works below. TDGG-KME (Xu et al. (202I) and HCNNG (Muñoz ct al. 2019) use KD-trees to determine the direction of the query and restrict the search to points in that direction. While this estimation is computationally efficient, it results in relatively low query accuracy. limiting their improvements over HNSW (Malkov & Yashumin (2020). FINGER (Chen et al. (2023)
examines all neighbors and estimates their distances to the query. For each node, FINGER locally generates promising projection vectors to define a subspace, then uses collision counting which is
similar to Siml approximate distances within each visited subspace. Leean-to-Route (Baranchuk et al. 2019) learns routing function using auxiliary representations that guide optimal navigation from the starting vertex to the nearest neighbor. Recently, [L et al. (2024) proposed PEOs, which leverages space partitioning and random projection techniques to estimate random variable representing the angle between each neighbor and the query vector. By aggregating projection information from multiple subspaces, PEOs substantially reduces the variance of this estimated distribution, significantly improving query accuracy.
Recently, a related quantization method RaBitQ (Gao & Long 2024 was proposed and used for the accelcration of similarity graphs (Gou et al. 2025). Notably, RaBitQ can be viewed as a special case of KS2: when m and L d, RaBitQ has exactly the same projection structure KS2. On the other hand, Lu et al. (2024) shows that when L is very large, an additional error will increase significantly. Thus, if the tradeoff between index size and search performance is taken into account, choosing d may not be ideal. Meanwhile, when RaBitQ is applied to similarity graphs, the additional overhead to accommodate the index is very large, consuming about 2-4 times the size of the dataset.
C.4 ALGORIHTMM RELATED TO KSI AND KS2
Alg. 1gg.5lam and Alg. 6 are used to compare the probing accuracies of CEOs and KS1, while Alg. 7 presents the graph-based search equipped with the KS2 test. Because Alg. resembles the probabilistic routing mechanism in Lu et (2024). we provide further clarification through Alg.
In Alg. 7 the list R serves as an ordered container of at most efs elements (efs K). Using a graph index G (V, E) constructed over the dataset. ANNS results are obtained by traversing this graph, as summarized in Alg. 7 The search starts from an entry node vo E G and maintains R? which holds the current best candidates, together with a priority queue P that stores nodes yet to be explored. A neighbor of the current node is inserted into the priority queue whenever it is closer q than the farthest element in Rt or whenever Rt has not reached its capacity. Nodes are repeatedly popped from the priority queue to explore their neighbors, and the procedure terminates once the queue becomes empty. In practice, additional optimizations -scch as early stopping or pruning strategies are commonly adopted to further accelerate the process (Malkov & Yashunin| 2022))
straightforward implementation would compute the exact distance between q and every encountered neighbor. However, routing test can be used to decide whether an exact distance evaluation is needed.
18

---

Published as a conference paper at ICLR 2026
Algorithm 5 Construction of the Projection Structure of KSI
Input: is the dataset with cardinality n, and S is configuration m projection vectors (CEOs: m/2 random
Gaussian vectors along with their antipodal vectors; KS1: (my(m, 1) or Sput (m,, 1))
Output: m projection vectors, each of which is associated with a n-sequence of data ID's
For every D (1 i n) and each My S (1 S J S m)) compute (m+4, 2457
For each uj E S, sort 2; in descending order of (æt, uz) and obtain 2/1p' ................................
Algorithm 6 Query Phase for MIPS
Input: y is the query; D the dataset; I is the index structure returned by Alg. denotes the value of top-k; so is the number of scanned top projection vectors; and #probe denotes the number of probed points for cach projection vector
Output: Top-k MIP results of
Among m projection vectors, find the top-8o projection vectors closest to
For each projection vector uy in the top-sp set (1 S S #o). scan the top-#prohe points in the sequence associated with uy and compute the exact inner products of these points with
Maintain and return the top-k points among all scanned candidates
Algorithm 7 Graph-based ANNS with the KS2 test
Input :q is the query, denotes the value top-k, G is the similarity graph
Output :Top-k ANNS results of
R. <- 0:
1s an ordered list of results, |R] S ef's %/
P entry node vo G);
/ priority queue"
while P do
e + P.pop()
foreach unvisited neighbor w of do if [R] < cfs then
else + Rlefs), + "iss(vv,g):
if KS2_Test(ww, v, =) true (Ineq. 9 then
if didist(w w. q) < 5 then
R.push( (w), P. P.push(w)
11 return ({ [R[])..... R
The probabilistic routing technique (Lu al. 2024 is one such example. Meanwhile, the proposed function K3 naturally leads to an alternative routing criterion, given by Ineq. (9). which can also be used to determine whether neighbor should undergo exact distance calculation.
C.5 NUMERICAL COMPUTATION OF REFERENCE ANGLE
Fig. shows the numerical values of the lower bounds (the RHS of Ineq. 29 under different pairs of (m, T.). From the results, we observe that increasing significantly raises the cosine of the reference angle, whereas a linear increase in m leads to only slow growth in the cosine of the reference angle, which explains why we need to introduce parameter L into our projection structure.
D ADDITIONAL EXPERIMENTS
D. DATASETS AND PARAMETER SETTINGS
The statistic of six datasets used in this paper is shown in Tab The parameter settings of all compared methods are shown as follows.
(1) CEOs: The number of projection vectors, m, to 2048, following the standard setting in Pham (202)).
For KSI, was fixed to 1, as multiple levels are not necessary for angle comparison. The number of projection vectors, m, was also set to 2048, consistent with CEOs. We evaluated both KS1 Sym (2048, 1)) and KS1(5 (Smi 1)).
(2) KS1:
19

---

Published as a conference paper at ICLR 2026
Table 3: Dataset statistics.
Dataset
Data Size
Query Size
Dimension
Type
Metric
Word
1,000,000
1,000
300
Text
E &iinnrr product
Glo
1,183,514
10,000
200
Text
angular innner product
GIMM
2,196.017
1,000
300
Text
angular&inne product
SIFT
10,000,000
1,000
128
Image
62
Tiny
5,000,000
1,000
384
Image
f2
GIST
1,000,000
1,000
960
Image
(3) HNSW: M was set to 32. The parameter efc was set to 1000 for SIFT, Tiny, and GIST, and to 2000 for Word, GloVe1M, and GloVe2M.
(4) ScaNN: The Dimensions _arrsspe_______ letss__eeee_eeee____ block was set to 4 for Tiny and GIST, and to 2 for the other datasets.
num leaves set to 2000. The other user-specified parameters were tuned to achieve the best trade-off curves.
(5) HNSW+PEOs: Following the suggestions in Lu 2024), set to 10, 15, 15, 16, and 20 for the six real datasets, sorted in ascending order of dimension. Additionally, e was set to 0.2, and m 256 ensure that each vector ID could be encoded with single byte.
(6) INSW+KS22 S was fixed to Ssym (m, L). The only tunable parameter is L, as m must be fixed at 256 to ensure that each vector ID is encoded with single byte. Since the parameter L in KS2 plays similar role to that in PEOs, we set L to the same value in HNSW+PEOs to eliminate the influence of L the comparison.
D.2 KSI vs. CEOS UNDER DIFFERENT SETTINGS
In Tab. compared the performance of CEOs and KS1 using the top-5 probed projection vectors. Here, we varied the value of su in Alg. 6 5 to and 10, and present the corresponding results in Tab. and Tab. respectively. We observe that (S)())a) still achieves the highest probing accuracy in most cases.
D.3 ANNS RESULTS UNDER DIFFERENT k'
Fig. and Fig. 7 show the comparison results of ANNS solvers under different values of k. When k ScaNN performs very well on Word, VeMM, Ve2M, and Tiny, which is partly due to the connectivity issue of HNSW on these datasets. In the other cases, HNSW achieves the best performance.
D.4 THE IMPACT OF L ON THE OTHER DATASETS
Fig. 8 shows the impact of L on GloVelM, GloVe2M, and Tiny, which is largely consistent with the results Fig. 2
D.S RESULTS OF NSSG+KS2
We also implement KS2 on another state-of-the-art similarity graph, NSSG (Fu et al. 2022 The parameter settings for NSSG are the same as those in Ln al. (2024). From the results in Fig. 9 we observe that NSSG+KS2 outperforms NSSG+PEOs on all datasets except for GIST, which indicates that the superiority KS2 is independent of the underlying graph structure.
STATEMENTS ON THE USE OF LARGE LANGUAGE MODELS
We used LLMss to polish writing only. We are responsible for all the materials presented this work.
20

---

Published as a conference paper at ICLR 2026
Table 4: Comparison of recall rates (%) for k-MIPS, k 10. Top-2 projection vectors are probed.
Dataset & Method
@robe I0
Probe@ 100
Probe 1K
Probe @ IOK
CEOs(2048)
17.255
46.348
68.893
84.366
Word
KSI(S (2048. 1))
17.334
46.740
69.232
84.548
KS1 20448, 1))
17,440
46.843
69.392
85.026
C204)2048)
0.839
3.404
12.694
38,607
GloVe1M
KS1(S sm (2048, 1))
0.849
3.464
12.890
39.109
KS1 (2048, 1))
0.866
3.503
12.916
39.170
CEOs(2048)
0.934
3.407
11.621
34.917
GloVe2M
KSI smm (2048, 1))
0.939
3,451
11.775
35.462
KSI 20488, 1))
0.917
3.401
11.748
35.159
Table 5: Comparison of recall rates (%) for k-MIPS, k= 10. Top-10 projection vectors are probed.
Dataset MeMhhdd
Probe 10
Probe 100
Probe IK
Probe IOK
CEOss
50.772
84.545
96.620
99.882
Word
KSI sym (2048, 1))
50.698
84.470
96.643
99.869
KS1 (2048, 1))
51.238
84.865
96.869
99.910
CEO0s(008)
3.012
11.301
36.293
80.995
GloVeIM
KS (2048, (2048,, 1))
3.047
11,401
36.604
81.307
KS1 pol (2048, 1))
3.069
11.451
36.857
81.781
CEOs(2048)
3.574
11.252
30.695
69.406
GloVe2M
KS KS1 sym (2048, 1))
3.567
11.256
30.741
69.668
KSI pal 20488, 1))
3.515
11.368
30.940
70.016
Reference Ax9le
0.7
0.7
Reference Angle
0.7
0.66
0.6
reference
0.5
0.5
0.5
0.4
0.4
0.3
0.3
10
(a) DDi=128. m 256
(b) Dim=200, m
256
(c) Dim=300, m 256
0.7
0.45
0.6
Seferenc A69
Reference Angle
0.5
0.28
0.4
0.26
0.3
0.25
0.24
0.20
0.2
8
12
16
20
24
28
32
6
12
15
18
21
24
27
30
1000
2000
3000
4000
m
(d) Dim=384,
256
(c) Dim=960,
256
(f) Dim==110 128, T.
Figure 5: Numerical computation under different m's and d's. The y-axis denotes the cosine of reference angle.
21

---

Published as a conference paper at ICLR 2026
4500
4000
2500
4000
EETA-TEN
3500
3000
2000
3000
2500
1500
2000
2000
1500
1000
1000
500
0.90
0.92
0.94
0.96
0.98
0.70
0.75
0.80
0.85
0.90
0.55
0.70
0.75
0.80
0.85
0.90
Recall@100
Recallg 100
Recallg100
(a) SIFT-62
(b) GloVeeMaannullar
(c) Word-
3000
2500
2500
1750
2000
2000
1500
1500
8 1000
1250
750
500
500
250
0.70
0.75
0.50
0.85
0.90
0.85
0.90
0.80
0.95
1.00
Rerali@100
Recall@100
Recal1@100
(d) Glo
(c) Tiny-E2
(f) GIST-12
Figure 6: Recall- MhS evaluation of ANNS. k 100.
POP
20000
6000
EETA M0%
15000
BISA-IC
5000
0
10000
3000
2000
5000
2000
1000
0.6
0.7
0.8
0.9
1.0
0.75
0.30
0.35
0.90
0.95
0.75
0.50
0.85
0.90
0.95
Reca Kg
Recallg1
Recall@1
(a) SIFT-82
(b) VeloVeeM-aggullii
(c) Word-
6000
8000
6000
7000
retn 1th.
5000
6000
4000
5000
3000
3000
2000
3000
2000
1000
2000
1000
1000
1.00
0.80
0.90
0.95
Recallg11
Recall@11
Recallg31
(d) Glo Ve2M-nnnaa
(e) Tiny-Ez
GIST-42
Figure 7: Recall-QPS evaluation of ANNS. k= I.
22

---

Published as a conference paper at ICLR 2026
Ancmoonll Costeg)
120
120
Additional Costr%)
80
90
100
100
60
monal
60
60
40
30
40
20
20
16
12
16
20
24
20
12
16
20
24
28
32
(a) Glo Ve M--anuular
(b) -aanuuaa
(c) Tiny-L2
10000
6000
00L--
5000
4000
Pult 201
6000
60311-00
6000
8000
1ab 1d
3000
4000
4000
1000
2000
2000
0.70
0.75
0.80
0.95
0.70
0.75
0.80
0.90
0.650.00..50.00
0.95 1.00
Recall@10
Recall@
Recall@10
(d) M-
(c) Glo -aaneMaaaa
(f) Tiny-&2
Figure 8: Impact of L index sizes and search performance. k= 10.
7000
7000
10000
5000
5000
8000
0 4000
0 4000
6000
3000
0 3000
4000
2000
1000
1000
0.80
0.65
0.50
0.95
1.00
0.70
0.75
0.80
0.85
0.90
0.95
0.70
0.75
0.60
0.85
0.90
0.35
1e
Recall@10
Recall@110
(a) SIFT-82
(b) Mangular
(c) Word-
3000
9000
2500
K556
8000
7000
4000
1005 0o1
2000
3000
5000
4000
2000
1000
3000
500
2000
1000
1000
0.95
0.85
0.90
0.50
1.00
Recalig10
Recalig10
Recalig 10
(d) Glo Ve2nn-aaaa
(e) Tiny-Ez
GIST-42
Figure 9: Recall-QPS evaluation of ANNS, with NSSG+KS2, A 10.
23


Reviews:
[{"review_id": "dK9Spna0T2", "reviewer": "Reviewer_EhUf", "summary": "The paper reframes angle estimation from stochastic Gaussian projections to deterministic reference-angle-based kernels. Authors first derive theoretical bounds and apply them to accelerating graph-based retrieval. Specifically authors design (what seems to be) a pruning algorithm that eliminates certain search paths. Although the pruning approach is not new in principle, the resulting approach HNSW-KS2 outperforms a previously proposed variant (HNSW-PEO) by 10% – 30%, along with a 5% reduction in index size.", "questions": "**Detailed comments:** \n\n \n\n1. Eq (1) does it really come from Theorem 3.1 in “Pham, Simple yet efficient algorithms for maximum inner product search via extreme order statistics.” It looks very different. \n\n2. Due to its ease of implementation, CEOs has been employed in several similarity search tasks (Pham, 2021; Andoni et al., 2015; Xu & Pham, 2024) -> CEO came after Andoni et al. Do you mean it was used in FALCON++? \n\n3. L354-356 you claim that you skip a distance computation. However, this doesn’t seem to be correct according to Alg 6. I think you also do not add a node to the queues. Basically, this seems to be search pruning approach, not the the approach to reduce the number of distance computations. Please, clarify. \n\n4. L376 Why didn’t you test multi-threaded retrieval as well? \n\n \n\n5. Is L the number of projections? It will be great to clarify in the experimental section. \n\n6. Does Figure 1 compare PEO and KS2 using the same L? \n\n7. Gains over CEO are marginal. For example (see Table 1), Probe@100: 6.98 vs 6.9, which is 1% relative. PEO improves upon reverse CEO and you improve upon PEO by double digits percentage points (e.g., 30%). How can you explain this discrepancy? What makes new kernel functions to be more effective? Is it due to the introduction of the threshold approximation? I think it is an important clarification to add to the paper as well. \n\n8. Thank you for sharing the code: which part of the code benchmarks HNSW-PEO though? I think it benchmarks just HNSW-K1/K2.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Important topic and well motivated-problem \n\n2. Theoretically grounded approach that achieves substantial practical gains. \n\n3. The paper is well-written \n\n4. Source code is provided.", "weaknesses": "1. Gains over HNSW-PEO are relatively modest (yet non-trivial!) and the method requires extra space, which is non-trivial in some cases. For example, it is >= 40% in the case of the SIFT dataset. \n2. Evaluation is only single-threaded.\n\n\n**Detailed comments:** \n\n**Please, do not respond to these, all questions are rhetorical. If suggested correction is not valid, just ignore it** \n\nEq. (2) Shouldn’t Z_{HS} be Z_S? \n\n \nL341 This is not understandable without a basic explanation of what a routing test is. \n\nL410 there is a missing dot after and HNSW+PEOs \n\nL427-428 On the other hand, in the high-recall region for Word, ScaNN outperforms HSNW+KS2 due to the connectivity issues of HNSW. -> This requires justification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0aFnzond6u", "reviewer": "Reviewer_XabQ", "summary": "This paper proposes two projection-based probabilistic kernel functions for fast angle testing in the context of similarity search in high-dimensional Euclidean spaces. Its core observation is that the reference angle can determine the estimation accuracy of angle comparison and testing, which in turn can be determined by the structure of the projection vectors. A detail theoretical analysis is presented to support the effectiveness of the proposed probabilistic kernel functions. Then, algorithms are proposed to compute the projection vectors, together with an analysis of the computational complexity. The proposed probabilistic kernel functions are integrated into high-dimensional similarity search algorithms (Maximum Inner Product Search and Graph-based ANN Search) to enhance their effectiveness and efficiency, which are verified with experiments on six commonly used benchmark vector datasets.", "questions": "There are no further questions.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper studies an important problem - high-dimensional similarity search.\n\n2. Detail theoretical analysis is presented to show the effectiveness and correctness of the proposed probabilistic kernel functions.\n\n3. Experimental results are presented to show the empirical effectiveness of the proposed probabilistic kernel functions and algorithms.\n\n4. Source code has been released.", "weaknesses": "The empirical performance of the proposed kernel functions is not as strong. It produces marginally higher recall than the CEOs technique (Pham, 2021) as shown in Table 1, while HNSW+KS2 is only 1.1 to 1.3 times faster than HNSW+PEOs. Also, why are Tiny, GIST, and SIFT omitted from Table 1?\n\nIt would be good to discuss if the proposed kernel functions are guaranteed to lead to more accurate (and/or more efficient) similarity search than Gaussian-distribution-based kernel functions given the same number of projection vectors. If this is not guaranteed, it would be good to tune down the claim: \"can be both theoretically and experimentally shown to outperform Gaussian-distribution-based kernel functions\".\n\nPresentation issues:\n\n- It would be good to add figures to help illustrate the key concepts and proposed algorithms. \n\n- The statement \"On the other hand, $v^\\top u_{max}$ can be computed beforehand during the indexing phase and can be easily accessed during the query phase\" needs further clarification. How can this value be easily accessed given that $u_{max}$ depends on $q$? \n\n- Typo: \"with i.i.d. Gaussian entries)\" => \"with i.i.d. Gaussian entries.\"; \"and Additional experimental results\" => \"and additional experimental results\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MfpNZ4qZCw", "reviewer": "Reviewer_yHFc", "summary": "The most commonly used metrics in approximate nearest neighbor, i.e. Euclidean distance, cosine similarity, and inner product, can crucially be reduced to just inner product computation with appropriate preprocessing. The paper proposes two probabilistic kernel functions that approximate (1) the comparison of two inner products $\\langle q, v_1\\rangle$ and $\\langle q, v_2\\rangle$ and (2) whether $\\langle q, v\\rangle$ exceeds a given threshold. These approximations are much faster than the corresponding computations, making it possible to significantly accelerate approximate nearest neighbor search algorithms.\n\nThe proposed kernel functions are based on reference angles. Based on these functions, the authors introduce the KS1 test for CEOs tasks such as maximum inner product search and the KS2 test as a routing test in graph-based approximate nearest neighbor search. In the authors' experiments, the KS1 test yields slight improvements, while the KS2 test applied to the HNSW algorithm yields significant improvements.", "questions": "- Could the authors point out where in the provided code release the SIMD implementation of the KS2 test is located? I tried briefly looking in the code but was unable to figure out where in the code it was.\n\n- The integration of KS2 into HNSW moderately increases the index size and indexing time. How do these compare to HNSW+PEOs?\n\n- Have the authors considered testing HNSW+KS2 by integrating it to a standard benchmark such as ANN-benchmarks such that it is easier to reliably compare results?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper proposes an interesting approach, angle testing, which has a central role in approximate nearest neighbor search. The authors propose methods for both angle comparison and thresholding. The provided theory is neat and well-motivated.\n\nThe proposed KS2 test can be generally applied to many different graph-based approximate nearest neighbor methods, and is amenable to an efficient SIMD implementation that yields a significant improvement in throughput when combined with the popular HNSW algorithm. This combination is also more efficient than combining HNSW with the earlier PEOs approach.\n\nThe experiments provided by the authors are comprehensive and use standard benchmark datasets.", "weaknesses": "In practice, the improvement provided by KS1 over CEOs is very minor. The improvement of HNSW+KS2 over the earlier HNSW+PEOs is slightly larger but still relatively small.\n\nThe state-of-the-art methods for approximate nearest neighbor search combine graphs and quantization, e.g. Glass combines graphs with scalar quantization and SymphonyQG [1] combines graphs with RaBitQ, yet these are not included in the comparisons. The authors mention that they do not compare to e.g. Glass as it was deemed less efficient than PEOs in the corresponding paper, but experimental results in the PEOs paper do not seem to align with e.g. the results of ANN-benchmarks [2]. The KS2 test is not applicable to quantized vectors in e.g. uint8 or binary precision which are increasingly popular due to the high dimensionality of modern embedding datasets.\n\nA weakness in presentation is that the numerous references to analysis and explanations in the PEOs paper make it difficult to understand the paper without a thorough reading of the PEOs paper.\n\n[1] Gou et al. SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data. 2025.\n\n[2] Aumüller et al. ANN-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "D58RdTMGfJ", "reviewer": "Reviewer_mXUD", "summary": "This paper tackles the angle testing problem as part of similarity search in high-dimensional Euclidean spaces. The key idea is to depart from conventional random projection methods based on Gaussian distributions, and instead propose probabilistic kernel functions with deterministic structures that leverage reference angles. Unlike prior approaches, the proposed method does not rely on asymptotic assumptions and theoretically and experimentally outperforms Gaussian-based methods. Applied to approximate nearest neighbor search (ANNS), the proposed approach achieves 2.5–3× higher query throughput (QPS) compared to HNSW.", "questions": "My questions about this paper are as follows.\n\n(1) Since the proposed method is based on probabilistic kernel functions, it presumably involves stochastic errors. Is it possible to predict or estimate the error rate analytically?\n\n(2) How does the error rate depend on the projection vector structure? Can this relationship be analyzed theoretically?\n\n(3) How should the number of projection vectors m and the number of subspaces L be optimized? These parameters likely depend on the data distribution, but what practical optimization strategy do the authors envision for real-world applications?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "This paper's strengths are as follows.\n\n(1) The paper presents a theoretically rigorous approach to the angle testing problem without asymptotic assumptions, proposing probabilistic kernel functions with deterministic structures.\n\n(2) By designing appropriate projection vector structures, the method improves estimation accuracy and further demonstrates that Gaussian structures are suboptimal.\n\n(3) The proposed method can be easily integrated into existing algorithms such as HNSW, suggesting strong practical applicability.\n\n(4) Extensive experiments on multiple datasets show that the proposed method achieves both high speed and high accuracy.", "weaknesses": "This paper's weaknesses are as follows.\n\n(1) Constructing the projection vector structures is computationally expensive and could become a bottleneck for extremely large-scale datasets.\n\n(2) Minor typographical issue found: Line 153: “ZS(·))” → “ZS(·)”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)