論文の概要: Prior Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods

• arxiv url: http://arxiv.org/abs/2510.16609v1
• Date: Sat, 18 Oct 2025 18:17:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 00:56:39.061797
• Title: Prior Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods
• Title（参考訳）: Prior が実現 - サブ線形グラフアルゴリズムから LLM テスト時間法へ
• Authors: Avrim Blum, Daniel Hsu, Cyrus Rashtchian, Donya Saless,
• Abstract要約: 少数の拡張ステップでクエリに応答するために、事前学習の知識がどの程度必要かは明らかではない。 本研究では,事前知識の一部が与えられた場合の正確な答えを生成するために,モデルに必要な拡張ステップの数を特徴付ける。
• 参考スコア（独自算出の注目度）: 14.581444640667364
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Test-time augmentation, such as Retrieval-Augmented Generation (RAG) or tool use, critically depends on an interplay between a model's parametric knowledge and externally retrieved information. However, the theoretical underpinnings of this relationship remain poorly understood. Specifically, it is not clear how much pre-training knowledge is required to answer queries with a small number of augmentation steps, which is a desirable property in practice. To address this question, we formulate multi-step reasoning as an $s$-$t$ connectivity problem on a knowledge graph. We represent a model's pre-training parametric knowledge as a partial, potentially noisy subgraph. We view augmentation as querying an oracle for true edges that augment the model's knowledge. Then, we characterize the necessary and sufficient number of augmentation steps for the model to generate an accurate answer given partial prior knowledge. One key result shows a phase transition: if the prior knowledge graph over $n$ vertices is disconnected into small components, then finding a path via augmentation is inefficient and requires $\Omega(\sqrt{n})$ queries. On the other hand, once the density of correct knowledge surpasses a threshold, forming a giant component, we can find paths with an expected constant number of queries.
• Abstract（参考訳）: Retrieval-Augmented Generation (RAG) やツールの使用のようなテスト時の拡張は、モデルのパラメトリック知識と外部から取得した情報との間の相互作用に大きく依存する。 しかし、この関係の理論的基盤はいまだに理解されていない。 具体的には、実際に望ましい性質である少数の拡張ステップでクエリに応答するために、事前学習の知識がどの程度必要かは明らかになっていない。 この問題に対処するため、知識グラフ上での複数ステップの推論を$s$-$t$接続問題として定式化する。 モデルの事前学習したパラメトリック知識を,部分的,潜在的にノイズのある部分グラフとして表現する。 拡張は、モデルの知識を増大させる真のエッジのオラクルをクエリするものだと考えています。 そして,モデルに必要な拡張ステップ数を特徴付けることで,部分的事前知識が与えられた正確な解を生成する。 1つの主要な結果は相転移を示している:$n$ vertices 上の前の知識グラフが小さなコンポーネントに切断された場合、拡張によるパスを見つけることは非効率であり、$\Omega(\sqrt{n})$クエリを必要とする。 一方、正しい知識の密度がしきい値を超え、巨大なコンポーネントを形成すると、一定の数のクエリで経路を見つけることができる。

関連論文リスト

• PropMEND: Hypernetworks for Knowledge Propagation in LLMs [82.99849359892112]
  本稿では,PropMENDという,ハイパーネットワークに基づく知識伝播手法を提案する。 インジェクションされた事実に回答が明記されていないマルチホップ質問に対して,ほぼ2倍の精度で回答を提示する。 我々はまた、ハイパーネットワークの一般化を評価するために、新しいデータセットである Controlled RippleEdit も導入した。
  論文  参考訳（メタデータ） (2025-06-10T15:44:19Z)
• Harnessing Large Language Models for Knowledge Graph Question Answering via Adaptive Multi-Aspect Retrieval-Augmentation [81.18701211912779]
  本稿では,KG(Amar)フレームワーク上での適応型マルチアスペクト検索手法を提案する。 この方法は、エンティティ、リレーション、サブグラフを含む知識を検索し、検索した各テキストを即時埋め込みに変換する。 提案手法は2つの共通データセットに対して最先端の性能を達成した。
  論文  参考訳（メタデータ） (2024-12-24T16:38:04Z)
• GLaM: Fine-Tuning Large Language Models for Domain Knowledge Graph Alignment via Neighborhood Partitioning and Generative Subgraph Encoding [39.67113788660731]
  グラフ対応LAnguage Models (GLaM) を開発するためのフレームワークを紹介する。 特定のグラフに基づく知識でモデルを構築することは、構造に基づく推論のためのモデルの能力を拡張することを実証する。
  論文  参考訳（メタデータ） (2024-02-09T19:53:29Z)
• Fine-grained Stateful Knowledge Exploration: Effective and Efficient Graph Retrieval with Large Language Models [19.049828741139425]
  大きな言語モデル(LLM)は印象的な能力を示していますが、その知識を更新することは大きな課題です。 既存のほとんどの手法では、知識グラフから関連する知識を漸進的に取り出すために、問題全体を目的として扱うパラダイムを使用している。 本研究では,細粒度ステートフル知識探索のための新しいパラダイムであるFiSKEを提案する。
  論文  参考訳（メタデータ） (2024-01-24T13:36:50Z)
• ReasoningLM: Enabling Structural Subgraph Reasoning in Pre-trained Language Models for Question Answering over Knowledge Graph [142.42275983201978]
  本稿では,構造化推論を行うためのGNNを模倣するサブグラフ認識型自己認識機構を提案する。 また、モデルパラメータを2万のサブグラフで合成した質問に適応するための適応チューニング戦略も採用する。 実験により、ReasoningLMは、更新されたパラメータが少なく、トレーニングデータが少ない場合でも、最先端のモデルを大きなマージンで上回っていることが示された。
  論文  参考訳（メタデータ） (2023-12-30T07:18:54Z)
• Physics of Language Models: Part 3.1, Knowledge Storage and Extraction [51.68385617116854]
  大規模言語モデル(LLM)は膨大な量の世界の知識を格納することができ、しばしば質問応答によって抽出できる。 モデルが知識を抽出する能力と,トレーニングデータの多様な多様性尺度との間には,強い相関関係が認められた。
  論文  参考訳（メタデータ） (2023-09-25T17:37:20Z)
• Fast Knowledge Graph Completion using Graphics Processing Units [0.1611401281366893]
  現在の知識グラフは、関係性の観点からより良い知識を得るために補完する必要がある。 知識グラフ埋め込みモデルを用いて新たな関係性を加えるためには、$Ntimes N times R$ vector operation を評価する必要がある。 我々は、知識グラフ埋め込みベクトルを用いて新しい関係を得るために、GPU上で効率的な知識グラフ補完フレームワークを提供する。
  論文  参考訳（メタデータ） (2023-07-22T12:00:54Z)
• UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph [89.98762327725112]
  KGQA(Multi-hop Question Answering over Knowledge Graph)は、自然言語の質問で言及されているトピックエンティティから、複数のホップを持つ回答エンティティを見つけることを目的としている。 我々は、モデルアーキテクチャとパラメータ学習の両方において、検索と推論を統合することで、マルチホップKGQAタスクの新しいアプローチであるUniKGQAを提案する。
  論文  参考訳（メタデータ） (2022-12-02T04:08:09Z)
• A Simple Approach to Case-Based Reasoning in Knowledge Bases [56.661396189466664]
  我々は,古典人工知能(AI)におけるケースベース推論を想起させる,アンフノトレーニングを必要とする知識グラフ(KG)における推論に対する驚くほど単純かつ正確なアプローチを提案する。 ソースエンティティとバイナリ関係が与えられたターゲットエンティティを見つけるタスクを考えてみましょう。 我々の非パラメトリックなアプローチは、与えられた関係を通して類似したソースエンティティを接続する複数のテキストトグラフパスパターンを見つけることによって、クエリ毎にクレープな論理ルールを導出します。
  論文  参考訳（メタデータ） (2020-06-25T06:28:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。