Large reasoning models often generate correct but unnecessarily long reasoning traces. Existing methods for improving efficiency use coarse trajectory-level signals or local step-level signals, but they fail to model inter-step semantic dependencies, making it hard to remove redundant steps without hurting accuracy. To address this, the paper introduces RECAP, which assigns step-level credit using two complementary signals: structural responsibility, which measures how much later reasoning depends on a step via an LLM-annotated semantic dependency graph, and step efficacy, which measures how much the step progresses toward the correct answer by tracking changes in gold-answer log-likelihood. These signals are combined to reshape the rollout-level GRPO advantage into step-specific updates, without needing a separate process reward model or preconstructed concise traces.
Experiments on two 7B models across four mathematical reasoning benchmarks show that RECAP improves both accuracy and efficiency. 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. Analysis indicates that the token savings come from fewer reasoning operations and less dead-end reasoning, not from compressing expression. This work offers a more principled way to train reasoning models that produce shorter, more efficient traces while maintaining or improving correctness.