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.