Source-linked AI summary
ParaTempo: Efficient Parallel Reasoning via Temporal Confidence
Xuteng Zhang, Wenhao Zeng, Xiaodong Gu, Chao Hu, Haotian Lin, Yuling Shi, Min Wang, Beijun Shen
TL;DR
Parallel reasoning incurs rising inference costs because fixed-budget methods overlook heterogeneous progress across branches. ParaTempo uses temporal confidence for asynchronous branch control, reducing latency by 21.8–32.2% and token usage by 18.1–30.3% while maintaining competitive accuracy.
Problem
Fixed-budget parallel reasoning overlooks heterogeneous branch progress, motivating dynamic allocation of computation across trajectories.
Method
ParaTempo uses temporally aggregated intermediate answer distributions to guide asynchronous branch pruning, retirement, forking, and confidence-weighted termination.
Results
21.8–32.2% lower average latency and 18.1–30.3% fewer generated tokens were achieved across four benchmarks while maintaining competitive accuracy.
Takeaways & Limitations
ParaTempo provides an asynchronous alternative to fixed-budget reasoning that allocates computation according to branch convergence while preserving parallel reasoning benefits.
Abstract
from arXiv · showhide
Parallel reasoning improves the accuracy and robustness of large reasoning models by exploring multiple solution paths, but its computational cost grows with reasoning depth and branch count. Existing methods for managing these parallel paths typically rely on final-answer consensus, local token confidence, or isolated intermediate probes. However, these signals are often delayed, weakly tied to actual reasoning progress, or too noisy for dynamic, branch-level control. To address these limitations, we introduce ParaTempo, a training-free asynchronous parallel reasoning framework. ParaTempo is driven by temporal confidence, a branch-local measure of answer-space convergence. Each branch is periodically probed for a tentative answer probability distribution, and temporal confidence quantifies how sharply the recent intermediate probes concentrate on a dominant answer. Once sufficient evidence has accumulated, ParaTempo drives its entire control process from this single signal: low-confidence branches are pruned, branches that persistently commit to their dominant answer are retired early, freed computation is reallocated by forking new branches, and generation stops globally once the confidence-weighted vote concentrates. Without requiring synchronization among reasoning trajectories, ParaTempo adaptively allocates computation based on branch-level convergence. Experiments on challenging mathematical and scientific reasoning benchmarks show that ParaTempo reduces average latency by 21.8-32.2% and total token usage by 18.1-30.3% while maintaining competitive accuracy. Moreover, temporal confidence exhibits stronger temporal stability and predictive power for future branch convergence than token-level and instantaneous signals.
1 Introduction
ParaTempo addresses the inefficiency of fixed-budget parallel reasoning with asynchronous, branch-local control driven by temporal confidence. It adaptively prunes, retires, and forks branches while reducing inference cost and preserving competitive accuracy.
- Motivation: Parallel reasoning improves reliability by exploring multiple solution trajectories, but inference cost scales with branch count and reasoning depth.Fixed-budget methods allocate identical computation to every branch and aggregate answers only after termination.
- ParaTempo: ParaTempo asynchronously uses temporal confidence for adaptive computation allocation through branch pruning, retirement, forking, and global early termination.The framework updates branch-local evidence without requiring synchronized global barriers.
- Motivation: Heterogeneous trajectory progress causes converged branches to generate redundant tokens while less promising branches consume computation without clear future utility.This motivates branch-level rather than uniform computation allocation.
- ParaTempo: Temporal confidence tracks whether a branch consistently concentrates probability mass on a dominant answer region or scatters it across alternatives.It is estimated by periodically probing active branches and aggregating intermediate answer distributions over time.
- Results: 21.8–32.2% lower average latency and 18.1–30.3% fewer total generated tokens versus standard self-consistency were achieved while maintaining competitive accuracy.The evaluation covered four mathematical and scientific reasoning benchmarks using Qwen3.5-35B-A3B and GPT-OSS-20B.
2 Problem Formulation
Parallel reasoning generates multiple independent branches, but fixed budgets waste computation because branches converge at different rates. The problem is formulated as online resource allocation: dynamically continue, terminate, or expand branches while preserving fixed-budget accuracy and reducing inference cost.
- Problem Formulation: Parallel reasoning generates K independent branches, each maintaining a reasoning prefix before producing an answer.The input problem is x, the model is M, and branch i is denoted r_i with prefix r_i,t.
- Problem Formulation: Fixed-budget execution allocates equal generation budgets to all branches and aggregates final answers only after completion.This can force early-converging branches to generate redundant tokens while uncertain branches receive insufficient exploration.
- Problem Formulation: Parallel reasoning is formulated as online resource allocation over branch continuation, early termination, and redistribution of released computation.The controller must dynamically choose among these actions while preserving reliable final answer aggregation.
- Problem Formulation: The controller objective is to minimize expected inference cost while maintaining the expected accuracy of fixed-budget execution.The formulation compares a parallel reasoning controller π with the standard fixed-budget controller π_fixed using accuracy A(·) and cost C(·).
3 A Preliminary Study
The preliminary study evaluates whether token-level uncertainty and answer-level confidence support reliable branch-level control through temporal stability and prediction of future answer convergence. It finds that token-level signals are poorly aligned with answer progress, while instantaneous answer confidence is vulnerable to transient changes, motivating temporally aggregated, answer-aligned, branch-local control.
- Evaluation Setup: The study probes independent reasoning branches periodically and evaluates token-level uncertainty and answer-level confidence for temporal stability and future convergence prediction.Experiments use K = 16 branches per problem across Qwen3.5-35B-A3B and GPT-OSS-20B on AIME 2026, HMMT November 2025, and HMMT February 2026.
- Token-Level Signals Lack Answer-Space Alignment: Token-level entropy and perplexity fluctuate most across probes because of local linguistic factors rather than underlying answer-state changes.Their association with future answer stability is weak, with |ρ| ≤0.13 and AUC ≤0.58.
- Instantaneous Answer Confidence Is Sensitive to Transient Changes: Standardized volatility 0.26 shows that instantaneous answer confidence remains sensitive to transient changes in evolving reasoning trajectories.Temporary preference for incorrect or unstable hypotheses can cause probe distributions to fluctuate, limiting long-term convergence assessment.
- Implications: Effective online control signals should align with candidate-answer space, aggregate evidence over multiple observations, and support independent branch-level updates.These properties address the limitations of surface-level statistics, single-probe confidence, and controls requiring cross-branch synchronization.
4 Methodology
ParaTempo is a training-free asynchronous framework that uses temporal confidence, an online measure of answer-space convergence, to allocate computation across reasoning branches. It aggregates intermediate answer probes to control continuation, pruning, retirement, forking, and confidence-weighted global termination.
- Branch-Level Control: Branches asynchronously continue decoding, retire after convergence, prune when confidence is insufficient, or fork to reallocate released computation.Pruned branches release computation, retired branches preserve voting evidence, and forked branches inherit a promising donor prefix with an independent sampling seed.
- Temporal Confidence: Temporal confidence aggregates recent intermediate answer distributions to measure how strongly a branch’s answer space converges over time.Sliding-window aggregation suppresses transient probe fluctuations and emphasizes persistent answer preferences.
- Temporal Confidence: Exponentiated negative entropy makes temporal confidence approach 1 for consistent single-answer probes and decrease as probability spreads across alternatives.It represents the inverse effective number of competing answer candidates.
- Branch-Level Control: A warmup phase calibrates an instance-specific pruning threshold from observed temporal-confidence values instead of using a manually specified global threshold.After warmup, pruning requires both insufficient confidence and sufficient post-fork probe history to avoid premature removal.
- Global Consensus: Confidence-weighted voting over eligible active and retired branches determines when generation terminates and produces the final prediction.The eligible voting set includes branches with valid temporal-confidence estimates, while generation otherwise continues until no active branch remains or the computation budget is exhausted.
5 Experiments
Experiments evaluate ParaTempo across challenging mathematical and scientific reasoning benchmarks using two long-chain-of-thought models and compare it with parallel, adaptive, and sequential controllers. Results show competitive accuracy with lower inference cost, while temporal confidence supports stable, predictive branch control and effective pruning, retirement, and forking.
- Experimental Setup: ParaTempo is evaluated on AIME 2026, HMMT November 2025, HMMT February 2026, and GPQA Diamond using Qwen3.5-35B-A3B and GPT-OSS-20B.The benchmarks cover long-horizon symbolic derivation and knowledge-intensive multi-step scientific inference.
- Main Results: ParaTempo matches or exceeds Parallel-Probe across evaluated latency ranges and reaches SC@16-comparable or higher accuracy at the highest budgets with lower latency.Figure 3 reports this latency–accuracy frontier on AIME26 and HMMT25.
- Signal Analysis: Temporal confidence produces smoother trajectories than token-level uncertainty and instantaneous answer confidence, while higher signal values correlate positively with future branch stability.These properties support using temporal confidence for online branch-level decisions.
- Ablations: Removing retirement increases total tokens and latency while reducing accuracy by 6.6 points; removing pruning increases latency marginally, and disabling forking removes budget reallocation.The ablations separately test pruning, early retirement, and computation reallocation through forking.
6 Related Work
Related work improves reasoning by allocating additional test-time computation and by exploring multiple trajectories in parallel. However, existing approaches include fixed rollout budgets and trajectory-reduction methods based on similarity or predicted answer equivalence.
- Efficient Test-Time Scaling: Test-time scaling allocates additional inference computation to longer trajectories or diverse sampled solutions, while self-consistency aggregates answers from multiple reasoning paths.Self-consistency can use fixed rollout budgets that ignore variation in problem difficulty and branch utility.
- Parallel Reasoning: Parallel reasoning explores multiple trajectories concurrently, spanning skeleton-based expansion, adaptive scaling and pruning, online similarity-based chain removal, and answer-equivalence clustering.These approaches include Slim-SC, which removes redundant chains using inter-trace similarity, and DeepPrune, which clusters partial traces using predicted answer equivalence.
7 Conclusion
ParaTempo is a training-free asynchronous framework for efficient parallel test-time reasoning, centered on temporal confidence as a branch-local convergence signal. This signal enables adaptive branch-level computation through pruning, retirement, exploration, and confidence-weighted termination.
- ParaTempo introduces a training-free asynchronous framework for efficient parallel test-time reasoning.
- Temporal confidence captures answer evolution through temporally aggregated intermediate answer distributions.
- Temporal confidence enables adaptive branch-level computation allocation through pruning, retirement, exploration, and confidence-weighted termination.