PaperlayerView exact revision on arXiv

Source-linked AI summary

SearchOS-V1: Towards Robust Open-Domain Information-Seeking Agent Collaboration

Yuyao Zhang, Junjie Gao, Zhengxian Wu, Jiaming Fan, Jin Zhang, Shihan Ma, Yao Yao, Weiran Qi, Chuyan Jin, Guiyu Ma, Xingzhong Xu, Kai Yang, Ji-Rong Wen, Zhicheng Dou

arXiv:2607.15257v1cs.AIcs.IR

TL;DR

Long-horizon search agents struggle to maintain progress, evidence, and failures across growing interactions. SearchOS externalizes this state and coordinates multi-agent search, leading all reported F1 metrics on WideSearch and GISA.

  • Problem

    Long-horizon search agents struggle to track unresolved work, preserve evidence, and avoid redundant or stalled searches as interaction histories grow.

  • Method

    SearchOS models information seeking as cited relational schema completion and externalizes search state through SOCM, pipeline orchestration, middleware control, and reusable skills.

  • Results

    80.3 item-level F1 on WideSearch and 76.5 set F1 on GISA, with SearchOS leading all reported F1 metrics among evaluated baselines.

  • Takeaways & Limitations

    Explicit search state, grounded evidence, and system-level execution control provide a practical foundation for reliable multi-agent information seeking.

  • Takeaways & Limitations

    SearchOS-V1 focuses on externalizing search state and infrastructure, leaving large-scale search-agent skill synthesis for follow-up work.

Abstract

from arXiv · show

Recent advances in Tool-Integrated Large Language Models have made web search a core capability of information-seeking agents. However, as interaction histories grow, agents increasingly struggle to track task progress. When search attempts fail to yield useful evidence, current single- and multi-agent systems can become trapped in repetitive loops, wasting search budgets and ultimately compromising the quality and completeness of the final output. We introduce SearchOS, a system-level multi-agent framework that turns fragile, implicit search progress into explicit, persistent, and shared state. First, we formulate open-domain information seeking as relational schema completion with grounded citations, where agents discover entities, populate attributes across linked tables, and anchor each value to source evidence. Then we design Search-Oriented Context Management (SOCM), which externalizes the evolving state into Frontier Task, an Evidence Graph, a Coverage Map, and Failure Memory. Built on SOCM, SearchOS applies a pipeline-parallel scheduling mechanism that overlaps the execution of sub-agents and continuously refills freed slots with tasks targeting unresolved coverage gaps to improve utilization and throughput. To schedule and control the execution of search agents, SearchOS introduces a Search Tool Middleware Harness that intercepts model and tool interactions to record grounded evidence and react to stalls or budget exhaustion, and provides a reusable hierarchical skill system comprising strategy and access skills to augment the agents' search process and avoid repeating failed search patterns across runs. On WideSearch and GISA, SearchOS leads all metrics among the evaluated single- and multi-agent baselines, paving the way toward robust information-seeking collaboration.

1 Introduction

SearchOS addresses unreliable long-horizon information seeking by making search progress, evidence, coverage gaps, and failures explicit and shared across agents. It combines relational schema completion, stateful pipeline-parallel collaboration, middleware controls, and hierarchical skills, achieving leading reported F1 results on WideSearch and GISA.

  • Motivation: Growing interaction histories bury evidence and progress, causing omissions, redundant collection, conflicting claims, and repeated searches that waste budgets.These failures can degrade the final answer when agents continue exploring unproductive search paths.
  • Relational Search Formulation: SearchOS formulates open-domain information seeking as relational schema completion with grounded citations for entity discovery, attribute completion, and evidence attribution.Relational schemas may contain multiple tables connected through primary–foreign-key relations.
  • Stateful, Pipeline-Parallel Collaboration: SOCM shares Frontier Task, an Evidence Graph, a Coverage Map, and Failure Memory while pipeline-parallel scheduling assigns freed agent slots to unresolved schema gaps.A central orchestrator coordinates specialized explore, search, and writer agents across concurrently progressing subtasks.
  • Middleware-Governed Search Agent Execution: The Search Tool Middleware Harness injects state, anchors evidence, enforces budgets, and detects repeated or stalled trajectories outside agent prompts.SearchOS also provides reusable search strategies and site-specific access procedures through a hierarchical skill system across sessions.
  • Results: 80.3 item-level F1 on WideSearch and 76.5 set F1 on GISA are reported for SearchOS, which leads all reported F1 metrics among evaluated baselines.On GISA, SearchOS exceeds the strongest baseline by 13.4 points.

2 Problem Formulation

Open-domain information seeking is formulated as relational schema completion with grounded citations. Given a natural-language request, the system defines linked tables, discovers entities, populates attributes, and produces a verifiable report with fine-grained inline citations.

  • Relational schema: The task represents a natural-language request q as a relational search schema T = (q, S) with tables, attributes, primary keys, and foreign-key relations.Primary keys identify entities, foreign keys express cross-table relations, and normalized tables reduce redundant or inconsistent fact representations.
  • Schema completion: For each table, the system discovers entities Em = {em,i}Nm and populates a value matrix Ym ∈VNm×|Am|.The schema provides an explicit target for search by organizing entities and attribute values across linked tables.
  • Grounded citations: Every populated value must link through citation matrix Cm to a source URL and anchored excerpt, making factual values independently verifiable.Citation entries have the same shape as the value matrix and ground each populated value in source evidence.
  • Final synthesis: The completed schema is synthesized into a natural-language report with fine-grained inline citations.Grounded citations support verification of individual factual values in the final report.

3 SearchOS

SearchOS externalizes long-horizon search progress into durable shared state and coordinates role-specialized agents through dependency-aware, continuously refilled execution. Its middleware grounds evidence, detects failures and resource problems, while reusable skills support search across operational levels.

  • Search-Oriented Context Management: SOCM externalizes unresolved gaps, grounded evidence, coverage, and failed attempts into durable shared state outside agent conversations.The state comprises Frontier Task, Evidence Graph, Coverage Map, and Failure Memory, with locked read–modify–write updates.
  • Search-Oriented Context Management: Frontier Task turns schema gaps into dependency-aware work, while target-cell deduplication, revalidation, and cancellation guards prevent redundant or invalid execution.Tasks become ready after dependencies terminate; dispatch-time checks close tasks whose cells are already filled.
  • Search-Oriented Context Management: The Evidence Graph stores atomic findings with source spans, schema bindings, confidence, provenance, and audit-preserving statuses, while Coverage Map tracks cell states and conflicts.Rejected or superseded evidence remains auditable but does not count toward coverage; disagreement marks a conflict rather than overwriting evidence.
  • Agent Roles and Scheduling: SearchOS separates orchestration, exploration, grounded search, and writing, then uses event-driven pipeline dispatch to refill released slots and avoid batch stragglers.After each completion, SOCM is updated and the ready set is recomputed, allowing roles to overlap when dependencies permit.
  • Search Tool Middleware Harness: The Search Tool Middleware Harness intercepts model and tool boundaries to preserve role-specific context, commit grounded evidence, and sensor-check progress, failures, and resource use.It addresses model-level state loss and safeguard failures alongside tool errors, malformed outputs, stalled loops, and budget overruns.
  • Hierarchical Skills: SearchOS-V1 provides 280 pre-built skills organized into orchestrator, strategy, and access levels for coordination, task methods, and source-specific retrieval.The stated scope emphasizes externalized search state and intermediate artifacts; large-scale skill synthesis is deferred to future work.

4 Experiments

SearchOS is evaluated on WideSearch and GISA using structured table metrics against single- and multi-agent baselines. It achieves the best overall performance, leading all six headline F1 metrics across both benchmarks while remaining competitive on precision-oriented metrics.

  • Benchmarks: WideSearch contains 200 questions across English and Chinese, spanning more than 15 domains and requiring large-scale collection of verifiable facts into complete tables.The benchmark is drawn from real user queries and emphasizes broad information collection.
  • Benchmarks: GISA contains 373 human-crafted queries with item, set, list, and table answer formats, combining deep multi-hop reasoning with broad cross-source aggregation.Its structured formats enable deterministic scoring.
  • Main results: SearchOS achieves the best overall performance on both benchmarks, leading all six headline F1 metrics while remaining competitive on precision-oriented metrics.Baselines include ReAct, Plan-and-Solve, A-MapReduce, Web2BigTable, and Table-as-Search.
  • WideSearch results: On WideSearch, SearchOS reaches Item-level Precision 83.9, Recall 79.7, and F1 80.3, exceeding A-MapReduce’s 76.0 F1 by +4.3 points.It also leads Row-level Precision 59.0, Recall 55.8, and F1 56.5, improving over Web2BigTable by +2.0.
  • GISA results: On GISA, SearchOS leads every question type, with Set F1 76.5 versus 63.1 for the best baseline, a +13.4-point improvement.It also tops Table Item F1 76.9, Table Row F1 59.7, and List F1 68.1, while matching the best Item-level EM 50.0.

5 Ablations & Analysis

The ablations show that SearchOS benefits from adaptive schema planning, continuous scheduling, middleware governance, and hierarchical skills. These components improve structural fit, utilization, search recovery, quality, and efficiency across the evaluated settings.

  • Schema planning: Adaptive schema planning outperforms fixed structures: an oracle choosing the better fixed schema still trails SearchOS by 8.2 Item F1 and 7.7 Row F1 points.Fixed multi-table wins only 21 of 40 cases by Item F1, while SearchOS selects single-table schemas for 35 tasks and multi-table schemas for five.
  • Pipeline scheduling: Continuous scheduling reduces average end-to-end time by 24.3% while improving slot utilization, throughput, and Item F1 with fewer LLM calls.It immediately refills released slots instead of waiting for synchronized task batches to finish.
  • Middleware governance: Early, middle, and late Loop Sensor interventions all restore search progress after stagnation, though their effects on coverage and entity discovery differ.The middleware triggers a strategy switch when it detects a low-progress search loop.
  • Hierarchical skills: Hierarchical skills raise Item F1 by 2.0 points and Row F1 by 3.4 points, indicating stronger coherent entity-record assembly.The larger row-level gain is attributed to reusable decomposition, search, and source-access knowledge.
  • Hierarchical skills: Hierarchical skills reduce session time by 36.6%, search calls by 39.1%, and page calls by 42.7% without adding exploratory browsing.This joint ablation disables all skill layers together and uses the same 100 WideSearch questions.

6 Related Work

Related work advances tool-integrated agents through improved search policies, decomposition, synthetic data, structured completion, multi-agent execution, context management, and agent-harness infrastructure. SearchOS positions relational completion, SOCM, and harness mechanisms as a unified response to limitations involving dependencies, provenance, failed attempts, and persistent search state.

  • Tool-integrated language agents combine search, browsing, reasoning, evidence collection, and synthesis, with progress from policy optimization, task decomposition, and synthetic interaction data.
  • Structured information-seeking completion exposes missing entities and attributes for parallel collection but omits dependencies, conflicting observations, provenance, and failed attempts.SearchOS formulates the task as relational schema completion with grounded citations.
  • Multi-agent frameworks use specialized roles, message exchange, structured workflows, hierarchical planning, and concurrent execution of independent branches.
  • Agent memory and context-management methods use reflection, memory stores, virtual context, compression, or trajectory consolidation; SOCM externalizes search state into four shared structures.These structures are Frontier Task, Evidence Graph, Coverage Map, and Failure Memory, with role-specific projections.
  • Agent-harness research treats infrastructure as governing execution, tools, context, state, lifecycle, observability, and evaluation, while engineering reports stress inspectability, feedback loops, and context curation.

7 Conclusion · A SOCM State Example · B Executable Access Skill Case

SearchOS externalizes long-horizon open-domain search into shared system-maintained state, combining grounded relational schema completion with SOCM and pipeline-parallel execution control. The appendices illustrate this state through task, coverage, and evidence tracking, and show how executable access skills provide typed, normalized source-specific retrieval.

  • 7 Conclusion: SearchOS externalizes long-horizon open-domain search as system-maintained state for relational schema completion with grounded citations.SOCM organizes coverage gaps, evidence, and intermediate search artifacts.
  • 7 Conclusion: Pipeline-parallel orchestration dispatches unresolved coverage gaps, while the Search Tool Middleware Harness prepares context, grounds observations, and handles stalls.
  • 7 Conclusion: SearchOS improves both completeness and efficiency on WideSearch and GISA, supporting explicit search state, grounded evidence, and system-level execution control.The authors identify these mechanisms as a practical foundation for reliable multi-agent information seeking.
  • A SOCM State Example: The SOCM snapshot shows concurrent task states: T-008 is RUNNING, T-009 is PENDING, and final-report task T-010 is BLOCKED by T-008.
  • A SOCM State Example: The evidence summary records 24 total nodes, 21 active nodes, 2 conflicts, and an unresolved Company X revenue discrepancy between source A’s $1.2B and source B’s $1.4B.
  • B Executable Access Skill Case: An executable access skill aligns skill.md guidance, manifest.yaml’s typed parameter schema, and executor.py’s dispatch, retrieval, parsing, and normalization.The abridged case uses Senate.gov access operations.
  • B Executable Access Skill Case: The Senate.gov manifest exposes get_senators_by_state, list_all_states, and get_state_history, with state_code defined as an optional string parameter.A typed invocation selects get_senators_by_state with state_code set to OK.
  • B Executable Access Skill Case: The executor hides URL construction, HTTP errors, and BeautifulSoup parsing, returning stable structured Senate records with state metadata, senator fields, and senator_count.The normalized example reports Oklahoma and senator_count: 2.

C Implementation Reference · C.1 Simple Browser · C.2 Schema and Entity Management Tools

The appendix documents implementation interfaces for the Simple Browser and the orchestrator’s schema, task-queue, and writer tools. The browser uses stack-based state to preserve navigation context, while schema tools provide CRUD operations over the Coverage Map.

  • C Implementation Reference: The implementation reference records Simple Browser operations and orchestrator tools for schema, task-queue, and writing, rather than defining the core method.These interfaces are included for reproducibility.
  • C.1 Simple Browser: Browser state is B = (P, H, σ), comprising a URL-to-content page cache, a LIFO navigation stack, and a scroll cursor.Search, fetch, and find operations push newly produced pages onto H.
  • C.1 Simple Browser: The browser resolves open(3) by searching backward through the stack for the most recent page containing link ID 3.This makes numeric link references unambiguous within navigation history.
  • C.1 Simple Browser: The navigation stack preserves the full path, supporting implicit back-navigation and further trajectory analysis.This is an advantage over a flat URL-based model.
  • C.1 Simple Browser: Cross-page find keeps matches tied to the source page and lets open(match_id) jump automatically to the matched line.This enables in-page exploration without losing context.
  • C.1 Simple Browser: The Simple Browser exposes three browser operations summarized in Table 7, with open() and find() outputs illustrated in Figure 7.open() renders line-numbered markdown with bracket-style links, while find() returns numbered contextual matches.
  • C.2 Schema and Entity Management Tools: The orchestrator manages relational search schema S through CRUD tools operating on the Coverage Map.The complete schema and entity management tool set is listed in Table 8 and is orchestrator-only.

C.3 Task Queue and Agent Coordination Tools · C.4 Writer Tools · D Agent Trajectory Case Studies

The orchestrator coordinates Frontier Memory and sub-agent lifecycles through dedicated task-queue tools, while the writer uses structured, evidence-grounded outline tools. Trajectory case studies then illustrate consequential search behaviors through logged decisions, actions, and state transitions.

  • C.3 Task Queue and Agent Coordination Tools: The orchestrator manages Frontier Memory and sub-agent lifecycles through dedicated task-queue and coordination tools.These orchestrator-only tools are listed in Table 9.
  • C.3 Task Queue and Agent Coordination Tools: Table 9 catalogs task-queue and agent-coordination tools available exclusively to the orchestrator.
  • C.4 Writer Tools: The writer agent operates on a structured outline rather than free-form text to maintain consistent organization and complete citation coverage.Writer-specific outline and section-management tools are listed in Table 10.
  • C.4 Writer Tools: The writer can read the full SOCM state and skill catalog, grounding its writing in the latest evidence.
  • D Agent Trajectory Case Studies: The trajectory case studies summarize logged decision rationale, tool actions, and observable state transitions at consequential steps.They use complete WideSearch trajectories without reproducing unabridged token-level reasoning.
  • D Agent Trajectory Case Studies: The cases illustrate parallel enrichment, scope auditing, and recovery from inaccessible sources rather than providing aggregate evidence.

D.1 Detailed Case: Spotify 2024 Rankings

The Spotify 2024 case completed global and U.S. top-ten song rankings with enriched metadata, achieving full known-cell coverage and strong item- and row-level F1. SOCM tracked shrinking uncertainty to zero gaps while preserving category-specific identities and triggering an exhaustiveness audit before termination.

  • Task and outcome: The run finished in 362 seconds with 221 evidence nodes, 100% known-cell coverage, 97.5 Item F1, and 85.0 Row F1.The task requested global and U.S. top-ten songs enriched with artist, language, songwriter, producer, and release date.
  • Decision trace: The workflow established two authoritative ranked lists before metadata enrichment, enabling sub-agents to write into stable composite keys instead of rediscovering row identities.This design choice was reconstructed from the stored trajectory.
  • SOCM evolution: SOCM reduced missing or uncertain columns from all 20 seeded rows early in the run to six mid-run and zero final gaps.The final snapshot still warned that filled known rows did not prove the requested row set was exhaustive.
  • SOCM evolution: The exhaustiveness warning triggered a Stage-5 row-set audit rather than immediate termination after all known rows were filled.This separated completion of known cells from verification that the requested row set was complete.
  • Output excerpt: The composite key preserved category-specific rank when a song appeared in both charts, while shared metadata remained independently grounded.This prevented chart identity from being lost during enrichment.

D.2 Additional Process Cases … E.3 Case 3: GPU Cloud Provider Comparison

The process cases show how SearchOS detects incomplete scope, resolves conflicting identities, and recovers from blocked sources while preserving evidence and bounded search. Together, they illustrate a control loop in which shared structured state exposes residual gaps and redirects or stops work based on observable progress.

  • D.2 Additional Process Cases: In the Phelps case, 100% coverage over 16 known rows is rejected as completion because agents imply roughly 31 eligible events.The orchestrator audits row scope and dispatches Olympic and World-Aquatics backfill agents.
  • D.2 Additional Process Cases: The orchestrator verifies a duplicate 2003 400m individual-medley identity against championship sources and removes the incorrect row.The two conflicting times are 4:09.09 and 4:11.04; the case outcome reports 35.
  • D.2 Additional Process Cases: In the journal case, blocked Wiley and JSTOR pages trigger pivots to Crossref, OpenAlex, and other sources after repeated access failures.The workflow also removes an out-of-scope 2026 article and dispatches targeted metadata tasks for five incomplete rows.
  • D.2 Additional Process Cases: The cross-case control loop explores before committing to row identities, accumulates evidence in shared structured state, exposes residual gaps, and redirects or stops work.In the Spotify case, an authoritative list establishes the complete key space before metadata agents launch.
  • D.2 Additional Process Cases: The Phelps case separates cell saturation from scope completion: coverage controls attribute filling, while an explicit row-set audit controls recall.This prevents apparent saturation from masking missing rows.
  • D.2 Additional Process Cases: Recovery remains bounded and evidence preserving: repeated failures prompt source or tool changes, while resource limits stop unproductive search.Unresolved cells remain visible rather than being filled through unsupported inference.
  • E SearchOS Case Walkthroughs: The case walkthrough interface snapshots are ordered by case number and then by step number, with two snapshots in each row.The supplied passage introduces the walkthrough layout but provides no case-specific findings for the named E.1–E.3 sections.
Loading 2607.15257v1…