ParallelMuse: Agentic Parallel Thinking for Deep Information Seeking

🎯 Pitch

Standard parallel thinking catastrophically wastes tokens on information-seeking agents by blindly restarting entire rollouts—oblivious to the fact that uncertainty is not spread uniformly across a trajectory but concentrated in specific functional phases like sub-question formulation. PARALLELMUSE exploits this structure by reusing low-uncertainty prefixes and only branching at high-uncertainty reasoning steps, then compresses the resulting redundant exploration streams to deliver up to a 62% accuracy gain while cutting token costs by 10–30%.

1. Executive Summary

This paper introduces PARALLELMUSE, a two-stage paradigm for applying parallel thinking to deep information-seeking (IS) agents—addressing inefficiency from repeatedly rolling out trajectories from scratch and difficulty integrating long-horizon reasoning traces during answer generation under limited context capacity. Evaluated across four open-source agents (GPT-OSS-20B, GPT-OSS-120B, DeepSeek-V3.1-Terminus, and Tongyi-DeepResearch-30B-A3B) on BrowseComp, BrowseComp-zh, GAIA, and Humanity's Last Exam, the framework combines Functionality-Specified Partial Rollout (uncertainty-guided branching at distinct functional regions—reasoning vs. exploration steps—with KV-cache prefix reuse to avoid regenerating shared prefixes) and Compressed Reasoning Aggregation (losslessly condensing redundant trajectories into structured reports capturing solution planning, methods, and final reasoning before aggregating across reports). PARALLELMUSE achieves up to 62% performance improvement with a 10–30% reduction in exploratory token consumption, establishing that agentic parallel thinking can simultaneously improve both accuracy and efficiency only when exploration is targeted at behavior-level uncertainty and aggregation exploits the high redundancy inherent in IS trajectories.

2. Context and Motivation

The Core Problem: Parallel Thinking Doesn't Translate Cleanly to Information-Seeking Agents

The fundamental question this paper addresses is deceptively simple: how do we effectively apply parallel thinking—generating multiple reasoning trajectories and synthesizing them into a single answer—to deep information-seeking (IS) agents? While parallel thinking has become a standard test-time scaling strategy for pure reasoning tasks (mathematics, coding), the paper argues that its direct application to IS agents is deeply suboptimal, plagued by two interdependent problems that prior work has not systematically addressed.

This gap matters because IS agents represent a qualitatively different class of AI systems. Unlike math solvers that reason over static problem statements, IS agents operate in an open-ended loop: they formulate sub-questions, issue search queries and page visits to external environments, integrate retrieved information into internal reasoning, and iteratively refine their understanding. This process generates long-horizon interaction–reasoning trajectories that can span dozens of turns, each containing both model-generated reasoning tokens and externally sourced tool responses. The sheer scale and hybrid nature of these trajectories breaks the assumptions underlying conventional parallel thinking methods.

The paper identifies two specific failure modes:

Failure Mode 1: Inefficient exploratory sampling through redundant from-scratch rollouts. Conventional parallel thinking typically resamples entire reasoning chains independently for each parallel branch (as in self-consistency or best-of-N approaches). In IS tasks, where trajectories are long and much of the early exploration (initial query formulation, broad information gathering) is shared across high-quality solutions, regenerating these shared prefixes from scratch for every branch is computationally wasteful. The paper cites prior work showing that exploration diversity is "inherently low" during certain reasoning phases (Section 1), making repeated rollouts token-expensive with diminishing returns. Some prior work has introduced partial rollout methods that estimate exploration potential via uncertainty and selectively branch where uncertainty is high (Hou et al., 2025; Dong et al., 2025; Li et al., 2025e). However, as the paper argues, these approaches make a critical assumption that the paper identifies as false for IS agents: they treat all tokens as functionally homogeneous, assuming every token contributes equally to exploration and exhibits similar uncertainty patterns. In IS agents, tokens fall into two functionally distinct categories—reasoning tokens (internal deliberation about what is known and what to do next) and exploration tokens (tool calls that retrieve external information). The paper's pilot observations (Section 2.1, Figure 1) demonstrate that these regions exhibit different uncertainty dynamics: exploration uncertainty peaks at the earliest stages when no external information has been gathered, while reasoning uncertainty peaks slightly later when the agent begins integrating retrieved information. A partial rollout method that doesn't distinguish between these regions is effectively aiming at the wrong target—it may branch at steps where uncertainty is high but the functional role of that step (e.g., a tool call) limits the potential for productive exploration, while missing branching opportunities in other functional regions where uncertainty genuinely signals unexplored solution paths.

Failure Mode 2: Context-limited answer aggregation that either ignores reasoning or exceeds capacity. After generating multiple candidate trajectories, parallel thinking must synthesize them into a single answer. The paper identifies a fundamental tension in how this is done for IS agents. On one hand, answer selection methods (majority voting, confidence-weighted voting) are efficient but fail in IS settings for two reasons. First, in complex agentic tasks with vast sampling spaces, the correct answer may not dominate numerically—"it often constitutes only a small fraction of all possible sampled outcomes" (Section 1). Second, the continual incorporation of external, non-model-generated information (tool responses) shifts the model's output distribution, degrading confidence calibration (Jang et al., 2024). The paper provides empirical evidence for this in Table 2: Weighted Vote underperforms Majority Vote across most models, with the paper attributing this to confidence miscalibration from external content integration. On the other hand, answer aggregation methods that consider intermediate reasoning—not just final answers—face a context capacity problem. IS trajectories are so long that including full reasoning traces from multiple candidates easily exceeds typical context windows (e.g., a single trajectory might span tens of thousands of tokens). Recent work attempts a compromise: aggregate only the last few reasoning steps (Qiao et al., 2025). But this discards earlier content—the planning, problem decomposition, and entity discovery phases—which is often essential for evaluating whether a final answer is well-supported by the evidence trail. The paper argues this creates an impossible tradeoff: either you see the full reasoning but can only compare a few candidates (severely limiting the benefits of parallel thinking), or you compare many candidates but only see their final answers or truncated reasoning (losing the signal needed to distinguish well-reasoned answers from lucky guesses).

The paper positions these two failure modes as coupled rather than independent: inefficient exploration (Failure Mode 1) means each candidate trajectory costs more tokens to generate, making the context capacity problem (Failure Mode 2) even more severe because you can afford fewer candidates or shorter representations of each. Conversely, an aggregation method that can't effectively use the intermediate reasoning within trajectories (Failure Mode 2) undermines the value of generating diverse exploratory paths in the first place (Failure Mode 1), since the additional exploration information is discarded during answer synthesis.

Why This Problem Matters: Beyond Benchmarks to Agentic Reasoning Deployment

The practical stakes are high across several dimensions that the paper touches on directly or implicitly:

Deployment economics for deep research systems. IS agents capable of conducting multi-step web research are among the most computationally expensive AI systems to operate. Each trajectory can involve dozens of search queries, hundreds of page visits, and extensive reasoning—with token counts easily reaching tens of thousands per query. When parallel thinking is applied (e.g., running 8 independent trajectories and selecting the best answer), costs scale linearly with the number of branches. Organizations deploying deep research capabilities at scale (for enterprise intelligence, scientific literature review, competitive analysis) face a direct choice: accept the linear cost scaling of naive parallel thinking, or find ways to achieve the benefits of parallelism without the proportional cost increase. The paper's reported 10–30% token reduction with up to 62% performance improvement makes this a concretely addressable engineering problem rather than an unavoidable cost of quality.

The exploration-exploitation tension in open-ended search. Deep IS tasks have an inherently different structure from closed-form reasoning. In math, the solution space is bounded—there are correct and incorrect ways to manipulate equations, and diversity primarily helps by providing multiple shots at finding a valid proof path. In IS, the solution space is fundamentally open: for a question like "What were the economic impacts of the 2023 Türkiye earthquakes on the textile industry?", there are countless web sources to consult, multiple analytical frameworks to apply, and no single ground-truth answer in the training data. The agent must simultaneously explore broadly (to discover relevant information from a vast web environment) and reason deeply (to synthesize findings into a coherent answer). Naive parallel thinking addresses only the exploration dimension by running independent searches, but at the cost of depth—each branch gets a fraction of the total compute budget, potentially none go deep enough. The paper's approach of targeted exploration (branching only at high-uncertainty functional steps) and reasoning-preserving aggregation (compressing full trajectories rather than truncating them) attempts to resolve this tension, making parallel thinking amplify both breadth and depth simultaneously.

The gap between pure reasoning and agentic reasoning test-time scaling laws. The field has made rapid progress in understanding how test-time compute scales for pure reasoning (the reference paper discusses compute-optimal strategies for math). But IS agents differ in ways that invalidate the assumptions of those scaling laws: (1) token costs are dominated by tool interactions, not reasoning, (2) the value of additional exploration is highly non-uniform—some branches discover nothing useful while others hit critical information, and (3) answer quality depends on information coverage (did you find the right sources?) as much as reasoning quality (did you correctly synthesize what you found?). The paper addresses a gap in the test-time scaling literature by analyzing these IS-specific properties and designing methods that exploit them rather than fighting against them.

Where Existing Approaches Fall Short

The paper identifies specific limitations in prior work along multiple axes, building on both parallel thinking literature and IS agent design:

Conventional parallel thinking assumes pure reasoning. Self-consistency (Wang et al., 2022) and its variants select answers by majority voting across independently sampled chains-of-thought. This works for math because: (a) the reasoning space is relatively constrained (same problem statement, same allowed operations), (b) correct answers tend to be produced by multiple reasoning paths (the "correct answer clusters" phenomenon), and (c) the model's internal knowledge is the primary information source (no external information shifts the output distribution). IS agents violate all three: (a) different trajectories may explore entirely different information sources and arrive at different conclusions that are both reasonable given what was discovered, (b) the correct answer may be rare because discovering the necessary information requires specific search queries that only a few branches happened to issue, and (c) tool responses inject external content that the model never generated, breaking the calibration between internal probability and external correctness. The paper's empirical evidence supports this: in Table 2, majority voting helps over no scaling but leaves substantial room for improvement, and confidence-weighted voting often underperforms majority voting (e.g., GPT-OSS-20B on BrowseComp: Majority Vote 44.0 vs. Weighted Vote 41.0), directly contradicting the expectation that model confidence should be a reliable signal.

Partial rollout methods assume token-homogeneous uncertainty. Prior work on tree-search and partial rollout for LLMs (Dong et al., 2025; Hou et al., 2025; Li et al., 2025e) estimates where to branch by computing uncertainty over all tokens and selecting high-uncertainty steps. The paper argues this is fundamentally mismatched to IS agents because it treats a tool-call token with high uncertainty (e.g., uncertainty about which search query to issue) as equivalent to a reasoning token with high uncertainty (e.g., uncertainty about how to interpret retrieved information). But these are different kinds of uncertainty with different implications: exploration uncertainty reflects ignorance about the external world (which can only be resolved by gathering more information), while reasoning uncertainty reflects difficulty integrating what is already known (which may benefit from alternative reasoning paths but not from additional tool calls). The paper's pilot observations (Section 2.1, Figure 1) provide quantitative evidence that these uncertainties peak at different stages of task execution, supporting the claim that functional-region-aware branching can allocate exploration budget more effectively. The paper explicitly notes that their preliminary experiments with homogeneous (non-functional-region-distinguished) partial rollout "performs comparably to full from-scratch rollouts and provides no observable gains" (Section 4.3 footnote), directly validating the insufficiency of prior token-homogeneous approaches in IS settings.

Answer aggregation methods either discard reasoning or discard candidates. The paper situates its contribution within a spectrum of prior approaches: (1) answer selection methods (majority vote, confidence weighting) are efficient but discard all intermediate reasoning—they treat each trajectory as a black box producing a final answer, ignoring whether that answer is well-supported by the evidence gathered; (2) full-reasoning aggregation is ideal but infeasible—context windows cannot hold multiple full IS trajectories simultaneously; (3) truncated aggregation (e.g., Qiao et al., 2025, which aggregates only the last few reasoning steps) compromises by keeping some reasoning context at the cost of discarding earlier planning and decomposition content. The paper's position is that this tradeoff is unnecessary: the redundancy inherent in IS trajectories (Section 2.2, Figure 2) means the essential reasoning information—which entities were discovered, how they relate, what sub-problems were solved—can be represented far more compactly than the raw trajectory. The paper formalizes this through the information state graph concept (Equation 2): an IS task is fundamentally about building a graph of discovered entities and their relations, and this graph is typically much smaller than the trajectory used to construct it. By extracting and representing this graph explicitly (as a structured report), the aggregation stage can consider the full reasoning of all candidates simultaneously without exceeding context limits. This reframes the problem: the bottleneck is not context capacity per se, but the inefficiency of raw trajectory representation.

IS agent design has focused on single-trajectory capability, not multi-trajectory synthesis. The paper lists extensive prior work on building capable IS agents—both proprietary (OpenAI DeepResearch, Kimi Researcher, Claude 4, Perplexity) and open-source (WebSailor, WebDancer, WebExplorer, DeepDive, and many others)—but notes that these efforts focus on improving the quality of individual trajectories through better training, more sophisticated search strategies, or improved reasoning architectures. The parallel thinking paradigm (generating multiple trajectories and synthesizing them) has been explored primarily in pure reasoning contexts and has not been systematically adapted to the unique properties of IS trajectories. The paper positions PARALLELMUSE as filling this specific gap: not proposing a new single-trajectory IS agent, but rather a wrapper framework that can be applied to existing IS agents to enable effective parallel thinking.

How This Paper Positions Itself

The paper's positioning can be understood through several key intellectual moves:

It treats IS-specific trajectory properties as design opportunities, not obstacles. Rather than viewing long trajectories and hybrid token types as problems to work around, the paper conducts pilot studies (Section 2) to characterize these properties quantitatively and then designs methods that exploit them. The functional distinction between reasoning and exploration tokens becomes the basis for targeted branching in partial rollout (Section 3.1). The entity-level redundancy of IS trajectories becomes the basis for lossless compression in reasoning aggregation (Section 3.2). This is fundamentally different from approaches that try to make IS agents fit the mold of pure-reasoning parallel thinking—it instead adapts the parallel thinking paradigm to IS-specific structure.

It provides an end-to-end two-stage framework, not isolated components. The paper argues that efficient exploration (Stage 1) and effective aggregation (Stage 2) are coupled: better exploration produces more diverse and higher-quality trajectories, but this benefit is only realized if the aggregation stage can fully utilize the reasoning content within those trajectories. Conversely, an aggregation method that can process compressed representations of full reasoning removes the pressure to keep trajectories short or to prune branches early, enabling more aggressive exploration. By designing both stages together and evaluating them jointly (Table 2), the paper demonstrates that the whole exceeds the sum of its parts. The ablation studies (Section 4.3 on partial rollout alone, Section 4.4 on aggregation alone) isolate each component's contribution, but the main results emphasize the combined system.

It is model-agnostic and benchmark-diverse. The paper evaluates four agent models spanning 20B to 671B parameters and three model families (GPT-OSS, DeepSeek, Tongyi), and four benchmarks that test different capability profiles (BrowseComp emphasizes deep search, HLE emphasizes reasoning, GAIA is balanced, BrowseComp-zh adds a Chinese-language dimension). The consistent gains across this matrix (Table 2) provide evidence that the framework addresses fundamental properties of IS tasks rather than exploiting quirks of a particular model or benchmark. This is important because IS agent behavior varies substantially across model scales and training approaches—a method that works on one model but not others would have limited practical value. The paper also demonstrates that when applied to the strongest open-source model (Tongyi-DR-30B-A3B), PARALLELMUSE achieves performance "comparable to or surpassing that of most closed-source agents" (Section 4.2), providing a concrete upper bound on what the framework can achieve given a capable base agent.

It explicitly connects efficiency and effectiveness, not trading one for the other. The paper emphasizes in Section 4.5 that PARALLELMUSE "is not a conventional test-time scaling strategy that improves performance by aggressively sacrificing efficiency." The 10–30% token reduction from partial rollout (via KV-cache prefix reuse) and the ~99% context compression from trajectory summarization mean that the framework reduces cost while improving quality—a "better and cheaper" result that is rare in test-time scaling. This positions PARALLELMUSE as a practical deployment strategy, not just an academic demonstration of what's possible with unlimited compute. The theoretical backing for the efficiency claims (Equations 4–6, deriving speedup from KV reuse and asynchronous parallelization) adds precision to what might otherwise be hand-wavy claims about efficiency gains.

The conceptual contribution is the functional-region-aware view of agentic uncertainty. While the specific methods (partial rollout, trajectory compression) have precedents in adjacent literatures, the paper's central insight is that what counts as "uncertainty" depends on what functional role a token plays in the agent's overall process. Exploration uncertainty (what should I search for?) and reasoning uncertainty (how should I interpret what I found?) are different signals that should trigger different responses. Prior work treats them as interchangeable because it operates in domains where all tokens serve the same function (pure reasoning). By demonstrating empirically that these uncertainties have different temporal dynamics (Figure 1) and different implications for branching strategy (Table 3), the paper provides both the conceptual framework and the empirical evidence needed to justify functional-region-specific parallel thinking. This insight likely generalizes beyond the specific methods proposed and could inform future work on adaptive computation in agentic systems.

3. Technical Approach

3.1 Reader Orientation

This paper proposes PARALLELMUSE, a two-stage wrapper framework that can be applied to any existing deep information-seeking (IS) agent to make its use of parallel thinking—generating multiple reasoning trajectories and synthesizing them into one answer—simultaneously more effective and more efficient. The system solves the coupled problems of (1) wasteful redundant computation when resampling entire long-horizon IS trajectories from scratch, and (2) context-limited answer aggregation that either ignores the reasoning process or exceeds the model's capacity window, by exploiting two IS-specific properties: functional regions (reasoning vs. exploration tokens) have distinct uncertainty dynamics that enable targeted branching, and IS trajectories are highly redundant at the entity level, enabling lossless compression before aggregation.

3.2 Big-Picture Architecture (Diagram in Words)

The system wraps an existing IS agent and operates in two sequential stages after receiving the user's query:

Stage 1 — Functionality-Specified Partial Rollout (exploratory sampling): Given a sampling budget $N$ (total number of trajectories to generate), the framework first produces $M$ initial complete trajectories from scratch (where $M$ is small, default $M=1$ ). It then analyzes these initial trajectories to identify which steps have high exploration potential—but critically, it measures uncertainty separately for reasoning steps and exploration (tool-call) steps, recognizing that these functional regions exhibit different uncertainty dynamics (per Section 2.1 observations). The top- $k$ highest-uncertainty steps in the chosen functional region(s) become branching points. From each branching point, the framework launches additional partial rollouts (up to the remaining budget $N-M$ ) that reuse the shared prefix via KV-cache rather than regenerating it from scratch. Branch generation is parallelized asynchronously. The output is $N$ complete trajectories, some sharing prefixes with others.
Stage 2 — Compressed Reasoning Aggregation (answer generation): Each of the $N$ trajectories is compressed into a structured report that preserves only information relevant to answer derivation: (i) solution planning (problem decomposition, dependency structure), (ii) solution methods (tools used, parameters, sub-answers), and (iii) final reasoning (how sub-answers integrate into the final answer). This compression exploits the observation from Section 2.2 that IS trajectories are ~90%+ redundant at the entity level—most discovered entities don't contribute to the final answer. All $N$ compressed reports are then jointly fed to a language model (the same agent model or a stronger one) that synthesizes a final answer by evaluating reasoning coherence across reports, explicitly avoiding majority-answer bias and avoiding any additional tool calls.

Information flows: user query → Stage 1 (initial rollouts → functional-region uncertainty analysis → branching point selection → asynchronous partial rollouts with KV reuse → $N$ complete trajectories) → Stage 2 (per-trajectory compression to structured reports → joint aggregation across all reports → final answer).

3.3 Roadmap for the Deep Dive

First, the formal definitions of functional regions ( $T^r$ , $T^e$ ) and step-level perplexity within each region (Equation 1), since the branching mechanism in Stage 1 depends on computing these separately and the whole functional-region distinction is the paper's key conceptual innovation.
Second, the Functionality-Specified Partial Rollout method in full detail: how branching steps are identified, how the functional region $f$ is chosen, how partial rollouts reuse KV caches, the asynchronous parallelization engine, and the theoretical efficiency analysis (Equations 4–6) that quantifies why this approach is faster.
Third, the Compressed Reasoning Aggregation method: the formalization of IS tasks as entity-relation graph construction (Equation 2) and redundancy measurement (Equation 3), the structure and content of the compressed reports, and the reasoning-guided aggregation procedure that operates over compressed representations rather than raw trajectories.
Fourth, the hyperparameter configuration (Table 1) and how choices like $M$ , $k$ , and functional region $f$ are set and tuned, since these control the exploration–exploitation tradeoff.
Fifth, design choices and their justifications: why functional-region-aware uncertainty, why lossless compression via structured reports, why no tool calls during aggregation, why asynchronous parallelization, and how these choices connect to the pilot observations.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a methods paper with extensive empirical validation whose core idea is that deep IS agents have two exploitable properties—functionally distinct token regions with different uncertainty dynamics, and high entity-level redundancy in trajectories—that enable a two-stage parallel thinking framework achieving better performance with less computation than conventional from-scratch parallel rollouts.

Functional Region Definition and Step-Level Perplexity (Equation 1)

The entire framework rests on the observation that tokens generated by a deep IS agent fall into two functionally distinct categories, which the paper treats as a formal partition of the generated sequence. Understanding this partition and how uncertainty is measured within each region is prerequisite to understanding how Stage 1 selects branching points.

The functional partition. At each step $t$ of the agent's execution, the model generates a sequence of tokens $T_t = \{x_{t,1}, x_{t,2}, ..., x_{t,m}\}$ . The paper partitions this set into two disjoint subsets:

$T^r_t$ : reasoning tokens — the model's internal deliberation, typically delimited by special tokens like <thinking> and </thinking> in the ReAct paradigm. These tokens represent the agent's analysis of what it knows, what it needs to find out, and how it plans to proceed.
$T^e_t$ : exploration tokens — the tool invocations (function calls) that the model issues, typically delimited by <tool_call> and </tool_call> tags. These tokens represent actions to retrieve external information (search queries, page visits).

The partition satisfies $T^r_t \cup T^e_t = T_t$ (every token belongs to one region) and $T^r_t \cap T^e_t = \emptyset$ (no token belongs to both). Aggregating across all steps of a trajectory yields global sets $T$ , $T^r$ , and $T^e$ . The paper contrasts this with pure reasoning tasks where $T^e = \emptyset$ and thus $T = T^r$ —the entire generation is homogeneous, and uncertainty over any token is uncertainty about the same type of cognitive operation.

Why this partition matters for parallel thinking. The paper's key conceptual move is arguing that uncertainty means different things in different functional regions. High uncertainty in the reasoning region suggests the agent is struggling to integrate information—it has multiple plausible interpretations of what it knows and is unsure which to pursue. Branching here can explore alternative reasoning paths. High uncertainty in the exploration region suggests the agent is unsure what information to retrieve—it doesn't know which search query or which webpage will be most productive. Branching here can explore alternative information-gathering strategies. A method that pools all tokens together (as prior partial rollout work does) cannot distinguish these cases and may branch at exploration steps when reasoning diversity would be more valuable, or vice versa.

Step-level perplexity as uncertainty proxy. The paper uses perplexity (PPL) as a quantitative measure of the model's self-uncertainty at each step, computed separately for each functional region. The definition (Equation 1) is:

$PPL(f, t) = \exp \left( -\frac{1}{|T^f_t|} \sum_{i=0}^{|T^f_t|} \log p(x_{t,i} \mid x_{<t,i}) \right), \quad x_{t,i} \in T^f_t, \quad f \in \{r, e\}$

where $f$ specifies the functional region (either $r$ for reasoning or $e$ for exploration), $t$ is the step index, $|T^f_t|$ is the number of tokens in region $f$ at step $t$ , $p(x_{t,i} \mid x_{<t,i})$ is the model's predicted probability for token $x_{t,i}$ given all preceding tokens $x_{<t,i}$ , and the sum runs over all tokens in the specified region at step $t$ .

What it computes: For each step and each functional region, the equation first computes the average negative log-probability across all tokens within that region at that step—this is the cross-entropy (surprisal) per token. Exponentiating this average yields the perplexity, which can be interpreted as the effective branching factor: a perplexity of $K$ means the model is as uncertain as if it were choosing uniformly among $K$ equally likely alternatives. Higher PPL means the model assigns lower probability to the tokens it actually generated, indicating it considered many alternatives as plausible—hence, more exploration potential at that step.

Why this form: Perplexity is a standard information-theoretic measure that directly captures the flatness of the model's predictive distribution. An alternative would be to use the raw negative log-likelihood, but PPL has the advantage of being interpretable in units of "effective vocabulary size" and is comparable across steps with different numbers of tokens (since it's averaged). The paper computes PPL separately per functional region rather than pooling all tokens because pooling would conflate the different uncertainty dynamics: an exploration step with moderate PPL might actually have higher exploration-specific PPL than a reasoning step with high reasoning PPL, and the framework needs to compare like-with-like when selecting the top- $k$ steps within a chosen functional region.

Connection to pilot observations (Figure 1). The paper's pilot study (Section 2.1) analyzed when PPL peaks for each functional region during task execution. The consistent finding across all tested models was that $PPL(e, t)$ (exploration perplexity) is highest at the very beginning of the task—when the agent has gathered no external information and must formulate initial queries under maximum ignorance—while $PPL(r, t)$ (reasoning perplexity) peaks slightly later, in the early-middle stage, when the agent has received some tool responses and must begin integrating contradictory or incomplete information. By step selection time (Section 3.1), the framework uses these per-region PPL values to choose which functional steps to branch from.

Functionality-Specified Partial Rollout (Stage 1)

This stage transforms the naive "generate $N$ independent trajectories from scratch" procedure into a targeted process that reuses shared computation and concentrates the exploration budget on high-uncertainty steps within the functionally appropriate region. The method has three sub-components: branching step identification, asynchronous partial rollout execution, and the theoretical efficiency model.

Branching Step Identification

The goal is to select, from an initial small set of complete trajectories, a set of steps (each associated with a specific trajectory position) from which to launch additional partial rollouts—branching the exploration tree at points where the model's uncertainty was highest, and doing so within the functional region that is most productive to branch in.

Procedure (offline, meaning completed before any branching rollouts are generated):

Generate $M$ initial trajectories from scratch. The paper's default is $M=1$ (Table 1), meaning only a single complete trajectory is generated before branching decisions are made. (The paper also sweeps other values implicitly through its ablation that reports performance with 8 from-scratch rollouts in Figure 4—the $M=1$ setting is the efficient default.)
Compute per-step, per-region PPL. For each step $t$ of each initial trajectory, compute $PPL(r, t)$ and $PPL(e, t)$ using Equation 1 with the same model that generated the trajectory. This requires access to the model's token-level log-probabilities during generation, which is standard in modern LLM serving frameworks.
Select a functional region $f \in \{r, e\}$ (or a mixed strategy) based on the agent model's characteristics. The paper treats this as a tunable hyperparameter, exploring three strategies in experiments (Table 3): branch based on reasoning uncertainty only ( $f = r$ ), exploration uncertainty only ( $f = e$ ), or a mixed strategy where half the branching steps are selected from each region. The choice is model-dependent because different agent models allocate their cognitive effort differently between reasoning and exploration. For instance, DeepSeek-V3.1-Terminus "employs function calling outside of the thinking mode, resulting in weaker internal reasoning capacity and thus higher sampling potential in reasoning steps" (Section 4.3), making reasoning-region branching more effective for that model.
Select top- $k$ steps. Within the chosen functional region $f$ , sort all steps from all $M$ initial trajectories by $PPL(f, t)$ descending and select the top- $k$ steps with the highest perplexity. The default is $k=2$ (Table 1). These become the branching points.
Multiple branches per step. From each selected branching point, the paper launches multiple partial rollouts—the default is 3 branches per step (Table 1, "#Branching Times per Step"), meaning each of the top- $k$ steps spawns 3 alternative continuations. With $k=2$ and 3 branches per step, this yields 6 additional partial rollouts. Combined with the $M=1$ initial rollout, this uses 7 of the $N=8$ total budget. The remaining budget allocation is implicit: the paper's default $N=8$ budget with $M=1$ , $k=2$ , and 3 branches per step exactly saturates the budget.

Why this procedure works—the exploration-exploitation analogy. The paper draws an explicit analogy to Monte Carlo Tree Search (MCTS) (Browne et al., 2012): while MCTS reuses high-reward trajectories, PARALLELMUSE reuses low-uncertainty (low-exploration-potential) paths and selectively expands exploration at high-uncertainty steps. The intuition is that low-uncertainty steps represent parts of the trajectory where the model is confident—its reasoning is clear, its tool calls are obvious—so regenerating these steps from scratch would almost certainly produce the same or similar output, wasting computation. High-uncertainty steps represent decision points where the model sees multiple plausible alternatives, so branching here has genuine potential to discover different (and possibly better) solution paths.

Why functional-region-specific selection matters. The paper's preliminary experiments with homogeneous (non-functional-region-distinguished) partial rollout—where steps are selected based on overall PPL without distinguishing reasoning from exploration tokens—"performs comparably to full from-scratch rollouts and provides no observable gains from branching at high-uncertainty steps" (Section 4.3 footnote). This directly validates the paper's central claim: in IS tasks, treating all uncertainty as interchangeable fails because high overall PPL might be driven by exploration uncertainty (where branching may just produce different but equally uninformed search queries) rather than reasoning uncertainty (where branching can explore genuinely different analytical approaches given the same retrieved information). The functional region distinction ensures branching targets the right type of uncertainty.

Asynchronous Partial Rollout

Once branching points are identified, the remaining $N-M$ rollouts are generated not from scratch but by reusing the prefix (all tokens before the branching step) and generating only the suffix (all tokens from the branching step onward). This is implemented through KV-cache reuse and asynchronous parallelization.

KV-cache prefix reuse. Modern transformer inference stores key-value (KV) activations at each layer for each token in a cache. When generating a sequence autoregressively, tokens beyond the cached prefix can be generated by feeding only the new tokens through the model while reusing the cached KV states for the prefix—this avoids recomputing attention over the prefix for every new token. In the partial rollout setting, for a branch that starts at step $t$ of an initial trajectory with prefix length $p_j$ (all tokens up to and including the branching step), the framework loads the cached KV states for those $p_j$ tokens and then generates only the suffix of length $s_j$ (the alternative continuation). This eliminates $p_j$ tokens of recomputation per branch compared to a full from-scratch rollout.

Asynchronous parallelization engine. The paper implements "an asynchronous rollout engine to parallelize branch generation while preserving each branch's causal decoding consistency" (Section 3.1). Each branch, once initiated, proceeds autoregressively—each token depends on all preceding tokens in that branch—but multiple branches can be generated concurrently. The engine manages multiple parallel decoding streams, each with its own KV-cache initialized from the shared prefix, and schedules them for simultaneous execution on available compute resources (e.g., multiple GPUs or batched inference on a single GPU). The requirement to "preserve causal decoding consistency" means each branch must be self-consistent (the $i$ -th generated token sees exactly the $i-1$ preceding tokens in its branch), but branches do not need to be synchronized with each other—they can proceed at different speeds.

Theoretical efficiency analysis. The paper provides a formal model (Equations 4–6) quantifying why this approach is faster than from-scratch rollouts. The analysis considers two sources of speedup: computation reuse (avoiding recomputation of shared prefixes) and parallelism (running branches concurrently).

Let branch $j$ reuse a prefix of token length $p_j$ and generate a suffix of token length $s_j$ . Define:

$c$ : per-token compute cost under cached decoding (with KV reuse)—the cost of processing one new token when all previous tokens are already cached.
$c_{\text{cold}}$ : per-token compute cost when regenerating from scratch (without KV reuse)—this is $\geq c$ because attention must be computed over the full prefix for each new token.

The cold decoding cost for branch $j$ would be $C^{\text{cold}}_j = c_{\text{cold}} \cdot (p_j + s_j)$ : all $p_j + s_j$ tokens processed from scratch. The hot (KV-reuse) decoding cost is $C^{\text{hot}}_j = c \cdot s_j$ : only the $s_j$ new suffix tokens are processed; the prefix is already cached.

The ReuseFactor (Equation 4) is the ratio of total cold cost to total hot cost across all branches:

$\text{ReuseFactor} \equiv \frac{\sum_j C^{\text{cold}}_j}{\sum_j C^{\text{hot}}_j} = \frac{c_{\text{cold}}}{c} \left(1 + \frac{\sum_j p_j}{\sum_j s_j}\right)$

where $\sum_j p_j$ is the total prefix length across all branches (summed because each branch reuses a potentially different prefix from the initial trajectories), $\sum_j s_j$ is the total suffix length across all branches, $c_{\text{cold}}/c$ is the cost ratio of cold vs. hot per-token processing, and the term in parentheses captures the token savings from avoiding prefix recomputation.

What it computes: The factor by which total computation is reduced through prefix reuse alone, before considering parallelism. If prefixes are long relative to suffixes ( $\sum_j p_j \gg \sum_j s_j$ ), the reuse factor is large; if suffixes dominate, the factor approaches $c_{\text{cold}}/c \approx 1$ (minimal savings from reuse). In the practical regime assumed by the paper ("efficient KV caching" where $c \approx c_{\text{cold}}$ ), this simplifies to $\text{ReuseFactor} \approx 1 + \sum_j p_j / \sum_j s_j$ .

Parallelism speedup (Equation 5). The second source of speedup comes from running $P$ active branches concurrently. Using Amdahl's Law, the speedup from parallelism is bounded by:

$\text{ParaFactor}(P) \leq \frac{1}{(1 - \alpha) + \alpha / P}$

where $\alpha \in [0, 1]$ is the parallelizable ratio—the fraction of the hot decoding work that can be executed in parallel across branches—and $P$ is the number of concurrent branches. The $(1-\alpha)$ term represents the inherently sequential portion of the work, and $\alpha/P$ represents the parallelizable work distributed across $P$ processors.

Combined speedup (Equation 6). The overall speedup is the product of the reuse and parallelism factors:

$\text{Speedup}_{\text{total}} \lesssim \text{ReuseFactor} \times \text{ParaFactor}(P)$

In the practical regime with $c \approx c_{\text{cold}}$ (efficient KV caching where recomputing a prefix is not significantly more expensive per-token than processing a new token from cache), high parallelizability ( $\alpha \approx 1$ , meaning almost all the hot decoding work can be parallelized), and $P$ within hardware concurrency limits, this simplifies to the clean form:

$\text{Speedup}_{\text{total}} \approx \left(1 + \frac{\sum_j p_j}{\sum_j s_j}\right) P$

Why this form—the design implications. The speedup expression reveals two independent levers: (1) make prefixes long relative to suffixes (increase the reuse factor by branching late in trajectories, where most of the work is already done in the shared prefix), and (2) maximize parallel branch execution (increase $P$ up to hardware limits). The first lever is controlled by the branching step selection—branching at later steps means larger $p_j$ and smaller $s_j$ , hence higher reuse. The second lever is controlled by the asynchronous rollout engine. The paper's empirical result of "up to 28% token savings" (Figure 5, Left) provides a concrete measurement of the reuse factor in practice, while the asynchronous engine ensures that generating $N-M$ additional branches adds sub-linear wall-clock time to the initial $M$ from-scratch rollouts.

Why this approach over beam search or tree search: The paper explicitly contrasts partial rollout with structured search methods like MCTS. In pure reasoning tasks, tree search with a value function (e.g., a process reward model) can prune low-quality branches and expand high-quality ones. But in IS tasks, there is no reliable step-level value function—the quality of a search query or a page visit can only be assessed retrospectively based on whether it led to useful information, which requires actually executing the tool call and processing the response. Partial rollout with uncertainty-guided branching avoids the need for a value function altogether: it branches where the model itself is uncertain, which is a signal that can be computed directly from the model's own log-probabilities without any external verifier. This is a crucial practical advantage in IS settings where training a reliable verifier (analogous to the math-domain PRM in the reference paper) would be extremely difficult due to the open-ended nature of web exploration.

Information State Graph and Trajectory Redundancy (Equations 2–3)

Before describing the compression and aggregation methods in Stage 2, the paper formalizes the IS task in a way that justifies why compression is both possible and near-lossless. This formalization is the theoretical foundation for the entire second stage.

Entity-relation graph formulation (Equation 2). The paper models a deep IS task as the process of constructing a graph of discovered entities and their relationships. Formally, given an initial query $q$ , the agent incrementally builds:

$G_t = (V_t, R_t)$

where $V_t = \{v_1, v_2, \ldots, v_{N_t}\}$ is the set of effective entities at step $t$ —entities that the agent has identified as relevant and potentially useful for deriving the answer—and $R_t \subseteq V_t \times V_t$ represents the relations (connections, dependencies, comparisons) that the agent has established among these entities. The agent evolves this graph through iterative environmental interaction: at each step, it explores the web (searching, visiting pages) to discover candidate entities, reasons about their relevance, and adds to $V_t$ and $R_t$ those it deems useful.

The task goal is to refine $G_t$ until it contains the information necessary for answer derivation. Let $I_{\text{answer}}$ denote the set of all information essential for deriving the final answer. When the agent's reasoning process terminates, the final graph $G_{\text{final}}$ must satisfy $G_{\text{final}} \supseteq I_{\text{answer}}$ —it must contain at least everything needed for the answer, though it may also contain additional (redundant) information that was explored but not ultimately used.

What this formulation captures: The graph $G$ is an abstraction of the agent's information state—what it knows and how those pieces of knowledge relate to each other. The trajectory (the raw sequence of thinking, tool calls, and tool responses) is the process by which the graph is constructed, but the graph itself is typically much smaller than the trajectory. A single entity might be mentioned in dozens of trajectory steps (discovered in step 3, revisited in step 7, compared with another entity in step 12, cited in the final answer in step 20), but it appears only once in $V_{\text{final}}$ . A relation might be established through a multi-step reasoning chain, but in $R_{\text{final}}$ it is just a single edge.

Why graph representation enables compression: The key insight is that for answer aggregation, what matters is $G_{\text{final}}$ —the information state at the end of the trajectory—not the sequence of operations that produced it. If two trajectories arrive at similar final graphs, they should receive similar weight in aggregation regardless of how efficiently they got there. Conversely, a trajectory that built a more comprehensive or better-connected graph should be favored even if its final answer text differs from the majority. This reframes the aggregation problem: instead of comparing raw trajectories or final answers, compare the compressed information state graphs.

Redundancy ratio definition (Equation 3). To quantify how much of a trajectory is compressible, the paper defines a redundancy ratio $\Gamma_{\text{red}}$ based on the entity-level view:

$\Gamma_{\text{red}} = 1 - \frac{|V_{\text{eff}}|}{|V_{\text{total}}|}$

where $V_{\text{total}}$ is the set of all entities explored by the agent during the entire task execution—every entity mentioned in any tool response, reasoning step, or intermediate note—and $V_{\text{eff}} \subseteq V_{\text{total}}$ is the subset of entities that are directly or indirectly useful for deriving the final answer.

What it computes: The fraction of total discovered entities that are not useful for the final answer. $\Gamma_{\text{red}} = 0.9$ means 90% of entities explored were irrelevant to the answer—the agent wandered through many web pages, considered many facts, but only 10% of the entities it encountered ended up mattering. $\Gamma_{\text{red}} = 0$ would mean every entity contributed to the answer (no wasted exploration).

Why this metric matters: $\Gamma_{\text{red}}$ serves as an approximate indicator of lossless compressibility. A trajectory with high $\Gamma_{\text{red}}$ can be compressed aggressively by keeping only $V_{\text{eff}}$ and $R_{\text{final}}$ and discarding the rest—the discarded content was, by definition, not used in the answer derivation, so removing it does not lose any information needed to reconstruct or evaluate the answer. The paper's pilot analysis (Figure 2) shows that across all tested models, $\Gamma_{\text{red}}$ is consistently high: GPT-OSS-120B explores an average of 103.4 entities per BrowseComp task but only 6.8 are effective ( $\Gamma_{\text{red}} = 0.934$ ), and similar patterns hold for other models and benchmarks (91.7% to 94.0% redundancy on BrowseComp, 79.2% to 82.4% on GAIA). This empirical finding directly justifies the compression stage: if 90%+ of explored entities are irrelevant, a compressed representation can be ~10× smaller while preserving all answer-relevant information.

Why entity-counting is used as the granularity: The paper acknowledges this is an approximation—not all entities carry equal information, and some discarded entities might have been necessary stepping stones even if they don't appear in $G_{\text{final}}$ . However, entity count provides a simple, interpretable, and automatable metric (entities can be extracted by a language model like GPT-4.1, as the paper does) that captures the key qualitative phenomenon: IS trajectories are long because agents explore broadly, but only a small fraction of that exploration directly contributes to the answer. The compression method (described next) operates at a finer granularity than entity counting—it preserves reasoning structure, sub-answers, and dependency relationships—but the entity-level analysis provides the conceptual foundation for why compression is possible without information loss.

Compressed Reasoning Aggregation (Stage 2)

This stage transforms the $N$ complete trajectories from Stage 1 into a single final answer by (1) compressing each trajectory into a structured report that preserves only answer-relevant information, and (2) aggregating across all reports by evaluating reasoning coherence rather than answer frequency.

Structured Report-Style Compression

Each trajectory from Stage 1 is independently compressed by the agent model (or a stronger model, per Section 4.6) into a structured report. The compression objective is to produce a representation that preserves everything needed to reconstruct and evaluate the trajectory's answer derivation while discarding all redundant exploration content.

Report structure (three required sections):

Solution Planning: Describes how the main problem was decomposed into subproblems, including their dependency structure (which subproblem must be solved before which other) and execution order. For example, for a question about the economic impacts of an earthquake on a specific industry: "First, identify the timeline and magnitude of the earthquake. Second, find data on the textile industry in the affected region before and after the earthquake. Third, identify specific impact channels (factory damage, supply chain disruption, labor displacement)..."
Solution Methods: Specifies the tools invoked to solve each subproblem (e.g., "Used Search to query '2023 Türkiye earthquake textile industry damage statistics'"), the corresponding parameters used in those tool calls, and any subanswers that contribute directly or indirectly to the final solution (e.g., "Search returned a report indicating 2,400 textile factories were damaged, with estimated losses of $1.2B"). This section captures the evidentiary basis for the answer—what was found and from where.
Final Reasoning: Illustrates how the identified subproblems and associated subanswers are integrated to derive the final answer. This is the logical bridge from evidence to conclusion: "Combining the factory damage estimate (2,400 factories) with pre-earthquake employment data (textile sector employed 1.2M people) and export figures ($12B annually), we estimate a 15-20% reduction in textile exports..."

What is removed: All content that does not contribute to any of these three sections—redundant tool responses that were superseded by later, more informative responses; ineffective reasoning paths that were explored but abandoned; search queries that returned no useful results; page visits that turned out to be irrelevant; and any other exploratory dead ends. This is exactly the $|V_{\text{total}}| - |V_{\text{eff}}|$ entities captured by the redundancy ratio $\Gamma_{\text{red}}$ .

Why this structure reconstructs $G_{\text{final}}$ : The three sections directly correspond to the components of the information state graph defined in Equation 2. Solution Planning describes the overall graph structure (what subgraphs exist and how they relate). Solution Methods populates the entity set $V_{\text{final}}$ (the discovered subanswers and their provenance) and the relation set $R_{\text{final}}$ (which entities depend on which tools and parameters). Final Reasoning describes how the edges in $R_{\text{final}}$ form a path from evidence to conclusion. Together, the three sections capture $G_{\text{final}} \supseteq I_{\text{answer}}$ —all information essential for answer derivation, and nothing beyond it.

Compression as lossless with respect to answer evaluation: The paper emphasizes that the compression is lossless specifically with respect to answer derivation—not with respect to reproducing the original trajectory. A human (or LLM) reading the compressed report should be able to understand exactly how the answer was arrived at, what evidence supports it, and whether the reasoning is coherent. Information that was explored but not used is irrelevant for this evaluation task, so removing it loses nothing that matters. This is a critical distinction: the compression is not a "summarization" that might introduce errors or omit crucial details; it is a structured extraction that keeps everything that contributed to the answer and removes only what demonstrably did not.

Empirical compression ratio: Figure 5 (Right) shows that compression "reduces context token usage by up to 99% relative to the full trajectory, achieving an almost complete compression." This is consistent with the entity-level redundancy analysis ( $\Gamma_{\text{red}} \approx 90-94\%$ on BrowseComp): if 93% of entities are irrelevant, and the trajectory text is roughly proportional to the number of entities discussed, a 99% token reduction indicates the compression is slightly more aggressive than entity-level filtering alone (perhaps because entities are described more verbosely in raw trajectories than in structured reports).

Reasoning-Guided Answer Aggregation

After all $N$ trajectories are compressed, the aggregation stage takes all $N$ compressed reports as input to a language model (the same agent model used for Stage 1, or optionally a stronger model as explored in Section 4.6) and produces a single final answer.

Key design constraints enforced in the aggregation prompt:

Explicitly prevent answer-consistency bias. The prompt instructs the model not to "rely solely on answer consistency as a correctness signal" (Section 3.2). This directly counters the majority-voting heuristic: if 6 out of 8 reports conclude "Answer X" and 2 conclude "Answer Y", the model should not default to X. Instead, it must evaluate which answer is better supported by the reasoning and evidence in the reports, even if that answer is in the minority. This constraint addresses the paper's observation that "in complex agentic tasks with vast sampling spaces, the correct answer may not dominate numerically."
Preserve aggregation validity. The model is restricted from "trivially concatenating or enumerating different answers" (Section 3.2). This prevents degenerate outputs like "Reports 1-4 say X, Reports 5-6 say Y, Reports 7-8 say Z, so the answers are X, Y, and Z." The model must commit to a single, coherent answer that synthesizes the strongest reasoning across reports.
No additional tool invocations. The model "does not perform additional tool invocations for secondary verification but instead conducts reasoning purely over the information encoded in the $N$ reports" (Section 3.2). This is justified because each report already contains "sufficient tool-calling provenance and attribution information for answer derivation"—the report records what tools were called, what they returned, and how those results fed into the answer, so the aggregator has the evidentiary trail without needing to re-execute any searches. Avoiding tool calls during aggregation is also practically important: tool interactions are the dominant cost in IS agent operation, and re-searching during aggregation would undermine the efficiency gains from compression.

What the aggregation model actually does: Given $N$ structured reports (each containing planning, methods, and reasoning), the model must:

Identify which reports arrive at consistent or contradictory conclusions.
Evaluate the reasoning coherence of each report: does the evidence presented in the Solution Methods section actually support the conclusion drawn in the Final Reasoning section? Are there logical gaps, unsupported leaps, or contradictions?
Assess the quality and comprehensiveness of each report's information gathering: did the agent explore the right sources? Did it miss important subproblems?
Synthesize a final answer that reflects the strongest evidential and reasoning basis across all reports, which may involve adopting a minority report's conclusion if its reasoning is superior, or synthesizing elements from multiple reports into a novel answer not present in any single trajectory.

Why this approach mitigates the failures of answer selection methods:

Majority voting fails when the correct answer is rare—it doesn't matter if 7/8 trajectories arrive at a wrong answer through similar faulty reasoning; majority voting mechanically selects the wrong answer. The aggregation stage, by evaluating reasoning quality rather than answer frequency, can recognize that the 1/8 trajectory with the correct answer has sound reasoning while the 7/8 had a shared flaw.
Confidence-weighted voting fails because model confidence is miscalibrated in IS settings—the model may be overconfident about an answer derived from bad information. The aggregation stage uses external evaluation (comparing reports, checking reasoning coherence) rather than internal confidence signals.
Truncated reasoning aggregation (e.g., using only the last few steps) fails because it misses the planning and evidence-gathering context. The compressed reports preserve exactly this context—the "planning" and "methods" sections capture the upstream information that the "final reasoning" section depends on.

The model capability scaling property (Section 4.6): A practically important design choice is that the compression and aggregation model can be different from the exploration model. Table 4 shows that using a stronger model for aggregation (e.g., GPT-5 aggregating rollouts from GPT-OSS-20B) yields further performance gains. The paper interprets this as evidence that the compressed reports effectively represent the agent's internal information state graph $G$ , and that "higher-quality graph reconstruction enhances overall performance." This has implications for multi-agent system design: a fleet of cheaper, faster agents can handle the expensive exploration (Stage 1), while a single more capable agent handles the cheaper but more cognitively demanding aggregation (Stage 2). Since aggregation operates over already-compressed reports (small context) and doesn't require tool calls, using a larger model here adds modest cost relative to the exploration budget.

Hyperparameter Configuration and Tuning

The paper's default configuration (Table 1) represents a specific operating point in the exploration–exploitation tradeoff space. Understanding these choices and their implications is essential for reproducing or adapting the method.

Hyperparameter	Default Value	Role
Sampling Budget $N$	8	Total number of trajectories to generate (initial + branched)
Number of Initial Rollouts $M$	1	How many complete trajectories are generated before branching decisions
Branching PPL Top- $k$	2	How many high-uncertainty steps are selected as branching points
Number of Branching Times per Step	3	How many alternative continuations are generated from each branching point

The $N=8$ budget choice. This is modest compared to typical parallel thinking budgets in pure reasoning (where best-of-64 or best-of-256 are common), reflecting the much higher per-trajectory cost in IS tasks. A single IS trajectory on BrowseComp might involve 20–50 tool calls and tens of thousands of tokens; 8 trajectories is already a substantial compute investment. The paper's choice to demonstrate 62% improvement at this budget level makes the practical value proposition clear: the gains come not from brute-force scaling but from smarter allocation of a fixed, realistic budget.

The $M=1$ initial rollout choice. Using only a single initial trajectory means the branching point selection is based on a single sample of the agent's behavior. This is efficient but potentially noisy—the PPL peaks in that one trajectory might not be representative of where the agent generally experiences uncertainty. The paper implicitly accepts this noise in exchange for efficiency (using $M>1$ would consume more of the budget on initial exploration, leaving less for branching). The fact that the method works well with $M=1$ suggests that PPL peaks are somewhat consistent across trajectories for the same task (i.e., certain steps are genuinely harder decision points regardless of the specific path taken), which is consistent with the pilot observation that exploration uncertainty peaks at the beginning and reasoning uncertainty peaks in early-middle stages—these are structural properties of the task, not random variation.

The $k=2$ top-K choice. Selecting only 2 branching points from all steps in the initial trajectory means the method is highly selective—only the most uncertain steps get expanded. This concentrates the exploration budget on the points with the highest expected information gain. A larger $k$ would spread branches more thinly (with fewer branches per step given the fixed budget), potentially diluting the exploration benefit.

The 3 branches per step choice. With $k=2$ and 3 branches per step, that's 6 partial rollouts plus the initial trajectory, totaling 7—just under the $N=8$ budget. The paper doesn't elaborate on the remaining budget allocation, but the structure suggests some flexibility in how branches are distributed.

The functional region $f$ choice as a model-dependent hyperparameter. Table 3 shows that the optimal functional region for branching varies across models: GPT-OSS-120B benefits most from exploration-region branching (39.9 on BrowseComp vs. 37.9 for reasoning-region), while DeepSeek-V3.1-T benefits most from reasoning-region branching (26.5 vs. 23.8 for exploration-region). The paper attributes this to model architecture and training differences: GPT-OSS-120B has "strong adaptive reasoning mechanisms" that already produce high-quality reasoning with limited exploration potential from branching there—the model is already good at reasoning, so the uncertainty is mostly about what to search for. DeepSeek-V3.1-T uses function calling "outside of the thinking mode," meaning its reasoning is less deeply integrated with its tool use, creating higher sampling potential in reasoning steps. This implies that deploying PARALLELMUSE with a new agent model requires a calibration step: run initial experiments with each functional region setting on a validation set to determine which strategy works best for that model's architecture and training.

Design Choices and Their Justifications

Several non-obvious design decisions underlie the framework's effectiveness. Understanding why these choices were made—and what alternatives were rejected—clarifies the paper's intellectual contribution.

Why functional-region-aware uncertainty instead of a unified uncertainty metric? The most fundamental design choice is the rejection of token-homogeneous partial rollout. The paper's preliminary experiments showed that branching based on overall PPL (without distinguishing reasoning from exploration tokens) "performs comparably to full from-scratch rollouts and provides no observable gains" (Section 4.3 footnote). The reason, which the paper's pilot observations support, is that overall PPL is dominated by whichever functional region has higher variance, which may not be the region where branching is productive. If exploration PPL is naturally higher than reasoning PPL (as Figure 1 suggests for early steps), then homogeneous branching would always select exploration steps as branching points, missing opportunities to branch at reasoning steps where the model is genuinely uncertain about how to interpret information. The separate computation of $PPL(r, t)$ and $PPL(e, t)$ and the explicit choice of which region to branch from ensure that the exploration budget is allocated to the type of uncertainty that the specific model most needs help with.

Why structured reports instead of extractive compression or embeddings? The compression format is a deliberate choice to preserve explainability and evaluability. Extractive compression (e.g., selecting the top- $K$ most important sentences from the trajectory) might be more efficient but would lose the structured relationships that matter for evaluation—knowing that entity A and entity B were both mentioned doesn't capture how they relate. Embedding-based compression would lose interpretability entirely—the aggregation model couldn't trace an answer back to specific evidence. The structured report format (planning, methods, reasoning) maps directly to the information state graph $G$ and enables the aggregation model to evaluate reasoning coherence by checking whether the planning covers all necessary subproblems, whether the methods section provides evidence for each planning element, and whether the reasoning section logically connects evidence to conclusion. This structure also makes the compression lossless in the specific sense the paper claims: if the report captures exactly the entities and relations in $G_{\text{final}}$ , and $G_{\text{final}} \supseteq I_{\text{answer}}$ , then no answer-relevant information is lost.

Why no tool calls during aggregation? The constraint that aggregation must reason "purely over the information encoded in the $N$ reports" without additional tool invocations serves two purposes. First, it enforces efficiency: the aggregation stage processes compressed reports that are each ~1% of the original trajectory size, avoiding the dominant cost driver (tool interactions) entirely. Second, it enforces epistemic honesty: the aggregation model must evaluate which answer is best given the evidence that was actually collected during exploration, not go searching for additional evidence that might tip the balance. This prevents the aggregation from becoming a second round of research that could introduce its own biases and errors.

Why asynchronous parallelization instead of batched synchronous decoding? The asynchronous rollout engine allows branches to proceed at different speeds—a branch that finishes early (e.g., because it discovers a dead end or converges quickly) doesn't block other branches. In a synchronous scheme, all branches would need to complete their current step before any can proceed to the next, creating idle time when some branches are faster than others. The cost of asynchrony is added complexity in managing multiple independent KV-caches and decoding streams, but the paper argues this is justified by the throughput gains (quantified in Equations 5–6).

Why $M=1$ and not $M>1$ for initial rollouts? Using a single initial trajectory maximizes the budget available for branching but risks selecting unrepresentative branching points. The paper implicitly bets that PPL peaks are task-structural rather than trajectory-idiosyncratic—in other words, that for a given query, most trajectories will show high uncertainty at roughly the same steps (early exploration, early-middle reasoning), so a single initial trajectory is sufficient to identify these. The pilot observations in Figure 1 (which aggregate across many trajectories per model) support this: the distributions of high-uncertainty steps show consistent patterns (exploration uncertainty peaks at the beginning, reasoning uncertainty slightly later) rather than random scatter. If PPL peaks were highly trajectory-specific, $M=1$ would be insufficient and the method would fail—the fact that it works suggests the structural interpretation is correct.

Why entity-level redundancy as the compression justification instead of token-level redundancy? The paper could have measured redundancy by token compression ratio (how many tokens in the raw trajectory vs. the compressed report). Instead, it uses entity-level redundancy ( $\Gamma_{\text{red}}$ , Equation 3). The entity-level perspective is more informative because it explains why compression is possible: the agent explores many entities that turn out to be irrelevant. This provides a causal story (agents over-explore; the effective entities are a small subset) that token-level compression ratios alone wouldn't—a 99% token reduction could be achieved by aggressive summarization that loses information, but the entity-level analysis shows the reduction preserves all effective entities, establishing losslessness.

4. Key Insights and Innovations

Innovation 1: Functional-Region-Aware Uncertainty as a Diagnostic for Agentic Branching

The field's default assumption in partial rollout and tree-search methods for LLMs has been token-homogeneous uncertainty: all tokens contribute equally to exploration potential, so branching decisions should be based on a single perplexity or confidence score computed over the entire generation (Hou et al., 2025; Dong et al., 2025; Li et al., 2025e). This assumption is natural in pure reasoning domains—mathematics, coding—where every token the model generates serves the same cognitive function (advancing a chain of deductive logic). The paper's foundational conceptual move is to reject this homogeneity assumption for information-seeking agents and replace it with a functional-region-aware view of uncertainty.

What makes this distinctive at the idea level is not the mechanism of computing per-step (already in existing partial rollout work) but the diagnostic insight that uncertainty means fundamentally different things depending on which functional role the uncertain tokens serve. Exploration uncertainty (where should I search? what query should I issue?) reflects the agent's ignorance about the external information landscape—a problem that branching can genuinely help with because different search strategies may discover different information. Reasoning uncertainty (how should I interpret what I found? what conclusion follows?) reflects the agent's difficulty synthesizing information it already possesses—a problem where branching may be productive (exploring alternative analytical frameworks) or may simply produce different ways of being confused if the underlying information is insufficient.

The paper's pilot observations (Figure 1) provide empirical teeth to this distinction: across multiple models, exploration uncertainty peaks at the earliest stages (before any information is gathered), while reasoning uncertainty peaks slightly later (during early integration of retrieved information). These are not random co-fluctuations of a single uncertainty signal—they are structurally different temporal patterns reflecting different cognitive bottlenecks. A unified uncertainty metric would obscure this structure, potentially directing branches toward exploration steps when reasoning diversity is what's needed, or vice versa.

The practical significance of this reframing is demonstrated in the paper's negative result (Section 4.3 footnote): homogeneous partial rollout—branching based on overall PPL without functional-region distinction—"performs comparably to full from-scratch rollouts and provides no observable gains from branching at high-uncertainty steps." This is a clean ablation: the functional-region distinction is not a minor improvement on existing partial rollout; it is what makes partial rollout work at all in IS settings. Without it, the method collapses to the performance of the naive baseline.

The innovation also has implications beyond this specific method. It establishes that agent architectures that partition generation into functionally distinct phases create exploitable structure for test-time compute allocation—a principle that could inform future work on adaptive computation in any system where different generation phases have different uncertainty characteristics. The fact that the optimal functional region for branching is model-dependent (Table 3: exploration-region branching works best for GPT-OSS-120B, reasoning-region branching for DeepSeek-V3.1-T) further suggests that functional-region uncertainty profiling could serve as a diagnostic tool for understanding where different agent architectures experience their primary bottlenecks—a kind of "uncertainty fingerprint" for agent models.

This is a fundamental conceptual reframing, not an incremental refinement. Prior partial rollout work treated uncertainty as a scalar property of a generation position; this paper treats uncertainty as a vector with functional dimensions, and shows that collapsing those dimensions (as prior work implicitly does) eliminates the benefits of targeted exploration in agentic settings.

Innovation 2: Information-State Graph as the Theoretical Basis for Lossless Trajectory Compression

Answer aggregation in parallel thinking faces a well-known dilemma: either consider only final answers (efficient but discards reasoning quality signals) or consider full reasoning traces (informative but exceeds context capacity). Prior work has navigated this tradeoff through compromise—aggregating truncated reasoning traces (Qiao et al., 2025, using only the last few steps) or ensembling at the answer level with confidence weights (Fu et al., 2025; Wang et al., 2022). The paper's second major conceptual move is to reject the premise that this tradeoff is necessary by formalizing IS tasks as entity-relation graph construction and showing that IS trajectories are highly redundant with respect to this graph representation.

The key insight is Equation 2 and the surrounding formalization: an IS task can be understood as the process of building $G_t = (V_t, R_t)$ —a graph of discovered entities and their relations—and the goal of the task is to refine this graph until $G_{\text{final}} \supseteq I_{\text{answer}}$ (the graph contains all information necessary for answer derivation). The trajectory—the raw sequence of thinking, tool calls, and tool responses—is the construction process for this graph, not the graph itself. And crucially, the construction process is vastly larger than the constructed object: Figure 2 shows that across all tested models, 91–94% of entities explored on BrowseComp and 79–82% on GAIA are irrelevant to the final answer.

This entity-level redundancy analysis (Equation 3, $\Gamma_{\text{red}}$ ) provides something that token-level compression ratios alone cannot: a causal explanation for why compression can be lossless. It is not that the trajectory can be aggressively summarized with acceptable information loss; it is that the answer-relevant information—the effective entities and their relations—constitutes only a small fraction of the trajectory, and systematically extracting exactly that fraction (discarding everything else) preserves all information needed to evaluate or reconstruct the answer. The compression is lossless in the specific, well-defined sense that $G_{\text{final}}$ is fully preserved while the construction scaffolding is removed.

This reframing has implications beyond the specific compression method proposed. It suggests that IS agent evaluation and aggregation should operate at the level of information state graphs, not raw trajectories. Just as program synthesis research distinguishes between a program's execution trace and its abstract syntax tree—and reasons about the latter for certain analyses—IS agent research could distinguish between the interaction trace and the information graph, using the compact graph representation for tasks where the construction details are irrelevant. This opens a direction for graph-based verifiers, graph-based search, and graph-based self-improvement that the paper does not explore but makes conceptually natural.

The compressed structured report format (planning, methods, reasoning) is the implementation of this graph extraction, but the intellectual contribution is the identification of the graph as the right abstraction level for aggregation. This is a fundamental reframing of the answer aggregation problem: the challenge is not "how do we fit long trajectories into limited context?" but rather "how do we extract the information state graph from redundant trajectories and aggregate at the graph level?" The 99% context reduction reported in Figure 5 (Right) validates that the graph representation is genuinely compact, but the deeper point is that this compactness is not a fortunate empirical accident—it follows from the structure of IS tasks as entity-discovery processes.

Innovation 3: Decoupling Exploration Cost from Trajectory Diversity Through Targeted Partial Rollout

Conventional parallel thinking for IS agents—whether self-consistency, best-of-N, or any method that generates independent complete trajectories—ties exploration diversity to a linear cost model: $N$ trajectories cost $N \times$ (cost of one trajectory). This is the default assumption across the test-time scaling literature, where the budget is measured in "number of generations" and each generation is an independent unit of computation. The paper's third conceptual move is to break this coupling by showing that exploration diversity can be achieved without proportional cost increase when trajectories share common prefixes.

What makes this distinctive is not KV-cache reuse itself (a standard inference optimization) but the argument that prefix reuse is structurally well-suited to IS trajectories in particular. The paper's uncertainty analysis shows that exploration uncertainty is concentrated at specific decision points (early exploration, early-middle reasoning), not uniformly distributed. This means that branching—launching alternative continuations from high-uncertainty decision points—can capture most of the diversity benefit of independent sampling while reusing the large fraction of the trajectory where the model is confident and would produce similar outputs regardless. The theoretical efficiency model (Equations 4–6) formalizes why: the speedup factor is $\approx (1 + \sum_j p_j / \sum_j s_j) P$ , which is large precisely when shared prefixes ( $p_j$ ) dominate branch-specific suffixes ( $s_j$ ), which is exactly the regime created by branching at late, high-uncertainty steps rather than early, low-uncertainty ones.

The paper's empirical demonstration that this approach achieves better performance with lower cost (up to 62% improvement with 10–30% token reduction) rather than trading one for the other is significant because it contradicts the standard test-time scaling narrative that "more compute = better performance, less compute = worse performance." PARALLELMUSE achieves a Pareto improvement—strictly better on both accuracy and efficiency—by reallocating computation from low-value prefix regeneration to high-value branch exploration. This is possible only because the naive baseline is fundamentally inefficient in ways the paper identifies and exploits.

This innovation connects to a broader principle in the test-time scaling literature that the reference paper on compute-optimal strategies also identifies: the relationship between compute and performance is not monotonic in strategy—different allocation strategies yield different scaling curves. But where the reference paper achieves efficiency by adaptively selecting among existing strategies (best-of-N vs. beam search), PARALLELMUSE achieves efficiency by redesigning the generation process itself to eliminate redundant computation. This is a significant refinement on partial rollout methods: prior work showed that partial rollout could reduce cost (via prefix reuse), but PARALLELMUSE shows that targeted partial rollout—branching only at high-uncertainty steps in the appropriate functional region—can simultaneously improve quality because it concentrates the exploration budget where diversity is most valuable.

The result that from-scratch full rollouts sometimes underperform partial rollouts (Table 3: Partial settings often exceed From Scratch) is particularly noteworthy. It means that naive independent sampling is not just inefficient—it can be counterproductive because it spreads the exploration budget across steps where diversity doesn't help, diluting the budget available for steps where diversity would help. This is a fundamental insight about the structure of IS exploration: diversity is not uniformly valuable across all steps, and allocating exploration budget without accounting for this heterogeneity wastes computation on diversity that provides no benefit.

Innovation 4: The Empirical Case Against Confidence-Based Answer Selection in Agentic Settings

The paper includes a finding that, while not its primary methodological contribution, constitutes an important diagnostic result with implications for the broader field of agentic reasoning. Table 2 shows that across most model-benchmark combinations, Weighted Vote (confidence-based answer selection) underperforms Majority Vote, despite confidence weighting being a more sophisticated method that incorporates the model's own uncertainty estimates.

This result contradicts the intuition—well-supported in pure reasoning domains—that model confidence should correlate with answer correctness, making confidence-weighted selection superior to uniform voting. The paper's explanation (Section 4.2) identifies the mechanism: "as agents repeatedly integrate external, non–model-generated content (e.g., tool responses), their internal probability distributions shift, degrading the reliability of confidence scores." This is a specific instantiation of a broader phenomenon: distribution shift from external information injection breaks the calibration between model probability and answer correctness. In pure reasoning, the model's probability distribution over tokens reflects its knowledge—higher probability tokens are more likely to be correct because the model's internal knowledge is the sole information source. In IS, the model's probability distribution over tokens also reflects the external information it has received—but the correctness-relevance of that external information is not calibrated in the model's training, so high probability does not reliably indicate correctness.

The exceptions to this pattern are themselves informative: Tongyi-DR-30B-A3B (where Weighted Vote often outperforms Majority Vote) benefits from "continual pre-training that improves calibration over Search and Visit tool responses" (Section 4.2), and HLE (where Weighted Vote also performs relatively better) is a benchmark that "emphasizes reasoning with limited external interaction" (Section 4.1). These exceptions validate the mechanism: when external information injection is reduced (HLE) or when the model is specifically trained to calibrate over tool responses (Tongyi-DR-30B-A3B), confidence becomes a more reliable signal.

This is a negative result with positive implications. It establishes a boundary condition for confidence-based methods—they should not be trusted in agentic settings without explicit calibration over tool interactions—and it explains a pattern of inconsistent findings in the literature (some papers find confidence weighting helps, others don't) through a specific, testable mechanism. It also reinforces the paper's design choice to avoid confidence signals entirely in the Compressed Reasoning Aggregation stage, instead relying on reasoning coherence evaluation across compressed reports—a method that does not depend on internal model confidence.

The significance of this finding extends beyond the paper: as agentic AI systems become more prevalent, the reliability of model confidence signals will be a critical safety and reliability concern. If an agent can be overconfident about answers derived from unreliable web sources, confidence-based selection or confidence-based escalation (routing low-confidence outputs to human review) will fail. The paper's evidence provides a concrete case study and a mechanistic explanation that can inform the design of more robust confidence estimation methods for agentic settings.

5. Experimental Analysis

Evaluation Methodology

Dataset. The paper evaluates on four deep information-seeking benchmarks: BrowseComp (Wei et al., 2025) with 200 randomly sampled tasks from the full dataset; BrowseComp-zh (Zhou et al., 2025), the full 289-task Chinese-language set; GAIA (Mialon et al., 2023), using 103 text-only tasks from a subset curated by Li et al. (2025d); and Humanity's Last Exam (HLE) (Phan et al., 2025), using 157 search-focused text-only tasks. BrowseComp and BrowseComp-zh emphasize deep search capability, HLE emphasizes reasoning with limited external interaction, and GAIA provides a balanced assessment across both dimensions (Section 4.1). The benchmarks jointly test the ability to discover hard-to-access web information and reason over it to produce correct answers.
Base model(s). Four open-source agent models spanning different parameter scales and model families are used: GPT-OSS-20B and GPT-OSS-120B (OpenAI, 2025a), DeepSeek-V3.1-Terminus (671B parameters, Liu et al., 2024), and Tongyi-DeepResearch-30B-A3B (Tongyi-DR-30B-A3B, Team, 2025b). These are all function-calling agents operating under the standard ReAct paradigm (think → tool call loop), invoked with their official function-calling protocols. The paper states the models are selected to represent "diverse parameter scales and advanced tool-use capabilities for deep IS tasks" (Section 4.1), and the range from 20B to 671B parameters across three model families (GPT-OSS, DeepSeek, Tongyi) provides evidence that results are not specific to a single architecture. The same agent model performs both stages of PARALLELMUSE unless otherwise specified (Section 4.1).
Metrics. All evaluations use LLM-as-a-Judge (Gu et al., 2024) under each benchmark's officially released evaluation prompts and judging models. For the No Scaling baseline, the paper reports "the average pass rate over N independent rollouts" (Section 4.1)—this means the fraction of individual trajectories that produce the correct answer, averaged across the $N$ independent runs. For parallel thinking methods (which produce a single final answer from $N$ rollouts), the paper reports "the pass rate of that final output"—the fraction of tasks where the synthesized answer matches the ground truth. Section 4.1 explicitly states that all agent model-specific hyperparameters are "aligned with their official optimal configurations for tool usage." For reproducibility, default PARALLELMUSE hyperparameters are listed in Table 1: sampling budget $N=8$ , initial rollouts $M=1$ , branching PPL top-K $k=2$ , and 3 branching times per step.
Baselines. Five baselines are compared against PARALLELMUSE (Section 4.1, Table 2):
- No Scaling: Standard single-trajectory inference with no parallel thinking, reported as average pass rate over $N$ independent runs.
- Self-Consistency (Majority Vote): (Wang et al., 2022) Generates $N$ complete trajectories, extracts the final answer from each, and selects the most frequent answer as the final output.
- Max #Tool Call: (Zeng et al., 2025) A heuristic that selects the answer from the trajectory with the largest number of environment interactions (tool calls), operating on the intuition that deeper exploration yields better answers.
- DeepConf (Weighted Vote): (Fu et al., 2025) Weights answers by the model's confidence over each trajectory (computed from token-level probabilities) and selects the answer with the highest weighted score.
- Partial Rollout (From Scratch): For the isolated analysis of Stage 1 (Table 3), complete from-scratch rollouts without any context reuse serve as the baseline against which functionality-specified partial rollouts are compared.
For the isolated analysis of Stage 2 (Figure 4), the paper compares Compressed Reasoning Aggregation against No Scaling, Majority Vote, and Weighted Vote, all using the same 8 from-scratch rollouts to isolate the effect of the aggregation method from the exploration method.
Generation budget / compute accounting. The primary unit of test-time compute is the sampling budget $N$ —the total number of complete trajectories generated (whether from scratch or partial). The default is $N=8$ across all experiments (Table 1). For partial rollout variants, the budget $N$ includes both the $M$ initial from-scratch rollouts and the $N-M$ partial rollouts launched from branching points. The paper also measures token consumption as a complementary efficiency metric (Section 4.5, Figure 5): for partial rollout, the token cost per trajectory is compared against the from-scratch baseline to quantify savings from prefix reuse; for trajectory compression, the context token count of compressed reports is compared against the full trajectory length. The theoretical efficiency model (Equations 4–6) uses per-token compute costs $c$ and $c_{\text{cold}}$ to derive speedup factors, but the empirical efficiency measurements report actual token counts rather than FLOP counts.
Cross-validation / statistical protocol. The paper does not describe a formal cross-validation or statistical testing protocol. Strategy selection (e.g., which functional region $f$ to use for partial rollout) appears to be determined by direct comparison on the test benchmarks rather than through held-out validation data. The paper also does not report confidence intervals, standard deviations, or significance tests for any results. Given the modest sample sizes (200 BrowseComp tasks, 157 HLE tasks, 103 GAIA tasks, 289 BrowseComp-zh tasks), the lack of statistical rigor is a notable limitation. The paper does state that results marked with $\ddagger$ in Table 2 represent full-benchmark results while unmarked scores correspond to the paper's sampled subsets, providing clarity about which numbers are directly comparable. For the No Scaling baseline, averaging pass rates over $N$ independent rollouts provides some reduction in sampling variance, but no formal error bounds are reported.

Main Quantitative Results

Overall Performance Across All Benchmarks and Models

The headline result appears in Table 2: PARALLELMUSE consistently achieves the highest performance across all four agent models and all four benchmarks, with improvements over the best baseline (usually Majority Vote or Weighted Vote) ranging from modest to dramatic depending on the model and task.

On BrowseComp, the gains are largest:

GPT-OSS-20B: PARALLELMUSE reaches 49.0% vs. Majority Vote at 44.0% (+5.0 percentage points) and No Scaling at 30.9% (+18.1 points, a 58.6% relative improvement over the base model).
GPT-OSS-120B: 56.5% vs. Majority Vote at 48.5% (+8.0 points) and No Scaling at 34.9% (+21.6 points, a 61.9% relative improvement).
DeepSeek-V3.1-T: 39.0% vs. Majority Vote at 30.0% (+9.0 points) and No Scaling at 23.2% (+15.8 points, a 68.1% relative improvement).
Tongyi-DR-30B-A3B: 65.0% vs. Weighted Vote at 62.0% (+3.0 points) and No Scaling at 51.0% (+14.0 points, a 27.5% relative improvement).

On BrowseComp-zh:

GPT-OSS-20B: 44.3% vs. Majority Vote at 38.8% (+5.5 points).
GPT-OSS-120B: 54.3% vs. Majority Vote at 46.7% (+7.6 points).
DeepSeek-V3.1-T: 50.2% vs. Majority Vote (and Weighted Vote) at 45.0% (+5.2 points).
Tongyi-DR-30B-A3B: 57.1% vs. Majority Vote at 56.8% (+0.3 points, a modest gain).

On GAIA:

GPT-OSS-20B: 72.8% vs. Majority Vote at 69.9% (+2.9 points).
GPT-OSS-120B: 85.4% vs. Weighted Vote at 82.5% (+2.9 points).
DeepSeek-V3.1-T: 74.8% vs. Majority Vote and Weighted Vote at 70.9% (+3.9 points).
Tongyi-DR-30B-A3B: 79.6% vs. Weighted Vote at 78.6% (+1.0 points).

On HLE (the reasoning-heavy benchmark), the gains are most striking for Tongyi-DR-30B-A3B:

GPT-OSS-20B: 32.5% vs. Weighted Vote at 31.2% (+1.3 points) and No Scaling at 24.2% (+8.3 points).
GPT-OSS-120B: 45.9% vs. Weighted Vote at 45.2% (+0.7 points) and No Scaling at 36.3% (+9.6 points).
DeepSeek-V3.1-T: 37.6% vs. Weighted Vote at 28.0% (+9.6 points) and No Scaling at 25.0% (+12.6 points, a 50.4% relative improvement).
Tongyi-DR-30B-A3B: 52.2% vs. Weighted Vote at 42.7% (+9.5 points) and No Scaling at 38.5% (+13.7 points, a 35.6% relative improvement).

Comparison to closed-source agents (Table 2, top section). The paper draws attention to the fact that "when applied to Tongyi-DR-30B-A3B, [PARALLELMUSE] attains performance comparable to or surpassing that of most closed-source agents" (Section 4.2). On BrowseComp, Tongyi-DR-30B-A3B + PARALLELMUSE at 65.0% exceeds ChatGPT Agent (68.9%) with a small gap, and substantially exceeds OpenAI-o3 (49.7%), OpenAI DeepResearch (51.5%), and Claude-4-Sonnet (12.2%). On HLE, Tongyi-DR-30B-A3B + PARALLELMUSE at 52.2% exceeds all listed closed-source agents except ChatGPT Agent (41.6%). This is a noteworthy result: an open-source 30B-active-parameter model with PARALLELMUSE can compete with proprietary research agents of unknown (but presumably much larger) scale.

The confidence weighting failure pattern. Table 2 reveals a consistent and informative pattern: Weighted Vote underperforms Majority Vote across most model-benchmark combinations. On BrowseComp, Weighted Vote vs. Majority Vote: GPT-OSS-20B (41.0 vs. 44.0), GPT-OSS-120B (48.0 vs. 48.5), DeepSeek-V3.1-T (29.5 vs. 30.0). On BrowseComp-zh: GPT-OSS-20B (37.0 vs. 38.8), GPT-OSS-120B (45.7 vs. 46.7), DeepSeek-V3.1-T (45.0 vs. 45.0, tied), Tongyi-DR-30B-A3B (53.6 vs. 56.8). The exceptions are GAIA (where Weighted Vote sometimes edges ahead, e.g., GPT-OSS-120B at 82.5 vs. 77.7 Majority Vote) and HLE (where Weighted Vote consistently outperforms Majority Vote across all models). The paper explains HLE as "emphasiz[ing] reasoning with limited external interaction" (Section 4.2), meaning less external information injection to miscalibrate confidence, and Tongyi-DR-30B-A3B as benefiting from "continual pre-training (Su et al., 2025) that improves calibration over Search and Visit tool responses" (Section 4.2). This pattern provides empirical support for the paper's claim that confidence miscalibration from tool-response integration is a genuine obstacle in IS settings, not merely a hypothetical concern.

The Max #Tool Call baseline performs poorly across the board. On BrowseComp, GPT-OSS-120B achieves only 17.5% with Max #Tool Call vs. 48.5% with Majority Vote and 56.5% with PARALLELMUSE—a striking failure that suggests more tool interactions do not reliably indicate better answers, and may even correlate with getting lost in unproductive exploration. This validates the paper's motivation for targeted (rather than unconstrained) exploration.

Analysis of Partial Rollout over Distinct Functional Regions (Table 3)

Table 3 isolates the first-stage contribution by reporting the average pass rate after 8 rollouts (the $N=8$ budget) under different functional-region branching strategies, compared against full from-scratch rollouts (which do not reuse context and therefore cannot benefit from functional-region distinction).

Key finding: Functional-region-aware partial rollout consistently outperforms from-scratch rollout. For GPT-OSS-120B on BrowseComp: from-scratch achieves 34.9%, while exploration-region partial rollout reaches 39.9% (+5.0 points), reasoning-region reaches 37.9% (+3.0 points), and mixed reaches 38.1% (+3.2 points). On GAIA: from-scratch achieves 74.2%, exploration-region reaches 77.9% (+3.7 points). For DeepSeek-V3.1-T on BrowseComp-zh: from-scratch achieves 36.1%, reasoning-region reaches 39.8% (+3.7 points). The improvements are not uniform—DeepSeek-V3.1-T on GAIA actually shows a slight degradation for reasoning-region partial rollout (60.2% vs. 61.0% from-scratch)—but the dominant pattern is positive.

Key finding: The optimal functional region for branching is model-dependent. On BrowseComp, GPT-OSS-120B benefits most from exploration-region branching (39.9) while DeepSeek-V3.1-T benefits most from reasoning-region branching (26.5 vs. 23.8 for exploration-region and 23.2 for from-scratch). The paper attributes this to model architecture differences (Section 4.3): "GPT-OSS-120B benefits less from reasoning-based branching, as its strong adaptive reasoning mechanism already yields consistently high-quality reasoning with limited exploration potential. In contrast, DeepSeek-V3.1-T employs function calling outside of the thinking mode, resulting in weaker internal reasoning capacity and thus higher sampling potential in reasoning steps." This model-dependence has practical implications: deploying PARALLELMUSE with a new agent model requires calibration to determine the optimal functional region for that model's architecture.

Key finding: Mixed-region branching (selecting half the top-k steps from each functional region) never dominates. On GPT-OSS-120B, mixed achieves 38.1 on BrowseComp vs. 39.9 for exploration-only and 37.9 for reasoning-only. On DeepSeek-V3.1-T, mixed achieves 23.4 on BrowseComp vs. 26.5 for reasoning-only. The mixed strategy appears to be a compromise that dilutes the benefit of targeting the most productive region for each model. This reinforces the paper's central claim that functional-region-aware selection is important, and that a one-size-fits-all strategy (or even a 50-50 split) is suboptimal.

The omitted baseline: homogeneous partial rollout. The paper's footnote in Section 4.3 states: "We omit results of partial rollout without functional-region distinction (i.e., treating all tokens as homogeneous), as our preliminary experiments show that this setting performs comparably to full from-scratch rollouts and provides no observable gains from branching at high-uncertainty steps." This is a critical negative result that the paper relegates to a footnote. It directly validates the paper's central conceptual claim: the functional-region distinction is not a minor refinement; it is what makes partial rollout work at all in IS settings. Without it, the method collapses to the performance of the naive baseline. This finding should have been presented as a primary result with its own table row, as it provides the strongest evidence for the paper's key innovation.

Performance Gains from Compressed Reasoning Aggregation (Figure 4)

Figure 4 isolates the second-stage contribution by comparing answer generation methods when the exploration stage is held constant at 8 from-scratch rollouts. This controls for the sampling gains of Stage 1 and measures only the effect of how trajectories are aggregated into a final answer.

Key finding: Compressed Reasoning Aggregation alone provides the largest gains, with Tongyi-DR-30B-A3B as the testbed. On BrowseComp: No Scaling (single trajectory) achieves 51.0%, Majority Vote reaches 60.0%, Weighted Vote reaches 62.0%, and Compressed Reasoning Aggregation reaches 63.5%. On BrowseComp-zh: 45.3% → 56.8% → 53.6% → 57.1% (aggregation slightly edges out Majority Vote). On GAIA: 73.6% → 77.7% → 78.6% → 80.6% (aggregation leads). On HLE: 38.5% → 40.1% → 42.7% → 52.2%. The HLE result is the most dramatic: Compressed Reasoning Aggregation achieves 52.2% vs. Weighted Vote at 42.7% and Majority Vote at 40.1%, a gain of +9.5 points over the next best method and +13.7 points over the base model. This is a 35.6% relative improvement from the aggregation stage alone, without any changes to the exploration process.

Key finding: Compressed Reasoning Aggregation substantially outperforms answer selection methods even when holding exploration constant. Since all methods in Figure 4 use the same 8 from-scratch rollouts, the performance gaps are entirely attributable to how answers are derived from those rollouts. Majority Vote mechanically selects the most common final answer, ignoring whether that answer is well-supported. Weighted Vote incorporates confidence signals but, as discussed, these are miscalibrated in IS settings. Compressed Reasoning Aggregation, by evaluating reasoning coherence across compressed full-trajectory reports, can recognize when a minority answer has stronger evidential support and can synthesize elements from multiple reports. The paper emphasizes that this approach "performs near-lossless compression over each agentic reasoning trajectory to efficiently integrate reasoning information without invoking additional tool calls for secondary verification" (Section 4.4), maximizing the information extracted from the fixed exploration budget.

Efficiency Gains through Context Reuse and Trajectory Compression (Figure 5)

Figure 5 quantifies the two sources of efficiency improvement claimed in the paper's title and abstract.

Left panel: Token reduction from context reuse in partial rollout. Using GPT-OSS-120B on BrowseComp as the test case, the green bars show the per-trajectory token cost after applying partial rollout, expressed as a ratio relative to the from-scratch baseline (the blue bars show the proportion of tokens saved). The paper reports "up to 28% token savings" (Section 4.5), with the efficiency gain increasing with sampling scale—"indicating better scalability" as more branches share the same prefixes. The exact ratio at $N=8$ is not numerically specified in the text, but the figure shows a clear reduction in token consumption relative to the from-scratch baseline. This validates the theoretical efficiency model (Equations 4–6): when prefixes are long relative to suffixes ( $\sum_j p_j / \sum_j s_j$ is large), the ReuseFactor drives substantial token savings. The paper emphasizes that these savings come from "allocating additional tokens and reasoning capacity as needed to high-utility regions while eliminating most redundant or avoidable computation" (Section 4.5).

Right panel: Context token reduction from trajectory compression. The paper reports that compressing agentic reasoning trajectories into structured reports "reduces context token usage by up to 99% relative to the full trajectory, achieving an almost complete compression" (Section 4.5). This directly validates the entity-level redundancy analysis from Section 2.2: the $\Gamma_{\text{red}} \approx 91-94\%$ on BrowseComp (Figure 2) means ~93% of explored entities are irrelevant, and the 99% token reduction suggests the compression is slightly more aggressive than entity-level filtering alone—perhaps because entities are described more verbosely in raw trajectories than in structured report form. The practical consequence is that "multi-trajectory reasoning aggregation within context limits" becomes feasible: $N$ compressed reports, each at ~1% of original size, can all fit within a standard context window even when the original trajectories would far exceed it.

Key finding: Efficiency gains are complementary and compound. The partial rollout savings (Stage 1) reduce the cost of generating diverse trajectories, while the compression savings (Stage 2) reduce the cost of aggregating them. The paper explicitly positions this as a departure from conventional test-time scaling: "PARALLELMUSE is not a conventional test-time scaling strategy that improves performance by aggressively sacrificing efficiency. Instead, by leveraging a task-informed design, it scales computation where it matters most" (Section 4.5). This is the empirical basis for the paper's claim of 10–30% exploratory token reduction simultaneously with up to 62% performance improvement—a Pareto improvement over naive parallel thinking.

Impact of Model Capability on Compressed Reasoning Aggregation (Table 4)

Table 4 explores whether a stronger model can improve the compression and aggregation quality beyond what the exploration model itself achieves. This is a practically important design choice: since Stage 1 exploration is expensive (many tool calls, long trajectories) while Stage 2 aggregation is cheap (operating over already-compressed reports, no tool calls), using a more capable model for aggregation adds modest cost while potentially unlocking substantial gains.

Key finding: Stronger aggregation models consistently improve performance. For GPT-OSS-20B as the rollout model on BrowseComp:

GPT-OSS-20B as the aggregation model (same-model baseline): 49.0%
GPT-OSS-120B as the aggregation model (+1 scale level): 50.5% (+1.5 points)
GPT-5 as the aggregation model (+much stronger): 55.5% (+6.5 points)

For Tongyi-DR-30B-A3B:

Same-model aggregation: 65.0%
GPT-5 aggregation: 66.0% (+1.0 points)

Key finding: The gain from stronger aggregation models varies with the base agent's capability. The +6.5 point gain when upgrading GPT-OSS-20B → GPT-5 is substantial, while the +1.0 point gain when upgrading Tongyi-DR-30B-A3B → GPT-5 is modest. This suggests that when the base agent is already highly capable (Tongyi-DR-30B-A3B produces high-quality reports that are already well-structured and comprehensive), a stronger aggregator has less room to improve. When the base agent is weaker (GPT-OSS-20B produces reports that may have gaps or reasoning errors), a stronger aggregator can better compensate by identifying and correcting those weaknesses during synthesis.

The paper interprets the improvement as evidence for the compressed report's fidelity: "the compressed report effectively represents the agent's internal information state graph and... higher-quality graph reconstruction enhances overall performance" (Section 4.6). A practical implication is that "combining models of different strengths can balance efficiency and performance" in multi-agent designs: cheaper models handle expensive exploration, and a single more capable model handles cheap but cognitively demanding aggregation.

Ablation Studies and Robustness Checks

Functional region choice for partial rollout branching (Table 3): The choice of whether to branch based on reasoning uncertainty ( $f=r$ ), exploration uncertainty ( $f=e$ ), or a mixed strategy produces substantially different results that are model-dependent. On GPT-OSS-120B BrowseComp, exploration-region branching (39.9) outperforms reasoning-region (37.9) by 2.0 points, while on DeepSeek-V3.1-T BrowseComp, reasoning-region branching (26.5) outperforms exploration-region (23.8) by 2.7 points. These are not marginal differences—they represent a 5–10% relative performance swing depending on the functional region choice. The mixed strategy consistently underperforms the best single-region strategy (38.1 vs. 39.9 for GPT-OSS-120B BrowseComp; 23.4 vs. 26.5 for DeepSeek-V3.1-T BrowseComp), indicating that evenly splitting branching points across regions dilutes the benefit. This ablation demonstrates that the functional-region distinction is not merely a conceptual framing but a practically consequential design choice that requires per-model calibration.

Homogeneous partial rollout (no functional distinction) — negative result (Section 4.3 footnote): The paper reports that partial rollout "without functional-region distinction (i.e., treating all tokens as homogeneous)... performs comparably to full from-scratch rollouts and provides no observable gains from branching at high-uncertainty steps." This is the strongest ablation supporting the paper's central claim. It shows that the performance gains in Table 3 are not simply from partial rollout with KV-cache reuse (which reduces cost but might be expected to preserve quality); rather, they depend specifically on targeting branching at the right functional region. A homogeneous uncertainty metric fails because it cannot distinguish between exploration-driven uncertainty (where branching may just produce different uninformed queries) and reasoning-driven uncertainty (where branching explores genuinely different analytical approaches). This negative result should have received more prominence—it is currently in a footnote rather than the main ablation table.

Compressed Reasoning Aggregation vs. answer selection methods (Figure 4): Holding the exploration stage constant at 8 from-scratch rollouts isolates the aggregation method's contribution. On Tongyi-DR-30B-A3B HLE, the Compressed Reasoning Aggregation achieves 52.2% vs. Weighted Vote at 42.7% and Majority Vote at 40.1%—a +9.5 point gap over the next best method. On GAIA, it achieves 80.6% vs. 78.6% for Weighted Vote and 77.7% for Majority Vote. On BrowseComp, it achieves 63.5% vs. 62.0% for Weighted Vote and 60.0% for Majority Vote. The aggregation advantage is largest on HLE (reasoning-heavy, less external information to miscalibrate answer-selection heuristics) and smallest on BrowseComp (search-heavy, where answer frequency may be a more reliable signal because multiple trajectories that independently discover the same obscure fact are likely correct). This pattern is consistent with the paper's claim that majority-based selection fails when the correct answer is rare, and that reasoning-coherence evaluation becomes more valuable as task complexity increases.

Same-model vs. stronger-model aggregation (Table 4): The gain from using a stronger model for compression and aggregation is monotonic with model capability. On GPT-OSS-20B BrowseComp: same-model (49.0%) < GPT-OSS-120B (50.5%) < GPT-5 (55.5%). This validates that the compression quality matters—a stronger model extracts a more faithful information state graph from the raw trajectory, and a stronger model synthesizes across reports more effectively. The paper does not ablate whether the compression model and the aggregation model need to be the same, or whether an even stronger compression model with a weaker aggregation model (or vice versa) would be optimal.

Token consumption ablation (Figure 5): The left panel demonstrates token reduction from KV-cache prefix reuse, with the paper reporting "up to 28%" savings. The right panel demonstrates 99% context token reduction from trajectory compression. These are both single-data-point measurements (GPT-OSS-120B on BrowseComp), not sweeps across models or budgets. The paper does not report how the token savings from partial rollout scale with $N$ beyond the qualitative observation that "the efficiency gain increases with sampling scale, indicating better scalability." The compression ratio is reported for the trajectory-to-report transformation but not broken down by whether the compression is equally lossless across all difficulty levels—there could be tasks where the effective entity set is larger and the compression is less aggressive.

Model-specific tool-call behavior as implicit ablation: The DeepSeek-V3.1-T model, which "employs function calling outside of the thinking mode" (Section 4.3), provides a natural test of whether the functional-region distinction generalizes across fundamentally different tool-use architectures. The fact that reasoning-region branching is optimal for DeepSeek-V3.1-T (26.5 BrowseComp) while exploration-region branching is optimal for GPT-OSS-120B (39.9 BrowseComp) suggests that the method adapts to model-specific functional allocations—it doesn't assume a particular architecture but rather computes uncertainty within whatever functional regions the model's output format defines. This is a robustness check in practice, though the paper doesn't frame it as such.

Critical Assessment

Claim 1: "PARALLELMUSE achieves up to 62% performance improvement with a 10–30% reduction in exploratory token consumption."

The performance improvement claim: The "up to 62%" figure comes from the relative improvement on BrowseComp for GPT-OSS-120B: No Scaling achieves 34.9% (or 33.8% on the full benchmark) while PARALLELMUSE achieves 56.5%—a relative increase of approximately 62% (calculated as (56.5-34.9)/34.9 ≈ 61.9%). This is for a specific model-benchmark pair, not an average across all conditions. On other models and benchmarks, the relative gains are substantial but smaller: DeepSeek-V3.1-T HLE shows +50.4%, GPT-OSS-20B BrowseComp shows +58.6%, while Tongyi-DR-30B-A3B GAIA shows only +8.2%. The "up to" formulation is accurate, but the paper's abstract and introduction emphasize this headline number without sufficiently contextualizing that it represents the upper bound across all tested configurations. The gains are consistently positive but highly variable in magnitude.

The efficiency claim: The "10–30% reduction in exploratory token consumption" is demonstrated in Figure 5 (Left) for GPT-OSS-120B on BrowseComp, with the paper reporting "up to 28%" savings. The paper provides this measurement for a single model-benchmark pair and does not report token consumption data for other models, benchmarks, or budget levels. The theoretical model (Equations 4–6) predicts that savings depend on the prefix-to-suffix length ratio, which varies by task and branching strategy. The paper does not demonstrate that the 10–30% range holds generally—it is an extrapolation from a single data point combined with theoretical analysis. Additionally, the difficulty estimation cost (Section 2 in the reference paper's analysis) has a parallel here: the paper does not account for the cost of computing per-step, per-region PPL in the initial $M$ trajectories to identify branching points. This cost includes storing and analyzing token-level log-probabilities during generation, which may have computational overhead not captured in the token-based accounting.

Claim 2: "Functionality-Specified Partial Rollout enhances exploration efficiency by performing uncertainty-guided path reuse and branching."

The evidence in Table 3 generally supports this claim: partial rollout with functional-region-aware branching outperforms from-scratch rollout in most (but not all) cases. The gains range from +5.0 points (GPT-OSS-120B BrowseComp exploration-region) to slight negatives (DeepSeek-V3.1-T GAIA reasoning-region at -0.8 points). The key supporting evidence is the negative result in the footnote: homogeneous partial rollout provides no gains, directly validating that the functional-region distinction is necessary—not just beneficial—for partial rollout to work in IS settings.

However, several important questions are unexplored:

The $M=1$ initial rollout sensitivity. With only a single initial trajectory, the branching point selection is based on one sample. If PPL peaks are trajectory-specific (the model's uncertainty at a given step depends on what information it happened to retrieve earlier), then $M=1$ could select unrepresentative branching points. The paper does not test $M > 1$ to see whether more initial trajectories improve branching point selection. The fact that the method works with $M=1$ suggests PPL peaks are task-structural (consistent across trajectories), but this should be empirically verified.
The $k=2$ top-K sensitivity. Only two branching steps are selected from all steps in the initial trajectory. The paper does not sweep $k$ to determine whether more (or fewer) branching points would be optimal, or whether the optimal $k$ varies by task difficulty or model. With a fixed $N=8$ budget, changing $k$ would also change the number of branches per step, creating a tradeoff between branching breadth (many points, few branches each) and branching depth (few points, many branches each).
The interaction between functional region selection and difficulty. The paper does not analyze whether the optimal functional region varies by task difficulty (as the reference paper finds for search vs. revisions). Easy questions might benefit from reasoning-region branching (where the model just needs to refine its synthesis) while hard questions might benefit from exploration-region branching (where the model needs to discover different information). This difficulty-dependent analysis, which the reference paper on compute-optimal test-time scaling found crucial, is entirely absent from PARALLELMUSE's evaluation.
The comparison to alternative partial rollout criteria. The paper uses PPL as the uncertainty metric but does not compare against alternative signals: entropy of the next-token distribution, variance across multiple samples from the same prefix, or disagreement among ensemble models. PPL is a convenient choice (available from standard log-probability outputs) but may not be the optimal signal for identifying productive branching points.

Claim 3: "Compressed Reasoning Aggregation exploits reasoning redundancy to losslessly compress information relevant to answer derivation and synthesize a coherent final answer."

The evidence for the effectiveness of this stage is strong in Figure 4: across all four benchmarks with Tongyi-DR-30B-A3B, Compressed Reasoning Aggregation outperforms both Majority Vote and Weighted Vote (which use the same 8 from-scratch rollouts). The gains are particularly large on HLE (+9.5 points over Weighted Vote) and more modest on BrowseComp (+1.5 points). This pattern is consistent with the paper's argument: on reasoning-heavy tasks (HLE), evaluating reasoning coherence matters more because surface-level answer agreement is a weaker signal of correctness.

The "lossless" claim requires more scrutiny:

Demonstrating losslessness would require showing that all information in $G_{\text{final}}$ is preserved. The paper's evidence is indirect: the entity-level redundancy analysis (Figure 2) shows that most entities are irrelevant, and the compression ratio (Figure 5 Right) shows 99% token reduction. But the paper does not directly measure whether the compressed reports faithfully capture all answer-relevant information—for example, by having human evaluators check whether any crucial evidence in the raw trajectory is missing from the compressed report, or by comparing answer accuracy when aggregating from full trajectories (impractical due to context limits) vs. compressed reports. The "lossless" claim is better understood as "lossless with respect to answer-relevant entities as identified by the model performing the compression," which depends on that model's extraction quality.
The extraction quality depends on the compression model's capability (as Table 4 demonstrates). A weaker compression model may fail to identify some effective entities or may incorrectly include irrelevant ones, making the compression lossy in practice even if the concept is lossless in theory. The paper's demonstration that a stronger compression model (GPT-5) improves results supports this interpretation.
The structured report format may introduce its own biases. The three-section structure (planning, methods, reasoning) forces the compression model to organize information in a particular way. Trajectories with non-standard reasoning patterns—where planning, execution, and synthesis are interleaved rather than sequential—may be poorly represented in this format, potentially losing information that doesn't fit neatly into one of the three sections.

Claim 4: "PARALLELMUSE attains performance comparable to or surpassing that of most closed-source agents" (when applied to Tongyi-DR-30B-A3B).

This claim in Section 4.2 compares Tongyi-DR-30B-A3B + PARALLELMUSE against closed-source agents from Table 2 (top section). On BrowseComp: PARALLELMUSE at 65.0% exceeds OpenAI-o3 (49.7%), OpenAI DeepResearch (51.5%), and Claude-4-Sonnet (12.2%), and is competitive with ChatGPT Agent (68.9%). On HLE: PARALLELMUSE at 52.2% exceeds all listed closed-source agents (the next highest is ChatGPT Agent at 41.6%).

Several caveats apply:

The closed-source numbers include full-benchmark results (marked with $\ddagger$ ) that are not directly comparable to the paper's sampled subsets. For example, GPT-OSS-120B BrowseComp reports both 34.9 (paper's 200-task subset) and 33.8‡ (full benchmark), a 1.1-point difference. Similar subset-vs-full discrepancies may exist for closed-source agents but are not reported, since the paper only has access to the published full-benchmark numbers for those agents.
The closed-source agents are evaluated with single-trajectory No Scaling (no parallel thinking), while PARALLELMUSE uses $N=8$ trajectories. A fairer comparison would give closed-source agents the same parallel thinking budget, but this is impossible since the paper cannot modify closed-source agent behavior. The comparison demonstrates that an open-source agent with smart parallel thinking can reach closed-source performance levels with single-trajectory inference, but it does not demonstrate that PARALLELMUSE is superior to what closed-source agents could achieve with their own parallel thinking.
The comparison is primarily interesting as an existence proof that open-source IS agents with parallel thinking can be competitive with proprietary systems, not as a controlled experiment establishing PARALLELMUSE's specific contribution to this parity.

General weaknesses in the experimental design:

Single-tool configuration. All experiments use only Search and Visit tools. The paper acknowledges in Section 7 that "more general agentic tasks often involve a broader range of tools... leading to substantially larger exploration spaces." Whether the functional-region distinction (reasoning vs. exploration) and the compression method generalize to settings with diverse tool types (database queries, API calls, code execution, file operations) is untested. Multiple tool types would create multiple functional sub-regions within $T^e$ , each potentially with different uncertainty dynamics—a complexity the current framework does not address.
No statistical error reporting. The paper provides point estimates for all results without standard deviations, confidence intervals, or significance tests. With test set sizes of 103–289 tasks, random variation could account for small performance differences (e.g., the 0.3-point gap between PARALLELMUSE and Majority Vote on Tongyi-DR-30B-A3B BrowseComp-zh, or the 0.7-point gap on GPT-OSS-120B HLE). The lack of statistical rigor makes it difficult to assess which reported differences are reliable and which could be noise.
No difficulty-stratified analysis. The reference paper on compute-optimal test-time scaling demonstrates that strategy effectiveness depends critically on problem difficulty, with different strategies optimal for easy vs. medium vs. hard problems. PARALLELMUSE does not analyze whether its gains are concentrated in particular difficulty regimes. It's possible that the 62% improvement on BrowseComp comes entirely from easy-to-medium questions where the base model already has some traction, while hard questions show no improvement (as the reference paper found for its hardest difficulty bin). Without difficulty stratification, the paper cannot characterize where PARALLELMUSE helps and where it doesn't, which limits the practical guidance for deployment.
No comparison to sequential test-time scaling strategies. The paper compares only against parallel thinking baselines (Majority Vote, Weighted Vote) and a heuristic baseline (Max #Tool Call). It does not compare against sequential strategies such as iterative self-refinement (where the agent revises its answer based on previous attempts) or best-of-N with a learned verifier. While the paper's focus is on parallel thinking, the absence of sequential baselines means the reader cannot assess whether parallel thinking is the right form of test-time compute for IS tasks at all, or whether the same budget would be better spent on a different strategy.
The $N=8$ budget is fixed across all experiments. The paper does not sweep $N$ to show how PARALLELMUSE's performance scales with compute budget, or whether the efficiency gains compound at larger budgets (as the reference paper finds for its compute-optimal strategies). A scaling curve (performance vs. $N$ for different methods) would reveal whether PARALLELMUSE's advantage over baselines grows, shrinks, or stays constant as more compute is allocated—information that is essential for practitioners deciding how to allocate their inference budget.
The functional region choice is evaluated only on two models (GPT-OSS-120B and DeepSeek-V3.1-T) in Table 3. The other two models (GPT-OSS-20B and Tongyi-DR-30B-A3B) are not included in the functional-region ablation, even though they appear in the overall results (Table 2). The paper does not specify which functional region was used for these models in the main results, making it unclear whether the optimal region was selected or whether a default was applied.
No analysis of the interaction between the two stages. The paper demonstrates that Stage 1 alone (Table 3) and Stage 2 alone (Figure 4) each improve performance, and the combined system (Table 2) improves further. But it does not include the ablation that would quantify synergy: comparing the combined system against (a) Stage 1 partial rollout with Majority Vote aggregation and (b) Stage 2 compressed aggregation with from-scratch rollouts. Such an analysis would reveal whether the stages are simply additive (combined gain ≈ Stage 1 gain + Stage 2 gain) or multiplicative (combined gain > sum of individual gains), which is important for understanding whether the two stages are genuinely coupled as the paper claims in Section 1.
The entity extraction for redundancy analysis relies on GPT-4.1 as an external tool. Figure 2's entity counts (and the derived $\Gamma_{\text{red}}$ values) depend on GPT-4.1's ability to correctly identify entities and classify them as effective or not. The paper does not validate this extraction against human annotations, so the reported 91–94% redundancy could be partly an artifact of the extraction model's biases (e.g., GPT-4.1 might miss entities that humans would consider effective, inflating the apparent redundancy). This is not a fatal flaw—the compression method doesn't directly use GPT-4.1 entity extraction—but it weakens the theoretical justification for why compression can be lossless.

6. Limitations and Trade-offs

Limitations in Statistical Rigor and Experimental Design

The constraint. The paper reports point estimates for all results without standard deviations, confidence intervals, or significance tests. The test sets are modest in size: 200 tasks for BrowseComp, 157 for HLE, 103 for GAIA, and 289 for BrowseComp-zh. With these sample sizes, non-trivial random variation is expected. The paper does not report whether the reported improvements are statistically significant or whether the functional-region strategy selection (which varies by model, as shown in Table 3) is robust to re-sampling the test data.

The consequence. Several headline comparisons may not be statistically reliable. For instance, on Tongyi-DR-30B-A3B BrowseComp-zh, PARALLELMUSE achieves 57.1% vs. Majority Vote at 56.8%—a 0.3 percentage point difference. On GPT-OSS-120B HLE, the gap is 45.9% vs. Weighted Vote at 45.2%—a 0.7 point difference. With 289 and 157 test tasks respectively, these gaps may fall within the margin of error from sampling variance alone. Similarly, the functional-region comparisons in Table 3 (e.g., GPT-OSS-120B BrowseComp: exploration-region 39.9 vs. reasoning-region 37.9, a 2.0 point gap on 200 tasks) cannot be assessed for robustness without error estimates. The paper's strategy of selecting the optimal functional region per model by direct comparison on the test benchmarks (Section 4.3) amounts to test-set optimization—the chosen functional region for each model may capitalize on noise in the specific test sample rather than reflecting a general property of the model's architecture.

Evidence in the paper. The paper provides no error bars, confidence intervals, p-values, or cross-validation protocol. Section 4.1 describes evaluation metrics and hyperparameters but does not mention statistical methodology. The test set sizes are reported in Section 4.1 (200 BrowseComp, 157 HLE, 103 GAIA, 289 BrowseComp-zh).

Mitigation status. Not addressed. The paper does not acknowledge the absence of statistical testing as a limitation. For the No Scaling baseline, averaging pass rates over $N=8$ independent rollouts provides some variance reduction (since each task's pass rate is estimated from 8 trials rather than 1), but no formal error quantification is applied to any parallel thinking method.

The $N=8$ Budget Is Fixed and Scaling Behavior Is Unexplored

The constraint. All experiments use a fixed sampling budget of $N=8$ trajectories (Table 1). The paper does not sweep $N$ to characterize how PARALLELMUSE's performance—or its advantage over baselines—scales with compute budget. The reference paper on compute-optimal test-time scaling demonstrates that strategy effectiveness can change qualitatively as budget increases (e.g., beam search outperforms best-of-N at low budgets but degrades at high budgets due to verifier over-optimization). Without a scaling analysis, the paper cannot answer whether PARALLELMUSE's advantage grows, shrinks, or plateaus as more compute is allocated.

The consequence. A practitioner deploying this method cannot determine whether PARALLELMUSE remains the best choice at higher budgets. Several scenarios are plausible and have different implications:

Advantage grows with $N$ : If partial rollout's targeted exploration benefits compound (more branches at high-uncertainty steps discover increasingly diverse information) and compressed aggregation's reasoning-coherence evaluation becomes more reliable with more reports, then PARALLELMUSE could pull further ahead of baselines at $N=16$ or $N=32$ . This would make the method especially attractive for high-budget deployments.
Advantage plateaus or reverses: If the uncertainty-guided branching saturates (after exploring the top few high-uncertainty steps, additional branches provide diminishing returns) while naive best-of-N continues to improve from sheer volume, the advantage could narrow or reverse at higher $N$ . This would mean PARALLELMUSE is primarily a low-budget efficiency technique.
Over-optimization emerges: The reference paper documents verifier over-optimization where aggressive search against a reward model eventually degrades performance. PARALLELMUSE has no explicit verifier, but compressed aggregation's evaluation of reasoning coherence could be "over-optimized" if more reports create more opportunities for the aggregation model to find spurious patterns rather than genuine reasoning quality.

The paper's claim of "up to 28% token savings" increasing with sampling scale (Section 4.5, referring to Figure 5 Left) hints at favorable scaling for efficiency, but efficiency scaling and performance scaling are different questions. The 10–30% token reduction claim is measured at the single budget $N=8$ for a single model-benchmark pair.

Evidence in the paper. All results in Tables 2, 3, and Figure 4 use $N=8$ . Figure 5 (Left) shows token consumption at multiple sampling scales for a single model-benchmark pair (GPT-OSS-120B on BrowseComp), but reports only the efficiency ratio, not the corresponding performance. The paper provides no performance-vs- $N$ scaling curves for any method.

Mitigation status. Not addressed. The paper does not discuss the fixed budget as a limitation or propose future scaling analysis. Section 7 (Limitations and Future Work) focuses on tool-set breadth rather than budget scaling.

Difficulty Estimation Cost Is Not Accounted For, and No Difficulty-Conditioned Strategy Exists

The constraint. PARALLELMUSE makes two design choices that introduce computational overhead before the main exploration begins. First, the initial $M=1$ from-scratch rollout must be completed before any branching decisions can be made—this is a sequential dependency that prevents full parallelization of the Stage 1 exploration. Second, per-step, per-region PPL computation requires storing and analyzing token-level log-probabilities for every step of the initial trajectory, which may involve additional computational overhead beyond standard generation (though the paper does not quantify this). Third—and most importantly—the paper does not condition its strategy on estimated task difficulty, despite the reference paper's demonstration that optimal test-time strategies are strongly difficulty-dependent. The functional region selection ( $f \in \{r, e\}$ ) is model-dependent but not task-dependent: all BrowseComp tasks receive the same functional-region branching strategy for a given model, regardless of whether the task is easy or hard for that model.

The consequence. Two problems arise from the absence of difficulty conditioning. First, the paper cannot characterize whether PARALLELMUSE's gains are concentrated in particular difficulty regimes. The reference paper finds that for its hardest difficulty bin (pass@1 near zero), no test-time strategy helps—the base model simply lacks the capability to produce correct solutions regardless of budget. If the same holds for IS agents, then PARALLELMUSE's 62% improvement on BrowseComp could be driven entirely by easy-to-medium questions, with zero improvement on the hardest questions. Without difficulty stratification, a practitioner cannot know whether the method helps on the tasks they care about most (the hard ones where baseline performance is unacceptable). Second, without difficulty estimation, PARALLELMUSE cannot adapt its strategy per-task. The reference paper shows that adaptive strategy selection (best-of-N on easy problems, beam search on medium problems) recovers a 4× efficiency gain over uniform strategies. PARALLELMUSE applies the same functional-region branching and the same compressed aggregation to every task, potentially leaving efficiency on the table for tasks where different settings would be optimal (e.g., easy tasks might benefit from more aggressive compression and simpler aggregation, while hard tasks might need more branching points).

Evidence in the paper. The paper does not report difficulty-stratified results for any benchmark or model. There is no analysis of whether PARALLELMUSE's gains correlate with baseline pass rates or any other difficulty proxy. The functional-region choice is treated as a model-level hyperparameter (Table 3) rather than a task-level adaptive decision. Section 3.1 describes the branching identification as using "the top-k steps with the highest uncertainty" without any mechanism for varying $k$ or the functional region based on task characteristics.

Mitigation status. Not addressed. The paper does not discuss difficulty estimation, difficulty-conditioned strategy selection, or the overhead of the initial PPL computation as part of the total cost accounting. Section 7 (Limitations and Future Work) does not mention this issue, focusing instead on extending to broader tool configurations.

Generalization Is Untested Beyond a Single Tool Configuration and Question-Answering Format

The constraint. All experiments use exactly two tools: Search (batched Google queries returning top-10 results) and Visit (fetching and extracting information from URLs) (Section 4.1). The paper explicitly acknowledges in Section 7: "In this work, we focus primarily on question-answering–oriented deep IS tasks, where the toolset is limited to Search and Visit. While this configuration is optimal for deep IS tasks, more general agentic tasks often involve a broader range of tools (Fang et al., 2025), leading to substantially larger exploration spaces." The paper does not evaluate PARALLELMUSE on tasks requiring other tool types (code execution, database queries, API calls, file operations, multi-modal tools) or on non-question-answering agentic tasks (planning, negotiation, interactive dialogue, creative generation).

The consequence. Several core assumptions of the framework may break under broader tool configurations:

The functional partition into two regions ( $T^r$ and $T^e$ ) may be insufficient. With multiple tool types, exploration tokens would partition into multiple sub-regions ( $T^{e_1}$ for search, $T^{e_2}$ for code execution, $T^{e_3}$ for database queries), each potentially with different uncertainty dynamics. The paper's method of computing separate PPL per functional region and selecting one region for branching would need to generalize to multi-way selection, and the optimal allocation of branching points across tool types is unknown.
The compression format (planning, methods, reasoning) assumes a particular task structure where problems decompose into subproblems that are solved by information retrieval, then synthesized. Tasks that involve iterative refinement (e.g., code generation with debugging), interactive negotiation, or open-ended exploration may not fit this three-section structure, making the compression lossy in ways the paper does not characterize.
The "no tool calls during aggregation" constraint (Section 3.2) may be inappropriate for tasks where answer verification requires re-executing code with different inputs or querying a database with a refined query. The paper argues that reports contain "sufficient tool-calling provenance and attribution information for answer derivation," but this assumes the provenance is self-contained—that one can evaluate an answer's correctness from the recorded evidence alone, without verifying that evidence through re-execution.
The Search–Visit tool pair has a particular cost structure (search is cheap, visiting many pages is expensive, and both return structured results) that may not generalize. For code execution tasks, where each execution is relatively cheap but provides critical feedback, the token savings from prefix reuse may be negligible compared to execution costs, and the optimal branching strategy may be entirely different.

Evidence in the paper. Section 7 explicitly acknowledges this as the primary limitation and future work direction: "Designing effective parallel thinking strategies under such complex tool configurations to extend applicability to general agentic settings remains an open direction for future research." The paper provides no ablation with additional tools, no analysis of how the functional-region PPL patterns might change with different tool types, and no discussion of whether the structured report format would need modification for non-retrieval task types.

Mitigation status. The paper is transparent about this limitation in Section 7 and frames it as future work. This is a fair acknowledgment, but it means the paper's claims of generality ("deep information-seeking agents") are qualified—the method has been validated only on a narrow subset of deep IS tasks (web search and browsing for question answering) with a specific tool configuration. The paper does not attempt to identify which aspects of the method are tool-specific and which are likely to generalize.

The "Lossless" Compression Claim Lacks Direct Validation, and Compression Quality Is Model-Dependent

The constraint. The paper claims that Compressed Reasoning Aggregation performs "lossless" compression with respect to answer-relevant information. The evidence for this claim is indirect: (1) the entity-level redundancy analysis (Figure 2) shows that 91–94% of explored entities on BrowseComp are irrelevant to the final answer, and (2) the compression ratio reaches ~99% token reduction (Figure 5 Right). However, the paper does not directly validate that the compressed reports faithfully preserve all answer-relevant information from the raw trajectories. There is no human evaluation or automated check comparing the information content of compressed reports against original trajectories. Table 4 demonstrates that stronger compression models (GPT-5 > GPT-OSS-120B > GPT-OSS-20B) yield better downstream aggregation performance, which implicitly suggests that weaker models may lose information during compression—making the compression lossy in practice even if the abstract concept is lossless.

The consequence. A practitioner cannot determine how much the reported performance gains depend on the compression model's quality versus the method itself. If a weaker model (e.g., GPT-OSS-20B used for both exploration and compression, as in the same-model configuration of Table 4) fails to extract some effective entities or misrepresents reasoning dependencies, the aggregation stage operates on degraded information and may produce worse answers than a method that could process full trajectories (if context limits permitted). The "lossless" framing could mislead practitioners into assuming that compression quality is guaranteed, when in fact Table 4 shows that upgrading the compression model from GPT-OSS-20B to GPT-5 yields a +6.5 point improvement on BrowseComp—a large gain that would not exist if the weaker model's compression were truly lossless.

Additionally, the structured report format imposes a particular organization (planning → methods → reasoning) that may not fit all reasoning patterns. Trajectories where planning, execution, and synthesis are interleaved (the agent discovers information, revises its plan, discovers more information, revises again) may be poorly represented as a clean three-section structure, causing information about the revision process and dependency evolution to be lost during compression. The paper does not analyze whether the compressed reports accurately capture such iterative reasoning patterns.

Evidence in the paper. Table 4 provides the key evidence that compression quality is model-dependent: aggregation performance monotonically increases with compression model capability. Figure 5 (Right) reports the compression ratio but not a fidelity metric. Section 3.2 defines the compression objective as preserving "key elements essential to answer derivation" without providing a validation method. The entity-level redundancy analysis (Figure 2, Section 2.2) uses GPT-4.1 for entity extraction without validating this extraction against human annotations, so the reported $\Gamma_{\text{red}}$ values may be partly an artifact of the extraction model's biases.

Mitigation status. Not addressed. The paper does not discuss compression fidelity validation, the possibility of information loss during compression, or the dependence of compression quality on model capability. Section 7 does not mention this limitation. Table 4 is presented as a positive result (stronger models improve aggregation) rather than as evidence that the compression is not lossless for weaker models.

Latency and Serial Dependencies Are Not Discussed, Despite the Method Introducing Sequential Bottlenecks

The constraint. PARALLELMUSE introduces at least two serial dependencies that increase wall-clock latency compared to fully parallel best-of-N sampling, even if total FLOPs or token counts are reduced. First, the initial $M=1$ from-scratch rollout must complete before per-step PPL can be computed and branching points selected—no partial rollouts can begin until this initial trajectory finishes. Second, the branching point identification requires computing PPL across all steps of the completed initial trajectory, adding a (potentially small) processing delay before partial rollouts launch. Third, Stage 2 (compressed aggregation) cannot begin until all $N$ trajectories from Stage 1 are complete—the aggregation is a synchronization barrier. In contrast, a naive parallel best-of-N strategy can launch all $N$ trajectories simultaneously and begin answer selection as soon as the first trajectory finishes (or as soon as any trajectory's final answer is generated). The paper's asynchronous rollout engine (Section 3.1) parallelizes branch generation once branching points are identified, but it does not eliminate the initial sequential phase.

The consequence. For latency-sensitive applications (interactive assistants, real-time research tools where users wait for answers), PARALLELMUSE's end-to-end wall-clock time could be substantially longer than naive best-of-N, even if total token consumption is lower. The theoretical speedup model (Equations 4–6) quantifies throughput improvement (total computation per unit time with perfect parallelism) but not latency (time from query to answer). The "Speeduptotal ≈ (1 + Σpj/Σsj) × P" expression describes how many branches can be processed per unit time, not how quickly the first answer is produced. If the initial rollout takes $T_0$ seconds, branching point identification takes $T_{\text{ppl}}$ seconds, the longest partial rollout takes $T_{\text{branch}}$ seconds, and aggregation takes $T_{\text{agg}}$ seconds, the end-to-end latency is approximately $T_0 + T_{\text{ppl}} + T_{\text{branch}} + T_{\text{agg}}$ . For best-of-N, the latency is approximately $\max(T_0, T_1, \ldots, T_N) + T_{\text{selection}}$ —which could be substantially shorter if trajectories vary in length and selection is fast. The paper provides no latency measurements or analysis to help practitioners assess whether the throughput-efficiency gains compensate for potential latency increases.

Evidence in the paper. Section 3.1 describes the asynchronous rollout engine and the theoretical speedup model (Equations 4–6), but exclusively in terms of throughput and token efficiency. Section 4.5 (Figure 5) reports token savings and context compression ratios but not wall-clock time. The paper mentions that Stage 1 branching identification is conducted "in an offline manner to ensure optimal branch selection" (Section 3.1), which acknowledges the sequential nature of the initial phase but does not discuss its latency implications. No latency measurements are reported for any model, benchmark, or budget configuration.

Mitigation status. Not addressed. The paper does not discuss latency as a tradeoff, does not report wall-clock times, and does not suggest latency-optimized variants (e.g., launching partial rollouts progressively as the initial trajectory generates rather than waiting for completion, or speculatively launching branches at predicted high-uncertainty steps). Section 7 does not mention latency. The paper frames PARALLELMUSE entirely through the lens of token and compute efficiency, not time-to-answer, which is a distinct and practically important dimension for deployment.

7. Implications and Future Directions

How This Work Changes the Landscape

PARALLELMUSE represents a conceptual reframing with immediate practical consequences, rather than a paradigm shift. The field already has partial rollout methods for test-time scaling and answer aggregation methods for parallel thinking—both exist independently in the literature. What PARALLELMUSE changes is the axis along which these methods are applied: it argues that for information-seeking agents, the critical distinction is not between "exploration" and "exploitation" in the abstract, but between the functional roles that tokens play in the agent's execution. This reframing has several specific consequences for how future work on agentic test-time compute will be conducted.

First, it establishes that token-homogeneous uncertainty is the wrong signal for agentic branching. Prior partial rollout work (Hou et al., 2025; Dong et al., 2025; Li et al., 2025e) treats all tokens as interchangeable for the purpose of selecting where to branch—high overall perplexity means high exploration potential, period. The paper's preliminary experiments (Section 4.3 footnote) demonstrate that this assumption completely collapses in IS settings: homogeneous partial rollout "performs comparably to full from-scratch rollouts and provides no observable gains." This is a negative result with substantial methodological implications: any future work on tree search, partial rollout, or adaptive computation for agentic systems must account for the functional heterogeneity of generated tokens. Researchers cannot simply port reasoning-domain branching heuristics to agentic settings and expect them to work. The functional-region distinction (reasoning vs. exploration tokens) demonstrated here for Search+Visit agents is likely the simplest case—agents with diverse tool sets will have more complex functional partitions that require correspondingly more sophisticated uncertainty measurement.

Second, it demonstrates that answer aggregation for IS agents should operate on extracted information state graphs, not on raw trajectories or final answers. The finding that Compressed Reasoning Aggregation substantially outperforms both Majority Vote and Weighted Vote across all four benchmarks (Figure 4), while simultaneously reducing context usage by ~99% (Figure 5 Right), provides a concrete existence proof that the trajectory-format bottleneck in answer aggregation is artificial. The bottleneck exists only if one insists on representing trajectories as the raw sequence of tokens used to produce them. Once the problem is reframed as graph extraction (Equation 2: the agent's task is to build $G_{\text{final}} \supseteq I_{\text{answer}}$ ), the apparent tradeoff between reasoning fidelity and context capacity dissolves: the relevant information is compact because most explored entities are irrelevant ( $\Gamma_{\text{red}} \approx 91-94\%$ on BrowseComp). This reframing should reorient future work on agentic answer aggregation away from incremental compression of raw trajectories (e.g., keeping the last K steps) and toward explicit extraction of information-state representations. The structured report format (planning, methods, reasoning) is one possible implementation of such extraction; future work may develop alternative graph formats better suited to tasks with different reasoning structures.

Third, it provides the first systematic evidence that confidence-based answer selection is unreliable in agentic settings with external information injection. The consistent pattern in Table 2—Weighted Vote underperforming Majority Vote on search-heavy benchmarks (BrowseComp, BrowseComp-zh) while performing better on reasoning-heavy benchmarks (HLE) and on models with tool-response calibration training (Tongyi-DR-30B-A3B)—establishes distribution shift from external information as a specific, testable mechanism for confidence miscalibration. This reconciles an apparent contradiction in the literature: some papers find confidence weighting helps for agentic tasks, others find it doesn't. The pattern in Table 2 suggests the discrepancy depends on how much external information the agent integrates and whether the model was trained to calibrate over tool responses. This is a diagnostic contribution: future work evaluating confidence-based methods for agents should control for external information injection as a confounding variable, and model developers should consider tool-response calibration training as a targeted intervention.

Fourth, it changes the conversation around test-time scaling efficiency from "performance vs. cost" to "performance and cost." The paper explicitly disclaims the conventional tradeoff framing: "PARALLELMUSE is not a conventional test-time scaling strategy that improves performance by aggressively sacrificing efficiency" (Section 4.5). Instead, by targeting computation at high-uncertainty functional steps and compressing trajectories before aggregation, it achieves a Pareto improvement over naive parallel thinking—better accuracy with lower token consumption. This is possible because the baseline is fundamentally wasteful: regenerating shared prefixes that the model is confident about, and passing full redundant trajectories to an aggregation stage that can only use a small fraction of their content. This reframing should shift how practitioners think about inference optimization: rather than asking "how much quality can I buy with this budget?", they can ask "what computation is actually wasted in my current pipeline, and how can task structure be exploited to eliminate it?" The technique is specific to IS agents, but the principle of eliminating computation that task structure makes redundant generalizes broadly.

Which research directions become more attractive because of this work:

Functional-region-aware adaptive computation for diverse agent architectures becomes a natural extension. If Search+Visit agents have two functional regions with distinct uncertainty dynamics, agents with 5+ tool types will have more complex functional landscapes—characterizing and exploiting these becomes an empirical research program.
Information-state graph extraction as a general capability becomes attractive beyond answer aggregation. The extracted graphs could serve as training data for self-improvement (the agent learns to plan better by studying which entities it explored versus which it actually used), as verifier inputs (evaluating whether $G_{\text{final}}$ covers the necessary information for the query), or as human-readable explanations.
Calibration over tool responses as a targeted training intervention becomes more attractive given the evidence that Tongyi-DR-30B-A3B's continual pre-training on tool responses (Su et al., 2025) correlates with better confidence weighting performance (Table 2). This is a concrete training recipe that other model developers could adopt.

Which research directions become less attractive:

Token-homogeneous partial rollout for agents is effectively ruled out as a productive direction by the negative result in Section 4.3 (footnote). Future work that proposes partial rollout methods without accounting for functional token distinctions would need to demonstrate that their specific setting lacks the functional heterogeneity that PARALLELMUSE identifies as critical.
Naive scaling of parallel trajectories (e.g., best-of-64 or best-of-256 for IS agents) becomes harder to justify when PARALLELMUSE achieves better results at $N=8$ with lower cost. The burden of proof shifts: a paper proposing to scale $N$ for IS agents without addressing the redundancy PARALLELMUSE exploits would need to show that the additional trajectories provide benefits not capturable by smarter allocation of a smaller budget.

Follow-Up Research This Work Enables

Difficulty-conditioned functional-region selection and budget allocation. The reference paper on compute-optimal test-time scaling demonstrates that optimal strategy selection (e.g., best-of-N vs. beam search) depends critically on problem difficulty, with qualitatively different strategies optimal for easy vs. medium vs. hard problems. PARALLELMUSE currently applies the same functional-region branching strategy to all tasks for a given model (Table 3), with no mechanism for adapting the functional region choice, the number of branching points $k$ , or the budget $N$ based on task difficulty. A natural extension would estimate difficulty from the initial $M$ rollouts—perhaps using the average PPL across steps, the number of distinct entities discovered, or the consistency of answers across the initial branches—and then adapt the branching strategy per difficulty bin. The hypothesis would be that easy tasks (where the agent is already confident and accurate) benefit from minimal branching (small $k$ , reasoning-region only to refine synthesis), while hard tasks (where the agent is uncertain about what to search for) benefit from aggressive exploration-region branching with higher $k$ and more branches per step. The evaluation would produce difficulty-stratified scaling curves analogous to Figure 3 (right) in the reference paper, showing which strategy is optimal for each difficulty quintile on BrowseComp or GAIA. A negative result—finding that difficulty conditioning does not improve over a uniform strategy—would suggest that PPL peaks are task-structural rather than difficulty-dependent, refining our understanding of what drives the observed uncertainty patterns.

Multi-tool functional-region generalization and the "uncertainty fingerprint" hypothesis. The paper's functional-region analysis is conducted exclusively with Search and Visit tools, yielding two functional regions ( $T^r$ and $T^e$ ). An agent with code execution, database queries, API calls, and file operations would partition $T^e$ into multiple sub-regions, each potentially with distinct uncertainty dynamics. A direct extension would instrument an agent with a broader tool set (e.g., the SWE-bench or WebArena tool environments) and compute per-sub-region PPL distributions across task execution, producing an "uncertainty fingerprint" for the agent—a characterization of which functional regions experience uncertainty peaks at which task phases. The experiment would then test whether PARALLELMUSE's branching strategy (select top- $k$ steps in the chosen sub-region) generalizes: does branching in the highest-uncertainty sub-region improve performance relative to homogeneous branching or from-scratch rollouts? The hypothesis is that the optimal sub-region varies by task type—code generation tasks might benefit from branching at tool-execution uncertainty peaks (where the model is unsure which API to call), while data analysis tasks might benefit from branching at reasoning uncertainty peaks (where the model is unsure how to interpret query results). A negative result—finding that with many tool types, functional-region-aware branching provides no benefit over homogeneous branching—would suggest that the benefit observed in this paper is specific to the Search+Visit tool pair's particular uncertainty structure, bounding the method's generality.

Direct measurement of compression fidelity with human annotation. The paper claims lossless compression but provides only indirect evidence (entity-level redundancy ratios computed by GPT-4.1, token compression ratios). A validation study would sample 50–100 trajectories from Stage 1 execution on BrowseComp or GAIA, produce compressed reports using the standard procedure, and have human annotators answer two questions per trajectory: (1) Does the compressed report contain all information necessary to derive and evaluate the answer? (2) Is there any information in the compressed report that was not present in the original trajectory (hallucinated content)? The study would establish a direct fidelity metric (e.g., "93% of reports preserved all answer-relevant information, 2% had minor omissions, 5% had significant omissions") and characterize failure modes (e.g., does compression struggle with trajectories that have iterative plan revision?). Additionally, annotators could compare the compressed reports to the original trajectories to identify systematic patterns in what gets lost—do certain types of evidence (quantitative data, conflicting sources, nuanced hedging language) tend to be omitted? This study would transform the "lossless" claim from a theoretical argument into an empirically validated property with known boundary conditions, and would inform practitioners about when it is safe to rely on compressed aggregation versus when full-trajectory processing is necessary.

Scaling behavior of PARALLELMUSE beyond $N=8$ and the over-optimization question. All experiments use a fixed budget of $N=8$ trajectories. The open question is how PARALLELMUSE's performance scales as $N$ increases, and whether it eventually hits an over-optimization regime analogous to what the reference paper documents for beam search against a PRM. A scaling study would sweep $N \in \{4, 8, 16, 32, 64\}$ on a subset of BrowseComp or GAIA, comparing PARALLELMUSE against (a) Majority Vote, (b) Weighted Vote, and (c) Compressed Reasoning Aggregation applied to $N$ from-scratch rollouts (to isolate the benefit of partial rollout at higher budgets). The key question is whether PARALLELMUSE's advantage over baselines grows (because targeted branching compounds), stays constant (because targeted branching saturates while from-scratch sampling continues to benefit from volume), or reverses (because over-optimization emerges—perhaps the aggregation model starts finding spurious patterns across many compressed reports, or branching at too many points produces trajectories that explore divergent enough paths to confuse the aggregation). A finding that PARALLELMUSE's advantage plateaus at moderate $N$ would suggest it is primarily a budget-efficiency technique for low-to-moderate compute regimes, while a finding that it continues to scale favorably would establish it as a general-purpose replacement for naive parallel thinking at any budget.

The interaction effect between partial rollout and compressed aggregation—are the stages additive or multiplicative? The paper demonstrates that Stage 1 alone (Table 3) and Stage 2 alone (Figure 4) each improve performance, and the combined system (Table 2) improves further. But it does not include the key ablation: comparing the combined system against (a) Stage 1 partial rollout with Majority Vote aggregation and (b) Stage 2 compressed aggregation with from-scratch rollouts. These comparisons would quantify whether the stages are additive (combined gain ≈ Stage 1 gain + Stage 2 gain) or multiplicative (combined gain > sum of individual gains). A multiplicative interaction would support the paper's claim that the two stages are coupled—that partial rollout's targeted exploration produces trajectories that are especially amenable to compressed aggregation because they share high-quality prefixes and diverge at well-chosen points, making the compression task easier and the aggregation's reasoning coherence evaluation more informative. An additive result would suggest that each stage independently improves a different part of the pipeline (exploration quality vs. aggregation quality) without synergy. The experiment would use a single model (e.g., GPT-OSS-120B) on BrowseComp with $N=8$ , creating a 2×2 design: {from-scratch, partial rollout} × {Majority Vote, Compressed Reasoning Aggregation}. The interaction term (partial rollout effect under Majority Vote vs. under Compressed Aggregation) would directly measure synergy.

Tool-response calibration training as a targeted intervention for confidence-based methods. The paper's observation that Weighted Vote performs better on Tongyi-DR-30B-A3B (which received continual pre-training over tool responses; Su et al., 2025) and on HLE (which involves less external information injection) suggests a causal mechanism: training on tool-response distributions improves confidence calibration in agentic settings. A targeted study would take a base model (e.g., GPT-OSS-20B, where Weighted Vote consistently underperforms Majority Vote on search-heavy benchmarks), perform continual pre-training on a corpus of Search and Visit tool responses across diverse tasks, and then measure whether the post-training model's confidence weighting becomes more reliable. The study would test specific calibration metrics (expected calibration error before and after training, both for answer-level confidence and for per-step PPL) and measure downstream answer selection accuracy. A positive result would establish a practical recipe for improving confidence-based methods in agentic settings; a null result would suggest that Tongyi-DR-30B-A3B's advantage comes from other factors (model scale, architecture, data mixture) not captured by the tool-response calibration hypothesis.

Practical Applications and Downstream Use Cases

Cost-efficient batch evaluation for deep research benchmarks and leaderboards. Organizations that evaluate IS agents at scale—running thousands of benchmark tasks to track model improvements, compare candidate training runs, or maintain leaderboards—face linearly scaling costs when using naive parallel thinking (e.g., running 8 independent trajectories per task multiplies the evaluation budget by 8×). PARALLELMUSE's 10–30% reduction in exploratory token consumption (Figure 5 Left) while achieving accuracy improvements of up to 62% (Table 2) translates directly to evaluation cost savings. For a benchmark like BrowseComp with 1,000+ tasks in the full set, reducing per-trajectory token costs by ~20% while achieving higher pass rates means organizations can run more evaluations per dollar or evaluate more experimental configurations within a fixed budget. The method can be deployed as a drop-in wrapper around any existing agent, requiring no model fine-tuning—only access to token-level log-probabilities for PPL computation.

On-device or edge deployment with asymmetric model allocation. The finding in Table 4 that a stronger aggregation model improves results (GPT-5 aggregating GPT-OSS-20B rollouts: 55.5% vs. 49.0% for same-model aggregation) enables a cost-asymmetric deployment architecture: a fleet of small, fast models handles the expensive exploration (Stage 1, which involves dozens of tool calls and long trajectory generation), while a single larger model handles the cheap aggregation (Stage 2, which operates over compressed reports with no tool calls). For on-device deployment, the small model could run locally (exploring the web, gathering information with modest latency), while the aggregation request is sent to a cloud-based larger model only once—the compressed reports are ~1% of the original trajectory size, so the upload cost is negligible. This architecture would be particularly attractive for latency-sensitive applications where the small model can begin exploration immediately without waiting for a cloud round-trip, while still benefiting from a larger model's superior reasoning at the synthesis stage. The specific efficiency numbers: if Stage 1 generates ~50,000 tokens across 8 trajectories (typical for BrowseComp) and the compressed reports total ~500 tokens, the cloud round-trip transmits only 1% of the exploration data.

Self-improvement data generation with higher-quality reasoning traces. When LLMs are used to generate training data for themselves (as in STaR, ReST, or rejection sampling fine-tuning pipelines), the quality of generated trajectories matters at least as much as their correctness—a correct answer with flawed reasoning provides poor training signal. PARALLELMUSE's Compressed Reasoning Aggregation produces structured reports that explicitly decompose solutions into planning, methods, and reasoning, providing higher-quality training data than raw trajectories (which intermix dead ends and irrelevant exploration with useful reasoning). A self-improvement pipeline could: (1) run an agent on training queries with PARALLELMUSE, (2) filter to tasks where PARALLELMUSE's aggregated answer is correct, (3) use the compressed reports from those tasks as fine-tuning data to train the agent on effective planning and reasoning patterns. The structured format would make it easier for the fine-tuning process to distinguish between productive exploration patterns (which should be reinforced) and wasteful ones (which should be suppressed), potentially accelerating self-improvement relative to training on raw trajectories. The entity-level redundancy analysis (Figure 2) quantifies the noise reduction: raw trajectories are 91–94% redundant entities, while compressed reports preserve only effective entities—training on the latter eliminates the majority of irrelevant content that could act as a confounding signal.

Human-in-the-loop verification and debugging of agent behavior with compressed reports. For high-stakes applications where agent outputs must be verified by humans before action (legal research, medical literature review, financial analysis), presenting raw agent trajectories is overwhelming—hundreds of search queries, dozens of page visits, and extensive reasoning intermixed with dead ends. PARALLELMUSE's compressed reports provide a human-digestible summary (planning, methods, reasoning) at ~1% of the original trajectory length. A deployment workflow could: (1) run the agent with PARALLELMUSE to produce both the aggregated answer and the individual compressed reports, (2) present the human verifier with the final answer, the supporting compressed reports, and optionally the ability to drill down into the full trajectory if a specific claim needs verification. The structure of the reports (explicit provenance from specific tool calls to specific subanswers) makes it straightforward for the human to verify claims by tracing them back to their information sources. This workflow would be particularly valuable when deploying IS agents in domains where accuracy requirements are stringent and the cost of human verification, while high, is acceptable for critical decisions.