論文の概要: Lychee: Certified Screening of Inverted Lists for High-Recall Vector Search

• arxiv url: http://arxiv.org/abs/2610.30697v1
• Date: Thu, 22 Oct 2026 04:10:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-24 02:08:44.209129
• Title: Lychee: Certified Screening of Inverted Lists for High-Recall Vector Search
• Title（参考訳）: Lychee:ハイリコールベクトル検索のための逆リストの認証スクリーニング
• Abstract要約: LycheeはGPUファイルによる検索で、同じリストのアンカーからしきい値のテンソルコア上の探索されたリストをスクリーニングし、少数の生存者のみ正確な距離を計算する。 我々は、Lycheeが、全精度で逆ファイル検索の答えである、探索されたリストの k 近いベクトルを正確に返すのに対し、探索されたリストの数に関係なく、クエリ毎に数百個の完全ベクトルを読み取ることを証明した。
• 参考スコア（独自算出の注目度）: 0.9179857807576733
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Nearest-neighbor search over embedding vectors matches faces against watchlists, transactions against known fraud patterns, and medical images against confirmed cases, where a missed neighbor is a missed threat, fraud, or diagnosis. Because an approximate index cannot report which queries lost a true neighbor, these applications require recall of 0.999 to 0.9999, at a cost far below that of exact search over billions of vectors. Inverted-file indexes reach high recall by probing more lists, but they read and score every probed vector at full precision, so that throughput falls in inverse proportion to the number of probed lists. Graph indexes saturate below these targets, whereas quantized lists must rerank their candidates with the full vectors. Our insight is to decide for almost every probed vector that it cannot enter the top k of the probed lists without reading the vector, through the certified lower bound of exact search by certified exclusion. This paper turns this insight into Lychee, a GPU inverted-file search that screens the probed lists on tensor cores under a threshold from anchors of the same lists and computes exact distances only for the few survivors. We prove that Lychee returns exactly the k nearest vectors of the probed lists, the answer of an inverted-file search at full precision, while it reads a few hundred full vectors per query regardless of the number of probed lists. On eleven datasets from one million to one billion vectors and against ten GPU and CPU baselines, Lychee is 9.7 to 117 times faster than IVF-Flat at equal recall with 200 probed lists on datasets of up to 100 million vectors. It also reaches recall levels that CAGRA and HNSW do not reach and outruns exact search by certified exclusion by 5 to 18 times above ten million vectors. On four GPUs, Lychee searches one billion vectors at recall 0.9999, 44.5 times faster than IVF-Flat on BIGANN-1B.
• Abstract（参考訳）: 埋め込みベクトルに関する最寄りの検索は、ウォッチリスト、既知の詐欺パターンに対する取引、および確認されたケースに対する医療画像と一致する。 近似インデックスは、真の隣人を失ったクエリを報告できないため、これらのアプリケーションは何十億ものベクトルの正確な探索よりもはるかに低いコストで0.999から0.9999のリコールを必要とする。 逆ファイルインデックスは、より多くのリストを探索することで高いリコールに達するが、全精度で全てのプローブベクトルを読み、スコアするので、スループットは、探索されたリストの数に反比例する。 グラフインデックスはこれらのターゲットより下位に飽和するが、量子化されたリストは候補を全ベクトルで再ランクしなければならない。 我々の洞察は、ベクトルを読まなければ、探究されたリストの上位 k に入ることができないほとんど全ての探究されたベクトルを、認定された排他的排他的検定による証明された検定の下限によって決定することである。 本稿では、この知見をLycheeに変換する。これはGPUの逆ファイル検索で、同じリストのアンカーからしきい値のテンソルコア上の探索されたリストをスクリーニングし、少数の生存者のみ正確な距離を計算する。 我々は、Lycheeが、全精度で逆ファイル検索の答えである、探索されたリストの k 近いベクトルを正確に返すのに対し、探索されたリストの数に関係なく、クエリ毎に数百個の完全ベクトルを読み取ることを証明した。 100万から10億のベクトルの11のデータセットと10のGPUとCPUベースラインに対して、LycheeはIVF-Flatの9.7倍から117倍高速で、最大1億のベクトルのデータセットに200のプローブリストがある。 また、CAGRAとHNSWは1000万ベクトルの5倍から18倍の精度で正確な探索を行なわないというリコールレベルに達する。 4つのGPU上で、LycheeはBIGANN-1B上のIVF-Flatの44.5倍の10億ベクトルをリコールで検索する。

関連論文リスト

• CertEx: Exact Visual Retrieval at Scale by Certified Exclusion [0.9179857807576733]
  エクササイズ$k$-nearest-neighbor (kNN)検索は、視覚検索、ほぼ重複検出、学習された表現の評価、LLMエージェントの記憶の増大を基盤としている。 厳密な探索は、各排除ベクトルが隣人にならないという証明しか必要としない。 このような証明は保守的である必要があるため、網膜が低解像度でシーン全体を検査するのと同様に、低い精度で検査することができる。
  論文  参考訳（メタデータ） (2026-10-15T06:16:08Z)
• Aperon Technical Report: Hierarchical No-Pointer Tangent-Local Search for High-Dimensional Approximate Nearest Neighbors [0.0]
  本稿では,Aperonベクトルメモリシステムのコアベクトルインデックスと候補生成フレームワークであるHNTLを提案する。 HNTLは、高次元空間を局所コヒーレント粒子に分割し、ベクトルを局所空間上の低次元接として表現することでこれを解決する。
  論文  参考訳（メタデータ） (2026-06-07T20:06:29Z)
• Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces [94.12116458306916]
  我々は、$q$の測度空間において、計量木は三角形の不等式のより強いバージョンを活用でき、正確な探索の比較を減らすことができることを示した。 任意の異方性測度を持つデータセットを$q$-metric空間に埋め込む新しい射影法を提案する。
  論文  参考訳（メタデータ） (2025-06-06T22:09:44Z)
• MicroNN: An On-device Disk-resident Updatable Vector Database [2.414259539583284]
  Micro Nearest Neighbour (MicroNN) は、低リソース環境におけるスケーラブルな類似性検索のための組込み近傍ベクトル検索エンジンである。 MicroNNは、アップデートとハイブリッド検索クエリを含む現実世界のワークロードのオンデバイスベクターサーチの問題に対処する。 MicroNNは、100位近くの近隣住民を回収するのに7ミリ秒未満で、公開されている100万規模のベクトルベンチマークで90%のリコールを行う。
  論文  参考訳（メタデータ） (2025-04-08T00:05:58Z)
• vCache: Verified Semantic Prompt Caching [95.16654660556975]
  本稿では,ユーザ定義エラー率保証を備えた最初の検証済みセマンティックキャッシュであるvCacheを提案する。 オンライン学習アルゴリズムを使用して、キャッシュされたプロンプト毎に最適な閾値を推定し、追加のトレーニングなしで信頼性の高いキャッシュ応答を可能にする。 我々の実験によると、vCacheは特定のエラー境界を一貫して満たし、最先端の静的な閾値と微調整された埋め込みベースラインより優れています。
  論文  参考訳（メタデータ） (2025-02-06T04:16:20Z)
• Vector search with small radiuses [10.880913075221361]
  本稿では,ベクトル検索結果に応じて難しい決定を下す必要がある場合に着目する。 本研究では,クエリー・ツー・ベクター距離に基づいて,範囲探索結果の値を厳密にモデル化できることを示す。 これにより、範囲探索の指標 RSM が得られ、これは原則的であり、エンドツーエンドの評価を行なわずに計算が容易である。
  論文  参考訳（メタデータ） (2024-03-16T00:34:25Z)
• Efficient k-NN Search with Cross-Encoders using Adaptive Multi-Round CUR Decomposition [77.4863142882136]
  クロスエンコーダモデルは、直接k-nearest neighbor(k-NN)サーチには不当に高価である。 本稿では,現実的に重要なトップk近傍の近似誤差を適応的に,反復的に,効率的に最小化するADACURを提案する。
  論文  参考訳（メタデータ） (2023-05-04T17:01:17Z)
• Precise Zero-Shot Dense Retrieval without Relevance Labels [60.457378374671656]
  仮説文書埋め込み(英: hypothetical Document Embeddings, HyDE)は、ゼロショット高密度検索システムである。 我々は,HyDEが最先端の非教師付き高密度検索器であるContrieverを著しく上回っていることを示す。
  論文  参考訳（メタデータ） (2022-12-20T18:09:52Z)
• IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
  分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。 クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。 我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
  論文  参考訳（メタデータ） (2021-03-17T23:13:25Z)
• SOLAR: Sparse Orthogonal Learned and Random Embeddings [45.920844071257754]
  我々は,高次元および超スパース埋め込みが,クエリ効率と精度の両面において,高密度な低次元埋め込みよりもはるかに優れていると論じている。 我々は,最大3つの公開データセット上で1.6万冊の書籍を検索し,複数ラベルの分類を行うタスクに対して,500K次元のSOLAR埋め込みを訓練する。 それぞれのタスクに対して,最大10倍の高速さで,各タスクの最先端のベースラインと比較して,精度とリコールの精度が向上する。
  論文  参考訳（メタデータ） (2020-08-30T17:35:35Z)

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

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