🤖 AI

Parason: Revealing Subtask and Trial Parallelism in LLM Reasoning

The paper introduces Parason, a framework that significantly accelerates LLM reasoning by identifying and leveraging both subtask and trial parallelism through a structured grammar and a specialized training algorithm, achieving approximately 1.7x speedup on complex mathematical benchmarks while maintaining accuracy.

Original authors: Zhengyang Zhang, Zijian Zhang, Jiaxuan Gao, Shusheng Xu, Yi Wu, Song Han, Ligeng Zhu

Published 2026-08-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhengyang Zhang, Zijian Zhang, Jiaxuan Gao, Shusheng Xu, Yi Wu, Song Han, Ligeng Zhu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Large language models have become remarkably skilled at solving complex problems, from cracking difficult math puzzles to writing sophisticated code. This ability often comes from a simple strategy: letting the model think for a longer time. By generating a long, step-by-step chain of thoughts before giving an answer, these systems can navigate tricky logic and avoid simple mistakes. However, this approach has a significant physical limitation. The standard way these models work is like a single person reading a book one word at a time, strictly in order. Every thought must wait for the previous one to finish. When a problem is extremely hard, the chain of thoughts can stretch to hundreds of thousands of words, meaning the user might wait minutes, hours, or even days for a single answer. This delay makes it impractical for real-time tools like coding assistants or interactive tutors, where speed matters as much as accuracy.

Researchers have long suspected that the answer lies in parallel thinking. Instead of one long line of thought, imagine a team of experts working on different parts of a problem at the same time. Some existing systems have tried to do this by breaking a big task into smaller, independent pieces, solving each piece separately, and then combining the results. While helpful, this method misses a crucial part of how intelligent reasoning actually works. When facing a truly difficult problem, a smart thinker does not just break the problem down; they also try out different ideas, see which ones fail, and keep the ones that work. They explore multiple paths simultaneously, discarding the dead ends and following the promising ones. This paper introduces a new system called Parason that teaches language models to do exactly this, turning the slow, single-file process of thinking into a fast, multi-lane highway.

The researchers began by analyzing thousands of reasoning traces from advanced models to see exactly how they think. They discovered that the thinking process is not just a single line of steps, but a mix of two very different types of activity. The first type is like a construction crew dividing a building project: one team lays the foundation, another frames the walls, and a third installs the roof. All these tasks are necessary, and they can be done at the same time. The researchers call this subtask parallelism. The second type is more like a detective testing several theories at once. The detective tries one suspect, realizes it doesn't fit, and immediately tries another, while a colleague checks a third possibility. Only one of these paths needs to be correct to solve the case, but the detective must explore them all to find the right one. The researchers call this trial parallelism.

What they found was surprising. In the hardest problems, the "detective" style of thinking—trying many different ideas and discarding the failures—makes up the majority of the work. In fact, for some of the most advanced models, this trial-based exploration accounts for more than two-thirds of the reasoning steps. Previous systems that only focused on breaking tasks into smaller pieces were essentially ignoring the most common way these models solve hard problems. They were optimizing for the construction crew while the real work was being done by the detectives.

To fix this, the team built a framework that teaches models to recognize when to split a task and when to try multiple ideas at once. They created a special set of rules, like a structured language, that allows the model to say, "Here are three different ways to solve this, and I will try them all at the same time." The system then runs these different attempts in parallel, collecting the results. If one attempt fails, the model simply moves on to the next one without having to wait for the failed attempt to finish before starting the next. This is a significant shift from the old way, where the model would have to finish one idea, realize it was wrong, and then start the next one, one after another.

The training process used a reward system that encouraged the model to be both correct and fast. The model was praised not just for getting the right answer, but for organizing its thoughts in a way that allowed the computer to do the work faster. By running these parallel branches simultaneously, the system effectively reduced the time it took to reach a conclusion. In tests on difficult math competitions, the new system achieved an average speedup of about 1.7 times compared to the standard sequential approach, while maintaining the same high level of accuracy. This means a problem that might have taken ten minutes to solve now takes roughly six minutes, without sacrificing the quality of the solution.

The researchers also observed that the harder the problem, the more this parallel approach helped. On the most difficult questions, the amount of work saved was the greatest. This is because hard problems naturally generate more dead ends and require more exploration of different possibilities. By allowing the model to explore these possibilities side-by-side rather than one after another, the system turns what was once a long, slow wait into a much more efficient process. The study suggests that the future of artificial intelligence reasoning is not just about thinking longer, but about thinking in many directions at once, mimicking the way human experts tackle the world's most complex challenges.

Technical Summary: Parason – Revealing Subtask- and Trial Parallelism in LLM Reasoning

1. Problem Statement

Recent advances in Large Language Model (LLM) reasoning, such as Chain-of-Thought (CoT) prompting and systems like OpenAI o1 and DeepSeek-R1, have demonstrated that increasing test-time compute significantly improves performance on complex mathematical and logical tasks. However, standard autoregressive decoding executes these long reasoning traces sequentially. This creates a severe latency bottleneck for difficult problems, where reasoning traces can grow to hundreds of thousands or even millions of tokens, rendering "think longer" strategies impractical for interactive agents and latency-sensitive applications.

While parallel reasoning offers a natural remedy, existing systems primarily focus on Subtask Parallelism, where a high-level task is decomposed into independent chunks (e.g., calculating different parts of a sum). This approach overlooks a pervasive form of parallelism: Trial Parallelism. In Trial Parallelism, the model explores multiple speculative, competing hypotheses in parallel to verify which path works, a behavior common in hard reasoning where the correct path is unknown. Prior methods often treat all parallel branches as independent full traces or fail to distinguish between necessary subtasks and speculative trials, leading to redundant computation or a lack of control over latency.

2. Methodology: The Parason Framework

The authors introduce Parason, a training-and-inference co-design framework that reveals and exploits both Subtask and Trial Parallelism. The methodology consists of three core components:

A. Semantic Taxonomy of Parallel Reasoning

The paper distinguishes two complementary forms of parallelism based on their execution semantics:

Subtask Parallelism (AND-branch): The problem is decomposed into independent sub-goals ( $g_1, \dots, g_k$ ). All branches are necessary, and their results must be aggregated to form the final answer. This is the dominant form in prior adaptive parallel systems.
Trial Parallelism (OR-branch): The model faces uncertainty about the solution path. It launches competing attempts ( $a_1, \dots, a_k$ ) to test different hypotheses. Unlike subtasks, not all branches are necessary; the system aggregates the exploratory trajectories into the reasoning history to keep the useful results. This mirrors the "try, detect dead end, and revise" behavior of strong reasoners.

Empirical analysis of reasoning traces from models like DeepSeek-R1 and DeepSeek-V4 on the Humanity's Last Exam (HLE) reveals that Trial Parallelism accounts for the majority (65.5%–73.8%) of parallelizable reasoning steps, exceeding Subtask Parallelism significantly on hard problems.

B. Structured Parallel Trajectory Format (CFG)

To make these modes executable, Parason defines a Context-Free Grammar (CFG) that converts sequential reasoning traces into structured parallel trajectories.

Tags: The format uses specific tags: <Parallel> to mark a region, <Outlines> to describe the region's purpose, <Subtask> and <Trial> to mark branch types, and <Thread> to store branch outcomes.
Execution: This structure allows an inference engine to parse the trace, dispatch independent workers for each branch (subtask or trial), and return the results to the main trajectory without modifying the model architecture. The system integrates with SGLang and uses XGrammar to enforce valid tag nesting.

C. Parallelism-Aware Reinforcement Learning (PA-GRPO)

The authors propose PA-GRPO, a multi-objective reinforcement learning algorithm that optimizes for accuracy, latency, and parallelism usage. The reward function ( $R_i$ ) for a trajectory $i$ is defined as:
$R_i = -1 + 2 \times \mathbb{1}(\text{correct}_i) \times \left( 1 - \alpha f\left(\frac{T_i - \mu_T}{\sigma_T}\right) + \beta_{\text{subtask}} f\left(\frac{R^{\text{subtask}}_i - \mu_s}{\sigma_s}\right) + \beta_{\text{trial}} f\left(\frac{R^{\text{trial}}_i - \mu_r}{\sigma_r}\right) + \min(\rho \cdot \eta(s), \rho_{\text{clip}}) \right)$

Correctness: The primary signal; incorrect answers receive a negative base reward.
Latency Penalty: Penalizes the critical-path token count ( $T_i$ ) to encourage shorter wall-clock times.
Parallelism Incentives: $\beta_{\text{subtask}}$ and $\beta_{\text{trial}}$ encourage the model to utilize the respective parallelism modes. The authors note that these target different goals: Trial Parallelism trades total tokens for search width (improving accuracy), while Subtask Parallelism compresses the longest path (reducing latency).
Acceleration Reward: A clipped term favoring reductions in the critical path relative to total generation length.

3. Key Contributions

Taxonomy of Parallel Reasoning: The paper identifies Trial Parallelism as a missing component in current parallel reasoning systems, demonstrating that it constitutes the majority of parallelizable computation in hard reasoning tasks (over 50% in HLE and OpenMath datasets).
Parason Framework: A system that converts sequential traces into grammar-constrained parallel trajectories executable by standard inference engines via tool calls, avoiding the need for deep runtime modifications.
PA-GRPO Algorithm: A reinforcement learning objective that jointly optimizes for answer correctness, latency along the longest token path, and the balanced utilization of Subtask and Trial parallelism.
Empirical Validation: Experiments show that Parason achieves an average acceleration of approximately 1.7× on mathematical benchmarks (AIME24, AIME25, Math500, AMC) while maintaining competitive accuracy. Under latency-constrained settings (e.g., 2048 tokens), Parason significantly outperforms standard Supervised Fine-Tuning (SFT) baselines.

4. Results

Accuracy: Parason achieves state-of-the-art results among listed parallel systems on AIME25 (70.6%) and AMC (97.5%) using an 8B model, outperforming larger 32B baselines in some metrics.
Latency and Acceleration:
- The system achieves an average token-level acceleration ratio of 1.7×.
- In latency-constrained scenarios (2048 token budget), the best Subtask-aware model reaches 34.7% accuracy on AIME24, compared to 16.8% for SFT-only baselines.
- Harder questions yield more parallelizable work; while total generated tokens increase with difficulty, the longest token path grows much slower, maintaining a stable 1.70–1.74× acceleration ratio across difficulty levels.
Ablation: The study shows that Trial rewards ( $\beta_{\text{trial}}$ ) are most effective for improving accuracy, while Subtask rewards ( $\beta_{\text{subtask}}$ ) are more effective for reducing latency.

5. Significance and Claims

The paper claims that Parason represents a shift from viewing reasoning solely as a sequential process or a simple decomposition of tasks. By explicitly recognizing and exploiting Trial Parallelism, the framework addresses the "missing piece" in current parallel reasoning systems.

The authors state that their work:

Bridges the gap between theory and practice: Unlike prior work that reports theoretical speedups or requires complex engine modifications, Parason uses a CFG and tool-call execution that is directly runnable in modern inference engines like SGLang.
Improves the latency-accuracy Pareto frontier: It demonstrates that difficult reasoning does not necessarily require longer serial waiting times; much of the computation can be moved off the critical path.
Highlights the nature of hard reasoning: The findings suggest that hard reasoning is not just about decomposition (Subtask) but also about exploring and refining uncertain paths (Trial), a behavior that previous systems largely ignored.

The paper concludes by noting limitations, specifically that the current evaluation focuses on mathematical reasoning and 8B-scale models, and that future work is needed to validate these patterns across broader domains and model sizes.