Solve More with Fewer Steps: Assigning Credit by Uncovering Dependencies in Agentic RL

Agentic reinforcement learning (RL) is a powerful technique for improving the multi-step reasoning of agents. The success of agentic RL largely relies on whether it can properly assign credit for final outcomes to intermediate steps, namely the credit assignment problem (CAP). However, solving the CAP remains highly challenging, as long reasoning trajectories often obscure the contribution of each step. To tackle this problem, we propose **CreditFlow**, a novel credit assignment method that directs agents to focus on critical steps, thus improving both reasoning performance and efficiency. Our key idea is to assign credit based on *underlying dependencies* (whether step $j$ depends on the result of step $i$), rather than the *temporal order* (whether step $j$ occurs after step $i$). The major challenge in developing CreditFlow is to efficiently distinguish underlying dependencies from the temporal adjacency in raw trajectories. To uncover the dependencies, CreditFlow introduces a rule-based provenance tracking mechanism to dynamically trace how later steps use results from earlier ones, *incurring negligible overhead* and *avoiding LLM-induced hallucinations*. Experiments on eight mainstream benchmarks show that CreditFlow outperforms the strongest baseline by **5 points** on average, while reducing the average number of inference steps by over **20%**.