Summary (Overview)

• Formulation: Open-domain information seeking is formulated as relational schema completion with grounded citations, where the task is to discover entities, populate attributes across linked tables, and anchor each value to source evidence.
• System-Level State Management: Introduces Search-Oriented Context Management (SOCM) to externalize execution state into four persistent components: Frontier Task, Evidence Graph, Coverage Map, and Failure Memory, replacing fragile implicit context.
• Pipeline-Parallel Orchestration: A continuous dispatch mechanism overlaps sub-agents and refills slots with unresolved coverage gaps, improving utilization and throughput over synchronous batch scheduling.
• Middleware Governance: A Search Tool Middleware Harness intercepts model/tool interactions to prepare context, extract and anchor evidence, detect stalls/loops, and enforce budgets outside agent prompts.
• Strong Empirical Results: On WideSearch and GISA benchmarks, SearchOS leads all evaluated single- and multi-agent baselines across all reported F1 metrics, with gains concentrated in recall and completeness (e.g., +13.4 set F1 on GISA, +4.3 item F1 on WideSearch).

Introduction and Theoretical Foundation

Recent advances in tool-integrated LLMs have made web search a core capability of information-seeking agents. However, as interaction histories grow, agents lose track of task progress: evidence becomes buried, omissions and conflicts go undetected, and failed search paths lead to repetitive loops and wasted budgets. Simply adding more agents introduces duplication and idle capacity.

Key insight: Search state should be maintained by the system rather than inferred repeatedly from interaction history. A long-horizon search system should expose coverage, preserve provenance, coordinate workers around explicit gaps, and intervene when execution stalls.

The paper formulates information seeking as relational schema completion with grounded citations. Given a natural-language request (q), the system constructs a relational search schema:

$$\mathcal{S} = (\{T_m\}_{m=1}^M, \mathcal{R}), \quad T_m = (A_m, P_m)$$

where (T_m) defines a table with attributes (A_m) and primary-key attributes (P_m), and (\mathcal{R}) contains foreign-key relations. The output is:

$$\mathcal{O} = \{(E_m, Y_m, C_m)\}_{m=1}^M$$

where each value in (Y_m) is grounded in a citation matrix (C_m) linking to a source URL and anchored excerpt. This turns an open-ended request into a concrete, measurable search target.

Methodology

Search-Oriented Context Management (SOCM)

SOCM maintains the shared state (\mathcal{M}_t = (\mathcal{F}_t, \mathcal{G}_t, \mathcal{C}_t, \mathcal{W}_t)):

• Frontier Task (\mathcal{F}_t): A dependency-aware task pool where each task (f_j = (\kappa_j, s_j, p_j, B_j, Z_j, a_j, n_j)) captures type, status, priority, dependencies, target cells, assigned agent, and attempt count. The ready set (\mathcal{R}_t) contains pending tasks whose dependencies are all terminated.
• Evidence Graph (\mathcal{G}_t = (\mathcal{N}_t, \mathcal{L}_t)): Stores atomic findings as nodes (g_i = (v_i, u_i, x_i, b_i, \gamma_i, \tau_i, s_i)) with value, source, span, schema binding, confidence, provenance tier, and status. Edges represent support, conflict, or refinement.
• Coverage Map (\mathcal{C}_t): Tracks each schema cell ((m, e, a)) with status (missing, filled, uncertain, unreachable) and supporting evidence. Coverage is computed as: $$\text{Cov}(\mathcal{C}_t) = \frac{\sum_{c \in \Omega_t} \mathbf{1}[s(c) = \text{FILLED}]}{|\Omega_t| + \sum_{m: |E_m(t)|=0} |A_m|}$$
• Failure Memory (\mathcal{W}_t): Records failed actions (uninformative queries, inaccessible sites, failed skills) to prevent repetition across agents.

Agents receive role-specific projections (x_t^{(r)} = \phi_r(\mathcal{M}_t; z_t)) rather than the full state.

Pipeline-Parallel Multi-Agent Orchestration

A central orchestrator decomposes the schema into coverage-oriented tasks. Specialized roles (orchestrator, explore, search, writer) are coordinated through SOCM, not agent-to-agent conversation.

At time (t), with (b_t) available slots and ready set (\mathcal{R}_t), the dispatcher selects:

$$\mathcal{D}_t = \text{Top}_{\min(b_t, |\mathcal{R}_t|)}(\mathcal{R}_t; p)$$

where (p) is frontier priority. After each completion, SOCM is updated, (\mathcal{R}_t) recomputed, and the freed slot immediately refilled. This event-driven policy overlaps roles and avoids batch stragglers.

Search Tool Middleware Harness

Three middleware components intercept the agent loop:

1. Context Middleware (before model call): Composes recent history (h_t), projected state (v_t^{(r)}), and retrieved skills (K_t) to produce (\tilde{h}_t^{(r)}).
2. Evidence Extraction Middleware (after tool call): Extracts schema-bound candidates (\hat{E}t = \text{Extract}(o_t, \mathcal{S}, \mathcal{C}t)), accepts only those with valid binding and anchoring, and atomically updates (\mathcal{G}{t+1}, \mathcal{C}{t+1}).
3. Sensor Middleware: Detects stalls via (\Delta^{\text{cov}}t) and (\Delta^{\text{ev}}t) over a window (w), and computes budget pressure (\rho_t = \max(n{\text{iter}}/B{\text{iter}}, n_{\text{search}}/B_{\text{search}}, \tau_t/B_{\text{time}})). Decides continue, correct, drain, or stop actions.

Hierarchical Search Skills

Three skill layers: orchestrator (decomposition, alignment), strategy (source-independent search methods), and access (site-specific retrieval). SearchOS-V1 includes 280 pre-built skills. Skills are retrieved and loaded for each task, improving quality and efficiency.

Empirical Validation / Results

Benchmarks

• WideSearch: 200 manually curated questions (100 EN, 100 ZH) across 15+ domains, requiring large-scale fact gathering and table completion.
• GISA: 373 human-crafted queries with four structured answer formats (table, set, list, item), combining multi-hop reasoning with broad aggregation.

Baselines

Single-agent: ReAct, Plan-and-Solve. Multi-agent: A-MapReduce, Web2BigTable, Table-as-Search.

Main Results (Table 2)

SearchOS leads all F1 metrics, with gains concentrated in recall and completeness.

Ablations

• Schema Planning (Table 3): Fixed schemas underperform dynamic schema planning. Even an oracle selecting the better fixed schema per case trails SearchOS by 8.2 item F1 and 7.7 row F1.
• Pipeline Scheduling (Table 4, 5): Continuous dispatch reduces time by 24.3%, improves slot utilization (34.6% → 41.7%), task throughput, and Item F1 (79.66 → 86.75) compared to batch scheduling.
• Middleware Governance (Figure 5): Three representative trajectories show loop detection and strategy switch restores coverage and entity discovery at early, mid-, and late stages.
• Skill Ablation (Table 6, Figure 6): Skills improve Item F1 by +2.0 and Row F1 by +3.4, while reducing session time by 36.6%, search calls by 39.1%, and page calls by 42.7%.

Theoretical and Practical Implications

• Theoretical: The relational schema completion formulation provides a unified, verifiable objective for long-horizon information seeking. Externalizing search state as durable, shared artifacts (rather than implicit context) offers a principled way to manage task progress, evidence provenance, and failure recovery in multi-agent systems.
• Practical: The middleware harness demonstrates that system-level execution control can make long-horizon agents more reliable without relying on fragile prompt engineering. The hierarchical skill system shows that reusable search knowledge can be separated from source-specific access, enabling efficient transfer across tasks. The continuous scheduling policy improves resource utilization and throughput.
• Limitations: The paper focuses on system infrastructure; large-scale skill synthesis from data is left for future work. The approach is evaluated on text-based benchmarks; multimodal extensions are planned.

Conclusion

SearchOS formulates open-domain information seeking as relational schema completion with grounded citations. It introduces SOCM to externalize search state (Frontier Task, Evidence Graph, Coverage Map, Failure Memory), pipeline-parallel orchestration for efficient task dispatch, a Search Tool Middleware Harness for robust execution, and hierarchical search skills. Experiments on WideSearch and GISA show significant improvements over strong baselines, especially on recall and completeness. These results suggest that explicit search state, grounded evidence, and system-level execution control provide a practical foundation for reliable multi-agent information seeking. Future work includes extending to broader domains, multimodal settings, and adaptive skill synthesis.