HNSWのMを4倍にしてもメモリが増えない理由：論文の隠しフラグと凡人の無駄な検証

無駄な努力の構造と今回の要点

ローカルLLMの連載において、パラメータを適当に弄って悦に浸る行為ほど生産性のないオナニー作業はない。

HNSWの原論文には「メモリ消費はMに比例する」と書かれている。ならばMを8から32へ4倍にすれば、索引サイズも4倍になるはずだと素朴に信じる。

だが、実際に測ってみればMを4倍にしたところでメモリは1.17倍しか増えない。

原因を調べもせず、ただ闇雲に数値を変更して「なぜか効果が出ない」と頭を抱えるのは、構造を理解せずガチャを回す養分と何ら変わらない。

パラメータを盲目的に信じるその姿勢が、いつまで経っても成果が出ない根本原因だと気づけ。

HNSWの構築時、近傍の間引きルールが働いている。

候補を近い順に見るとき、「すでに採用した隣のどれかが候補と自分より近いなら採らない」という規則でふるいにかけられる。

この規則はM本に達すれば打ち切るが、M本に届かなくても足りない分を足すことはしない。

つまり、Mは「張るリンクの本数」ではなく単なる「上限」に過ぎない。

データの局所的な形が許す方向の数しかリンクが生えないため、Mをいくら上げても平均次数は一切増えない。

ここで効いてくるのが、論文の擬似コードに埋め込まれた `keepPrunedConnections` という任意フラグだ。

このフラグを有効にすることで、間引きによって捨てられた候補を使い、M本に達するまで強制的に埋め戻すことができる。

でも、本当に稼ぐ奴やバグを潰す奴がやっていることは全く違う。