ParallelMuse: Agentic Parallel Thinking for Deep Information Seeking

1 Introduction

• Conventional rollouts restart from scratch, wasting tokens in low-diversity reasoning phases; existing uncertainty-based branching assumes all tokens behave alike.The cited prior partial-rollout methods estimate exploration potential using uncertainty and selectively branch where uncertainty is high.Source: §1 · p. 2
• In agentic IS, reasoning and tool-call actions form functional regions with different uncertainty patterns, motivating region-wise uncertainty estimates and selective branching.The method segments generated sequences into functional regions and expands rollouts for reasoning steps with higher exploration potential.Source: §1 · p. 2
• Answer aggregation is difficult because correct answers may be a minority, external information shifts confidence calibration, and long traces exceed context limits.Selecting only final answers neglects intermediate reasoning, while aggregating entire traces is infeasible for long-horizon agents.Source: §1 · p. 2
• Compressed Reasoning Aggregation condenses candidates into structured reports preserving answer-relevant information, then aggregates them to produce the final answer.The approach is intended to improve processing efficiency and mitigate bias from majority-based selection.Source: §1 · p. 2
• Up to 62% improvement was achieved while using 70–90% of conventional parallel thinking’s exploratory token cost across four agents and four benchmarks.The benchmarks assess deep search and reasoning abilities.Source: §1 · p. 2

2.1 Distinct Uncertainty Patterns Across Functional Reasoning Steps

• Exploration uncertainty peaks earliest, while reasoning uncertainty peaks slightly later as agents integrate retrieved information; step-level PPL serves as an uncertainty proxy.The analysis compares uncertainty in reasoning and exploration regions across steps.Source: §2.1 · p. 3, Figure 1 · p. 3

2.2 From Exploration Redundancy to Losslessly Compressible Trajectory

• The evolving information state represents discovered entities as nodes and their constructed relations, refined toward the key information needed for the answer.The final graph is described as containing information essential to answer derivation.Source: §2.2 · p. 4
• Figure 2 reports consistently high trajectory redundancy across models, supporting compression that preserves information needed for answer derivation.The redundancy ratio reflects the share of explored entities that contribute directly or indirectly to deriving the answer.Source: Figure 2 · p. 4, §2.2 · p. 4

3 ParallelMuse

• ParallelMuse combines Functionality-Specified Partial Rollout with Compressed Reasoning Aggregation as the exploration and answer-generation stages of agentic parallel thinking.The first component expands exploration; the second integrates sampled reasoning candidates.Source: §3 · p. 5

3.1 Functionality-Specified Partial Rollout

• Step-level perplexity estimates generation uncertainty within reasoning and exploration regions, and the method selects high-uncertainty steps as branching points.The process generates M initial trajectories and selects the top-k steps in a chosen functional region; M, k, and the region are tunable.Source: §3.1 · p. 5
• Branches launched from selected steps reuse preceding context through cached hidden states rather than regenerating prefixes, avoiding redundant forward passes.N − M additional partial rollouts are launched asynchronously under an overall sampling budget of N.Source: §3.1 · p. 5
• Prefix reuse lowers duplicated decoding cost while asynchronous scheduling parallelizes hot decoding, jointly targeting near-linear exploration speedup with lower token cost.The stated speedup depends on prefix reuse and asynchronous parallelization.Source: §3.1 · p. 6

3.2 Compressed Reasoning Aggregation

• Compressed reports preserve information relevant to answer derivation while removing redundant tool responses and ineffective reasoning or tool calls.The compression objective is to integrate richer intermediate reasoning while maintaining computational efficiency and avoiding context overflow.Source: §3.2 · p. 6
• Each report records the solution plan and dependencies, tools and parameters used with contributing subanswers, and how these are integrated into the final answer.Source: §3.2 · p. 6
• Aggregation considers all N compressed reports, prioritizes reasoning coherence over answer consistency, and disallows merely concatenating or enumerating answers.The reports include tool-calling provenance, so aggregation reasons over them without additional tool invocations.Source: §3.2 · pp. 6–7

4.1 Setup

• Experiments assess both PARALLELMUSE stages individually and jointly across four benchmarks spanning deep search and reasoning, using four open-source agents and benchmark-specific evaluation settings.The evaluation uses selected text-only subsets for BrowseComp, HLE, and GAIA, and all 289 BrowseComp-zh tasks.Source: §4 · p. 7, §4.1 · pp. 7–8

4 Experiments

• The experiments examine how each PARALLELMUSE stage contributes to the performance and efficiency of existing deep information-seeking agents.Source: §4 · p. 7

4.2 Overall Performance

• Across every agent model and benchmark, PARALLELMUSE consistently achieves the highest performance gains over baselines; on Tongyi-DR-30B-A3B, it is comparable to or surpasses most closed-source agents.Weighted Vote underperforms Majority Vote except for Tongyi-DR-30B-A3B and on the HLE benchmark; PARALLELMUSE avoids confidence-based answer selection.Source: §4.2 · pp. 8–9

4.3 Analysis of Partial Rollout over Distinct Functional Regions

• Partial rollout outperforms from-scratch rollout in most cases, but useful branching regions vary by model; reasoning-based branching helps less when adaptive reasoning is already strong.The analysis compares reasoning-only, exploration-only, and mixed uncertainty selection; treating all tokens as homogeneous showed no observable gains over from-scratch rollout.Source: §4.3 · p. 9

4.4 Performance Gains from Compressed Reasoning Aggregation

• With exploration gains held aside, Compressed Reasoning Aggregation alone yields the most significant improvement among the answer-generation methods.It compresses trajectories near-losslessly and integrates sampled reasoning without additional tool calls for secondary verification.Source: Figure 4 · p. 10, §4.4 · p. 10

4.5 Efficiency Gains through Context Reuse and Trajectory Compression

• 28% token savings come from context reuse in partial rollout, while trajectory compression reduces context-token usage by up to 99% relative to the full trajectory.The paper characterizes these two efficiency sources as enabling computation to be allocated to high-utility regions while removing redundant or avoidable computation.Source: Figure 5 · p. 10, §4.5 · pp. 10–11

4.6 Impact of Model Capability on Compressed Reasoning Aggregation

• Using a stronger model for aggregation improves performance: GPT-OSS-120B and then GPT-5 improve results after GPT-OSS-20B rollout, with a similar trend for Tongyi-DR-30B-A3B.The authors suggest that combining models with different strengths can balance efficiency and performance.Source: §4.6 · p. 11, Table 4 · p. 11

5.1 Deep Information-Seeking Agents

• PARALLELMUSE is proposed to exploit deep IS agents’ unique characteristics and enhance their capability and efficiency.Source: §5.1 · p. 11

5.2 Parallel Thinking for Test-Time Scaling

• Existing parallel-thinking methods inherit pure-reasoning assumptions, while PARALLELMUSE is designed around deep IS task properties.Source: §5.2 · p. 12

• PARALLELMUSE addresses redundant rollouts and difficulty integrating long-horizon reasoning under limited context capacity.Source: §6 · p. 12
• The two-stage paradigm uses insights about deep IS tasks to enhance exploration efficiency and reasoning aggregation.Source: §6 · p. 12
• Experiments across multiple open-source agents and benchmarks show substantial performance improvements while greatly reducing exploratory token consumption.Source: §6 · p. 12

• The study focuses primarily on question-answering-oriented deep IS tasks.Source: §7 · p. 12
• Its toolset is limited to Search and Visit, whereas more general agentic tasks often use broader toolsets and have substantially larger exploration spaces.Source: §7 · p. 12
• Extending effective parallel-thinking strategies to general agentic settings with complex tool configurations remains open future work.Source: §7 · p. 12