💬 NLP

CompassLLM: A Multi-Agent Approach toward Geo-Spatial Reasoning for Popular Path Query

CompassLLM is a novel multi-agent framework that leverages Large Language Models to solve popular path queries through a two-stage pipeline of searching historical trajectories and generating novel paths, offering superior accuracy and cost-effectiveness compared to traditional methods that require extensive training.

Original authors: Md. Nazmul Islam Ananto, Shamit Fatin, Mohammed Eunus Ali, Md Rizwan Parvez

Published 2026-05-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Md. Nazmul Islam Ananto, Shamit Fatin, Mohammed Eunus Ali, Md Rizwan Parvez

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a tour guide in a busy city, and a tourist asks you: "What is the most popular way to walk from the Botanic Garden to Arthur's Seat?"

To answer this, you have a massive notebook filled with thousands of walking routes taken by other people in the past. This is the problem the paper COMPASSLLM tries to solve.

Here is the breakdown of the paper using simple analogies:

1. The Problem: The "Old Map" vs. The "New Guide"

Traditionally, to find the best route, computers use complex math algorithms or "machine learning" models. Think of these like old, rigid GPS systems.

The Flaw: If the city changes (a new road opens, or a park closes), or if you want to add new data, you have to completely rebuild and retrain the GPS system. It's like having to re-learn how to drive every time a new street is built.
The New Idea: The authors ask, "Can we use a Super-Intelligent Tour Guide (a Large Language Model or LLM) instead?" These guides are great at reading stories and understanding context. They don't need to be retrained; they just need to be told, "Here is the notebook of past walks, find the best path."

2. The Solution: A Team of Specialized Guides (Multi-Agent System)

The paper introduces COMPASSLLM. Instead of asking one giant AI to do everything (which often leads to it "hallucinating" or making up fake roads), they created a team of four specialized agents working together like a well-organized travel agency.

Think of the process as a two-stage journey:

Stage 1: The "Search" (Looking for existing paths)

Agent 1: The Detective (Path Discovery)
- Job: Scans the notebook of past walks. If there is a direct line from Point A to Point B in the history books, the Detective finds it.
- Success: If found, the team moves to the next step.
- Failure: If the Detective looks everywhere and finds no path connecting A and B (maybe the data is too sparse or the route is new), the team switches to Stage 2.

Stage 2: The "Generate" (Building a new path)

Scenario: Imagine the tourist wants to go from the Garden to the Seat, but no one has ever walked that exact route in the notebook.
Agent 2: The Statistician (Popularity Ranking)
- Job: Instead of looking for whole paths, this agent looks at individual road segments. It asks, "Which specific streets are walked on the most?" It creates a list of the "hottest" street connections.
Agent 3: The Architect (Path Synthesis)
- Job: Using the Statistician's list of "hot streets," the Architect builds a new path. They connect the popular street segments together to create a valid route from A to B.
- Crucial Rule: The Architect is strictly forbidden from inventing roads that don't exist in the notebook. They can only use the "hot streets" they were given. This prevents the AI from making up fake bridges or tunnels.
Agent 4: The Judge (Path Selection)
- Job: Now the team has a list of possible paths (some found by the Detective, some built by the Architect). The Judge looks at the "Popularity" of every single landmark (POI) on these paths.
- Decision: The Judge picks the path that passes through the most famous and popular landmarks.

3. Why is this better? (The Results)

The paper tested this team against other methods using real data (like tourists in Edinburgh) and made-up data (synthetic datasets).

Accuracy: When a path already existed in the history books, COMPASSLLM found it better than almost any other method.
Creativity: When no path existed, the team successfully built a new, valid path using popular segments, outperforming other AI methods that often got stuck or made up fake roads.
Cost & Speed: The team is surprisingly efficient. Because each agent has a specific, small job, they don't waste "brain power" (computational tokens) trying to solve the whole problem at once. It's cheaper to run than other complex AI methods.

4. The Catch (Limitations)

The authors are honest about the downsides:

Size Matters: If the notebook of past walks is too huge (larger than the AI's memory window), the system struggles. It's like trying to read a library of books in one sitting; the AI gets overwhelmed.
Consistency: Because the AI is probabilistic (it makes choices based on probability), sometimes it might give a slightly different answer if you ask the same question twice, though the team tries to minimize this.

Summary Analogy

Imagine you are trying to find the best route through a maze.

Old Methods: You hire a robot that has to be programmed with the maze layout every time the walls move.
COMPASSLLM: You hire a team of four experts. One looks for the exit in the history books. If they can't find it, a second expert finds the most popular hallways, a third expert connects those hallways into a new path, and a fourth expert picks the path that goes through the most beautiful rooms. They work together to give you the best answer without needing to be retrained.

The paper claims this "team approach" is the most effective way to use modern AI for finding popular routes in cities and parks.

Technical Summary: COMPASSLLM

Problem Definition

The paper addresses the Popular Path Query problem, which involves identifying the most frequented routes between a source and destination pair based on historical trajectory data. This task is critical for urban planning, navigation optimization, and travel recommendations.

The problem presents two distinct challenges:

SEARCH: Finding the most popular path when a direct route exists in the historical data.
GENERATE: Synthesizing a valid, traversable path when no direct historical route exists between the source and destination (a common issue in sparse datasets where the graph is incomplete).

Traditional algorithmic and machine learning approaches (e.g., Markov models, Neural Networks like NMLR or GEIT) often struggle with these tasks because they require extensive model training, parameter tuning, and retraining when data updates or constraints change. Furthermore, standard Large Language Models (LLMs) applied directly to geo-spatial reasoning often generate invalid or untraversable paths (hallucinations) due to a lack of strict adherence to graph connectivity constraints.

Methodology

The authors propose COMPASSLLM (Coordinated Orchestration of Multi-agent Path Analysis and Spatial Synthesis), a novel multi-agent framework designed to leverage LLM reasoning capabilities without requiring model training. The framework operates through an orchestrated two-stage pipeline involving four specialized agents:

Path Discovery Agent: Acts as the entry point. It analyzes historical trajectories to extract candidate paths where the source precedes the destination. If valid candidates are found, the framework proceeds to the evaluation phase. If the set is empty ( $T_{LLM} = \emptyset$ ), it triggers the GENERATE stage.
Popularity Ranking Agent: Operates in two modes:
- Edge Ranking Mode: Activated conditionally during the GENERATE stage. It ranks individual edges (road segments) based on their frequency in historical data to guide path synthesis.
- POI Ranking Mode: Activated during the SEARCH stage (either after discovery or synthesis). It ranks Points of Interest (POIs) by their occurrence frequency to determine the "popularity" of specific locations.
Path Synthesis Agent: Activated only when no historical path exists. Using the edge rankings from the Popularity Ranking Agent, it constructs new candidate paths by connecting popular edges. Crucially, it is constrained to use only edges present in the historical data, preventing the generation of non-existent connections (hallucinations).
Path Selection Agent: Evaluates all candidate paths (whether discovered or synthesized) by aggregating the popularity scores of their constituent POIs. It selects the path with the highest cumulative popularity score as the final output.

The framework is designed to be training-free, relying on prompt engineering and the inherent reasoning capabilities of LLMs (tested with Llama 3.1 8b, GPT 4o, and GPT o3 mini).

Key Contributions

The paper claims the following contributions:

Novel Framework: Introduction of COMPASSLLM, a multi-agent system specifically architected for popular path queries in geo-spatial domains.
Orchestrated Pipeline: A two-stage workflow that seamlessly integrates path finding (SEARCH) and path synthesis (GENERATE), enabling the system to recommend valid paths even in the absence of historical ground truth.
Comprehensive Evaluation: Extensive experiments on real-world datasets (Edinburgh, Toronto, Melbourne, and theme parks) and synthetic datasets. The study demonstrates that the framework achieves competitive or superior performance compared to state-of-the-art (SOTA) methods while maintaining cost-effectiveness.

Results

The evaluation utilized two primary metrics: F1 Score for the SEARCH problem (measuring accuracy against ground truth) and Traversability for the GENERATE problem (measuring the validity of edges in generated paths).

SEARCH Performance: COMPASSLLM consistently outperformed traditional ML/DL baselines (e.g., Markov, NASR, DeepAltTrip) and other LLM-based approaches (e.g., Direct, CoT, ReAct, Reflexion, LLM-A*, PathGPT). On the GPT o3 mini model, it achieved an average F1 score of 0.80, significantly higher than the next best LLM-based method (PathGPT at 0.65).
GENERATE Performance: In sparse data scenarios where no ground truth path exists, COMPASSLLM demonstrated competitive Traversability scores, matching or exceeding SOTA models like NMLR (which requires retraining) and outperforming other LLM baselines. For instance, on the Edinburgh dataset, it achieved a Traversability of 0.95 with GPT o3 mini.
Cost Efficiency: The framework is highly cost-effective. While methods like APE (Automated Prompt Engineering) achieved strong results, they incurred significantly higher token costs (e.g., 67.7k tokens for the Melb dataset vs. 33.0k for COMPASSLLM). COMPASSLLM balanced high performance with lower computational overhead.
Scalability: The system maintained superior performance as dataset complexity increased (higher number of POIs and trajectories), largely due to its modular agent design which filters data before ranking, reducing context size for downstream agents.

Significance and Claims

The paper positions COMPASSLLM as a significant step forward in applying LLMs to geo-spatial reasoning. Its primary significance lies in:

Adaptability: Unlike traditional models that require retraining for new data or constraints, COMPASSLLM adapts instantly via prompt orchestration, making it suitable for dynamic environments.
Handling Sparsity: It effectively addresses the "sparse data" problem where historical trajectories do not cover all possible source-destination pairs, a scenario where traditional methods often fail or require complex retraining.
Safety and Validity: By explicitly constraining the synthesis agent to use only observed edges, the framework mitigates the risk of generating hallucinated, untraversable paths, which is critical for safety-critical navigation systems.

The authors acknowledge limitations, noting that the system faces challenges with extremely large datasets exceeding LLM context windows (128k tokens) and that the inherent stochasticity of LLMs can occasionally lead to suboptimal paths. However, they conclude that COMPASSLLM offers a "training-free," cost-effective, and highly competitive alternative for popular path queries, particularly in scenarios involving sparse historical data.