PaperlayerView exact revision on arXiv

Source-linked AI summary

Ko-WideSearch: A Korean Breadth-Search Benchmark for Exhaustive Set Enumeration by Web Agents

Minbyul Jeong

arXiv:2606.27595v1cs.CL

TL;DR

Breadth-search benchmarks rarely evaluate exhaustive set enumeration with complete per-item attributes, especially in Korean. Ko-WideSearch addresses this gap with an automated benchmark, finding that agents recover membership but not full rows, with performance declining as task structure hardens.

  • Problem

    Breadth-search evaluation barely exists outside English, while verifying complete sets and correct attribute cells is costly.

  • Method

    Ko-WideSearch is a Korean benchmark of breadth-search tables built by automated synthesis and verification across independently varied table width and 2-D composite keys.

  • Results

    Agents recover membership but not complete rows: GPT-5.5 scores Item-F1 92.8 versus Row-F1 53.7, while Row-F1 declines as width and composite-key difficulty increase.

  • Takeaways & Limitations

    The benchmark identifies row completion, rather than set recovery, as the central breadth-search performance bottleneck.

  • Takeaways & Limitations

    The HARD 2-D tier is sports-season heavy, and non-sports 2-D coverage such as elections remains partial.

Abstract

from arXiv · show

Web-agent benchmarks overwhelmingly measure depth -- pinning one obscure answer behind a chain of constraints -- while breadth, exhaustively enumerating a closed set and filling each item's attributes, is barely evaluated, especially outside English. Breadth is also hard to build: certifying that a gold set is complete and every cell correct is far costlier than checking a single answer. I introduce \textsc{Ko-WideSearch}, a Korean breadth-search benchmark built by an automated synthesize-and-verify pipeline. Each task names a set-parent entity -- a TV season, a dynasty, a league, an administrative region, an election -- and asks for its full membership plus a per-item attribute table, graded by Item-, Column-, and Row-F1. It spans 228 tables over 190 entities and sixteen categories across three difficulty tiers, set by two structural knobs I dial independently -- table width and a 2-D composite key -- so cross-product membership climbs from 0\% to 100\% across the tiers. A single normalization-aware comparator is shared between gold construction and grading, so stable date and count columns are not over-dropped on formatting alone. Across twenty web agents, the failure is consistent: agents recover the set but not the rows (e.g.\ Item-F1 92.8 against Row-F1 53.7), accuracy falls steadily as the knobs harden, and neither more search nor more spend closes the gap. Broken down by cell, the hard part is finding the right value, not formatting it: open-ended free-text cells fail most, while cells with a standard answer such as a date or a name usually come out right.

Introduction

Ko-WideSearch addresses the under-evaluation and construction difficulty of Korean breadth search by testing exhaustive set recovery alongside complete per-item attribute tables. Its benchmark uses automated verification, standardized metrics, and independently controlled difficulty axes to expose failures in filling rows even when agents recover the set.

  • Motivation: Breadth-search tasks require exhaustive set recovery and internally complete attribute tables, unlike depth benchmarks that seek one answer behind multiple constraints.The motivating example requires identifying all nine Korean low-cost carriers and filling attributes whose values may come from different pages.
  • Motivation: Korean breadth evaluation remains scarce, while certifying complete gold sets and correct attribute cells creates an additional benchmark-construction challenge.The paper identifies both the lack of Korean breadth-search evaluation and the cost of verifying completeness and cell correctness.
  • Benchmark: Ko-WideSearch contains 228 tables covering set-parent entities such as TV seasons, dynasties, leagues, regions, and elections, graded by Item-, Column-, and Row-F1.Each task requests full membership plus an attribute table.
  • Verification: An automated synthesize-and-verify pipeline exhaustively searches each gold table and applies independent gates for non-memorization, completeness, and cross-source attribute verification.The benchmark construction pipeline is paired with a comparator shared between grading and verification to avoid formatting-based over-dropping of stable columns.
  • Difficulty Design: 2-D membership rises from 0% in EASY to 100% in HARD, while median table width increases from three to seven columns across the difficulty tiers.The two structural knobs are table width and a 2-D composite key, which independently manufacture harder breadth-search tasks.

Related Work

Prior work centers on depth-oriented web-agent and factuality benchmarks, while breadth-oriented set enumeration has only recently emerged as a distinct challenge. Ko-WideSearch builds on this breadth lineage and Korean evaluation traditions while adapting synthetic-data methods to correctness-constrained benchmark construction.

  • Web agents and browsing: Web-agent research builds on language models that reason, call tools, and read retrieved results, with this paradigm extended to Chinese and Korean contexts.The Korean extension emphasizes local entities, semi-structured Korean pages, and culturally grounded clues.
  • Depth-oriented benchmarks: Depth-oriented QA and browsing benchmarks typically grade a single answer per question, unlike Ko-WideSearch’s set-valued evaluation.The cited lineage includes multi-hop, open-domain, short-answer factuality, and freshness benchmarks.
  • Breadth and set enumeration: WideSearch established set-valued enumeration as a distinct agentic challenge using item-, column-, and row-level F1 metrics.Follow-up work further isolates aggregation and counting error.
  • Korean evaluation: Korean evaluation has developed across reading comprehension, core understanding, multitask knowledge, factual and cultural knowledge, and social bias.Multilingual efforts additionally extend evaluation toward regional coverage.
  • Synthetic data and judging: Ko-WideSearch’s pipeline extends self-generated data methods from training-data synthesis to evaluation-set construction, where correctness rather than diversity is the binding constraint.The passage identifies model-generated gold data as a risk motivating this correctness-focused framing.

The Ko-WideSearch Benchmark

Ko-WideSearch evaluates exhaustive set enumeration by requiring agents to recover a closed membership set and fill per-item attributes, with separate membership, cell, and strict row metrics. Its difficulty is controlled by table width and 2-D composite-key structure, while independent verification and sourcing labels govern benchmark construction and interpretation.

  • Task and metrics: Each instance names a closed finite set and requests attributes for every member, with Item-F1, Column-F1, and Row-F1 measuring membership, cell correctness, and fully correct rows.The gold answer is an n-row table whose first k columns form the membership key; k=2 represents cross-products such as team × season.
  • Construction and verification: Gold tables are built autonomously and certified through non-memorization, completeness, and cross-source attribute-verification gates, with at least one cross-verified attribute column required.A closed-book model must fail to reproduce the cells, an independent agent must agree on membership, and source-fragile columns are dropped.
  • Difficulty design: Width and 2-D composite keys independently create hardness: wider tables require more attributes, while cross-products require exhaustive grid enumeration where one missed combination breaks a band of rows.These knobs shift difficulty from row count toward attribute width and grid structure as tiers harden.
  • Difficulty tiers: HARD uses a median of seven columns and a composite key in 100% of tables, whereas MEDIUM uses either a wide 1-D table or a narrow 2-D grid, with 2-D membership in 30% of tables.EASY turns neither knob; MEDIUM turns exactly one; HARD turns both.
  • Sourcing: Sourcing is orthogonal to difficulty: EXHAUSTIVE-ONLY tables consolidate membership and attributes on one page, while CROSS-SOURCE tables require item-level lookup from another source.Thus even a narrow EASY table can be CROSS-SOURCE.
  • Coverage: The benchmark spans sixteen categories and 190 distinct set-parent entities across 228 tables, with 83% of tasks enumerating a unique set.The 80 sports tasks are nearly all different leagues, seasons, and tournaments.

Experimental Setup

The evaluation tests browsing agents under a fixed single-attempt budget, comparing three model families and measuring exhaustive membership, attribute correctness, table success, and parsing across task conditions.

  • Agent harness: 30 agent iterations and one attempt per task define the browsing-agent evaluation budget.Each iteration may batch several tool calls, so total search calls can exceed thirty; agents must return exactly one structured table.
  • Models: Three model families are evaluated: proprietary frontier, open-weight, and Korean-specialized systems.Examples include GPT, Claude, and Gemini; GLM, Llama, Qwen, and DeepSeek; and EXAONE, HyperCLOVA X, A.X, and Kanana.
  • Metrics: Four WideSearch metrics—Item-F1, Column-F1, Row-F1, and table-success rate—are reported alongside structured-output parse rate.Results are broken down by difficulty tier, sourcing label, and category.
  • Metrics: Item-F1 measures exhaustive membership, whereas Row-F1 and table success additionally require correct attribute cells within rows and across the full table.For the running election grid, membership requires recovering all thirty-four province-round rows without omissions or inventions.

Results

Results show a consistent breadth-search failure: systems recover closed-set membership substantially better than complete attribute rows or whole tables. Performance worsens with wider, composite-key tables, while Korean specialization alone does not close the gap.

  • Membership versus full rows: GPT-5.5 scores Item-F1 92.8 but Row-F1 53.7, with only 19.3 table success, showing that membership recovery substantially exceeds complete-row recovery.The passage describes table success as roughly one entirely correct table in five.
  • Model comparisons: Claude-Opus-4.7 leads membership and per-cell accuracy with Item-F1 94.6 and Column-F1 75.6, while DeepSeek-V4-Pro remains competitive at Row-F1 45.0.DeepSeek-V4-Pro ranks ahead of GPT-5.4, Claude-Sonnet-4.6, and every smaller proprietary tier.
  • Difficulty gradient: Row-F1 falls from EASY to HARD for every model as width and the 2-D composite key increase: GPT-5.4-mini drops from 42.6 to 18.8, and DeepSeek-V4-Pro from 50.7 to 36.9.GPT-5.5 declines more modestly from 58.9 to 48.1, while Item-F1 remains roughly flat and can rise on HARD.
  • Korean-specialized models: A.X-4.0 and Solar-Open-2-preview score Row-F1 24.2 and 24.4, respectively, near Gemma-4-31B at 23.0 and below GPT-5.5 at 53.7.DeepSeek-V4-Pro is the best open-weight model at Row-F1 45.0, indicating that Korean fluency alone does not overcome the benchmark’s core demand.
  • Failure modes: A.X-4.0 reaches Item-F1 71.7 but Row-F1 24.2, whereas Solar-Open-2-preview has Item-F1 44.0 and returns a scorable table only 62.7% of the time.The passage characterizes A.X-4.0’s weakness as cell filling and Solar’s as structured-output failure after extensive searching.

Analysis

Analysis shows that web agents usually recover the closed item set but fail to populate correct rows, especially for open-ended attributes and harder tasks. Larger sets, additional search, and higher spending do not reliably overcome this cell-filling bottleneck.

  • Failure taxonomy: GPT-5.5 recovers the set at precision 85 and recall 86, while whole-row precision and recall fall to 25–37, indicating cell-filling rather than membership failure.DeepSeek-V4-Pro likewise achieves membership precision 71 and recall 71, while parse failures form a separate error mode.
  • Set size and search effort: 35.4 at 8–15 rows, 31.2 at 16–30, and 35.0 beyond 30 show that Row-F1 is essentially flat across gold set size.The analysis instead identifies table width and the 2-D key as the drivers of difficulty, while failures concentrate in harder tiers.
  • Set size and search effort: Qwen3.6 uses 66 tool calls per table for Row-F1 16, whereas GPT-5.5 uses 33 calls for Row-F1 53.7, showing that more search does not buy completeness.Cost also saturates: GPT-5.5 reaches Row-F1 53.7 at about $0.87 per table, while DeepSeek-V4-Pro reaches 45.0 at $0.23.
  • Robustness and evaluation: Row-F1 standard deviations are 0.016 for DeepSeek-V4-Pro, 0.025 for GPT-5.4-mini, and 0.040 for GLM-5.1, making differences above about five points robust.Table success remains the strictest metric, but its 15.9–53.7 Row-F1 comparison is more discriminating than near-floor whole-table success.

Conclusion and Limitations

KO-WIDESEARCH introduces a Korean breadth-search benchmark whose agents recover set membership far more reliably than complete attribute rows. Its coverage remains limited by category skew, primary-page source anchoring, and evaluation under a single harness.

  • Conclusion: GPT-5.5 reaches Item-F1 92.8 against Row-F1 53.7, showing that agents recover membership but not the corresponding rows.The benchmark contains 228 tables across three difficulty tiers and uses an automated synthesize-and-verify pipeline with a shared normalization-aware comparator.
  • Limitations: The benchmark’s HARD, 2-D tier is roughly 67% sports-season tables because compact season tables are the most reliably buildable cross-products.Non-sports 2-D coverage, including elections, remains only partial.
  • Limitations: Each table is anchored to one primary membership-page URL rather than separate sources per attribute, although cross-source verification was applied during construction.This source design is a stated coverage limitation rather than a claim that verification was absent.
  • Limitations: Performance is measured under a single harness, limiting the evaluation setup’s coverage.The passage identifies the single-harness measurement as another limitation of the benchmark’s coverage.

Technical Appendix · Data Schema

Each released task is represented as one JSON record containing metadata, question and schema definitions, row-key information, and a gold answer set. The schema supports difficulty, category, sourcing, temporal, formatting, and grid-structure specifications.

  • Data Schema: Each task is stored as one JSON record with an id and an EASY, MEDIUM, or HARD difficulty tier.
  • Data Schema: The record specifies a category and an orthogonal sourcing label: EXHAUSTIVE ONLY or CROSS SOURCE.
  • Data Schema: Volatile tables include an as-of date, while nonvolatile tables use null for that field.
  • Data Schema: Each record contains the natural-language question and ordered columns with per-column format specifications.Supported formats include name, int, float:N, date:YYYY-MM-DD, and enum:A|B.
  • Data Schema: Key columns jointly identify each row, using one column for a primary key or two columns for a 2-D grid.
  • Data Schema: The record includes a gold answer set for evaluating the requested table contents.

Construction and Verification Details

Gold tables are constructed and verified by frontier models using live Korean web search, with independent gates for non-memorizability, completeness, and cross-source verification. Semantic judging can raise measured Row-F1, especially for stronger models, relative to strict cell matching.

  • Gold-table construction: Frontier models GPT-5.4 and DeepSeek-V4-flash build and verify gold tables through live Korean web searches.The searches use the search/open/find namespace.
  • Semantic evaluation: DeepSeek-V4-Pro gains +4.9 judged Row-F1 over strict scoring, versus +0.8 for the weakest model.The correction grows with model strength, so strict cell matching understates the gap between strong and weak systems.
  • Acceptance gates: Three independent acceptance gates test non-memorizability, completeness, and cross-source verification.Non-memorizability fails closed; completeness uses independent re-enumeration; cross-source verification re-looks up entries.
  • Acceptance gates: 0.5 closed-book cell recall rejects a table under the non-memorizability gate.An inconclusive closed-book check also counts as a rejection.
  • Acceptance gates: Set-F1 ≥0.7 is required for completeness, using a different model family from the builder to avoid self-confirming set agreement.Completeness is assessed by independent re-enumeration of membership.

Pipeline Prompts

The pipeline prompts make breadth exhaustive by requiring a closed, finite set and a wide multi-source attribute table, then verify non-memorization, completeness, and cross-source cell accuracy. Evaluation standardizes Korean web-agent instructions and JSON output, while sourcing labels are calibrated against list-page coverage with roughly 72% structural accuracy.

  • Build agent: The builder targets 8–40 entities in an officially bounded set and requires exhaustive search rather than a single-answer lookup.The primary key is each item’s canonical name, and the predicate must define a finite set with an authoritative complete list.
  • Build agent: The builder requires 4–7 heterogeneous attribute columns sourced from different pages, with explicit per-cell formats and as-of dates for volatile values.Required column types include dates, numbers, names, and where natural enums, money, locations, or URLs.
  • Verification gates: Verification separately tests cell recovery from memory, bidirectional membership completeness, and independent cross-source attribute correctness.The non-memorization gate scores recovered item and attribute cells, while completeness uses independent re-enumeration and set matching.
  • Evaluation harness: The evaluation harness instructs Korean web agents to find every item, use only search-confirmed values, leave unknown cells blank, and end with exactly one JSON block.The JSON attrs keys must match the requested attribute columns.
  • Sourcing-tier labeling: Roughly 72% structural accuracy was achieved when a web-grounded calibrator checked whether the best list page contained every requested column.A classifier labels tables EXHAUSTIVE-ONLY or CROSS-SOURCE from the question, defaulting to CROSS-SOURCE when uncertain, before calibration overwrites the guess.

Scoring Details … Qualitative Case Studies

Ko-WideSearch scores exhaustive set enumeration by separating membership, attribute, and complete-row correctness, then exposes systematic breadth-search failures across task tiers and model case studies. The benchmark’s examples show that agents often recover the set boundary while leaving attributes blank, fabricating values, or failing to emit a scorable table.

  • Scoring Details: The scorer parses JSON, Markdown, or CSV rows, matches them one-to-one on primary or 2-D keys, and applies one shared type-aware comparator to every non-sentinel cell.This prevents repeated keys from inflating precision, recall, or F1 and keeps parsing, matching, and cell comparison deterministic.
  • Scoring Details: Item-F1 measures membership, Column-F1 measures attribute agreement, and Row-F1 requires the key plus every attribute cell; table success requires Row-F1 = 1.The metrics distinguish recovering the correct set from completing every row correctly.
  • Sample Tasks: Representative samples span EASY, MEDIUM, and HARD tasks, from eight planets with discovery attributes to 34 election rows formed by a province-by-round 2-D key.The hard metropolitan-election example has 17 provinces and two election rounds, with seven columns including free-text and numeric-tolerance fields.
  • Reproducibility, License, and AI Assistance: The benchmark, construction pipeline, and scorer are released under MIT, while the items are labeled pipeline-verified because language-model synthesis and automated gates were followed by native-speaker spot checks.The license covers benchmark items and code, not linked web content.
  • Additional Results: 0.44, 0.30, and 0.23 are Row-F1 for EASY, MEDIUM, and HARD, respectively, while scorable-table trajectories fall from 90% on EASY to about 85% on MEDIUM and HARD.Harder tiers increasingly defeat agents’ ability to emit wide 2-D tables, not merely to fill them correctly.
  • Qualitative Case Studies: Case studies show blank attributes, under-recall, fabricated values, and parse failures: A.X-4.0 recovers all planets but leaves only one row correct, while Solar-Open-2-preview often emits prose or wrong numbers.These examples instantiate the broader pattern of recovering members but failing to complete rows.
  • Qualitative Case Studies: GPT-5.5 achieves Item-F1 100 but Row-F1 42 in one case, recovering the set while breaking seven of twelve rows through enum, address, and boundary errors.Its membership boundary remains strong, with precision 75 from four invented trims and recall 94 from one dropped member.
Loading 2606.27595v1…