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

Esraa Ghourab; Nouf Alabbasi; Omar Alhussein

arxiv: 2606.23136 · v1 · pith:D6UO7FMAnew · submitted 2026-06-22 · 💻 cs.NI · cs.AI· cs.LG

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

Nouf Alabbasi , Esraa Ghourab , Omar Alhussein This is my paper

Pith reviewed 2026-06-26 06:25 UTC · model grok-4.3

classification 💻 cs.NI cs.AIcs.LG

keywords A* searchLLM-aided searchnon-geometric graphslandmark distancesnetwork optimizationwaypointsshortest path

0 comments

The pith

LLM-generated waypoints reduce A* node expansions by about 50% in non-geometric network graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes using an LLM to generate intermediate waypoints that steer A* search in graphs where edge weights represent arbitrary costs rather than spatial distances. Landmark distances serve both as an admissible heuristic for the search itself and as compact features fed to the LLM so it can produce waypoints that restore a useful distance-to-destination signal. Experiments across multiple topologies with up to 2,000 nodes show the LLM waypoints cut expanded nodes by roughly half while the final path cost stays close to optimal. The work further reports that feeding heuristic estimates to the LLM outperforms advanced prompting techniques.

Core claim

An LLM can generate waypoints from landmark distance features that guide A* expansions in non-geometric graphs, reducing the number of expanded nodes by around 50% while incurring only a marginal path cost increase compared to the optimal solution.

What carries the argument

Landmark distances, used both as an admissible ALT heuristic for A* and as structural features supplied to the LLM to generate guiding waypoints.

If this is right

LLM-generated waypoints reduce the number of expanded nodes by around 50%.
The approach incurs only a marginal path cost increase compared to the optimal solution.
Incorporating compact structural features such as heuristic estimates is more effective than advanced prompting techniques.
The results hold on multiple graph topologies with up to 2,000 nodes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The technique could be evaluated on graphs larger than 2,000 nodes or on real network topologies to test scaling behavior.
Caching waypoint suggestions for repeated landmark patterns might offset the cost of LLM calls in repeated queries.
Similar waypoint guidance could be explored for other informed search algorithms or for dynamic networks where edge costs change.

Load-bearing premise

Landmark distances supplied to the LLM will consistently produce waypoints that meaningfully reduce expansions without violating A* admissibility or introducing unacceptable computational overhead from LLM calls.

What would settle it

A counterexample would be a collection of test graphs where the LLM waypoints cause A* to expand more nodes than the baseline or produce paths whose cost exceeds the optimal cost by more than a small margin.

Figures

Figures reproduced from arXiv: 2606.23136 by Esraa Ghourab, Nouf Alabbasi, Omar Alhussein.

**Figure 1.** Figure 1: Effect of waypoint guidance on A* exploration. Standard A* (left) is compared with large language model (LLM)- aided A* (middle). Source and destination nodes are shown in dark blue, expanded nodes in yellow, LLM-derived waypoints in pink and the selected path in light blue. being an admissible heuristic for the solver and a compact structural feature input for the LLM. • We show that prompt content outwei… view at source ↗

**Figure 2.** Figure 2: Representative subgraphs: (a) Barabasi–Albert (BA) ´ model graph exhibiting a scale-free topology, and (b) SNAP road network graph. TABLE I: Effect of the number of LLM-derived waypoints on exploration reduction across different SNAP graph sizes. Results report the percentage reduction in expanded nodes achieved by LLM-aided A* for varying waypoint counts (5, 8, and 12) and graph sizes ranging from 750 to … view at source ↗

**Figure 4.** Figure 4: Expanded nodes versus graph size for SNAP road network subgraphs. Results compare standard A* with LLMaided A* using 5, 8, and 12 waypoints across graph sizes ranging from 500 to 2000 nodes [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗

**Figure 5.** Figure 5: Path cost comparison across varying graph sizes. Results are averaged over 50 runs towards more promising regions. With the right number of waypoints, the search receives a general directional guide while retaining the flexibility to identify the optimal route within those regions. The results on BA graphs reveal a complementary pattern, as plotted in [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗

**Figure 6.** Figure 6: Comparison of standard A* (top row) and LLM-aided A* (bottom row). Yellow nodes represent expanded nodes. Dark blue nodes indicate the final path, while red nodes denote LLM-generated waypoints, which guide the search and reduce exploration. algorithmic optimization provides a degree of robustness to potential LLM hallucinations. Since the LLM’s output is used to bias the search priority rather than to dic… view at source ↗

**Figure 7.** Figure 7: Instance of an outlier case on a 2000-node graph. Yellow nodes represent expanded nodes. Dark blue nodes indicate the final path, while red nodes denote LLM-generated waypoints quality. Importantly, the LLM acts as a guide rather than a solver, preserving the robustness of the underlying algorithm. Several directions remain for future work. While the present study targets unweighted graphs to isolate the e… view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

LLM waypoints halve A* expansions on non-geometric graphs but the unmeasured LLM call overhead looks like the real limit.

read the letter

The paper's core move is to feed landmark distance vectors to an LLM so it can propose waypoints that steer A* on graphs where no geometric heuristic exists. That combination is not a standard extension of either ALT or prior LLM search work, and the experiments show it cuts expanded nodes by about 50% across several topologies up to 2000 nodes while keeping path cost close to optimal. They also test that adding the landmark features beats fancier prompt engineering, which is a useful practical result.

The experiments are run on multiple graph families, which is better than a single synthetic case. The dual role of the landmarks (heuristic plus LLM input) is cleanly motivated and avoids obvious circularity.

The main gap is runtime. The stress-test concern about prompt size holds up from the abstract: for 2000 nodes the landmark vectors will make each prompt large, yet the paper only reports node expansions and path cost, not number of LLM calls, token counts, or wall-clock time. If the LLM is invoked once per query the latency could dominate; if more often it gets worse. Without those numbers the 50% expansion claim does not yet translate to a net efficiency gain.

The work is aimed at people doing pathfinding in latency or cost-based networks who are already willing to experiment with LLM calls. A referee should see the full methods to check graph generation details, exact baselines, and whether any end-to-end timing was collected. It is worth sending out for review because the idea is concrete and the reported reduction is large enough to test further, even if the overhead question needs to be answered.

Referee Report

2 major / 1 minor

Summary. The paper proposes an LLM-aided A* search algorithm for shortest paths in non-geometric network graphs. Landmark distances serve dual roles as an admissible ALT heuristic and as compact structural features fed to an LLM to generate waypoints that guide expansion. Experiments on multiple topologies with up to 2,000 nodes are reported to show an approximately 50% reduction in expanded nodes with only marginal path-cost increase relative to optimal; prompt engineering is also analyzed, with the conclusion that heuristic features outperform advanced prompting techniques.

Significance. If the efficiency claims can be substantiated with complete experimental protocols and overhead measurements, the work would offer a concrete demonstration of hybrid LLM-classical search for domains lacking geometric structure, with potential relevance to network routing and optimization. The absence of runtime accounting and statistical validation currently prevents assessment of whether net gains are realized.

major comments (2)

[Abstract / Experiments] Abstract and Experiments section: the central claim of ~50% reduction in expanded nodes with marginal cost increase is presented without any description of graph generation procedures, number of queries or trials per topology, choice of baselines (standard A*, pure ALT, etc.), error bars, or statistical significance tests. This directly undermines evaluation of the reported improvement.
[Experiments] Experiments section: no quantification is given of LLM call frequency, prompt token counts (especially the landmark-distance vectors for 2,000-node graphs), or total wall-clock time including inference latency. Without these metrics the net efficiency gain cannot be established even if node expansions drop.

minor comments (1)

[Method] Notation for landmark distances and waypoint selection could be formalized with a short pseudocode or equation block to clarify how the LLM output is integrated into the A* open set.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our experimental presentation. We address each major comment below and will revise the manuscript accordingly to improve clarity and substantiation of results.

read point-by-point responses

Referee: [Abstract / Experiments] Abstract and Experiments section: the central claim of ~50% reduction in expanded nodes with marginal cost increase is presented without any description of graph generation procedures, number of queries or trials per topology, choice of baselines (standard A*, pure ALT, etc.), error bars, or statistical significance tests. This directly undermines evaluation of the reported improvement.

Authors: We agree that additional experimental details are needed for full reproducibility and evaluation. In the revised manuscript we will expand the Experiments section with: explicit graph generation procedures for each topology, the exact number of queries and independent trials per topology, a complete list of baselines (standard A*, pure ALT, and others), error bars on all reported metrics, and statistical significance tests (e.g., paired t-tests) supporting the ~50% node-expansion reduction. The abstract will remain unchanged as it accurately summarizes the findings once these details are provided. revision: yes
Referee: [Experiments] Experiments section: no quantification is given of LLM call frequency, prompt token counts (especially the landmark-distance vectors for 2,000-node graphs), or total wall-clock time including inference latency. Without these metrics the net efficiency gain cannot be established even if node expansions drop.

Authors: The referee is correct that overhead accounting is required to confirm net gains. We will add to the revised Experiments section a dedicated analysis quantifying LLM call frequency per search, average and maximum prompt token counts (noting that the landmark-distance vectors are compact and scale linearly), and total wall-clock runtime decomposed into classical search time and LLM inference latency. These measurements will allow readers to assess whether the reduction in node expansions translates to practical efficiency improvements. revision: yes

Circularity Check

0 steps flagged

No circularity; empirical results are independent measurements

full rationale

The paper reports experimental outcomes from running LLM-aided A* on graphs up to 2000 nodes, with the 50% reduction in expanded nodes measured directly from those runs rather than derived from any equation or fitted parameter. Landmark distances are supplied as an external admissible heuristic (ALT) and prompt feature; no self-definitional loop, fitted-input prediction, or self-citation chain is present in the provided text. The central claim rests on observable search behavior, not on any reduction to the paper's own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard properties of A* with admissible heuristics and the empirical behavior of LLMs when given structural features; no new entities or fitted parameters are introduced in the abstract.

axioms (2)

standard math A* with admissible heuristic returns optimal paths
Invoked implicitly when claiming marginal cost increase relative to optimal solution.
domain assumption Landmark distances yield admissible ALT heuristics
Used both for search guidance and as LLM input; standard in ALT literature but assumed here without re-derivation.

pith-pipeline@v0.9.1-grok · 5756 in / 1119 out tokens · 28596 ms · 2026-06-26T06:25:20.556926+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

16 extracted references · 3 canonical work pages

[1]

AI reasoning for wireless communications and networking: A survey and perspectives,

H. Luo, Y . Yan, Y . Bian, W. Feng, R. Zhang, Y . Liu, J. Wang, G. Sun, D. Niyato, H. Yu, A. Jamalipour, and S. Mao, “AI reasoning for wireless communications and networking: A survey and perspectives,”CoRR, vol. abs/2509.09193, 2025

work page arXiv 2025
[2]

AI reasoning for wireless communications and networking: A survey and perspectives,

H. Luo, Y . Yan, Y . Bian, W. Feng, R. Zhang, Y . Liu, J. Wang, G. Sun, D. Niyato, H. Yuet al., “AI reasoning for wireless communications and networking: A survey and perspectives,”ACM Comput. Surveys, 2025

2025
[3]

Evaluating large language models on graphs: Perfor- mance insights and comparative analysis,

C. Liu and B. Wu, “Evaluating large language models on graphs: Perfor- mance insights and comparative analysis,”CoRR, vol. abs/2308.11224, 2023

work page arXiv 2023
[4]

A 1000 timesxfaster LLM- enhanced algorithm for path planning in large-scale grid maps,

J. Zeng, X. Zhang, X. Zhao, and Y . Pan, “A 1000 timesxfaster LLM- enhanced algorithm for path planning in large-scale grid maps,”CoRR, vol. abs/2510.02716, 2025

work page arXiv 2025
[5]

LLM-a*: Large language model enhanced incremental heuristic search on path planning,

S. Meng, Y . Wang, C.-F. Yang, N. Peng, and K.-W. Chang, “LLM-a*: Large language model enhanced incremental heuristic search on path planning,” inFindings ACL EMNLP, Nov. 2024, pp. 1087–1102

2024
[6]

Computing the shortest path: A search meets graph theory

A. V . Goldberg and C. Harrelson, “Computing the shortest path: A search meets graph theory.” inSODA, vol. 5, 2005, pp. 156–165

2005
[7]

Language is all a graph needs,

R. Ye, C. Zhang, R. Wang, S. Xu, and Y . Zhang, “Language is all a graph needs,” inin Findings ACL EACL, 2024, pp. 1955–1973

2024
[8]

Leveraging large language models for multi-objective and adaptive SFC deployment: Techniques, case study, and promising directions,

L. Zhu, J. Yu, X. Chen, Z. Jiang, X. Liu, J. Zhang, X. Yang, R. Zhang, D. Niyato, X. Yi, I. Khalil, D. Zhang, and C. Wu, “Leveraging large language models for multi-objective and adaptive SFC deployment: Techniques, case study, and promising directions,”IEEE Commun. Mag., vol. 64, no. 1, pp. 32–39, 2026

2026
[9]

Har- nessing explanations: Llm-to-lm interpreter for enhanced text-attributed graph representation learning,

X. He, X. Bresson, T. Laurent, A. Perold, Y . LeCun, and B. Hooi, “Har- nessing explanations: Llm-to-lm interpreter for enhanced text-attributed graph representation learning,” inProc. Int. Conf. Learn. Represent. (ICLR), 2024, pp. 5711–5732

2024
[10]

LLMAP: LLM- assisted multi-objective route planning with user preferences,

L. Yuan, D.-J. Han, C. Brinton, and S. Brunswicker, “LLMAP: LLM- assisted multi-objective route planning with user preferences,” inFind- ings ACL EMNLP, Nov. 2025, pp. 7866–7894

2025
[11]

Can large language models analyze graphs like professionals? a benchmark, datasets and models,

X. Li, W. Chen, Q. Chu, H. Li, Z. Sun, R. Li, C. Qian, Y . Wei, Z. Liu, C. Shi, M. Sun, and C. Yang, “Can large language models analyze graphs like professionals? a benchmark, datasets and models,” inAdv. Neural Inf. Process. Syst. (NeurIPS), vol. 37. Curran Associates, Inc., 2024

2024
[12]

Mathematical discoveries from program search with large language models,

B. Romera-Paredes, M. Barekatain, A. Novikov, M. Balog, M. Kumar, E. Dupont, F. Ruiz, J. Ellenberg, P. Wang, O. Fawzi, P. Kohli, and A. Fawzi, “Mathematical discoveries from program search with large language models,”Nature, vol. 625, 12 2023

2023
[13]

Eureka: Human-level reward design via coding large language models,

Y . J. Ma, W. Liang, G. Wang, D.-A. Huang, O. Bastani, D. Jayaraman, Y . Zhu, J. Fanet al., “Eureka: Human-level reward design via coding large language models,” inProc. Int. Conf. Learn. Represent. (ICLR), 2024, pp. 26 516–26 560

2024
[14]

Guiding pretraining in reinforcement learning with large language models,

Y . Du, O. Watkins, Z. Wang, C. Colas, T. Darrell, P. Abbeel, A. Gupta, and J. Andreas, “Guiding pretraining in reinforcement learning with large language models,” inInternational Conference on Machine Learn- ing. PMLR, 2023, pp. 8657–8677

2023
[15]

Snap: A general-purpose network analysis and graph-mining library,

J. Leskovec and R. Sosi ˇc, “Snap: A general-purpose network analysis and graph-mining library,”ACM Trans. Intell. Syst. Technol., vol. 8, no. 1, pp. 1–20, 2016

2016
[16]

GPT-4.1 model documentation,

OpenAI, “GPT-4.1 model documentation,” 2025, accessed: March 2026

2025

[1] [1]

AI reasoning for wireless communications and networking: A survey and perspectives,

H. Luo, Y . Yan, Y . Bian, W. Feng, R. Zhang, Y . Liu, J. Wang, G. Sun, D. Niyato, H. Yu, A. Jamalipour, and S. Mao, “AI reasoning for wireless communications and networking: A survey and perspectives,”CoRR, vol. abs/2509.09193, 2025

work page arXiv 2025

[2] [2]

AI reasoning for wireless communications and networking: A survey and perspectives,

H. Luo, Y . Yan, Y . Bian, W. Feng, R. Zhang, Y . Liu, J. Wang, G. Sun, D. Niyato, H. Yuet al., “AI reasoning for wireless communications and networking: A survey and perspectives,”ACM Comput. Surveys, 2025

2025

[3] [3]

Evaluating large language models on graphs: Perfor- mance insights and comparative analysis,

C. Liu and B. Wu, “Evaluating large language models on graphs: Perfor- mance insights and comparative analysis,”CoRR, vol. abs/2308.11224, 2023

work page arXiv 2023

[4] [4]

A 1000 timesxfaster LLM- enhanced algorithm for path planning in large-scale grid maps,

J. Zeng, X. Zhang, X. Zhao, and Y . Pan, “A 1000 timesxfaster LLM- enhanced algorithm for path planning in large-scale grid maps,”CoRR, vol. abs/2510.02716, 2025

work page arXiv 2025

[5] [5]

LLM-a*: Large language model enhanced incremental heuristic search on path planning,

S. Meng, Y . Wang, C.-F. Yang, N. Peng, and K.-W. Chang, “LLM-a*: Large language model enhanced incremental heuristic search on path planning,” inFindings ACL EMNLP, Nov. 2024, pp. 1087–1102

2024

[6] [6]

Computing the shortest path: A search meets graph theory

A. V . Goldberg and C. Harrelson, “Computing the shortest path: A search meets graph theory.” inSODA, vol. 5, 2005, pp. 156–165

2005

[7] [7]

Language is all a graph needs,

R. Ye, C. Zhang, R. Wang, S. Xu, and Y . Zhang, “Language is all a graph needs,” inin Findings ACL EACL, 2024, pp. 1955–1973

2024

[8] [8]

Leveraging large language models for multi-objective and adaptive SFC deployment: Techniques, case study, and promising directions,

L. Zhu, J. Yu, X. Chen, Z. Jiang, X. Liu, J. Zhang, X. Yang, R. Zhang, D. Niyato, X. Yi, I. Khalil, D. Zhang, and C. Wu, “Leveraging large language models for multi-objective and adaptive SFC deployment: Techniques, case study, and promising directions,”IEEE Commun. Mag., vol. 64, no. 1, pp. 32–39, 2026

2026

[9] [9]

Har- nessing explanations: Llm-to-lm interpreter for enhanced text-attributed graph representation learning,

X. He, X. Bresson, T. Laurent, A. Perold, Y . LeCun, and B. Hooi, “Har- nessing explanations: Llm-to-lm interpreter for enhanced text-attributed graph representation learning,” inProc. Int. Conf. Learn. Represent. (ICLR), 2024, pp. 5711–5732

2024

[10] [10]

LLMAP: LLM- assisted multi-objective route planning with user preferences,

L. Yuan, D.-J. Han, C. Brinton, and S. Brunswicker, “LLMAP: LLM- assisted multi-objective route planning with user preferences,” inFind- ings ACL EMNLP, Nov. 2025, pp. 7866–7894

2025

[11] [11]

Can large language models analyze graphs like professionals? a benchmark, datasets and models,

X. Li, W. Chen, Q. Chu, H. Li, Z. Sun, R. Li, C. Qian, Y . Wei, Z. Liu, C. Shi, M. Sun, and C. Yang, “Can large language models analyze graphs like professionals? a benchmark, datasets and models,” inAdv. Neural Inf. Process. Syst. (NeurIPS), vol. 37. Curran Associates, Inc., 2024

2024

[12] [12]

Mathematical discoveries from program search with large language models,

B. Romera-Paredes, M. Barekatain, A. Novikov, M. Balog, M. Kumar, E. Dupont, F. Ruiz, J. Ellenberg, P. Wang, O. Fawzi, P. Kohli, and A. Fawzi, “Mathematical discoveries from program search with large language models,”Nature, vol. 625, 12 2023

2023

[13] [13]

Eureka: Human-level reward design via coding large language models,

Y . J. Ma, W. Liang, G. Wang, D.-A. Huang, O. Bastani, D. Jayaraman, Y . Zhu, J. Fanet al., “Eureka: Human-level reward design via coding large language models,” inProc. Int. Conf. Learn. Represent. (ICLR), 2024, pp. 26 516–26 560

2024

[14] [14]

Guiding pretraining in reinforcement learning with large language models,

Y . Du, O. Watkins, Z. Wang, C. Colas, T. Darrell, P. Abbeel, A. Gupta, and J. Andreas, “Guiding pretraining in reinforcement learning with large language models,” inInternational Conference on Machine Learn- ing. PMLR, 2023, pp. 8657–8677

2023

[15] [15]

Snap: A general-purpose network analysis and graph-mining library,

J. Leskovec and R. Sosi ˇc, “Snap: A general-purpose network analysis and graph-mining library,”ACM Trans. Intell. Syst. Technol., vol. 8, no. 1, pp. 1–20, 2016

2016

[16] [16]

GPT-4.1 model documentation,

OpenAI, “GPT-4.1 model documentation,” 2025, accessed: March 2026

2025