バイナリ量子化とは｜容量を1.6%まで削ったら、再現率が5.4%まで落ちた

容量を1.6%まで削ったら、再現率が5.4%まで落ちた

20,000件を丸めて測りました。1ビットで容量1.6%・再現率5.4%、8ビットで容量12.5%・再現率94.8%です。

バイナリ量子化がどれだけ容量を削り、何を失うのかを実際に測りました。用意したのは64次元のベクトル20,000件です。

丸めも検索も本当に実行しています。全探索の上位10件を正解として、丸めた値で検索した結果と重ねました。

function quantize(bits) {
  // 各次元を bits ビットに丸める。min/max は全体から取る
  let lo = Infinity, hi = -Infinity;
  for (const v of vecs) for (let d = 0; d < DIM; d++) { if (v[d] < lo) lo = v[d]; if (v[d] > hi) hi = v[d]; }
  const levels = Math.pow(2, bits) - 1;
  const q = vecs.map((v) => Uint8Array.from({ length: DIM },
    (_, d) => Math.round(((v[d] - lo) / (hi - lo)) * levels)));
  const de = (a) => Float64Array.from({ length: DIM },
    (_, d) => lo + (a[d] / levels) * (hi - lo));
  return { q, de, bytesPerVec: Math.ceil((DIM * bits) / 8) };
}

登録 20,000件（64次元）・上位10件・問い合わせ 200回
元の大きさ 1件あたり 512 バイト（64次元 × 8バイト）

1次元あたり  1件の大きさ  全体の大きさ  再現率   元に対する比
        1bit          8B        0.2 MB     5.4%          1.6%
        2bit         16B        0.3 MB     6.0%          3.1%
        4bit         32B        0.6 MB    42.7%          6.3%
        8bit         64B        1.2 MB    94.8%         12.5%

参考: 元のまま持つと全体で 9.8 MB

落ち方が一定ではありません。8ビットから4ビットに落とすと94.8%から42.7%で、半分以下になります。

崖のように落ちる

容量のほうは素直に半分ずつ減ります。ところが再現率は、4ビットと2ビットの間で42.7%から6.0%へ崖のように落ちます。

1ビットと2ビットの差はほとんどありません。5.4%と6.0%です。この領域では、どちらもほぼ当たっていないということになります。

8ビットの位置づけ

実用になりそうなのは8ビットです。容量が元の12.5%、つまり8分の1になって、再現率は94.8%を保っています。

9.8MBが1.2MBです。件数が10倍になっても、丸めた側は12MBで済みます。記憶上に載るかどうかが変わる規模になります。

そのまま結果にはしない

1ビットの5.4%という数字は、そのまま使えば使いものにならないという意味です。ただし使い方が違います。

pgvectorでも、並べ直しと組み合わせて、規模が大きくても索引を記憶上に保つ使い方が案内されています。粗く絞ってから、残った候補だけを元の値で並べ直す形です。

バイナリ量子化とは何をする手法なのか

各次元の値を粗い段階に丸めて保存します。容量を減らすのが目的で、精度は落ちます。

バイナリ量子化は、ベクトルの各次元を粗い段階に丸めて保存する手法です。極端な形では、各次元を0か1かの2段階だけにします。

何のために削るのか

目的は容量です。索引が記憶上に載るかどうかで、検索の速さは桁で変わります。

前の節の数字でいえば、9.8MBは載っても98GBは載りません。件数が増えたときに効いてくる話です。

他の削り方

1. 精度の低い型に変える。倍精度から半精度へ
2. 次元そのものを減らす。埋め込みの作り方を変える
3. 粗い段階に丸める。この記事の手法
4. 件数を減らす。古いものを外す

1番目についても案内があります。pgvectorでは、扱う量を小さくするために通常の型ではなく精度の低い型を使うとされています。

索引を作る時間も変わる

副次的な効果もあります。同じ文書では、規模が大きい場合に索引を小さくし、作る時間を短くする手段として挙げられています。

扱う量が減れば、索引を作る計算も軽くなります。データを入れ替えるたびに索引を作り直す運用では、ここが効いてきます。

落ちた再現率をどう取り戻すのか

粗い値で候補を絞り、残った候補だけを元の値で並べ直します。この工程が入る前提の手法です。

バイナリ量子化を実務で使うときは、丸めた値だけで結果を決めません。前の節の5.4%は、そのまま使った場合の数字です。

2段構えにする

組み合わせるのは並べ直しです。丸めた値で粗く候補を絞り、残った候補だけを元の値で計算し直して並べます。

pgvectorでも、並べ直しと組み合わせることで、規模が大きくても索引を記憶上に保てると案内されています。丸めた索引で速く絞り、正確さは元の値で確保する形です。

元の値も持っておく

ここに条件があります。並べ直すには元の値が要ります。丸めた値だけを保存して元を捨てると、この手が使えません。

つまり削れるのは索引の容量であって、保存する容量ではありません。記憶上に載せるものと、置いておくものを分けて考えることになります。

採用前に測る

再現率の落ち方はデータによって変わります。前の節の数字は、こちらで作ったデータでのものです。自分のデータで測り直してください。

測り方はANN再現率の記事で扱っています。全探索の結果を先に保存しておくのが前提になります。