コンテンツにスキップ

LSH Cascade PoCプロジェクトの紹介

CMScom Labの2つ目の記事として、現在進行中のLSH Cascade PoCについて紹介します。 1月の最終週に集中的に実験を行い、良い成果が得られたため、その概要をまとめます。

モチベーション

今回のプロジェクトの最大のモチベーションは、「ZopeのIndex技術を活用して、低コストでベクトル検索を実現したい」という点にあります。

一般的に、ベクトル検索やセマンティック検索を行うには、専用のVector DB（Pinecone, Milvus, Qdrantなど）や、pgvectorのような拡張機能を備えたRDBMSが必要になります。しかし、すべてのプロジェクトでそのようなインフラを用意できるわけではありません。特にコスト制約が厳しい場合や、既存のインフラを変更できない場合があります。

我々は、この技術の先にFirestoreなどのNoSQL系データベースへの応用を見据えています。これが実現できれば、専用のベクトルDBが準備できないシチュエーションでも、既存のデータストアを活用して高度な検索機能を提供できるようになります。

背景と課題

セマンティック検索（意味による検索）は非常に強力ですが、以下の課題がありました。

  1. コストの問題: 全ての案件で専用のベクトルDBを導入するのはオーバースペック、または予算オーバーになることが多い。
  2. 既存技術（HNSWなど）とのミスマッチ: 高速な近似近傍探索（ANN）アルゴリズムとしてHNSWが有名ですが、これを単純にNoSQLや従来のKVS上で実装しようとすると、全探索に近い処理が必要になり、読み取りコストが跳ね上がってしまいます。

アプローチ：古典技術「LSH」の再評価

そこで注目したのが、LSH (Locality Sensitive Hashing) という技術です。 これは、高次元のベクトルを、類似性が保たれるようにハッシュ値（ビット列）に変換する、次元削減と量子化の手法です。

私たちのアイデアは以下の通りです：

  1. EmbeddingベクトルをLSHでビット列に変換する。
  2. 生成されたビット列をさらにチャンク（小さな塊）に分割する。
  3. このチャンクを利用することで、SQLの SELECT やNoSQLのフィルタリング機能といった、既存の枯れたインデックス技術を活用して絞り込みを行う。

直面したハードル

アイデアはシンプルでしたが、実装には2つの大きな壁がありました。

  1. 精度の問題: LSHのランダム射影（Random Projection）を単純に適用しただけでは、現代のEmbeddingベクトルの意味情報を十分に表現できず、検索精度が出ませんでした。
  2. チャンク化の工夫: ビット列を単純に切るだけでは、類似したベクトルを効率的に拾い上げることができませんでした。

実験結果

1月の最終週、私たちはこれらの課題を解決するために40パターン以上の実験を繰り返しました。 パラメータの調整、射影方法の工夫、チャンク分割のロジックなど、様々なアプローチを試行錯誤しました。

その結果、実験は成功しました。 既存のインデックス技術を活用できる形でありながら、十分に実用的な精度で類似検索が行える目処が立ちました。

導き出された解決策と成果

この実験の裏には、使用した埋め込みモデル（E5）の「異方性（Anisotropy）」の問題なども絡んでおり、単純な手法では精度が出にくいという課題がありました。 これに対し、ITQ (Iterative Quantization) を用いたLSHと、ビット列のチャンク化に Overlap（重ね合わせ） を導入することで解決を図りました。

結論:

E5-baseモデル（768次元）に対して、ITQ-LSHとOverlapフィルタを組み合わせた高速近似検索の最適パラメータを特定しました。 これにより、40万件規模のデータセットにおいて、検索候補を 87.5%削減 しつつ、 Recall 83.7% を維持することに成功しました。

選択されたパラメータ構成:

  • モデル: intfloat/multilingual-e5-base
  • 埋め込み次元: 768
  • ITQビット数: 128 bits
  • Overlap設定:
    • セグメント幅: 8 bits
    • ストライド: 4 bits
    • セグメント数: 31

達成された性能指標:

  • データ規模: 399,029件
  • Step1候補数: 約50,000件（削減率 87.5%）
  • Recall@10 (limit=1000): 83.7%
  • ベースラインRecall: 88.8%（Overlapなし）
  • Recall低下: -5.1pt

今回の実験の詳細は、以下のJupyter Notebook（日本語）で公開しています。

技術的な深掘りについては、また別のエントリーで詳しく解説したいと思います。

LSH Cascade PoCの実験まとめ

今後の展望

実験室レベルでのPoCは成功しました。次は、実際の現場で使えるかどうかを検証するための、より具体的なPoCを行う予定です。 実際のデータセットや、Firestoreなどの具体的なデータストアを用いた検証を進めていきます。