SearchOS: Explicit State Management for Robust Multi-Agent Information-Seeking

Paper: 2607.15257 Authors: Yuyao Zhang, Junjie Gao, Zhengxian Wu, Jiaming Fan, Jin Zhang, Shihan Ma, Yao Yao, Weiran Qi, Chuyan Jin, Guiyu Ma Categories: cs.AI, cs.IR

The Gap

The field has made LLM-powered agents great at executing single search queries. The boundary we’ve hit: when you string many queries together to answer a complex question, the agents lose track. They forget what they’ve already tried, what evidence they’ve gathered, and what’s still missing. Existing single-agent and even multi-agent systems (like AutoGPT-style loops) treat the search process as a stateless sequence of actions. When a query fails to return useful information, the agent doesn’t learn—it just tries something similar, wasting time and budget until it gives up or repeats itself. The core limitation is the absence of a persistent, shared memory of search progress itself, leading to fragile, inefficient, and incomplete outputs.

                    [Fragile, implicit state in agent's context]
                                      |
                                      v
[Complex Open-Domain Query] --> [Multi-Agent Search] --> [Repetitive Loops & Wasted Budget]
                                      |                                  |
                                      |                                  v
                                      +----> [Poor Quality/Incomplete Final Answer]

[SearchOS Assumption: Making state explicit and external prevents loops.]

                                      |
                                      v
[Query] --> [SOCM (Explicit State)] --> [Pipeline-Parallel Scheduling] --> [Robust, Complete Answer]

The Increment

One sentence: Before this paper, multi-agent search systems operated on implicit, ephemeral state trapped in context windows; after this paper, they have a robust, externalized memory system (SOCM) that tracks progress and failures, enabling coordinated, efficient search.

Core Mechanism

SearchOS works by first reframing the information-seeking problem. Instead of just “find answers,” it’s framed as relational schema completion. The system treats the user’s query as defining a set of linked tables (an “evidence graph”) that need to be populated. For example, answering “Compare the founding teams of SpaceX and Blue Origin” would involve a table for each company with rows for founders, their backgrounds, etc. Each cell must be filled with a value and a grounded citation.

The engine of this process is Search-Oriented Context Management (SOCM). SOCM externalizes four key data structures that represent the evolving search state:

1. Frontier Task: The current, highest-priority sub-task (e.g., “Find CTO of Blue Origin”).
2. Evidence Graph: The growing network of discovered entities, their attributes, and the citations linking them.
3. Coverage Map: A scorecard tracking which parts of the schema are filled, empty, or flagged as failed.
4. Failure Memory: A log of all attempted queries that yielded no useful results.

A central scheduler uses this state to orchestrate a team of sub-agents in a pipeline-parallel manner. It constantly refills the agents’ task queues by pulling new tasks that target the biggest gaps shown in the Coverage Map. A Search Tool Middleware Harness sits between the agents and the search tools, logging every interaction, detecting stalls or budget exhaustion, and enforcing the use of a reusable hierarchical skill system (e.g., “use a specific academic database for author queries”).

[User Query]
       |
       v
[Schema Parser] --> [Evidence Graph (Tables)]
       |                   ^
       v                   |
[Coverage Map] <--> [SOCM State Manager] <--> [Failure Memory]
       |                   |
       +-------v-----------+
               |
       [Task Scheduler]
       /      |       \
      v       v        v
[Agent 1] [Agent 2] [Agent 3]  <-- Pipeline-parallel execution
      \       |       /
       v      v      v
[Search Middleware Harness] --> Logs, Skills, Budget Control
       |
       v
[External Search APIs]

Key Concepts

• Relational Schema Completion: Imagine you’re asked to fill out a complex form about a topic, but the form is blank and the information is scattered across the entire internet. You don’t just hunt for the final answer; you first design the form (the schema), then you go field-by-field, searching for each specific piece of data. Once you find a name for one field, that name might become a new search term to fill related fields in another part of the form. SearchOS does this automatically, structuring the chaotic search into a systematic data-filling mission.
• Coverage Map: Think of this as a progress bar for your research project, but it’s not just one bar. It’s a dashboard with a progress bar for every single sub-question or data point. The scheduler’s job is to always look at this dashboard and assign the next researcher (sub-agent) to the part of the project that’s most behind schedule. It prevents ten people from accidentally working on the same easy question while ignoring the hard, crucial one.
• Failure Memory: This is the system’s “blacklist” and “lesson learned” journal. If a search for “Blue Origin founding date via news articles” returns nothing but ads, that specific query pattern is logged. The next time an agent tries something similar, the middleware can block it or force it to try a different skill (e.g., “try a financial database instead”). It’s what allows the system to get smarter within a single task, not just across tasks.

Framework Shift

Before (mainstream approach):        After (SearchOS):
[Query] --> [Single/Loose Multi-Agent Loop]
            |  (State is implicit, internal, ephemeral)
            v
[Search, Search, Search...] --> [Hope for answer]
            |                 (Repeats failed patterns)
            v
[Result: Often incomplete]

[Query] --> [SOCM (Explicit, Persistent State)]
            |  (Coverage Map, Evidence Graph, Failure Memory)
            v
[Scheduler sees gaps] --> [Assigns targeted tasks to agents in parallel]
            |                    (Reuses successful skills, blocks failures)
            v
[Result: More complete, efficient]

From implicit, agent-local state to explicit, system-shared state, the core shift is turning the fragile memory of an LLM into a robust, externalized project management dashboard for information retrieval.

Expert Assessment

Problem choice: This is a real and growing gap. As agents move from simple Q&A to complex, multi-step research tasks, the “state amnesia” problem is becoming the primary bottleneck. The paper correctly identifies that the issue isn’t just about better LLMs, but about better system design around them. It’s well-positioned at the intersection of systems engineering and AI.

Method maturity: This is a clever systems engineering insight applied to AI agents, not a new fundamental model. It’s more “brute force” in the sense of building a complex middleware layer, but that’s arguably necessary. The schema-completion framing is elegant. One potential oversight is the added latency and complexity of the middleware; simpler approaches like better prompt engineering for chain-of-thought might be overlooked, but they likely wouldn’t scale to this level of robustness.

Experimental integrity: The baselines (single-agent, basic multi-agent) seem fair and standard. The benchmarks (WideSearch, GISA) are designed for open-domain seeking. The claim of leading “all metrics” is strong but plausible given the architectural advantage. A red flag would be if the benchmarks are too small or synthetic; the paper would need to show it works on real, messy web-scale queries.

Writing quality: The abstract is very dense. The methodology section, likely where the SOCM and scheduling details live, is probably where the authors could have been clearer with more concrete examples and fewer acronyms. The “structural metaphor” (which I had to create for this summary) is missing from the paper itself, making it less accessible.

Verdict: weak accept — It’s a well-motivated systems paper that addresses a clear pain point with a novel architectural solution. The impact is more on the engineering side than a new scientific paradigm, but it’s a necessary step for practical agent deployment.

Takeaways

1. Externalize Your Agent’s “Scratchpad”: Don’t let your agent’s memory of what it’s done live only in its context window. For any complex, multi-step task, build an external, structured state object (a JSON, a simple database) that the agent reads from and writes to. This makes the agent’s progress inspectable, debuggable, and preventable from going in circles.
2. Frame Ambiguous Tasks as Data-Filling Problems: When faced with a vague “research this” task, start by asking: “What would the final report’s structure look like?” Define the headers and required data points first (the schema). Then, turn each data point into a discrete, searchable sub-task. This creates natural parallelism and a clear definition of “done.”
3. Implement a “Circuit Breaker” for Search: For any system that calls external APIs repeatedly, build a lightweight layer that logs failed or low-value queries. If the same pattern of failure repeats, this layer should force the agent to use a different strategy or stop and escalate, preventing infinite loops and wasted spend.