GIST: Gibbs-Targeted Hierarchical Data Selection for Offline RLVR

Summary (Overview)

  • Core problem: In offline RLVR (Reinforcement Learning with Verifiable Rewards), not all responses and tokens are equally informative, yet standard approaches supervise all tokens of retained responses equally.
  • Key theoretical contribution: The authors derive data selection principles from the bidirectional KL divergence between the current policy and the Gibbs-optimal target policy of KL-regularized RLVR, showing that correct responses are governed by forward KL (coverage) while incorrect responses are governed by reverse KL (over-commitment).
  • Proposed method: GIST (Gibbs-Targeted Hierarchical Data Selection), a two-level selection method that uses only three observable signals—sampling temperature, verifier outcome, and initial-policy token probabilities—to select responses and tokens.
  • Empirical results: GIST improves accuracy across GSM8K, MATH-500, and MBPP for all three tested models under both BOLT and SFT objectives (29 of 30 settings improved), and outperforms seven selection baselines while supervising 66.6% fewer tokens.
  • Key insight: The selection principles are independent of the regularization parameter β—only the balance between correct and incorrect response classes depends on β.

Introduction and Theoretical Foundation

Background

Offline RLVR trains language models on a fixed pool of responses whose outcomes are verified automatically. Common approaches supervise every token of retained responses, but responses and tokens differ in informativeness. Low-probability tokens in high-temperature samples may be noise, but in verified correct responses they likely represent valid steps the policy under-weights. Conversely, failures sampled at low temperature reveal errors near the policy's mode.

Theoretical Foundation

The paper builds on KL-regularized RLVR, which maximizes:

Jx(π)=Ey∼π(⋅∣x)[r(x,y)]−βKL(π(⋅∣x)∥πref(⋅∣x))(1)J_x(\pi) = \mathbb{E}_{y \sim \pi(\cdot|x)}[r(x,y)] - \beta \text{KL}(\pi(\cdot|x) \| \pi_{\text{ref}}(\cdot|x)) \tag{1}

Proposition 2.1 (Gibbs target): The unique maximizer is:

π⋆(y∣x)=πref(y∣x)er(x,y)/βZ(x),Z(x)=∑y′πref(y′∣x)er(x,y′)/β(2)\pi^{\star}(y|x) = \frac{\pi_{\text{ref}}(y|x) e^{r(x,y)/\beta}}{Z(x)}, \quad Z(x) = \sum_{y'} \pi_{\text{ref}}(y'|x) e^{r(x,y')/\beta} \tag{2}

with the objective gap:

Jx(π⋆)−Jx(π)=βKL(π(⋅∣x)∥π⋆(⋅∣x))(3)J_x(\pi^{\star}) - J_x(\pi) = \beta \text{KL}(\pi(\cdot|x) \| \pi^{\star}(\cdot|x)) \tag{3}

Offline fitting: The forward KL can be rewritten as a weighted likelihood objective:

Ex[KL(π⋆∥πθ)]=ExEy∼μ[−ρ(x,y)log⁡πθ(y∣x)]+C,ρ(x,y)=πref(y∣x)μ(y∣x)er(x,y)/βZ(x)(4)\mathbb{E}_x[\text{KL}(\pi^{\star} \| \pi_\theta)] = \mathbb{E}_x \mathbb{E}_{y \sim \mu}[-\rho(x,y) \log \pi_\theta(y|x)] + C, \quad \rho(x,y) = \frac{\pi_{\text{ref}}(y|x)}{\mu(y|x)} \frac{e^{r(x,y)/\beta}}{Z(x)} \tag{4}

Token-level factorization: The Gibbs target factorizes over tokens as:

π⋆(a∣s)=πref(a∣s)Z(sa)Z(s)(5)\pi^{\star}(a|s) = \pi_{\text{ref}}(a|s) \frac{Z(sa)}{Z(s)} \tag{5}

Methodology

Bidirectional Mismatch and Curvature Score

For a fixed prompt xx, define py=π⋆(y∣x)p_y = \pi^{\star}(y|x) and qy=πθ(y∣x)q_y = \pi_\theta(y|x). The bidirectional mismatch is:

Dλ(p,q)=KL(p∥q)+λKL(q∥p),Uyλ=(py−qy)2(1qy+λpy)(7)D_\lambda(p,q) = \text{KL}(p\|q) + \lambda \text{KL}(q\|p), \quad U_y^\lambda = (p_y - q_y)^2 \left(\frac{1}{q_y} + \frac{\lambda}{p_y}\right) \tag{7}

Theorem 3.1 (KL-curvature bounds): Under bounded density ratios γ≤py/qy≤Γ\gamma \leq p_y/q_y \leq \Gamma:

c−Uλ≤Dλ≤c+Uλc_- U^\lambda \leq D_\lambda \leq c_+ U^\lambda

where c−=12min⁡{Γ−1,γ}c_- = \frac{1}{2}\min\{\Gamma^{-1}, \gamma\} and c+=12max⁡{γ−1,Γ}c_+ = \frac{1}{2}\max\{\gamma^{-1}, \Gamma\}.

Corollary 3.3 (Informative correct and incorrect responses):

  • If r=1r=1 and qy≪pyq_y \ll p_y: Uyλ∼py2/qyU_y^\lambda \sim p_y^2/q_y (forward term dominates) — favors under-represented correct responses
  • If r=0r=0 and qy≫pyq_y \gg p_y: Uyλ∼λqy2/pyU_y^\lambda \sim \lambda q_y^2/p_y (reverse term dominates) — favors over-represented incorrect responses

Proposition 3.4 (Exact mismatch at reference policy): At q=πrefq = \pi_{\text{ref}}, Kyλ=qyhλ(κr(x))K_y^\lambda = q_y h_\lambda(\kappa_r(x)) where κr(x)=er/β/Z(x)\kappa_r(x) = e^{r/\beta}/Z(x). With P(x)P(x) the reference success probability: κ1≈1/P(x)>1\kappa_1 \approx 1/P(x) > 1 and κ0≈e−1/β/P(x)<1\kappa_0 \approx e^{-1/\beta}/P(x) < 1.

Token-Level Mismatch

Corollary 3.6 (Informative tokens):

  • In correct responses: low-probability tokens (qt≪ptq_t \ll p_t) carry the forward mismatch
  • In incorrect responses: high-probability tokens (qt≫ptq_t \gg p_t) carry the reverse mismatch

Proposition 3.7: At πθ=πref\pi_\theta = \pi_{\text{ref}}: Ktλ=qthλ(ρt)K_t^\lambda = q_t h_\lambda(\rho_t) where ρt=Z(styt)/Z(st)\rho_t = Z(s_t y_t)/Z(s_t) and ρt≤1/qt\rho_t \leq 1/q_t.

GIST Algorithm

Response-level selection (temperature pairing):

  • Correct responses from on-policy pool (τh=1.0\tau_h = 1.0)
  • Incorrect responses from near-mode pool (τl=0.3\tau_l = 0.3)
  • Keep prompts with both classes (eligible prompts), sample B+=4B_+ = 4 correct and B−=4B_- = 4 incorrect uniformly

Token-level selection (masks):

mt+=1[qt<qˉ] for correct responsesm_t^+ = \mathbf{1}[q_t < \bar{q}] \text{ for correct responses} mt−=1[qt>qˉ] for incorrect responses(12)m_t^- = \mathbf{1}[q_t > \bar{q}] \text{ for incorrect responses} \tag{12}

where qˉ\bar{q} is the mean token probability over the response.

Training: Combined with BOLT (weighted by er/βe^{r/\beta}, rescaled so prompt weights average to 1) or SFT (unit weights).

Empirical Validation / Results

Main Results (Table 2)

ModelMethodGSM8K StrictGSM8K Flex.MATH-500 StrictMATH-500 Flex.MBPP pass@1Avg.
Qwen3-0.6BBOLT43.2947.4644.6050.4026.6041.49
BOLT+GIST45.7949.7345.4051.0031.4044.04
Qwen3.5-2BBOLT54.1354.5146.4054.4042.4050.44
BOLT+GIST56.6357.0947.4056.2041.8051.70
Gemma-4-E2BBOLT12.8926.3140.8052.8056.4045.17
BOLT+GIST14.1029.5742.2053.2057.0046.59

Comparison with Baselines (Table 3, Qwen3-0.6B/GSM8K)

MetricRandomPODSRFT-styleRSI-SETSProFitHESGIST
Strict ↑43.1443.5244.0543.2143.7542.4644.2045.79
Flex. ↑48.6048.2248.1447.8447.5446.4747.3149.73

Ablation Study (Table 4)

Removing any component hurts performance:

  • Removing all selection: −1.97/−3.03 points
  • Removing pairing: −2.20/−0.98 points
  • Removing mask: −2.04/−2.12 points
  • Removing Boltzmann weights: −1.97/−1.59 points

Key interaction: The mask adds 2.04/2.12 points with pairing but only 0.45/0.15 without it.

Efficiency (Table 6)

AllRandomGIST
Tokens13.60M6.64M4.55M
Reduction-51.2%66.6%
Strict ↑43.8243.1445.79

GIST also requires only 2,394 optimizer steps vs. 4,779 for all candidates (49.9% fewer).

Theoretical and Practical Implications

Theoretical Implications

  1. Unified selection framework: The paper provides a principled, theory-driven framework for data selection in offline RLVR, unifying response-level and token-level selection under a single bidirectional KL-divergence analysis.

  2. β-independence of selection principles: The four selection principles (Table 1) hold for every β>0\beta > 0; only the class balance depends on β through the ratio:

Rλ(x)=(1−P(x))hλ(κ0)P(x)hλ(κ1)(10)R_\lambda(x) = \frac{(1-P(x)) h_\lambda(\kappa_0)}{P(x) h_\lambda(\kappa_1)} \tag{10}
  1. Exact factorization at reference policy: The mismatch factorizes exactly at the reference policy, enabling principled selection before training begins.

Practical Implications

  1. Efficiency: GIST achieves higher accuracy while supervising 66.6% fewer tokens and taking 49.9% fewer optimizer steps—significant compute savings.

  2. Generality: GIST uses only observable signals (temperature, verifier outcome, initial-policy probabilities), works across model families (Qwen, Gemma), and pairs with different offline objectives (BOLT, SFT).

  3. Contrary to existing practice: Unlike ProFit which keeps high-probability tokens, GIST keeps low-probability tokens of correct responses—a finding that challenges existing heuristics.

Conclusion

GIST addresses the central design question in offline RLVR: which responses and tokens to supervise. By analyzing the bidirectional KL mismatch between the policy and its Gibbs-optimal target, the authors derive four selection principles that separate the roles of correct and incorrect responses at both response and token levels. The resulting method improves accuracy across nearly all tested settings while supervising substantially fewer tokens.

Future directions suggested by the authors include:

  • Applying the analysis to other offline objectives
  • Settings where data are re-selected as the policy changes (online/iterative selection)
  • The broader principle that "which responses and which tokens to train on can be read from the policy itself"

Related papers