To the best of our knowledge, this work is the first successful attempt to employ a VP-tree with the learned pruning algorithm in non-metric spaces. We focus on approximate nearest neighbor (NN) retrieval methods and experiment with two simple yet effective learning-to-prune approaches: density estimation through sampling and “stretching” of the triangle inequality. Both methods are evaluated using data sets with a metric (the Euclidean) and a non-metric (the KL-divergence) distance functions. The VP-tree with a learned pruner is compared against the recently proposed state-of-the art approaches: the bbtree, the multi-probe locality sensitive hashing (LSH), and permutation methods. Our method was competitive against state-of-the art methods and outperformed them in most cases by a wide margin. Our experiments also showed that the bbtree (an exact search method) was typically slower than exhaustive searching, if the KL-divergence was evaluated efficiently (through precomputing logarithms at index time). Conditions on spaces where the VP-tree is applicable are discussed.