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

Technical Breakdown§

SearchOS formulates open-domain information seeking as relational schema completion. The goal is to populate a set of linked tables (entities and attributes) with citations. The system maintains four key externalized state components:

• Frontier Task: A queue of pending information-seeking tasks.
• Evidence Graph: A directed graph linking queries to retrieved evidence and extracted facts.
• Coverage Map: A bitmask indicating which attributes of which entities have been resolved.
• Failure Memory: A log of failed query patterns and their outcomes.

Search-Oriented Context Management (SOCM)§

SOCM externalizes the evolving state outside the LLM's context window. This prevents the agent from losing track of progress. The state is updated after each tool call.

Pipeline-Parallel Scheduling§

Instead of sequential or naive parallel execution, SearchOS uses a pipeline-parallel approach. Sub-agents operate on different stages of the pipeline: one may be generating queries, another extracting evidence, another resolving contradictions. When one sub-agent finishes a task, it picks up a new task from the Frontier Task queue that targets unresolved coverage gaps. This maximizes throughput.

Search Tool Middleware Harness (STMH)§

STMH intercepts all model-to-tool interactions. It records grounded evidence (the actual snippet returned), detects stalls (e.g., repeated same query), and reacts to budget exhaustion. It also provides a hierarchy of skills:

• Strategy Skills: High-level tactics (e.g., "decompose query", "cross-reference sources").
• Access Skills: Low-level API calls (e.g., search(query, engine)).

Agents are augmented with these skills to avoid repeating failed search patterns.

Implementation Details§

• The system is built on a Multi-Agent LLM platform (e.g., LangChain, AutoGen).
• Each sub-agent is a separate LLM instance (e.g., GPT-4) with a system prompt that includes the current state.
• Pipeline stages are implemented as Python coroutines.

Code Snippet (Pipeline Scheduler)

class SearchOSPipeline:
    def __init__(self, agents, middleware, max_tasks=100):
        self.agents = agents
        self.middleware = middleware
        self.frontier = deque()
        self.coverage = CoverageMap()
        self.failure_memory = FailureMemory()
        self.max_tasks = max_tasks
        self.active_tasks = []

    def schedule(self, task):
        if len(self.active_tasks) < len(self.agents):
            agent = self.agents[len(self.active_tasks)]
            future = agent.run(task, self.middleware)
            self.active_tasks.append((agent, future))
        else:
            self.frontier.append(task)

    def step(self):
        completed = []
        for agent, future in self.active_tasks:
            if future.done():
                result = future.result()
                self.update_state(result)
                completed.append((agent, future))
                if self.frontier:
                    new_task = self.frontier.popleft()
                    new_future = agent.run(new_task, self.middleware)
                    self.active_tasks.append((agent, new_future))
        for item in completed:
            self.active_tasks.remove(item)

    def update_state(self, result):
        # Update Evidence Graph, Coverage Map, Failure Memory
        for evidence in result.evidences:
            self.coverage.mark(evidence.entity, evidence.attribute)
        if result.failed:
            self.failure_memory.record(result.query, result.error)

Mathematical Formulation§

Let $\mathcal{E}$ be the set of entities and $\mathcal{A}$ the set of attributes. The goal is to find a mapping $f: \mathcal{E} \times \mathcal{A} \rightarrow \text{Value} \times \text{Citation}$. The Coverage Map $C$ is a binary matrix where $C_{e,a} = 1$ if attribute $a$ of entity $e$ is resolved. The Frontier Task queue $F$ consists of tuples $(e, a, q)$ where $q$ is a generated query. The agent's policy $\pi$ maps current state $S = (F, C, G, M)$ to action $a_t$ (either search, extract, or terminate). The cumulative reward is:

$$R = \sum_{e \in \mathcal{E}} \sum_{a \in \mathcal{A}} \mathbb{1}[C_{e,a}=1] - \lambda \cdot \text{cost}$$

where $\lambda$ is a cost penalty for search API calls.

Results§

On WideSearch and GISA benchmarks, SearchOS outperforms single-agent baselines (e.g., ReAct) and multi-agent baselines (e.g., AutoGen) on completeness, citation accuracy, and budget efficiency.