💬 NLP

Searching the Internet for Challenging Benchmarks at Scale

This paper introduces a fully automatic, cost-efficient framework that models the Internet as a vast topic space and utilizes a multi-armed bandit strategy to dynamically discover and construct challenging benchmarks that avoid the saturation issues plaguing static test sets.

Original authors: Wenda Xu, Vilém Zouhar, Parker Riley, Mara Finkelstein, Markus Freitag, Daniel Deutsch

Published 2026-05-08

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Wenda Xu, Vilém Zouhar, Parker Riley, Mara Finkelstein, Markus Freitag, Daniel Deutsch

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 teacher trying to grade a student who is getting incredibly smart, very fast. You have a stack of old math tests (benchmarks). At first, the student struggled with them, so you could easily see where they needed help. But now, the student is acing every single question on those old tests. They get 100% on everything.

The problem? You can't tell if they are actually a genius or if they just memorized the answers to those specific tests. You need a new, harder test to see where they really struggle. But making a new test by hand is slow, expensive, and experts might accidentally make it too easy or too hard based on their own biases.

This paper proposes a clever, fully automatic way to find the "hardest questions" in the entire world (the Internet) without needing a human to write them.

The Big Idea: The Internet as a Giant Buffet

Think of the Internet as a massive, endless buffet with thousands of different food stations (topics). Some stations serve simple snacks (like "how to make toast"), while others serve incredibly complex, spicy dishes (like "legal loopholes in international tax law").

The authors want to find the "spiciest" dishes—the topics where even the smartest AI models choke. But they can't taste every single dish on the buffet; that would take forever and cost a fortune.

The Strategy: The "Smart Taster" (Multi-Armed Bandit)

Instead of tasting everything, the authors treat this like a game of slots or a "smart taster" using a strategy called a Multi-Armed Bandit.

The Slots: Each topic on the Internet (e.g., "Baroque music," "Concrete masonry," "Gas welding") is like a slot machine.
The Cost: Pulling the lever (sampling a text from that topic and testing the AI) costs money and time.
The Goal: Find the slot machine that pays out the most "difficulty" (where the AI fails the most) using the fewest pulls possible.

The paper uses a specific strategy called $\epsilon$ -greedy. Imagine you are in a casino:

Exploration (The Wild Card): Sometimes, you try a machine you've never touched before, just to see what it does.
Exploitation (The Winner): Most of the time, you keep pulling the lever on the machine that has been paying out the most "difficulty" so far.

By balancing these two, the system finds the hardest topics incredibly fast. The paper claims this method only needs to check 6% of the available topics to find the hardest ones, saving 100 times the cost compared to checking everything.

What They Found

They tested this on two things:

Machine Translation: Asking the AI to translate text from English to other languages.
Knowledge Questions: Asking the AI factual questions.

The Results:

Old Tests vs. New Finds: The topics their system found were much harder than the standard tests used by experts today (like WMT or FLORES).
Short but Sweet: Interestingly, the hardest texts they found were often shorter than the hard texts in existing benchmarks. This proves that length isn't what makes things hard; it's the specific, tricky concepts (like legal terms or obscure facts) that trip up the AI.
Real Weaknesses: The errors the AI made on these new tests weren't just "silly mistakes." They were deep issues with terminology (using the wrong word for a specific field) and accuracy (getting the facts wrong). This shows the tests are actually finding real weaknesses, not just confusing the AI with long sentences.

The "Hacking" Check

A smart reader might ask: "Did the AI just find questions that are hard for other AIs to grade, but easy for the real world?"

The authors checked this by using two different "judges" (scoring systems) that don't know each other. They found that when the system found a hard topic, both judges agreed it was hard. This proves the system isn't "hacking" the scoring system; it's finding genuinely difficult content.

The Bottom Line

This paper introduces a tool that automatically hunts for the "final boss" level of difficulty in the AI world. Instead of humans manually curating hard tests, the system searches the Internet, learns where the AI fails, and builds a new, tougher benchmark. This allows researchers to see the true limits of AI models as they get smarter, ensuring we don't just think they are perfect because they passed the old, easy tests.

Key Takeaway: The Internet is a goldmine of hard problems. This paper gives us a map to find them quickly and cheaply, so we can keep testing AI models against the real world, not just against old textbooks.

Technical Summary: Searching the Internet for Challenging Benchmarks at Scale

Problem Statement

Static benchmarks for Large Language Models (LLMs) are rapidly saturating. As models improve, they achieve near-perfect scores on fixed test sets (e.g., WMT, FLORES), leaving little "headroom" to expose genuine weaknesses. Even expert-curated challenge sets quickly become saturated as models "hillclimb" them, requiring costly and repetitive manual curation to refresh. The central challenge is to automatically and continuously construct challenging benchmarks at scale that reveal true model limitations without relying on human intuition, which often misaligns with actual model failure modes (e.g., humans may perceive "Baroque music" as hard, while models fail on "concrete masonry" due to specialized terminology).

Methodology

The authors propose a fully automatic framework that treats the Internet as an effectively unbounded reservoir of content and formalizes the search for difficult topics as a Multi-Armed Bandit (MAB) problem.

1. Topic Space Construction

The framework constructs a hierarchical topic space ( $T$ ) starting from broad seed categories (e.g., "science," "business") and recursively specializing them into finer subtopics using a prompted LLM. This process generates a tree of approximately 3,200 leaf topics (e.g., "corporate finance" $\to$ "cash flow forecasting").

2. Sampling and Difficulty Estimation

The system operates via a sample-and-evaluate loop:

Grounded Generation: For a selected topic, an LLM uses Google Search to retrieve real-world snippets, extracting text and source URLs to ensure grounding.
Difficulty Scoring: The framework generates model outputs for the sampled text and estimates quality.
- Machine Translation (MT): Uses GEMBA (an LLM-as-a-judge metric based on Gemini-2.5-Pro) to assign a quality score. Difficulty is defined as $100 - \text{quality score}$ .
- Knowledge Question Answering (KQA): Generates factual Q&A pairs from retrieved snippets. Difficulty is estimated by the error rate across multiple model configurations (e.g., with/without "thinking" or search).
Cost Model: Each query (sampling + generation + evaluation) has a unit cost. The goal is to identify the top- $k$ most difficult topics within a fixed budget $B$ .

3. Search Algorithm: $\epsilon$ -Greedy

The search is modeled as a Best Arm Identification problem. The authors compare several strategies:

Brute-force: Random sampling (inefficient).
Greedy: Pure exploitation of the currently best topic (requires sampling all topics once first, which is expensive).
$\epsilon$ -Greedy: Stochastically switches between exploration (sampling unsampled topics with probability $\epsilon$ ) and exploitation (sampling the currently best topic with probability $1-\epsilon$ ).

The $\epsilon$ -greedy strategy allows the system to begin exploiting promising topics early without waiting to score every topic in the space, significantly reducing the budget required to find the hardest content.

Key Results

Efficiency and Cost Reduction

Search Efficiency: $\epsilon$ -greedy identifies near-oracle difficulty levels by exploring only 6% of the search space in the MT task and ~10% in the KQA task.
Cost Reduction: This represents a 100 $\times$ cost reduction compared to exhaustive evaluation. For example, achieving a top-10 difficulty of 19.7 cost $104 with $\epsilon$ -greedy, whereas brute-force would require $10,403 to reach similar levels.
Convergence: $\epsilon$ -greedy converges to accurate difficulty estimates ( $\Delta < 0.12$ ) by step 5,000, whereas brute-force fails to converge even at step 6,000.

Benchmark Quality

Superiority to Existing Benchmarks: The automatically discovered topics (e.g., "Prison vs. Jail," "Leasehold Estates") are significantly more difficult than subsets from WMT 2024/2025 and FLORES, despite having lower average word counts. This confirms the difficulty stems from content complexity (terminology, legal nuance) rather than text length.
Robustness: The discovered difficulty is robust across:
- Languages: High performance in both high-resource (English $\to$ Chinese) and lower-resource (English $\to$ Ukrainian) pairs.
- Models: The challenge topics remain difficult for frontier models (Gemini-2.5-Pro) and open-source models (Gemma-3-27B).
- Metrics: Validation using independent metrics (MetricX) confirms that the search does not merely exploit biases of the primary estimator (GEMBA).

Error Analysis

Analysis of the discovered test set using AutoMQM reveals that 90% of errors fall into Terminology (47.7%) and Accuracy (42.3%) categories. Fluency and style errors are minimal (~10%), indicating that modern LLMs have largely solved fluency, and the remaining frontier lies in domain-specific terminology and factual accuracy. Different models exhibit distinct error profiles on the same data, confirming the benchmark exposes genuine, model-specific weaknesses.

Reproducibility

The entire pipeline was successfully replicated using the open-source Gemma-27B-it model for all generation steps (topic proposal, text extraction, difficulty estimation), demonstrating that the framework does not depend on proprietary frontier models.

Significance and Claims

The paper claims to establish a path from static, manually curated benchmarks to dynamic, automatically constructed ones that evolve alongside model capabilities.

Task-Agnostic Framework: The MAB formulation transfers effectively across diverse tasks (MT and KQA) without task-specific modifications.
Mitigation of Proxy Over-Optimization: The authors demonstrate that relying on a single metric can lead to "metric hacking." They propose two cost-free mitigation strategies: (1) Ensembling architecturally diverse metrics (e.g., GEMBA + MetricX) and (2) Early stopping guided by a held-out independent metric.
Scalability: The framework scales to arbitrarily large topic spaces (tested up to 1M synthetic topics) with predictable logarithmic gains in difficulty.
Community Accessibility: By proving the pipeline works with open-source models and providing detailed prompts and pseudocode, the authors make the construction of challenging benchmarks accessible to the broader research community, reducing reliance on expensive, closed-source APIs.

In summary, the work argues that the Internet, when searched efficiently via bandit algorithms, provides a sustainable, low-cost source of challenging content that exposes the genuine "tail" of model performance distributions, addressing the critical issue of benchmark saturation.