PaperlayerView exact revision on arXiv

Source-linked AI summary

ThreadWeaver: Adaptive Threading for Efficient Parallel Reasoning in Language Models

Long Lian, Sida Wang, Felix Juefei-Xu, Tsu-Jui Fu, Xiuyu Li, Adam Yala, Trevor Darrell, Alane Suhr, Yuandong Tian, Xi Victoria Lin

arXiv:2512.07843v2cs.LGcs.AIcs.CL

TL;DR

Long autoregressive reasoning can incur substantial latency, while adaptive parallel reasoning has yet to match strong sequential models on complex problems. ThreadWeaver combines parallel-trajectory data generation, trie-based execution, and parallelization-aware reinforcement learning; across six math benchmarks it reports comparable accuracy with reduced token latency.

  • Problem

    Autoregressive decoding creates substantial latency for long reasoning, and adaptive parallel approaches have not demonstrated performance comparable to strong sequential models on complex problems.

    Source: §1 · p. 1

  • Method

    ThreadWeaver combines a two-stage parallel-trajectory generator, trie-based training and inference co-design, and parallelization-aware reinforcement learning.

    Source: §1 · p. 2

  • Results

    Across six math reasoning benchmarks, ThreadWeaver achieved accuracy comparable to cutting-edge thinking models and up to a 1.53× token-level latency reduction versus sequential baselines.

    Source: §7 · p. 9

  • Takeaways & Limitations

    The results establish a Pareto frontier between efficiency and reasoning performance for ThreadWeaver.

    Source: §7 · p. 9

    Acceleration is bounded by sequential trace portions, branch imbalance, and orchestration overhead, so ThreadWeaver is not universal for intrinsically sequential tasks.

    Source: §5.4 · p. 7

Abstract

from arXiv · show

Scaling inference-time computation has enabled Large Language Models (LLMs) to achieve strong reasoning performance, but their inherently sequential decoding incurs substantial latency, motivating parallelization of the generation process. However, existing parallel reasoning approaches suffer from performance degradation compared to their sequential counterparts, and often rely on specialized inference engines. We introduce ThreadWeaver, a framework for adaptive parallel reasoning that matches the accuracy of comparably sized sequential reasoning models while significantly reducing inference latency via three key innovations: 1) a two-stage parallel trajectory generator that produces high-quality parallel chain-of-thought data for supervised fine-tuning; 2) a trie-based rollout design that enables parallel reasoning on any off-the-shelf autoregressive inference engine; and 3) a parallelization-aware reinforcement learning framework that trains the model to balance reasoning accuracy with effective parallelization. Across six challenging math reasoning benchmarks, ThreadWeaver trained on top of Qwen3-8B achieves performance on par with cutting-edge sequential reasoning models (79.9% on AIME24 and 71.9% on average) while delivering up to 1.53x speedup in token latency, establishing a new Pareto frontier between accuracy and efficiency.

1 Introduction

Long autoregressive reasoning incurs substantial latency, while adaptive parallel methods have struggled to match strong sequential models. ThreadWeaver combines structured trajectory generation, trie-based execution, and parallelization-aware reinforcement learning, reporting comparable benchmark accuracy with lower token latency.

1 Introduction

  • Autoregressive decoding makes each token depend on all previous tokens, so longer reasoning trajectories increase inference latency.Parallel reasoning offers an additional test-time scaling axis beyond extending sequence length.Source: §1 · p. 1
  • ThreadWeaver addresses scarce training trajectories, difficult deployment on standard inference engines, and added reinforcement-learning challenges in branch-level advantages and rollout consistency.These challenges include prior datasets’ limited scale and diversity and inference approaches that modify model or engine components.Source: §1 · pp. 1–2
  • Its three innovations are a two-stage parallel-trajectory generator, trie-based training and inference co-design, and parallelization-aware GRPO to jointly optimize accuracy and latency reduction.The framework targets problems requiring long chain-of-thoughts and assumes abundant compute for reducing reasoning latency.Source: §1 · p. 2
  • Across six math benchmarks, ThreadWeaver averaged 71.9% accuracy versus Qwen3-8B’s 72.2% and achieved up to 1.53× token-latency speedup.The reported speedups include 1.14× on AIME24 and 1.53× on Minerva Math.Source: §1 · p. 2

2 Model

ThreadWeaver represents reasoning as fork-join trajectories, executes thread bodies concurrently over standard inference engines, and packs these trajectories into trie-based training sequences.

2.1 Parallel Trajectory Format

  • A parallel block places outlines and multiple threads inside a fork-join structure; threads are generated independently, while the surrounding trajectory remains sequential.The described format restricts trajectories to a single parallelization level, though the techniques are said to generalize to nested branches.Source: §2.1 · pp. 2–3, Figure 2 · p. 3

2.2 Parallel Inference

  • The orchestrator decodes outlines sequentially, launches one completion request per thread in parallel, then joins the results and resumes sequential decoding on a standard inference engine.The design also supports choosing parallel mode for low latency or autoregressive mode for high throughput.Source: Figure 3 · p. 3, §2.2 · p. 3

2.3 Efficient Training with Trie-based Sequence Merging

  • Trie-based training extracts inference context-completion units, packs them under a shared prefix, and traverses the trie with ancestor-only attention and loss only on completion tokens.This preserves thread isolation during training and allows ordinary autoregressive inference to recover a valid subsequence of the trajectory.Source: §2.3 · pp. 3–4, Figure 4 · p. 4

3 Parallel Trajectory Curation for Supervised Fine-tuning

ThreadWeaver constructs parallel supervised fine-tuning data through LLM-assisted rewriting followed by self-training with reward-based filtering.

LLM rewriting

  • A five-step LLM annotation and rewriting pipeline converted 959 of 53k sequential Qwen3-8B trajectories into parallelized cold-start examples.The pipeline identifies parallelizable spans, defines thread boundaries, rewrites for clarity and independence, generates outlines, and validates format while aiming to preserve the original reasoning semantics.Source: §3 · p. 4

Self-training with reward-based filtering

  • After cold-start fine-tuning, parallel rollouts on 53k prompts were filtered for format and answer correctness to build trajectories aligned with the model’s own generation patterns.The authors describe this filtered corpus as high-quality SFT data for reliable parallel rollout in later reinforcement learning.Source: §3 · p. 4

4 Reinforcement Learning

P-GRPO adapts GRPO to parallel rollouts by broadcasting a trajectory-level advantage across its units and masking context tokens from the loss. Its reward combines answer correctness with a conditional acceleration bonus, while mean-centering avoids instability from standard-deviation normalization.

4 Reinforcement Learning

  • GRPO computes advantages using within-prompt reward normalization, with the prompt-group mean and standard deviation defined for the sampled trajectories.The method describes a small ε for stability; its parallel-reward variant instead uses simple mean-centering.Source: §4 · p. 4, §4.2 · p. 5

4.1 P-GRPO: GRPO with Parallel Rollout

  • A single scalar reward per trajectory supplies the same group-normalized advantage to all units across its parallel threads.The authors report that this broadcast is mathematically justified and stabilizes training without per-branch credit heuristics.Source: §4.1 · p. 5
  • The loss masks context tokens, so only completion-token log probabilities contribute and each generated token receives loss at most once.Training units pair context with the corresponding completion, matching the test-time execution distribution and avoiding a train–inference gap.Source: §4.1 · pp. 4–5

4.2 Parallelization-Aware Reward

  • The reward adds answer correctness to a softly scaled acceleration bonus, which is granted only when the answer is correct.The acceleration ratio uses the longest thread's sequence length as token latency and the total trajectory token count.Source: §4.2 · p. 5
  • Mean-centering replaces standard-deviation normalization because the latter destabilizes the multi-term reward and can favor acceleration over correctness.When all rollouts are correct, mean-centering removes the correctness signal, while standard-deviation normalization cancels the acceleration scale.Source: §4.2 · p. 5
  • P-GRPO learns parallel behavior that transfers directly to off-the-shelf autoregressive engines, alongside correctness and acceleration improvements.The rollout uses the paper's parallel inference scheme.Source: §4.2 · p. 5

5 Experiments

Across six math benchmarks, ThreadWeaver matches the sequential GRPO baseline’s accuracy while reducing mean critical-path length; experiments compare adaptive methods, problem-level acceleration, and training choices.

5.1 Setup

  • Evaluation uses Qwen3-8B across six math benchmarks, with a three-stage training pipeline and the same RL setup for the sequential baseline.The stages are fine-tuning, self-training, and P-GRPO reinforcement learning.Source: §5.1 · p. 6

5.3 Comparisons

  • 79.9% accuracy on AIME24 exceeds Multiverse’s up to 53.8% and Parallel-R1 variants’ up to 19.4%, alongside higher self-parallelism speedup and activation ratio.ThreadWeaver also outperforms Multiverse, built on Qwen2.5-32B, in accuracy and measured self-parallelism speedup.Source: §5.3 · p. 6, Table 2 · p. 7

5.2 Main Results

  • 71.9% vs. 72.2% average accuracy accompanies mean critical-path length falling from 15.1k to 13.2k tokens, with up to 1.53× average speedup.The comparison is between ThreadWeaver and the sequential GRPO baseline on Qwen3-8B.Source: §5.2 · p. 6, Table 1 · p. 7

5.4 Acceleration Distribution Analysis

  • Most per-problem speedup ratios exceed 1.0×, but vary widely: gains reach 1.47× on AIME24 and 3.05× on MATH500, while some problems show mild slowdowns.Figure 5 summarizes per-problem speedup distributions relative to the sequential baseline.Source: §5.4 · pp. 6–7, Figure 5 · p. 7
  • Sequential trace portions, branch imbalance, and orchestration overhead bound acceleration; the speed-accuracy Pareto improvement applies to problems with exploitable parallel structure, not intrinsically sequential tasks.The analysis relates these bounds to Amdahl’s law.Source: §5.4 · p. 7

5.5 Ablations

  • 1.14× wall-clock speedup was measured on 50 MATH problems using four GPUs for orchestration versus single-GPU autoregressive decoding.The wall-clock gain is lower than token-latency gains because of system overhead.Source: §5.5 · p. 7
  • Mean-centering rather than standard-deviation normalization preserves the intended correctness-acceleration balance, yielding higher accuracy and shorter critical paths.Source: §5.5 · p. 8, Table 4 · p. 8
  • Without self-training, accuracy is 77.9% and latency 17.6k; with self-training plus parallel rollout, ThreadWeaver reaches 79.9% accuracy and 16.9k token latency.The ablation reports that both parallel rollout during RL and self-training improve accuracy and efficiency.Source: §5.5 · p. 8

6 Related work

Prior parallel reasoning ranges from independent sampling to structured search, but these approaches can waste computation or lack scalable learned coordination. ThreadWeaver is presented as adaptive branching within one reasoning trajectory, compatible with standard inference engines.

Test-Time Scaling

  • Longer autoregressive reasoning raises latency, motivating test-time parallelism as an alternative scaling dimension.The cited discussion describes OpenAI o1 and DeepSeek R1 as scaling reasoning-trajectory length via reinforcement learning.Source: §6 · p. 8

Parallel Reasoning

  • Independent self-consistency threads can duplicate reasoning, while structured agentic methods often depend on hand-crafted structures and lack gradient-based optimization across branches.ThreadWeaver instead learns branching and joining within a single reasoning trajectory.Source: §6 · pp. 8–9

Adaptive Parallel Reasoning

  • Training-based adaptive methods differ in their use of RL, data, base models, and inference-engine requirements; ThreadWeaver uses thinking models and standard sequential engines.The passage notes that Parallel-R1 and NPR have shorter chains of thought than ThreadWeaver, while Multiverse and NPR require inference-engine modifications.Source: §6 · pp. 8–9

7 Conclusion

ThreadWeaver combines parallel-trajectory data construction, trie-based deployment, and P-GRPO to pursue accuracy and acceleration together. The accompanying background defines intra-trajectory parallelism, frames latency through a speed-accuracy Pareto view, and reviews GRPO.

7 Conclusion

  • Across six math benchmarks, ThreadWeaver achieves up to a 1.53× token-level latency reduction while matching the accuracy of cutting-edge thinking models.The conclusion presents this as a new Pareto frontier between efficiency and reasoning performance.Source: §7 · p. 9

A.1 Adaptive Parallel Reasoning

  • Adaptive parallel reasoning branches and rejoins threads inside one trajectory, coordinating decomposable subproblems along a single solution path.A model dynamically decides when to exploit parallelizable structure, such as independent cases or alternative solution paths.Source: §A.1 · p. 12

A.2 Test-time Speed-Accuracy Pareto Frontier

  • The speed-accuracy Pareto view compares end-to-end answer latency, proxied by the longest thread’s token count, against a sequential model with comparable reasoning capability.Self-consistency can retain whole-trajectory critical-path latency and redundant computation, whereas aligned intra-run decomposition can shorten the longest thread.Source: §A.2 · p. 12

A.3 GRPO Preliminary

  • GRPO normalizes trajectory rewards within each prompt to produce comparable advantages, and fully on-policy updates make clipping inactive in the described setting.The preliminaries describe a score-function objective and token normalization across sequences in the batch.Source: §A.3 · pp. 12–13

B Derivations for P-GRPO

The derivations justify P-GRPO’s on-policy score-function update, factor its trajectory probability across generated segments, and show why one trajectory advantage can be broadcast across completion tokens.

B.1 From clipped GRPO to the score-function objective

  • With a single fully on-policy update, the importance ratio is one and clipping is inactive, reducing clipped GRPO to a score-function gradient.The derivation identifies the resulting estimator as REINFORCE with a baseline.Source: §B.1 · p. 13

B.2 Factorization of Parallel Reasoning Trajectories

  • A parallel trajectory’s log-probability factors into the log-probabilities of its completion segments, each conditioned on its own context.This factorization applies across parallel structures, including shared outline and later thread segments branching from a common trie node.Source: §B.2 · p. 13

B.3 Broadcasted Credit Assignment

  • Broadcasting one trajectory advantage to every completion token computes the summed segment gradients, making it the policy-gradient estimator for the parallel trajectory reward.The implementation estimates the expectation over a batch and applies the same scalar advantage to each completion segment.Source: §B.3 · p. 14

C Implementation Details

The implementation builds training data in stages, merges parallel segments into packed trie sequences, and runs an orchestrated rollout pipeline on standard inference infrastructure. Evaluation covers six math datasets under a 40k-token budget across parallel branches.

Training data

  • From 36,296 valid Qwen3-8B trajectories, 1,000 were rewritten and 959 passed filtering for SFT; self-training then generated and filtered trajectories for a second fine-tuning stage.The initial valid pool represents 68.1% of the 53,291 Polaris prompts; the second-stage trajectories use correctness and structural-validity checks.Source: C Implementation Details · pp. 14–16

Trie-based sequence merging

  • Trie merging packs context-completion units into one sequence with ancestor-only attention, applying loss only to completion tokens and supporting multiple parallel blocks.The full prompt-to-completion trajectory is also treated as a unit to allow standard autoregressive decoding.Source: C Implementation Details · p. 14, Figure 6 · p. 15

Inference orchestration

  • The orchestrator decodes outlines sequentially, runs their threads independently, joins their text, then continues until another outline block or end of sequence.Threads do not attend to one another during independent generation; the implementation can use common completion APIs and serving optimizations without architecture changes.Source: C Implementation Details · pp. 14–15

SFT

  • Initial SFT runs for eight epochs; self-training SFT uses the same hyperparameters for one epoch, with a maximum sequence length of 40,960 tokens.The initial SFT uses AdamW, a 1 × 10−5 starting learning rate, and batch size 16.Source: C Implementation Details · pp. 15–16

Reinforcement learning

  • P-GRPO samples each prompt eight times per batch, normalizes sequence-level advantages within prompts, and trains for 350 optimization steps.The RL setup uses batch size 128 and a 5 × 10−6 Adam learning rate, with no KL penalty.Source: C Implementation Details · p. 16

Evaluation setup

  • Evaluation spans AIME24, AIME25, AMC23, MATH500, Minerva Math, and OlympiadBench, with 40k total tokens across parallel branches.Source: C Implementation Details · p. 16

D Dataset Statistics

GPT-5 rewrites add substantial parallel structure to sequential trajectories, while model-generated self-training produces a larger corpus that better reflects what the student can reliably parallelize.

D Dataset Statistics

  • The original trajectories are long and purely sequential, with no acceleration from parallelization; the passage then introduces rewriting with GPT-5 but gives no thread-count average.Source: D Dataset Statistics · p. 16
  • About 77% of rewritten tokens lie in parallel blocks, with a critical path about 26% shorter than total token count despite slightly greater overall length.The dataset’s idealized self-parallelism speedup is roughly 1.35×.Source: D Dataset Statistics · p. 17
  • Self-training yields 17,491 trajectories and a 1.22× self-parallelism speedup, reflecting parallel structures the student can generate without global hindsight.The traces are filtered for structural validity, answer correctness, length, and acceleration constraints.Source: D Dataset Statistics · p. 17
  • The two-stage dataset pipeline provides supervision for supervised fine-tuning and prepares the model for reinforcement learning.Table 7’s format-correctness measure checks proper closure of opened Parallel blocks and well-formed thread markers.Source: D Dataset Statistics · p. 17, Table 7 · p. 17

E.1 Performance Across Training Stages

Across the AIME 24 training stages, self-training improves structural format correctness, and reinforcement learning further improves accuracy, with the strongest reported accuracy after RL on the larger dataset.

E.1 Performance Across Training Stages

  • 77.9% and 79.9% accuracy are reported after reinforcement learning from the two SFT starting points, respectively.RL improves accuracy in both cases; format correctness decreases slightly when RL starts from the smaller dataset.Source: §E.1 · p. 17
  • 17k-example self-training raises format correctness to 77.0% while maintaining similar accuracy, compared with 56.4% format correctness after the first 959-example SFT at 74.5% accuracy.Format correctness is a proxy for structural stability, not a direct determinant of answer accuracy.Source: §E.1 · p. 17
  • The first SFT on 959 examples yields 74.5% accuracy and 56.4% format correctness, indicating limited structural mastery from the smaller supervised dataset.Table 7 measures AIME 24 accuracy and format correctness across training stages.Source: §E.1 · p. 17

E.2 Cold-start with Sequential Data Mixture

Neither sequential–parallel cold-start curriculum improves over parallel-only SFT in this setting, while ThreadWeaver’s parallel SFT retains most of the base models’ reasoning performance.

E.2 Cold-start with Sequential Data Mixture

  • Neither staged nor gradual sequential–parallel mixing improves over parallel-only SFT on AIME 24.The authors hypothesize that continued sequential-data training reinforces Qwen3-8B’s existing autoregressive style and slows adaptation to the parallel format.Source: Table 8 · p. 18, §E.2 · pp. 18–19
  • The staged curriculum runs two fully sequential epochs, four mixed epochs, then two fully parallel epochs; the gradual curriculum ramps parallel data across eight epochs.The staged mixed epochs move from 90% sequential/10% parallel through two 50/50 epochs to 10% sequential/90% parallel.Source: §E.2 · p. 18

E.3 ThreadWeaver Reuses Existing Reasoning Capabilities for Parallel Reasoning

  • The AIME 24 performance gap between parallel SFT and autoregressive SFT is roughly 5% for both Qwen3-4B and Qwen3-8B models.The comparison uses 959 GPT-5-rewritten trajectories for parallel SFT versus 1k correct sequential trajectories for autoregressive SFT; the stronger 8B base’s gains carry into the parallel setting.Source: §E.3 · p. 19, Table 9 · p. 19

E.4.1 CRITICAL-PATH SPEEDUP AGAINST SEQUENTIAL BASELINE AS ROBUST EFFICIENCY MEASUREMENT

Self-parallelism speedup can overstate acceleration relative to a sequential baseline, so critical-path comparison against that baseline is the more relevant deployment measure.

E.4.1 CRITICAL-PATH SPEEDUP AGAINST SEQUENTIAL BASELINE AS ROBUST EFFICIENCY MEASUREMENT

  • The reported measures distinguish sequential-baseline speedup from self-parallelism speedup; sequential-baseline token latency equals total generated tokens.Self-parallelism compares total output length with the parallel critical path; baseline speedup compares baseline and ThreadWeaver critical paths.Source: §E.4.1 · p. 19
  • On AIME 25, 1.18× self-parallelism speedup corresponds to only 1.03× improvement over the sequential baseline.In three of six benchmarks, self-parallelism speedup significantly exceeds speedup measured against sequential baselines.Source: §E.4.1 · p. 19
  • Self-parallelism speedup is incomplete for deployment because outline-token generation and thread redundancy add overhead.Threads operate without visibility into one another.Source: §E.4.1 · p. 19

E.4.2 HIGH-QUALITY SFT DATA IS CRITICAL FOR MODEL PERFORMANCE

The ablations link SFT performance to model-data alignment and quality, while a qualitative trace illustrates parallel exploration and unfiltered speedup distributions remain similar to filtered results.

E.4.2 HIGH-QUALITY SFT DATA IS CRITICAL FOR MODEL PERFORMANCE

  • Under identical fine-tuning settings, Multiverse yields lower performance despite its stronger teacher, indicating dataset-model compatibility matters more than teacher strength in this setting.Source: §E.4.2 · pp. 19–20
  • Parallel-R1's GSM8K-derived Parallel-GSM8K accompanies substantially lower performance; its RL gains remain modest, suggesting RL cannot fully offset lower-quality SFT.Source: §E.4.2 · p. 20

E.5 Qualitative Study

  • In a MATH500 trigonometry example, ThreadWeaver explores distinct strategies, runs independent subgoals in parallel—including numerical checking and exact derivation—and then integrates branch results.Source: §E.5 · p. 20

E.6 Per-problem Speedup Without Filtering

  • Without correctness filtering, per-problem speedup distributions remain similar to filtered results, with most mass above 1.0×; upper-tail maxima may reflect incorrect early termination.Source: §E.6 · p. 22

E.7 Error Analysis: Repetition in Branches

These parts examine how ThreadWeaver structures parallel-reasoning demonstrations, including converting sequential trajectories into parallelizable supervision and addressing duplicate computations and mixed branch roles. They also cover sanitization, filtering, safeguards against reward hacking, and future directions in hardware-aware and interactive parallelization.

E.7 Error Analysis: Repetition in Branches

  • In the 42! failure case, the answer is correct, but redundant computations and mixed branch roles leave the parallel threads without genuinely complementary reasoning.The paths were intended to divide the main 42! calculation and checks on smaller factorials, but each blends both tasks, undermining the intended division of labor.Source: §E.7 · p. 22

F Reasoning Trajectory Annotation Pipeline for ThreadWeaver

  • The pipeline turns Qwen3-8B reasoning trajectories into parallelizable supervision through five stages: identify parallel structures, canonicalize threads, revise context transitions, regenerate branch outlines, and filter failures.Filtering removes samples with failed rewriting or format errors to produce the final training corpus.Source: F Reasoning Trajectory Annotation… · pp. 24–25
  • Parallel groups are formed only for adjacent steps without logical dependencies, with line-range annotations preserved so structures remain traceable to the original reasoning.The pipeline also examines substeps within main steps for valid parallel groupings, reusing their original line ranges.Source: F Reasoning Trajectory Annotation… · pp. 27–28
  • The annotation pipeline restructures trajectories into validated parallel threads, removes forbidden cross-branch references, rebuilds independent planning outlines, and filters artifacts that violate structural constraints.Its programmatic restructuring preserves line-number references; the review uses minimal substring replacements, and the outlines are derived from preceding context. [Not included: marker]Source: F Reasoning Trajectory Annotation… · pp. 32, 34, 35

G Discussion: Reward Hacking

  • Experiments showed no clear evidence of reward hacking; SFT priors, a 40k-token trajectory cap, and a clipped, conservative acceleration reward help keep correctness dominant.A length penalty could better address future reward hacking, but normalization is challenging; the bounded acceleration ratio is normalized to each trajectory’s structure. [Not included: marker]Source: G Discussion: Reward Hacking · p. 35

H.1 Topology-aware Parallelized Reasoning

  • ThreadWeaver’s topology-agnostic policy cannot adapt thread counts to hardware, risking underuse or oversubscription; future work could condition its plans on hardware profiles and SLOs.Proposed training would randomize hardware profiles and use latency- and cost-aware rewards to map problem structures to device resources. [Not included: marker]Source: §H.1 · p. 36

H.2 Parallelizing Interactions Beyond Reasoning

  • Future work could extend parallel reasoning to interactive environments, where agents pursue complementary tasks but require stronger coordination and synchronization mechanisms.Suggested applications include software engineering, scientific discovery, robotics, and large-scale planning; hierarchical coordination, role-based delegation, or resource locking are possible mechanisms.Source: §H.2 · p. 36

Related papers

Loading 2512.07843v2…