VERIFY-RL: Verifiable Recursive Decomposition for Reinforcement Learning in Mathematical Reasoning Kaleem Ullah Qasim, Jiashu Zhang, Hao Li, Muhammad Kafeel Shaheen Abstract Training language models to solve complex mathematical problems benefits from curriculum learning progressively training on simpler subproblems. However, existing decomposition methods are often heuristic, offering no guarantees that subproblems are simpler, that solving them aids the parent task, or that their relationships are mathematically grounded. We observe that symbolic differentiation provides a natural structure for verified decomposition: calculus rules explicitly define how expressions reduce to simpler components with provable properties. We introduce Verify-RL , a framework where every parent-child decomposition satisfies three verifiable conditions: strictly decreasing structural complexity, solution containment, and formal rule derivation. Unlike heuristic methods where a significant fraction of decompositions are invalid our properties admit automatic verification through symbolic computation, achieving ”verification by construction.” Experiments demonstrate that eliminating invalid decompositions yields sizable gains, accuracy on the hardest problems more than doubles from 32% to 68%, with a 40% relative improvement overall. keywords Recursive Decomposition ,Curriculum learning ,Mathematical Reasoning ,Symbolic Differentiation ,Large Language Models † † corresponding: Corresponding author † † credit: Data curation, Writing - Original draft preparation 1 Introduction Curriculum learning improves mathematical reasoning in language models by decomposing complex problems into simpler subproblems [ 1 , 2 ] . Recent work shows that reinforcement learning with verifiable rewards can push models beyond their supervised training distribution [ 3 ] , and that ordering problems by difficulty improves both sample efficiency and final performance [ 4 , 5 ] . The core challenge lies in constructing such curricula: how do we ensure that subproblems are genuinely easier, that solving them helps solve the original, and that parent-child relationships are mathematically meaningful? Current decomposition methods face a fundamental limitation. Heuristic approaches rely on language models to propose easier variants of hard problems [ 6 ] , offering flexibility but no guarantees about validity. When evaluated against formal criteria, a significant fraction of generated decompositions fail basic properties: the child is not actually easier, its solution does not help solve the parent, or the relationship is spurious. These invalid examples introduce noise into training. Formal verification in theorem proving [ 7 , 8 ] provides provable correctness, but such methods have remained confined to narrow domains with established proof assistants. We present Verify-RL , a framework that achieves the flexibility of curriculum learning with the guarantees of formal verification. The key insight is that symbolic differentiation possesses decomposition rules with built-in mathematical structure: calculus rules define exactly how expressions reduce to simpler components. When differentiating \sin(x^{2}) , the chain rule specifies that x^{2} becomes a subproblem, that its derivative appears in the parent’s solution, and that this relationship follows from a formal rule. We formalize this observation through three verifiable properties: the child must be structurally simpler, the child’s solution must appear in the parent’s solution, and the relationship must derive from a calculus rule. These properties admit automatic verification through symbolic computation, achieving complete verification by construction. We train models ranging from 0.6B to 3B parameters using multiple RL algorithms on curricula constructed via verified decomposition. Training progresses from base-case derivatives through compositions of increasing depth, with each problem’s decomposition tree guaranteeing prerequisite ordering. Unlike heuristic methods where a significant fraction of decompositions are invalid, our rule-based approach achieves complete verification by construction. This translates to substantial accuracy gains: performance more than doubles on the hardest problems, with 40% relative improvement overall. Our contributions are: 1 A formal framework for verifiable decomposition with three properties structural simplicity, solution containment, and rule derivation that admit automatic verification through symbolic computation. 2 Decomposition operators for chain, product, and sum rules with proofs that each preserves verification properties, achieving complete verification by construction. 3 A curriculum construction algorithm that guarantees prerequisite ordering through topological sorting of verified decomposition trees. 4 Experiments across multiple model scales demonstrating substantial accuracy gains, with systematic ablations isolating each component’s contribution. Figure 1 : Verify-RL framework. Problems pass through rule-based decomposition, verification (V1–V3), and curriculum ordering before RL training. Failed verifications trigger re-decomposition. The rest of this paper is organized as follows: Section 2 reviews related work on curriculum learning and reasoning verification. Section 3 presents our formal framework including problem formulation, decomposition theory, and verification procedures. Section 4 describes experimental setup and research questions. Section 5 presents main results and training dynamics. Section 6 provides systematic ablations isolating each component’s contribution. Section 8 concludes with limitations and future directions. 2 Related Work Mathematical reasoning in language models has advanced through prompting strategies that encourage structured problem-solving. Chain-of-thought prompting [ 1 ] demonstrated that eliciting intermediate steps improves arithmetic accuracy, while self-consistency [ 9 ] aggregates multiple reasoning paths via majority voting to reduce variance. These methods expose reasoning but do not decompose problems into subproblems with guaranteed relationships. Task decomposition approaches address complex reasoning by breaking problems into simpler components. Least-to-most prompting [ 10 ] teaches models to solve subproblems sequentially from easiest to hardest, achieving strong generalization on symbolic manipulation tasks. Tree of Thoughts [ 11 ] extends chain-of-thought by exploring multiple reasoning branches with backtracking, enabling deliberate planning. ADaPT [ 12 ] dynamically decomposes failed tasks into subtasks based on execution feedback. FunCoder [ 13 ] applies recursive decomposition to code generation. Recent work on complexity-agnostic recursive decomposition [ 14 ] and logical thought decomposition [ 15 ] explores frameworks for breaking down reasoning tasks recursively, demonstrating improved performance through structured decomposition and knowledge propagation. Hierarchical multi-agent methods [ 16 ] have shown that temporal and structural task decomposition enables effective learning for complex long-horizon problems, though decomposition strategies remain domain-specific. These methods rely on the model to generate or evaluate decompositions heuristically and the subproblem-parent relationship is assumed rather than verified. Self-improvement enables models to bootstrap reasoning capability from their own outputs. STaR [ 17 ] iteratively fine-tunes on model-generated rationales that lead to correct answers, demonstrating that models can learn from successful reasoning traces. ReST [ 18 ] scales self-training by filtering generated solutions through verifiers, while V-STaR [ 19 ] trains verifiers alongside generators to improve sample efficiency. ReST-MCTS* [ 20 ] combines process reward guidance with tree search for more targeted self-improvement. These approaches assume access to correctness signals but do not exploit structured problem decomposition. Reinforcement learning has emerged as a powerful paradigm for reasoning improvement. RLHF [ 21 ] aligns models with human preferences through learned reward functions, while PPO [ 22 ] provides stable policy updates. DeepSeek-R1 [ 3 ] demonstrated that pure RL with verifiable rewards (RLVR) can induce sophisticated reasoning patterns, introducing GRPO for efficient group-relative optimization. Hierarchical RL with option scheduling [ 23 ] addresses sparse reward challenges through unlimited option abstraction. VinePPO [ 24 ] addresses credit assignment limitations in standard PPO by computing Monte Carlo estimates of intermediate values. Recent work [ 25 ] shows RLVR extends model capability beyond supervised fine-tuning. GRPO-LEAD [ 26 ] incorporates difficulty-aware scheduling into GRPO training. DeepSeekMath [ 27 ] pushed mathematical reasoning limits by combining large-scale pretraining with GRPO fine-tuning. Process reward models (PRMs) provide step-level supervision for reasoning verification. Lightman et al. [ 28 ] found that process supervision outperforms outcome supervision for mathematical reasoning, achieving 78% accuracy on MATH. Math-Shepherd [ 29 ] automates process annotation without human labels by verifying step correctness through solution sampling. The distinction between outcome and process supervision [ 30 ] informs reward design: outcome rewards verify final answers while process rewards assess intermediate steps. Curriculum learning [ 31 ] organizes training from easy to hard examples to improve convergence. Recent work [ 32 ] applies this principle to LLM reasoning, where difficulty-ordered training improves mathematical performance. Domain-specific models like Minerva [ 33 ] , Llemma [ 34 ] and MathCoder [ 35 ] combine mathematical pretraining with structured fine-tuning. LADDER [ 6 ] introduced recursive decomposition for self-improvement, where models generate easier variants of hard problems to create training curricula. The model trains on solvable subproblems then bootstraps to harder ones. Complementary approaches [ 14 , 15 ] explore recursive decomposition through complexity-agnostic frameworks and logical reasoning structures, though these methods similarly employ model-generated decompositions. However, LADDER and related heuristic approaches rely on decomposition without mathematical guarantees: the model generates “easier” variants that may not satisfy formal properties. Under formal verification (V1–V3), 21.6% of generated subproblems fail at least one property, introducing noise into training. Despite these advances, existing approaches share three fundamental limitations: (1) Heuristic decomposition methods rely on models to generate subproblems without guarantees that children are actually easier or helpful; (2) No formal verification curriculum ordering assumes rather than verifies prerequisite relationships; and (3) Training instability invalid decompositions introduce noise, causing models to encounter unsolvable problems or learn spurious patterns. Our work addresses these limitations through rule-based decomposition that provides mathematical guarantees (V1–V3), achieving 100% verification success compared to 78.4% for model-generated approaches. Table 1 : Verification Properties V1–V3 with Example Validation Property Definition Example Verification V1: Easier Child has strictly lower nesting depth: \delta(c)<\delta(p) Parent: \frac{d}{dx}[\sin(\cos(x^{2}))] ( \delta=3 ) Child: \cos(x^{2}) ( \delta=2 ) \delta(c)=2<3=\delta(p) ✓ V2: Helpful Child solution appears in parent solution: \sigma(c)\preceq\sigma(p) Parent: \sigma(p)=-\sin(\cos(x^{2}))\cdot\sigma(c)\cdot 2x Child: \sigma(c)=-\sin(x^{2})\cdot 2x \sigma(c) is a factor in \sigma(p) ✓ V3: Related Derived via calculus rule: c\sqsubseteq p Chain rule: \frac{d}{dx}[f(g(x))]=f^{\prime}(g(x))\cdot g^{\prime}(x) c=g(x)=\cos(x^{2}) is inner function ✓ 3 Methods We present Verify-RL , a formal framework for verifiable recursive decomposition in symbolic differentiation (Figure 1 ). The problem space and complexity measure appear in Section 3.1 . Decomposition theory with complete proofs that calculus rules satisfy verification properties V1–V3 follows in Section 3.2 . Verification procedures for checking decomposition validity are formalized in Section 3.3 . Curriculum construction and RL training are described in Section 3.4 , with the reward function presented in Section 3.5 . 3.1 Problem Space and Complexity Measure Let \mathcal{F} denote the set of differentiable functions f:\mathbb{R}\rightarrow\mathbb{R} composed from the basis \mathcal{B}=\{\sin,\cos,\exp,\log,\tan,x^{n}\} under the operations \{+,\times,\circ\} . A differentiation problem p\in\mathcal{P} takes the form \frac{d}{dx}[f(x)] for f\in\mathcal{F} . Definition 1 (Expression Tree) . For f\in\mathcal{F} , the expression tree T_{f} is defined inductively: \displaystyle T_{x} \displaystyle=\text{leaf}(x) (1) \displaystyle T_{c} \displaystyle=\text{leaf}(c)\quad\text{for }c\in\mathbb{R} (2) \displaystyle T_{f\circ g} \displaystyle=\text{node}(f,[T_{g}]) (3) \displaystyle T_{f\cdot g} \displaystyle=\text{node}(\times,[T_{f},T_{g}]) (4) \displaystyle T_{f+g} \displaystyle=\text{node}(+,[T_{f},T_{g}]) (5) Definition 2 (Nesting Depth) . The nesting depth \delta:\mathcal{F}\rightarrow\mathbb{N} measures structural complexity: \delta(e)=\begin{cases}0&\text{if }e\in\{x\}\cup\mathbb{R}\\[4.0pt] 1+\max\limits_{i\in[n]}\delta(a_{i})&\text{if }e=g(a_{1},\ldots,a_{n})\text{ for }g\in\mathcal{B}\\[4.0pt] \max\limits_{i\in[n]}\delta(a_{i})&\text{if }e=\sum_{i=1}^{n}a_{i}\text{ or }e=\prod_{i=1}^{n}a_{i}\end{cases} (6) This measure counts the maximum number of function applications on any root-to-leaf path in T_{f} , excluding additive and multiplicative nodes which do not increase computational difficulty. Verified Decomposition ⬇ # Input: problem p # Output: children verified edges def Decompose ( p ): if depth ( p ) == 1: # Base case return [] children = [] # Try chain rule: f(g(x)) if is_composition ( p ): g = inner_function ( p ) if Verify ( p , g ): # V1,V2,V3 children . append (( g , "chain" )) # Try product rule: u * v if is_product ( p ): u , v = factors ( p ) for c in [ u , v ]: if Verify ( p , c ): children . append (( c , "product" )) return children Curriculum Construction ⬇ # Input: target problems P_target # Output: curriculum C (easy->hard) def BuildCurriculum ( P_target ): all_problems = set () edges = [] for p in P_target : # Recursively decompose stack = [ p ] while stack : curr = stack . pop () all_problems . add ( curr ) for c , rule in Decompose ( curr ): edges . append (( curr , c )) stack . append ( c ) # Topological sort by depth C = TopoSort ( all_problems , key = lambda x : depth ( x )) # D1 -> D2 -> ... -> D5 return C Figure 2: Pseudocode for verified decomposition (left) and curriculum construction (right). Verify checks all three properties V1–V3 before accepting a child problem. Definition 3 (Difficulty Partition) . We partition \mathcal{P} into five levels based on nesting depth: D_{k}=\{p\in\mathcal{P}:\delta(p)=k\}\quad\text{for }k\in\{1,2,3,4,5\} (7) Level D_{1} contains base cases: \frac{d}{dx}[x^{n}]=nx^{n-1} , \frac{d}{dx}[\sin x]=\cos x , \frac{d}{dx}[e^{x}]=e^{x} . Level D_{2} requires one rule application, e.g., \frac{d}{dx}[\sin(x^{2})] . Higher levels involve nested compositions reaching D_{5} for expressions like \frac{d}{dx}[\sin(\cos(\exp(\log(x^{2}))))] with \delta=5 . 3.2 Verifiable Decomposition Theory We formalize decomposition as a mapping \phi:\mathcal{P}\rightarrow 2^{\mathcal{P}} that extracts subproblems from a parent problem. Unlike prior work where models generate “easier” variants heuristically, our decomposition derives directly from calculus differentiation rules. Two forms of containment capture the relationship between parent and child problems. Definition 4 (Structural Containment) . Expression c is structurally contained in p , written c\sqsubseteq p , if T_{c} is a subtree of T_{p} : c\sqsubseteq p\iff\exists\text{ path from root}(T_{p})\text{ to }T_{c}\text{ as subtree} (8) Definition 5 (Solution Containment) . Let \sigma:\mathcal{P}\rightarrow\mathcal{F} denote the solution operator \sigma(p)=\frac{d}{dx}[p] . The solution of c is contained in the solution of p , written \sigma(c)\preceq\sigma(p) , if: \sigma(c)\preceq\sigma(p)\iff\sigma(c)\in\text{factors}(\sigma(p))\cup\text{terms}(\sigma(p)) (9) where \text{factors}(e) extracts multiplicative factors and \text{terms}(e) extracts additive terms. Structural containment ensures the child appears syntactically within the parent. Solution containment ensures the child’s derivative appears within the parent’s derivative. Definition 6 (Verifiable Decomposition) . A decomposition \phi(p)=\{c_{1},\ldots,c_{k}\} is verifiable if each child c_{i} satisfies: V1 : Easier or Equal Complexity: \delta(c_{i})\leq\delta(p) , with strict inequality \delta(c_{i})<\delta(p) required for composition-based decomposition (chain rule, product rule). For additive decomposition (sum rule), weak inequality suffices since additive terms are solved independently without requiring sequential prerequisites. V2 : Solution Helpful: \sigma(c_{i})\preceq\sigma(p) V3 : Structurally Related: c_{i}\sqsubseteq p via a calculus rule \rho\in\{\text{chain},\text{product},\text{sum}\} V1 ensures curriculum ordering: children are solved before parents. V2 ensures knowledge transfer: solving children provides partial solutions to parents. V3 ensures mathematical grounding: the parent-child relationship follows from a formal rule. Table 1 summarizes these properties with concrete examples. Table 2 : Recursive Decomposition Tree Example: D4 to D3 to D2 to D1 Level Problem Difficulty \delta Rule V1 V2 V3 Root \frac{d}{dx}[\sin(\cos(\tan(x^{2})))] D4 4 Child \frac{d}{dx}[\cos(\tan(x^{2}))] D3 3 Chain ✓ ✓ ✓ Grandchild \frac{d}{dx}[\tan(x^{2})] D2 2 Chain ✓ ✓ ✓ Leaf \frac{d}{dx}[x^{2}] D1 1 Chain ✓ ✓ ✓ • Curriculum order: D1 leaf to D2 grandchild to D3 child to D4 root. Each edge satisfies V1 ( \delta decreases by exactly 1), V2 (inner derivative factors into outer via chain rule), and V3 (chain rule derivation). Chain Rule Decomposition. The chain rule handles function composition, the primary source of difficulty in differentiation. For composed functions p=f(g(x)) where g(x)\neq x , define \phi_{\text{chain}}(p)=\{g(x)\} . The inner function becomes the child problem. Theorem 1 (Chain Rule Satisfies V1–V3) . For p=f(g(x)) with g(x)\neq x and c=g(x) : \delta(c)<\delta(p) , \sigma(c)\preceq\sigma(p) , and c\sqsubseteq p . Proof. (V1) By Definition 2 : \delta(p)=\delta(f(g(x)))=1+\delta(g(x))=1+\delta(c) . Since 1+\delta(c)>\delta(c) , we have \delta(p)>\delta(c) . (V2) By the chain rule: \sigma(p)=f^{\prime}(g(x))\cdot\frac{d}{dx}[g(x)]=f^{\prime}(g(x))\cdot\sigma(c) . Thus \sigma(c)\in\text{factors}(\sigma(p)) . (V3) By Definition 1 , T_{p}=\text{node}(f,[T_{c}]) , so T_{c} is a direct subtree. ∎ Product Rule Decomposition. The product rule handles multiplication of two x -dependent terms, generating two children (one per factor). For products p=u(x)\cdot v(x) where both factors depend on x , define \phi_{\text{prod}}(p)=\{u(x),v(x)\} . Theorem 2 (Product Rule Satisfies V1–V3) . For p=u(x)\cdot v(x) with \frac{\partial u}{\partial x}\neq 0 and \frac{\partial v}{\partial x}\neq 0 , each c\in\{u,v\} satisfies V1–V3. Proof. (V1) \delta(p)=\max(\delta(u),\delta(v)) , so \delta(c)\leq\delta(p) . Strict inequality holds when either factor contains compositions. (V2) By the product rule: \sigma(p)=u\cdot\sigma(v)+v\cdot\sigma(u) . Both \sigma(u) and \sigma(v) appear as factors within terms. (V3) T_{u} and T_{v} are subtrees of T_{p}=\text{node}(\times,[T_{u},T_{v}]) . ∎ Sum Rule Decomposition. The sum rule decomposes additive expressions into two children. For sums p=u(x)+v(x) , define \phi_{\text{sum}}(p)=\{u(x),v(x)\} . Lemma 1 (Sum Rule Properties) . For p=u(x)+v(x) and c\in\{u,v\} : (V1) \displaystyle\quad\delta(c)\leq\delta(p)\quad\text{(weak inequality for sum rule)} (10) (V2) \displaystyle\quad\sigma(c)\in\text{terms}(\sigma(p))\text{ since }\sigma(p)=\sigma(u)+\sigma(v) (11) (V3) \displaystyle\quad c\sqsubseteq p\text{ as direct subtree of }T_{p} (12) Recursive Decomposition Tree. Applying \phi repeatedly constructs a decomposition tree \mathcal{T}(p) where every edge satisfies V1–V3, terminating at D_{1} base cases. Definition 7 (Decomposition Tree) . For problem p\in\mathcal{P} , define \mathcal{T}(p) recursively: \mathcal{T}(p)=\begin{cases}(\{p\},\emptyset)&\text{if }\delta(p)=1\\[6.0pt] \begin{aligned} &\Big(\{p\}\cup\bigcup_{c\in\phi(p)}V_{c},\\ &\quad\{(p,c,\rho_{c})\}_{c\in\phi(p)}\cup\bigcup_{c\in\phi(p)}E_{c}\Big)\end{aligned}&\text{otherwise}\end{cases} (13) where (V_{c},E_{c})=\mathcal{T}(c) and \rho_{c}\in\{\text{chain},\text{product},\text{sum}\} is the applicable rule. Theorem 3 (Tree Depth Bound) . For p\in D_{k} , the decomposition tree \mathcal{T}(p) has depth at most k-1 . Proof. By induction on k . Base case k=1 : \mathcal{T}(p)=(\{p\},\emptyset) has depth 0. Inductive step: if p\in D_{k} with k>1 , each child c\in\phi(p) satisfies \delta(c)