Source-linked AI summary
Parason: Revealing Subtask and Trial Parallelism in LLM Reasoning
Zhengyang Zhang, Zijian Zhang, Jiaxuan Gao, Shusheng Xu, Yi Wu, Song Han, Ligeng Zhu
TL;DR
Long reasoning traces improve LLM reasoning but create severe latency under sequential decoding, while prior parallel systems largely overlook speculative trial exploration. Parason learns both parallelism forms through structured trajectories, PA-GRPO, and executable tool-call inference, achieving about 1.7× acceleration with competitive accuracy.
Problem
Prior parallel reasoning systems mainly exploit Subtask Parallelism, leaving Trial Parallelism—speculative exploration of uncertain paths—less addressed in long-horizon reasoning.
Method
Parason converts sequential reasoning traces into CFG-structured parallel trajectories and trains models with PA-GRPO to optimize accuracy, latency, and both parallelism modes.
Results
About 1.7× acceleration is achieved across mathematical reasoning benchmarks while maintaining competitive accuracy.
Takeaways & Limitations
Trial Parallelism is a key mechanism for complex mathematical reasoning, and Parason translates it into executable parallel inference.
Takeaways & Limitations
Evaluation mainly covers mathematical reasoning with 8B-scale models, so transfer across domains, model families, and larger sizes remains unclear.
Abstract
from arXiv · showhide
Scaling test-time reasoning has substantially improved the problem-solving ability of large language models (LLMs), but standard autoregressive decoding still executes long reasoning traces sequentially, creating severe latency for difficult tasks (up to days and weeks). Parallel reasoning offers a natural remedy. However, prior systems primarily focus on Subtask Parallelism, where the model learns to decompose a high-level task into smaller chunks that can be solved independently. This approach overlooks another pervasive form of parallelism: Trial Parallelism, where multiple speculative attempts explore, verify, and aggregate competing hypotheses in parallel. In this paper, we introduce Parason, which reveals and learns both forms of parallelism in LLM reasoning. Our analysis identifies Trial Parallelism as the majority of parallelizable reasoning computation (65.5% in DeepSeek-V4's reasoning steps in HLE), and it becomes increasingly dominant on hard problems. Guided by this taxonomy, Parason converts sequential reasoning traces into structured parallel trajectories with a context-free grammar, then trains models with Parallelism-Aware Group Relative Policy Optimization (PA-GRPO), whose reward jointly balances accuracy, latency, and the two parallelism ratios. At inference time, Parason executes the learned parallel structure through tool calls, translating theoretical savings to real-world wall-clock acceleration. Experiments on mathematical reasoning benchmarks including AIME24 and AIME25 show that Parason achieves an average acceleration about 1.7$\times$ while maintaining competitive accuracy.
1 Introduction
Longer test-time reasoning improves LLM problem solving but makes sequential decoding prohibitively slow. Parason addresses this bottleneck by identifying and exploiting both Subtask and Trial Parallelism through structured trajectories, PA-GRPO, and executable inference support.
- Motivation: Standard autoregressive decoding serializes every reasoning token, making long traces a severe latency bottleneck for difficult problems.Reasoning traces can reach hundreds of thousands or millions of tokens, and AlphaProof reportedly requires up to three days on challenging IMO problems.
- Parallelism taxonomy: Trial Parallelism explores competing uncertain paths, whereas Subtask Parallelism decomposes a problem into independent branches whose results are all required.Trial outputs are concatenated into subsequent context for final synthesis rather than selecting only one branch.
- Empirical analysis: 73.8% and 65.5% are the Trial Parallelism ratios for DeepSeek-R1 and DeepSeek-V4 on Humanity’s Last Exam, respectively.Trial Parallelism remains the majority for most models on OpenMath, reaching 68.5% and 58.1% for the same models.
- Approach: Parason converts sequential traces into grammar-constrained parallel trajectories that preserve final semantics and mark executable parallel regions, branches, and summaries.The structure is dispatched through tool calls and integrated into SGLang for real inference-engine execution.
- Approach: PA-GRPO jointly optimizes answer accuracy, longest-token-path latency, and the model’s use of both parallelism modes.The objective extends outcome-based reinforcement learning with latency and parallelism-aware rewards.
- Results: 1.7× average acceleration is achieved while maintaining competitive accuracy across challenging mathematical reasoning benchmarks.Under latency constraints, Parason matches the performance of an 8k-token budget using only 25% of that budget.
2 Related Work
Prior parallel reasoning methods use independent sampling or explicit structures, but most remain centered on decomposing tasks into mandatory subtasks. Parason highlights trial-style exploration as a major form of parallelizable computation, especially in hard reasoning.
- Existing approaches: Sequential test-time scaling improves reasoning but directly increases latency because autoregressive decoding generates every token one after another.Parallel reasoning seeks to preserve test-time computation while shortening the longest token path.
- Independent sampling: Independent sampling methods explore multiple candidate trajectories but do not share intermediate work or expose executable branch structure inside a trace.Examples include self-consistency, verifier-guided Best-of-N, and confidence-based variants.
- Structured parallel reasoning: Structured and adaptive systems split reasoning into trees, graphs, outlines, or sub-agents, but their main mechanism remains subtask-centric.They typically decompose a high-level task, run chunks in parallel, and merge the results.
- Gap and direction: Trial Parallelism accounts for most parallelizable reasoning steps in hard cases by trying uncertain paths, rejecting failures, and retaining useful exploration.The paper reports that Trial Parallelism exceeds 50% for every model on HLE and most models on OpenMath.
- Gap and direction: Parason separates Subtask Parallelism from Trial Parallelism and trains models to exploit both forms explicitly.Its approach treats uncertain-path exploration as parallel search within a single reasoning trace rather than decomposition into mandatory parts.
3 Methodology
Parason models reasoning with two semantic parallelism forms, encodes them in a context-free grammar, and trains execution-aware policies that balance correctness, latency, and parallel structure.
- Parallelism in Reasoning: Parason distinguishes Subtask Parallelism, which solves independent mandatory sub-goals, from Trial Parallelism, which explores competing hypotheses and merges exploratory results.Subtask branches use AND-style aggregation, whereas Trial branches use OR-style exploratory search within one reasoning trace.
- Parallelism in Reasoning: Trial Parallelism launches competing attempts from an uncertain state and concatenates their useful trajectories instead of selecting only one branch.This represents parallel search inside a single reasoning trace and supports revision after dead ends.
- Parallel Trajectory Format: Parason represents mixed reasoning with grammar-constrained tags for parallel regions, outlines, branch types, and thread outcomes.The CFG permits free-form reasoning and nested parallel regions, although training data maintains strict separation between the two modes.
- Parallel Trajectory Format: The format is semantic and engine-parseable: explicit branch types determine merge behavior, while start and stop tags let runtimes dispatch workers without architectural changes.The CFG provides a shared contract for training and inference infrastructure.
- Parallelism-Aware Reinforcement Learning: PA-GRPO extends outcome-based reinforcement learning with rewards for correctness, lower critical-path latency, and useful Subtask and Trial structure.Its reward includes normalized latency and parallelism-ratio signals, plus a clipped acceleration term favoring reduced critical-path latency relative to total generation length.
- Inference Engine Integration: Parason executes parallel regions as tool calls: the runtime parses outlines, dispatches branches as workers, and returns thread outputs to the main trajectory.The implementation uses XGrammar for valid tags and SGLang for tool-call execution.
4 Experiments
Experiments evaluate Parason’s training pipeline, accuracy–latency trade-offs, executable parallelism, and behavior across difficulty levels. Results show competitive accuracy with shorter token paths and roughly 1.7× acceleration.
- Main Results: 84.7% average accuracy is achieved by the best Parason four-benchmark configuration, with leading AIME25 and AMC results among listed systems.PA-GRPO reaches 70.6% on AIME25, 97.5% on AMC, and 94.6% on Math500 across the reported settings.
- Main Results: 34.7% AIME24 accuracy versus 16.8% for SFT only is achieved at a 2,048-token longest-path budget.At 8,192 tokens, the corresponding comparison is 60.3% versus 41.8%, showing gains under fixed token-latency budgets.
- Executable Parallelism: 98.8% trigger ratio and 1.71× acceleration ratio are reached in the Trial sweep, compared with 77.3% and 1.46× before the sweep.SFT alone triggers parallel execution on 69.3% of samples and yields 1.27× token-level acceleration.
- Parallelism Ablations: 1.75× acceleration with 80.3% average accuracy is reached by βsubtask = 0.050, while Trial rewards produce the strongest reported accuracy.The original βtrial = 0.100 setting reaches 84.7% average accuracy; additional runs reduce four-benchmark token latency to 12.1–13.4k versus 14.8k for ThreadWeaver.
- Difficulty Analysis: 1.70–1.74× token-level acceleration remains stable across easy, medium, and hard problems, while saved tokens increase from 8.8k to 21.3k.Measured wall-clock speedups are 1.62×, 1.38×, and 1.47× for easy, medium, and hard problems, respectively.
5 Conclusion
Parason brings parallel processing to sequential LLM reasoning by distinguishing deterministic Subtask Parallelism from speculative Trial Parallelism. Across benchmarks, it reduces token latency by about 1.7× while maintaining comparable accuracy.
- Conclusion: Parason is an algorithm-system co-design framework that combines taxonomy, data curation, CFG-based structure, PA-GRPO training, and inference-engine execution.The framework is presented as a pipeline for efficient parallel reasoning.
- Conclusion: Trial Parallelism is identified as a key mechanism for complex mathematical reasoning, whereas prior work mainly focused on subtask decomposition.The conclusion frames the two schemes as complementary forms of parallel reasoning.
- Conclusion: About 1.7× token-latency reduction is reported across benchmarks while maintaining comparable accuracy.The paper positions this result as evidence for more efficient and scalable reasoning systems.
A Limitations and Future Work
The study’s training and evaluation mainly cover mathematical reasoning with 8B-scale models. Transfer to other domains and broader model families remains unresolved.
- Scope Boundary: Parason’s training and evaluation mainly focus on mathematical reasoning, leaving transfer to real-world agents unclear.The same taxonomy, data curation pipeline, and PA-GRPO objective are not yet established beyond this domain.
- Scope Boundary: Experiments focus on 8B-scale models and do not fully show behavior across model families and sizes.Future work will test more backbones and larger models to assess whether parallelism patterns and latency gains persist.
B Prompts Used for Data Curation
The data-curation prompts first reconstruct logical subproblems, then classify each step as Trial or Subtask. They use explicit output formats and step-linking instructions.
- Subproblem Identification: The first prompt decides whether each segment starts a new subproblem or continues a previous one.New concepts or distinct tasks indicate new subproblems, while added calculations or explanations continue the same concept.
- Parallel Stage Identification: The second prompt classifies each logical step as a Trial Step or Subtask Step.Trial steps introduce uncertain ideas or approaches; Subtask steps belong to a known solution path and contribute directly to the final solution.
- Output Format: Each output preserves step numbering, reports continuation origins when applicable, and places reasons after the step type.Commercial-model summaries marked with “***Step i***” are classified directly, while open-source traces undergo both prompts.
C AIME 2024 Problem Indices
Table 6 documents the AIME 2024 validation problems used for difficulty-based analysis, grouping them into Easy, Mid, and Hard subsets with zero-based indices for reproducibility.
- Table 6 lists the AIME 2024 validation problems used in the difficulty-based analysis reported in Table 5.
- The problems are grouped into Easy, Mid, and Hard subsets according to their difficulty labels.
- The table reports zero-based problem indices for each difficulty subset to support reproducibility.