HN 日本語サマリー

← 一覧へ戻る
プログラミング

Lumeの仕組み: 検索のプリミティブ

How Lume Works: The Retrieval Primitives (deepbluedynamics.com)

3 pointsby kordlessagain0 コメント

要約

Lumeは、GitHubでオープンに開発されているRust製のハイブリッド検索エンジンです。このシステムは、BM25、GTR-T5ベクトル、およびエンティティグラフという3つの独立したプリミティブを使ってドキュメントをランク付けし、クエリから証拠までの全ステップを検査可能にすることを目指しています。ローカルファースト、レイヤード、監査可能という設計原則に基づき、エージェントシステムにおける検索を「魔法のステップ」として扱わないことを目指しています。

全文翻訳

Lumeの仕組み:検索プリミティブ

[画像: Lume retrieval pipeline - BM25, dense vectors, and the entity graph]

Lume は、Steve Harris と私が github.com/DeepBlueDynamics/lume でオープンに開発してきたRust製のハイブリッド検索エンジンです。これは小さなCLIとMCPサーバーで構成され、BSD-3ライセンスが付与されており、「エージェントが質問した際に、クエリから証拠までのすべてのステップが検査可能である」という譲れないアイデアを中心に構築されています。

LumeはMarkdown、ソースコード、PDF(小さなPythonエクストラクター経由)をインデックス化し、3つの独立したプリミティブ — フィールド認識BM25、Shivvr経由の密なGTR-T5ベクトル、および有意性スコア付きエンティティグラフ — でそれらをランク付けします。レキシカルコアとグラフは完全にローカルで実行され、密なベクトルのみが外部に接続しますが、そのエンドポイントはデフォルトで localhost です。不透明な「ランキングを返す検索ボックス」は存在せず、すべてのスコアには名前、ファイル、および調整ノブがあります。

この記事では、現在のツリーへの行レベル参照を含め、Lumeの検索コアをエンドツーエンドで解説します。エージェントシステムを構築していて、検索を魔法のようなステップとして扱うのにうんざりしているなら、この記事はあなた向けです。

設計を説明するために、まずいくつかの原則を挙げます。

  • ローカルファースト。 レキシカル検索とエンティティグラフは完全にローカルで実行されます。密なベクトルは SHIVVR_BASE_URL を介してShivvrから取得され、デフォルトはローカルエンドポイントです。
  • モノリシックではなくレイヤード。 BM25、セマンティック、グラフは、独自のスコアを持つ独立したシグナルです。それらのブレンドは1行で記述され、各入力は交換可能です。
  • 監査可能。 エンジンは、何がプルーニングされ、何がランク付けされ、なぜ残りが却下されたのかを出力します。

0. 検索の単位:セクション

LumeはMarkdownをインデックス化し、# ヘッダーでセクションに分割します(src/bm25.rs:211 の parse_markdown)。Section(src/bm25.rs:106)は、すべてがランク付けされる原子単位です。

pub struct Section {
    pub title: String,
    pub body: String,
    pub line_number: usize,
    pub filename: Option<String>,
    pub entities: Vec<String>,   // resolved named entities, for the graph
}

タイトルと本文は、別々の統計を持つ別々のフィールドです。この区別は、スコアリングにすぐに現れます。インデックス全体は、フィールドごとの用語頻度マップ、ドキュメント頻度、フィールド長、ローリングビットマップ投稿リスト、プライム/ゲーデル署名フィルター、およびグラフに供給されるエンティティ投稿リストとしてメモリ内に存在します(src/bm25.rs:147 の Bm25Index)。

1. プリミティブ:フィールド認識BM25

レキシカルコアは、3つの選択可能なバリアントを持つフィールド認識BM25です。チューニングのデフォルト(src/bm25.rs:125 の Bm25Params)は意図的にクラシックです。

Self { k1: 1.2, b: 0.75, delta: 1.0, title_weight: 2.0, body_weight: 1.0 }

k1 は用語頻度の飽和を制御し、b は長さ正規化を制御します。唯一の意見的な選択はtitle_weight: 2.0です。これは、調整係数が適用される前に、タイトルへのヒットが本文へのヒットの2倍の寄与をすることを意味します。これは有用ですが、クエリのトークンが広範な場合に章のタイトルを過度に重視する可能性があります。これを法則ではなくノブとして扱ってください。

IDFは標準的な平滑化形式で、ゼロで床打ちされ、各用語の寄与はフィールドごとに計算され、フィールドの重みで合計されます(src/bm25.rs:728 の calculate_bm25_term_score)。

let len_normalization = 1.0 - b + b * (doc_len / avgdl);
match variant {
    SearchVariant::Classic => idf * (tf * (k1 + 1.0)) / (tf + k1 * len_normalization),
    SearchVariant::Plus    => idf * ((tf*(k1+1.0))/(tf + k1*len_normalization) + params.delta),
    SearchVariant::L       => { let s = tf / len_normalization;
                                idf * (s*(k1+1.0))/(s + k1) },
}
// total_score += title_weight * title_score + body_weight * body_score;  (src/bm25.rs:635)
  • Classic は教科書的なBM25です。
  • Plus は delta の床を追加し、一致した用語が決して何も寄与しないことを防ぎ、長いドキュメントに対するBM25の過剰なペナルティに対抗します。
  • L は長さ正規化を飽和の内側に移動させ、非常に長いドキュメントを平滑化します。

LumeはデフォルトでClassicを実行します(src/main.rs:1430)。

2. 2段階プルーニング:ローリングユニオン、次にゲーデル署名

すべてのクエリに対して、本の1,926セクションすべてをBM25スコアリングしたくはありません。Lumeのsearch(src/bm25.rs:445)は2段階です。

ステージ1 — 候補収集。 クエリ用語のローリングビットマップ投稿リストのユニオンを取ります。これは少数のビットセットOR演算で、コーパスをクエリ用語のいずれかを含むセクションに即座に絞り込みます。

// src/bm25.rs:460
let mut candidate_set = MiniRoaring::new();
let mut first = true;
for q_tok in &query_tokens {
    if let Some(list) = self.posting_lists.get(&q_tok.bytes) {
        if first {
            candidate_set = list.clone();
            first = false;
        } else {
            candidate_set = candidate_set.union(list);
        }
    }
}

ステージ1b — ゲーデルタグ署名プルーニング。 クエリタガーがエンティティを認識する場合、各候補セクションは素数分解された署名フィルター(src/fast_retrieval.rs:449 の PrimeFilter::test_tag_prime、src/bm25.rs:538 で評価)に対して検証されます。既知の各タグ出力は素数にマッピングされ、セクションのタグ署名はそれらのタグ素数の積であるため、包含は割り算によってチェックされます。未知のクエリタグは意図的にダミーの素数を受け取り、失敗します。失敗した候補は、より重いスコアリングの前に TagSignatureMismatch としてドロップされます。

ステージ2 — 重いスコアリング は、生存者に対してのみ実行されます。そしてエンジンは、漏斗の形状をstderrに出力します(src/bm25.rs:557)。

[Two-Stage Pruning] Pruned candidate space from 1926 to 302 (roaring generated: 609) sections in 54.70µs
Candidates: 609
Ranked: 302
Rejected:
  TagSignatureMismatch: 307
  ...

そのアカウンティングは装飾ではありません。クエリが間違ったものを返したときに最初に読むものです。

3. クエリ衛生:ストップワードと調整

品質に大きな影響を与える2つの小さなプリミティブがあります。

クエリ側のストップワードフィルタリング(src/bm25.rs:98 の filter_query_stopwords)。機能語や疑問詞は、インデックスからは決して削除されず、クエリのみからストリップされます。これがないと、「how does Dantès know Mercédès」は how/does/know によって支配され、無関係なセクション(“How a Gardener…”というタイトルの章)に一致してしまいます。セーフティネット:すべてのトークンがストップワードの場合(「how are you」)、結果を得られるように元のトークンは保持されます。

調整係数(src/bm25.rs:638)。より多くの異なるクエリ用語に一致するドキュメントは、単一の一般的な用語を繰り返すドキュメントよりも優れているべきです。Lumeは、カバレッジベースの係数でスコアを乗算します。

let coverage = matched_terms.len() as f64 / num_distinct as f64;
let coord = COORD_FLOOR + (1.0 - COORD_FLOOR) * coverage;   // COORD_FLOOR = 0.5
total_score *= coord;

したがって、3つのクエリ用語すべてに一致するセクションはスコアの100%を維持し、3つ中1つに一致するセクションは約⅔を維持します。単一用語クエリでは coverage == 1.0 なので、通常のルックアップは変更されません。これはハードなANDではなく、穏やかな後押しです。

4. プリミティブ:密なベクトル(ローカルGTR-T5)

レキシカル検索は語彙のギャップを埋めることができません。「starved to death」(飢え死に)と「gastroenteritis」(胃腸炎)のような場合です。それがセマンティックプリミティブの仕事です。

Lumeは、Shivvr を介してテキストを768次元GTR-T5ベクトルに埋め込みます。デフォルトのベースURLは http://localhost:8085(src/hybrid.rs:777)であり、リクエストにはサービストークンが必要です(src/hybrid.rs:784)。専用の埋め込みエンドポイントはないため、embed_text(src/hybrid.rs:43)は一時的なスクラッチストアにインジェストし、レスポンスから直接ベクトルを読み取ります。

// 768-d GTR-T5 ("organize") vector, asserted on the way out:
if emb.len() != 768 { return Err(format!("Expected 768-d GTR-T5 vector, got {}", emb.len())); }

インデックス作成時に、セクションはセマンティックセッション(src/hybrid.rs:581 の ensure_semantic_session)にプッシュされます。巧妙な部分は増分性です。各セクションにはコンテンツハッシュ(src/hybrid.rs:407 の section_hash)が割り当てられ、これがリモートチャンクIDとして使用されます。行番号は意図的に除外されているため、セクションの移動は再埋め込みを強制しません。再インデックスはハッシュで差分を取り、変更されたものだけを補充します。一致するコーパスフィンガープリントはノープランです。クエリ結果もキャッシュされます(.lume-semantic-cache.json)。

クエリ時、query_semantic_search(src/hybrid.rs:637)はShivvrに n=60 個の近傍を要求します。インデックスがセマンティックベクトルなしで構築された場合、またはトークンが見つからない場合、検索はレキシカルBM25にクリーンに低下し、それを伝えます。alpha > 0 のリクエストがレキシカルのみのインデックスに対して行われた場合、レキシカルのみであると通知されます(src/main.rs:1389)。

5. プリミティブ:セマンティック知識グラフ(共起数ではなく有意性)

3番目のシグナルは構造的です。Lumeは、エンティティの共起グラフをペアワイズローリングビットセットの交差から構築します。「ものの数のカウント」(src/graph_search.rs:1)。それ自体は書き込み専用のエクスポートですが、graph_search はそれをクエリ時のランキングシグナルに変換し、完全にローカルです。

微妙で重要な点は、エッジの重み付け方法です。生の共起やJaccardでさえ、広範なハブ(どこにでも現れるエンティティがすべてと共起する)を報酬します。Lumeはデフォルトで、代わりに有意性スコアを使用します(src/semantic_mesh.rs:558 の cooccurrence_relatedness)。n 個のドキュメントのうち、Aが a 個に、Bが b 個に、両方が k 個に現れるとします。独立性の期待値 E = a·b/n をzスコアとして観測された k と比較し、ダイナミックレンジを維持するために対数圧縮してから tanh で圧縮します。

let expected  = a * b / n;
let variance  = expected * (1.0 - a/n) * (1.0 - b/n);
let z         = (k - expected) / variance.sqrt();
let compressed = z.signum() * (1.0 + z.abs()).ln();   // keep z=10 vs z=100 distinct
(compressed / 3.0).tanh()                              // -> [-1, 1]; negative = avoidance

結果は [-1, 1] に収まります。正は実際の関連性、負は回避(確率より低い共起をするエンティティ)を示します。これはTrey Graingerのフォアグラウンド対バックグラウンドSKG関連性をペアワイズケースに還元したものです。回帰テストがその動作を固定しています。真のペアリング(edmond–dantès)は、ハブが完璧なJaccardオーバーラップを持っていても、広範なハブよりも優位になります(src/graph_search.rs:305)。--scoring jaccard でレガシーJaccardを選択することもまだ可能で、エッジ weight()(src/semantic_mesh.rs:532)が選択され、負の有意性は 0 にクランプされるため、回避がブーストすることはありません。

ウォーク自体(src/graph_search.rs:154 の compute_skg_scores):

  1. クエリのエンティティを、最長ファーストでn-gramをスライドさせることで解決します(「edmond dantes」が格納されている「edmond dantès」に一致するように)。max_ngram = 4。
  2. それらを重み 1.0 でシードします。トップ-k(8)の最も強い近傍に1ホップウォークし、各近傍は decay * weight(decay = 0.5)を運びます。シード全体で最大値を取ります。これにより、共有ハブ近傍が合計されて支配的になるのを防ぎます。
  3. エンティティ投稿リストからセクションごとの質量を蓄積し、[0, 1] に正規化します。

[動画]

6. ブレンド:1行の乗算

3つのシグナル — レキシカル、セマンティック、グラフ — は blend_hybrid_scores(src/hybrid.rs:673)で融合します。デフォルトは乗算であり、レキシカルマッチがリードし、他の2つがそれを持ち上げます。

hybrid = bm25 * (1.0 + alpha * semantic + beta * skg);

これにより、強力なレキシカルヒットがトップに維持され、セマンティックとグラフのシグナルがそれらを持ち上げます。リコール拡張は2つのパスから来ます。セマンティックのみのヒットは bm25_score = 0 で許可され、SKGのみのセクションは、正規化されたグラフ質量が SKG_EXPAND_MIN = 0.5(src/graph_search.rs:22)に達した場合にのみ許可されます。レキシカルのみのパスでは、それらのSKGのみのセクションは beta*skg としてスコアリングされ、比較可能なレキシカルマッチ(apply_skg_boost in src/graph_search.rs:218)よりも低くなります。beta = 0 を設定すると、グラフ項は削除されます。

セマンティック/グラフがレキシカルを追い越すことができるようにしたい場合の代替モードがあり、これは LUME_BLEND_NORM=1 によってゲートされ、3つすべてを比較可能な [0,1] スケールに配置します(src/hybrid.rs:745)。

// src/hybrid.rs:745
let hybrid_score = if normalize {
    (bm25_score / bm25_max) + alpha * sem_score + beta * skg_score
} else if bm25_score > 0.0 {
    bm25_score * (1.0 + alpha * sem_score + beta * skg_score)
} else {
    sem_score + beta * skg_score // fallback for semantic-only recall expansion
};

7. チューニングサーフェス:各ノブが実際に行うこと

上記のすべてが lume search(src/main.rs:1295 の handle_search)で公開されています。これは実践的なガイドです。

ノブフラグ / 環境変数デフォルト変更内容
レキシカル ↔ セマンティック-a, --alpha / ALPHA0.5 (lume search時)0.0 = 純粋なBM25; 値が高いほどGTR-T5項が増加します。回答がクエリと異なる単語を使用する場合に値を上げてください。
グラフブースト-g, --graph / GRAPH_ALPHA0.4SKG項の重み。エンティティ関連セクションを引き込みたい場合は上げてください。0 はグラフを無効にします(純粋なレキシカル+セマンティック)。
エッジスコアリング--scoringrelatednessrelatedness(有意性、ハブ耐性)対 jaccard(生のオーバーラップ)。古い数値を再現しない限り、有意性を使用してください。
スペル訂正-c, --spell-checkオフ検索前にインデックス語彙に対して各クエリ単語を訂正します(src/main.rs:1273 の correct_query)。
BM25長さ / 飽和Bm25Paramsk1=1.2, b=0.75セクション長が大きく変動するコーパスでは b を低くし、繰り返し用語をより多く報酬したい場合は k1 を上げてください。
フィールド重みtitle_weight2.0タイトルヒットが本文ヒットをどれだけ上回るか。セクション/章のタイトルが結果を乗っ取っている場合は、値を下げてください。
クエリ反転(デバッグ)LUME_QUERY_INVERSION=1オフクエリのGTR-T5ベクトルをテキストに逆変換します(src/inversion.rs:30 の invert_vector)。これにより、埋め込みを検査できます。追加の埋め込みと逆変換リクエストが必要で、ランキングには影響しません。

反転トリックの具体的な例:セマンティック検索がうまくいかない場合、LUME_QUERY_INVERSION=1 を設定し、クエリが何に埋め込まれるかを読み取ります。もし「how does the prisoner escape」が庭園に関する何かに反転する場合、埋め込みは「escape」にアンカーされていません — 言い換えるか、低いalphaでレキシカルに依存してください。

8. ケーススタディ:エージェントを混乱させた検索バグ

これらのプリミティブがどのように相互作用するかを理解するために、テスト中に『モンテ・クリスト伯』の全文に対して実行された実際のクエリを検討します:「エドモン・ダンテスの父親はどのように死ぬのか?」

Lumeの初期実行では、回答エージェントは次のように返しました:「提供された箇所には、エドモン・ダンテスの父親がどのように死んだかに関する情報は含まれていません。」

しかし、その死はコーパスに完全に詳細に記述されています。この失敗を、クエリと検索パラメータの境界での3つの複合的な問題にトレースしました。

  1. 固有名詞のバイアス。 クエリプランナーは `