論文の概要: A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search

• arxiv url: http://arxiv.org/abs/2609.02143v1
• Date: Wed, 02 Sep 2026 05:56:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-03 17:53:18.09961
• Title: A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search
• Title（参考訳）: 対数衣服における電力法則--グラフに基づくベクトル探索のスケーラビリティについて
• Abstract要約: データセットの内在的な次元は、データが基礎となる分布を解決するまで、そのサイズでどのように成長するかを示す。 データセットの内在的な次元性は、データが基礎となる分布を解決するまでそのサイズとともに成長する。 我々は、ビーム探索コストの統一理論を提示し、我々の観測を解説する。
• 参考スコア（独自算出の注目度）: 2.0263791972068623
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Most vector databases rely on graph-based indexes, notably HNSW and Vamana, for approximate nearest neighbor search. With embedding models widely adopted, the datasets these databases store grow rapidly. At a fixed accuracy, how does search cost scale with dataset size? The prevailing answer is poly-logarithmic growth. Yet the claim is proven only under special conditions and asserted without proof for the indexes used in practice. It is also largely untested: standard benchmarks measure cost at one dataset size, not across sizes. We put the claim to the test. The answer depends on the scale itself. While the dataset size $N$ is small relative to the data's intrinsic dimensionality, search cost grows as $N^c$ for a constant $0<c<1$. We call this scaling the Sublinear Power Law. Once $N$ is large enough, growth slows to subpolynomial, consistent with the poly-logarithmic claim. The Sublinear Power Law appears on every dataset, mostly up to its full size, at every recall target, query hardness level, and index configuration we test. The transition to subpolynomial growth appears on the two datasets that grow large enough relative to their intrinsic dimensionality. One mechanism underlies both behaviors: a dataset's intrinsic dimensionality grows with its size until the data resolves its underlying distribution. Higher intrinsic dimensionality packs more vectors into the query neighborhood the search must examine. We present a unifying theory of beam-search cost that explains our observations. For exact and bounded-degree constructions, we prove the Sublinear Power Law and the eventual transition to poly-logarithmic scaling, and derive the scale at which it occurs. We also develop models that predict the power-law exponents for any recall target and index configuration. These models give a principled way to navigate trade-offs among search cost, insertion cost, and recall as data grows.
• Abstract（参考訳）: ほとんどのベクトルデータベースはグラフベースのインデックスに依存しており、特にHNSWやVamanaは近傍の探索によく似ている。 埋め込みモデルが広く採用されると、これらのデータベースが格納するデータセットは急速に成長する。 一定の精度で、データセットサイズによる検索コストはどのようにスケールするか? 主な答えは多対数成長である。 しかし、主張は特別な条件下でのみ証明され、実際に使用される指標の証明無しに主張される。 標準ベンチマークは、サイズではなく、ひとつのデータセットサイズでコストを測定します。 私たちはその主張を試験に当てた。 答えはスケールそのものに依存します。 データセットサイズ$N$は、データ固有の次元に対して小さいが、検索コストは、一定の$0<c<1$に対して$N^c$として増加する。 これをサブリニア電力法と呼ぶ。 N$が十分に大きいと、成長はポリ対数的クレームと一致して、サブポリノミカルに遅くなる。 サブリニア電力法(Sublinear Power Law)は、ほとんどの場合、すべてのリコールターゲット、クエリのハードネスレベル、テスト対象のインデックス設定など、すべてのデータセットに表示される。 サブポリノミカルな成長への遷移は、その内在的な次元に対して十分に大きく成長する2つのデータセットに現れる。 データセットの内在的な次元性は、データが基礎となる分布を解決するまでそのサイズとともに成長する。 より内在的な次元性は、探索が調べなければならないクエリ近傍により多くのベクトルを詰め込む。 我々は、ビーム探索コストの統一理論を提示し、我々の観測を解説する。 厳密かつ有界な構成に対しては、サブ線形パワー法と、多対数スケーリングへの最終的な遷移を証明し、それが生じるスケールを導出する。 また,任意のリコール目標とインデックス設定に対するパワーロー指数を予測するモデルも開発している。 これらのモデルは、検索コスト、挿入コスト、データの増加に伴うリコールの間のトレードオフをナビゲートする原則的な方法を提供する。

関連論文リスト

• Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions [4.018187102803958]
  我々は,データセットサイズが$N$,次元が$d$に対して,マルチプローブグリッドアルゴリズムの体系的特性を示す。 その結果、マルチプローブグリッドのようなグリッドベースの手法は、再構築重度や高次元設定において競合する可能性が示唆された。
  論文  参考訳（メタデータ） (2026-07-01T08:42:38Z)
• Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval [59.859592671274704]
  $dtimes d$ リニアメモリストアはいくつのキー値アソシエーションが可能ですか? この答えは、メモリマトリックスの$d2$自由度だけでなく、検索基準にも依存する。
  論文  参考訳（メタデータ） (2026-05-06T17:53:20Z)
• Improved Scaling Laws in Linear Regression via Data Reuse [36.110514249309254]
  データの再利用は線形回帰における既存のスケーリング法則を改善することができることを示す。 これはデータ再利用によるスケーリング法則の改善(すなわち、データ制約されたレシエーションで$L>N$を選択する)を示唆している。
  論文  参考訳（メタデータ） (2025-06-10T03:39:29Z)
• Scaling Laws for Gradient Descent and Sign Descent for Linear Bigram Models under Zipf's Law [4.6193503399184275]
  最近の研究は、トランスフォーマーベースの言語モデルの最初の層と最後の層を訓練する際の勾配降下による困難を浮き彫りにした。 これらの研究は、テキストデータ中の単語の重み付き分布に、難易度が関係していることを示唆している。 データが重い尾を持つ場合、問題はより困難であることを示す。
  論文  参考訳（メタデータ） (2025-05-25T16:43:51Z)
• DataDecide: How to Predict Best Pretraining Data with Small Experiments [67.95896457895404]
  私たちはDataDecideのモデル、データ、評価を公開しています。 最大100Bトークン,最大1Bパラメータのモデルサイズ,および3つのランダムシードを用いて,25コーパスにわたる事前学習実験を行った。
  論文  参考訳（メタデータ） (2025-04-15T17:02:15Z)
• Highly Adaptive Ridge [84.38107748875144]
  直交可積分な部分微分を持つ右連続函数のクラスにおいて,$n-2/3$自由次元L2収束率を達成する回帰法を提案する。 Harは、飽和ゼロオーダーテンソル積スプライン基底展開に基づいて、特定のデータ適応型カーネルで正確にカーネルリッジレグレッションを行う。 我々は、特に小さなデータセットに対する最先端アルゴリズムよりも経験的性能が優れていることを示す。
  論文  参考訳（メタデータ） (2024-10-03T17:06:06Z)
• Scaling Laws in Linear Regression: Compute, Parameters, and Data [86.48154162485712]
  無限次元線形回帰セットアップにおけるスケーリング法則の理論について検討する。 テストエラーの再現可能な部分は$Theta(-(a-1) + N-(a-1)/a)$であることを示す。 我々の理論は経験的ニューラルスケーリング法則と一致し、数値シミュレーションによって検証される。
  論文  参考訳（メタデータ） (2024-06-12T17:53:29Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  逆例は機械学習モデルにおいて広く研究されている現象である。 そこで本研究では,$k$-nearest 近傍分類の逆ロバスト性を評価するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-19T08:49:10Z)
• A Neural Scaling Law from the Dimension of the Data Manifold [8.656787568717252]
  データが豊富であれば、よく訓練されたニューラルネットワークによって達成される損失は、ネットワークパラメータの数でN-alpha$のパワーロープロットとしてスケールする。 スケーリングの法則は、ニューラルモデルが本質的に内在次元$d$のデータ多様体上で回帰を行えば説明できる。 この単純な理論は、スケーリング指数が、クロスエントロピーと平均二乗誤差損失に対して$alpha approx 4/d$となることを予測している。
  論文  参考訳（メタデータ） (2020-04-22T19:16:06Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。