PPM Framework Addresses Sparse Reward Inefficiency in Long-Horizon LLM Reasoning

Core Idea and Mechanism of PPM

Progressive Point Matching (PPM) is an asymptotically unbiased partial credit assignment framework proposed to address the inefficiency of sparse outcome reward in long-horizon LLM tasks. Existing sparse rewards cause an exponential decrease in the signal-to-noise ratio in long horizons, degrading policy gradient performance. Additionally, existing partial credit methods introduce asymptotic bias, where the optimal policy under a surrogate objective may not be optimal under the outcome reward.

PPM models the reasoning process as path exploration through a Markovian state space. Reasoning points are intermediate results extracted from a reference trajectory, and states are defined as sets of visited reasoning points. The core component is the Shortcutting mechanism. If all points dependent on a specific point are reached, that point is also considered reached, allowing trajectories that succeed via strategies different from the reference trajectory to obtain full credit. This ensures optimal policies under the outcome reward.

Performance Improvements and Experimental Results

Experimental results show that when subproblems are independent, PPM's learning speed improvement increases exponentially with the number of subtasks (n). Particularly on extremely difficult math datasets where the base policy almost always receives an outcome reward of 0, GRPO was unable to sample trajectories to fill a training batch within 24 hours, whereas PPM demonstrated significantly superior performance compared to the runner-up method (POPE).

A surprising finding is that Length 4K training yields performance equal to or better than Length 8K training. This is because Length 8K training causes output length collapse, where the policy greedily guesses the answer and terminates reasoning early. In contrast, Length 4K training induces partial progress optimization due to token budget limitations, which is advantageous in specific task regimes.

Limitations and Future Directions

PPM is unbiased and aims for reward allocation proportional to partial progress toward the goal. Since general reasoning tasks lack clean partitions, reasoning points must be generated using off-the-shelf LLMs, requiring significant iteration. Future work needs to address the issues of increased cost and variance associated with graph expansion when applying multiple reference trajectories. PPM can be interpreted as an approximation of imitation learning and is expected to be applicable to non-verifiable environments.