論文の概要: LLM-Aided A* Search in Non-Geometric Network Graphs

• arxiv url: http://arxiv.org/abs/2606.23136v1
• Date: Mon, 22 Jun 2026 10:26:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-24 23:50:55.80078
• Title: LLM-Aided A* Search in Non-Geometric Network Graphs
• Title（参考訳）: 非幾何学的ネットワークグラフにおけるLLM支援A*探索
• Authors: Nouf Alabbasi, Esraa Ghourab, Omar Alhussein,
• Abstract要約: 本稿では,LLM が A* 拡張を有望なグラフ領域へ導く中間経路を生成できる大規模言語モデル (LLM) を用いた A* アルゴリズムを提案する。 最大2,000ノードのグラフトポロジに関する実験により,LLMは拡張ノード数を50%程度削減する一方,最適解に比べて限界パスコストの増加しか生じないことが示された。
• 参考スコア（独自算出の注目度）: 0.4078247440919473
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding the shortest path in non-geometric network graphs, where edge weights encode arbitrary metrics such as latency or monetary cost rather than spatial distance, poses a challenge for informed search algorithms. Their efficiency depends on an informative heuristic, typically supplied in spatial domains by geometric distances that have no counterpart on non-geometric graphs. We propose a large language model (LLM)-aided A* algorithm in which an LLM generates intermediate waypoints that guide the A* expansion toward promising graph regions. At the core of the approach are landmark distances, which serve both as an admissible landmark-based (ALT) heuristic for the search and as a compact structural feature that, supplied to the LLM, restores the distance-to-destination signal it would otherwise lack on non-geometric graphs. Our comprehensive experiments on multiple graph topologies with up to 2,000 nodes demonstrate that LLM-generated waypoints reduce the number of expanded nodes by around 50% while incurring only a marginal path cost increase compared to the optimal solution. We further analyze the impact of prompt engineering and show that incorporating compact structural features, namely heuristic estimates, is more effective than advanced prompting techniques. These findings demonstrate the potential of combining LLM- based guidance with classical search algorithms for efficient network optimization.
• Abstract（参考訳）: エッジ重みが空間距離よりも遅延や金銭コストなどの任意の指標をエンコードする非幾何学的ネットワークグラフの最も短い経路を見つけることは、情報検索アルゴリズムの課題となる。 それらの効率は情報的ヒューリスティックに依存し、通常は幾何学的距離によって空間領域に供給されるが、非幾何学的グラフにはない。 本稿では,LLM が A* 拡張を有望なグラフ領域へ導く中間経路を生成できる大規模言語モデル (LLM) を用いた A* アルゴリズムを提案する。 アプローチの核心はランドマーク距離であり、これは探索のための許容ランドマークベース(ALT)ヒューリスティック(英語版)として機能し、LLMに供給されるコンパクトな構造的特徴として機能し、それ以外は非幾何学グラフに欠けている距離から目的地への信号が復元される。 最大2,000ノードのグラフトポロジに関する包括的実験により, LLM生成した経路点が拡張ノード数を約50%削減する一方, 最適解に比べて限界パスコストの増加しか生じないことが示された。 我々はさらに、プロンプトエンジニアリングの影響を分析し、より高度なプロンプト技術よりも、よりコンパクトな構造的特徴、すなわちヒューリスティックな見積もりを取り入れることが効果的であることを示す。 これらの結果は,LLMに基づくガイダンスと従来の探索アルゴリズムを組み合わせることで,効率的なネットワーク最適化を実現する可能性を示している。

関連論文リスト

• Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle [56.92868481531399]
  粗大化における近隣住民の集団干渉を優先する非利己的原則を提案する。 局所等方性仮定に基づいて、O(dot d)干渉評価をO(d)に還元する高速なNOPE*を導出する。 粗いグラフの学習は、元のグラフに匹敵する性能を示し、LLMベースのグラフ推論よりも優れた性能を示すことができる。
  論文  参考訳（メタデータ） (2026-05-13T05:24:35Z)
• Efficient Sketching and Nearest Neighbor Search Algorithms for Sparse Vector Sets [16.768212375976546]
  スパースANNSのための新しいデータ構造とアルゴリズム手法を提案する。 我々の貢献は、スパースベクトルに対する理論的に基底化されたスケッチアルゴリズムから、それらの有効次元を減少させるものまで様々である。 我々の最終アルゴリズムは耐震性と呼ばれ、大規模ベンチマークデータセット上で高精度でミリ秒以下のレイテンシに達する。
  論文  参考訳（メタデータ） (2025-09-29T14:02:45Z)
• LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning [91.95362946266577]
  経路計画はロボット工学と自律航法における基本的な科学的問題である。 A*やその変種のような伝統的なアルゴリズムは、パスの妥当性を保証することができるが、状態空間が大きくなるにつれて、計算とメモリの非効率が著しく低下する。 本稿では, A* の正確なパスフィニング能力と LLM のグローバルな推論能力とを相乗的に組み合わせた LLM ベースの経路計画法を提案する。 このハイブリッドアプローチは、特に大規模シナリオにおいて、パス妥当性の完全性を維持しながら、時間と空間の複雑さの観点からパスフィニング効率を向上させることを目的としている。
  論文  参考訳（メタデータ） (2024-06-20T01:24:30Z)
• LightDiC: A Simple yet Effective Approach for Large-scale Digraph Representation Learning [42.72417353512392]
  磁気ラプラシアンに基づくダイグラフ畳み込みのスケーラブルな変種であるLightDiCを提案する。 LightDiCは、最も代表的な大規模データベースで満足な結果を提供する最初のDiGNNである。
  論文  参考訳（メタデータ） (2024-01-22T09:09:10Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• LCS Graph Kernel Based on Wasserstein Distance in Longest Common Subsequence Metric Space [22.215852332444904]
  パスとウォークのより包括的類似性を計算するグラフカーネルを提案する。 また、グラフのより深い特徴を抽出するために、最適輸送理論と組み合わせる。 提案手法は多くの最先端グラフカーネル手法に勝る。
  論文  参考訳（メタデータ） (2020-12-07T11:59:14Z)
• Solving Sparse Linear Inverse Problems in Communication Systems: A Deep Learning Approach With Adaptive Depth [51.40441097625201]
  疎信号回復問題に対するエンドツーエンドの訓練可能なディープラーニングアーキテクチャを提案する。 提案手法は,出力するレイヤ数を学習し,各タスクのネットワーク深さを推論フェーズで動的に調整する。
  論文  参考訳（メタデータ） (2020-10-29T06:32:53Z)

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

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