Searching the Internet for Challenging Benchmarks at Scale

• Static benchmarks reach near-perfect scores and expert-curated challenge sets quickly saturate, requiring repeated, costly manual refreshes.Source: §1 · p. 1
• The framework searches the Internet efficiently as a source of challenging content beyond existing benchmarks.Source: §1 · p. 2
• Internet content is vast, but manual curation is infeasible at scale, and human-perceived topic difficulty does not reliably predict model failures.Measuring difficulty requires costly sampling and evaluation, making exhaustive searches across tens of thousands of topics computationally intractable.Source: §1 · p. 2
• The paper treats each topic as a bandit arm and allocates costly queries to identify topics yielding consistently challenging examples.Source: §1 · p. 2
• The framework is validated on machine translation and knowledge question answering, with discovered difficulty robust across independent metrics, languages, and models.Source: §1 · p. 2

2.1 Topic Space Construction

• The topic space recursively expands broad seed categories into five-level trees, yielding 3.2k leaf topics, though predefined taxonomies can replace this construction.Source: §2.1 · p. 2

2.2 Sampling and Difficulty Estimation

• For each query, web search retrieves topic-relevant text; difficulty is estimated across model outputs, using GEMBA-derived scores for MT and model error rates for KQA.Source: §2.2 · pp. 2–3

2.3 Finding Difficult Topics as a Multi-Armed Bandit

• With budget B, the objective is to select k topics with the highest expected average difficulty, treating each sample-and-evaluate query as a unit-cost draw.Source: §2.3 · p. 3

2.4 Search Algorithms

• Brute force samples topics randomly; greedy exploits the hardest observed topic after all topics are sampled, while ε-greedy probabilistically alternates exploration and exploitation.Source: §2.4 · p. 4
• Batching selects top-b topics together to regularize against local minima; a keyword-similarity contextual variant interpolates neighbor difficulty, but ε-greedy matched or outperformed it.Source: §2.4 · p. 4

3 Experiments

• The experiments instantiate the framework on machine translation and knowledge question answering, targeting the most difficult topics among thousands of candidates.Translation covers four target languages; the QA setup retains 5,160 domains after filtering context-dependent questions.Source: §3 · p. 4

3.1 Search Algorithm Comparison

• By 4,500 steps, ϵ-greedy reaches machine-translation near-oracle difficulty (∆< 0.1) at 6% of full evaluation cost; for knowledge QA it recovers near-oracle difficulty using ∼10% of subtopics.Figure 2 compares top-10 difficulty at equal budgets across both tasks.Source: Figure 2 · p. 5, §3.1 · p. 5

3.2 Discovered Challenge Topics Surpass Existing Benchmarks

• Discovered oracle topics match or exceed established benchmark difficulty despite shorter texts, and the full difficulty distribution shifts rightward relative to brute-force sampling.The comparison includes WMT 2024, WMT 2025, and FLORES-101; the paper reports that the five top topics exceed most benchmark subsets.Source: §3.2 · pp. 5–6, Table 1 · p. 5

3.3 Scaling to Larger Topic Spaces

• On synthetic sets of 10k and 1M topics, the algorithms reach near-oracle difficulty at ∼1.5 samples per topic (∼6%); difficulty grows approximately logarithmically with topic-space size.A 10× increase in |T| yields roughly +5 difficulty, consistent with log |T| extreme-value scaling.Source: §3.3 · p. 6, Figure 3 · p. 6, Figure 4 · p. 6

3.4 Monetary Cost of Benchmark Construction

• For only $104, ϵ-greedy achieves top-10 difficulty of 19.7, which brute search cannot reach even at $10,403—a 100× cost reduction.The framework is estimator-agnostic, so cheaper quality estimators can reduce per-query costs while retaining the same MAB search framework.Source: §3.4 · p. 6, Table 2 · p. 7

3.5 Robustness Across Languages and Models

• ϵ-greedy finds near-optimal challenge samples across all four languages, including English→Chinese, and difficult topics transfer across related languages and models.The paper gives Czech and Ukrainian as an example of cross-language transfer and reports robustness even against Gemini-2.5-Pro.Source: §3.5 · p. 7, Table 3 · p. 7

3.6 Cross-Metric Validation and Proxy Over-Optimization

• GEMBA-SQA-guided search also raises independent MetricX difficulty from 8.03 to 12.7 over 6,000 steps, while combined metric guidance gives the best trade-off across both metrics.Using MetricX alone raises its difficulty from 17.3 to 20.1 while GEMBA-SQA falls from 6.47 to 5.57; the paper proposes metric ensembling or held-out-metric early stopping as mitigations.Source: §3.6 · p. 7, Table 4 · p. 8

3.7 Reproducibility with Open-Source Models

• With Gemma-27B-it for content generation, ϵ-greedy reaches difficulty 20.83 at step 6,000 and 22.13 at step 10,000, against an oracle difficulty of 30.2.The relative algorithm ordering and performance gaps match the Gemini-based results, supporting reproducibility without proprietary models.Source: §3.7 · p. 8, Table 5 · p. 8

• The authors interpret the terminology and accuracy pattern as reflecting remaining SOTA translation weaknesses, consistent with Kocmi et al..Source: §4 · p. 8
• Error profiles vary by model: Gemma-3-27b has more fluency errors (14.2% vs. 8.7%), while Gemini-2.5-Pro has more accuracy errors (53.7% vs. 37.6%).The authors characterize these as distinct model weaknesses surfaced by the benchmark.Source: §4 · pp. 8–9
• AutoMQM labels error locations, categories, and severity independently of the search process, complementing GEMBA-SQA’s scalar difficulty score.Source: §4 · p. 8
• 90% of errors were terminology (47.7%) or accuracy (42.3%), while fluency and style made up only ∼10%.The breakdown covers 250 challenge examples across four language directions and three models.Source: §4 · p. 8, Table 6 · p. 9

• Prior difficult-example searches rely on known cues such as syntactic complexity or rare words, while other approaches generate difficult-to-translate texts or adversarial examples [25] [28].Example-level difficulty can be estimated with reference-free metrics such as SEScore [17] [18], InstructScore, COMET [20], or MetricX.Source: §5 · p. 9
• This work frames topic search as best arm identification, unlike bandit applications to translation efficiency, training-data selection, or curriculum learning [29] [30].Source: §5 · p. 9
• Unlike active learning over a fixed pool or curriculum learning that orders known examples, this framework searches the Internet for new examples and difficult topics; its discoveries can feed either approach.Source: §5 · p. 9

• The bandit-based pipeline identifies difficult topics while exploring 6% of the search space, a 100× cost reduction versus exhaustive search, with gains over established MT benchmarks and on knowledge QA.The conclusion also reports cross-metric validation and robustness across languages and models.Source: §6 · p. 9
• The full pipeline can be reproduced with open-source models, supporting broader research access to automatically constructed benchmarks.Source: §6 · pp. 9–10
• Future work could extend the approach to mathematical reasoning, code generation, or safety, or use discovered examples for targeted training through active learning.Source: §6 · p. 10

• On MT, ϵ-greedy comes within Δ<1 of oracle difficulty by step 5,000; on knowledge QA, it recovers oracle-level difficulty after exploring ∼10% of the subtopic space.Source: A Ablation: Top-1 Topic Performance · p. 13
• Top-1 performance is noisier than top-10 because it depends on one topic rather than an average over ten, making ϵ-greedy’s exploration-exploitation advantage more pronounced.Source: A Ablation: Top-1 Topic Performance · p. 13
• The top-1 trends confirm that the main-paper findings are robust to the choice of k and hold across both evaluation tasks.Source: A Ablation: Top-1 Topic Performance · p. 13

Per-language results

• ϵ-greedy identifies near-optimal challenge topics across all four language directions, including English→Chinese, where baseline performance is already strong.The convergence rate is similar across languages.Source: B Robustness Across Languages and Models · p. 13

Per-model results

• ϵ-greedy dominates the other search algorithms across Gemini-2.5-Pro, Gemma3-27B, and Google Translate.The relative algorithm ordering is preserved across all three models.Source: B Robustness Across Languages and Models · p. 13
• The search still identifies challenging topics when Gemini-2.5-Pro, also the quality estimator, is the evaluated model.This addresses the concern that the framework only finds topics difficult for its estimator.Source: B Robustness Across Languages and Models · p. 13

Relationship to Active Learning and Curriculum Learning

• Unlike active learning, which selects examples from a fixed pool to label, this method searches the unbounded Internet for new examples.The discovered examples could also be used by active learning.Source: C Relationship to Active Learning and… · p. 13
• Unlike curriculum learning, which orders known training examples by difficulty, this method identifies difficult topics in the first place.The discovered examples could also be used by curriculum learning.Source: C Relationship to Active Learning and… · p. 13
• The contribution is applying Best Arm Identification to this setting, not proposing a novel bandit algorithm; simple ϵ-greedy yields 100× savings over brute force.The search algorithms perform consistently across language directions and identify challenging source texts across models.Source: C Relationship to Active Learning and… · pp. 13–14, Figure 7 · p. 14, Figure 8 · p. 14

Dataset construction

• The dataset contains 5,160 domains, each with 25 subtopics, after filtering domains with context-dependent questions.Questions are generated from retrieved Google snippets but are intended to be answerable without that context.Source: D Knowledge Question Answering · p. 14

Evaluation

• Generated question–response pairs are treated as ground truth, and difficulty is estimated by averaging answer quality across three Gemini configurations.Those configurations use no thinking, default thinking, and search turned on.Source: D Knowledge Question Answering · p. 14

Results

• 10% of the search space (13k of 130k subtopics) recovers oracle difficult samples, and ϵ-Greedy performs better as the budget grows.Bandit-based algorithms greatly outperform brute force; Greedy (10%) finds sub-optimal domains quickly at early steps.Source: D Knowledge Question Answering · pp. 14–15

E Estimated vs. Actual Difficulty

• ∆=3.65 at step 1,000 and ∆<0.12 by step 5,000 for ϵ-greedy, which reaches faithful difficulty estimates sooner than the other methods.Both ϵ-greedy and Greedy (no cap) approach near-zero ∆ by step 6,000, but ϵ-greedy is reliable sooner.Source: Table 7 · p. 15, E Estimated vs. Actual Difficulty · p. 15
• ∆≈19–25 persists for brute force, including ∆=19.19 at step 6,000, as sparse uniform sampling leaves top-k selection vulnerable to chance scores.With about 6,000 samples over 35k+ topics, each topic receives fewer than one sample on average.Source: Table 7 · p. 15, E Estimated vs. Actual Difficulty · p. 15
• Top-D (D=10%) reaches ∆=0.09 at step 2,000 but its actual difficulty plateaus at 18.26, below ϵ-greedy’s 23.98 and the oracle’s 24.56.Its restricted search space prevents it from discovering harder topics outside the top 10%.Source: Table 7 · p. 15, E Estimated vs. Actual Difficulty · p. 15

F Difficult Texts Rank Models Better

• The ϵ-greedy challenge set outperforms random selection on the reported measures, while the highest-variance challenge does not perform consistently across criteria.The measures include statistical discriminability, average difficulty, differences in average model scores, and subset-to-full-set ranking similarity.Source: F Difficult Texts Rank Models Better · p. 16, Figure 9 · p. 16

G.1 Contextual Bandit

• Unsampled topics can be deprioritized when their neighbors are easy; topics with difficult neighbors are prioritized, with keyword overlap measured by Jaccard index.The illustration contrasts likely-easy gas welding topics with likely-difficult harpsichord in baroque music.Source: §G.1 · p. 16, Figure 10 · p. 16

G.2 Upper Confidence Bound Bandit

• Upper confidence bound search still requires sampling every initial topic; its benefit is faster descent only after initialization.The paper notes that the initialization cost is substantial relative to the already steep descent of its method.Source: §G.2 · p. 16

H Per-Model Error Profile Analysis

• The same English→Ukrainian test set elicits markedly different error profiles from Gemma-3-27b and Gemini-2.5-Pro.The analysis presents this variation as evidence that the examples probe model-specific weaknesses rather than superficial difficulty.Source: H Per-Model Error Profile Analysis · pp. 17–18
• 14.2% of Gemma-3-27b errors are fluency/style errors, compared with 8.7% for Gemini-2.5-Pro.The passage associates these errors with grammatical mistakes, awkward phrasing, and register mismatches.Source: H Per-Model Error Profile Analysis · p. 17
• 53.7% of Gemini-2.5-Pro errors are accuracy errors, compared with 37.6% for Gemma-3-27b.The passage describes these as meaning-altering mistranslations, omissions, or additions.Source: H Per-Model Error Profile Analysis · p. 17
• Terminology errors affect 48.2% of Gemma-3-27b errors and 37.6% of Gemini-2.5-Pro errors, making them common to both.The relative balance differs: Gemma’s errors are more terminology-heavy, while Gemini’s skew toward accuracy errors.Source: H Per-Model Error Profile Analysis · p. 17

I Cost Analysis

• Grounded search costs $35 per 1,000 requests, and each topic typically requires three queries to collect 25 source sentences.Data-generation prompts averaged 146 input tokens and 94 generated source-output tokens; translation prompts and outputs averaged 107 and 76 tokens, respectively.Source: I Cost Analysis · p. 18

J.1 Topic Generation Prompt

• The topic-generation prompt requests a nested concept tree with specified depth and branching, using self-contained node names suitable for Google search.The prompt also specifies the root domain and output format.Source: §J.1 · p. 18

J.2 Source Text Sampling Prompt

• The source-sampling prompt asks Google Search to retrieve distinct, relevant snippets of approximately 20–40 words for a topic and language.The requested output is a JSON list of extracted snippets and source URLs.Source: §J.2 · pp. 18–19

J.3 Quality Estimation Prompt; J.4 Translation Prompt

• The MT quality-estimation prompt scores translation quality from 0 to 100, while the translation prompt requests only the translation inside designated tags.The quality prompt asks for brief consideration of error severity and a single formatted score line.Source: §J.3 · p. 19, §J.4 · p. 19

J.5 KQA Question Sampling Prompt; J.6 KQA Answering Prompt

• KQA questions must ask for one concrete detail answerable solely from the paragraph, and the generated answer is requested to be very short.The question prompt also requires self-contained wording and a specified question-and-answer format.Source: §J.5 · pp. 19–20, §J.6 · p. 20

J.7 KQA Autorater Prompt

• The KQA autorater judges factual accuracy against context and reference answers, then returns only “yes” or “no” for a factual mistake.The prompt distinguishes single-answer matching from checking multiple valid answers against the context and reference.Source: §J.7 · p. 20

J.8 AutoMQM Prompt

• AutoMQM classifies translation errors by category and severity, including critical, major, and minor levels.The prompt requires error spans, explanations, categories, types, and severity in JSON.Source: §J.8 · pp. 20–21
• The discovered topics are reported as harder than existing benchmark subsets despite shorter average texts, while the hardest topic is comparable to challenging benchmark subsets.Tables 11–13 provide example source texts and translations with major errors.Source: §J.8 · pp. 22–23, Table 11 · p. 24, Table 12 · p. 25