Exact Robustness Certification of k-Nearest Neighbors

Robustness guarantees are essential for deploying machine learning models in security-critical environments where adversarial attacks pose a serious threat. While extensive progress has been made in certifying (deep) neural networks, nonparametric models such as k-Nearest Neighbors (k-NN) have been less investigated, despite their interpretability and usage in high-assurance settings. Prior certification methods for k-NN provide sound but incomplete guarantees, leaving many genuinely robust inputs uncertified. This work introduces a sound and complete certification framework for k-NN classifiers, offering exact robustness guarantees against adversarial perturbations. Our approach combines hypercube space decomposition with a novel graph-theoretic analysis based on an adversarial proximity precedence graph, enabling full coverage of adversarial regions. Extensive evaluation on widely used datasets demonstrates that our exact methodology significantly improves certification rates over existing techniques while maintaining scalability. By closing the gap between soundness and completeness, our framework advances the security guarantees of k-NN models and contributes to the broader goal of provably robust machine learning in adversarial settings.