💬 NLP

LoHoSearch: Benchmarking Long-Horizon Search Agents Beyond the Human Difficulty Ceiling

To overcome the difficulty ceiling of existing human-authored search benchmarks, this paper introduces LoHoSearch, an automated, knowledge graph-based benchmark featuring 544 complex, long-horizon questions across 11 domains that significantly challenges current state-of-the-art search agents, reducing their accuracy to 34.74%.

Original authors: Jiarui Zhao, Rongzhi Zhang, Lingchuan Liu, Hao Yang, Xunliang Cai, Xi Su

Published 2026-06-12

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Jiarui Zhao, Rongzhi Zhang, Lingchuan Liu, Hao Yang, Xunliang Cai, Xi Su

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

The Big Problem: The "Easy Mode" Trap

Imagine a video game where the goal is to find a specific hidden treasure. For the last year, researchers have been testing AI "search agents" (robots that browse the internet) using a game called BrowseComp.

At first, the game was hard. But because humans designed the questions, they accidentally made them too easy. Humans tend to pick famous things (like "The Eiffel Tower" or "Taylor Swift") and connect them with obvious clues. It's like hiding a treasure behind a door labeled "Treasure."

Because the clues were so obvious, the best AI robots quickly learned to solve 90% of the puzzles. The game lost its ability to tell the difference between a smart robot and a really smart one. The difficulty hit a "ceiling" that human designers couldn't break because they don't have a perfect map of the entire internet to see how many other "treasures" might fit the clues.

The Solution: Building a "Super-Map"

The authors of this paper, LoHoSearch, decided to stop relying on human guesswork. Instead, they built a massive, automated system based on a Knowledge Graph.

Think of this Knowledge Graph as a giant, digital map of the entire internet (specifically Wikipedia), containing over 7 million entities (people, places, things) and how they are connected.

Instead of a human picking a question, the computer uses this map to:

Find the "Hard" Paths: It looks for connections where there are thousands of possible answers, not just one or two famous ones.
Build Complex Mazes: It creates questions that require the robot to check many dead ends before finding the right path.
Verify the Answer: It mathematically proves that only one specific answer fits the clues, ensuring the puzzle is fair.

The New Game: LoHoSearch

The result is a new benchmark called LoHoSearch (Long-Horizon Search). It contains 544 tricky questions across 11 different topics (like music, sports, and movies).

Here is how the new game changes the rules:

The Search Space is Huge: In the old game, if the clue was "Who sang this song?", there might be 5 famous singers. In LoHoSearch, the clue might be "Who sang this obscure song from a specific year in a specific genre?" where there are hundreds of possible singers. The robot has to check them all.
The Maze is Twisted: The questions aren't just a straight line. They are like a tangled web where you have to cross-reference clues that loop back on each other. You can't just guess; you have to think deeply.

The Results: Robots Hit a Wall

The researchers tested the world's smartest AI models on this new game. The results were shocking:

The Old Game: Top models scored over 90%.
The New Game: Even the absolute best model (GPT-5.5) only scored 34.7%.

It's as if the robots went from being "Grandmasters" in chess to struggling to learn the rules of a new, much harder game.

Why Current Tricks Don't Work

When robots get stuck on hard puzzles, they usually try a strategy called "Context Management." Imagine a detective who has written down 100 pages of notes. If the notebook gets too full, the detective tries to summarize the notes or throw away old pages to make room for new ones.

The researchers tested these strategies on LoHoSearch.

On the old easy game, these tricks helped the robots improve by 14%.
On the new hard game, the tricks only helped by 6.8%.

This shows that the problem isn't just about remembering things; the problem is that the "maze" is so complex and the "search space" is so big that the robots' current brains just can't handle the long chain of reasoning required.

The Bottom Line

LoHoSearch proves that we can't just keep making slightly harder human-written questions. To truly test if AI is getting smarter, we need to use a computer-generated map to create puzzles that are mathematically guaranteed to be difficult.

This new benchmark acts as a "stress test" that reveals the current limits of AI. It shows that while AI is great at finding easy answers, it still struggles significantly when it has to navigate a massive, complex web of information to find a single, hidden truth.

Technical Summary: LoHoSearch

Problem Statement

Search agent benchmarks, such as BrowseComp, have rapidly reached a "difficulty ceiling" where even the most advanced models achieve over 90% accuracy. The root cause of this saturation is the reliance on human-authored questions. Human annotators lack a global perspective on entity statistics, leading them to select familiar entities with high popularity and direct connections. Consequently, these benchmarks fail to systematically maximize two core determinants of search difficulty:

Search Space Size: The number of candidate entities satisfying a single constraint.
Structural Complexity: The number of constraints that must be jointly satisfied to uniquely identify an answer.

While reasoning depth (knowledge hops) has been well-addressed by existing benchmarks, the combination of large search spaces and high structural complexity creates a "long-horizon" challenge that current agents struggle with, yet human construction cannot reliably scale to produce.

Methodology

To overcome the limitations of human authorship, the authors introduce LoHoSearch (Long-Horizon Search Agents), a benchmark constructed via an automated pipeline grounded in a large-scale knowledge graph (KG).

1. Knowledge Graph Construction

The pipeline utilizes the full English Wikipedia dump to construct a KG containing approximately 7.62 million entities and 265 million directed edges.

Nodes: Wikipedia pages.
Edges: Hyperlinks between pages.
Attributes: Each entity is assigned a type (via Wikidata P31) and a popularity metric (in-degree).

2. Subgraph Sampling

The system samples two types of subgraphs from the KG to form the basis of questions, ensuring low entity popularity to prevent easy inference:

Tree-Structured Subgraphs: A root node (the answer) connects to intermediate nodes, which connect to leaf nodes. Constraints are selected to ensure:
- Each relation has a large search space ( $|S| > \tau$ ).
- The intersection of candidate sets for all relations equals exactly the root node (guaranteeing uniqueness).
- Removing any single relation leaves multiple candidates (ensuring every relation is necessary).
Graph-Structured Subgraphs: These introduce cyclic dependencies and cross-constraints, making the problem non-decomposable. They are constructed greedily to maximize edge count and search space size while maintaining connectivity and type diversity.

3. QA Generation and Verification

Obfuscation: For each edge in the subgraph, an LLM extracts a natural language description of the relation from the source entity's Wikipedia page. For leaf nodes, additional property descriptions are added.
Search Verification: Relations are verified to ensure they cannot be directly located via search engines or inferred by an LLM without the specific context of the question.
Uniqueness Verification: The system performs exhaustive backtracking searches on the full KG to confirm that no other set of entities satisfies the same structural constraints.
Human Review: The final 544 questions undergo professional human review to verify answer correctness, uniqueness, logical coherence, and language fluency.

Key Contributions

Automated Construction Pipeline: A knowledge-graph-based pipeline that systematically controls search space size and structural complexity, breaking the difficulty ceiling inherent in human-authored benchmarks.
The LoHoSearch Benchmark: A dataset of 544 human-verified questions across 11 topical domains (e.g., Music, Geography, Film). It features structurally complex subgraphs (both tree and graph types) with KG-verified unique answers.
Evaluation of Context Management: The benchmark serves as a rigorous testbed for evaluating long-horizon reasoning and context management strategies, revealing their limitations in high-difficulty scenarios.

Experimental Results

The authors evaluated a range of state-of-the-art models (including GPT-5.5, DeepSeek-V4-Pro, and Claude-Opus-4.6) on LoHoSearch.

Performance Ceiling: Even the strongest model, GPT-5.5, achieved only 34.74% accuracy. The majority of models scored below 14%, with some (e.g., MiniMax-M2.5) scoring as low as 2.29%.
Tool Usage: Correct trajectories on LoHoSearch required significantly more tool calls than on BrowseComp. The mean number of tool calls increased from 35 (BrowseComp) to 61 (LoHoSearch), a 74% relative increase.
Context Management Limitations: The authors tested various context management strategies (Summarization, Discard-all, Verification) on DeepSeek-V4-Flash.
- On BrowseComp, these strategies yielded a 14.03% gain.
- On LoHoSearch, the best strategy (Discard-all + Verify) yielded only a 6.8% gain (from 10.02% to 16.82%).
- This suggests that current context management techniques are insufficient for the extended reasoning chains required by LoHoSearch.
Structural Complexity: Graph-structured questions (8.01% accuracy) proved significantly harder than tree-structured ones (11.89% accuracy), highlighting the impact of cyclic dependencies.
Parallel Sampling: Using a "best-of-N" strategy with 16 samples improved performance to 24.6%, indicating substantial room for improvement through repeated sampling, though still far below human-level performance on easier benchmarks.

Significance and Claims

The paper claims that LoHoSearch provides a more demanding and discriminative standard for evaluating search agents. By leveraging a knowledge graph to systematically maximize search space and structural complexity, the benchmark successfully creates a difficulty level that current models cannot easily overcome.

The authors argue that LoHoSearch is significant because:

It exposes the limitations of existing context management strategies, showing that gains observed on prior benchmarks do not translate to high-difficulty, long-horizon tasks.
It demonstrates that human annotation cannot scale to create truly difficult questions due to a lack of global statistical perspective, necessitating automated, KG-driven construction.
It establishes a new baseline where even the most advanced models struggle, providing a necessary testbed for future research into long-horizon reasoning and robust context handling.

The authors acknowledge limitations, including the current restriction to English, the static nature of the evaluation set, and the reliance on LLM judges for grading, which may introduce noise. They also note that for a subset of questions, answer uniqueness could not be conclusively confirmed by human annotators, though no alternatives were found via thorough search.