🤖 AI

MapSatisfyBench: Benchmarking Satisfaction-Aware Map Agents through Behavior-Grounded Implicit Decision Factors

This paper introduces MapSatisfyBench, a new benchmark constructed from real-world data and a restore-identify-filter framework to evaluate large language model agents' ability to proactively recover implicit decision factors and satisfy user needs in map services, revealing that current agents excel at explicit tasks but struggle with satisfaction-aware spatial decision-making.

Original authors: Lubin Bai, Mengyu Cao, Sixue Wang, Zhongwei Wan, Yue Pan, Jiale Hou, Xiang Li, Xiuyuan Zhang

Published 2026-06-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Lubin Bai, Mengyu Cao, Sixue Wang, Zhongwei Wan, Yue Pan, Jiale Hou, Xiang Li, Xiuyuan Zhang

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 asking a friend for directions to a restaurant. You say, "Take me to a good place to eat."

A basic map agent (like a standard GPS) would hear "place to eat" and immediately spit out the nearest three restaurants. It followed your literal instruction perfectly. But if you just got off a train, have no car, and are carrying heavy luggage, the "nearest" place might be a fancy steakhouse up a steep hill with no elevator. Your friend would say, "That's a bad suggestion! I need somewhere flat and accessible."

The paper MapSatisfyBench argues that current AI map agents are too much like that basic GPS. They are great at following orders, but they are terrible at reading the room. They don't "get" the hidden reasons (called implicit decision factors) that actually make a suggestion useful to you.

Here is the breakdown of their work using simple analogies:

1. The Problem: The "Unspoken Wish"

When you ask a map app for help, you rarely say everything. You might say, "Find me a coffee shop," but you actually mean, "Find me a coffee shop that is open right now, has a power outlet, and is quiet because I'm on a call."

The Old Way: The AI gives you a list of coffee shops. If you have to ask, "Wait, is this one open?" or "Do they have outlets?", the AI failed you.
The New Goal: The AI should act like a mind-reading concierge. It should look at your history (you usually work from cafes), your location (you are near a train station, so you probably don't have a car), and the time (it's 8 PM, so it's late) to guess your hidden needs before you even ask.

2. The Solution: The "Detective Framework"

The authors created a new testing ground called MapSatisfyBench. To build this, they invented a three-step "Detective Framework" to figure out what the user really wanted, even if they didn't say it:

Restore (The Time Traveler): The system looks at the "behavior chain." It doesn't just look at the question; it looks at what you did before (your history) and what you did after (did you actually go to the place the AI suggested?). It reconstructs the full story of your day.
Identify (The Gap Finder): It compares what you said ("Coffee shop") with the full story ("I'm tired, I need a seat, and I need Wi-Fi"). It spots the missing pieces.
Filter (The Realist): This is crucial. The AI can only guess things it has evidence for. If the AI has no data about your past preferences, it can't guess them. This step filters out "magic guesses" and keeps only the "smart guesses" based on real evidence.

3. The Test: The "Sandbox"

They built a deterministic replay sandbox. Think of this as a video game simulation where the rules never change.

They feed the AI a user's question and the "clues" available (like your profile or the weather).
The AI has to make a decision.
The system checks: Did the AI pick the right tools? Did it guess the hidden needs correctly? Did it ask you too many annoying questions?

4. The Results: "Smart" vs. "Satisfied"

They tested 12 different AI models (the "brains" behind the agents). Here is what they found:

The Good News: The AIs are excellent at Explicit Tasks. If you say "Drive me to the airport," they get you there. They are like perfect clerks who follow the rulebook.
The Bad News: The AIs are struggling with Implicit Satisfaction. They are like clerks who follow the rulebook but ignore the customer's mood.
- They often fail to check their own "memory" (user profiles) to see if you prefer trains over buses.
- They often ask you too many questions ("Do you want to drive or take the bus?") instead of just checking your history to know you hate driving.
- Even the "smartest" models (the ones with "thinking mode" enabled) only got slightly better at guessing your hidden needs. They still mostly stick to the literal text.

The Bottom Line

The paper concludes that we need to stop judging map agents just on whether they can "finish the task." Instead, we need to judge them on whether they can make a decision that feels right to the user.

Currently, AI map agents are like very obedient but slightly clueless assistants. They will do exactly what you tell them, but they haven't learned how to be proactive enough to figure out what you actually need before you have to explain it to them. MapSatisfyBench is the new report card designed to teach them how to be less robotic and more human-like in their understanding.

Technical Summary of MapSatisfyBench

Problem Statement
Large Language Model (LLM) agents are increasingly deployed in map services to translate natural language requests into actions like route navigation and trip planning. However, real-world map queries are often underspecified; users provide short, incomplete requests while expecting the agent to infer unspoken needs. Unlike fact-seeking questions with unique ground truths, map tasks are inherently multi-solution. The core challenge is that user satisfaction depends on implicit decision factors—critical conditions not explicitly stated in the query (e.g., a user arriving by train needing public transit over driving) but recoverable from available information sources like user profiles and interaction history.

Current benchmarks primarily evaluate task completion (can the agent plan a route?) or factual faithfulness. They fail to measure whether an agent can proactively recover these implicit factors to select the response most likely to be accepted by the user. Furthermore, evaluating this ability is difficult because: (1) not all implicit factors are recoverable from pre-response information, and (2) satisfaction cannot be reduced to a single reference answer or a binary satisfied/unsatisfied label.

Methodology
To address these challenges, the authors propose a restore-identify-filter framework and construct MapSatisfyBench, a benchmark grounded in behavior-chain evidence.

Framework Construction:
- Restore: Reconstructs the complete user need by combining pre-query information (context $c$ , profile $p$ ), the spatio-temporal environment ( $g$ ), and post-query user behavior ( $h^+$ ). This creates an objective basis for what the user intended.
- Identify: Compares the reconstructed complete need with the surface query to expose unspoken decision factors that narrow the feasible solution space.
- Filter: Retains only those implicit factors supported by evidence available before the agent responds (i.e., $g$ and $h^-$ ). Factors requiring post-response clarification or unavailable data are excluded to ensure evaluability.
Ground Truth Annotation:
Instead of a single gold answer, the benchmark defines a structured decision reference $G(x)$ containing:
- Explicit Factors ( $E(x)$ ): Derived from the surface query.
- Evaluable Implicit Factors ( $Z_{eval}(x)$ ): Recovered via the framework, annotated with a constraint type (Hard vs. Soft) and an evidence-supported weight ( $s_i$ ). Hard constraints (e.g., unavailable transport) are binary; soft preferences are graded.
- Execution Annotations: Clarification policies, expected tool trajectories, and factual response requirements.
Evaluation Environment:
The benchmark operates in a Deterministic Replay Sandbox. It simulates a user agent driven by the complete need and a business agent (the model under test) interacting with a fixed set of 22 map-service tools. Tool responses are deterministic mocks to ensure reproducibility.
Metrics:
The evaluation covers the full decision pipeline with seven metrics:
- ECR (Explicit-decision-factor Completion Rate): Measures satisfaction of stated requirements.
- IISR (Implicit-decision-factor Satisfaction Rate): A weighted average of satisfaction scores for implicit factors, distinguishing between hard constraints and soft preferences.
- AR (Accepted-response Probability): The primary aggregate metric, calculated as $ECR \times IISR$ . It represents the probability a response would be accepted.
- TS (Tool Selection Accuracy): Measures correct selection of tools required to recover evidence.
- IFS (Information Faithfulness Score): Checks factual claims against tool outputs.
- Eff (Interaction Efficiency): Normalizes the number of interaction turns against a reference budget.
- SES (Satisfaction Efficiency Score): A composite metric ( $AR \times Eff$ ) rewarding high-quality decisions made efficiently.

Key Contributions

Methodology: A novel approach to operationalize subjective user satisfaction into objective, behavior-supported implicit decision factors, enabling evaluation without direct satisfaction labels.
Benchmark: The construction of MapSatisfyBench, derived from large-scale, real-world anonymized user data, covering diverse map-service scenarios with full-chain evaluation protocols.
Diagnostic Insights: Empirical evidence revealing a persistent gap between surface task completion and satisfaction-aware decision making in current LLM agents.

Experimental Results
The authors evaluated 12 LLM-based agents (including GPT-4.1/5.3, Claude Opus/Sonnet 4.6, Gemini 3.1, DeepSeek, and Qwen families).

Task Completion vs. Satisfaction: Frontier models achieved high ECR scores (e.g., GPT-5.3 at 0.9272), indicating strong ability to complete explicit tasks. However, IISR and AR scores were significantly lower (best IISR was 0.7170 for Claude-4.6-opus), showing a failure to satisfy implicit needs.
Tool Selection Bottleneck: TS scores were consistently low (ranging from 0.28 to 0.49), even for top models. Analysis revealed that agents rarely proactively invoke profile-related tools to recover implicit evidence, preferring instead to ask users for clarification, which increases interaction burden.
Thinking Mode: Enabling "thinking mode" improved performance for some models (e.g., Gemini-3.1-pro-preview SES increased from 0.2120 to 0.2724) but did not fully close the gap between explicit and implicit satisfaction.
Domain Variance: Performance varied by domain; itinerary planning was easiest, while real-time information queries and ride-hailing were most difficult. Agents struggled most with spatio-temporal factors compared to context or preference-based factors.

Significance
The paper claims that MapSatisfyBench shifts the evaluation paradigm for map agents from "whether the task is finished" to "whether the decision satisfies the user." The findings suggest that current agents, while capable of planning and retrieving facts, lack the ability to proactively acquire evidence from available sources to resolve ambiguity. The benchmark serves as a diagnostic tool to guide the development of agents that can align open-ended spatial decisions with behavior-supported user needs, reducing unnecessary user interaction while improving decision quality.