LLM-Aided A* Search in Non-Geometric Network Graphs
For practitioners needing efficient shortest-path search in non-geometric networks (e.g., latency or cost graphs), this hybrid approach offers a practical speedup, though it is incremental over existing A* and ALT heuristics.
The authors propose an LLM-aided A* algorithm for non-geometric network graphs, where the LLM generates waypoints to guide search. Experiments on graphs up to 2,000 nodes show a 50% reduction in expanded nodes with marginal path cost increase.
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.