KNN Implementation Details Can Cost You 7.5x: Cover Trees Show Why Benchmarks Mislead
_reachsumit · x · 2026-10-14
Amol Khanna and Edward Raff (arXiv:2610.16940) built RustKNN, a unified Rust implementation of three Cover Tree construction variants with three query modes, and found implementation details materially change KNN performance:
- Optimal query mode depends on k and dataset: single-tree is fastest at k=1 on 3 of 4 large datasets, dual-tree fastest at k≥5; the wrong choice costs up to 7.5x runtime.
- The common base parameter default of 1.3 is optimal on only 1 of 7 datasets, and 1.6x slower than optimal on covtype.
- Of five micro-optimizations, only early-exit distance computation helps consistently, scaling with dimension (none at d=32, 1.49x at d=784).
- All-NN and held-out benchmarks rank implementations differently, meaning conclusions about algorithmic superiority can hinge on implementation choices.
Timing tables report medians over 20 independent runs.
More from Research
- AIPOCH's Open-Science ships portable .science packages that share full research context, not just outputs — ahuja_priyank · 2026-10-14
- Video-Arena: Game-Based Video Benchmark Shows Native Models Score Just 13.2 F1 — Kuan Zhang · 2026-10-14
- LSCBench: Vibe Coding Agents Write Functional Code, But Only 25% Is Also Secure — Qwen · 2026-10-14
- Omni-LLMs Know More Than They Say: NAVER's OmniCatalyst Adds 7.29% via Self-Generated Text — naver-ai · 2026-10-14
- Repeated-Data Pretraining Study: Smaller Batches Act as Regularizers and Beat More GPUs — Sewon Min · 2026-10-14
- NAVER's WATCH: Cross-Video Human-Video Pretraining Lifts Robot Success Rate to 77.7% — naver-ai · 2026-10-14