arXiv (アーカイヴ) は2026年11月12日(現地時間)、Christopher Liaw氏らが、言語モデルのコンテキスト帰属(Context attribution)を効率的に推定する新たなスケッチングアルゴリズムに関する研究論文を公開した。プロンプトの一部を削除した場合の言語モデル出力への影響を分析する手法、Leave-one-out (LOO) attribution (リーブワンアウト帰属) の効率化を目指す。本研究では、従来のモデル評価回数を大幅に削減するアルゴリズムを開発し、その計算量と性能を実証している。

Christopher Liaw氏、Aranyak Mehta氏、Grigoris Velegkas氏、Felix Zhou氏の4氏は、Sketching Language Models for Context Attributionと題した論文で詳細を報告した。

既存のLeave-one-out (LOO) attributionの直接計算では、$n$個のトークンを持つプロンプトに対し$n$回のモデル評価が必要となる。これに対し、本研究で提案されたアルゴリズムは、安定性仮定の下で、$O(\sqrt{\log(1/\varepsilon)}/\varepsilon)$回の評価呼び出しで、誤差を$\varepsilon$に比例させて全てのLOO値を推定できるとされている。これは、従来の順方向微分スケッチが必要とする$\widetilde{O}(\log(n)/\varepsilon^2)$回の評価呼び出しと比較して大幅な改善である。

研究チームは、この推定上限を補完する形で、オラクルモデルにおける評価呼び出し回数の下限が$\Omega(\sqrt{\log(1/\varepsilon)}/\varepsilon)$であることを証明した。さらに、小規模な言語モデル検索タスクにおいて、係数減衰が安定性と一致することを確認し、開発したスケッチングアルゴリズムの性能を経験的に評価している。この技術的成果は、Gunn氏が最近導入した安定性条件を満たす算術回路のテイラー係数に関するスケッチングアルゴリズムに基づいている。主要な観察として、順方向微分をバックプロパゲーション回路に適用することで、スケッチの分散が減少し、評価バウンドの改善に繋がったと説明されている。下限の証明は、Amsel氏らが示した技術に基づいている。

本研究は、データ構造とアルゴリズム (Data Structures and Algorithms)、人工知能 (Artificial Intelligence)、機械学習 (Machine Learning) の分野に関連するものとされている。


参考: arXiv cs.DS (アーカイブ) — 2026年11月13日 03:57 (JST)

原文ハイライト

"Sketching Language Models for Context Attribution"

この記事をシェア
X はてブ LinkedIn