--- title: "HNSWとは？階層グラフの仕組みとM・ef_constructionの決め方を実装目線で解説【2026年版】" url: "https://www.issoh.co.jp/tech/details/16468/" published: 2026-08-12 updated: 2026-08-12 categories: ["AI"] publisher: "株式会社一創" --- # HNSWとは？階層グラフの仕組みとM・ef\_constructionの決め方を実装目線で解説【2026年版】 ベクトル検索の索引を張るとき、pgvectorでもQdrantでもMilvusでも既定の選択肢として出てくるのがHNSWです。ところが同じHNSWなのに、辺の本数`m`の既定値は製品によって16だったり30だったり、構築時の候補リスト長は64だったり360だったりと揃っていません。この記事では、HNSW（Hierarchical Navigable Small World）が階層グラフで距離計算を削る仕組みを内部の動きから追い、`M`・`ef_construction`・探索時の`ef`がそれぞれ何を買っているのかを分解します。1件あたりのメモリを何バイトで見積もるか、削除やフィルタ併用でどこが壊れるか、そしてHNSWを選ばずに済ませる条件までを扱います。 ## まとめ：HNSWの正体と、Mとefを決める順序の結論 HNSWとは、ベクトル同士を近いもの同士でつないだグラフを多層に積み、上の疎な層で大きく移動してから下の密な層で詰めることで、距離計算の回数を件数に比例しない量まで削る索引構造です。原典は Malkov と Yashunin による arXiv:1603.09320（2016年提出）。全件走査が件数Nに比例して伸びるのに対し、HNSWの探索はグラフをたどるホップ数で決まるため、100万件でも数千回程度の距離計算で上位候補が返ります。 調整すべき値は3つだけ。`M`は各ノードが持つ辺の本数で、メモリと再現率を同時に押し上げます。`ef_construction`は構築時に見る候補の数で、辺の質を決める代わりに構築時間を食う。探索時の`ef`は候補リストの長さで、これだけが索引を作り直さずに動かせます。したがって手を付ける順序は、まず探索時の`ef`で目標の再現率に届くか試し、届かないか応答時間が要件を超えたときに初めて`M`と`ef_construction`へ戻る、という向きになります。 既定値は製品ごとに揃っていません。pgvector 0.8系は`m`16・`ef_construction`64、Qdrantは16と100、Milvusは30と360、Elasticsearchは16と100。同じ設定で移植したつもりが再現率も速度も変わるのは、この差が原因です。移設時は数字をそのまま持ち込まず、意味で読み替えてから測り直します。 ## HNSWが階層グラフで距離計算の回数を削る仕組みと探索の流れ なぜグラフをたどるだけで速くなるのか。理由は層の作り方と辺の選び方の両方にあります。 ### スモールワールド性と長距離の辺が探索の跳躍を生む構造上の理由 近いもの同士だけをつないだグラフは、目的地までの経路が長くなります。隣の隣の隣、と1歩ずつしか進めないためです。ここに少数の長距離の辺を混ぜると、平均経路長が急に縮む。これがスモールワールド性と呼ばれる性質で、HNSWの土台になっています。 HNSWは、この長距離の辺を「上の層」という形で分離しました。層を上がるほど要素数が減り、残った少数のノード同士が遠くまで届く辺でつながる。下の層は近傍だけの密なグラフで、細かい詰めを担当します。長距離移動と近傍探索という役割の違う動きを、別の層に分けて持たせた構造。 索引構造を製品側の視点から俯瞰したい場合は[ベクトル化とインデックス構造から理解するベクトルデータベースの仕組み](https://www.issoh.co.jp/tech/details/7691/)を参照してください。 ### レベル抽選で上の層ほど疎になる構造と入口から降りる探索の手順 各ベクトルは挿入時に、自分が到達する最上位レベルを確率的に決めます。レベルが1つ上がる確率が一定割合まで下がる指数的な減衰を使うため、大半の要素はレベル0だけに存在し、レベル1に残るのはごく一部、さらに上はもっと少ない。結果として、ピラミッド状の層構造が乱数だけで自然に組み上がります。木構造のように分割の基準を学習しないため、データ分布に依存しないのが利点です。 探索は最上層の入口ノードから始まります。その層で現在地より近い隣接ノードがあれば移動し、動けなくなったらそこを入口として1つ下の層へ降りる。この動作を繰り返し、最下層のレベル0では候補リストを持ちながら幅を持たせて探します。 この構造から2つの帰結が出ます。1つは、探索コストが件数の対数に近いオーダーで伸びる点。もう1つは、レベル0のグラフの質が最終的な再現率をほぼ決める点です。上の層をいくら厚くしても、レベル0の辺が貧弱なら目的のベクトルには届きません。 ### 探索時のefが候補リスト長として精度と応答時間を同時に決める役目 探索時の`ef`は、探索中に保持する候補リストの長さです。値が大きいほど、いったん遠回りに見える経路も候補として残るため、局所解にはまって取りこぼす確率が下がります。同時に、評価する距離計算の回数が増えて応答時間が伸びる。`ef`とは再現率と速度の交換レートを決めるつまみだ、と押さえておけば十分です。 制約として、`ef`は取得件数以上でなければ意味を持ちません。上位10件が欲しいのに`ef`が10のままだと、候補リストに余裕がなく探索が早々に打ち切られます。実務では取得件数の4倍から10倍あたりから試し、再現率の伸びが鈍る点で止めるのが扱いやすい。Milvusの公式ドキュメントも推奨レンジを取得件数Kの1倍から10倍として示しています。 そして`ef`は、索引を作り直さずにセッション単位やクエリ単位で変えられます。作り直しの要る`M`や`ef_construction`と決定的に違う点がここ。だから調整はいつも`ef`から始めます。再現率の目標値そのものをどう決めるか、IVFやPQを含めた3系統の比較は[近似最近傍探索とは？HNSW・IVF・PQの選び分けとRecall調整を実装目線で解説【2026年版】](https://www.issoh.co.jp/tech/details/16466/)に整理しました。 ## 構築時パラメータMとef\_constructionが実際に買っているもの この2つは作り直さないと変えられません。だからこそ、何を買っているのかを先に把握してから決めます。 ### Mを増やすと辺の本数が増えメモリと再現率が同時に動く関係と計算式 `M`は各ノードが保持する辺の本数の上限です。多いほど経路の選択肢が増えて取りこぼしが減る一方、辺を格納する領域が線形に増えます。Faissのインデックス選定ガイドは範囲を4以上64以下として示し、1ベクトルあたりの消費量を「次元数d×4バイト＋M×2×4バイト」と明示しています。前半がfloat32のベクトル本体、後半が辺の分です。 数字を入れると判断が早くなります。768次元・`M`16なら、1件あたり3,072バイト＋128バイトで約3.2KB。100万件で約3.2GBです。ここで`M`を32へ倍増しても増えるのは128バイトぶんだけで、合計は約3.33GB。つまり768次元クラスでは、メモリを押し上げている主因は辺ではなくベクトル本体のほうです。 この内訳が分かると、メモリが厳しいときに手を付ける順序も決まります。`M`を削るより先に、次元数を落とすか、量子化でベクトル本体のバイト数を縮めるほう。次元の切り詰めに対応した埋め込みモデルの選び方は[埋め込みモデルとは？仕組みと日本語モデルの選び方・RAG実装での判断基準【2026年版】](https://www.issoh.co.jp/tech/details/16044/)で扱っています。逆に1億件規模になると`M`32の辺だけで25GB前後に達し、ここからは辺の本数も削減対象に入る。 ### ef\_constructionが辺の質を決める仕組みと近傍選択ヒューリスティック `ef_construction`は、1件を挿入するときに候補として保持する近傍の数です。候補が多いほど、その中から良い辺を選べる。逆に少なければ、たまたま先に見つかった近いノードだけで辺が埋まり、グラフの一部が孤立しやすくなります。構築時間とメモリを払って辺の質を買うパラメータ、という位置づけになります。 原典が単純な最近傍選択と分けて示しているのが、近傍選択のヒューリスティックです。候補の中から近い順にM本を選ぶと、同じ方向に固まったノードばかりが辺になり、別のクラスタへ渡る橋が失われます。ヒューリスティックはこれを避け、既に選んだ辺より近い関係にある候補を落として方向の多様性を残す。分布が複数の塊に分かれたデータで再現率が保たれるのは、この選び方のおかげです。 実務上の目安として、`ef_construction`を上げても効くのは再現率の頭打ち位置だけで、探索時の`ef`ほど素直には効きません。既定値のまま構築し、探索側で目標に届かないと分かってから100や200へ引き上げて作り直す、という順序が費用対効果に合います。Milvusは既定360・推奨50から500と大きめのレンジを示しています。 ### pgvectorとQdrantとMilvusで既定値が食い違う理由と読み替え表 名前も既定値も製品ごとに違いますが、指しているものは共通です。2026年8月時点の一次情報から拾った対応を1枚にまとめます。 | 役割 | pgvector 0.8系 | Qdrant | Milvus | Elasticsearch | | ------- | -------------------- | --------------------- | ------------------- | --------------------- | | 辺の本数 | m（既定16） | m（既定16） | M（既定30） | m（既定16） | | 構築時の候補数 | ef\_construction（64） | ef\_construct（100） | efConstruction（360） | ef\_construction（100） | | 探索時の候補数 | hnsw.ef\_search（40） | ef（既定はef\_construct） | ef（既定はtopK） | num\_candidates で指定 | | 全走査へ切替 | 反復スキャンで回収 | full\_scan\_threshold | FLAT型を別途選択 | フィルタ戦略に依存 | 差が生まれる理由は、各製品が既定で想定する規模とワークロードにあります。PostgreSQLの拡張として動くpgvectorは構築時間とロック時間を短く保つ方向に寄せ、分散前提のMilvusは大規模コレクションで再現率を確保する方向に寄せている、という説明が数字とかみ合います。 移設時に踏む事故は決まっています。Milvusで`M`30・`efConstruction`360で作った索引の感触のまま、pgvectorへ既定値で移して再現率が落ちる。逆にpgvectorの`hnsw.ef_search`40の感覚でMilvusへ移ると、`ef`の既定が取得件数と同値のため候補リストが短すぎて取りこぼします。製品側の制限値やデプロイ形態は[Milvusとは？v3.0の外部コレクション・インデックス選定・デプロイ形態【2026年版】](https://www.issoh.co.jp/tech/details/15929/)にまとめてあります。作成時と検索時で距離指標がずれていないかも移設のたびに確認する箇所。指標の選び方は[コサイン類似度とは？計算式・仕組みと類似検索での実装を実装目線で解説](https://www.issoh.co.jp/tech/details/15075/)で扱いました。 ## HNSWの索引が運用の中で劣化する箇所と再構築を判断する基準 HNSWは追加に強い構造ですが、無限に育つわけではありません。壊れる箇所は3つに絞られます。 ### 削除された頂点が墓標として残りグラフの経路が痩せていく仕組み グラフから1つのノードを取り除くと、そのノードを経由していた経路がすべて切れます。切れた分をつなぎ直すには周辺の辺を選び直す必要があり、コストが高い。そのため多くの実装は、削除を即時の再配線ではなく無効化のフラグで処理し、探索時に読み飛ばす方式を採ります。 この方式の代償が経路の痩せです。無効化されたノードは辺の一部として残り続けるため、探索は存在しない行のためにホップを消費します。削除の割合が増えるほど、同じ`ef`でも実際に評価できる有効な候補が減り、再現率が静かに下がる。 実装によって扱いは異なり、Lucene系はセグメントのマージ時にグラフを作り直すため削除の影響がマージで解消される一方、追記型のグラフでは無効化した頂点が残ったままになります。判断は勘に頼らず、削除率が全体の2割を超えたあたりを再構築の検討開始点に置き、保存した正解セットで再現率を測って目標を割ったら作り直す運用に落とします。 ### メタデータフィルタとの併用で候補が枯れる現象と実装ごとの回避策 実務でいちばん踏むのが、テナントIDや日付での絞り込みとの併用です。グラフは条件を知らずに近い順へ進むため、条件に合うノードが全体の数%しかないと、たどり着いた候補のほとんどが後段のフィルタで落ちます。10件欲しいのに3件しか返らない、という状態。 回避策は実装ごとに用意されています。pgvector 0.8系は反復スキャンを持ち、`hnsw.iterative_scan`に厳密な距離順を保つ設定と順序を緩める設定の2種類があり、既定は無効のため明示的な有効化が要る。Qdrantは絞り込み後の件数を見積もり、`full_scan_threshold`（既定10000・単位KB、1KBが256次元ベクトル1個相当）を下回るならグラフを使わず全走査へ切り替えます。Elasticsearchはフィルタの適用位置とフィルタ後の候補数の指定で調整する形。 いずれの手段も、選択率が極端に低い場合には効きません。絞り込み後に全体の0.1%しか残らない設計なら、索引側の設定を触るのではなくテナント単位でコレクションやテーブルを分けるほうが素直です。検索工程全体の組み立て方は[リトリーバルとは？RAGの検索工程の仕組みと実装・精度改善の判断基準【2026年版】](https://www.issoh.co.jp/tech/details/16055/)にまとめました。 ### インデックス構築の所要時間とメモリを見積もる手順と並列度の上限 HNSWの構築は、1件ずつ挿入してグラフを伸ばす処理の繰り返しです。件数に対しておおむね線形より少し重い伸び方をし、`ef_construction`を上げれば1件あたりのコストがそのぶん増えます。100万件クラスで数十分、1億件で数日という桁感になるため、初回構築の時間はリリース計画に先に織り込みます。 pgvectorのREADMEは、グラフが`maintenance_work_mem`に収まる場合に構築が大幅に速くなる旨と、`max_parallel_maintenance_workers`を既定の2から引き上げる旨を示しています。収まらなければディスクへの書き出しが挟まって桁で遅くなるため、前節の計算式で必要量を先に出し、作業メモリをそこへ合わせるのが手順です。768次元・100万件・`M`16なら約3.2GBが目安になります。 並列度は上げるほど速くなるわけではありません。グラフ構築は共有構造への書き込みを伴い、探索側もメモリ帯域を強く使うため、コア数を増やしても途中で頭打ちになります。並列度は実測で決める。構築の負荷を自前で抱えたくない場合は、マネージド側へ寄せる判断もあります。その比較材料は[Pineconeとは？サーバーレス型ベクトルDBの料金・制限値・実装と選び分け【2026年版】](https://www.issoh.co.jp/tech/details/15926/)に整理しました。 ## HNSWを選ばないと判断してよい条件と、代わりに置く索引設計 ここは言い切ります。HNSWは既定解として優秀ですが、メモリと構築コストを払える範囲でのみ既定解です。 ### メモリ上限が先に来る規模の試算とディスク常駐型への切り替え条件 判断はバイト数の試算だけで足ります。件数N、次元数d、辺の本数Mを前節の式に入れ、搭載可能なメモリと突き合わせる。768次元で1,000万件なら約32GB、1億件なら約320GBです。後者は単一ノードのメモリに載る規模ではなく、分割するかディスク常駐型へ移すかの二択になります。 切り替えの目安は、必要量が搭載メモリの7割を超えたとき。残りをOSのページキャッシュとクエリ処理へ回す余裕がなくなると、スワップが起きて応答時間が桁で悪化します。ディスク常駐型はグラフの一部だけをメモリへ載せる設計で、応答時間は劣る代わりに件数の上限が桁で上がる。RAGの索引が数千万件を超えて伸び続けるなら、HNSWのまま粘るより早めに切り替えたほうが運用は静かになります。 もう1つの分岐は更新頻度です。日次で文書が増え続けるならHNSWの追加耐性が効きますが、月1回の一括入れ替えで済むなら、構築を伴う別方式でも運用が回ります。 ### 量子化を併せる判断と、int8とバイナリのどちらに倒すかの基準 メモリが厳しいときの現実的な手が、グラフ構造はHNSWのまま、ベクトル本体だけを圧縮する組み合わせです。Elasticsearchの`dense_vector`は`int8_hnsw`でスカラー量子化によりメモリを4分の1、`bbq_hnsw`でバイナリ量子化により32分の1へ削ると記載しています。Milvusにも`HNSW_SQ`や`HNSW_PQ`という同型の種別があり、命名は「グラフ構造＋量子化方式」の組み合わせで読めます。 倒し方の基準は次元数です。Elasticsearchは Elastic Stack 9.1 以降、384次元未満のfloatベクトルで`int8_hnsw`、384次元以上で`bbq_hnsw`を既定に置いています。低次元ほど情報量が少なく荒い圧縮が効きにくい、という性質と一致する設計です。 どちらを選ぶにせよ、圧縮した距離は近似値になるため、上位候補だけを元の精度で計算し直す再ランキングを併せて設計します。粗く上位100件から500件を取り、そこから上位10件を確定する形。圧縮率と再ランキングの候補数はセットで決める値で、片方だけ動かすと精度が読めなくなります。 ### 精度不足の原因がHNSW側に無いときの切り分けと委譲先の判断 「検索結果が的外れなのでHNSWのパラメータを詰めたい」という相談は、切り分けから入ります。索引を使わない全件走査で上位10件を取り、それでも欲しい文書が入らないなら、原因はHNSWではありません。埋め込みモデルが日本語の意味を捉えていないか、チャンク分割が文脈を切っているか、そもそも対象文書に答えが書かれていないかのどれかです。 再現率が0.95なら厳密な上位10件のうち平均9.5件は拾えている計算で、的外れな結果の主因としては小さすぎます。逆に、全件走査なら正しい結果が返るのにHNSW経由だと落ちるなら、そのときが`ef`を上げる場面。IVFやPQを含めた方式そのものの選び直しと再現率目標からの逆算手順は[近似最近傍探索とは？HNSW・IVF・PQの選び分けとRecall調整を実装目線で解説【2026年版】](https://www.issoh.co.jp/tech/details/16466/)へ委譲しました。 索引方式の選定からパラメータの初期値決め、再現率の実測までを外部に任せたい場合は、[RAG構築支援](https://www.issoh.co.jp/service/ai/rag/)で対応しています。既存データの件数と次元数からメモリを試算し、製品選定と設定値の初期案を出したうえで、実データでの測定まで含めて設計する進め方です。 ## よくある質問 HNSWの実装で問い合わせの多い論点を5つ挙げます。 ### HNSWのMはいくつから始めるのが無難ですか？ 16から始めれば大きく外しません。pgvector・Qdrant・Elasticsearchはいずれも既定が16で、Faissのガイドも4以上64以下の範囲を示しています。数千万件を超える、あるいは再現率が0.95に届かないと分かった段階で32へ引き上げ、構築時間とメモリの増分を測って採否を決める順序が扱いやすい。Milvusだけは既定が30なので、他製品から移すときは数字の差を意識してください。 ### ef\_searchを上げても再現率が伸びないのはなぜですか？ 探索側で伸びが止まったなら、限界はグラフの質のほうにあります。`ef_construction`が小さいまま構築された索引は、レベル0の辺が近い方向へ偏り、どれだけ候補リストを長くしても届かない領域が残ります。作り直しが必要なサイン。併せて、距離演算子が作成時と検索時で一致しているか、フィルタ併用で候補が枯れていないかも確認します。 ### HNSWのインデックス構築が終わらないときは何を疑いますか？ 最初に見るのは作業メモリです。グラフが収まらずディスクへ書き出されると桁で遅くなります。pgvectorなら`maintenance_work_mem`を必要量へ引き上げ、`max_parallel_maintenance_workers`も既定の2から増やす。次に`ef_construction`の値。360のような大きい設定のまま数千万件を構築していないか確かめ、既定へ戻して測り直します。 ### 製品を移るときHNSWのパラメータはそのまま使えますか？ 数字の直輸入は避けてください。役割の対応は共通でも既定値が違うため、同じ値でも相対的な強さが変わります。探索時の候補数はとくに注意が必要で、既定が固定値の製品と取得件数に連動する製品が混在。移設後は正解セットで再現率を測り直し、探索側の値だけを動かして目標へ合わせる手順を1度通します。 ### hnswlibのような単体ライブラリとDB内蔵のHNSWはどう使い分けますか？ 件数が数十万までで、更新もバッチで完結し、メタデータでの絞り込みが要らないなら単体ライブラリで足ります。実装が薄く、パラメータの効き方も直接確かめられるためです。逆に、権限やテナントでの絞り込み、トランザクション、既存データとの結合が要るならDB内蔵側。索引の永続化と再構築の運用まで含めて考えると、後者の総コストが下回る場面が多くなります。 ## 関連記事 - [近似最近傍探索とは？HNSW・IVF・PQの選び分けとRecall調整を実装目線で解説【2026年版】](https://www.issoh.co.jp/tech/details/16466/)：IVF・PQを含めた方式選定と再現率の逆算手順 - [ベクトル化とインデックス構造から理解するベクトルデータベースの仕組み](https://www.issoh.co.jp/tech/details/7691/)：製品側から見た索引構造と選定基準 - [Milvusとは？v3.0の外部コレクション・インデックス選定・デプロイ形態【2026年版】](https://www.issoh.co.jp/tech/details/15929/)：分散構成での索引種別と制限値 - [埋め込みモデルとは？仕組みと日本語モデルの選び方・RAG実装での判断基準【2026年版】](https://www.issoh.co.jp/tech/details/16044/)：次元数と日本語品質の選定基準 - [コサイン類似度とは？計算式・仕組みと類似検索での実装を実装目線で解説](https://www.issoh.co.jp/tech/details/15075/)：距離指標の計算式と使い分け --- 出典: [HNSWとは？階層グラフの仕組みとM・ef\_constructionの決め方を実装目線で解説【2026年版】]()（株式会社一創）