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

SearchOS externalizes search state into a relational schema to prevent agent loops and redundant work.

How can we prevent information-seeking agents from losing track of task progress and state during long-horizon web searches?

Long-horizon information-seeking agents often lose track of progress, leading to repetitive search loops, redundant data collection, and wasted compute budgets as interaction histories grow. SearchOS addresses this by externalizing the search state into a persistent, shared relational schema—complete with an evidence graph and coverage map—that exists outside the agent's conversation history. On the WideSearch and GISA benchmarks, this framework outperforms existing single- and multi-agent systems, achieving a 13.4-point F1 gain on set-based queries.

Paper Primer

SearchOS treats information seeking as a relational database problem: it decomposes requests into tables, attributes, and primary keys. By forcing agents to populate this schema with grounded citations, the system makes progress measurable and verifiable at the cell level.

The core mechanism is Search-Oriented Context Management (SOCM), which acts as a shared memory layer. It uses pipeline-parallel scheduling to keep agents busy: as soon as one sub-task finishes, the orchestrator assigns a new unresolved schema gap to the freed slot, preventing the idle time common in batch-based multi-agent systems.

SearchOS significantly improves completeness and recall in complex, multi-hop search tasks.

On the GISA benchmark, SearchOS achieved 76.5 F1 on set-based queries, outperforming the strongest baseline by 13.4 points.

Continuous pipeline-parallel scheduling increases throughput and reduces redundant compute.

Compared to batch-based scheduling, continuous dispatch reduced end-to-end session time by 24.3% and decreased the number of required LLM calls.

Why does the system need a "Middleware Harness" if the agents are already instructed to search?

Prompt-level instructions often fail as context grows or agents encounter tool errors. The middleware intercepts interactions at the system level to enforce budget limits, detect stalled loops, and ensure evidence is properly anchored to the schema, regardless of the agent's internal state.

Is the relational schema fixed at the start of the search?

No. SearchOS uses an explore agent to dynamically plan and revise the schema based on the information topology discovered during the search, allowing it to switch between single-table and multi-table structures as needed.

The system's reliance on a pre-defined relational schema assumes that the information-seeking task can be decomposed into structured entities and attributes; it may be less effective for purely exploratory or open-ended creative synthesis tasks where the output structure is not known in advance.

For researchers building agentic systems, this paper demonstrates that moving state out of the LLM's context window and into a system-managed, relational structure is a viable path to solving the "repetitive loop" problem in long-horizon search.

Introduction: The State Tracking Problem

Agents lose progress tracking in long‑horizon searches, motivating a relational, stateful framework.

Current long‑horizon agents treat search progress as a fleeting conversation thread. As the dialogue grows, they forget which facts have already been gathered and which gaps remain, causing repeated queries and wasted compute.

SearchOS replaces the linear, memory‑less view of a search episode with a relational table that is filled incrementally, making progress observable and verifiable.

**Figure 1.** SearchOS interface for a long-horizon information-seeking task. The workspace exposes the orchestration trace, pipeline parallel agent activity, and relational schema coverage.

The key insight is to replace a linear history of queries with an explicit relational state that tracks coverage and evidence.

Relational Schema Completion

We externalize search state as relational schema completion with a durable context manager.

Long‑horizon search agents collapse under a linear view of information gathering; without an explicit representation of what remains unknown, they repeatedly chase dead ends.

We treat the search problem as filling a set of normalized tables, each identified by primary keys and linked by foreign keys, so that every fact we discover has a precise place in a relational structure.

Agent discovers entity Place = “Paris” and inserts a row into $T_1$ → $Y_1$ entry (Paris, France) with citation to a Wikipedia page.

Next, it finds Landmark = “Eiffel Tower”, links it to Place = Paris, and adds row (Eiffel Tower, Paris) to $T_2$ with a news‑article citation.

Because $T_2$’s foreign key points to $T_1$, the system can later query “all landmarks in France” by joining the two tables.

This toy illustrates how every discovered fact is anchored both structurally (via keys) and evidentially (via $C_m$), eliminating ambiguous or unsupported statements.

How does Relational Schema Completion differ from ordinary table‑completion in databases?

Standard table completion fills missing cells using statistical patterns, but here each cell must be backed by a concrete source URL and excerpt; the schema is built on‑the‑fly from a natural‑language query rather than being pre‑defined.

Even with a clean schema, agents still need a shared, mutable view of what remains to be done; that is the role of Search‑Oriented Context Management (SOCM).

SOCM externalizes the evolving search state into a durable four‑part memory that agents read from and write to via atomic projections, keeping everyone synchronized without leaking stale context.

Why not give every agent the full $M_t$ instead of a projection?

Full $M_t$ quickly exceeds model context windows and mixes unrelated signals; projections keep prompts short, prevent stale reads, and enforce the principle‑of‑least‑privilege for each role.

All four memories are updated through the same locked interface, guaranteeing that agents never observe a mixture of old and new evidence, task status, or failure guidance.

Orchestrator-Worker Architecture

Orchestrator‑worker pipelines keep agents busy and data flowing without idle batches.

The system must keep multiple agents productive while respecting their data dependencies, so a naïve batch‑synchronous schedule would waste compute.

The orchestrator holds the global schema and decides which gaps need attention; workers (explore, search, writer) execute focused actions on those gaps.

E receives G₁, discovers two candidate sources C₁ and C₂, and reports them to the orchestrator.

The orchestrator selects C₂ (higher priority) and creates a new gap G₂ for concrete evidence.

S picks up G₂, fetches the required page, extracts the needed fact, and returns it.

The orchestrator marks G₁ as filled, updates the schema, and the pipeline proceeds to the next gap.

The orchestrator never performs raw retrieval itself; it merely routes work, keeping the system modular and allowing each worker to specialize.

How does this differ from classic pipeline parallelism that simply splits a model across devices?

Classic pipeline parallelism partitions a single computation graph into stages; here the pipeline partitions *different agents* with distinct responsibilities, and the orchestrator dynamically schedules work based on data dependencies rather than a static layer order.

To keep agents from idling, the system applies pipeline parallelism at the role level, dispatching work as soon as execution slots become free.

After a worker finishes, SOCM is updated, the frontier recomputed, and any newly released slot is immediately refilled, overlapping roles whenever dependencies allow.

Each agent sees only the tools it needs, preventing interference and reducing the search space.

The table maps various tool groups to four functional categories: Orchestrator, Search, Explore, and Writer. The rows include Simple Browser, Schema & Entity CRUD, Task Queue & Coordination, Outline Management, SOCM Read, and Skill Catalog.

The browser component implements a shared navigation stack with three operations—search, open, and find—each yielding an observation that middleware turns into evidence and provenance.

Middleware Harness

System‑level middleware intercepts the search loop to enforce safety and progress.

During long‑horizon search the agent can lose track of its task or exhaust resources, and prompt‑only safeguards cannot reliably protect heterogeneous tool calls.

The harness sits between the orchestrator and each tool, injecting context, grounding evidence, and watching for stalls so that safety and progress are enforced outside the language model prompt.

Run Context Middleware to produce role‑specific context $e_h^{(r)}_t$.

Invoke the language model with $e_h^{(r)}_t$ and obtain a tool call.

Execute the tool, receive observation $o_t$, and run Evidence Extraction Middleware to update $M_{t+1}$.

Run Sensor Middleware on $(M_t, M_{t+1}, \xi_t)$ to compute stall flag $s_t$ and budget pressure $\rho_t$, then emit action $a_{t+1}$.

If $a_{t+1}$ signals correction, inject a fix into the next context; if it signals stop, terminate the branch.

Context Middleware projects $M_0$ → $v^{(r)}_0 = \phi_r(M_0) = (\,)$ (empty vector) and retrieves the top‑1 skill “lookup‑capital”, so $K_0 = \{ \text{lookup-capital} \}$.

Compose context $e_h^{(r)}_0 = h_0 \oplus v^{(r)}_0 \oplus \psi(K_0)$, yielding the prompt “Find the capital of France. Use skill: lookup‑capital”.

The model calls the browser tool; observation $o_0$ returns the HTML snippet “

Evidence Extraction extracts candidate $z = (\text{entity}= \text{Paris}, \text{attribute}= \text{capital}, \text{value}= \text{Paris}, \text{source}=$o_0$, \text{span}=

Sensor computes coverage increase $\Delta\text{cov}_0 = 1$, evidence increase $\Delta\text{ev}_0 = 1$, so stall flag $s_0 = 0$; budget pressure $\rho_0 = 0.1$ (well below limits), thus $a_1$ = “continue”.

The example shows how the three middleware modules cooperate: context preparation guides the model, evidence extraction turns raw HTML into a schema‑bound fact, and the sensor confirms forward progress before the next iteration.

How does the Middleware Harness differ from adding safety prompts directly into the language model?

Prompt‑only safeguards are evaluated *before* the model generates output and can be ignored by clever prompting; the harness intervenes *after* each model‑tool interaction, inspecting actual tool results and resource usage, so it cannot be bypassed by prompt engineering.

**Figure 3.** Illustration of middleware interventions in the Search Agent loop.

Empirical Evaluation

SearchOS outperforms baselines on WideSearch and GISA benchmarks.

Recall that SearchOS treats long‑horizon information gathering as relational schema completion, using an orchestrator to manage shared state and workers to perform grounded searches.

SearchOS attains the highest F1 scores on both WideSearch and GISA, improving the strongest baseline by up to +13.4 points.

Table 2 reports the detailed scores across all metrics.

In relational schema completion, SearchOS outperforms fixed and oracle schema settings, gaining up to +8.2 F1 points on item‑level evaluation.

Table 3 presents the schema‑completion analysis.

**Figure 4.** Pre-built skills: (a) weighted keyword frequency; (b) access-skill counts and mean functions by domain.

SearchOS delivers sizable performance gains on long‑horizon information‑seeking tasks.

Ablation Studies

Ablation studies quantify the impact of schema planning, scheduling, middleware, and skills on SearchOS performance.

We first compare a static schema choice against SearchOS’s autonomous schema planning on 40 multi‑table questions.

Even an oracle that picks the better fixed schema for each question trails SearchOS by 8.2 Item F1 and 7.7 Row F1 points.

Table 3 shows the oracle’s aggregate scores versus SearchOS on the 40 cases.

Next we test whether continuous pipeline‑parallel dispatch improves utilization compared with synchronized batch dispatch.

Continuous scheduling reduces average end‑to‑end time by 24.3 % relative to batch scheduling.

Table 5 reports 476.34 s vs. 629.13 s across 30 trajectories.

Continuous scheduling improves Item F1 by 7.09 points over batch scheduling.

Table 5 shows Item F1 79.66 → 86.75.

**Figure 5.** Middleware-governance trajectories on WideSearch.

We also examine the Middleware Harness’s Loop Sensor, which detects low‑progress loops and switches strategies to keep long‑horizon searches productive.

**Figure 6** Efficiency with and without skills on the same 100 WideSearch questions. Error bars show 95% confidence intervals.

Finally, we ablate the hierarchical skill modules to measure their contribution to search quality and efficiency.

Enabling hierarchical skills raises Item‑level F1 by 2.0 points.

Table 6 reports Item‑level F1 78.3 → 80.3.

Enabling hierarchical skills raises Row‑level F1 by 3.4 points.

Table 6 reports Row‑level F1 53.1 → 56.5.

Related Work

Related work surveys prior agentic search, orchestration, and harness designs.

Tool‑integrated language agents now interleave search, browsing, reasoning, evidence collection, and synthesis. Progress stems from better search policies, task decomposition, synthetic interaction data, and reinforcement‑based post‑training, yet interaction histories grow opaque, hiding established evidence and open questions.

Multi‑agent frameworks decompose complex tasks via specialized roles, message exchange, and structured workflows; hierarchical designs separate strategic planning from execution, while structured execution systems run independent sub‑tasks concurrently. Existing systems keep coordination state inside conversations or generic ledgers, which leads to redundant work, stale results, coverage gaps, and idle capacity during long‑horizon searches.

Recent surveys treat the agent harness as a first‑class infrastructure layer that governs execution, tools, context, state, lifecycle, observability, and evaluation. The Search Tool Middleware Harness adopts these ideas for long‑horizon information seeking by preparing role‑specific context, grounding evidence, and monitoring repetition, stalls, and budget exhaustion.

System Implementation Details

Appendix details the SOCM state snapshot, skill definitions, tool interfaces, and case‑study trajectories.

The appendix A presents a concrete SOCM snapshot: frontier memory counts, a coverage map for a “Fortune 500 Comparison” table, and an evidence summary that highlights node totals and a revenue conflict for Company X.

**Table.** Fortune 500 Comparison

Appendix B describes an executable access skill for the Senate.gov API, consisting of a manifest that declares a typed parameter schema, a JSON invocation, and a Python executor that dispatches the requested function.

```yaml # manifest.yaml description: Fetch current U.S. Senators by state from senate.gov params_schema: function: type: string required: true description: one of [get_senators_by_state, list_all_states, get_state_history] state_code: type: string required: false # typed invocation selected by the agent {"function": "get_senators_by_state", "state_code": "OK"} # executor.py dispatch (simplified) async def execute(params, ctx=None): function = params.get("function") async with httpx.AsyncClient(timeout=30, follow_redirects=True) as client: if function == "get_senators_by_state": return await get_senators_by_state(client, params["state_code"]) if function == "list_all_states": return await list_all_states(client) if function == "get_state_history": ```

Appendix C records the concrete tool interfaces used throughout the system: simple‑browser operations, schema CRUD utilities, task‑queue coordination primitives, and writer‑agent commands.

The table lists three tools: **search**, **open**, and **find**. Each entry includes its required parameters and a brief description of its functionality.

**Figure 7.** Browser tool outputs as seen by a search agent. **Left:** `open()` renders a page with line-numbered markdown and bracket-style link references ([id†title†domain]). **Right:** `find()` returns numbered matches with context; calling `open(match_id)` jumps to the source line.

**Table 8.** Schema and entity management tools (orchestrator only).

**Table 9.** Task queue and agent coordination tools (orchestrator only).

The table lists five tools available to the writer agent, their key parameters, and a brief description of their functionality.

Appendix D presents process‑level case studies from WideSearch runs, each summarizing decision rationale, tool actions, and observable state transitions.

**Table 11.** Condensed agent trajectory for `ws_en_022`. Rationale is summarized from logged steps; state values are taken from SOCM deltas.

**Output excerpt.** The same song may occur in both charts, but the composite key preserves its category-specific rank while shared metadata is independently grounded.

Two further studies illustrate (i) false saturation detection and repair in a Michael Phelps medal table, and (ii) bounded recovery when journal pages return HTTP 402, prompting source fallback to Crossref/OpenAlex.

Appendix E lists ordered interface snapshots for three SearchOS cases: Beijing travel planning, agent‑harness engineering survey, and GPU‑cloud provider comparison.

Read the original paper

Open the simplified reader on Paperglide

Browse all simplified papers