PaperlayerView exact revision on arXiv

Source-linked AI summary

MaPP: A Unified Marginalized Posterior-Predictive Framework for Data-Efficient RLVR

Yangyang Ren, Haodong Zhu, Sheng Xu, Yanjing Li, Nikolai Yu. Zolotykh, Wentao Zhang, Baochang Zhang

arXiv:2609.34990v1cs.LG

TL;DR

Online prompt selection predicts prompt difficulty, but existing methods overlook how group composition affects the reliability of GRPO's response-level advantages. MaPP marginalizes advantage estimates and prompt scores using a shared Beta posterior. Across three reasoning domains and five backbones, it consistently outperforms GRPO and strong baselines, with up to +2.45 average accuracy improvement over the strongest baseline at the same rollout budget.

  • Problem

    Existing prompt-selection methods overlook how uncertainty in sampled group composition affects the reliability of GRPO response-level advantages, which also limits downstream prompt selection.

    Source: §3.2 · p. 5

  • Method

    MaPP uses a shared Beta posterior for closed-form marginalization of response-level advantages and uncertainty-aware prompt selection.

    Source: §1 · p. 3, §4.2 · p. 6

  • Results

    Across three reasoning domains and five backbones, MaPP consistently outperforms GRPO and strong baselines, achieving up to +2.45 average accuracy improvement over the strongest baseline at the same rollout budget.

    Source: §1 · p. 3, §6 · p. 10

  • Takeaways & Limitations

    MaPP addresses data-efficiency losses in advantage estimation and prompt selection through one shared posterior without additional rollout overhead.

    Source: §6 · p. 10

Abstract

from arXiv · show

Reinforcement learning with verifiable rewards (RLVR) improves the reasoning capabilities of large language models but incurs substantial costs from rollouts and policy updates. Online prompt selection improves efficiency by using per-prompt Bayesian posteriors to predict difficulty and prioritize informative prompts. However, existing methods overlook how reliably learning signals are extracted from sampled responses. In GRPO, a response's advantage depends on both its own outcome and the randomly sampled outcomes of its peers through group normalization. Our theoretical and experimental analyses show that uncertainty in group composition introduces composition noise, a non-vanishing variance component that imposes an irreducible lower bound on gradient estimation error and impairs downstream prompt selection. We propose MaPP (Marginalized Posterior-Predictive), a unified framework for data-efficient RLVR that denoises response-level advantage estimation and improves prompt selection using a shared Beta posterior. For each response, MaPP replaces the standard group-relative advantage with a composition-invariant intrinsic advantage through closed-form Beta-Binomial marginalization. The resulting posterior-predictive estimator has an error that provably diminishes as the posterior concentrates. Using the same posterior, MaPP derives an uncertainty-aware prompt selection score to improve data efficiency without additional rollout cost. Experiments on mathematics, planning, and visual geometry across five model backbones show that MaPP consistently outperforms GRPO and strong selection baselines, achieving up to +2.45 average accuracy improvement over the strongest baseline under the same rollout budget and setting a new state of the art.

1 Introduction

RLVR training is costly, and prompt selection alone does not address uncertainty in the response-level learning signal. MaPP uses a shared Beta posterior to denoise advantages and improve prompt selection, with consistent gains across domains and model backbones.

1 Introduction

  • RLVR's intensive rollouts for policy evaluation and updates make improving utility per fixed rollout budget a central efficiency challenge.Uniform sampling can spend rollouts on overly easy or hard prompts whose degenerate groups provide zero gradient; Dynamic Sampling discards such prompts only after rollout.Source: Figure 1 · p. 2, §1 · p. 2
  • Composition noise arises because identical responses can receive different GRPO advantages depending on randomly sampled peers, degrading gradient estimation and downstream prompt selection.It is induced by uncertainty in group composition and persists across non-degenerate difficulty levels in the illustrated setting.Source: §1 · p. 2, Figure 1 · p. 2
  • MaPP uses a shared Beta posterior for two closed-form components: MaPP-AD marginalizes advantages, while MaPP-PS derives an uncertainty-aware prompt-selection score.MaPP-AD produces composition-invariant advantages, and the posterior-predictive estimator's error provably diminishes as the posterior concentrates.Source: §1 · pp. 2–3, Figure 2 · p. 3
  • Across three domains and five model backbones, MaPP consistently outperforms GRPO and strong selection baselines, with up to +2.45 average accuracy improvement over the strongest baseline at the same rollout budget.The CountDown figure also reports higher accuracy than all selection methods at equal rollout cost and 80% fewer rollouts than DS for comparable performance.Source: Figure 1 · p. 2, §1 · p. 3

2 Related Work

GRPO and online prompt-selection methods address different parts of RLVR training, but existing selection approaches do not account for group-composition uncertainty in response-level advantages. MaPP complements these methods by marginalizing advantage estimates and reusing a shared Beta posterior for prompt selection.

2.1 RL Finetuning for Large Language Models

  • GRPO removes PPO's learned value network through within-group normalization, while MaPP changes how its advantages are estimated under group-composition uncertainty.The paper characterizes MaPP as Rao–Blackwellizing the GRPO advantage with a conjugate Beta posterior rather than a learned critic.Source: §2.1 · p. 3

2.2 Online Prompt Selection for RLVR

  • Online prompt selection addresses uneven prompt informativeness, but evaluation-based methods oversample and filter while prediction-based methods estimate difficulty before rollout.These approaches primarily allocate budget across prompts and ignore composition noise in GRPO response-level advantages.Source: §2.2 · pp. 3–4
  • MaPP complements existing selection pipelines by denoising GRPO advantages with posterior-predictive marginalization and reusing the shared Beta posterior for prompt selection.Its components are modular and can be layered on existing pipelines.Source: §2.2 · p. 4

3 Challenge Analysis

GRPO estimates response advantages from sampled groups, while online prompt selection uses Bayesian success-rate estimates to identify informative prompts. Because group composition is random, realized advantages contain a strictly positive noise component that prompt selection alone cannot remove.

3.1 Preliminaries

  • GRPO generates independent responses for each prompt and estimates advantages through within-group normalization, without a learned value network.Responses receive binary correctness rewards, and groups in which every response is correct or every response is incorrect yield zero advantage and no gradient signal.Source: §3.1 · p. 4
  • Online prompt selection models each prompt’s latent success rate with a Beta posterior updated from observed binary rewards.The posterior supports prioritizing prompts of intermediate difficulty, which are more likely to yield non-degenerate gradients.Source: §3.1 · pp. 4–5

3.2 Composition Noise in GRPO

  • Composition noise is variance in a response’s advantage caused by random group composition, even when its correctness is fixed.The component is strictly positive for prompt success rates between 0 and 1 and contributes variance to gradient estimation.Source: §3.2 · p. 5
  • This noise also makes prompt-informativeness assessments less faithful because they rely on sampled group rewards from the same policy.The proposed target is the conditional expectation of the realized advantage given the response reward and latent prompt difficulty, which removes composition noise by construction.Source: §3.2 · p. 5

4 Method

MaPP combines response-level advantage denoising and prompt selection through posterior-predictive marginalization over a shared Beta posterior. It replaces dependence on a realized group composition with an intrinsic advantage and uses posterior uncertainty to score prompts.

4.1 The Intrinsic Advantage

  • The intrinsic advantage depends on a response’s reward and latent prompt difficulty, not on which peers were sampled.For a fixed response reward and prompt difficulty, its advantage has no variance across group compositions; the latent success rate must therefore be estimated.Source: §4.1 · pp. 5–6

4.2 Marginalized Posterior-Predictive Advantage Denoising

  • MaPP-AD estimates a response’s advantage by marginalizing over a leave-one-out Beta posterior that excludes that response’s own reward.This makes the posterior conditionally independent of the evaluated response and yields a composition-free estimate through Beta–Binomial conjugacy.Source: §4.2 · p. 6
  • The MaPP-AD estimator averages advantages across plausible group compositions under posterior-predictive probabilities.The posterior-predictive probability represents the chance that a hypothetical group of G−1 responses contains s−1 correct responses; the estimator’s MSE is provably lower than GRPO’s after a few posterior updates per prompt.Source: §4.2 · p. 6

4.3 Marginalized Posterior-Predictive Prompt Selection

  • MaPP-PS marginalizes the probability of obtaining a non-degenerate gradient over the prompt’s posterior, down-weighting prompts with wide posteriors.Existing selection methods instead use point estimates of difficulty; MaPP draws prompt batches with probability proportional to its marginalized score.Source: §4.3 · pp. 6–7

4 Method

  • MaPP unifies posterior-predictive advantage denoising and prompt selection using a shared posterior.The two components are modular and can be adopted independently or combined with existing selection strategies.Source: §4.3 · p. 7

5 Experiments

MaPP is evaluated across mathematics, numerical planning, and visual geometry with multiple model backbones. It consistently improves benchmark accuracy and training efficiency, while ablations examine its components and key settings.

5.1 Experimental Setup

  • The experiments cover mathematics, numerical planning, and visual geometry, using text-only and vision-language model backbones.The setup includes three text models for mathematics and planning and two vision-language models for visual geometry.Source: §5.1 · pp. 7–8

5.2 Main Results

  • +2.45 average accuracy over MoPPS on Qwen3-4B; MaPP also exceeds Dynamic Sampling by +1.55 while using 25% of its rollout budget.The mathematics results report consistent gains over MoPPS on Qwen3-8B (+1.49) and R1-Distill-7B (+1.42).Source: §5.2 · p. 8
  • +1.84 and +1.71 final accuracy gains on Countdown, and +1.04 and +2.40 on Geometry3k, over the strongest baselines.The gains correspond respectively to Qwen3-4B and Qwen3-8B on Countdown, and Qwen2.5-VL-3B-Instruct and Qwen2.5-VL-7B-Instruct on Geometry3k.Source: §5.2 · p. 8
  • Across six model-task combinations, MaPP converges faster; it reaches Random Sample’s MATH accuracy at 2.5–2.8× faster speed and accelerates Countdown convergence by 1.6×–2.6×.It adds no rollout cost over prediction-based methods and requires less than half the runtime of Dynamic Sampling across settings.Source: §5.2 · pp. 8–9, Figure 3 · p. 8

5.3 Ablation Analysis

  • Combining MaPP-AD and MaPP-PS improves MATH by +3.44, exceeding the individual gains of +2.66 and +1.62, respectively.Adding MaPP-AD to MoPPS and DPS also improves them by +1.04 and +1.12 without changing their selection logic.Source: §5.3 · p. 9, Table 4 · p. 9
  • On Countdown, λ=0.5 reaches 79.50 average performance, while λ=0.0 and λ=0.9 reach 74.85 and 75.21; MaPP also leads baselines at group sizes G=4 and G=16.At G=4, margins are +0.28 on CD-34 and +0.33 on CD-4; at G=16, they are +1.43 and +0.63, respectively.Source: §5.3 · p. 9, Table 2 · p. 9, Table 3 · p. 9

6 Conclusion

The conclusion presents MaPP as a shared-posterior framework addressing composition noise in GRPO through advantage estimation and prompt selection. Its training loop selects prompts, rolls out responses, applies posterior-predictive advantages, updates the policy, and updates the shared posterior.

6 Conclusion

  • MaPP addresses composition noise, which degrades gradient estimation and prompt selection, with a shared-posterior framework for advantage estimation and prompt selection.The framework uses a posterior-predictive advantage estimator with provably diminishing MSE and an uncertainty-aware selection score.Source: §6 · p. 10

A Algorithm

  • The training loop selects prompts using a posterior-predictive score, then replaces standard GRPO advantages with posterior-predictive advantages after rollout.The shared Beta posterior is updated from new observations after the policy update.Source: A Algorithm · p. 12
  • The procedure adds closed-form computations without additional rollouts or model forward passes.Source: A Algorithm · p. 12

B.1 Tasks and Datasets

The appendix describes the datasets used to train and evaluate MaPP in mathematics, numerical planning, and visual geometry.

B.1 Tasks and Datasets

  • Mathematics training uses 7,500 MATH competition problems; evaluation uses AMC23, MATH500, Minerva Math, and OlympiadBench.The MATH problems span algebra, geometry, number theory, and combinatorics.Source: §B.1 · p. 12
  • Countdown training uses 2,000 Countdown-34 problems, with evaluation on held-out CD-34 and harder CD-4 sets.The CD-4 subset uses four source numbers per problem, enlarging the search space.Source: §B.1 · p. 13
  • Geometry3k training uses 2,101 diagram-and-reasoning problems, with evaluation on its official 601-problem test split.Source: §B.1 · p. 13

B.2 Training Details

Training uses GRPO with task-specific rollout group sizes and shared posterior settings. Calibration analyses compare MaPP’s predicted advantage and prompt difficulty scores with empirical observations.

B.2 Training Details

  • Training samples five responses per MATH prompt and eight per Countdown or Geometry prompt, using GRPO with β=0 and 8 NVIDIA H100 GPUs.The experiments use AdamW with learning rate 1 × 10^-6 and a maximum response length of 1024 tokens.Source: §B.2 · p. 13
  • MaPP initializes its Beta prior as (α0, β0) = (1, 1) and uses temporal discount λ=0.5; prompt batches are sampled according to posterior-predictive scores.Prediction-based baselines use a candidate pool eight times the training batch size and select the top-B prompts.Source: §B.2 · p. 13

C.1 Empirical Calibration of MaPP-AD and MaPP-PS

  • MaPP-AD’s theoretical intrinsic advantage closely tracks empirical mean advantage, while MaPP-PS’s predicted score tracks the empirical non-degenerate ratio within ±0.05.The calibration plots use sampled groups for Countdown Qwen3-4B and observations collected throughout training, respectively.Source: §C.1 · p. 13

C.2 Training Dynamics

MaPP converges faster than the strongest baseline across the tested group sizes and outperforms it on visual geometry; its performance also depends on the posterior tracking discount.

Robustness to group size

  • On Countdown, with group sizes G=4 and G=16, MaPP reaches the strongest baseline’s accuracy approximately 2.0–2.4× faster in convergence speed at G=4, increasing to 2.6–2.8× at G=16.Source: §C.2 · pp. 13–14

Visual geometry and sensitivity to λ

  • At convergence on visual geometry, MaPP exceeds the strongest baseline by +1.04 and +2.40 on Qwen2.5-VL-3B and Qwen2.5-VL-7B, respectively.It reaches comparable accuracy about 1.4–1.5× faster; Figure C(a) shows the training curves.Source: §C.2 · p. 14
  • With λ=0.5, MaPP achieves its best final accuracy and convergence speed; λ=0.0 and λ=1.0 converge noticeably slower.Figure C(b) compares MaPP under different posterior tracking discounts.Source: §C.2 · p. 14

D Theoretical Analysis

The analysis identifies a composition-dependent variance floor in GRPO and establishes conditions under which MaPP’s posterior-predictive advantage estimator and resulting gradient bound improve with posterior evidence. It also derives closed forms and describes an extension to multi-level rewards that remains unevaluated in this work.

D Theoretical Analysis

  • For any G≥2 and γ∈(0,1), GRPO has a strictly positive composition-noise lower bound that prompt-level posterior or selection schemes cannot reduce.The bound depends only on (γ, G); the analysis also reports that MaPP suppresses realized advantage variability and yields a smaller gradient MSE upper bound when n≥n⋆.Source: D Theoretical Analysis · pp. 15–16
  • With standard initialization (α0, β0)=(1,1), MaPP strictly improves over GRPO per response after a small threshold reached after a few posterior updates per prompt.The gradient-level bound transfers this comparison under a score-function moment condition.Source: D Theoretical Analysis · p. 16

E Derivation of Closed Forms

  • The closed-form derivation models the number of correct peer responses as Binomial(G−1, γ) when evaluating a response’s intrinsic advantage.The posterior-predictive advantage marginalizes the intrinsic advantage over a leave-one-out Beta posterior; the prompt-level selection score is also derived from posterior moments.Source: D Theoretical Analysis · p. 15, E Derivation of Closed Forms · pp. 16–17

F Extension to Multi-Level Rewards

  • For discrete multi-level rewards, MaPP can replace the Beta–Binomial pair with a Dirichlet–Multinomial pair and enumerate leave-one-out count vectors.All experiments use binary rewards; the {0, 0.1, 1} scheme merges 0 and 0.1 into the negative class, and systematic evaluation of the multi-level extension is left for future work.Source: F Extension to Multi-Level Rewards · p. 17

G Data Examples

This section provides illustrative prompt examples for MATH, Countdown, and Geometry3k, with templates sourced from prior work and the verl framework.

G Data Examples

  • MATH and Geometry3k prompts use templates adopted from the verl framework, while the Countdown template follows Pan et al. (2025).The MATH example asks for the smallest initial coin total satisfying equal redistribution across eight bags; the prompt requests a boxed final answer.Source: G Data Examples · pp. 17–18
  • The Countdown example asks the model to use 79, 8, 27, and 47 once each to form an equation equal to 91.The prompt requests work in think tags and the final expression in answer tags.Source: G Data Examples · p. 18
  • The Geometry3k example asks the model to find x, assuming segments that appear tangent are tangent, and to round to the nearest tenth if needed.The prompt specifies a boxed final answer.Source: G Data Examples · p. 18

Related papers

Loading 2609.34990v1…