A Two-Tier Perspective on Inference-Time Parallelism in Multi-Agent LLM Systems

The paper addresses a critical bottleneck in large language model (LLM)-driven multi-agent systems. The authors note that LLM-driven multi-agent systems typically require multiple model invocations and complex coordination during inference, and their execution strategies directly affect system accuracy, latency, and computational cost. They observe that "in practice, however, their inference-time behavior is often dominated by serial coordination: agents repeatedly call LLMs and tools, exchange intermediate states, and append new evidence into a growing context. As the number of execution rounds increases, this serial process can create long critical paths, context expansion and dilution, error propagation, and high wall-clock latency, all of which directly affect system accuracy, efficiency, and cost."

While parallel execution provides a natural way to mitigate these bottlenecks, the authors identify a gap in the literature: existing systems "usually study a particular portion of the design space in isolation. Consequently, it remains unclear how different forms of parallelism relate to one another, what roles they play in the accuracy–latency–cost trade-off, and whether combining them yields complementary or conflicting effects."

The paper proposes viewing inference-time parallelism as a two-tier design space. The two distinct levels are:

1. Replica Parallelism, which explores multiple complete solution paths at the task level to expand solution-space coverage. This is described as primarily trading additional computation for robustness and accuracy.

2. Structural Parallelism, which exposes concurrent execution opportunities within a single solution path by decomposing and scheduling agent and tool calls. This is described as primarily compressing the execution critical path to reduce wall-clock latency.

The authors emphasize that because both tiers consume shared resources and jointly determine the final output, they cannot be understood only as independent optimizations.

Based on this perspective, the authors propose TIPEX (Two-tier Inference-time Parallel EXecution), described as a controllable execution framework that unifies Replica Parallelism and Structural Parallelism for multi-agent systems. TIPEX separates the hierarchy and responsibilities of the two decision layers while supporting flexible combinations of generation, scheduling, and selection strategies under a unified execution semantics. A key design property is that it enables systematic combinations of generation, scheduling, and selection strategies while keeping the underlying agent pipeline unchanged.

This tier addresses uncertainty in LLM-based reasoning by parallelizing solution exploration at the task level and consists of two stages:

Solution Generation includes two strategies:

• Random Isomorphic Generation (RIG): All solution replicas share the same generation instruction... Diversity arises solely from stochastic decoding. This generalizes self-consistency by drawing multiple independent samples.

• Orthogonal Heterogeneous Generation (OHG): The system explicitly synthesizes a set of semantically distinct solution strategies where orthogonal means methodologically diverse rather than mathematically orthogonal. The synthesis promotes diversity along dimensions such as solution pathway, information source preference, verification mechanism, and risk preference.

Solution Selection is a discriminator-based two-stage procedure consisting of validity filtering and comparative selection. It uses a judge operator J that scores answer definiteness, evidence strength, and reasoning consistency. Three orchestration strategies are instantiated:

• Global Selection (GS): waits until all replicas complete and then applies J to the full candidate set.

• First-Valid Early Stopping (FVES): returns the first completed replica that passes validity filtering.

• Top-K Selection (TKS): waits until k valid candidates are available, then applies J only to this subset.

This tier aims to reduce end-to-end latency within a single solution replica by exploiting parallelism among dynamically generated subtasks. Execution is modeled as dynamic DAG expansion and scheduling under partial observability, where each replica maintains a monotonically growing directed acyclic graph with nodes as atomic computation units and edges encoding strict data or logical dependencies. Three scheduling policies are defined:

• Strict Sequential (SS): organizes structural execution in the original agent trajectory order.

• Balanced Parallelism (BP): executing naturally separable subtasks in parallel while maintaining the original high-level task decomposition.

• Aggressive Parallelism (AP): decomposing the workflow into more parallelizable subtasks to expose a larger concurrent execution space.

The authors use the GAIA benchmark as the primary testbed, which covers a diverse set of task modalities, including information retrieval, multimodal reasoning, code execution, and web browsing with three increasing difficulty levels. Magentic-One serves as the baseline, and TIPEX is implemented directly on top of the Magentic-One architecture. Except for the introduction of Replica Parallelism and Structural Parallelism, all other system configurations are kept strictly identical to the baseline. The default settings are "Balanced Parallelism as the default Structural Parallelism strategy, Orthogonal Heterogeneous Generation as the solution generation strategy, set the number of solution instances to n = 3, and use the Top-K Selection strategy with k = ⌈3/2⌉ = 2." The default model is Qwen-Plus, and Oracle Accuracy is introduced as a metric measuring whether at least one correct solution exists in the set of n parallel candidates C, representing the upper bound performance under an ideal (perfect) judge.

"Compared to Magentic-One, parallel configurations achieve higher accuracy and lower end-to-end latency across all three difficulty levels. For example, accuracy improves from approximately 43% to 52–57% on Level 1 tasks, and from around 26% to up to 39% on Level 2 tasks. Meanwhile, execution time is reduced by roughly 15%–40% in most configurations. These gains, however, are accompanied by a substantial increase in token consumption."

"OHG combined with TKS yields the most balanced performance. OHG with GS achieves high accuracy but incurs higher latency and token cost; RIG combined with FVES can perform strongly in some cases, but suffers from instability due to judgment errors and coordination overhead. In contrast, OHG with TKS achieves near-optimal accuracy with lower latency than GS, providing a robust balance between solution-space coverage, judgment reliability, and execution efficiency."

"Across all difficulty levels, OHG-based configurations show a consistently smaller gap between actual accuracy and Oracle Accuracy compared to RIG-based configurations, indicating more stable and predictable behavior during the selection phase. The authors hypothesize that OHG introduces more discriminative solution perspectives during parallel generation, thereby reducing the decision burden on the judge."

"Parallel execution on Level 2 tasks yields substantial latency reduction (from ∼320s to 170–280s), indicating effective Structural Parallelism. Compared to Level 3, Level 2 tasks exhibit larger accuracy gains (from ∼26% to up to 39%), suggesting that parallel generation and selection can still effectively translate expanded solution-space coverage into performance improvements. Overall, medium-difficulty tasks represent a 'golden stage' where Structural Parallelism is well-exploited and Replica Parallelism remains effective, leading to the strongest synergistic effects."

"Starting from Level 2, latency reductions become more pronounced: Magentic-One requires approximately 320s, while parallel configurations reduce this to around 170–280s. This trend further amplifies on Level 3, suggesting that as task complexity increases, more internal parallelism is exposed and Structural Parallelism increasingly compresses critical execution paths."

"Regardless of whether GS, TKS, or FVES is used, actual accuracy remains consistently below the corresponding Oracle Accuracy across tasks and configurations. This persistent gap indicates that judge quality plays a decisive role in determining final system performance."

"Multiple solution instances consistently improve accuracy across difficulty levels... Structural Parallelism effectively reduces end-to-end latency. With n = 3, switching from SS to BP or AP significantly shortens execution time. However, accuracy drops notably under AP... Overall, Replica Parallelism improves accuracy while Structural Parallelism reduces latency, and the two complement each other under different constraints."

"Increasing the number of solution instances improves accuracy, but with rapidly diminishing returns. Increasing n from 1 to 3 yields stable accuracy gains, while further increasing to n = 5 brings marginal or even negative improvements, despite significantly higher token consumption. Regarding structural parallelism, increasing structural parallelism from BP to AP leads to substantial accuracy drops and increased token consumption. Although AP further shortens execution time in some cases, these gains are unstable and often offset by redundant execution and scheduling overhead, resulting in degraded overall performance."

The joint analysis shows the two tiers interact rather than contribute additively. Specifically, "Structural Parallelism buffers the time cost of replica scaling: as replicas increase, BP and AP mitigate latency overhead more effectively than SS. Meanwhile, accuracy gains from replica scaling are clearly modulated by the structural policy. Under BP, accuracy rises from 29% to 37% as replicas grow, whereas under the more aggressive AP it drops from 28% to 25%, indicating that excessive structural parallelism can undermine or even negate the accuracy gains from replication."

"Replica Parallelism and Structural Parallelism are not independent knobs whose benefits simply add together. BP can reduce the latency cost of replica scaling while preserving the accuracy gains from broader solution exploration. AP, however, can undermine those gains by introducing redundant execution or weakening information integration."

"The benefits of parallel execution vary across task difficulty and task type. Harder tasks expose longer critical paths and more parallelizable structures... Table 3 shows that web and file tasks favor combined parallelism, code tasks favor structural decomposition, and multimodal tasks rely more on replica-level exploration."

Moderate replica parallelism combined with balanced structural parallelism yields the most robust trade-off among accuracy, latency, and computational cost.

"On GAIA2-mini using DeepSeek-v3.2 as the backbone... The same qualitative patterns remain: Replica Parallelism expands solution-space coverage, Structural Parallelism compresses wall-clock time. The stronger gains on GAIA2 are accompanied by higher token costs, reinforcing that inference-time parallelism should be understood as a joint accuracy–latency–cost trade-off rather than a free improvement."

The authors categorize 104 failed cases across GAIA L1–L3 and find:

• Reasoning/computation error (64/104): The system applies incorrect reasoning steps, uses invalid formulas, or makes numerical mistakes despite retrieving relevant information.

• Information retrieval error (24/104): The system fails to locate, extract, or verify critical evidence from web pages, files, or multimodal inputs.

• Error propagation (11/104): Early mistakes in decomposition, retrieval, or intermediate reasoning are carried forward and affect later agents or subtasks.

• Redundant execution (5/104): Parallel branches produce overlapping or weakly complementary outputs, increasing cost without providing additional evidence.

They conclude that parallelism alone cannot replace stronger reasoning, retrieval, and verification mechanisms in complex agent workflows.

The paper concludes that "the benefits of inference-time parallelism are inherently regime-dependent, and that optimal performance emerges from carefully balanced configurations that respect both task structure and coordination overhead, rather than from indiscriminate increases in parallel execution. The authors advocate that practical deployments should treat parallelism as a tunable control knob rather than a maximization target."

Here are specific improvements for multi-agent LLM systems, derived directly from the paper’s findings, and what the improved system will be able to do.

Improvement 1: Adaptive two-tier parallelism controller

Implement a runtime controller that dynamically sets the number of solution replicas (n) and the structural scheduling policy (SS, BP, AP) based on an online estimate of task difficulty and available token budget. The controller uses hard-task signals (e.g., number of failed retries, retrieved evidence ambiguity, or DAG depth growth) to switch from low-overhead settings (n=1, SS) for simple tasks to balanced settings (n=3, BP) for medium tasks, and to increase structural parallelism only when long critical paths are detected.

The improved system can automatically adjust its own parallelization strategy per task, avoiding both wasteful over-parallelization on easy tasks and under-parallelization on hard tasks, while respecting a token-cost ceiling.

Improvement 2: Orthogonal heterogeneous generation (OHG) with discriminative diversity

Replace naive random sampling with explicit synthesis of semantically diverse solution strategies. The system will generate a small set of orthogonal approaches by varying solution pathway (e.g., top-down decomposition vs. bottom-up evidence aggregation), information source preference (web-first vs. file-first vs. code-first), verification mechanism (self-consistency vs. tool-based checking), and risk preference (aggressive inference vs. conservative evidence collection). This diversity is used for all replicas when n>1.

The improved system can explore a broader solution space with fewer replicas, and its outputs are more distinguishable during selection, making the judge more reliable and reducing the accuracy gap between practical and oracle performance.

Improvement 3: Two-stage judge with comparative selection (TKS) and confidence gating

Design the selection stage as: (a) validity filtering — discard replicas that lack definite answers, sufficient evidence, or internally consistent reasoning; (b) comparative selection — apply a judge to score the remaining candidates on answer definiteness, evidence strength, and reasoning consistency, but only after k = ceil(n/2) valid candidates are available (Top-K Selection). Add an early-exit: if a replica passes validity filtering with very high confidence (e.g., score above a robust threshold), return it immediately without waiting for more candidates.

The improved system can return high-quality answers faster than waiting for all replicas, maintain accuracy close to the global-selection upper bound, and avoid the instability caused by premature first-valid returns.

Improvement 4: Balanced parallelism (BP) as the default structural policy, with guardrails against aggressive decomposition

Use Balanced Parallelism: within each solution replica, keep the original high-level task decomposition unchanged, but execute naturally independent subtasks (e.g., separate retrieval queries, independent tool calls, disjoint code executions) concurrently. Explicitly forbid Aggressive Parallelism unless a task has been independently verified to contain weakly-coupled subtasks; otherwise, measure and warn that AP increases token consumption and degrades accuracy due to redundant execution and weaker information integration.

The improved system can reduce wall-clock latency by 15–40% without sacrificing accuracy, and avoids the accuracy collapse (e.g., from 37% down to 25%) that aggressive parallelism causes.

Improvement 5: Cross-tier synergy scheduling for medium-difficulty tasks

Implement a special golden stage mode for medium-difficulty tasks (where structural parallelism is well-exploited and replica exploration is still effective): use n=3 replicas with BP and Top-K selection. For hard tasks, increase structural parallelism moderately and keep n=2–3; for easy tasks, use n=1 or n=2 with SS to minimize cost. Additionally, track task type (web/file vs. code vs. multimodal) and bias the configuration: web/file tasks use combined replica+structural parallelism; code tasks rely more on structural decomposition; multimodal tasks rely more on replica-level exploration.

The improved system can achieve the strongest accuracy–latency–cost trade-offs by recognizing that parallelism benefits are regime-dependent and by matching the execution strategy to the task’s structure and difficulty.

Improvement 6: Token-cost-aware replica scaling with diminishing returns detection

During runtime, monitor incremental accuracy gain per additional replica. If increasing n from 3 to 5 yields marginal or negative accuracy improvement (as observed in the paper), the system stops scaling and reallocates the saved token budget to improving retrieval or reasoning verification (e.g., adding a second retrieval pass or a verification step).

The improved system can avoid wasting tokens on non-productive replica expansion, and can instead invest resources in fixing the dominant failure modes (reasoning/computation errors and information retrieval errors), which the paper found to account for 88/104 of failures.

Improvement 7: Verification and error-propagation prevention loops

Because the failure analysis showed that 64/104 failures are reasoning/computation errors and 11/104 are error propagation, add a lightweight verification stage after each critical subtask in the DAG: check intermediate numerical outputs, code execution return codes, and factual consistency of retrieved evidence before allowing downstream agents to proceed. If an error is detected, trigger a targeted retry within the same replica instead of spawning a new replica.

The improved system can catch mistakes early, preventing them from polluting later agents’ context and reducing the need for replica-level redundancy to compensate for early errors.

Improvement 8: Judge calibration with oracle-accuracy monitoring

In deployment, periodically evaluate the judge against Oracle Accuracy (whether at least one correct candidate exists in the parallel set). If the gap between actual accuracy and oracle accuracy grows beyond a threshold, the system automatically adjusts the judge’s scoring weights (e.g., increase evidence-strength weight) or switches to a different judge model.

The improved system can self-monitor its selection quality and compensate for judge weaknesses, ensuring that gains from parallel exploration are not lost during the final selection step.

Large language model (LLM)-driven multi-agent systems typically require multiple model invocations and complex coordination during inference, and their execution strategies directly affect system accuracy, latency, and computational cost. Parallel execution provides a means to improve inference-time efficiency. From the perspective of inference-time execution, this paper models parallelism in multi-agent systems as two distinct levels of decision processes: Replica Parallelism, which explores multiple complete solution paths at the task level, and Structural Parallelism, which enables concurrent execution within a single solution path through task decomposition. However, the roles of different forms of parallelism and their interrelationships still lack systematic study in terms of unified organization and coordination. We therefore propose TIPEX, a controllable execution framework that unifies these two levels of parallelism and coordinates their roles within the inference process under a unified execution semantics while supporting systematic combinations and analyses of different parallel strategies and parameter configurations. Systematic experiments on the GAIA benchmark demonstrate that inference-time parallelism can significantly improve accuracy and reduce end-to-end latency at the cost of increased token consumption. Further analysis shows that Replica and Structural Parallelism exhibit complementary effects across task complexities, with tasks of intermediate difficulty benefiting most from their coordination, while overly aggressive parallel strategies do not necessarily yield better performance.