# LLM-Aided A* Search in Non-Geometric Network Graphs

arXiv: https://arxiv.org/abs/2606.23136 · HTML: https://mlsanity.com/paper/2606.23136/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 15 references that are in the map.
- First posted on arXiv 22 Jun 2026.

## Builds on (most cited first, 10 of 10)

- [Eureka: Human-Level Reward Design via Coding Large Language Models](https://mlsanity.com/paper/2310.12931/) (2023)
- [Language is All a Graph Needs](https://mlsanity.com/paper/2308.07134/) (2023)
- [Guiding Pretraining in Reinforcement Learning with Large Language Models](https://mlsanity.com/paper/2302.06692/) (2023)
- [SNAP: A General Purpose Network Analysis and Graph Mining Library](https://mlsanity.com/paper/1606.07550/) (2016)
- [LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning](https://mlsanity.com/paper/2407.02511/) (2024)
- [Evaluating Large Language Models on Graphs: Performance Insights and Comparative Analysis](https://mlsanity.com/paper/2308.11224/) (2023)
- [Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models](https://mlsanity.com/paper/2409.19667/) (2024)
- [LLMAP: LLM-Assisted Multi-Objective Route Planning with User Preferences](https://mlsanity.com/paper/2509.12273/) (2025)
- [AI Reasoning for Wireless Communications and Networking: A Survey and Perspectives](https://mlsanity.com/paper/2509.09193/) (2025)
- [A 1000× Faster LLM-enhanced Algorithm For Path Planning in Large-scale Grid Maps](https://mlsanity.com/paper/2510.02716/) (2025)

## Abstract (arXiv)

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.