REDSearcher: A Scalable and Cost-Efficient Framework for Long-Horizon Search Agents

Dual-Constrained Task Synthesis

• REDSearcher synthesizes tasks with graph cycles and interlocking constraints, while dispersing logically coupled facts across sources to require multi-hypothesis reasoning and cross-document search.Generation is formulated as constraint satisfaction over a latent knowledge graph, with explicit evidence-dispersion constraints to prevent single-page shortcuts.Source: §1 · p. 2

Proactive Tool-Augmented Queries

• Tool-augmented queries replace explicit entities with tool-resolvable constraints, making task completion depend on appropriate tool use and densifying targeted learning signals.Examples include replacing a place name with a routing or distance constraint for a map tool, or a named entity with a visual cue requiring image understanding.Source: §1 · p. 2

Cost-Efficient Mid-Training

• Two-stage mid-training first strengthens grounding and hierarchical planning with synthetic data, then uses simulated tool loops and long-horizon trajectories to improve exploration and reduce downstream trajectory-collection costs.The stages separate atomic subskill acquisition from interactive execution, preparing models for environmental feedback and state retention before real-world exposure.Source: §1 · p. 2

Functionally Equivalent Simulation Environment

• A lightweight local environment mimics web dynamics without live API latency, keeping evidence solvable but dispersed among distractors for efficient reinforcement-learning experiments and evaluation.All necessary evidence is present in a closed corpus, but physically dispersed and buried in extensive distractor documents.Source: §1 · p. 2

2.1 Problem Formulation

• An agent addresses a potentially fuzzy, underspecified text or multimodal question through tool calls and observations, maintaining an internal state and returning an evidence-grounded answer that reflects uncertainty when evidence is incomplete or conflicting.The internal state summarizes interaction history, constraints, hypotheses, and intermediate conclusions; observations can include text, images, and metadata.Source: §2.1 · p. 3

2.2 ReAct-style Trajectory Representation

• Following ReAct [44], each session is represented as the question, interleaved state/action/observation tuples, and a final answer produced from accumulated evidence and state.The agent selects each tool call from its current transcript, receives tool feedback, and answers after the final update.Source: §2.2 · p. 3

2.3 Context Management

• When repeated tool calls and accumulated content approach the context limit, Discard-all [23] removes prior interaction tuples while retaining the original question and minimal task specification.This trades long-term in-context memory for token budget to continue exploration and tool use.Source: §2.3 · p. 3

3 Scalable Complex Task Synthesis

• Existing open-source datasets [43] are predominantly linear and retrieval-friendly, so the authors propose a controllable synthesis pipeline for challenging deep-search queries.The target queries require multi-hop reasoning, ambiguity, non-linear search paths, iterative tool use, and synthesis of fragmented evidence.Source: §3 · p. 4

3.1 Motivation

• Deep-search complexity is decomposed into topological logical complexity and information source dispersion.These dimensions capture how tightly reasoning constraints are coupled and how fragmented the evidence is across sources.Source: §3.1 · p. 4

3.1.1 Topological Logical Complexity: A Treewidth Perspective

• Treewidth is adopted to measure topological logical complexity because graph-structured reasoning difficulty depends on structural coupling, not only graph size.The passage notes that broad families of CSP-style problems become tractable on bounded-treewidth graphs, motivating treewidth as a structural metric.Source: §3.1.1 · p. 4
• Reasoning cost is approximated as O(N · d^(k+1)), making higher treewidth k an exponential burden as entangled hypotheses must be maintained.Here N is reasoning hops and d is the branching factor; low-treewidth structures support divide-and-conquer, while higher treewidth signals stronger constraint entanglement.Source: §3.1.1 · p. 4
• Figure 2 maps increasing treewidth from chains (k = 1) through cycles (k = 2) to tetrahedral coupling (k = 3), shifting reasoning from propagation to joint verification.The examples give approximate costs of O(N · d^2), O(N · d^3), and O(N · d^4), respectively; the high-dimensional case requires validating a complete K4 subgraph.Source: §3.1.1 · pp. 4–5, Figure 2 · p. 5

3.1.2 Distributional Complexity: Information Dispersion

• Treewidth alone does not determine open-web difficulty, since a single comprehensive document can shortcut retrieval; Minimum Source Dispersion measures the minimum documents needed to cover the reasoning graph’s required information.A retrieved subset covers graph G when the union of its information suffices to resolve all nodes in G.Source: §3.1.2 · p. 5
• Tasks are most resistant to shortcut retrieval when both treewidth and evidence dispersion are high, motivating joint control of graph topology and Minimum Source Dispersion.The resulting synthesis encourages iterative planning and cross-document evidence synthesis under realistic web retrieval.Source: §3.1.2 · p. 5

3.2.1 QA generation

• Filtered English and Chinese Wikipedia seeds anchor DAGs expanded from Wikidata relations and web hyperlinks, then LLM graph densification adds cycles that require joint constraint satisfaction.The pipeline targets structural complexity k ≥2 rather than relying only on explicit database relations.Source: §3.2.1 · p. 6
• One-Graph-Multi-Task sampling selects connected subgraphs and answer nodes by topological role, yielding an order-of-magnitude more training instances from each enriched graph.Different roles, such as deep leaves and high-degree hubs, induce different reasoning requirements.Source: §3.2.1 · p. 6
• Questions generated from sampled graphs are rewritten to replace static facts with tool-resolvable constraints, making external execution intrinsic to the reasoning task.Examples include routing constraints resolved with a Maps API and citation-based identifiers retrieved from academic profile indexes.Source: §3.2.1 · p. 7

3.2.2 Verifier pipeline

• The verifier escalates from tool-free difficulty filtering and top-50 search-snippet retrievability to inconsistency checks, n-rollout answer validation, and alternative-answer uniqueness filtering.An instance is retained after rollout verification if at least one rollout predicts the supplied answer; rollout pass rate is recorded as a confidence signal.Source: §3.2.2 · p. 7
• Over 85% of 500 instances passed human verification; DeepSeek-V3.2 [23] achieved ∼40% accuracy under the standard agent setting, while humans solved 47% within 30 minutes.University-level annotators assessed logical consistency and grounding sufficiency; human solvability was measured with a 30-minute search budget.Source: §3.2.2 · p. 7

3.3.1 Multimodal QA Generation

• Modality injection turns textual reasoning DAGs into cross-modal tasks by anchoring intermediate constraints in images and making visual cues necessary for downstream reasoning.Visual attribute anchoring attaches an image and description to a DAG node; cross-modal dependency ensures the image is not merely decorative.Source: §3.3.1 · p. 8
• Image-aware fuzzing uses abstract visual references and relocates visual constraints along the reasoning path to create visual bottlenecks and tune task difficulty.Modality translation can place a visual constraint after text-based steps, increasing effective reasoning depth.Source: §3.3.1 · p. 8
• The multimodal verifier filters text-solvable or text-retrievable tasks, image-only guessable answers, visually misaligned evidence, and tasks too easy for multimodal agents.The checks test image necessity, visual consistency with retrieved webpages, and agent success across multiple rollouts.Source: §3.3.1 · p. 8
• The extension uses the text-only pipeline’s end-to-end skeleton with limited modifications, preserving scalability, controllable difficulty, explicit dependencies, and verifiability for multimodal QA generation.Modality injection and vision-aware verification turn a static knowledge graph into a cross-modal reasoning scaffold requiring perception, reasoning, and retrieval.Source: §3.3.1 · pp. 7–8

3.3.2 Multimodal Trajectory Generation

• For multimodal SFT, a ReAct [44] Qwen3VL-235B agent alternates reasoning and structured tool calls, with episodes capped at 20 rounds and only ground-truth-matching answers retained.Tool outputs guide subsequent steps; after the cap, the model must provide a final answer.Source: §3.3.2 · p. 8

• The recipe starts from pretrained open-source models and specializes them for multi-turn online web search with tool interaction.Source: §4 · p. 9
• Mid-training uses large-scale synthetic long-horizon search traces to teach diverse reasoning trajectories and tool-use patterns at low cost without degrading general language ability.It aims to establish stable interleaved behaviors.Source: §4 · p. 9
• Post-training optimizes end-to-end behavior to enhance agentic reasoning for complex information seeking.Source: §4 · p. 9

5 Agentic Mid-Training via Low-Cost Large-Scale Data Synthesis

• Agentic mid-training bridges pre-training and agent-specific post-training in two phases, using scalable data synthesis to address the high cost of manual annotation and real-world interaction.The first phase strengthens atomic capabilities; the second builds multi-turn environmental interaction and long-horizon decision-making.Source: §5 · p. 9

5.1 Stage I: Intent-anchored Grounding and Hierachical Planning (32K Context)

• Stage I trains intent-anchored grounding and hierarchical planning: reverse QA with relevant and distractor documents supports evidence extraction, while entity and page structure guides plans from concrete and ambiguous goals.The QA synthesis uses public Wikipedia dumps and cached web crawls; plans are generated from flattened knowledge-graph and webpage structure along information flow.Source: §5.1 · pp. 9–10

5.2 Stage II: Agentic Tool Use and Long-horizon Interaction (128K Context)

• Stage II adds complete multi-turn ReACT tool-calling trajectories and long-horizon search interactions through LLM-generated tool protocols and feedback plus a local simulated web environment.The local environment, based on Wikipedia and web-crawl dumps, supports search and webpage access and is designed to make synthesized complex queries solvable, avoiding costly and potentially inconsistent LLM-simulated inputs for long-horizon tasks.Source: §5.2 · pp. 10–11

6.1 High-quality Trajectory Synthesis in Real-world Environments

• The low-cost, scalable pipeline synthesizes deep-search questions without human intervention at difficulty comparable to BrowseComp and keeps correct, low-failure ReAct trajectories, one per question.Samples exceeding the 128K-token context limit are discarded; synthesis and agentic RL use QAs produced by this pipeline.Source: §6.1 · p. 11

6.2 Supervised Fine-tuning

• SFT applies standard next-token prediction to high-quality trajectories while masking environment observations from gradient updates, with a 128K-token context limit.SFT starts from the mid-training checkpoint.Source: §6.2 · p. 12

6.3 Agentic Reinforcement Learning

• GRPO [29] trains a ReAct policy with an LLM judge’s answer-correctness reward, group-relative advantages, and clipped policy gradients using DAPO [45] clip higher, without format rewards.The judge evaluates whether the agent’s prediction aligns with the ground-truth answer after each rollout.Source: §6.3 · p. 12
• The offline search simulator preserves real-API interfaces, complete direct and intermediate evidence, and realistic distracting noise; its local corpus spans tens of millions of documents and supports search, visit, and Python.It uses cached search and visit results collected during QA synthesis.Source: §6.3 · p. 12
• RL queries are drawn from diverse synthesis pipelines and filtered to avoid overly simple or difficult tasks; an Agent-as-Verifier reduces the query set’s error rate to 10% of the original.The verifier uses external tool calls to check relevant information against question metadata and trajectories.Source: §6.3 · p. 13
• Asynchronous rollouts based on Slime and two-tier load balancing improve throughput and prefix-cache reuse for searches up to 128K tokens, while a dedicated tool server with fallbacks stabilizes environment calls.Requests within a rollout retain inference-engine affinity; balancing across engines combines round-robin and least-access scheduling.Source: §6.3 · p. 13

7.2.1 Main Results

• With context management, REDSearcher scores 51.3 overall, surpassing Tongyi DeepResearch-30B (48.5) [37] and WebSailorV2-30B (46.0) [20], and scores 80.1 on GAIA versus GPT-5–Thinking–high (76.7) [30].The paper also reports that REDSearcher surpasses Claude-4.5-sonnet (41.1) and OpenAI-o3 (49.6) in overall performance.Source: Table 1 · p. 14, §7.2.1 · p. 14

7.2.2 Ablation of Mid-Training Stages

• Mid-training raises average performance from 42.81 to 47.39; grounding improves BrowseComp (+1.87), planning improves GAIA (+4.13), and tool-use training improves BrowseComp-ZH (+8.91).Grounding and planning build atomic competencies, while Stage II uses environmental feedback, long-horizon trajectories, and 128K context to support goal consistency and execution.Source: §7.2.2 · p. 14, Table 2 · p. 15

7.3 RL Continues to Advance Model Capabilities

• 51.3 average evaluation reward (+3.9) and a BrowseComp score of 42.1 (+2.7) follow RL, up from the SFT checkpoint’s 47.4 and 39.4, respectively.Average tool calls decrease from 100.6 to 90.1 (10.4%) while reward remains stable or improves, indicating more streamlined search without sacrificing effectiveness.Source: Figure 6 · p. 15, §7.3 · p. 15

7.3.1 Decoupling Tool Use from Parametric Knowledge

• REDSearcher scores lowest among compared systems without tools but improves substantially with tools, making tool-enabled gains a more diagnostic signal of deep-search competence than final accuracy alone.Several strong baselines retain non-trivial tool-free accuracy, potentially reflecting broader pretraining coverage or benchmark overlap.Source: §7.3.1 · p. 15, Figure 7 · p. 16

7.4.1 Main Results

• On MM-BrowseComp, REDSearcher is competitive with Gemini-3-Pro and Seed1.8 and substantially outperforms the Qwen3-VL-235B agent baseline.It also performs strongly on MMSearch [16] and LiveVQA [11]; the paper reports text-only transfer and further overall improvement from reinforcement learning.Source: Table 3 · p. 16, §7.4.1 · p. 16

7.4.2 MultiModal DeepReSearch Analysis

• Simple multimodal benchmarks generally need fewer search turns than challenging ones, where over-searching is more pronounced and many examples approach the 30-turn cutoff.After RL, tool-use turns decrease, particularly on simpler benchmarks; the authors attribute this to the RL phase’s 20-turn limit.Source: Figure 8 · p. 17, §7.4.2 · p. 17
• REDSearcher-MM varies its tools by benchmark: MM-BrowseComp [22] prompts more text-search steps, while MMSearchPlus [32] prompts more image-centric operations.MMSearch [16] mainly involves web search and webpage browsing.Source: Figure 9 · p. 17, §7.4.2 · p. 17
• The model’s multimodal reasoning uses decomposition, reflection, and verification, with less of each on simpler benchmarks and greater use of visual information in multimodal reasoning.The analysis contrasts simpler BrowseComp-VL [12] and MMSearch [16] with benchmarks of varying difficulty and type.Source: §7.4.2 · pp. 17–18, Figure 10 · p. 18

8 Conclusion

• Dual-constrained task synthesis generates structurally complex tasks with dispersed evidence, requiring iterative planning and cross-document synthesis.This targets the scarcity of high-quality training data.Source: §8 · p. 18
• Cost-efficient mid-training separates atomic subskill acquisition from interactive execution, while a functionally equivalent simulation enables high-throughput trajectory generation without expensive live API calls.Source: §8 · p. 18
• Trajectory synthesis, supervised fine-tuning, and agentic reinforcement learning advance search intelligence toward proactive, long-horizon reasoning and autonomous exploration.The framework targets exploration over the open world.Source: §8 · p. 18

A Implementation Details.

• Text REDSearcher uses Qwen3-30B-A3B [42], staged mid-training and SFT, and GRPO with 32 queries and 16 rollout samples per query.Mid-training batch sizes are 512 in Stage 1 and 256 in Stage 2; SFT uses batch size 128. The learning rate decays from 5e-5 to 1e-6 (linear in mid-training, cosine in SFT); RL uses learning rate 1e-6, clip high 0.28, TIS and R2, and excludes repetitive, excessively long, or tool-failure samples from gradient updates. Inference uses temperature 0.85, top_p 0.95, and maximum length 128K; context-limit overflow triggers rollback and a forced answer. The visit-tool summarizer is Qwen3-30B-A3B-Instruct-2507, and the LLM-as-Judge is GPT-OSS-120B.Source: A Implementation Details · p. 23
• Multimodal search uses Qwen3-VL-30B-A3B-Thinking, with GRPO training using 32 prompts and 8 rollouts per prompt.SFT uses batch size 128, learning rate 1×10−5, and three AdamW epochs with cosine learning-rate decay. RL uses KL coefficient 0.0, maximum response length 32,768 tokens, and a maximum of 20 tool calls per episode.Source: A Implementation Details · p. 23

REDSearcher system prompt

• The REDSearcher prompt assigns a deep-search assistant to conduct rigorous, multi-source investigations and integrate findings into comprehensive, accurate, objective responses.It frames the remit to include both broad open-domain questions and specialized academic inquiries.Source: B System Prompt · p. 24
• Its operating principles direct the agent to decompose complex questions, prioritize authoritative sources, assess source quality and uncertainty, synthesize evidence, and remain neutral.Source: B System Prompt · p. 24
• REDSearcher provides web search and page-visit, Python, Google Scholar, and Google Maps functions, with calls formatted as JSON inside tool-call tags.Source: B System Prompt · pp. 24–25

REDSearcher-MM system prompt

• The multimodal prompt requires stepwise problem solving, continued work until resolution, and extensive planning before calls and reflection on their outcomes.It also directs the agent to search when its knowledge is insufficient.Source: B System Prompt · p. 26
• REDSearcher-MM supports text and image search, image zoom-in, and image-similarity search to gather and inspect visual evidence.Source: B System Prompt · pp. 26–27
• For image tasks, the prompt makes supplied images accessible through indexed variables and requires a boxed core answer with supporting context inside answer tags.Source: B System Prompt · p. 26

Synthetic data cases

• A music-industry question links clues about a South American disease outbreak, a founder, and polymer record material to the pressing plant and label Vinil Brasil.The question asks for the plant and label combining the Portuguese word for vinyl with a South American country.Source: C Synthetic Data Case · p. 28
• A healthcare question connects fatal generator and electrical fires in 2020 to identify the suburban facility as Apex Hospital.The question links the facility to a separate hotel COVID-facility fire in the same state.Source: C Synthetic Data Case · p. 28
• A stock-car racing question combines a 2001 event, its pole winner, and an image of the winning vehicle’s livery; the supplied answer is 14th Annual Checker Auto Parts.The prompt asks for the competition’s official name.Source: C Synthetic Data Case · p. 29
• A historical-geography question uses a depopulated village, a medieval tower image, and a settlement name’s translation to ask for the village’s identity.The passage does not supply an answer.Source: C Synthetic Data Case · p. 30
• An athlete-identification question combines a copper-sculpture image with clues about a neighboring district’s school and its founding year.The passage asks for the athlete but does not supply an answer.Source: C Synthetic Data Case · p. 31