Beyond Structure-Driven Tuning: Cost-Aligned Graph Optimization for Approximate Nearest Neighbor Search

Abstract

Graph-based approximate nearest neighbor search (ANNS) is widely used in vector databases and retrieval systems. Most existing methods typically rely on structure-driven index construction and tuning, building graph topologies that approximate idealized geometric archetypes to promote navigability. However, geometric proximity is often an indirect proxy for search efficiency: static graph structures may fail to reflect actual traversal dynamics, leading to redundant distance evaluations such as low-yield node expansions and unnecessary local detours. These inefficiencies can significantly hinder high-recall performance. To address this limitation, we introduce PIGR (Post-hoc Iterative Graph Refinement), a trace-driven framework that explicitly aligns efficiency with observed search behavior. Instead of relying on coarse-grained construction parameter tuning, PIGR leverages self-queries to analyze search traces and identify inefficient traversal behaviors. It further performs iterative index optimization via trace-guided, budgeted prune-and-add edge edits without modifying the deployed search procedure. As a post-construction plug-in, PIGR delivers 1.3x-2.5x speedups at near-exact recall across diverse datasets and index families, consistently outperforming the best build-time tuned baselines.