# Adaptive kNN graph model

arXiv: https://arxiv.org/abs/2601.16509 · HTML: https://mlsanity.com/paper/2601.16509/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 44 references that are in the map.
- First posted on arXiv 23 Jan 2026.

## Builds on (most cited first, 6 of 6)

- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Test-Time Training on Nearest Neighbors for Large Language Models](https://mlsanity.com/paper/2305.18466/) (2023)
- [Why do Nearest Neighbor Language Models Work?](https://mlsanity.com/paper/2301.02828/) (2023)
- [KNN Classification with One-step Computation](https://mlsanity.com/paper/2012.06047/) (2020)
- [Reachable Distance Function for KNN Classification](https://mlsanity.com/paper/2103.09704/) (2021)
- [PALM: A Dataset and Baseline for Learning Multi-subject Hand Prior](https://mlsanity.com/paper/2511.05403/) (2025)

## Abstract (arXiv)

The k-nearest neighbors (kNN) 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). 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 inherent inference bottleneck of kNN, laying an adaptive structural foundation for graph-based nonparametric learning.