PaperlayerView exact revision on arXiv

Source-linked AI summary

SPRINT: Enabling Interleaved Planning and Parallelized Execution in Reasoning Models

Emil Biju, Shayan Talaei, Zhemin Huang, Mohammadreza Pourreza, Azalia Mirhoseini, Amin Saberi

arXiv:2506.05745v2cs.AIcs.LG

TL;DR

Long sequential reasoning outputs increase inference time, while existing parallel approaches can lack coordination or flexibility. SPRINT fine-tunes reasoning models on curated trajectories to plan and execute independent subtasks in parallel. Across math and out-of-domain evaluations, it matches or exceeds reasoning fine-tuned performance while reducing sequential tokens.

  • Problem

    Reasoning models generate lengthy sequential outputs, while parallel methods may lack coordination or flexible search structures.

    Source: §1 · p. 1

  • Method

    SPRINT curates reasoning trajectories into structured plans and parallel executions, then fine-tunes models to identify independent subtasks dynamically.

    Source: §1 · p. 2

  • Results

    Across MATH-500, GPQA, and Countdown, SPRINT matches or exceeds reasoning fine-tuned performance, with up to 39% fewer sequential tokens on problems requiring more than 8,000 tokens.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The evaluations show that SPRINT can reduce sequential generation while retaining reasoning-model performance on math and out-of-domain tasks.

    Source: §1 · p. 2, §6 · p. 10

    Realizing wall-clock speedups requires hardware-aware caching and high-bandwidth GPU interconnects, and parallel tasks require corresponding GPUs; limited resources prevented optimal hardware-accelerated decoding.

    Source: §5 · pp. 9–10

Abstract

from arXiv · show

Large reasoning models (LRMs) excel at complex reasoning tasks but typically generate lengthy sequential chains-of-thought, resulting in long inference times before arriving at the final answer. To address this challenge, we introduce SPRINT, a novel post-training and inference-time framework designed to enable LRMs to dynamically identify and exploit opportunities for parallelization during their reasoning process. SPRINT incorporates an innovative data curation pipeline that reorganizes natural language reasoning trajectories into structured rounds of long-horizon planning and parallel execution. By fine-tuning LRMs on a small amount of such curated data, the models learn to dynamically identify independent subtasks within extended reasoning processes and effectively execute them in parallel. Through extensive evaluations, we demonstrate that models fine-tuned with the SPRINT framework match the performance of reasoning models on complex domains such as mathematics while generating up to 39% fewer sequential tokens on problems requiring more than 8,000 output tokens. Finally, we observe consistent results transferred to two out-of-distribution tasks, namely GPQA and Countdown, with up to 45% and 65% reduction in average sequential tokens respectively for longer reasoning trajectories, while matching the performance of the fine-tuned reasoning model.

1 Introduction

SPRINT addresses the long sequential outputs of reasoning models and the coordination or flexibility limits of existing parallel methods. It reorganizes reasoning trajectories into plans and parallel executions so fine-tuned models can identify independent subtasks dynamically.

1 Introduction

  • SPRINT combines sequential reasoning with parallel inference, using a planner to propose independent tasks and executors to perform them concurrently.The planner uses the cumulative reasoning context, and simultaneous execution accelerates lengthy tasks.Source: §1 · p. 2
  • Fine-tuning on only 1,700 curated demonstrations teaches the model to recognize and exploit parallel reasoning opportunities while closely preserving the original data distribution.Source: §1 · p. 2
  • On MATH-500, SPRINT raises Deepseek-R1-distill-7B accuracy from 89.1% to 92.5%, exceeding RFT at 91%, while using 440 fewer sequential tokens on average.For problems requiring more than 8,000 tokens under RFT, sequential-token savings reach 39%.Source: §1 · p. 2
  • The data-curation pipeline converts natural-language reasoning trajectories into structured fine-tuning data through step extraction, DAG creation, packing, filtering, and reformatting.Source: §1 · p. 2
  • On GPQA and Countdown, SPRINT matches the reasoning fine-tuned model while saving sequential tokens by about 45% and 65%, respectively.Source: §1 · p. 2

2 Related Work

Prior approaches use long sequential chains, uncoordinated parallel paths, or fixed search and planning structures. SPRINT instead trains models to dynamically allocate computation between serial and parallel reasoning within a solution trajectory.

2 Related Work

  • Long chains of thought improve reasoning but produce long sequential outputs that increase latency and slow inference.Source: §2 · p. 3
  • Tree-, graph-, forest-, and atom-based search and multi-agent methods rely on fixed patterns or protocols, whereas SPRINT autonomously allocates computation across serial and parallel subtasks.Source: §2 · p. 3
  • Task-decomposition and iterative-refinement methods primarily execute sequentially, while SPRINT supports dynamic parallel planning.Source: §2 · p. 3
  • Best-of-N and self-consistency lack coordination among paths, while SoT and APAR assume independent subtasks and can underperform when later reasoning depends on earlier computations.Source: §2 · p. 3
  • PASTA, Hogwild! Inference, and APR have limits in multi-step planning, task distribution, or general-purpose data curation; SPRINT targets dynamic inference structuring for general reasoning tasks.Source: §2 · pp. 3–4

3 Methodology

SPRINT couples iterative planner–executor inference with a curation pipeline that converts reasoning trajectories into staged planning and execution examples for fine-tuning. The stages preserve dependencies while grouping work that can proceed concurrently.

3.1 Interleaved Planning and Parallel Execution at Inference Time

  • At inference, a planner uses cumulative context to issue independent subtasks, executors run them concurrently, and their outputs return to the planner for another stage or termination.The process continues until the planner produces the final answer.Source: §3.1 · pp. 4–5, Figure 3 · p. 6

3.2 Training Reasoning Models for SPRINT Framework

  • The curation pipeline extracts planning and execution steps from reasoning trajectories, merging very short executions into plan-only steps to discourage trivial executor calls.Plan-only steps have no explicit execution component.Source: §3.2 · p. 5, Figure 2 · p. 5
  • A prompted model identifies dependencies among steps, represented as a DAG whose nodes are steps and whose edges encode dependencies.The pipeline uses GPT-4o-mini for dependency identification.Source: §3.2 · p. 5
  • Packing groups steps into stages for concurrent plans and executions, allowing a child step to share its plan-only parent’s stage while maintaining context availability.Stage assignment accounts for whether a parent has an execution component.Source: §3.2 · p. 6
  • Within each stage, plans are concatenated in original order, while the execution set excludes plan-only steps.The stage-wise training examples represent plans and executions separately.Source: §3.2 · p. 6
  • Training retains trajectories with at least a 1.5 steps-to-stages ratio, reformats them as tagged stage-wise plans and executions, and fine-tunes the reasoning model on these patterns.The model learns to propose independent parallelizable tasks from prior plans and executions.Source: §3.2 · p. 6

4 Experiments

Experiments compare SPRINT with reasoning and parallel-sampling baselines on MATH-500 and two out-of-domain benchmarks, measuring accuracy and sequential tokens. SPRINT reports higher accuracy with fewer sequential tokens than RFT, with larger savings on longer trajectories.

4.1 Experimental Setup

  • Training uses approximately 1,700 curated trajectories from 6,000; evaluation covers MATH-500, GPQA-Diamond, and Countdown against base/RFT and repeated-sampling baselines using accuracy and sequential-token metrics.The base model and RFT are DeepSeek-R1-Distill-Qwen-7B; RFT uses the same trajectories as SPRINT.Source: §4.1 · p. 7

4.2 Results

  • 92.5% accuracy and 440 (∼15%) fewer sequential tokens on average: SPRINT slightly outperforms RFT on MATH-500.Figure 4 compares accuracy and sequential token counts across methods.Source: Figure 4 · p. 8, Figure 5 · p. 8
  • SPRINT replans across stages using prior execution results; SoT's independent subtasks produce nearly three times SPRINT's total tokens, while harder problems require more stages.SPRINT generates more plans early, as it explores strategies and identifies subtasks; later stages are more deterministic.Source: §4.2 · pp. 8–9
  • 53.5% reduction (2,284 vs. 4,917 tokens) on Countdown; on GPQA-Diamond, SPRINT reaches 51.0% accuracy and reduces sequential tokens 10.8% versus RFT.SPRINT was fine-tuned on math reasoning, not trajectories from Countdown.Source: Table 2 · p. 8, §4.2 · p. 9
  • 39% reduction in sequential tokens when RFT requires more than 8,000 tokens on average; short trajectories instead incur a 5% increase.The short-trajectory increase comes from additional prompts and plan/execution tags.Source: §4.2 · p. 9
  • 9% estimated runtime reduction on MATH-500 (36.92s vs. 40.57s) and 38% on the longer-reasoning subset (74.47s vs. 120.54s).The estimates add time-to-first-token overhead to decoding time.Source: §4.2 · p. 9

5 Limitations and Future work

SPRINT reduces sequential-token counts, but practical wall-clock gains depend on hardware support. The current work also leaves tool-use parallelization and improvements beyond supervised demonstrations for future work.

5 Limitations and Future work

  • Realizing ideal wall-clock latency gains requires optimized key-value caching and high-bandwidth GPU interconnects, especially for long trajectories.The authors lacked resources to implement optimal hardware-accelerated decoding and suggest scalable GPU architectures for future work.Source: §5 · pp. 9–10
  • The current work treats executions as decoded token sequences; extending the curation pipeline to parallel tool or API calls remains future work.The authors identify tool-dominated decoding latency as a scenario that could particularly benefit.Source: §5 · p. 10
  • The parallelism SFT can achieve is limited by the quality of its curated training data.The authors propose latency-aware reinforcement learning as a possible way to discover strategies beyond demonstration data.Source: §5 · p. 10

6 Conclusion

SPRINT reorganizes reasoning trajectories into plans and parallel executions, and uses a trained model to identify independent subtasks. It reduces sequential tokens while maintaining performance on par with RFT, with greater savings on long trajectories.

6 Conclusion

  • 39% fewer sequential tokens on extensive-reasoning problems, while maintaining performance on par with RFT.The authors also report substantially fewer sequential tokens with performance on par with RFT across multiple out-of-domain tasks.Source: §6 · p. 10
  • SPRINT reorganizes reasoning trajectories into plans and parallelized executions, then uses the trained model to identify and execute independent subtasks in parallel.The framework combines post-training with an inference mechanism for parallel execution.Source: §6 · p. 10
  • The authors report that SPRINT maintains performance on par with RFT while generating substantially fewer sequential tokens on multiple out-of-domain tasks.The conclusion describes these results as generalizing across diverse domains with longer reasoning trajectories.Source: §6 · p. 10

A Implementation Details

The implementation alternates between planning and execution using one SPRINT model and shared prompt structure. It sets generation limits for stages and segments, while providing different context for planning and execution.

A.1 Inference

  • Sequential baselines use a shared prompt for fine-tuning and inference, temperature 0.6, and a 36,000-token response cap.Outputs exceeding the cap are truncated.Source: §A.1 · p. 14
  • SPRINT alternates planner and executor invocations, using stop tokens to end each generated plan or execution segment.The model is fine-tuned to generate a whole trajectory, while inference manages calls and output handling to alternate roles.Source: §A.1 · p. 14
  • Planning receives the cumulative trajectory context, whereas execution receives prior stages and the current plan through its corresponding prompt.The model may generate at most 12 stages; each plan or execution is capped at 8,000 tokens.Source: §A.1 · p. 14
  • The prompt organizes reasoning into phases with a plan and execution, followed by a final-answer segment when the results suffice.The sequential prompt instead structures responses into Thought and Solution sections.Source: §A.1 · pp. 14–15

A.2 Dataset Curation

Dataset curation extracts plan–execution components, infers dependencies, and packs components into interleaved stages. The resulting trajectories are used for full fine-tuning after LoRA did not adequately enforce the response format.

A.2 Dataset Curation

  • GPT-4o extracts logical components from DeepSeek R1 trajectories, separating each component’s plan and execution and identifying reflective comments where present.Components may include validation, alternative methods, or comparisons between strategies.Source: §A.2 · p. 15
  • Each curated component distinguishes planning, execution, and commenting, with verification treated as a separate component rather than a comment.The planner receives completed components and produces a plan and executor prompt; the executor carries out that task using the plan and context.Source: §A.2 · pp. 15–16
  • A GPT-4o-mini model infers a DAG whose parent dictionary records which components must precede each component, excluding those that can run in parallel.Line-numbered trajectories let the extraction process identify the text ranges for plans and executions.Source: §A.2 · pp. 15, 17
  • Packing assigns components to stages, merging executions shorter than three lines with their plans and combining plans when execution results are not needed.The resulting stage assignments are used to generate fine-tuning trajectories.Source: §A.2 · pp. 17–18

A.3 Fine-tuning

  • The authors use full fine-tuning because LoRA did not adequately enforce the response format, with training conducted for five epochs.Training used a single machine with eight 40-GB A100 GPUs, batch size 1, bfloat16, and ZeRO Stage 3 for extended context lengths.Source: §A.3 · p. 18

A.4 Evaluation

The evaluation uses single-GPU serving and task-specific answer checking, while the baseline section specifies the comparison models and inference settings.

A.4 Evaluation

  • Each 7B-scale model was served with vLLM on one NVIDIA A100 GPU with 40 GB of memory.Source: §A.4 · p. 18
  • MATH-500 and Countdown answers were checked with Math-Verify and SymPy, while GPQA answers were matched against ground-truth option labels.Source: §A.4 · p. 18

A.5 Baselines

  • SoT-chat used Qwen2.5-7B-Instruct and SoT-reasoning used DeepSeek-R1-Distill-Qwen-7B, with original-paper prompts and GPT-4o-mini answer extraction.Source: §A.5 · pp. 18–19
  • RFT fine-tuned DeepSeek on sequential R1 trajectories; parallel self-consistency sampled 20 Qwen2.5-7B-Instruct responses per problem and used majority vote.Source: §A.5 · p. 19

B.1 Demonstration of the Data Curation Pipeline

This section demonstrates how SPRINT reorganizes reasoning into dependency-aware plans and parallel executions, using a MATH example of the curation pipeline and a binary-to-octal conversion. It also compares inference-time sequential token counts with RFT.

B.1 Demonstration of the Data Curation Pipeline

  • Step extraction separates the reasoning into components, and DAG creation identifies Components 2, 3, 6, and 7 as parallelizable after Component 1.Component 4 depends on Component 3; Component 8 depends on Components 4, 6, and 7, and Component 9 depends on Component 8.Source: §B.1 · pp. 22–23, Figure 7 · p. 24
  • For short executions, the pipeline merges executions with their plans and orders plans according to dependencies in the DAG.The resulting trajectory is the fine-tuning sample for the MATH example.Source: §B.1 · pp. 23–24
  • The curated MATH trajectory contained 1445 sequential tokens, versus 1645 in the original R1 response, due to parallelized executions.The example asks for the vertex’s y-coordinate; the response identifies n as −6.Source: §B.1 · pp. 20, 23

B.2 Demonstration of SPRINT execution versus sequential reasoning from RFT

  • SPRINT’s binary-to-octal response used 1463 sequential tokens, compared with 1989 for the RFT response to the same question.The SPRINT example carries out binary grouping and decimal conversion as parallel executions.Source: §B.2 · pp. 27, 29
  • The example converts binary 10101001110 to octal 2516 by adding one leading zero and grouping digits into triples from the right.The padded number is 010101001110, grouped as 010, 101, 001, 110.Source: §B.2 · pp. 29, 31
  • The groups 010, 101, 001, and 110 convert respectively to octal digits 2, 5, 1, and 6.Together, the digits give 2516 in base eight.Source: §B.2 · pp. 30–31
  • The worked example checks the result by converting the binary input through decimal to octal and by converting the octal digits back to binary.Both checks yield 2516 in octal and 010101001110 in binary.Source: §B.2 · pp. 30–31

B.3 Demonstration of SPRINT parallelism within a single solution method

This example shows SPRINT splitting one solution method into parallel subtasks, then aggregating their results later.

B.3 Demonstration of SPRINT parallelism within a single solution method

  • The planner divides the asymptote problem into parallel calculations of vertical and horizontal asymptotes.Source: §B.3 · p. 32
  • The example presents parallel execution within one method as distinct from parallelizing alternative solution methods, with results aggregated later.Source: §B.3 · p. 32
  • The vertical-asymptote subtask factors the denominator to find roots x=7 and x=-2, while the horizontal-asymptote subtask returns y=0 from the degree comparison.Source: §B.3 · p. 32

B.4 Demonstration of SPRINT execution on a non-STEM task

The creative-writing example demonstrates SPRINT applying parallel planning beyond the STEM tasks used for fine-tuning. It divides a scene into concurrent perspective-based subtasks and combines their outputs into a unified narrative.

B.4 Demonstration of SPRINT execution on a non-STEM task

  • After three planning and execution rounds, SPRINT integrated independently developed outputs into a coherent scene for a non-STEM creative-writing task.Source: §B.4 · p. 32
  • The 250-word scene prompt asks for events shortly after the Battle of King’s Landing.Source: §B.4 · p. 33
  • The planner identifies Bran’s visions, a noble’s skepticism, and an urchin’s admiration as distinct perspectives, then assigns their lines to concurrent executors.Source: §B.4 · p. 33

Related papers

Loading 2506.05745v2…