🤖 AI

VERIFY-RL: Verifiable Recursive Decomposition for Reinforcement Learning in Mathematical Reasoning

Verify-RL is a reinforcement learning framework that improves mathematical reasoning by using symbolic differentiation to ensure that problem decompositions are mathematically grounded, structurally simpler, and verifiable by construction.

Original authors: Kaleem Ullah Qasim, Jiashu Zhang, Hao Li, Muhammad Kafeel Shaheen

Published 2026-02-10

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Kaleem Ullah Qasim, Jiashu Zhang, Hao Li, Muhammad Kafeel Shaheen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a child how to solve complex, multi-step math problems.

Most current AI models are taught like students who are handed a massive, terrifying textbook of advanced calculus on day one. They try to "guess" their way through the problems by looking at similar ones they've seen before. Sometimes they get lucky, but often they get confused, try to solve things that are too hard, or follow "shortcuts" that don't actually make sense.

The researchers behind VERIFY-RL decided to change the teaching method entirely. Instead of letting the AI "guess" how to break down a hard problem, they built a mathematical training course that is impossible to cheat on.

Here is how it works, explained through three simple analogies:

1. The "Lego Instruction" Rule (Verification by Construction)

Imagine you want to build a giant, complex Lego castle.

The Old Way (Heuristic): You tell a student, "Try to break this castle down into smaller pieces." The student might grab a handful of random bricks and say, "Here, these are the smaller pieces!" But those pieces might not actually belong to the castle, or they might be just as hard to put together as the castle itself. This creates "noise" and confusion.
The VERIFY-RL Way: This method uses the actual "instruction manual" of math (calculus rules). It says, "You can only break this castle down if you follow these specific, proven steps." If the student tries to break a piece off that doesn't follow the rules, the system immediately says, "No, that’s not a valid step." This is what they call "Verification by Construction"—the pieces are guaranteed to be correct because they were born from the rules.

2. The "Video Game Level" Strategy (Curriculum Learning)

Think about how a video game like Super Mario works. You don't start by fighting the final boss in a lava castle. You start by jumping over a single mushroom in a green field. As you get better, the levels get harder.

VERIFY-RL creates a "Mathematical Staircase."

Step 1: Learn the absolute basics (the "mushrooms").
Step 2: Learn how to combine two basics (the "Goombas").
Step 3: Learn how to combine those combinations (the "Koopas").
Step 4: Finally, tackle the "Final Boss" (the complex calculus problem).

Because the researchers use math rules to build this staircase, they can guarantee that Step 2 is actually easier than Step 3. In older methods, the "staircase" was often broken—some steps were actually harder than the ones before them, causing the AI to trip and fall.

3. The Three Golden Rules (The V1, V2, V3 Properties)

To make sure the training is perfect, every single "sub-problem" the AI learns must pass a three-part inspection:

Is it actually easier? (The "Baby Step" Rule): You can't teach a toddler to run a marathon. The sub-problem must be simpler than the big one.
Is it actually helpful? (The "Building Block" Rule): If you are learning to bake a cake, learning how to crack an egg is helpful. Learning how to tie your shoes is not. The sub-problem must be a piece of the final puzzle.
Is it actually related? (The "Family Tree" Rule): You can't solve a math problem by suddenly deciding to learn history. The sub-problem must be a direct "descendant" of the main problem.

The Result: A Smarter Student

By using this rigorous, rule-based training, the researchers saw incredible results. When the AI faced the hardest possible problems, its accuracy more than doubled (jumping from 32% to 68%).

In short: Instead of asking the AI to "figure it out," they gave it a perfectly organized, mathematically guaranteed ladder to climb, ensuring that every step it took was solid, meaningful, and moving it closer to the top.

Technical Summary: VERIFY-RL

VERIFY-RL: Verifiable Recursive Decomposition for Reinforcement Learning in Mathematical Reasoning

1. Problem Statement

Training Large Language Models (LLMs) to solve complex mathematical problems often relies on curriculum learning, where models are progressively trained on simpler subproblems. However, existing decomposition methods (such as LADDER) are primarily heuristic, relying on LLMs to propose "easier" variants of hard problems. This approach suffers from three critical flaws:

Lack of Guarantees: There is no mathematical assurance that the generated subproblems are actually easier or that their solutions are relevant to the parent task.
Noise Injection: A significant portion of heuristic decompositions (approximately 21.6% in this study) fail basic validity checks, introducing "spurious patterns" or unsolvable problems into the training set.
Unverified Prerequisites: Current curricula assume a logical progression of difficulty rather than verifying that the prerequisite knowledge is formally established.

2. Methodology

The authors propose VERIFY-RL, a framework that replaces heuristic decomposition with rule-based decomposition grounded in symbolic differentiation. By using calculus rules (chain, product, and sum rules), the framework achieves "verification by construction."

A. The Three Verifiable Properties (V1–V3):
Every parent-child relationship in the decomposition tree must satisfy:

V1: Structural Simplicity (Easier): The child problem must have a strictly lower nesting depth ( $\delta(c) < \delta(p)$ ) than the parent.
V2: Solution Containment (Helpful): The solution to the child problem must appear as a mathematical factor or term within the parent's solution ( $\sigma(c) \preceq \sigma(p)$ ).
V3: Rule Derivation (Related): The decomposition must be explicitly derived from a formal calculus rule (e.g., the chain rule).

B. Curriculum Construction:
The framework builds a curriculum by recursively decomposing target problems into a Decomposition Tree. These problems are then organized using topological sorting based on their nesting depth, ensuring a strict "easy-to-hard" progression ( $D_1 \to D_2 \to \dots \to D_5$ ).

C. Reinforcement Learning (RL) Setup:

Algorithms: The framework was tested using GRPO (Group Relative Policy Optimization), PPO, and DPO. GRPO was found to be most effective due to its group-relative advantage normalization, which stabilizes training for reasoning tasks.
Reward Function: A simple rule-based reward system was used, combining accuracy (verified via SymPy symbolic simplification) and format (correct use of delimiters like \boxed{}).

3. Key Contributions

Formal Framework: Introduced a mathematically grounded decomposition theory for symbolic differentiation.
Verification by Construction: Developed decomposition operators for calculus rules that guarantee 100% satisfaction of verification properties, eliminating the noise found in LLM-generated curricula.
Topological Curriculum Algorithm: A method to guarantee prerequisite ordering through the systematic traversal of verified decomposition trees.
Empirical Validation: Demonstrated that eliminating invalid decompositions directly correlates with higher sample efficiency and accuracy.

4. Results

The experiments were conducted on models ranging from 0.6B to 3B parameters (Qwen3 and DeepSeek-R1-Distill).

Accuracy Gains: VERIFY-RL yielded substantial improvements. Most notably, on the hardest problems ( $D_5$ ), accuracy more than doubled (e.g., for Qwen3-1.5B, increasing from 32% to 68%). Overall relative improvement was 40%.
Algorithm Performance: GRPO consistently outperformed PPO and DPO, providing the most stable optimization for mathematical reasoning.
Ablation Insights:
- Curriculum Order: Easy-to-hard ordering was crucial; hard-to-easy ordering performed the worst.
- Verification Importance: Removing the "Easiness" property (V1) caused the largest performance drop (-17.2 points), proving that difficulty guarantees are the backbone of the framework.
- Complexity: Interestingly, complex reward shaping (adding step-level rewards) provided only marginal gains (+1.0 point), suggesting that the structure of the curriculum is more important than the complexity of the reward signal.
Efficiency: The training produced more "calibrated" models. Unlike baseline models that produced long, rambling, incorrect responses for hard problems, the trained models produced more concise and correct reasoning traces.

5. Significance

VERIFY-RL shifts the paradigm of curriculum learning from probabilistic/heuristic (relying on model intuition) to deterministic/verifiable (relying on formal mathematical rules). This work demonstrates that in domains with structured logic (like mathematics or code), "verification by construction" can significantly mitigate the noise inherent in self-improving LLMs, leading to much higher reasoning capabilities and training stability.