Critique-GRPO: Advancing LLM Reasoning with Natural Language and Numerical Feedback — part 5/7

Cleaned-text code points [62667, 78321). Bibliography omitted here; source.md includes it.

For reward-informative LLF problems with constant C F C_{F} , the Transfer Eluder Dimension is bounded by the standard Eluder Dimension of the effective reward class ℛ ℋ = { r η : η ∈ ℋ } \mathcal{R}_{\mathcal{H}}=\{r_{\eta}:\eta\in\mathcal{H}\} : dim T ​ E ( ℋ , C F ​ ℓ , ϵ ) ≤ dim E ( ℛ ℋ , ϵ ) . \dim_{TE}(\mathcal{H},C_{F}\ell,\epsilon)\leq\dim_{E}(\mathcal{R}_{\mathcal{H}},\epsilon). (9)

Proposition F.5 guarantees that learning from critiques is no harder than learning from rewards. However, in practice, the inequality is strict and the gap is large. Below, we quantify this gap for reasoning tasks.

##### Complexity Reduction Analysis.

We analyze the reduction in the effective search space for a reasoning task where the goal is to construct a hidden optimal solution sequence a ∗ = ( s 1 ∗ , … , s L ∗ ) a^{*}=(s^{*}_{1},\dots,s^{*}_{L}) of length L L over a vocabulary 𝒮 \mathcal{S} . The action space is defined as 𝒜 = 𝒮 L \mathcal{A}=\mathcal{S}^{L} .

###### Proposition F.6 (Sample Efficiency of Critique-Guided Refinement) .

We compare the dimension of the hypothesis space under Reward-Only Learning versus Critique-Guided Learning.

1. Standard Generation – Reward-Only Learning (Eluder Dimension): With binary rewards r ⁡ ( a ) = 𝕀 ⁡ ( a = a ∗ ) r(a)=\mathbb{I}(a=a^{*}) , the signal is sparse (a “needle in a haystack”). Observing r ⁡ ( a ) = 0 r(a)=0 eliminates only the specific sequence a a , providing no information about the correctness of other sequences a ′ ≠ a a^{\prime}\neq a . Consequently, the agent must effectively enumerate the action space to find a ∗ a^{*} . The Eluder dimension scales exponentially with the sequence length: dim E ( ℛ , ϵ ) ≈ O ⁡ ( | 𝒮 | L ) . \dim_{E}(\mathcal{R},\epsilon)\approx O(|\mathcal{S}|^{L}). (10)

2. Critique-Guided Refinement – Critique-Guided Learning (Transfer Eluder Dimension): We analyze two types of feedback mechanisms: • Indicative Feedback ( c I c_{\text{I}} , c GT c_{\text{GT}} ): This feedback indicates failure but lacks specific error localization. While the worst-case complexity remains dim T ​ E ( ℋ , ℓ , ϵ ) ≈ O ⁡ ( | 𝒮 | L ) \dim_{TE}(\mathcal{H},\ell,\epsilon)\approx O(|\mathcal{S}|^{L}) , the critique acts as a pruning signal. Conditioning on the failure and the specific content of the critique restricts the search to a subspace 𝒜 c ⊂ 𝒜 \mathcal{A}_{c}\subset\mathcal{A} , reducing the effective search space size by a constant factor α < 1 \alpha<1 .

• Constructive Feedback ( c CoT c_{\text{CoT}} ): If the critique localizes the first error at step t t , the problem decomposes into L L sequential sub-problems, each of size | 𝒮 | |\mathcal{S}| . This reduces the complexity from exponential to linear, i.e., dim T ​ E ( ℋ , ℓ , ϵ ) ≈ O ⁡ ( L ​ | 𝒮 | ) \dim_{TE}(\mathcal{H},\ell,\epsilon)\approx O(L|\mathcal{S}|) . Furthermore, if the critique provides the correction suggestion for the first error s t ∗ s_{t}^{*} , the complexity becomes independent of the vocabulary size, scaling as dim T ​ E ( ℋ , ℓ , ϵ ) ≈ O ⁡ ( L ) \dim_{TE}(\mathcal{H},\ell,\epsilon)\approx O(L) .

Consequently, for a fixed computational budget M M where L ​ | 𝒮 | ≪ M ≪ | 𝒮 | L L|\mathcal{S}|\ll M\ll|\mathcal{S}|^{L} , critique-guided exploration yields a significantly higher probability of success: P ⁡ ( a ∗ ∈ { y refined ( j ) } j = 1 M ) ≫ P ⁡ ( a ∗ ∈ { y ( i ) } i = 1 M ) . P(a^{*}\in\{y_{\text{refined}}^{(j)}\}_{j=1}^{M})\gg P(a^{*}\in\{y^{(i)}\}_{i=1}^{M}). (11)

###### Proof.

We prove this by estimating the Transfer Eluder Dimension d d , which quantifies the effective search space size. We assume a uniform exploration strategy over the effective search space.

1. Derivation of Effective Dimension ( d d )

Case A: Reward-Only. The binary indicator problem is equivalent to a standard bandit problem with | 𝒮 | L |\mathcal{S}|^{L} arms. In this setting, the feedback function is simply the reward itself, f η ​ ( a ) = r ​ ( a ) f_{\eta}(a)=r(a) . Observing r ⁡ ( a ) = 0 r(a)=0 provides information only about action a a and no other a ′ ≠ a a^{\prime}\neq a . Thus, a ′ a^{\prime} is ϵ \epsilon -independent of a a (Definition F.1 ). We can construct a sequence of independent actions spanning the entire space. Thus, the dimension is bounded by the cardinality of the action space: d std = | 𝒮 | L . d_{\text{std}}=|\mathcal{S}|^{L}. (12)

Case B: Critique-Guided (Constructive). Let the feedback f ⁡ ( a ) f(a) return the index of the first error: t = min ⁡ { i ∣ s i ≠ s i ∗ } t=\min\{i\mid s_{i}\neq s^{*}_{i}\} . We partition the action space 𝒜 \mathcal{A} into L L disjoint sets, where 𝒜 t = { ( s 1 , … , s L ) ∣ s 1 : t − 1 are correct, s t is incorrect } \mathcal{A}_{t}=\{(s_{1},\dots,s_{L})\mid s_{1:t-1}\text{ are correct, }s_{t}\text{ is incorrect}\} . According to Definition F.3 , an action is transfer-dependent if similar feedback implies similar rewards. If we select more than | 𝒮 | |\mathcal{S}| actions from a partition 𝒜 t \mathcal{A}_{t} , by the Pigeonhole Principle, at least two actions must share the same incorrect token s t s_{t} (given they share the same correct prefix). Observing the error index t t for the first action effectively predicts the error index for the second. This reduces the problem to solving L L sequential classification problems of size | 𝒮 | |\mathcal{S}| . The effective dimension is the sum of these sub-problems: d crit = ∑ t = 1 L | 𝒮 | = L ​ | 𝒮 | . d_{\text{crit}}=\sum_{t=1}^{L}|\mathcal{S}|=L|\mathcal{S}|. (13) If the critique also provides the correction suggestion for the first error s t ∗ s_{t}^{*} , the sequence of error indices in an independent action sequence becomes strictly monotonic, further reducing the dimension to d corr ≈ O ⁡ ( L ) d_{\text{corr}}\approx O(L) .

2. Probability of Success

Let M M be the computational budget. The probability of finding the unique optimal solution a ∗ a^{*} is equivalent to sampling the correct element from a set of size d d without replacement. The probability of success is approximately: P ⁡ ( success ) ≈ 1 − exp ⁡ ( − M d ) . P(\text{success})\approx 1-\exp\left(-\frac{M}{d}\right). (14)

Given the regime L ​ | 𝒮 | ≪ M ≪ | 𝒮 | L L|\mathcal{S}|\ll M\ll|\mathcal{S}|^{L} :

For Reward-Only Learning , substituting d std = | 𝒮 | L d_{\text{std}}=|\mathcal{S}|^{L} : P std ≈ 1 − exp ⁡ ( − M | 𝒮 | L ) ≈ M | 𝒮 | L ≈ 0 . P_{\text{std}}\approx 1-\exp\left(-\frac{M}{|\mathcal{S}|^{L}}\right)\approx\frac{M}{|\mathcal{S}|^{L}}\approx 0. (15)

For Critique-Guided Learning , substituting d crit = L ​ | 𝒮 | d_{\text{crit}}=L|\mathcal{S}| : P crit ≈ 1 − exp ⁡ ( − M L ​ | 𝒮 | ) ≈ 1 . P_{\text{crit}}\approx 1-\exp\left(-\frac{M}{L|\mathcal{S}|}\right)\approx 1. (16)

Conclusion. The ratio of success probabilities is P crit P std ≈ | 𝒮 | L M ≫ 1 \frac{P_{\text{crit}}}{P_{\text{std}}}\approx\frac{|\mathcal{S}|^{L}}{M}\gg 1 . This confirms that critique-guided refinement is strictly more sample-efficient than standard reward-based generation. ∎

### F.5 Theoretical Analysis of Convergence and Policy Improvement

Building upon the sample efficiency established in Appendix F.4 , we now analyze the optimization dynamics. We prove that while standard GRPO converges given sufficient samples, Critique-GRPO accelerates this process by altering the trajectory distribution. We utilize the framework of Policy Gradient methods ( Sutton et al., 1999 ; Agarwal et al., 2021 ) to demonstrate that Critique-GRPO learns from higher quality trajectories , guaranteeing a steeper monotonic policy improvement.

##### Preliminaries and Problem Setup.

We consider the reasoning task as a contextual bandit problem ( Lu et al., 2010 ) . Let π θ ​ ( y | x ) \pi_{\theta}(y|x) be the policy parameterized by θ \theta .

###### Definition F.7 (Sparse Reward Landscape) .

The reward function R ⁡ ( y , x ) R(y,x) is binary and sparse. Let 𝒴 x ∗ \mathcal{Y}^{*}_{x} be the set of correct reasoning chains. R ⁡ ( y , x ) = 𝕀 ⁡ ( y ∈ 𝒴 x ∗ ) . R(y,x)=\mathbb{I}(y\in\mathcal{Y}^{*}_{x}). (17)

###### Definition F.8 (GRPO Gradient Estimate) .

Following Shao et al. (2024a) , GRPO estimates the gradient using a group of G G outputs { y 1 , … , y G } \{y_{1},\dots,y_{G}\} sampled from π θ old \pi_{\theta_{\text{old}}} for a single input x x . The gradient estimator is: g ^ GRPO = 1 G ​ ∑ i = 1 G A ^ i ​ ∇ θ ​ log ⁡ π θ ​ ( y i | x ) , where ​ A ^ i = R ⁡ ( y i ) − μ R σ R + ϵ . \hat{g}_{\text{GRPO}}=\frac{1}{G}\sum_{i=1}^{G}\hat{A}_{i}\nabla_{\theta}\log\pi_{\theta}(y_{i}|x),\quad\text{where }\hat{A}_{i}=\frac{R(y_{i})-\mu_{R}}{\sigma_{R}+\epsilon}. (18)

#### F.5.1 Inefficiency of Standard Exploration

In complex reasoning tasks, the probability of generating a correct solution y ∗ y^{*} via random sampling, denoted as p ∗ = P y ∼ π θ ​ ( y ∈ 𝒴 x ∗ ) p^{*}=P_{y\sim\pi_{\theta}}(y\in\mathcal{Y}^{*}_{x}) , is small but non-negligible. While standard GRPO is an unbiased estimator, its convergence rate is limited by the sparsity of the signal.

###### Proposition F.9 (Signal-to-Noise Ratio in Standard GRPO) .

For a group size G G , the expected number of positive rewards in a standard GRPO batch is 𝔼 ⁡ [ N + ] = G ​ p ∗ \mathbb{E}[N^{+}]=Gp^{*} . The gradient contribution from optimal trajectories is weighted by p ∗ p^{*} . If p ∗ < 1 / G p^{*}<1/G , many batches will contain no positive signal ( σ R = 0 \sigma_{R}=0 ), resulting in wasted computation steps where Δ ​ θ = 0 \Delta\theta=0 . Even when σ R > 0 \sigma_{R}>0 , the magnitude of the update in the direction of the optimal policy is proportional to p ∗ p^{*} .

#### F.5.2 Policy Improvement via Critique-Guided Refinement

Critique-GRPO modifies the sampling distribution. Instead of optimizing solely on y ∼ π θ y\sim\pi_{\theta} , we optimize on a mixture distribution induced by the critique mechanism. Let the refined set be 𝒴 ref = { Refine ​ ( y ) ∣ y ∼ π θ } \mathcal{Y}_{\text{ref}}=\{\text{Refine}(y)\mid y\sim\pi_{\theta}\} .

###### Lemma F.10 (Trajectory Quality Enhancement) .

Let P crit P_{\text{crit}} be the success rate of the critique mechanism in generating a correct solution y ∗ y^{*} . As shown in Proposition 4.1 , P crit ≫ p ∗ P_{\text{crit}}\gg p^{*} . By including 𝒴 ref \mathcal{Y}_{\text{ref}} in the GRPO group, the effective probability of observing an optimal trajectory in the batch becomes P eff ≈ P crit P_{\text{eff}}\approx P_{\text{crit}} . This ensures that the gradient estimator is dominated by high-quality trajectories, significantly reducing the variance of the advantage function and ensuring σ R > 0 \sigma_{R}>0 with high probability.

We now prove that learning from these higher-quality trajectories leads to superior policy improvement.

###### Theorem F.11 (Policy Improvement Lower Bound) .

Let π old \pi_{\text{old}} be the current policy and π new \pi_{\text{new}} be the policy after an update step with learning rate α \alpha . The expected improvement in the objective function J ⁡ ( π ) J(\pi) is lower-bounded by the quality of the trajectories used in the update. Comparing Standard GRPO and Critique-GRPO: Δ ​ J std \displaystyle\Delta J_{\text{std}} ≥ α ⋅ p ∗ ⋅ 𝔼 ⁡ [ 1 σ R ​ π old ​ ( y ∗ ) ​ ‖ ∇ log ⁡ π ​ ( y ∗ ) ‖ 2 ] − O ⁡ ( α 2 ) \displaystyle\geq\alpha\cdot p^{*}\cdot\mathbb{E}\left[\frac{1}{\sigma_{R}}\pi_{\text{old}}(y^{*})\|\nabla\log\pi(y^{*})\|^{2}\right]-O(\alpha^{2}) (19) Δ ​ J crit \displaystyle\Delta J_{\text{crit}} ≥ α ⋅ P crit ⋅ 𝔼 ⁡ [ 1 σ R ​ π old ​ ( y ∗ ) ​ ‖ ∇ log ⁡ π ​ ( y ∗ ) ‖ 2 ] − O ⁡ ( α 2 ) \displaystyle\geq\alpha\cdot P_{\text{crit}}\cdot\mathbb{E}\left[\frac{1}{\sigma_{R}}\pi_{\text{old}}(y^{*})\|\nabla\log\pi(y^{*})\|^{2}\right]-O(\alpha^{2}) (20) Since P crit ≫ p ∗ P_{\text{crit}}\gg p^{*} , it follows that Δ ​ J crit ≫ Δ ​ J std \Delta J_{\text{crit}}\gg\Delta J_{\text{std}} .

###### Proof.

Step 1: Performance Difference. From Kakade and Langford (2002) , J ⁡ ( π new ) − J ⁡ ( π old ) ≈ 𝔼 y ∼ ρ ​ [ A ^ ​ ( y ) ] J(\pi_{\text{new}})-J(\pi_{\text{old}})\approx\mathbb{E}_{y\sim\rho}[\hat{A}(y)] , where ρ \rho is the sampling distribution. The update vector Δ ​ θ \Delta\theta is proportional to the advantage-weighted gradient: Δ θ ∝ ∑ y ∈ Batch A ^ ( y ) ∇ log π ( y ) \Delta\theta\propto\sum_{y\in\text{Batch}}\hat{A}(y)\nabla\log\pi(y) .

Step 2: Dominance of Optimal Trajectories. In a sparse reward setting, the advantage of an optimal solution y ∗ y^{*} is positive and large, while incorrect solutions have small negative advantages. The update direction is dominated by the term corresponding to y ∗ y^{*} : Δ θ ≈ η ⋅ A ^ ( y ∗ ) ∇ log π ( y ∗ ) . \Delta\theta\approx\eta\cdot\hat{A}(y^{*})\nabla\log\pi(y^{*}). (21) The magnitude of this update depends on the frequency of observing y ∗ y^{*} in the batch.

Step 3: Comparison of Sampling Distributions. • Standard GRPO: Samples y ∼ π old y\sim\pi_{\text{old}} . The probability of observing y ∗ y^{*} is p ∗ p^{*} . The expected update norm is proportional to p ∗ ​ ‖ ∇ log ⁡ π ​ ( y ∗ ) ‖ p^{*}\|\nabla\log\pi(y^{*})\| .

• Critique-GRPO: Samples from a mixture including refined outputs. The probability of observing y ∗ y^{*} is P crit P_{\text{crit}} . The expected update norm is proportional to P crit ​ ‖ ∇ log ⁡ π ​ ( y ∗ ) ‖ P_{\text{crit}}\|\nabla\log\pi(y^{*})\| .

Conclusion: The superiority of Critique-GRPO lies in the fact that it learns from a distribution of higher trajectories . Even if standard exploration is capable of finding the solution (non-negligible p ∗ p^{*} ), the critique mechanism artificially amplifies the density of optimal solutions in the training data. Substituting the observation probabilities into the Taylor expansion of the objective function: J ( π new ) − J ( π old ) ≈ ∇ J ( π old ) ⊤ Δ θ ∝ P ( observing y ∗ ) ⋅ ∥ ∇ log π ( y ∗ ) ∥ 2 . J(\pi_{\text{new}})-J(\pi_{\text{old}})\approx\nabla J(\pi_{\text{old}})^{\top}\Delta\theta\propto P(\text{observing }y^{*})\cdot\|\nabla\log\pi(y^{*})\|^{2}. (22) Given P crit ≫ p ∗ P_{\text{crit}}\gg p^{*} , the lower bound on policy improvement is strictly higher for Critique-GRPO. ∎

###### Theorem F.12 (Global Convergence via Policy Shaping) .

Assuming the function approximation class of π θ \pi_{\theta} is sufficiently expressive and the learning rate satisfies Robbins-Monro conditions, Critique-GRPO converges to the optimal policy π ∗ \pi^{*} . The convergence rate is accelerated by a factor of O ⁡ ( P crit / p ∗ ) O(P_{\text{crit}}/p^{*}) compared to standard GRPO.

###### Proof.

We utilize the property that Critique-GRPO simulates Supervised Fine-Tuning (SFT) on dynamically generated optimal data within the RL loop. From Theorem F.11 , the policy probability mass on y ∗ y^{*} increases at each step. Since the gradient variance is bounded (due to the high probability of non-zero variance batches via Lemma F.10 ), stochastic gradient descent converges. Crucially, the effective learning rate on the optimal trajectory y ∗ y^{*} is scaled by the critique success rate. Thus, the model requires fewer iterations to reach the same level of performance as standard GRPO, effectively leveraging the higher quality of the critique-refined trajectories. ∎

### F.6 Theoretical Analysis: Gradient Efficiency and Manifold Preservation

Now we provide a analysis of the optimization dynamics in 𝒥 Critique-GRPO \mathcal{J}_{\text{Critique-GRPO}} after employing the shaping function on the refinements. We address the dual challenge of (1) efficiently extracting learning signals from off-policy refined responses ( y ref y_{\text{ref}} ) and (2) preventing the catastrophic forgetting (entropy explosion) caused by distribution shift.

#### F.6.1 Gradient Dynamics of the Shaping Function