PaperlayerView exact revision on arXiv

Source-linked AI summary

DeepPrune: Parallel Scaling without Inter-trace Redundancy

Shangqing Tu, Yaxuan Li, Yushi Bai, Lei Hou, Juanzi Li

arXiv:2510.08483v2cs.CLcs.AI

TL;DR

Parallel scaling can consume 100M or more tokens, while many generated traces yield identical answers. DeepPrune predicts answer equivalence from partial traces and prunes redundant paths; it reduces token consumption versus consensus sampling while maintaining comparable accuracy.

  • Problem

    Parallel scaling generates multiple reasoning traces but can push token costs to 100M or higher, raising the question of how to achieve high performance at low token cost.

    Source: §1 · p. 1

  • Method

    DeepPrune trains a judge to predict answer equivalence between truncated reasoning traces and uses greedy clustering to prune redundant paths dynamically.

    Source: §1 · p. 2

  • Results

    65.73%–88.50% token reduction versus cons@512 came with accuracy within 3.4 percentage points in online evaluations.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Learned similarity judgment effectively addresses redundancy in parallel scaling, with token consumption reduced by up to 88.5% without hurting accuracy in online experiments.

    Source: §6 · p. 8

    Greedy clustering makes locally optimal decisions that may occasionally prune beneficial diverse paths, especially when early similarity does not indicate final answer equivalence.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Parallel scaling has emerged as a powerful paradigm to enhance reasoning capabilities in large language models (LLMs) by generating multiple Chain-of-Thought (CoT) traces simultaneously. However, this approach introduces significant computational inefficiency due to inter-trace redundancy -- our analysis reveals that over 80% of parallel reasoning traces yield identical final answers, representing substantial wasted computation. To address this critical efficiency bottleneck, we propose DeepPrune, a novel framework that enables efficient parallel scaling through dynamic pruning. Our method features a specialized judge model trained with out-of-distribution data (AIME 2022, AIME 2023, and MATH 500) using oversampling techniques to accurately predict answer equivalence from partial reasoning traces, achieving 0.7072 AUROC on unseen reasoning models. Combined with an online greedy clustering algorithm that dynamically prunes redundant paths while preserving answer diversity. Comprehensive evaluations across three challenging benchmarks (AIME 2024, AIME 2025, and GPQA) and multiple reasoning models demonstrate that DeepPrune achieves remarkable token reduction of 65.73%--88.50% compared to conventional consensus sampling, while maintaining competitive accuracy within 3 percentage points. Our work establishes a new standard for efficient parallel reasoning, making high-performance reasoning more efficient. Our code and data are here: https://deepprune.github.io/.

1 Introduction

DeepPrune reduces token use against consensus sampling while maintaining comparable accuracy. It targets redundancy in parallel reasoning by predicting whether unfinished traces will produce identical answers and pruning redundant paths.

1 Introduction

  • Parallel scaling generates multiple traces at once, but its token costs can reach 100M or more, motivating high performance at lower cost.The introduction contrasts parallel scaling with sequential scaling, which increases computation within one trace.Source: §1 · p. 1
  • About 80% of parallel reasoning traces yield identical answers, motivating DeepPrune to prune redundant paths while preserving answer diversity.The approach predicts answer equivalence from partial traces and uses dynamic pruning.Source: §1 · p. 2
  • Shallow similarity reached AUROC 0.58 and zero-shot LLM comparison AUROC 0.66, motivating a specialized judge model for early pruning.DeepPrune uses truncation strategies, focal loss, oversampling, and greedy clustering.Source: §1 · p. 2
  • DeepPrune reduces token consumption by 65.73%–88.50% versus cons@512, which samples 512 traces and uses majority voting, while maintaining comparable accuracy within 3.4 percentage points.Source: §1 · p. 2

2 Related Work

Prior efficiency work addresses verbosity within individual traces or reduces parallel sample counts through confidence estimates and aggregation. DeepPrune instead explicitly models redundancy between parallel reasoning paths.

2 Related Work

  • Prior work improves inference efficiency through shorter individual traces, confidence-based early stopping, or altered aggregation strategies.The cited approaches include length-conscious fine-tuning, prompting techniques, confidence estimates, and refined aggregation.Source: §2 · pp. 2–3
  • Figure 2 reports that SentenceBERT similarity has AUROC 0.58, while Qwen3-4B-Instruct deep comparison reaches AUROC 0.66.Both approaches compare traces with the same versus different final answers.Source: Figure 2 · p. 3
  • DeepPrune explicitly targets inter-trace redundancy while preserving answer diversity, unlike methods focused on intra-trace verbosity or sample quantity.The comparison distinguishes its target from prior efficiency methods.Source: §2 · p. 3

3 Preliminaries

The preliminaries define pruning as selecting a subset of parallel traces that reduces redundancy while retaining answer diversity. They motivate this objective with evidence that same-answer pairs are common and that partial-trace similarity can help predict answer equivalence.

3.1 Problem Definition

  • The pruning objective selects a subset of parallel traces to reduce redundancy while preserving answer diversity, considering queries with verifiable answers.Similarity is framed as predicting whether unfinished traces will yield identical final answers.Source: §3.1 · p. 3

3.2 Inter-trace Redundancy: The Efficiency Bottleneck of Parallel Reasoning

  • Same-answer pairs exceeded 80% in most models tested, with GLM-4.5-Air at 94.5%; even with 16 samples per problem, this prevalence meant substantial computational resources were spent generating redundant reasoning paths.Source: §3.2 · p. 4
  • SentenceBERT achieved AUROC 0.58 on partial-trace answer-equivalence prediction, while zero-shot Qwen3-4B-Instruct achieved AUROC 0.68 but remained suboptimal for deployment.The methods compared unfinished traces using their first 700 tokens.Source: §3.2 · p. 4

4 DeepPrune

DeepPrune combines an offline judge trained to predict answer equivalence from partial reasoning traces with online pruning of redundant paths. Its greedy clustering and final-answer voting aim to reduce computation while preserving answer diversity and quality.

4 DeepPrune

  • DeepPrune combines offline training of a specialized judge with online pruning of redundant paths while preserving answer diversity.The judge predicts whether incomplete traces will yield identical final answers.Source: §4 · p. 4

4.1.1 Trace Pair Data Collection

  • Training data exhaustively pairs same-query traces, labels answer equivalence with a rule-based DeepScaler reward, and uses Deepseek-R1-Distill-Llama-8B outputs from AIME 2022, AIME 2023, and MATH 500.Source: §4.1.1 · p. 5

4.1.2 Judge Model Training Strategy

  • Qwen3-4B-Instruct is fine-tuned to predict similarity from concatenated unfinished traces, using focal loss and 2x oversampling of the minority class.Focal loss focuses on hard negative pairs; γ downweights easy examples, and α_t balances class importance for the 80/20 label distribution.Source: §4.1.2 · p. 5

4.2.1 Early Stopping via Greedy Clustering

  • Greedy clustering compares unfinished traces with sampled cluster representatives, assigns above-threshold matches, and creates new clusters up to K; it reduces similarity judgments versus exhaustive pairwise comparison.The selection objective is to maximize answer diversity while minimizing computational cost.Source: §4.2.1 · p. 5

4.2.2 Majority Voting for Final Answer

  • The final-answer stage reduces token consumption while preserving answer quality, even when the judge makes wrong predictions.Normally, up to 20 traces from the largest cluster finish; if every cluster is a singleton, 32 sampled traces are finished and their answers are majority-voted.Source: §4.2.2 · pp. 5–6

5 Experiments

DeepPrune is evaluated offline as a judge model and online as a parallel-trace pruning framework. Across the reported settings, it substantially reduces token use, while truncation choices and redundancy thresholds affect predictive performance and answer diversity.

5.1 Experimental Setup

  • The offline evaluation trains on Deepseek-R1-Distill-Llama-8B traces and tests generalization on three other reasoning models.Online tests use DeepSeek-8B, Qwen3-32B, and GPT-OSS-20B across AIME 2024, AIME 2025, and GPQA, with 512 traces per baseline problem.Source: §5.1 · p. 6

5.2 Offline Experiment Results

  • 0.8701 average AUROC and 0.8186 TNR@0.2 are achieved with top-25 reasoning words, focal loss, and oversampling.Reasoning-aligned truncation outperforms top-500-token truncation, while oversampling alone degrades performance.Source: §5.2 · pp. 6–7

5.3 Online Experiment Results

  • 52.5%–91.6% token savings versus cons@512 are reported for DeepPrune, with AIME savings of 79.6%–91.6% and accuracy drops within 3 percentage points.The online results cover three reasoning models and three benchmarks; Table 2 compares token consumption and accuracy across methods.Source: §5.3 · pp. 7–8, Table 2 · p. 7

5.4 Ablation Study

  • Reasoning-word features generally yield higher AUROC than raw top-token features, with an intermediate feature count often performing best.The reported sweet spots include 500 tokens or 25 reasoning words.Source: §5.4 · p. 8
  • On AIME25, lowering τ from 0.75 to 0.25 drops greedy-clustering pass rate from 96.7% to 70%, while τ = 0.5 provides the best balance.The passage attributes the pass-rate decline to more aggressive pruning reducing answer diversity.Source: §5.4 · p. 8, Table 3 · p. 8

6 Conclusion

The conclusion identifies equivalent reasoning paths as a source of wasted parallel-computation resources and presents DeepPrune as a learned approach to pruning them. Experiments report generalization to unseen reasoning models and large token reductions without hurting online accuracy.

  • Over 80% of computational resources are described as wasted on generating equivalent reasoning paths in parallel reasoning.Source: §6 · p. 8
  • DeepPrune uses an out-of-distribution-trained judge model and online greedy clustering to prune redundant traces while preserving answer diversity.Source: §6 · p. 8
  • The conclusion reports 0.7072 AUROC on unseen reasoning models and token reductions up to 88.5% without hurting accuracy in online experiments.Source: §6 · p. 8

Limitations

The authors identify constraints in the judge model’s training distribution, greedy clustering decisions, inference overhead, and threshold selection. These factors may affect transfer, retained answer diversity, efficiency gains, and performance across problems.

  • Training exclusively on Deepseek-R1-Distill-Llama-8B traces may limit generalization to model families with distinct reasoning styles.Source: Limitations · pp. 8–9
  • Greedy clustering makes locally optimal decisions that may prune beneficial diverse paths when early similarity does not indicate final answer equivalence.Source: Limitations · p. 9
  • Judge-model inference adds computational overhead, and efficiency gains depend on the cost ratio between judge and reasoning models.Source: Limitations · p. 9
  • The optimal redundancy threshold may depend on the problem, although τ = 0.5 works well across the evaluated benchmarks.Source: Limitations · p. 9

Ethical Consideration

The authors report no significant ethical concerns and state that the models and datasets used are publicly available with permissible licenses. The work processes mathematical and scientific reasoning tasks rather than sensitive personal material.

Ethical Consideration

  • The authors affirm that the work raises no significant ethical concerns.Source: Ethical Consideration · p. 9
  • The models and datasets used are described as publicly available with permissible licenses.The passage names DeepSeek-8B, Qwen, GPT-OSS, AIME, and GPQA.Source: Ethical Consideration · p. 9
  • The research processes mathematical and scientific reasoning tasks, which the authors describe as devoid of personal, biased, or harmful material.Source: Ethical Consideration · p. 9

A Detailed Analysis of Inter-trace Redundancy

The analysis accounts for uneven trace-pair contributions when estimating inter-trace redundancy and documents how baseline results were aligned for comparison.

A Detailed Analysis of Inter-trace Redundancy

  • Invalid or non-terminating traces were excluded, and resource constraints limited full 760-query collection to Deepseek-R1-Distill-llama-8b; other models used about 100 problems.The resulting model-specific pair counts and similarity ratios are summarized in Table 4.Source: A Detailed Analysis of Inter-trace… · p. 12, Table 4 · p. 12
  • Unequal pair counts across models make a weighted aggregate, rather than a simple average of model ratios, necessary to represent overall redundancy.The analysis uses the aggregate distribution; the amount of trace data collected varied substantially by model.Source: A Detailed Analysis of Inter-trace… · p. 12

B.1 Differences in cons@512 and DeepConf Baselines

  • Experiments matched the DeepConf models, benchmarks, sampling temperatures, max_length settings, and inference engine, yet minor result differences remained.The setup used vllm and was aligned with the DeepConf codebase.Source: §B.1 · p. 12
  • Re-sampling 512 responses brought pass@1 values close to those reported by DeepConf, with differences within 3 percentage points.The procedure first sampled 640 responses, then re-sampled 512 to align pass@1 metrics by model and dataset.Source: §B.1 · p. 12

B.2 Missing DeepConf Result for GPT-OSS-20B on GPQA

This appendix explains a missing DeepConf comparison, specifies experiment resources and settings, and discusses how the online evaluation treats answer diversity.

B.2 Missing DeepConf Result for GPT-OSS-20B on GPQA

  • DeepConf has no reported GPT-OSS-20B result for GPQA, and limited resources prevented the authors from running the additional experiment.Table 5 reports aligned pass@1 values for the available comparisons, with differences within 3 percentage points of DeepConf’s paper.Source: §B.2 · pp. 12–13, Table 5 · p. 13

B.3 Dataset and Model Specifications

  • GPQA refers to its 198-problem Diamond subset; DeepSeek-8B denotes DeepSeek-R1-0528-Qwen3-8B, and Qwen3-4B-Thinking denotes Qwen3-4B-Thinking-2507.These names clarify the dataset and model variants used in the experiments.Source: §B.3 · p. 13

C Hyperparameters

  • Table 6 lists DeepPrune’s hyperparameters and defaults, and its two k symbols represent mutually exclusive truncation strategies.Only one truncation strategy can be used at a time.Source: C Hyperparameters · p. 13, Table 6 · p. 13

D Computational Resources

  • Most judge-model training and testing used four 80-GB NVIDIA A100 GPUs; later experiments also used eight H20 GPUs for about two days.The authors describe computational resources as relatively limited, particularly for generating 512-response baselines.Source: D Computational Resources · p. 14

E.1 Comparison of Diversity with Baselines

  • Online comparisons prioritize final accuracy rather than pass@k; DeepPrune retains cluster representatives for multiple candidates, unlike baselines that return one aggregated answer.The authors regard direct pass@k comparison as unfair because the methods have different effective k values.Source: §E.1 · p. 14

E.2 Analysis of Low Pass Rate with Low Thresholds

At low redundancy thresholds, permissive clustering can reduce the measured pass rate; majority voting is used to produce a single answer comparable with baseline outputs.

E.2 Analysis of Low Pass Rate with Low Thresholds

  • For Qwen3-32B on AIME25, Greedy Clustering pass@k at thresholds 0.5 and 0.25 is 70.0%; permissive judgments can concentrate traces into few large clusters.With one representative per cluster, fewer clusters yield a smaller effective k and can lower measured pass@k.Source: §E.2 · p. 14
  • At low thresholds, majority voting can sample up to q1 = 20 traces from the largest cluster, supporting a consensus even when few clusters remain.This can sustain final accuracy despite lower cluster-level pass@k when the judge is imperfect.Source: §E.2 · p. 14

E.3 Rationale for Majority Voting

  • Majority voting consolidates DeepPrune’s retained paths into one answer, matching the single-answer output format used by DeepConf and cons@512.The authors also identify selection models and combinations with confidence-based filters as alternative aggregation strategies for future exploration.Source: §E.3 · p. 15
Loading 2510.08483v2…