💬 NLP

Mango: Multi-Agent Web Navigation via Global-View Optimization

Mango is a multi-agent web navigation framework that optimizes exploration efficiency by dynamically selecting optimal starting URLs via a multi-armed bandit approach and leveraging episodic memory, achieving state-of-the-art success rates on WebVoyager and WebWalkerQA benchmarks.

Original authors: Weixi Tong, Yifeng Di, Tianyi Zhang

Published 2026-04-22

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Weixi Tong, Yifeng Di, Tianyi 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 trying to find a specific, obscure recipe on a massive, chaotic library website.

The Old Way (Traditional Web Agents):
Most current AI web agents act like a person who walks into the library and starts at the front door (the homepage). They have to walk down every single aisle, check every shelf, and read every book title, one by one, hoping to stumble upon the recipe. If the library has 10,000 aisles, this person gets tired, runs out of time (budget), and gives up before finding the recipe. They often get stuck in dead-end aisles or wander around the "History" section when they needed the "Cooking" section.

The New Way (MANGO):
The paper introduces MANGO, a smarter team of AI agents that changes the game entirely. Instead of starting at the front door and walking blindly, MANGO does three clever things:

1. The "Map Maker" (Global Structure Analysis)

Before the team even starts walking, MANGO sends out a tiny, fast drone to quickly scan the library's layout. It doesn't read every book; it just looks at the signs on the doors.

What it does: It builds a rough map of the website.
The Magic: Instead of guessing where to start, it uses a search engine (like Google) to ask, "Where is the recipe section?" and then picks the top 10 most likely doors to enter. It skips the "History" and "Sports" sections entirely.

2. The "Gambler's Strategy" (Thompson Sampling)

Now, the team has 10 candidate doors. They only have enough energy to try a few of them. How do they decide which door to open first?

The Analogy: Imagine a slot machine with 10 levers. You don't know which one pays out, but you want to find the winner quickly.
How MANGO works: It uses a mathematical trick called Thompson Sampling. It's like a smart gambler who says, "Door A looks promising based on the map, so I'll try it first. But I'll also keep Door B in mind just in case."
The Learning: If Door A leads to a dead end, the team marks it as "bad luck" and stops wasting energy there. If Door A leads to a hallway with more clues, the team gets excited and focuses more energy on that path. It constantly updates its "gut feeling" based on what it finds.

3. The "Notebook" (Episodic Memory)

If the team tries a door and fails, they don't just forget it. They write a note in a shared notebook: "Door 3 led to a broken elevator. Don't go there again."

Why it matters: If the team has to try Door 3 again later (maybe they got confused), they check the notebook, see the warning, and avoid repeating the same mistake. This prevents them from running in circles.

The Results

The researchers tested MANGO on two giant websites (like Amazon and educational sites) with very strict time limits.

The Outcome: MANGO found the answers much more often than the old "walk from the front door" method.
The Trade-off: Sometimes MANGO took a few more steps (actions) to solve a really hard puzzle, but it was worth it because it actually solved the puzzle instead of giving up.

In Summary

Think of MANGO as a smart detective who:

Scouts the crime scene from a helicopter first (Global View).
Chooses the best suspects to question based on probability, not random guessing (Thompson Sampling).
Keeps a case file so they never ask the same question twice or chase a dead lead (Episodic Memory).

This approach allows AI to navigate the deep, messy internet much faster and more successfully than ever before, turning a blind search into a targeted hunt.

1. Problem Statement

Existing web navigation agents, powered by Large Language Models (LLMs), typically initiate exploration from a website's root URL (homepage). This approach suffers from significant inefficiencies when dealing with complex, large-scale websites with deep hierarchical structures:

Inefficient Exploration: Agents must traverse the site top-down, often wasting computational budget on irrelevant sub-trees or generic intermediate pages.
Navigation Traps: Without a global view, agents frequently fall into dead ends or fail to locate target information within a limited action budget.
Partial Observations: Prior methods rely on step-by-step decision-making without a holistic understanding of the website's structure, limiting their ability to plan long-horizon tasks effectively.

2. Methodology: MANGO

MANGO (Multi-Agent Navigation with Global-view Optimization) addresses these limitations by constructing a global structural representation of the website before navigation begins. The framework operates through four key stages:

A. Global Structure Analysis

Instead of starting blindly at the root, MANGO first builds a candidate set of relevant URLs ( $U$ ) using a hybrid approach:

Lightweight Crawling: Performs a Breadth-First Search (BFS) from the root URL to collect reachable pages, filtering out non-HTML content and external links.
Search-Based Augmentation: For sites too large to crawl fully (e.g., arXiv), MANGO uses an LLM to generate search keywords based on the user query and leverages Google Search (site operator) to retrieve additional relevant pages.
Relevance Scoring: Uses the BM25 algorithm to score the semantic similarity between the content of these URLs and the user query, selecting the top 10 candidates to form the initial set $U$ .

B. URL Prioritization via Multi-Armed Bandit (MAB)

MANGO models the selection of the next URL to visit as a Multi-Armed Bandit (MAB) problem with finite-lifetime arms.

Thompson Sampling: The system employs Thompson Sampling to dynamically allocate the navigation budget. Each URL is treated as an "arm" with a dynamic status (Active or Exhausted).
Initialization: The Beta distribution parameters ( $\alpha, \beta$ ) for each URL are initialized based on the BM25 relevance scores.
Adaptive Selection: At each step, the agent samples from the posterior distribution of active arms to select the most promising URL.
Dynamic Updates: After a navigation attempt, the distribution is updated based on the outcome (reward). If a URL leads to a dead end, it is marked as "Exhausted."

C. Web Navigation Agent

The navigation agent interacts with the browser environment starting from the selected URL.

Contextual Memory: If a URL has been visited before, the agent retrieves the previous navigation trajectory and reflection summary from Episodic Memory to avoid repeating failed actions.
Budget Constraints: The agent operates under a strict action budget ( $b$ ). If the task is incomplete but the budget is exhausted, control is passed to the Reflection Agent.

D. Reflection Agent

A dedicated reflection agent evaluates the navigation trajectory and final output to determine the status of the attempt:

Success: If the output satisfies the query, the process terminates.
Promising but Incomplete: If the path is relevant but requires more steps (e.g., budget exhaustion), a positive reward ( $r=1$ ) is assigned to maintain a high selection probability for that URL in future iterations.
Dead End: If the path is irrelevant or leads to a dead end, a negative reward ( $r=0$ ) is assigned, and the URL is marked as exhausted.
Memory Storage: All trajectories, outputs, and reflections are stored in episodic memory to prevent redundant exploration.

3. Key Contributions

Global-View Optimization: Unlike traditional agents that start from the root, MANGO constructs a global structural map to identify intent-related entry points, significantly reducing the search space.
Bandit-Based Budget Allocation: The novel application of Thompson Sampling allows for adaptive, probabilistic allocation of the navigation budget across candidate URLs, balancing exploration and exploitation more effectively than static strategies.
Episodic Memory Integration: The system incorporates a memory module that stores navigation history and reflections, enabling the agent to learn from past failures and avoid redundant loops.
Comprehensive Evaluation: The method is rigorously tested across diverse LLM backbones (both open-source Qwen3 and closed-source GPT-5-mini) and benchmarks.

4. Experimental Results

MANGO was evaluated on two benchmarks: WebVoyager (real-world sites like Amazon, Coursera) and WebWalkerQA (multi-domain QA tasks).

Success Rate (SR):
- WebVoyager: MANGO achieved a 63.6% success rate using GPT-5-mini, outperforming the best baseline (AgentOccam) by 7.3%.
- WebWalkerQA: MANGO achieved a 52.5% success rate, surpassing the best baseline by a massive 26.8%.
- Scalability: MANGO consistently outperformed baselines across all five tested backbone models (Qwen3-4B to 32B and GPT-5-mini).
Efficiency (Action Count):
- On Qwen3 models, MANGO maintained competitive or lower action counts while achieving higher success rates.
- On GPT-5-mini, MANGO used more actions but successfully solved significantly more complex, long-horizon tasks that baselines failed to complete.
Ablation Studies:
- Removing the global structure analysis (using random or Google-only selection) significantly reduced performance.
- Replacing Thompson Sampling with Monte Carlo Tree Search (MCTS) resulted in lower success rates (e.g., 46.51% vs. 63.57% on WebVoyager), proving that Thompson Sampling is more efficient for budget-constrained navigation where simulation is costly.

5. Significance and Limitations

Significance:
MANGO represents a paradigm shift in web automation by moving from reactive, step-by-step navigation to proactive, structure-aware planning. It demonstrates that leveraging global website structure and probabilistic budget allocation can drastically improve the success rate of LLM agents on complex web tasks, particularly for multi-source QA and deep-hierarchy sites.

Limitations:

Partial Coverage: The global view is an approximation based on lightweight crawling and search. Extremely large or dynamic sites (e.g., deep e-commerce catalogs) may still have target information missed by the initial candidate set.
Dependency on Initial Relevance: The effectiveness of the bandit selection relies heavily on the quality of the initial candidate set. Poor keyword generation or relevance scoring can lead to early budget misallocation.
Reasoning Errors: Like other LLM agents, MANGO can still fail due to the underlying model's reasoning or reading comprehension errors, which are orthogonal to navigation strategy.
Action Count Trade-off: While effective, MANGO may require more actions to solve difficult tasks compared to baselines that give up early, which could be a concern in latency-sensitive or strictly cost-constrained environments.