論文の概要: Coordination-Free Lane Partitioning for Convergent ANN Search

• arxiv url: http://arxiv.org/abs/2511.04221v1
• Date: Thu, 06 Nov 2025 09:36:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-07 20:17:53.379103
• Title: Coordination-Free Lane Partitioning for Convergent ANN Search
• Title（参考訳）: 収束ANN探索のためのコーディネーションフリーレーン分割
• Authors: Carl Kugblenu, Petri Vuorimaa,
• Abstract要約: 生産ベクトルサーチシステムは、遅延サービスレベル目標(SLO)を満たすために、並列レーンにまたがる各クエリをファンアウトすることが多い。 複製を相補的な作業に同じコストと期限で変換する調整不要レーン分割器を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Production vector search systems often fan out each query across parallel lanes (threads, replicas, or shards) to meet latency service-level objectives (SLOs). In practice, these lanes rediscover the same candidates, so extra compute does not increase coverage. We present a coordination-free lane partitioner that turns duplication into complementary work at the same cost and deadline. For each query we (1) build a deterministic candidate pool sized to the total top-k budget, (2) apply a per-query pseudorandom permutation, and (3) assign each lane a disjoint slice of positions. Lanes then return different results by construction, with no runtime coordination. At equal cost with four lanes (total candidate budget 64), on SIFT1M (1M SIFT feature vectors) with Hierarchical Navigable Small World graphs (HNSW) recall@10 rises from 0.249 to 0.999 while lane overlap falls from nearly 100% to 0%. On MS MARCO (8.8M passages) with HNSW, hit@10 improves from 0.200 to 0.601 and Mean Reciprocal Rank at 10 (MRR@10) from 0.133 to 0.330. For inverted file (IVF) indexes we see smaller but consistent gains (for example, +11% on MS MARCO) by de-duplicating list routing. A microbenchmark shows planner overhead of ~37 microseconds per query (mean at the main setting) with linear growth in the number of merged candidates. These results yield a simple operational guideline: size the per-query pool to the total budget, deterministically partition positions across lanes, and turn redundant fan-out into complementary coverage without changing budget or deadline.
• Abstract（参考訳）: プロダクションベクターサーチシステムは、遅延サービスレベルの目的(SLO)を満たすために、並列レーン(スレッド、レプリカ、シャード)にまたがるクエリをファンアウトすることが多い。 実際には、これらのレーンは同じ候補を再発見するため、余分な計算ではカバレッジは増加しない。 複製を相補的な作業に同じコストと期限で変換する調整不要レーン分割器を提案する。 各クエリに対して,(1)全トップk予算に匹敵する決定論的候補プールを構築し,(2)クエリごとの擬似乱数置換を適用し,(3)各レーンに不連続な位置のスライスを割り当てる。 ランは、実行時の調整なしに、異なる結果をコンストラクションによって返します。 SIFT1M(1M SIFT特徴ベクトル)の階層的ナビゲート可能な小型世界グラフ(HNSW)リコール@10は0.249から0.999に上昇する一方、レーンオーバーラップは100%から0%に低下する。 HNSWによるMS MARCO (8.8Mパス)では、 hit@10 は 0.200 から 0.601 に改善され、平均 Reciprocal Rank (MRR@10) は 0.133 から 0.330 に改善された。 逆ファイル(IVF)インデックスの場合、リストルーティングの非重複化により、より小さいが一貫したゲイン(例えばMS MARCOでは+11%)が見られる。 マイクロベンチマークは、クエリ毎に約37マイクロ秒のプランナーオーバーヘッドを示し、マージされた候補の数は線形に増加する。 これらの結果は、クエリ単位のプールを総予算にサイズし、レーンを横断する位置を決定的に分割し、冗長なファンアウトを予算や期限を変更することなく補完的なカバレッジに変換するという単純な運用ガイドラインをもたらす。

関連論文リスト

• Practical Code RAG at Scale: Task-Aware Retrieval Design Choices under Compute Budgets [1.933829683108616]
  本研究では,現実的な計算予算下でのコード中心生成タスクの検索設計について検討する。 我々は, (i) チャンキング戦略, (ii) 類似度スコア, (iii) 粒度を分割する3つの軸に沿って, 様々なコンテキストウィンドウサイズにわたる検索構成を比較した。
  論文  参考訳（メタデータ） (2025-10-23T14:40:11Z)
• Batched Stochastic Matching Bandits [43.651070266360954]
  本稿では,MNL選択モデルに基づくマッチングのための新しい帯域幅フレームワークを提案する。 私たちの設定では、一方の$N$エージェントは他方の$K$アームに割り当てられます。 目的は、すべてのエージェントで成功した試合から累積収入を最大化することで、後悔を最小限に抑えることである。
  論文  参考訳（メタデータ） (2025-09-04T13:16:32Z)
• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。 実現可能な最小二乗の設定において、新しい最上界を創出する。 我々は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスで破滅的な事態を防げることを初めて証明した。
  論文  参考訳（メタデータ） (2025-04-06T18:39:45Z)
• Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations [92.1840862558718]
  実用的な分散システムでは、労働者は概して均質ではなく、非常に多様な処理時間を持つ。 本稿では、任意に遅い計算を扱うための新しい並列手法Freyaを提案する。 Freyaは従来の手法と比較して,複雑性の保証が大幅に向上していることを示す。
  論文  参考訳（メタデータ） (2024-05-24T13:33:30Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)
• GraB: Finding Provably Better Data Permutations than Random Reshuffling [39.067886932979874]
  ランダムリシャッフルはデータセットを各エポックにランダムに置換するが、非置換サンプリングよりも高速な収束をもたらすため、モデルトレーニングでは広く採用されている。 最近の研究では、厳密に選択されたデータ順序付けは、より多くの計算とメモリを使用するコストで、経験的に収束をさらにスピードアップさせることができることが示されている。 グラディエント・バランシング・アルゴリズム(GraB)は、トレーニングと検証の両方のパフォーマンスにおいて、ランダムなリシャッフルよりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-22T04:17:32Z)
• Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
  本稿では、特にバッチ強化学習に適した報酬不要強化学習フレームワークと、複数の報酬関数に対するポリシーを必要とするシナリオについて検討する。 textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname) という新しい効率的なアルゴリズムを提供しています。
  論文  参考訳（メタデータ） (2020-10-12T17:51:19Z)

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

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