HOF SWIFT スケーラブル情報検索 ― モジュール型・ハードウェア対応の類似検索アーキテクチャ
著者: Asher Bond (asher.bond@distillative.ai)
要旨
大規模な埋め込み集合に対する類似検索は、検索拡張生成(RAG)[1] とベクトルデータベースを支える検索基盤である。10億規模ともなればこれはシステム上の問題であり、その基準点は FAISS [2] であって、厳密なアテンションの計算コストは FlashAttention [3] のような IO 対応カーネルが処理する。本稿は HOF SWIFT スケーラブル情報検索(SIR) を提示する。すなわち、類似検索を合成可能な五つの段階 ― Score・Weight・Isolate・Fit・Transform(SWIFT)― へ分解し、関数型プログラミングの伝統 [4, 5, 6] に則って原子的操作の上の高階関数として表現し、各段階をそれを最も高速に実行するハードウェア標的(CPU/GPU/TPU)へ対応づけたものである。本アーキテクチャは設計である。そのスケーリングは、明示した定数の下での例示的な算術として与える。そして本設計が切り出す未解決の問いは明確である ― コントローラが、タスクに関連する疎な部分集合を、クエリあたりのコストをコーパスではなく当該部分集合に追従させられるほど正確かつ安価に選択できるか、という問いである。FAISS [2] は、本設計がそれに照らして測定されるべく築かれたベースラインである。
1. 序論
埋め込み集合に対する検索は、セマンティック検索・推薦・RAG [1] を支える。網羅的な最近傍探索は、次元 D の N 個のベクトルに対しクエリあたり O(N·D) を要する。実運用上の解は近似最近傍(ANN)インデクシング ― 転置ファイル、直積量子化、グラフインデックス ― であり、これらは FAISS [2] において統合され GPU で加速されている。別途、Transformer 生成器 [7] における厳密なアテンションの二次的コストは、FlashAttention [3] のような IO 対応カーネルによって近似なしに削減される。これらは、検索アーキテクチャが対置される、測定済みのベースラインである。SWIFT SIR は検索パイプラインを因数分解し、各段階を独立に差し替え可能とし、独立にハードウェア上へ配置できるようにする ― そして唯一の難所である疎な候補選択を、インデックスの内へ畳み込むのではなく明示的に名指しする。
2. 関連研究
近似最近傍探索。 GPU 加速による10億規模の類似検索こそ FAISS が築かれた目的である [2]。FAISS と、それが取りまとめる IVF/HNSW/PQ 系は、参照すべきベースラインである。SWIFT SIR はその成果を、ハードウェアへ配置された段階へと再編する。主張は因数分解であって、先験的に高速なインデックスではない。
効率的アテンション。 FlashAttention [3] は、Transformer バックボーン [7] の上で、メモリ/IO 効率の良い 厳密な アテンションを実現する、公表済みかつベンチマーク済みの技術であり ― Transform 段階が基礎とする先行技術である。
検索拡張生成。 RAG [1] は検索器と生成器を結合する。検索の品質は生成の忠実度を上限づけ、根拠づけを施してもなおハルシネーションは残存する [8]。これが、より強力な検索器が報われるシステム的文脈である。
関数合成。 パイプラインを、原子的操作の上に合成された高階関数として表現することは、Backus [4]、Hughes [5]、Strachey [6] が定式化した関数型プログラミングの伝統である。本稿の寄与は、その合成を、ハードウェア分割された検索パイプラインへ適用する点にある。
検証のための信号検出。 パイプラインが候補を受理あるいは棄却する箇所において、信号検出理論 [9](d′、基準 β)はその判断へ測定可能な構造を与える ― これは SWIFT の検証段階における応用精神物理学であり、Score と Isolate の閾値を統べる弁別閾(JND)およびウェーバー・フェヒナーのスケーリングと並ぶものである。
3. SWIFT 分解
類似検索は、合成された五つの段階として表現される。各段階は入力・処理・出力の変換 [4, 5] であり、独立に差し替え可能で、独立にそれぞれ最適なハードウェア標的へ配置される。
- Score(S) ― 入力: クエリ埋め込み q、候補集合。処理: 密な全対積ではなく、疎あるいはブロック単位のスコアリングパス。出力: スコア付けされた候補部分集合。
- Weight(W) ― 入力: スコア付き部分集合。処理: 文脈関連度による再重み付け。出力: 重み付けされた候補。
- Isolate(I) ― 入力: 重み付けされた候補。処理: 最高関連度の領域へのルーティング/枝刈り。出力: 小さな作業集合。
- Fit(F) ― 入力: 作業集合。処理: 階層的な文脈ウィンドウへの集約。出力: 文脈に適合させた結果。
- Transform(T) ― 入力: 適合済みの結果。処理: 最終化(マスキング、混合精度)。出力: ランク付けされた検索結果。
合成 Transform ∘ Fit ∘ Isolate ∘ Weight ∘ Score が高階関数であり、各段階は原子的関数 [5, 6] である。この因数分解は、パイプラインの各段階をハードウェアごとに配置可能とし、疎選択の工程(Score)を第一級かつ差し替え可能な構成要素とする ― ANN インデクシングが解くために存在するその工程を、ここでは隠すのではなく露わにするのである。
4. 例示的スケーリング
効率性の論拠は算術である ― Score 段階が疎な部分集合 S ≪ N を選択し、後続の段階が固定の top-k 上で動作するなら、クエリあたりの仕事量は N ではなく S に追従する。下表は [ILLUSTRATIVE] である ― 選定した定数の下での算術(埋め込み次元 D=768、疎割合 S=N の 0.1%、top-k=1000)。
[ILLUSTRATIVE — arithmetic under the stated constants]
| データセット | N(埋め込み数) | 疎部分集合 S(0.1%) | Score 段階の演算数(S·D) |
|---|---|---|---|
| 1 GB | 10⁷ | 10⁴ | ≈ 7.7 × 10⁶ |
| 1 TB | 10¹⁰ | 10⁷ | ≈ 7.7 × 10⁹ |
| 1 PB | 10¹³ | 10¹⁰ | ≈ 7.7 × 10¹² |
This table lays out データセット, N(埋め込み数), 疎部分集合 S(0.1%), Score 段階の演算数(S·D) across 3 rows.
この節約は 0.1% という疎割合の性質であり、それは残余に触れることなくスコアリングに値する 0.1% を見出す Score 段階を前提としている。その選択こそが実質的な問題であり、SWIFT の因数分解は、それをインデックスに埋もれた仮定ではなく、名指しされ測定可能な段階へと変えるものである。したがって効率性の主張は条件付きかつ鋭利である ― コントローラが低いオーバーヘッドでタスク関連の部分集合を予測するなら、検索コストは S に支配される。これを決着させる測定は、共有コーパス上で FAISS [2] に対して行われる。
5. 検証が根拠づけられる場所
検索パイプラインは候補に対し受理/棄却を判断し、その判断は検出問題である。信号検出理論 [9] はそれに構造を与える ― 再現率/適合率のトレードオフは ROC 曲線に沿った基準(β)の移動であり、検索器の品質は感度(d′)と閾値とに分離される。これが SWIFT の検証段階の測定可能な核心であり ― アーキテクチャが数値と出会う地点である。
証拠と適用範囲
SWIFT SIR は、切り出された検証可能な問いを備えた設計である。スケーリングの数値は明示した定数の下での例示的算術である。判断層は信号検出理論 [9] に根拠づけられる。そして効率性の主張を決着させる直接対決は、共有コーパス上での SWIFT-SIR 対 FAISS [2] の比較(両者の top-k 再現率とレイテンシ)であり、利用可能な計算資源によって制約される。FAISS がベースラインであり、Score 段階が帰結を決める変数である。
References
- Patrick Lewis et al. (2020). Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks. Advances in Neural Information Processing Systems (NeurIPS). arXiv:2005.11401. [RAG]
- Jeff Johnson et al. (2019). Billion-Scale Similarity Search with GPUs. IEEE Transactions on Big Data. arXiv:1702.08734. [FAISS]
- Tri Dao et al. (2022). FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness. Advances in Neural Information Processing Systems (NeurIPS). arXiv:2205.14135.
- John Backus (1978). Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs. Communications of the ACM. [1977 ACM Turing Award Lecture]
- John Hughes (1989). Why Functional Programming Matters. The Computer Journal.
- Christopher Strachey (2000). Fundamental Concepts in Programming Languages. Higher-Order and Symbolic Computation. [Reprint of 1967 lecture notes]
- Ashish Vaswani et al. (2017). Attention Is All You Need. Advances in Neural Information Processing Systems (NeurIPS). arXiv:1706.03762.
- Ziwei Ji et al. (2023). Survey of Hallucination in Natural Language Generation. ACM Computing Surveys. arXiv:2202.03629.
- David M. Green & John A. Swets (1966). Signal Detection Theory and Psychophysics. Wiley.
