Efficient Approximate Vector Search via Adaptive Result Feedback on Graphs

Graph-based approximate nearest neighbor search is a fundamental component of vector retrieval in modern AI systems. Efficient search requires adapting exploration to the needs of individual queries, whose results may improve at different rates throughout execution. Conventional search-width and frontier-based controls do not explicitly track this temporal progress, limiting their ability to identify when additional exploration remains productive. We propose feedsearch, a query-state-aware search strategy that accelerates search on proximity graphs through online result feedback. Feedsearch characterizes a query's evolving search state using the magnitude and temporal history of improvements to its current top-$k$ results. A lightweight, training-free controller inspired by Adam maintains decaying statistics of these improvements and normalizes recent progress against a query-specific scale. This feedback determines how long exploration continues, allowing the strategy to adjust search effort as the query progresses. A lazy implementation skips repeated statistic updates during zero-gain intervals. Experiments across diverse datasets, graph indexes, and similarity measures demonstrate improved recall–throughput trade-offs on a range of workloads.