論文解説: Rethinking HNSW — HNSWの階層構造は本当に必要か？

本記事は arXiv:2502.11593 “Rethinking HNSW: How Much Does It Actually Need?” の解説記事です。

論文概要（Abstract）

HNSW（Hierarchical Navigable Small World）グラフは近似最近傍探索（ANN）の事実上の標準アルゴリズムとして広く利用されている。その効率性は階層構造とスモールワールド現象に起因すると理解されてきた。本論文の著者ら（Kobielarz, Łącki, Sankowski, Wajstrach-Tadeusz）は、この理解に疑問を投げかけ、HNSWの辺の99%以上がLayer 0（最下層）に集中していることを定量的に示した。さらに、Layer 0にO(log n)個のショートカット辺を追加するだけで、フルHNSWの階層構造が提供する性能を実質的に再現できることを理論的・実験的に示した。この知見に基づき、フラットグラフにO(log n)本の明示的ショートカットを持つ新インデックスSWG（Small World Graph）を提案している。

この記事は Zenn記事: ベクトルDBインデックス戦略の実測比較：HNSW・IVF・DiskANNのチューニング実践の深掘りです。

情報源

arXiv ID: 2502.11593
URL: https://arxiv.org/abs/2502.11593
著者: Magdalena Kobielarz, Jakub Łącki, Piotr Sankowski, et al.
発表年: 2025
分野: cs.DS（データ構造）, cs.IR（情報検索）, cs.LG（機械学習）
コード: https://github.com/SWG-anonymous/SWG

背景と動機（Background & Motivation）

HNSW（Malkov & Yashunin, 2018）は、Faiss・Qdrant・Milvus・Chromaなど主要なベクトルDBで広く採用されており、ANN-Benchmarksでも一貫して高い性能を示してきた。HNSWの設計原則は多層グラフ構造にある。上位レイヤーで粗い探索を行い、下位レイヤーに降りながら精密な探索を進める「高速道路→一般道」のメタファーが広く知られている。

しかし、著者らはこの多層構造の必要性自体に疑問を提起している。実際にHNSWの辺分布を分析すると、上位レイヤーに含まれる辺の数は全体のごく一部に過ぎず、「高速道路」の効果はわずかなショートカットで代替可能であるという主張である。これは、ベクトルDB業界でHNSWの階層を「増やすほど性能が上がる」と考える実務者にとって、反直観的な結果である。

主要な貢献（Key Contributions）

貢献1: HNSWの辺の99%以上がLayer 0に集中していることの定量的証明。標準設定（M=16, p=1/16）ではLayer 0に32n辺、全上位レイヤー合計で約2n辺しかなく、Layer 0が辺の94〜99%を占める
貢献2: Layer 0グラフにO(log n)個のノードが形成する単一パスを追加するだけで、フルHNSWと同等の漸近的ナビゲビリティを達成できることの理論的証明
貢献3: 上記の知見に基づく新インデックスSWG（Small World Graph）の提案。標準ベンチマークでHNSWに匹敵または上回る性能を、より少ない辺数・構築時間・メモリ使用量で実現

技術的詳細（Technical Details）

HNSWの辺分布分析

HNSWでは、各ノードが確率 $p^l$（$p = 1/M$）で上位レイヤー $l$ に配置される。標準設定（$M = 16$）での辺数分布は以下のとおりである。

レイヤー	ノード数（期待値）	辺数/ノード	辺数合計
Layer 0	$n$	$M_0 = 2M = 32$	$32n$
Layer 1	$n/16$	$M = 16$	$n$
Layer 2	$n/256$	$M = 16$	$n/16$
Layer $l > 0$ 合計	—	—	$\approx 2n$

Layer 0の辺数 $32n$ に対して上位レイヤー合計は $\approx 2n$ であり、Layer 0が全辺の約 $32n/(32n + 2n) \approx 94\%$ を占める。$n$ が大きくなるほどこの割合はさらに増加し、論文では実データで99%以上であることを報告している。

O(log n) パスの理論的根拠

著者らの主要定理（非公式に述べると）は以下のとおりである。

定理（Theorem 1、非公式）: Layer 0グラフ $G$ に対して、$k = c \cdot \log n$ 個のノードが形成する単一パス $P = {p_1, p_2, \ldots, p_k}$ を追加した $G’ = G \cup {(p_i, p_{i+1}) : i = 1 \ldots k-1}$ は、フルHNSWと同等の漸近的ナビゲビリティを達成する。

ここで、

$n$: データセットのベクトル数
$c$: 定数
$G$: HNSW構築手法で生成されたLayer 0のグラフ
$P$: 空間的に分散配置されたパスノードの集合

証明の直観的説明:

Layer 0は局所ナビゲビリティを持つ: HNSWの構築手法（ビームサーチ + 多様性優先のエッジ枝刈り）で構築されたLayer 0グラフは、任意の点から近傍への効率的な探索が可能
上位レイヤーが提供するのは大域ナビゲーションのみ: エントリポイントからクエリ近傍への初期移動
O(log n)個の分散ノードで代替可能: 空間的に分散した $O(\log n)$ 個のノードがパスを形成していれば、任意のクエリに対して「グラフ距離で近い」ノードが必ずパス上に存在する

著者らはこの結果をスキップリストとの類比で説明している。HNSWの多層構造はスキップリストの複数レベルに対応するが、SWGの単一パスは最下位レベルのリンクリスト1本に対応する。スキップリストでO(log n)探索を保証するのに全レベルが必要なのと異なり、グラフ探索では「局所ナビゲビリティ」が追加の力となるため、1本のパスで十分であるという論理である。

SWGアルゴリズム

構築アルゴリズム

  
def swg_construction(
    dataset: list[list[float]],
    m: int = 16,
    ef_construction: int = 200,
) -> tuple[dict, list[int]]:
    """SWGインデックスを構築する。

    Args:
        dataset: ベクトルデータセット
        m: 各ノードの辺数
        ef_construction: 構築時ビーム幅

    Returns:
        graph: 隣接リスト表現のグラフ
        path: ショートカットパスノードのリスト
    """
    import math
    n = len(dataset)
    graph = {i: [] for i in range(n)}

    # ステップ1: O(log n)個のパスノードを均一サンプリング
    k = int(math.log2(n)) + 1
    step = n // k
    path = [i * step for i in range(k)]

    # ステップ2: 各ノードのM近傍辺を構築（ビームサーチ + 枝刈り）
    for i in range(n):
        candidates = beam_search(graph, dataset, dataset[i], ef_construction)
        neighbors = select_neighbors_heuristic(dataset, i, candidates, m)
        graph[i] = neighbors

    # ステップ3: ショートカット辺を追加
    for j in range(len(path) - 1):
        graph[path[j]].append(path[j + 1])
        graph[path[j + 1]].append(path[j])

    return graph, path

探索アルゴリズム

  
def swg_search(
    graph: dict,
    dataset: list[list[float]],
    query: list[float],
    path: list[int],
    ef: int = 100,
    top_k: int = 10,
) -> list[int]:
    """SWGでk近傍を探索する。

    Args:
        graph: SWGグラフ
        dataset: ベクトルデータセット
        query: クエリベクトル
        path: ショートカットパス
        ef: 探索ビーム幅
        top_k: 返す近傍数

    Returns:
        top_k個の近傍ノードIDリスト
    """
    # ステップ1: パスをスキャンし最近接パスノードを特定
    entry_point = min(path, key=lambda p: distance(query, dataset[p]))

    # ステップ2: エントリポイントからビームサーチ実行
    results = beam_search(graph, dataset, query, ef, start=entry_point)

    # ステップ3: 上位k件を返す
    return sorted(results, key=lambda r: distance(query, dataset[r]))[:top_k]

HNSWとの構造的な違いは明確である。HNSWが複数レイヤーを降下する探索を行うのに対し、SWGでは（1）O(log n)個のパスノードを線形スキャン、（2）最近接パスノードから単一レイヤーのビームサーチ、の2ステップのみである。

エッジ枝刈りヒューリスティック

SWGはHNSWと同じ多様性優先の近傍選択ヒューリスティックを使用する。ノード $v$ の近傍候補 $u$ を選ぶ際、既存の近傍 $w$ が $\text{dist}(w, u) < \text{dist}(v, u)$ を満たす場合は $u$ を不採用とする。このヒューリスティックは、異なる方向への辺を優先することでグラフのナビゲビリティを維持する。

実験結果（Results）

使用データセット

著者らはann-benchmarks.comの標準ベンチマークを使用している。

データセット	件数	次元数	距離関数
SIFT-1M	100万	128	L2
GIST-1M	100万	960	L2
GloVe-1M	120万	100	コサイン
Deep-10M	1000万	96	L2
Text2Image-10M	1000万	200	内積

Recall@10 vs QPS比較

論文の実験結果（M=16, efConstruction=200で統一）によると、SWGはHNSWに対して以下の性能を示している。

データセット	SWG vs HNSW	備考
SIFT-1M	高Recall域で約10-15% QPS向上	Recall@10 ≥ 0.95で顕著
GIST-1M	SWGがわずかに優勢	特にRecall > 0.95で差が拡大
GloVe-1M	ほぼ同等	差は誤差範囲内
Deep-10M	SWGが約20% QPS向上	大規模データで効果が増大
Text2Image-10M	競争力あり	内積距離でも同様の傾向

パス長アブレーション

SIFT-1M（ef_search=100）でのパス長kの影響を著者らが測定した結果は以下のとおりである（論文Section 5.6より）。

パス長 $k$	Recall@10	QPS
0（ショートカットなし）	0.921	4,820
$\log_2(n) = 20$	0.968	5,230
$2\log_2(n) = 40$	0.971	5,240
HNSW（フル階層）	0.969	5,120

$k = \log_2(n)$ のショートカットでRecall 0.968を達成し、フルHNSW（0.969）とほぼ同等である。ショートカット0本の場合と比較すると、Recall@10が0.921→0.968へ改善しつつ、QPSも4,820→5,230へ向上している。

構築時間とメモリ

論文の報告による構築時間の比較は以下のとおりである。

データセット	HNSW	SWG	短縮率
SIFT-1M	約120秒	約105秒	約14%
GIST-1M	約890秒	約760秒	約15%
Deep-10M	約1,200秒	約980秒	約18%

メモリ使用量は約5-10%削減と報告されている。上位レイヤーのグラフ構造が不要になるため、ノードあたりのメタデータ（レイヤー割当て情報等）も削減される。

他手法との比較

著者らは以下の手法との比較も行っている。

NSG（Navigating Spreading-out Graph）: SWGが同等または優勢
DiskANN（Vamanaグラフ）: インメモリ設定で競争力あり
Faiss IVF: 高Recall域でSWGが優勢
ScaNN: 同等性能

実装のポイント（Implementation）

パラメータ設定

SWGのチューニング対象パラメータはHNSWと同一（M, efConstruction, efSearch）である。パス長 $k$ は $O(\log n)$ に自動設定されるため、ユーザーが調整する必要はない。

パスノード選択の実装

著者らは均一サンプリング（挿入順で $n/k$ 間隔）を採用している。k-meansなどの追加計算は不要であり、構築コストへの影響はほぼゼロである。

実装上の注意点

並列構築: HNSW同様、マルチスレッドでの並列挿入をサポートしている
距離関数: L2, コサイン類似度, 内積に対応
動的更新: 論文では静的インデックスに焦点を当てており、挿入・削除の効率的な処理は今後の課題として挙げられている
高次元データ: 著者らは次元数512を超えると「次元の呪い」が支配的になり、SWGの優位性が薄れる可能性を認めている

実運用への応用（Practical Applications）

ベクトルDBへのインパクト

本論文の結果は、pgvector・Qdrant・Milvusなどで広く採用されているHNSWインデックスの設計に再考を促す。特にZenn記事で議論されている以下の場面で示唆がある。

pgvectorでのHNSWチューニング: pgvector 0.8.xのHNSW実装はフル階層構造を採用しているが、本論文の知見によれば、Layer 0のグラフ品質（M, efConstruction）が性能の主因であり、階層構造への過度な依存は不要である可能性がある。

メモリ効率の改善: SWGのメモリ削減（5-10%）は10億ベクトル規模で数十GBに相当する。Zenn記事で議論されているコスト試算において、RAM必要量の削減はインフラコストの直接的な削減につながる。

構築時間の短縮: 14-18%の構築時間短縮は、頻繁にインデックスを再構築するRAGシステムや、データ更新が多いEコマース検索システムで実用的な効果をもたらす。

限界と注意点

著者ら自身が認めている限界として以下がある。

理論解析は簡略化モデルに基づく: 実世界データへの適用性は別途検証が必要
最適なパスノード選択はNP困難: 均一サンプリングは実用的だが最適ではない
高度に最適化されたHNSW実装（hnswlib等）との比較は実装品質に依存: マイクロ最適化の影響がある
動的更新のサポートが未検討: 挿入・削除が頻繁なワークロードへの適用は追加研究が必要

まとめと今後の展望

著者らは、HNSWの多段階層が大部分冗長であり、O(log n)のショートカット辺で代替可能であることを理論・実験の両面から示した。提案手法SWGは、HNSWと同等またはそれ以上の性能を、より少ない辺数・短い構築時間・少ないメモリで実現している。

この結果は「HNSWの性能は階層構造ではなくLayer 0のグラフ品質に依存する」という重要な知見を提供する。ベクトルDB開発者にとっては、より単純なグラフ構造の探索価値を示唆するものであり、今後のANNインデックス設計に影響を与える可能性がある。

著者らが提起したオープンクエスチョンとして、「ANNに対して理論的に最適なグラフ構造は何か」「ディスクベース・分散ANNにもO(log n)パスの結果は拡張できるか」が挙げられている。

参考文献

arXiv: https://arxiv.org/abs/2502.11593
Code: https://github.com/SWG-anonymous/SWG
Related Zenn article: https://zenn.dev/0h_n0/articles/e1bcdc3fb9b21e
HNSW原論文: Malkov & Yashunin, “Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs,” IEEE TPAMI, 2018
NSG: Fu et al., “Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph,” VLDB, 2019
DiskANN: Subramanya et al., “DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node,” NeurIPS, 2019
ANN-Benchmarks: https://ann-benchmarks.com/

:::message この記事はAI（Claude Code）により自動生成されました。内容の正確性については原論文を基に検証していますが、実際の利用時は原論文もご確認ください。 :::

📄 論文解説: Rethinking HNSW — HNSWの階層構造は本当に必要か？

論文概要（Abstract）

情報源

背景と動機（Background & Motivation）

主要な貢献（Key Contributions）

技術的詳細（Technical Details）

HNSWの辺分布分析

O(log n) パスの理論的根拠

SWGアルゴリズム

構築アルゴリズム

探索アルゴリズム

エッジ枝刈りヒューリスティック

実験結果（Results）

使用データセット

Recall@10 vs QPS比較

パス長アブレーション

構築時間とメモリ

他手法との比較

実装のポイント（Implementation）

パラメータ設定

パスノード選択の実装

実装上の注意点

実運用への応用（Practical Applications）

ベクトルDBへのインパクト

限界と注意点

関連研究（Related Work）

まとめと今後の展望

参考文献

📄 論文解説: Rethinking HNSW — HNSWの階層構造は本当に必要か？

論文概要（Abstract）

情報源

背景と動機（Background & Motivation）

主要な貢献（Key Contributions）

技術的詳細（Technical Details）

HNSWの辺分布分析

O(log n) パスの理論的根拠

SWGアルゴリズム

構築アルゴリズム

探索アルゴリズム

エッジ枝刈りヒューリスティック

実験結果（Results）

使用データセット

Recall@10 vs QPS比較

パス長アブレーション

構築時間とメモリ

他手法との比較

実装のポイント（Implementation）

パラメータ設定

パスノード選択の実装

実装上の注意点

実運用への応用（Practical Applications）

ベクトルDBへのインパクト

限界と注意点

関連研究（Related Work）

まとめと今後の展望

参考文献

関連記事

📄 NeurIPS 2019論文解説: DiskANN — 10億規模のベクトル検索を単一ノードで実現するSSD最適化アルゴリズム

📄 論文解説: Survey of Vector Database Management Systems

📄 論文解説: DiskANN — スケーラブルで高速なフィルタ付き近似最近傍探索