Skip to content

Pushing Test-Time Scaling Limits of Deep Search with Asymmetric Verification

🕒 Published (v1): 2026-01-01 · Source: ICLR · Venue: ICLR 2026 · link

Why this paper was selected

Asymmetric sequential and parallel test-time scaling with verification improves agent accuracy

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

This paper studies test-time compute scaling for deep search (web research) agents along two axes—sequential scaling (longer single trajectories) and parallel scaling (multiple trajectories + aggregation)—and shows that sequential scaling eventually saturates and hurts performance, while a lightweight verifier agent exploiting asymmetric verification achieves the same accuracy gains at 5–6× lower compute cost. Open-source models scaled via this framework ("Heavy" variants) match or exceed proprietary systems like OpenAI Deep Research and o3 on hard benchmarks.

Problem

Existing test-time scaling research focuses on reasoning tasks with self-contained, easily checkable answers. Deep search agents navigating real-world web environments face a harder exploitation problem: parallel sampling broadens candidate coverage (high Pass@K) but majority voting fails to identify which candidate is correct (low Maj@K). Sequential scaling via budget forcing eventually degrades performance due to the challenge of coherent long-range reasoning in extended trajectories. There is no principled, compute-efficient framework for scaling these agentic search systems.

Method

The framework is a ReAct-based search agent with a web search+browsing tool. Test-time compute is scaled along three orthogonal dimensions:

  1. Scaling target: search agent (exploration) vs. verifier agent (exploitation).
  2. Scaling strategy: Max # Tool Call (system-prompt quota), Budget Forcing (force additional tool calls after premature termination), or Parallel Sampling (K independent trajectories).
  3. Aggregation metric: Pass@K, Maj@K (majority vote), Weighted Voting (confidence-weighted), or Best-of-K (highest verifier score).

The verifier agent reuses the same model and search tool as the search agent, differing only in the system prompt: it is instructed to search specifically to verify a candidate answer and output a confidence score. Multiple verification trajectories can be run per candidate; the final score is averaged across them. The key insight is asymmetric verification: on BrowseComp, GLM-4.5 requires ~75 tool calls to find an answer but only ~18 to verify one—a 4× asymmetry that grows with task difficulty.

To build "Heavy" variants, the best configuration is selected per model by jointly optimizing across all three dimensions given a compute budget.

Key Contributions

  • Empirical characterization of sequential vs. parallel scaling behavior in agentic web search, showing budget forcing improves but saturates, and that the Pass@K–Maj@K gap identifies an exploitation bottleneck.
  • Quantification of asymmetric verification in deep search: verification requires \(\sim\)4× fewer tool calls than generation across multiple models and benchmarks.
  • A verifier framework that reuses the search agent with a prompt swap, achieving the same 10-point accuracy gain on BrowseComp with ~100 tool calls versus ~500 for search-only scaling.
  • Demonstration that verifier compute itself scales (via budget forcing and parallel sampling), and that the optimal scaling strategy is model-dependent.
  • Open-source "Heavy" variants (GLM-4.5-Heavy, K2-Heavy, Qwen3-2507-Heavy, Tongyi-DeepResearch-Heavy) that match OpenAI Deep Research and o3 across BrowseComp, GAIA, and xbench-DeepSearch.

Results

  • GLM-4.5 Heavy: 54.0% BrowseComp, 66.0% GAIA, 68.0% xbench-DeepSearch (vs. 19% Pass@1 baseline).
  • Tongyi-DeepResearch Heavy: 69.0% BrowseComp—highest reported among open-source systems.
  • GLM-4.5 Heavy vs. proprietary: on par with OpenAI Deep Research and o3; GLM-4.5-Heavy BrowseComp-zh: 49.0%.
  • Verifier efficiency: raising GLM-4.5 from 35.7% (Maj@8) to 45% (Weighted Voting) costs ~100 extra tool calls; achieving the same gain through search-only scaling (Maj@32) costs ~560 additional tool calls—a 5.6× efficiency advantage.
  • K2 verifier: Best-of-8 Weighted Voting reaches 18% from Maj@8 baseline of ~10% with only ~77 extra tool calls, vs. ~370 calls for Maj@32.
  • Sequential scaling saturation: GLM-4.5 Pass@1 rises from 19% → 27% after one budget forcing round, then plateaus; excessive budget forcing degrades performance.
  • Parallel scaling ceiling: GLM-4.5 Pass@32 = 67% but Maj@32 ≈ 40.8%, illustrating the exploration–exploitation gap.

Limitations

  • Experiments use a 100-question random sample of BrowseComp (full set ~1200) to reduce compute cost; sample variance is not characterized.
  • The auxiliary browsing model (K2) is held fixed throughout; its quality likely bounds search tool performance in ways not fully ablated.
  • Verifier relies on the same model family as the searcher; independent, specialized verifiers are not studied.
  • Optimal scaling configuration is model-dependent and must be tuned empirically, limiting plug-and-play deployment.
  • All evaluation is on English and Chinese web-search benchmarks; generalization to other languages or closed-domain corpora is not established.
  • Compute efficiency is measured in tool calls, not wall-clock time or API cost; practical latency of "Heavy" variants is not analyzed.

Relevance to Agentic AI / LLM Agents

This paper directly addresses the core challenge of test-time compute allocation for long-horizon web agents, a setting where existing reasoning-focused scaling work (chain-of-thought length, MCTS over token sequences) does not cleanly apply. The asymmetric verification framework is a generalizable design pattern: any agentic task where backward-checking is cheaper than forward-search (e.g., tool-use validation, code execution verification, database query checking) can exploit this compute redistribution. The "Heavy" variant construction methodology—joint optimization of scaling target, strategy, and aggregation metric—provides a replicable blueprint for elevating open-source agents to frontier performance without architectural changes, which is directly actionable for practitioners building research or information-retrieval agents.