# boldsymbolSteiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes

arXiv: https://arxiv.org/abs/2408.13899 · HTML: https://mlsanity.com/paper/2408.13899/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Aug 2024.

## Built on by (most cited first, 8 of 8)

- [Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search](https://mlsanity.com/paper/2508.01405/) (2025)
- [Cloud-Native Vector Search: A Comprehensive Performance Analysis](https://mlsanity.com/paper/2511.14748/) (2025)
- [An In-Depth Study of Filter-Agnostic Vector Search on a PostgreSQL Database System: [Experiments and Analysis]](https://mlsanity.com/paper/2603.23710/) (2026)
- [MCGI: Manifold-Consistent Graph Indexing for Billion-Scale Disk-Resident Vector Search](https://mlsanity.com/paper/2601.01930/) (2026)
- [Efficient K-generalizable Learned Search](https://mlsanity.com/paper/2603.06159/) (2026)
- [HNSW with Accuracy Guarantees Using Graph Spanners](https://mlsanity.com/paper/2607.02338/) (2026)
- [Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning](https://mlsanity.com/paper/2607.04630/) (2026)
- [A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search](https://mlsanity.com/paper/2609.02143/) (2026)

## Abstract (arXiv)

Graph-based indexes have been widely employed to accelerate approximate similarity search of high-dimensional vectors. However, the performance of graph indexes to answer different queries varies vastly, leading to an unstable quality of service for downstream applications. This necessitates an effective measure to test query hardness on graph indexes. Nonetheless, popular distance-based hardness measures like LID lose their effects due to the ignorance of the graph structure. In this paper, we propose Steiner-hardness, a novel connection-based graph-native query hardness measure. Specifically, we first propose a theoretical framework to analyze the minimum query effort on graph indexes and then define Steiner-hardness as the minimum effort on a representative graph. Moreover, we prove that our Steiner-hardness is highly relevant to the classical Directed Steiner Tree (DST) problems. In this case, we design a novel algorithm to reduce our problem to DST problems and then leverage their solvers to help calculate Steiner-hardness efficiently. Compared with LID and other similar measures, Steiner-hardness shows a significantly better correlation with the actual query effort on various datasets. Additionally, an unbiased evaluation designed based on Steiner-hardness reveals new ranking results, indicating a meaningful direction for enhancing the robustness of graph indexes. This paper is accepted by PVLDB 2025.