LLM-Aided A* Search in Non-Geometric Network Graphs
2026-06-22 • Networking and Internet Architecture
Networking and Internet ArchitectureArtificial IntelligenceMachine Learning
AI summaryⓘ
The authors address the problem of finding the shortest path in networks where distances are not physical but represent things like cost or delay. They use a large language model (LLM) to suggest helpful waypoints that guide the search more efficiently. By combining these LLM-generated tips with a classical A* algorithm that uses special 'landmark distances' as hints, they reduce the search effort by about half with only a small increase in path cost. Their work shows that adding these compact distance features to the LLM input works better than just fancy prompting. This suggests that mixing AI guidance with traditional methods can improve how we solve complex network problems.
A* algorithmlarge language modelsshortest pathheuristiclandmark distancesnon-geometric graphsnetwork optimizationprompt engineeringgraph topologyheuristic search
Authors
Nouf Alabbasi, Esraa Ghourab, Omar Alhussein
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.