GridRoute: A Benchmark for LLM-Based Route Planning with Cardinal Movement in Grid Environments
Kechen Li, Yaotian Tao, Ximing Wen, Quanwei Sun, Zifei Gong, Hongli Zhang , Chang Xu, Xizhe Zhang, Tianbo Ji · 2025
Read GridRoute: A Benchmark for LLM-Based Route Planning with Cardinal Movement in Grid Environments by Kechen Li, Yaotian Tao, Ximing Wen, Quanwei Sun, Zifei Gong, Hongli Zhang , Chang Xu, Xizhe Zhang, Tianbo Ji (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-24306.txt.
Introduction
Kechen Li and seven co-authors build a bench that tests how well language models plan routes on a grid, alone and with classic algorithms at their side. Their paper appeared in two thousand twenty-five. Models can reason about paths in words, yet most studies grade them in isolation. The gains from teaming them with proven pathfinders stay unmeasured.
Their grids vary in size, and moves run in the four compass directions. Six models, from small to large, were scored on correctness, best-ness, and speed. A new prompting style feeds the steps of a classic algorithm into the chat. That style lifted every model, most of all on big, tangled maps. The authors share the code in public. The bench gives a fair way to judge hybrid planning.
Catalog record
| CREATOR | Kechen Li, Yaotian Tao, Ximing Wen, Quanwei Sun, Zifei Gong, Hongli Zhang , Chang Xu, Xizhe Zhang, Tianbo Ji |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-24306
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
GridRoute: A Benchmark for LLM-Based Route Planning with Cardinal Movement in Grid Environments Kechen Li, Yaotian Tao, Ximing Wen, Quanwei Sun, Zifei Gong, Hongli Zhang , Chang Xu, Xizhe Zhang, Tianbo Ji Abstract Recent advancements in Large Language Models (LLMs) have demonstrated their potential in planning and reasoning tasks, offering a flexible alternative to classical pathfinding algorithms. However, most existing studies focus on LLMs’ independent reasoning capabilities and overlook the potential synergy between LLMs and traditional algorithms. To fill this gap, we propose a comprehensive evaluation benchmark GridRoute to assess how LLMs can take advantage of traditional algorithms. We also propose a novel hybrid prompting technique called Algorithm of Planning (AoP), which introduces traditional algorithms’ guidance into prompting. Our benchmark evaluates six LLMs ranging from 7B to 72B parameters across various map sizes, assessing their performance in correctness, optimality, and efficiency in grid environments with varying sizes. Our results show that AoP significantly boosts performance across all model sizes, particularly in larger or more complex environments, suggesting a promising approach to addressing path planning challenges. 1 1 1 Our code is open-sourced at https://github.com/LinChance/GridRoute . 1 Introduction Pathfinding in grid-based environments has long been dominated by classical algorithms such as A* Hart et al. (1968) , Dijkstra ( Dijkstra, 1959 ) , and DFS, which rely on explicit search heuristics and guarantee optimality under predefined conditions. However, the recent rise of Large Language Models (LLMs) has introduced an alternative paradigm, everaging their implicit reasoning capabilities and contextual adaptation. Specialized benchmarks, such as Path Planning from Natural Language (PPNL) Aghzal et al. (2023) explored LLMs’ ability to perform end-to-end navigation while adhering to movement constraints and avoiding obstacles. However, they only explored the independent exploring ability of LLMs using prompting strategies such as Chain-of-Thought (CoT) Wei et al. (2023) , ReAct Yao et al. (2023) . LLM-A* Meng (2025) , on the other hand, tried to integrate LLM’s ability with guidance from traditional pathfinding algorithms, but they only use LLM in one of the steps, which is to generate intermediate target lists, and still rely on A* to generate the final solution. In this way, there still lacks research exploring how traditional algorithms could help LLM-generated route planning. To bridge this gap, we propose a comprehensive benchmark GridRoute to systematically evaluate the role of traditional algorithmic guidance in enhancing the pathfinding capabilities of LLMs. Our benchmark is designed around three core prompting paradigms: (1) independent prompting, (2) Algorithm of Planning(AoP) prompt, where traditional algorithms such as DFS, A*, and Dijkstra provide reasoning guidance; and (3) hybrid prompting, which leverages algorithm-generated trajectories or decisions within both direct-answer and reasoning-based prompts. This design facilitates a comprehensive comparison of traditional algorithmic guidance versus independent prompting approaches, and further allows for in-depth analysis of variation within algorithm-guided prompts. To assess scalability and generalization, we construct grid-based environments of three different sizes with increasing complexity. We evaluate the performance of six LLMs, ranging from 7B to 72B parameters, including models from multiple families, such as GPT-4 OpenAI et al. (2024) , DeepSeek DeepSeek-AI et al. (2024) , and QWEN Qwen et al. (2025) . Model performance is assessed using metrics that capture correctness, optimality, and efficiency—-such as format compliance, path validity, solution quality, error from the optimal path, and runtime. This multifaceted evaluation offers a rigorous analysis of how algorithmic guidance affects LLM pathfinding, both in terms of accuracy and efficiency. Through this benchmark, we aim to answer several key questions: To what extent can LLMs benefit from classical search heuristics? How do the different shot strategies affect the traditional algorithm’s guidance for LLM? Do algorithm-guided prompt performance remain indispensable regardless of model scale and map size? Our findings suggest that algorithm-guided prompts achieve better results than vanilla prompts and comparable performance compared with the CoT prompt. While larger models tend to perform better under independent prompting, algorithm-guided strategies significantly boost performance across all model sizes, particularly in larger or more complex environments. Moreover, integrating few-shot learning could further improve the performance of algorithm-guided prompt. These results highlight the complementary strengths of LLMs and classical algorithms and point toward promising directions for hybrid neuro-symbolic planning systems. In conclusion, this study makes three major contributions: • We propose GridRoute, a comprehensive benchmark designed to evaluate LLMs’ route planning abilities in grid-based environments, comparing independent prompting and algorithm-guided strategies. • We introduce AoP prompting, a novel framework that guides LLMs using classical pathfinding algorithms (e.g., A*, Dijkstra, DFS) by embedding their reasoning principles directly into the prompt. • We perform large-scale experiments across multiple LLMs and environment sizes, showing that AoP consistently improves planning performance, especially in complex settings, and offers complementary benefits to traditional CoT prompting. 2 Related Work 2.1 Grid-based route planning Grid-based route planning is central to robotics and embedded systems, especially in warehouse automation, where robots navigate structured indoor environments such as aisles and shelves. These environments are typically modeled as 2D grids with discrete free or occupied cells, offering memory and computational efficiency suitable for embedded platforms. Algorithms such as A* ( Hart et al., 1968 ) , Dijkstra’s Dijkstra (1959) , and variants like Jump Point Search ( Harabor and Grastien, 2014 ) are widely used for computing collision-free, cost-effective paths. Many systems adopt 4-directional movement (up, down, left, right) to reflect real-world layouts and simplify pathfinding. This constraint, along with lightweight planning algorithms, enables real-time decision-making under tight power and timing constraints, making grid-based navigation viable on low-power processors. Figure 1: Struture of GridRoute 2.2 Route planning with LLM Recent advances in large language models (LLMs) have showcased their emerging capabilities in reasoning, planning, and problem-solving. Unlike classical algorithms, LLMs leverage implicit knowledge and contextual understanding, allowing them to generate flexible solutions in unfamiliar scenarios ( Wang et al., 2023 ; Li et al., 2025 ; Wen, 2025 ) . Early studies have demonstrated that LLMs can produce plausible paths or high-level plans in grid-based environments when provided with textual descriptions of the environment, along with specified start and goal positions ( Valmeekam et al., 2023 ; Latif, 2024 ) . However, these outputs are often inconsistent or suboptimal, particularly as the complexity of the environment increases. To address these limitations, recent research has introduced structured reasoning techniques to improve LLM-based planning. For example, the PPNL benchmark investigates the use of Chain-of-Thought (CoT) and ReAct prompting to encourage step-by-step reasoning in route planning tasks. While these methods improve performance over naive prompting, they still do not fully leverage the systematic search capabilities of classical algorithms. In parallel, an emerging line of work explores hybrid approaches that integrate LLMs with traditional pathfinding algorithms such as A* and Dijkstra ( Liu et al., 2023 ) . In these settings, LLMs may generate sub-goals for symbolic planners to solve or invoke classical algorithms as external tools within a CoT-style reasoning framework. Building on this line of work, our study systematically investigates how classical algorithms can be used to guide LLM-based route planners. We focus on grid-based environments, where structured search procedures are well-defined, computationally efficient, and particularly suited for real-time or embedded applications. 3 GridRoute Benchmark This section introduces the design of the GridRoute benchmark, including data generation, evaluation metrics, and error analysis. We