k k NN-Graph: An adaptive graph model for k k -nearest neighbors

Jiaye Li, Gang Chen, Hang Xu, Shichao Zhang · 2026

Read k k NN-Graph: An adaptive graph model for k k -nearest neighbors by Jiaye Li, Gang Chen, Hang Xu, Shichao Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-16509.txt.

Introduction

Jiaye Li and three coauthors build a graph that adapts for near mate search. Their 2026 preprint deals with the k near mate rule. That rule is a base tool for sorts in AI work. Big sets make its use slow, due to the cost of far counts. Each new point can need counts to all past points.

An adapt graph holds near links in a form that updates fast. New points join the graph with just a few link checks. Fast joins cut the cost of sorts on big data. The team tests the graph on large sort tasks. The work seeks near mate speed at big scale.

Catalog record

CREATORJiaye Li, Gang Chen, Hang Xu, Shichao Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE54 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-16509

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

k k NN-Graph: An adaptive graph model for k k -nearest neighbors Jiaye Li, Gang Chen, Hang Xu, Shichao Zhang Abstract The k k -nearest neighbors ( k k NN) algorithm is a cornerstone of non-parametric classification in artificial intelligence, yet its deployment in large-scale applications is persistently constrained by the computational trade-off between inference speed and accuracy. Existing approximate nearest neighbor solutions accelerate retrieval but often degrade classification precision and lack adaptability in selecting the optimal neighborhood size ( k k ). Here, we present an adaptive graph model that decouples inference latency from computational complexity. By integrating a Hierarchical Navigable Small World (HNSW) graph with a pre-computed voting mechanism, our framework completely transfers the computational burden of neighbor selection and weighting to the training phase. Within this topological structure, higher graph layers enable rapid navigation, while lower layers encode precise, node-specific decision boundaries with adaptive neighbor counts. Benchmarking against eight state-of-the-art baselines across six diverse datasets, we demonstrate that this architecture significantly accelerates inference speeds, achieving real-time performance, without compromising classification accuracy. These findings offer a scalable, robust solution to the long-standing inference bottleneck of k k NN, establishing a new structural paradigm for graph-based nonparametric learning. keywords k NN, artificial intelligence, inference 1 Introduction The k -Nearest Neighbors ( k NN) algorithm, a foundational non-parametric method, is a cornerstone of modern artificial intelligence 9566737 . Beyond its traditional role in classification and regression, the neighbor matching principle underpins advanced computational paradigms, including memory-augmented networks hardttest , attention mechanisms in large language models xu2023nearest , and the construction of graph neural networks zhang2018novel . Its strong interpretability and robustness have ensured its pervasive application across critical sectors, such as precision medicine, financial risk assessment, and personalized recommendation systems, underscoring k NN’s sustained theoretical importance and practical utility su2025utility ; souza2025cardiac ; 10366842 ; zhang2025knn . Despite its ubiquity, large-scale deployment of k NN is fundamentally constrained by an inherent and persistent computational trade-off between inference speed and classification accuracy . During the inference phase, every query requires searching the entire training dataset to identify the k nearest data points. This exhaustive search leads to computational complexity that scales linearly with the dataset size ( O(n) ), rendering the algorithm prohibitively slow for real-time applications involving massive and high-dimensional data. Efforts to mitigate this computational bottleneck have historically bifurcated into two distinct research streams, yet neither has successfully reconciled the conflict between efficiency and accuracy. The first stream concentrates on model refinement , specifically through the optimization of k -value selection and distance weighting strategies to bolster classification performance zhang2018novel ; accikkar2024improved ; 9802923 ; ccetin2025new ; zhang2020cost . While these adaptive approaches effectively enhance decision robustness, they remain fundamentally orthogonal to the issue of latency. By focusing solely on optimizing the decision logic after neighbors are retrieved, they fail to alleviate the underlying O(n) computational burden of the search process itself. Conversely, the second stream prioritizes search acceleration via indexing structures, ranging from deterministic tree-based methods ( e.g., KD-Tree) to Approximate Nearest Neighbor (ANN) algorithms such as Locality-Sensitive Hashing (LSH), Product Quantization, and graph-based indexing. However, these solutions incur critical trade-offs. Tree-based exact methods suffer from the “curse of dimensionality” and exponentially increasing retrieval times as the required k grows. Meanwhile, ANN-based approaches, though faster, achieve speed by sacrificing retrieval precision. This introduces approximation errors that inevitably degrade the final classification accuracy and robustness. Consequently, developing a unified framework that achieves high-speed inference without compromising the exactness of k NN classification remains an elusive scientific challenge. A promising intermediate strategy, exemplified by k *tree 7898482 and its variants 9269360 , attempted to pre-determine optimal k values and localize the search space. Yet, these methods still require costly real-time distance measurement and neighbor retrieval within localized nodes during inference. They primarily reduce the search space complexity, but fail to eliminate the need for on-the-fly neighbor computation, thus falling short of fundamentally addressing the inference bottleneck. Figure 1: Schematic illustration of the Adaptive Graph Model for k NN. a Traditional k NN relies on a fixed k and performs computationally expensive search and voting at runtime. b During the training phase, the proposed method adaptively learns the optimal neighborhood structure for each sample (adjusting k to local density) and embeds a precomputed consensus label directly into each node. c During inference, a query utilizes a Hierarchical Navigable Small World (HNSW) structure to rapidly navigate to the nearest precomputed node and instantly retrieve its stored label, achieving logarithmic-time classification without real-time voting. Here, we propose an adaptive graph model for k NN ( k NN-Graph) that fundamentally resolves the efficiency-accuracy trade-off by completely decoupling inference latency from computational complexity. Our central concept is to shift the entire computational burden of neighbor finding and voting aggregation from the expensive inference phase to the robust training phase. The proposed framework leverages two novel integrated components: First, Adaptive Neighborhood Learning , where we utilize a kernel-based self-representation model with an \ell_{1} -norm sparsity constraint to jointly learn the optimal neighbor count ( k_{i}^{\text{opt}} ) and the corresponding weighted neighbor set for every training sample i . This data-driven approach fundamentally overcomes the limitations of fixed or globally defined k values. Second, Hierarchical Navigable Small World (HNSW) Indexing , where the learned optimal neighborhood and decision information is encoded directly into a HNSW graph structure. In this topological index, higher layers provide efficient, logarithmic-time navigation paths to the relevant region, while lower layers serve as a repository, storing the precomputed classification decision labels and weights. During inference, a test query merely traverses the highly efficient HNSW graph to locate the nearest encoded node and directly retrieves the precomputed classification result. This design achieves highly efficient logarithmic-time classification by bypassing exhaustive distance computations and eliminating the overhead of real-time neighbor voting. A schematic illustration of the proposed adaptive graph model for k NN is shown in Fig. 1 . Our source code is publicly available for reproducibility/future research. 1 1 1 https://github.com/Lijy207/kNN-Graph The core contributions of this paper are summarized as follows: • A Novel Structural Paradigm: We introduce the k NN-Graph, an adaptive graph model that redefines k NN computation by transferring the entire inference workload to a pre-computation phase, establishing a new structural paradigm for non-parametric learning. • Adaptive k and Neighborhood Joint Learning: We develop a kernel-based self-representation model that automatically and jointly infers the optimal neighbor set and k value for each sample, maximizing classification performance. • Logarithmic-Time Inference: By embedding precomputed optimal neighbors and weighted voting results into a hierarchical HNSW graph index, our method achieves near-instantaneous, logarithmic-time classification ( O(\log n) ) during inference, fundamentally addressing the long-standing O(n) complexity problem. To validate the robustness and scalability of our framework, we conducted extensive experiments on six diverse public datasets, benchmarking against eight state-of-the-art baselines. The empirical results demonstrate that the proposed method achieves superior scalability, establishing a new efficiency benchmark with the lowest recorded inference latency across all datasets. Notably, our method delivers a substantial acceleration even compared to the most recent sparse optimization algorithms. Crucially, this gain in efficiency is achieved without compromising performance; our method maintains, and in many cases surpasses, the classification accuracy of existing solutions. Collectively,

Read the complete text