Search papers, labs, and topics across Lattice.
This paper introduces an LLM-aided A* search algorithm designed for non-geometric network graphs, where traditional heuristics based on spatial distances are ineffective. By leveraging large language models to generate intermediate waypoints and utilizing landmark distances as a heuristic, the approach significantly enhances search efficiency. Experimental results reveal that this method reduces the number of expanded nodes by approximately 50% while maintaining a minimal increase in path cost compared to optimal solutions.
LLM-generated waypoints can halve the search space in non-geometric graphs without sacrificing optimality.
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.
