アーカイブ / RAG
候補までの距離で探索を止める近傍検索：Adaptive Beam Searchの保証と実験
Adaptive Beam Search
Adaptive Beam Searchの原論文から掲載した図です。細部はクリックして拡大できます。
出典：Adaptive Beam Search / arXiv ↗概要
- 近い候補から調べる順序を保ち、固定ビーム幅による停止を、上位k件と次の候補との距離比による停止へ置き換える。
- 距離が三角不等式を満たし、グラフがナビゲート可能なら、γが2のとき正確な上位k件を返すと著者らは証明した。
- 著者らの実験では、同じ再現率で必要な距離計算回数が典型的に10～50％少なかった。
補足：編集した模式図で仕組みを確認する
VISUAL EXPLAINER
図でつかむ、Adaptive Beam Searchの仕組み
- 01質問と検索グラフ
- 02最近候補を選択
- 03隣接点を追加
- 04距離比で停止
- 05上位k件を返す
原論文の説明をもとにした模式図です。処理の細部は省略しています。
研究の背景
Adaptive Beam Searchは、グラフをたどって質問に近いデータを探す際、候補までの距離を基に探索を止める方法だ。近傍検索とは、質問に最も近い文書や画像などを、登録済みのデータから選ぶ処理をいう。
高次元のデータでは全件との距離計算が重いため、各データを点とし、点同士を結んだグラフをたどる方法が使われる。早く止めると近い候補を逃し、長く続けると計算が増える。この研究は、その停止判断を扱う。
手法
入力は検索グラフ、質問、距離の測り方、返す件数k、調整値γである。開始点から、発見済みで隣接点をまだ調べていない候補のうち、質問に最も近い点を選ぶ。その隣接点と質問との距離を測って候補に加え、同じ順序で調査を続ける。発見済みとは、質問との距離を計算済みという意味だ。
発見済みのk番目に近い点と比べ、次に調べる候補の距離が「1＋γ」倍以上なら止め、発見済みの点から近い順にk件を返す。例えばkが1、最良の点までの距離が10、γが0.5なら、次の候補までの距離が15以上で停止する。γを大きくすると停止は遅くなり、調べる範囲が広がる。
新規性
著者らの主張する進歩は、グラフのナビゲート可能性と、探索結果の近似精度を結び付けた点にある。ナビゲート可能とは、任意のデータ点から別のデータ点へ、目標に厳密に近づく隣接点を選べる性質を指す。
距離が三角不等式を満たし、グラフがこの性質を持つ場合、調整値γが0より大きく2以下なら精度を保証する。γが2なら正確な上位k件を返す。実用的なグラフ構築法にも同じ保証がある、という意味ではない。
従来手法との違い
比較対象の通常のビーム探索は、発見済みの候補のうち、質問に近い順で何番目まで調べるかを固定のビーム幅で決める。新方式は候補を近い順に調べる流れを保ち、停止条件を、発見済みの上位k件と次の候補との距離の比に置き換える。
著者らは、一定以下のビーム幅では、グラフがナビゲート可能でも有限の近似倍率を保証できない例を示した。新方式の保証には距離とグラフの条件が要る。実験では、両方式を同じ再現率になるよう調整して比較している。
実験結果
著者らは、ナビゲート可能なグラフと、HNSWやVamanaで構築した実用的なグラフで、固定幅のビーム探索と比較した。データセット、グラフ構築法、返す近傍の件数、再現率を変えている。再現率は、真の近傍のうち検索で見つけた割合を表す。
著者らの報告では、同じ再現率を達成する設定で、質問と候補との距離計算回数は典型的に10～50％少なかった。図の説明には、1万件の質問に対する距離計算回数の分布もある。確認できた本文の範囲では、個別データセット名、再現率ごとの数値、実時間の詳細は確認できない。
応用の可能性
編集上の応用案 · 論文が実証した用途とは区別しています。
編集上の応用案：社内文書検索で、質問に近い文書を上位数件提示する。入力は閲覧権限を確認した文書のベクトルと質問のベクトル、出力は候補文書と質問からの距離とする。既存の検索グラフを使い、停止条件を切り替えて候補の変化を調べる。
必要な元データは社内文書と実際の質問で、評価には質問ごとの関連文書ラベルを人手で用意する。追加学習用データやセンサーは使わない想定とする。文書のベクトル化とグラフへの追加は現行システムに合わせて適応する。効果は検証で判断する。
応用先の候補からNauhに相談できます。
導入時の検証
導入時の検証案 · 対象データでの再評価が必要です。
導入時の検証案：権限を確認した社内文書と実際の質問から作った既存のベクトルと検索グラフを使い、固定幅のビーム探索を基準に新方式を比較する。追加学習用データやセンサーは使わない想定とし、質問ごとの正解文書ラベルを人手で作る。両方式には同じ質問集合を入力する。
返す件数と目標再現率を固定し、基準側のビーム幅と新方式のγをそれぞれ調整する。再現率、質問当たりの距離計算回数、実時間の分布を測り、文書更新後も確認する。適応時にはベクトル化方法とグラフ構築方法をそろえ、停止条件の変更を検証する。
限界と課題
著者らは、この定理から最悪時の実行時間保証は得られないと述べる。また、HNSWなどの構築法が作るグラフには、定理で要請するナビゲート可能性の保証がないと説明する。したがって、実用グラフでの測定結果と定理の保証は分けて読む必要がある。
編集上の検証事項は、対象データで同じ再現率に合わせた場合の距離計算回数、実時間、検索品質である。確認できた本文の範囲では、個別データセットの測定値や実時間の比較表は示されていない。文書更新後も同じ傾向が続くか、別途確かめたい。
出典
元のタイトル・要旨を確認する（英語）
Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search
Nearest neighbor search is central in machine learning, information retrieval, and databases. For high-dimensional datasets, graph-based methods such as HNSW, DiskANN, and NSG have become popular thanks to their empirical accuracy and efficiency. These methods construct a directed graph over the dataset and perform beam search on the graph to find nodes close to a given query. While significant work has focused on practical refinements and theoretical understanding of graph-based methods, many questions remain. We propose a new distance-based termination condition for beam search to replace the commonly used condition based on beam width. We prove that, as long as the search graph is navigable, our resulting Adaptive Beam Search method is guaranteed to approximately solve the nearest-neighbor problem, establishing a connection between navigability and the performance of graph-based search. We also provide extensive experiments on our new termination condition for both navigable graphs and approximately navigable graphs used in practice, such as HNSW and Vamana graphs. We find that Adaptive Beam Search outperforms standard beam search over a range of recall values, data sets, graph constructions, and target number of nearest neighbors. It thus provides a simple and practical way to improve the performance of popular methods.
論文本体の取得範囲に基づく解説。AIが作成した未校閲の記事です。性能の数値は著者の評価条件に依存します。応用例と検証計画は編集上の提案です。解説更新：2026-10-01