PyNNDescent builds a neighbour graph and searches it in pure Python

The algorithm and the two additions

PyNNDescent provides a Python implementation of nearest neighbor descent for k-neighbour graph construction and approximate nearest neighbor search, following the paper by Dong, Wei, Charikar and Li titled Efficient k-nearest neighbor graph construction for generic similarity measures, from the 20th international conference on the World Wide Web. The library supplements that approach with two additions that are worth separating out. The first is the use of random projection trees for initialisation, which the documentation says can be particularly useful for the metrics that are amenable to such approaches, naming euclidean, minkowski, angular and cosine. The second is graph diversification, which prunes the longest edges of any triangles in the graph. The effect of that second step is to break up the clusters that a purely local descent tends to form, and it is the difference between a graph that is locally accurate and one that is globally navigable.

High accuracy is the stated target

The documentation is direct about what this library is aiming at. It currently targets relatively high accuracy approximate nearest neighbor searches, with an accuracy rate of 80% to 100%. That range is the important design choice, because approximate nearest neighbour libraries differ enormously in where they sit on the curve between speed and accuracy, and a library that gives you near-exact answers is much slower than one that gives you 90% recall. PyNNDescent sits at the accurate end, and the reason is visible in the dependency list, where numba at 0.55 or newer and llvmlite at 0.38 or newer are hard requirements. The hot loops are compiled, which is what makes a pure Python package able to compete with the C and C++ libraries in the ann-benchmarks system, which the README cites as putting it solidly in the mix of top performing ANN libraries with results shown for the SIFT-128 Euclidean and NYTimes-256 Angular datasets.

The metric list is the reason to use it

The most practical section of the README is the list of supported distance metrics, because a nearest neighbour library that only does euclidean is not much use. The Minkowski style family covers euclidean, manhattan, chebyshev and minkowski. The miscellaneous spatial family adds canberra, braycurtis and haversine, the last of which is the one you want for geographic coordinates. The normalised spatial family is mahalanobis, wminkowski and seuclidean. The angular and correlation family is cosine, dot, correlation, spearmanr, tsss and true_angular, and the probability family is hellinger and wasserstein. For binary data there is hamming, jaccard, dice, russelrao, kulsinski, rogerstanimoto, sokalmichener, sokalsneath and yule. Custom user defined distance metrics are also supported while still retaining performance. That breadth is the practical difference between this and a general purpose ANN library, since choosing a metric that matches your data is usually the first thing you have to do anyway.

Two operations and not much else

The interface is deliberately small. Building a search index on training data is one call:

from pynndescent import NNDescent
index = NNDescent(data)

and querying it is the other:

index.query(query_data, k=15)

The documentation says that is pretty much all there is to it, and that the index can be pickled to disk if you wish. The comparison the README makes is with KDTrees and BallTrees in scikit-learn, where it says the interface is similar but more limited, and in practice there are only two operations, index construction and querying an index for nearest neighbors. That is a deliberate narrowness. A library that also did clustering, or dimensionality reduction, or a different graph type, would have a bigger API surface and a harder upgrade path, and for a search structure the two operations are the whole contract.

It drops into scikit-learn

The integration point with the wider Python stack is the scikit-learn transformer. PyNNDescent integrates well with scikit-learn, including providing support for the KNeighborTransformer as a drop in replacement for algorithms that make use of nearest neighbor computations. That is the feature that turns a standalone search structure into a pipeline component, since a transformer that computes nearest neighbours can be dropped into a pipeline or a cross validation loop where the exact index would be too slow.

Installing is a conda or a pip line

PyNNDescent is designed to be easy to install, being a pure Python module with relatively light requirements. The listed requirements are numpy, scipy at 1.0 or newer, scikit-learn at 0.18 or newer, numba at 0.55 or newer and joblib at 0.11 or newer, all of which should be pip or conda installable. The documentation says the easiest way is via conda:

conda install -c conda-forge pynndescent

or via pip:

pip install pynndescent

There is also a manual route for a machine without either, which is to download the master archive, unzip it, and pip install from the directory. The README makes a point of the install experience, saying the library is easy to install with no platform or compilation issues. That claim is a real differentiator in the ANN space, where a competing library that needs a compiler and a BLAS is a common reason a project ends up with a different dependency story. The pyproject file confirms the same dependency set, with scikit-learn, scipy, numba, llvmlite and joblib.

An alpha package with a slow release rhythm

The project is honest about its status in more than one place. The package metadata marks the development status as 3 - Alpha, and the help section says the project is still young and the documentation is still growing, pointing to the docstrings for parameter descriptions in the meantime. The version numbers and release dates show a slow rhythm, with release-0.6.0 published on 2026-01-08, release-0.5.13 on 2024-06-17 and release-0.5.12 on 2024-03-29, and the last push to the repository on 2026-10-19, so the code is being worked on between releases. The classifiers cover Python 3.10 through 3.14 and the usual operating systems, and the licence is 2-clause BSD. The build is a standard setuptools project with a pyproject file, a setup.py that has been reduced to a compatibility stub because all the metadata now lives in the pyproject, and a requirements.txt for the same dependency set. The continuous integration runs on Azure Pipelines, and the documentation is built with Read the Docs.

Editorial conclusion

PyNNDescent fits a data scientist who needs approximate nearest neighbour search over a metric that the tree based indexes do not cover, since a non-euclidean metric is the usual reason to leave KDTrees and BallTrees behind, and the package handles that case without leaving Python. It does not fit a problem where exact results are required, since it is an approximate method targeting high accuracy rather than exactness, and it does not fit a deployment that cannot install numba. Before you adopt it, read the metric list and confirm your distance is in it, since the supported families are enumerated and a custom metric is a last resort, and check the version you pin, where 0.6.0 was released on 2026-01-08 while the last push was on 2026-10-19 and the package metadata still marks the project as alpha.

Frequently asked questions

Official sources

1. Issues
2. License: BSD-2-Clause
3. lmcinnes/pynndescent on GitHub
4. README
5. Releases