PaperlayerView exact revision on arXiv

Source-linked AI summary

Giving Credit Where It's Due: Redundancy-Aware Learning for Efficient Reasoning

Yuqing Zhou, Hong Wang, Manqing Mao, Zhuoer Wang, Samson Koelle, Jie Yuan, Yanjun Lin, James Feng, Nikki Lijing Kuang, Ziwei Zhu, Wei Niu

arXiv:2609.27156v1cs.CLcs.LG

TL;DR

Existing trajectory-level and local step-level efficiency signals rarely model inter-step semantic dependencies, limiting their ability to distinguish redundant steps from those supporting later deductions. RECAP propagates structural responsibility through an LLM-annotated semantic dependency graph and combines it with step efficacy to reshape rollout-level GRPO advantages into step-specific updates. Across two 7B models and four mathematical reasoning benchmarks, RECAP improves the accuracy–efficiency trade-off; on Qwen2.5-Math-7B, it reduces reasoning tokens by 8%–31% versus GRPO while improving pass@1 on all four benchmarks.

  • Problem

    Existing trajectory-level and local step-level efficiency signals rarely model inter-step semantic dependencies, limiting their ability to distinguish redundant steps from those supporting later deductions.

    Source: §1 · pp. 1–2

  • Method

    RECAP propagates structural responsibility through an LLM-annotated semantic dependency graph and combines it with step efficacy to reshape rollout-level GRPO advantages into step-specific updates.

    Source: §1 · p. 2, §4.1.1 · p. 4, §4.3 · p. 5

  • Results

    Across two 7B models and four mathematical reasoning benchmarks, RECAP improves the accuracy–efficiency trade-off; on Qwen2.5-Math-7B, it reduces reasoning tokens by 8%–31% versus GRPO while improving pass@1 on all four benchmarks.

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

  • Takeaways & Limitations

    The reported savings reflect fewer unnecessary reasoning operations and less dead-end reasoning rather than more compact expression.

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

Abstract

from arXiv · show

Large reasoning models can produce correct yet unnecessarily long reasoning traces. Existing methods improve reasoning efficiency with trajectory-level objectives or local token- and step-level signals, but rarely model inter-step semantic dependencies. This limits their ability to distinguish redundant steps from those that support later deductions, making it harder to shorten reasoning without sacrificing accuracy. We introduce RECAP (REdundancy-aware Credit Assignment via Propagation), which addresses this limitation by assigning credit where it is due based on both a step's downstream role in the reasoning structure and its contribution to solving the problem correctly. We define structural responsibility to capture the step's downstream role by measuring how strongly later reasoning depends on it, using credit propagated backward from the final-answer node through an outcome-independent, LLM-annotated semantic dependency graph. However, a step can have high structural responsibility yet steer the reasoning away from the correct solution. RECAP therefore introduces step efficacy to measure answer-directed progress through changes in gold-answer log-likelihood as each step is added. Together, these signals reshape rollout-level GRPO advantages into step-specific updates. RECAP requires neither a separately trained process reward model nor preconstructed concise trajectories. Across two 7B models and four mathematical reasoning benchmarks, RECAP improves the accuracy-efficiency trade-off. On Qwen2.5-Math-7B, it improves pass@1 by 2.0-3.7 percentage points while reducing reasoning tokens by 8%-31% relative to GRPO across all four benchmarks. Analysis suggests these savings reflect fewer reasoning operations and less dead-end reasoning, rather than more compact expression.

1 INTRODUCTION

The introduction frames redundant reasoning as an efficiency cost that outcome-based training does not directly address, then presents RECAP’s combination of downstream-dependence and answer-progress signals. It reports improved pass@1 and fewer reasoning tokens across four benchmarks.

1 INTRODUCTION

  • Outcome-based reinforcement learning applies a trajectory-level advantage across the sequence, allowing low-contribution steps to be reinforced alongside useful deductions.Repetition, unproductive exploration, and unnecessary verification add inference-time cost despite contributing little to the final solution.Source: §1 · p. 1
  • Local utility signals can miss contributions realized through later deductions, while structural dependence alone cannot show whether a step advances the correct solution.The introduction identifies inter-step information propagation and answer-directed progress as complementary aspects of step contribution.Source: §1 · p. 2
  • RECAP combines a step’s downstream role with its progress toward the correct solution to assign step-level credit.It propagates structural credit backward through a typed semantic dependency graph and measures efficacy through changes in correct-answer log-likelihood as each step is added.Source: §1 · p. 2
  • RECAP requires neither a separately trained process reward model nor preconstructed concise trajectories.Its step-specific signal refines the outcome-derived advantage using efficacy and propagated structural responsibility.Source: §1 · p. 2
  • Across four benchmarks, RECAP improves pass@1 by 2.0–3.7 percentage points while reducing reasoning tokens by 8%–31% on Qwen2.5-Math-7B versus GRPO.The method targets unnecessary computation, including dead-end reasoning.Source: §1 · p. 2

2 RELATED WORK

Prior efficiency methods use trajectory-level signals or compressed traces, while fine-grained and structure-aware approaches have different limits. RECAP models semantic dependencies within sampled traces and combines them with answer-directed progress.

Prompt-Based Control

  • Prompt-based methods use instructions, output constraints, or adaptive hints to encourage concise reasoning, but provide limited guidance on which steps to preserve.Source: §2 · p. 2

Length Regularization and Trace Compression

  • Trajectory-level length or model-derived objectives encourage shorter solutions but assign one signal to the whole trace, while compression methods learn from pruned or distilled traces.These approaches do not assign credit to individual steps in newly sampled rollouts.Source: §2 · pp. 2–3

Fine-Grained and Structure-Aware Credit Assignment

  • Fine-grained signals often evaluate local effects without explicitly capturing how one step’s information contributes to later reasoning.Structure-aware approaches organize trajectories or assign finer-grained credit, but may target sampling or shorter paths rather than identifying redundant computation.Source: §2 · p. 3
  • RECAP propagates structural responsibility through semantic dependencies and uses step efficacy to incorporate answer-directed progress into policy updates.This distinguishes steps by both their downstream role and their effect on the final solution.Source: §2 · p. 3

3 PRELIMINARY

GRPO samples groups of rollouts and assigns each rollout an outcome-derived advantage, which it applies uniformly to all tokens. The section motivates redistributing that signal according to each step’s contribution.

3 PRELIMINARY

  • GRPO assigns each rollout a group-normalized advantage based on its outcome reward, with above-average rollouts receiving positive advantages and below-average rollouts negative ones.The stability term ϵ is used in the normalization.Source: §3 · p. 3
  • The policy objective uses token-level importance-sampling ratios, clipping to limit drastic updates, and a KL term to regularize deviation from a reference policy.Source: §3 · p. 3
  • GRPO applies the same rollout-level advantage to every token, although tokens can contribute differently to the final solution.Useful derivations, repeated checks, and abandoned branches are therefore reinforced or penalized together.Source: §3 · p. 3
  • The section motivates redistributing rollout credit toward steps whose information is used by later reasoning and contributes to the final answer.Source: §3 · p. 3

4 METHODOLOGY

RECAP assigns step-specific credit by combining a step’s downstream role in a semantic dependency graph with its progress toward the correct answer. It uses these signals to redistribute rollout-level GRPO advantages across steps.

4 METHODOLOGY

  • RECAP uses structural responsibility, step efficacy, and reshaped rollout-level GRPO advantages as three stages of step-specific credit assignment.Structural responsibility captures downstream use; efficacy captures answer-directed progress.Source: §4 · pp. 3–4

4.1 STRUCTURAL RESPONSIBILITY WITHIN A TRACE

  • Structural responsibility measures how strongly subsequent deductions depend on information introduced by a step, using an intra-trace dependency graph and propagated credit.The graph represents which steps contribute to downstream reasoning leading to the final answer.Source: §4.1 · p. 4

4.1.1 INTRA-TRACE DEPENDENCY MODELING

  • The semantic DAG links an earlier step to a later one when the later step uses its information, and distinguishes support, context, and restatement relations.Support is required for a derivation, context is useful but removable, and restatement repeats established information without progress.Source: §4.1.1 · p. 4

4.1.2 DEPENDENCY-BASED STRUCTURE CREDIT PROPAGATION

  • Responsibility propagates backward through dependencies: support edges carry the most credit, context edges partial credit, and restatement edges none.Incoming edge weights are normalized so a step distributes only the responsibility it holds; credit follows downstream use rather than positional distance.Source: §4.1.2 · pp. 4–5

4.2 STEP EFFICACY TOWARD THE SOLUTION

  • Step efficacy measures the immediate change in mean gold-answer log-likelihood when a step extends the preceding trajectory prefix.Positive changes indicate movement toward the gold answer; negative changes indicate movement away.Source: §4.2 · p. 5

4.3 FROM STEP SCORES TO POLICY-GRADIENT ADVANTAGES

  • RECAP combines structural responsibility with clipped, advantage-direction-aware efficacy, then normalizes step scores and uses them to redistribute GRPO advantages across tokens.The normalization approximately preserves the rollout-level update scale while giving structurally important, answer-advancing steps stronger updates in positive-advantage rollouts.Source: §4.3 · pp. 5–6

5 EXPERIMENTS

Across four mathematical benchmarks and two 7B models, the experiments assess RECAP’s accuracy–efficiency trade-off, its two credit signals, and the source of its token savings. Results favor RECAP’s combined approach and suggest its savings come from fewer reasoning operations and less dead-end reasoning.

5.1 OVERALL ACCURACY–EFFICIENCY TRADE-OFF (RQ1)

  • On Qwen2.5-Math-7B, RECAP improves pass@1 by 2.0–3.7 percentage points and reduces response length by 8%–31% versus GRPO across four benchmarks.It achieves the highest pass@1 on all four benchmarks; on DeepSeek-R1-Distill-Qwen-7B, it saves at least 170 tokens per rollout versus DDCA, LEASH, and ThoughtFold.Source: Figure 2 · p. 7, §5.1 · p. 7, Table 1 · p. 8

5.2 CONTRIBUTIONS OF STRUCTURAL RESPONSIBILITY AND STEP EFFICACY (RQ2)

  • Removing structural responsibility lowers pass@1 from 81.90 to 78.30 while increasing average response length from 352 to 459 tokens.The ablation indicates that step efficacy alone does not reliably identify which steps should receive stronger updates.Source: Table 2 · p. 8, §5.2 · p. 8
  • Removing step efficacy reduces pass@1 by 0.58 points but increases mean response length by approximately 5%.Step efficacy calibrates structural credit by indicating whether a step advances the correct solution.Source: §5.2 · p. 8
  • Replacing structural responsibility with shuffled or random credit shortens responses slightly but lowers pass@1 by 2.80 or 3.45 points, respectively.Shuffling preserves the responsibility-score distribution but breaks its alignment with reasoning steps.Source: §5.2 · pp. 8–9, Table 2 · p. 8

5.3 WHERE DO RECAP’S TOKEN SAVINGS COME FROM? (RQ3)

  • Tokens per equation on correct rollouts change only from 36.4 to 36.8, while total tokens fall by 23.7%, equations by 24.5%, and sentences by 17.3%.The stable cost per reasoning unit and falling totals suggest fewer operations rather than more compact expression.Source: Figure 3 · p. 9, §5.3 · p. 9
  • RECAP’s dead-end steps account for 5.4–5.7% of steps, versus 9.6–13.6% for Simple Length and 19.5–25.3% for GRPO.By inference tokens, dead-end shares are 3.3–4.0% for RECAP, versus 6.4–10.4% for Simple Length and 11.1–17.2% for GRPO.Source: §5.3 · p. 9, Table 3 · p. 10

6 CONCLUSION

RECAP uses semantic dependencies and step-level reasoning progress to reshape GRPO updates for more efficient reasoning. Across two 7B models and four mathematical benchmarks, it improves the accuracy-efficiency trade-off, with gains attributed to reduced unnecessary computation rather than more compact expression.

6 CONCLUSION

  • Across two 7B models and four mathematical reasoning benchmarks, RECAP improves the accuracy-efficiency trade-off over trajectory-level, compression-based, and fine-grained baselines.The analysis suggests gains come from reducing unnecessary reasoning computation and dead-end reasoning, rather than expressing the same reasoning more compactly.Source: §6 · p. 10
  • RECAP combines semantic dependencies with step-level reasoning progress to reshape GRPO updates for more efficient reasoning.Source: §6 · p. 10
  • The study uses publicly available datasets and models under their applicable licenses and excludes human subjects, private or sensitive data, and safety-critical applications.Source: ETHICS STATEMENT · p. 10
  • The paper reports the algorithm and training objective in Section 4, experimental settings in Section 5, and additional annotation and analysis details in Appendix A.4.Source: REPRODUCIBILITY STATEMENT · p. 10

A.1 RELATED WORK

Prior token-efficiency approaches provide differing levels of control over reasoning length, but often do not identify which steps should be retained. RECAP instead attributes credit through semantic dependencies among steps within a derivation.

Prompt-Based Methods

  • Prompt-based methods encourage concise reasoning through instructions, output constraints, or adaptive hints, but provide limited guidance on which steps to preserve.Source: §A.1 · p. 14

Length Regularization and Trace Compression

  • Length-regularized methods shorten responses with trajectory-level penalties but cannot identify individual redundant steps.Source: §A.1 · p. 15
  • Pruning and distillation train on preconstructed compressed trajectories, which may generalize poorly to unseen redundancy patterns or retain unnecessary steps and overcompress useful reasoning.Source: §A.1 · p. 15

Fine-Grained and Structure-Aware Credit Assignment

  • Fine-grained methods use local signals such as answer likelihood, confidence, mutual information, or attention, but do not capture how steps support later deductions.They may undercredit structurally important steps and overcredit locally plausible but redundant ones.Source: §A.1 · p. 15
  • Existing structure-aware methods capture shared rollout structure or model-internal information flow, rather than semantic dependencies among steps within one derivation.RECAP constructs such a per-rollout graph and attributes contribution to downstream reasoning.Source: §A.1 · p. 15

Latent Reasoning

  • Latent-reasoning methods reduce explicit chain-of-thought tokens, but those counts may conceal additional latent computation and the methods require specialized training or architectures.The section focuses on token efficiency under the standard autoregressive interface.Source: §A.1 · p. 15

A.2 RECAP ALGORITHM

Algorithm 1 constructs a dependency DAG for each rollout, computes structural responsibility and step efficacy, and reshapes rollout advantages into token-level advantages.

A.2 RECAP ALGORITHM

  • The algorithm combines step-level contribution with rollout-level advantage and assigns the resulting step-level advantage to every token in that step.Source: §A.2 · pp. 15–16
  • For each rollout, RECAP segments the trace into semantic steps, builds a dependency DAG with the annotator, and propagates structural responsibility.Source: §A.2 · p. 16
  • RECAP computes gold-answer log-likelihood before the first step and for each prefix, then clips the change in likelihood for each step.Source: §A.2 · p. 16

A.3 ANNOTATION QUALITY

Annotation quality is assessed through graph validity and agreement with an independent judge consensus, with Claude Haiku 4.5 selected for RECAP. In fixed-hyperparameter downstream comparisons, it outperforms Qwen3-32B on all four benchmarks, though the comparison is not fully tuned.

Annotation Quality

  • The evaluation distinguishes graph-format validity from dependency correctness, and estimates correctness by agreement with independent judges because exact step dependencies lack ground truth.Source: §A.3 · pp. 16–17

Annotation Validity

  • Claude Haiku 4.5 achieves 100.0% graph validity, comparable to Qwen3-32B; only these two annotators achieve validity above 99%.Qwen3 validity rises from 9.8% at 0.6B to 63.8% at 1.7B and 4B, 80.5% at 8B, and 99.9% at 32B; thinking mode changes validity by at most 2.5 percentage points.Source: §A.3 · pp. 16–17, Figure 4 · p. 17

Annotation Accuracy

  • Claude Haiku 4.5 outperforms Qwen3-32B on every reported annotation metric, with a 35-point advantage in pooled accuracy against judge consensus.The evaluation covers support, context, restatement, and step-to-final-answer dependencies.Source: Table 4 · p. 17, §A.3 · p. 17

Annotator Selection

  • Claude Haiku 4.5 matches Qwen3-32B in format reliability while agreeing more often with independent judges, so the authors use it as RECAP’s annotator.Source: §A.3 · p. 17

Effect of Annotator Choice

  • With fixed, untuned hyperparameters, RECAP using Haiku 4.5 achieves higher pass@1 and fewer tokens than using Qwen3-32B on all four benchmarks.The comparison reflects a common configuration rather than each annotator’s best achievable result.Source: §A.3 · p. 18, Table 5 · p. 18

Reasoning Capability of Annotator Models

  • Haiku 4.5 has higher pass@1 and pass@8 than Qwen3-32B on the four reasoning benchmarks, with particularly large gaps on MATH-500 and AIME.The annotator is answer-blind and receives neither gold answers nor solution trajectories.Source: §A.3 · p. 18, Table 6 · p. 18

A.4.1 SETUP

The appendix documents RECAP’s training and step-splitting setup, then reports training-time efficiency, reasoning-structure, and annotation analyses. It also describes the prompts used for annotators and policy models.

A.4.1 SETUP

  • Training used 16 rollouts per prompt, four passes over the prompt pool, and two policy-update epochs per step; RECAP changed advantage construction while keeping other training settings aligned with baselines.Step-efficacy and normalized step weights were clipped, and efficacy scaling and residual mixing were selected by validation search.Source: §A.4.1 · pp. 18–19

A.4.2 STEP SPLITTING

  • Raw splitting produced a median 174 fragments per DeepSeek rollout, often exhausting the annotator budget; RECAP merges adjacent short steps above a per-rollout target.Reliability remained 1.000 through target 100 and was 0.980 at 150, but fell to 0.711 with the raw split.Source: §A.4.2 · pp. 19–20, Figure 5 · p. 22
  • Target 50 won on validation accuracy, kept live annotation reliability at or above 0.992, and trained faster than the larger targets, so it was adopted for thinking models.At target 150, live reliability fell to 0.953–0.963.Source: §A.4.2 · p. 21, Table 13 · p. 22

A.4.3 TRAINING TIME COMPARISON

  • Dependency annotation used about 12% of RECAP’s recorded step time; on 8×H100, RECAP averaged ∼510s per step for Qwen versus GRPO’s ∼300s.For DeepSeek, the corresponding averages were ∼1320s for RECAP and ∼912s for GRPO; measured times were not normalized across hardware.Source: §A.4.3 · p. 21, Figure 6 · p. 23, Table 14 · p. 23

A.4.4 TRAINING DYNAMICS ANALYSIS.

  • RECAP ended training with fewer tokens and reasoning steps and higher reward than GRPO, while Simple Length often shortened responses more at substantially lower reward.The reported training trajectories show these patterns across both models.Source: §A.4.4 · p. 21
  • The fraction of RECAP steps with zero structural responsibility decreased during training for both models, alongside reductions in total step count.The authors describe this trend as consistent with suppressing structurally unused reasoning rather than merely shortening individual steps.Source: §A.4.4 · p. 21, Figure 8 · p. 24, Figure 7 · p. 24

A.4.5 ATOMIC REASONING OPERATION ANNOTATION

  • Manual annotation counted atomic reasoning operations independently of RECAP’s semantic-step boundaries; an operation changes the solution state or adds information later used in the derivation.The rubric excludes pure planning, restatements, exact repetitions, and off-task text, but counts incorrect operations.Source: §A.4.5 · p. 22, Table 16 · p. 24

A.4.6 PROMPTS

  • Annotator prompts are shown in Figures 9–10, while Figure 11 shows the policy prompt; only R1-Distill-Qwen-7B receives <think> to enable thinking mode.Qwen2.5-Math-7B has no explicit thinking mode.Source: §A.4.6 · p. 22, Figure 9 · p. 25, Figure 10 · p. 26

Related papers

Loading 2609.27156v1…