2025-11-16T09:07:12.223206

Where to Search: Measure the Prior-Structured Search Space of LLM Agents

Song

The generate-filter-refine (iterative paradigm) based on large language models (LLMs) has achieved progress in reasoning, programming, and program discovery in AI+Science. However, the effectiveness of search depends on where to search, namely, how to encode the domain prior into an operationally structured hypothesis space. To this end, this paper proposes a compact formal theory that describes and measures LLM-assisted iterative search guided by domain priors. We represent an agent as a fuzzy relation operator on inputs and outputs to capture feasible transitions; the agent is thereby constrained by a fixed safety envelope. To describe multi-step reasoning/search, we weight all reachable paths by a single continuation parameter and sum them to obtain a coverage generating function; this induces a measure of reachability difficulty; and it provides a geometric interpretation of search on the graph induced by the safety envelope. We further provide the simplest testable inferences and validate them via a majority-vote instantiation. This theory offers a workable language and operational tools to measure agents and their search spaces, proposing a systematic formal description of iterative search constructed by LLMs.

academic

LLMエージェントの事前構造化探索空間の測定：どこで探索するか

基本情報

論文ID: 2510.14846
タイトル: Where to Search: Measure the Prior-Structured Search Space of LLM Agents
著者: Zhuo-Yang Song
分類: cs.AI cs.CL cs.LO
発表日: 2025年10月16日 (arXiv プレプリント)
論文リンク: https://arxiv.org/abs/2510.14846

要旨

大規模言語モデル(LLM)に基づく生成-フィルタリング-洗練(generate-filter-refine)反復パラダイムは、推論、プログラミング、AI+科学における手続き発見において進展を遂げている。しかし、探索の有効性は「どこで探索するか」、すなわちドメイン事前知識を実行可能な構造化仮説空間にどのようにエンコードするかに依存する。本論文では、ドメイン事前知識によって導かれるLLM支援反復探索を記述および測定するための簡潔な形式化理論を提案する。著者はエージェントを入出力上の曖昧関係演算子として表現し、実行可能な変換を捉える。エージェントは固定の安全包絡線制約によって制限される。多段階推論/探索を記述するため、著者は単一の継続パラメータによってすべての到達可能経路に重み付けし合計することで、生成関数をカバーする。これは到達可能性難易度の測度を誘導し、安全包絡線誘導グラフ上の探索の幾何学的解釈を提供する。

研究背景と動機

核心問題

本研究が解決する核心問題は：LLMエージェントの探索空間を体系的にどのように測定・記述するかである。具体的には、LLMベースの反復探索プロセスにおいて、探索効率は根本的に「どこで探索するか」という問題に制限される。すなわち、ドメイン事前知識をエージェントが操作可能な空間にどのようにエンコードするかという問題である。

問題の重要性

長時間領域タスクの要件：長時間領域タスクは安全性と制御性に対してより高い要件を提示し、検証可能で制御可能な境界内での操作が必要である
複雑性の課題：長時間領域問題は組み合わせ爆発と疎な報酬を伴うことが多く、純粋なヒューリスティックスまたは0/1スコアリングでは到達可能性難易度を定量化するのに不十分である
理論的欠落：現在の実践は主にエンジニアリングヒューリスティック(プロンプト設計、フィルタ、スコアリング関数など)に依存しており、統一された言語と定量的ツールが欠けている

既存方法の限界

エージェント-空間-探索測定の統一言語の欠落
異なるエージェント間の到達可能性と安全性のトレードオフを比較可能に測定することの困難さ
エージェントの長時間領域行動特性の明確な記述と説明の欠落

研究動機

簡潔で計算可能、モデル非依存の形式化理論を確立し、安全性と到達可能性の測定を統一し、テスト可能な予測とエンジニアリング利用可能な設計原則を提供する。

核心的貢献

簡潔な形式化理論の提案：エージェントを曖昧関係演算子として形式化し、生成関数をカバーすることで反復探索プロセスを統一的に記述
統一測定フレームワークの確立：継続パラメータとカバレッジ指数を導入し、安全性と到達可能性の統一的定量化方法を提供
幾何学的解釈の提供：安全包絡線誘導有向グラフ上で幾何学的量を定義し、探索プロセスの幾何学的解釈を提供
理論予測の検証：多数決インスタンス化を通じて理論のテスト可能な推論を検証し、外部検証を提供

方法論の詳細

タスク定義

入力空間： $C_1$ (エージェント入力空間)
出力空間： $C_2$ (エージェント出力空間、反復をサポートするため $C_2 \subseteq C_1$ を満たす)
目標：安全制約下での反復探索プロセスを測定・記述する

最短距離： $d_0(f,g) := \inf\{n \in \mathbb{N}: N_n(f,g) \geq 1\}$
最短経路数： $N_{d_0}(f,g)$
臨界パラメータ： $p_c(f,g) := \inf\{p \in [0,1]: P_{f,g}^{ideal}(p) \geq 1\}$
カバレッジ指数： $R_c(f,g) := 1 - p_c(f,g)$

仮説1：近似単向探索(閉ループ経路が稀)
仮説2：低次項主導(過度に長い軌跡が相対的に稀)

実験設定

実験環境

探索空間：2次元グリッド $G_N := \{0,\ldots,N-1\}^2$
グリッドスケール： $N = 3, 5, 8$
目標点：それぞれ $(1,2), (3,4), (6,7)$

エージェント構成

LLMモデルセット：gpt-4-mini、gpt-4、qwen3、qwen-plus、gemini-2.5-flash、deepseek-v3、grok-4、doubao
多数決メカニズム：各位置 $f$ に対して独立に $m=5$ 回サンプリングし、最頻値を決定として採用
理想的エージェント： $\mu_f^{(t)}(g) := \frac{1}{n}\sum_L \mu_f^{(L,t)}(g)$
安全包絡線： $\mu_f^{0,(t)}(g) := \mathbf{1}\{\mu_f^{(t)}(g) > 0\}$