HN 日本語サマリー

← 一覧へ戻る
AI・機械学習

Turbovec – Rustにおけるベクトル検索のためのGoogleのTurboQuant

Turbovec – Google's TurboQuant for vector search in Rust (github.com)

282 pointsby fittingopposite32 コメント

要約

Turbovecは、GoogleのTurboQuantアルゴリズムを基盤としたRust製のベクトル検索ライブラリです。このライブラリは、大規模なドキュメントコーパスを大幅に圧縮し、FAISSよりも高速な検索性能を実現します。オンラインでのベクトル追加や、CPUアーキテクチャに最適化されたSIMD検索、差分のみを保存するインクリメンタルセーブなどの機能を備えています。

全文翻訳

Python

[画像: turbovec — Google's TurboQuant for vector search]

[画像: License] [画像: PyPI version] [画像: crates.io version] [画像: TurboQuant paper]

Python · Rust · How it compares · When to use something else · API reference · Benchmarks


1000万個の768次元ベクトル(float32)は31 GBのRAMを消費しますが、turbovecはそれを4 GBに収め、同等の再現率でFAISSより4.4倍高速に検索できます。

turbovecは、PythonとRust向けのインプロセスベクトルインデックスです。Google ResearchのTurboQuantを使用して、各ベクトルを次元あたり2または4ビットで格納し、エージェント最適化されたSIMDカーネルでその圧縮形式を直接検索します。

  • 高速。 ARMおよびx86で、4ビットではFAISS FastScanの4.4倍、2ビットでは2.2倍高速です。段階的な検索により、1ビットプレーンをスキャンし、候補リストを正確に再スコアリングします。
  • 低メモリ。 4ビットではfloat32の7.8倍、2ビットでは15.5倍小さく、FAISSと同等の再現率です。
  • オンライン。 トレーニングステップや再構築は不要です。コードブックはデータからではなく、数学から導き出されます。ベクトルを追加するとすぐに検索可能になり、マイクロ秒単位で削除できます。
  • 増分。 sync(path)は、前回の呼び出し以降に変更された部分のみを書き込みます。1回のfsyncで、どのバイトでもクラッシュセーフであり、インデックスのサイズに関わらずミリ秒単位で完了します。
  • ローカル。 サービスではなくライブラリです。プロセス外に出るものはありません。オープンソースの埋め込みモデルと組み合わせることで、完全にオフラインのスタックを構築できます。
  • フィルタリング。 IDの許可リストまたはビットマスクを渡すことができます。カーネルは、フィルターで除外されたものをスキップし、許可されたセットから最大k個の結果を返します。
pip install turbovec
import numpy as np
from turbovec import TurboQuantIndex

vectors = np.load("embeddings.npy").astype(np.float32)   # shape (n, 1536)

index = TurboQuantIndex(dim=1536, bit_width=4)
index.add(vectors)

scores, indices = index.search(vectors[:1], k=5)
print(indices)         # [[    0 86544  3385 84492 24967]]   int64 slot positions
print(scores.shape)    # (1, 5)                             float32 inner products

index.sync("index.tv")                  # first sync writes the file
index.add(more_vectors)
index.sync("index.tv")                  # later syncs write just the change, durably

index = TurboQuantIndex.load("index.tv")   # loads either a sync'd or a write() file

入力は形状(n, dim)の2次元float32配列です。他のデータ型はサイレントに変換されず、エラーが発生します。スコアは内積なので、コサイン類似度が必要な場合はベクトルを正規化してください。

削除後も有効なIDが必要な場合は? IdMapIndexは、独自のuint64 IDで全てをキーイングします。

from turbovec import IdMapIndex

index = IdMapIndex(dim=1536, bit_width=4)
index.add_with_ids(vectors, ids)               # ids: uint64 array, one per row

scores, ids = index.search(query, k=10)        # your ids, not slot positions
index.remove(1002)                             # O(1)

# Filter: only ids another system approved — a SQL predicate, an ACL, a time window.
allowed = np.array([1001, 1003, 1042], dtype=np.uint64)
scores, ids = index.search(query, k=10, allowlist=allowed)   # shape (1, min(k, 3))

フレームワーク統合は、各フレームワークのインメモリストアのドロップイン置換です。パブリックサーフェス、永続化、リトリーバー配線は同じです。LangChain (pip install turbovec[langchain]) · LlamaIndex (turbovec[llama-index]) · Haystack (turbovec[haystack]) · Agno (turbovec[agno])。

Rust

cargo add turbovec
use turbovec::{IdMapIndex, TurboQuantIndex};

let mut index = TurboQuantIndex::new(1536, 4)?;
index.add(&vectors);                          // &[f32], row-major, n × 1536
let results = index.search(&queries, 10);     // scores and slot indices, nq × 10
index.write("index.tv")?;
let index = TurboQuantIndex::load("index.tv")?;

let mut ids = IdMapIndex::new(1536, 4)?;
ids.add_with_ids(&vectors, &[1001, 1002, 1003])?;
let (scores, found) = ids.search(&queries, 10);
ids.remove(1002);

Rust APIはPython APIとほぼ同じです。docs/api.mdは、ファイル形式、sync()、キャリブレーション、段階的検索を含め、両方をカバーしています。

How it compares

全データ:100KのOpenAI埋め込み(d=1536およびd=3072)とGloVe(d=200)、k=64、1Kクエリ、5回の実行の中央値。GCP c4a-standard-8(ARM)およびc3-standard-8(x86)で、同等のビットレートのFAISSと比較。スクリプト、生のJSON、およびすべてのチャートはdocs/benchmarks.mdにあります。

[画像: Search speed, ARM, multi-threaded: turbovec vs FAISS IndexPQFastScan]

[画像: Recall at k on OpenAI d=1536: turbovec vs FAISS IndexPQ at the same bit rate]

turbovecFAISS
Search, 4-bit3.8–5.1× faster across the eight cells (ARM 4.0×, x86 4.9×)IndexPQFastScanevery cell
Search, 2-bit1.8–2.5× faster (ARM 2.05×, x86 2.35×)IndexPQFastScanevery cell
Recall@1, OpenAI0.959 / 0.981 at 4-bit, 0.901 / 0.931 at 2-bit (d=1536 / d=3072)0.966 / 0.971, 0.876 / 0.911IndexPQ, m matched to bit rate
Recall@1, GloVe d=2000.860 at 4-bit, 0.572 at 2-bit0.842, 0.565IndexPQ, m matched to bit rate
Memory, d=153675 MB at 4-bit, 38 MB at 2-bit586 MB float327.8× / 15.5×
Single add()7.9–21.7 µs6.3–12.6× slowerinto a trained, populated index
remove(id)1.4–5.8 µs0.19–1.03 sFAISS repacks all codes per call
Whole-file save1.0–1.4× slower than FAISSwrite_indexturbovec fsyncs and renames atomically
Load → first search1.0–1.5× slower than FAISSread_index40 vs 31 ms at d=1536 4-bit on x86

どちらもOpenAIコーパスでは常に最初の8結果以内に真の最近傍を返します。完全なスイート(すべてのチャート、生のJSON、および再実行用のスクリプト)はdocs/benchmarks.mdにあります。

When to use something else

  • グラフインデックスが必要な場合。 turbovecはすべてのベクトルをスキャンします。10万ベクトルでクエリコストはベンチマークボックスの全8コアで0.13〜0.25 ms、1スレッドで0.5〜2.0 ms(k=64、1000クエリバッチ、d=1536〜d=3072)であり、コストはコーパスのサイズに比例して増加します。厳密なレイテンシの制約下で数億のベクトルを扱う場合、HNSWまたはIVFインデックスが適しており、turbovecはそれらではありません。
  • 正確なfloat結果が必要な場合。 量子化は損失を伴います。OpenAIコーパスでは、4ビットでトップ結果がfloatの正解と96〜98%一致し(2ビットでは90〜93%)、常に返される最初の8件に含まれます。GloVe d=200のような低次元埋め込みは、より多くの損失が発生します。自身のデータサンプルで再現率を確認してください。
  • サーバーが必要な場合。 turbovecはファイル形式を持つライブラリです。ネットワークAPI、レプリケーション、マルチテナントサービスはありません。上記の統合は、それらを持つスタックにどのように組み込まれるかを示しています。
  • ベクトルが8の倍数でなく、16,384より大きい場合。 これらは次元の制限です。ビット幅は2と4です。

How it works

各ベクトルを正規化し、その長さを格納します。各座標が入力に関わらず既知の分布に従うように、各ベクトルを1つの共有ランダム直交行列で回転させます。その後、その分布のために計算されたLloyd-Maxコードブック(2ビットで4レベル、4ビットで16レベル)で各座標を量子化し、ビットパックします。検索時には、クエリは一度回転され、SIMDルックアップテーブルを使用してコードブックに対してスコアリングされます。エンコード時に固定されたベクトルごとのスカラーが、量子化が導入する内積バイアスを除去します。オプションのワンショットcalibrate(sample)は、漸近分布から外れるデータ(低次元および単語ベクトルの埋め込みが最も効果を得る)に対して、座標ごとに2つのスカラーを適合させます。

数学と参照を含む完全な解説は、docs/how-it-works.mdにあります。

Building from source

Python wheelとRust crate

pip install maturin
cd turbovec-python && maturin build --release && pip install target/wheels/*.whl
cargo build --release

x86_64ビルドは.cargo/config.toml経由でx86-64-v2(SSE4.2、Nehalem 2008+)をターゲットとします。AVX-512およびAVX2カーネルは#[target_feature]でゲートされ、実行時にis_x86_feature_detected!で選択されるため、1つのバイナリがどこでも実行され、CPUが持つ機能を使用します。ベンチマークスイートの実行については、docs/benchmarks.mdで説明されています。

References