Fishing Out Free Riders: Shapley-Based Reward Attribution for Parallel Reasoning via Reinforcement Learning
For researchers training LLMs on multi-step reasoning tasks, this method improves learning signal quality by distinguishing helpful from harmful reasoning paths, leading to better performance and stability.
Parallel Shapley addresses the problem of uniform reward assignment in multi-path reasoning for LLMs by using Shapley values to attribute fine-grained path-level contributions. It outperforms existing baselines on mathematical reasoning benchmarks, providing more stable and interpretable training.
Large Language Models (LLMs) excel at multi-step reasoning, yet current parallel reasoning approaches often fail to distinguish the contributions of individual reasoning paths. Many paths may be redundant, misleading, or even detrimental, but outcome-level rewards assign uniform reward, leading to ambiguous learning signals and unstable training. We propose Parallel Shapley, a reinforcement learning framework that attributes fine-grained, path-level contributions in multi-path reasoning. Treating each path as a player in a cooperative game, we leverage Shapley values to quantify marginal contributions, using a generative reward model to evaluate path utilities and Monte Carlo sampling for efficient approximation. Experiments on mathematical reasoning benchmarks show that Parallel Shapley outperforms existing baselines while providing more stable and interpretable training. Our framework effectively "fishes out the free riders," assigning reward proportionally and improving multi-path reasoning in LLMs.