RL Post-Training Builds Compositional Reasoning Strategies

# RL Post-Training Builds Compositional Reasoning Strategies
Source: [https://arxiv.org/html/2607.07646](https://arxiv.org/html/2607.07646)
###### Abstract

Does RL post\-training merely amplify primitive skills already latent in a base model, or can it compose primitive skills into new higher\-level strategies? We study this question in a fully observable rewrite\-grammar environment where the pretraining distribution is known and every generated rewrite can be audited\. A Transformer is pretrained on primitive symbol\-rewrite chains and post\-trained on a Trace\-based reasoning task with only a binary final\-answer reward\. RL solves held\-out problems that remain rarely solved by the pretrained model even under much larger sampling budgets, while rejection fine\-tuning improves early but plateaus\. Trace analysis shows that RL reorganizes primitive competence through a phased compositional mechanism: it first strengthens primitive reductions, then discovers valid composed procedures\. These include sequential compositions, which collapse ordered chains of primitive contractions, and parallel compositions, which combine independent primitive contractions in a single step\. The composed procedures are not isolated samples; they are reused and consolidated into a stable repertoire\. Comparing RL with rejection fine\-tuning shows that the key difference is not exploration volume but selectivity: RFT produces many shortcut\-like rewrites, much of them invalid, whereas RL concentrates exploration into valid reusable structure\. Pretraining ablations show that the emergence of compositional strategies is gated not by primitive exposure alone, but by whether pretraining organizes primitive competence into reduction procedures that RL can later compress\. The base model provides weak procedural ingredients; RL builds them into reliable higher\-level strategies\.

reinforcement learning, compositional reasoning, post\-training

## 1Introduction

Does reinforcement learning \(RL\) post\-training merely reweight behaviors already latent in a base model, or can it compose primitive skills into new higher\-level strategies? Recent work has sharpened this into an active debate\. Yue et al\.\(Yueet al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib1)\)argue that RL with verifiable rewards often improves small\-kksuccess without expanding the large\-kkcapability frontier; ProRL\(Liuet al\.,[2025a](https://arxiv.org/html/2607.07646#bib.bib3)\)and Yuan et al\.\(Yuanet al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib5)\)present evidence that prolonged RL or controlled compositional tasks can uncover behaviors inaccessible to the base model under extensive sampling; and imitation\-style baselines such as rejection fine\-tuning are sometimes surprisingly competitive\(Chuet al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib4); Xionget al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib6)\)\.

A central obstacle is that the relevant mechanisms are hard to observe in pretrained language models\. When a post\-trained model exhibits a new behavior, it is usually unclear whether that behavior was absent from the base model, merely low\-probability, or already present in pretraining data\. Aggregate metrics such as pass@kkleave three questions open: what strategies are being used, whether their emergence reflects broader exploration or selective filtering, and what pretraining structure makes them reachable in the first place\.

We study these questions in a fully observable rewrite\-grammar environment\. The task abstracts a common structure in step\-by\-step reasoning: complex solutions can be built by composing local transformations into reusable procedures\. A Transformer is pretrained from scratch on primitive rewrite chains and then post\-trained on goal\-directed contraction task\. Because every generated rewrite can be audited against the grammar, we can decompose behavior into primitive rule use, valid composed strategies, and spurious invalid rewrites\. The valid composed strategies come in two forms:*sequential compositions*, which collapse ordered chains of primitive contractions, and*parallel compositions*, which combine independent primitive contractions in a single emitted step\. This turns normally opaque post\-training behavior into exactly classifiable trajectories, letting us ask whether RL reorganizes primitive competence into reusable higher\-level strategies\.

#### Contributions\.

1. 1\.A fully observable rewrite\-grammar testbed\.We introduce an environment in which primitive rules, pretraining histories, and generated rewrites are exactly inspectable, enabling a four\-way taxonomy: primitive, macro, parallel, and spurious\.
2. 2\.Phased procedural chunking\.We show that RL first strengthens primitive reductions, then discovers, reuses, and consolidates valid compositions of the primitive contractions\.
3. 3\.Finite\-budget frontier expansion\.We show that RL solves held\-out problems the pretrained model rarely solves even under much larger sampling budgets, with gains that emerge late and grow with difficulty\.
4. 4\.Selection, not exploration volume\.We show that RFT also attempts many shortcut\-like rewrites, but much of this behavior is spurious; RL concentrates exploration into valid reusable structure\. A finite\-group view of GRPO explains how same\-prompt contrast can suppress spurious passenger actions that RFT clones\.
5. 5\.Pretraining as procedural substrate\.We show that strategy emergence depends on how pretraining organizes primitive competence into reduction procedures that RL can later compress and reuse\.

## 2Related Work

#### RL beyond the base model\.

A central question in RL with verifiable rewards is whether post\-training expands a model’s effective capability frontier or mainly reweights behaviors already latent in the base policy\. Yue et al\.\(Yueet al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib1)\)argue that RLVR often improves small\-kksuccess without expanding the large\-kkfrontier, while support\-based analyses emphasize that on\-policy RL cannot amplify zero\-probability completions\(Wuet al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib13)\)\. In contrast, ProRL\(Liuet al\.,[2025a](https://arxiv.org/html/2607.07646#bib.bib3)\)argues that prolonged RL can make some problems reachable that were inaccessible under extensive base\-model sampling\. Closest to our setting, Yuan et al\.\(Yuanet al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib5)\)study RL\-induced composition in a controlled synthetic task\. Our work studies this question in a setting where the mechanism is directly observable: the pretraining distribution is generated by a known grammar, and every emitted solution step can be checked against that grammar\. We return to the comparison with prior composition experiments in Section[8](https://arxiv.org/html/2607.07646#S8)\.

#### RL versus imitation\-style post\-training\.

Rejection and supervised baselines are often strong in reasoning post\-training\. STaR bootstraps reasoning from self\-generated rationales filtered by answer correctness\(Zelikmanet al\.,[2022](https://arxiv.org/html/2607.07646#bib.bib14)\), and recent work shows that rejection\-style or minimalist supervised methods can be competitive with policy\-gradient RL in some RLVR settings\(Xionget al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib6); Chuet al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib4)\)\. We therefore treat rejection fine\-tuning as a strong on\-policy comparator rather than a weak baseline: RL and RFT are trained on the same prompts and optimized separately under the same final\-answer supervision\.

#### Process validity, exploration, and pretraining substrate\.

Outcome\-only rewards can hide invalid intermediate reasoning\(Uesatoet al\.,[2022](https://arxiv.org/html/2607.07646#bib.bib19); Lightmanet al\.,[2023](https://arxiv.org/html/2607.07646#bib.bib20); Cobbeet al\.,[2021](https://arxiv.org/html/2607.07646#bib.bib21)\)\. This is hard to measure in natural\-language tasks, where valid intermediate steps are usually not enumerable\. In our environment, process validity is mechanically checkable, letting us refine recent discussions of exploration and negative samples in RLVR\(Wanget al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib24); Tanget al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib23)\)\. We also connect to work arguing that post\-training depends on capabilities and biases shaped during pretraining\(Zhaoet al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib11); Liuet al\.,[2025b](https://arxiv.org/html/2607.07646#bib.bib25)\); here, because pretraining is controlled, we can ask how the base distribution determines which higher\-level strategies RL can later select, compress, and consolidate\.

## 3Rewrite Grammar and Primitive Actions

The grammar is defined over an alphabet𝒜\\mathcal\{A\}, where each source symbol maps to one or more globally unique multi\-character right\-hand\-side strings \(Figure[1](https://arxiv.org/html/2607.07646#S3.F1)a\)\. Global uniqueness makes primitive contraction unambiguous: any substring matching a right\-hand side maps back to exactly one source symbol\. The environment supports two inverse primitive operations:*expansion*, which replaces a symbol by one of its right\-hand sides, and*contraction*, which replaces a matching substring by its source symbol\. Each step is serialized as

lhs\_word​∣action∣​rhs\_word,\\texttt\{lhs\\\_word\}\\mid\\texttt\{action\}\\mid\\texttt\{rhs\\\_word\},where the action specifies a position and rule for expansion, or a span and rule for contraction \(Figure[1](https://arxiv.org/html/2607.07646#S3.F1)c\)\.

Because the primitive rule set is known, every generated rewrite can be audited against the grammar: it can be a primitive rule application, a valid non\-primitive shortcut, or an invalid rewrite\. This is what makes trajectory\-level strategy analysis possible\.

![Refer to caption](https://arxiv.org/html/2607.07646v1/x1.png)Figure 1:Controlled environment and training pipeline\.\(a\)Each source character maps to one or more globally unique right\-hand\-side strings\.\(b\)Pretraining data consists of multi\-step sequences in which the output of one step becomes the input to the next\.\(c\)Each training triple encodes a single primitive expansion or contraction\.\(d\)RL prompts are constructed by repeated forward expansion from a target symbol\.\(e\)Difficulty levels are defined by how many optimal contraction steps lie beyond the model’s 256\-token generation budget\.### 3\.1Pretraining on Primitive Rewrite Chains

The model is pretrained from scratch on chained rewrite trajectories\. Starting from an initial word, the data generator repeatedly samples a valid primitive expansion or contraction, appends the corresponding serialized triple, and uses the resulting word as the input to the next step\. Thus, pretraining exposes the model to local grammar\-consistent rewrite dynamics, but not to the later non\-primitive shortcuts analyzed in this paper\.

We control the pretraining distribution with a contraction weightρ\\rho, which locally upweights contraction moves relative to expansion moves whenever both are available\. Thusρ\\rhoaffects the realized contraction frequency and the amount of contraction chaining, but does not directly specify either statistic\. Unless otherwise stated, we useρ=4\\rho=4\. Section[7](https://arxiv.org/html/2607.07646#S7)later ablates this parameter to test whether properties of the pretraining distribution affect which strategies RL can unlock\. Full grammar\-generation and optimization details are given in Appendix[A](https://arxiv.org/html/2607.07646#A1)\.

### 3\.2Trace\-Based Reasoning Task

After pretraining, the model is post\-trained on a trace\-based reasoning task\. A prompt is generated by starting from a target symbolc⋆c^\{\\star\}and repeatedly applying primitive expansions to obtain a longer wordwpromptw\_\{\\mathrm\{prompt\}\}\. At post\-training time, the model sees onlywpromptw\_\{\\mathrm\{prompt\}\}and must generate a step\-by\-step contraction trace whose final emitted symbol isc⋆c^\{\\star\}\.

Difficulty is defined by the length of the optimal primitive contraction solution under the serialized action format\. Difficulty 1 problems have an optimal primitive solution that fits within the 256\-token generation budget\. Difficulty 2 problems require one additional primitive contraction step beyond the budget, and Difficulty 3 problems require two additional steps\. The RL training mixture contains 60% Difficulty 1, 20% Difficulty 2, and 20% Difficulty 3 examples\. For evaluation, we use held\-out problems spanning Difficulties 1–6, including buckets beyond the training distribution\.

This difficulty definition is important: higher difficulty does not mean the grammar is different, but that the straightforward primitive contraction trace is too long for the generation budget\. Solving harder buckets therefore requires shorter valid reasoning procedures, analogous to using simplification shortcuts rather than executing every local transformation one step at a time\.

### 3\.3RL and RFT Post\-Training

The post\-training reward is binary and outcome\-only: it is11if the trajectory consists of well\-formed action triples in the format above and the final emitted symbol equals the targetc⋆c^\{\\star\}, and0otherwise\. There is no supervision on intermediate rewrites — only the format of the output and the identity of the final symbol matter\. Any valid non\-primitive strategies that emerge must therefore arise from post\-training dynamics rather than from direct reward shaping\. This mirrors RLVR on math reasoning, where final\-answer correctness is the only training signal\(Shaoet al\.,[2024](https://arxiv.org/html/2607.07646#bib.bib7)\)\.

Our RL method is Group Relative Policy Optimization \(GRPO\)\(Shaoet al\.,[2024](https://arxiv.org/html/2607.07646#bib.bib7)\)\. As an imitation baseline, we use rejection fine\-tuning \(RFT\), which retains successful on\-policy rollouts and performs next\-token prediction on them\. RFT is therefore a strong comparator: any RL\-vs\-RFT gap cannot be attributed to data or prompt mismatch\. Full GRPO and RFT details are in Appendix[B](https://arxiv.org/html/2607.07646#A2)\.

## 4Utilisation of Composition to go Beyond the Base Model

Because the grammar is fully known, every generated rewrite in a successful trajectory can be audited by comparing its left\- and right\-hand sides\. Aprimitive contractionreplaces the right\-hand side of an original grammar rule with its source symbol; for example,dffcontracts tobwhen the grammar containsb→dffb\\rightarrow\\texttt\{dff\}\. Amacro contractionis a non\-primitive rewrite equivalent to a ‘sequential composition’ of primitive contractions, such asbae→\\rightarrowaby composingae→\\rightarrowcandbc→\\rightarrowa\. Aparallel contractionapplies a ‘parallel composition’ of primitive contractions simultaneously, such asdffae→\\rightarrowbc\. Together these two action types — macro and parallel — instantiate the procedural chunks introduced in Section 1: compressed multi\-step procedures that can stand in for chains or combinations of primitive operations\. Any non\-primitive rewrite that is neither macro nor parallel is classified asspurious\.

![Refer to caption](https://arxiv.org/html/2607.07646v1/x2.png)Figure 2:RL undergoes a delayed transition from primitive contractions to compressed valid shortcuts\. Macro contractions accelerate and overtake primitive contractions around iteration 12,500; parallel contractions emerge later\. Bottom examples show the structural analogy to algebraic simplification: primitive contractions correspond to local simplifications, macro contractions to reusable multi\-step maneuvers, and parallel contractions to independent simplifications appliexd simultaneously\.Thus, RL first strengthens primitive reduction behavior and only later shifts toward valid compositional procedures that were never present as primitive training actions\. This trace\-level phase transition explains the late gains in Figure[5](https://arxiv.org/html/2607.07646#S6.F5): on the hardest buckets, primitive paths are least compatible with the generation budget, so valid compressed rewrites make previously over\-budget solutions reachable\.

### 4\.1Dynamics of Compositional Strategy Emergence

Recent RL post\-training work reports phase\-like changes in reasoning behavior: models first improve lower\-level solution execution and later exhibit reflection, alternative approaches, or higher\-level strategic behavior\(DeepSeek\-AIet al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib34); Wanget al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib24); Chenget al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib35)\)\. In natural\-language settings, these phases are hard to audit because intermediate reasoning steps are not mechanically checkable\. Our grammar gives a trace\-level analogue: each generated rewrite can be classified against the known rule system, letting us measure which kind of procedure becomes more common during training\.

Figure[2](https://arxiv.org/html/2607.07646#S4.F2)shows a delayed transition\. Early successful trajectories are dominated by primitive contractions\. Around iteration 5,000, macro contractions begin to rise and overtake primitive contractions by roughly iteration 12,500, while parallel contractions emerge later and grow steadily\.

### 4\.2Discovery and Consolidation of Macro Rules

The previous subsection showed that macro contractions become increasingly important during RL training\. We now ask whether this increase reflects scattered one\-off shortcuts, or whether RL builds a reusable repertoire of macro rules\. We distinguish between a*macro action*, a single occurrence of a macro contraction in a trajectory, and a*macro rule*, the underlying rewrite pattern that may be used repeatedly across trajectories\. We measure*discovery*as the first appearance of a macro rule, and*consolidation*as the later reuse of previously discovered macro rules\.

![Refer to caption](https://arxiv.org/html/2607.07646v1/x3.png)Figure 3:RL discovers and consolidates reusable macro rules\.\(a\)Number of newly discovered macro rules at each checkpoint\.\(b\)Reuse count of previously discovered macro rules\.\(c\)Reuse fraction among all macro actions\. RL continues discovering new macro rules while increasingly reusing earlier ones, indicating consolidation into a stable repertoire\.Figure[3](https://arxiv.org/html/2607.07646#S4.F3)shows that RL’s macro behavior is not just an accumulation of isolated shortcuts\. RL continues discovering new macro rules throughout training, with discovery peaking around iteration 10,000\. Reuse rises in parallel: by the end of training, most macro actions emitted by the RL model are reapplications of rules observed at earlier checkpoints\. RFT also discovers some macro rules, but at a lower rate and with weaker reuse: it finds shortcuts, but does not consolidate them into an equally stable repertoire\.

This consolidation is the bridge from discovery to capability\. A macro contraction compresses a sequence of primitive contractions into a single emitted rewrite, behaving like an implicit macro\-action without any option set or high\-level controller being provided\(Suttonet al\.,[1999](https://arxiv.org/html/2607.07646#bib.bib29); Konidaris and Barto,[2009](https://arxiv.org/html/2607.07646#bib.bib30)\)\. The abstractions emerge inside the sequence model and are visible only because the trace can be audited\. Thus RL accumulates capability not by relying on a fresh lucky shortcut each time, but by stabilizing discovered shortcuts into reusable policy structure that can be deployed on later problems\.

## 5Structured Versus Unstructured Exploration

The previous section established that RL discovers and consolidates valid macro rules more effectively than RFT\. A natural alternative explanation is that RL simply explores more: perhaps it generates more non\-primitive actions in total and therefore finds more valid shortcuts by chance\. Figure[4](https://arxiv.org/html/2607.07646#S5.F4)rules out this explanation\. Panels \(a\) and \(b\) show that both methods generate valid non\-primitive behavior: RFT discovers macro contractions and parallel contractions, but RL discovers many more of both, especially later in training\. Panels \(c\) and \(d\) show the key difference\. RFT accumulates many more spurious contractions, and its spurious\-action ratio remains high throughout training\. RL instead keeps spurious contractions low and shifts an increasing fraction of its non\-primitive behavior toward valid structure\. The difference is therefore not raw non\-primitive volume, but selectivity\.

A finite\-group view of GRPO explains how this selectivity can arise\. Consider a binary trajectory featureF​\(τ\)∈\{0,1\}F\(\\tau\)\\in\\\{0,1\\\}, such as the presence of a particular macro contraction, parallel contraction, or spurious contraction\. For one prompt, GRPO samples a group ofGGcompletions\. Letnnbe the number of successful completions,k\+k^\{\+\}the number of successful completions containingFF, andk−k^\{\-\}the number of failed completions containingFF\.

With binary rewards and0<n<G0<n<G, the group mean is

The group standard deviation is

σ2\\displaystyle\\sigma^\{2\}=1G​\[n​\(1−μ\)2\+\(G−n\)​μ2\]\\displaystyle=\\frac\{1\}\{G\}\\left\[n\(1\-\\mu\)^\{2\}\+\(G\-n\)\\mu^\{2\}\\right\]=1G​\[n​\(1−nG\)2\+\(G−n\)​\(nG\)2\]\\displaystyle=\\frac\{1\}\{G\}\\left\[n\\left\(1\-\\frac\{n\}\{G\}\\right\)^\{2\}\+\(G\-n\)\\left\(\\frac\{n\}\{G\}\\right\)^\{2\}\\right\]=n​\(G−n\)G2,\\displaystyle=\\frac\{n\(G\-n\)\}\{G^\{2\}\},so

σ=n​\(G−n\)G\.\\sigma=\\frac\{\\sqrt\{n\(G\-n\)\}\}\{G\}\.Thus successful and failed completions receive normalized advantages

A\+=1−μσ=G−nn,A−=−μσ=−nG−n\.A^\{\+\}=\\frac\{1\-\\mu\}\{\\sigma\}=\\sqrt\{\\frac\{G\-n\}\{n\}\},\\qquad A^\{\-\}=\\frac\{\-\\mu\}\{\\sigma\}=\-\\sqrt\{\\frac\{n\}\{G\-n\}\}\.
Ignoring token\-level constants, clipping effects, and the KL term, the feature\-count contribution to the GRPO update is proportional to

A\+​k\+\+A−​k−\\displaystyle A^\{\+\}k^\{\+\}\+A^\{\-\}k^\{\-\}=G−nn​k\+−nG−n​k−\\displaystyle=\\sqrt\{\\frac\{G\-n\}\{n\}\}\\,k^\{\+\}\-\\sqrt\{\\frac\{n\}\{G\-n\}\}\\,k^\{\-\}=n​\(G−n\)​\(k\+n−k−G−n\)\.\\displaystyle=\\sqrt\{n\(G\-n\)\}\\left\(\\frac\{k^\{\+\}\}\{n\}\-\\frac\{k^\{\-\}\}\{G\-n\}\\right\)\.The prefactor is positive, so the sign is determined by the same\-prompt success–failure contrast

ΔF=k\+n−k−G−n\.\\Delta\_\{F\}=\\frac\{k^\{\+\}\}\{n\}\-\\frac\{k^\{\-\}\}\{G\-n\}\.Herek\+/nk^\{\+\}/nis the feature frequency among successful completions, whilek−/\(G−n\)k^\{\-\}/\(G\-n\)is its frequency among failed completions\. GRPO therefore increases features that are more common in successful completions than failed completions from the same prompt, and suppresses features enriched in failures\. This is a feature\-level approximation rather than a full model of Transformer optimization, but it isolates the finite\-sample contrast that distinguishes GRPO from imitation on accepted rollouts\.

RFT uses the same sampled rollouts differently\. It discards failed completions, retains only successful trajectories, and performs next\-token prediction on the full accepted sequence\. For the same prompt group, the only feature frequency available to RFT is

f^\+=k\+n,\\hat\{f\}^\{\+\}=\\frac\{k^\{\+\}\}\{n\},so the failure\-side termk−/\(G−n\)k^\{\-\}/\(G\-n\)does not appear in the supervised targets\. As a result, if a successful trajectory contains a spurious rewrite alongside useful steps, that rewrite is cloned along with the useful ones\. GRPO does not identify which individual action caused success, but its within\-prompt contrast can give downward pressure to action patterns that appear frequently in failed rollouts, even if they also occur inside some successful ones\.

This does not mean that RFT is a weak or misaligned baseline\. In the idealized infinite\-sample, infinitesimal\-update limit, on\-policy RFT with binary rewards points in the same first\-order direction as the policy gradient\. Let

J​\(θ\)=𝔼τ∼πθ​\[R​\(τ\)\]\.J\(\\theta\)=\\mathbb\{E\}\_\{\\tau\\sim\\pi\_\{\\theta\}\}\[R\(\\tau\)\]\.Using the score\-function identity,

∇θJ​\(θ\)=𝔼τ∼πθ​\[R​\(τ\)​∇θlog⁡πθ​\(τ\)\]\.\\nabla\_\{\\theta\}J\(\\theta\)=\\mathbb\{E\}\_\{\\tau\\sim\\pi\_\{\\theta\}\}\\left\[R\(\\tau\)\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}\(\\tau\)\\right\]\.For binary rewards,

∇θJ​\(θ\)=Pθ​\(R=1\)​𝔼τ∼πθ​\(τ∣R=1\)​\[∇θlog⁡πθ​\(τ\)\]\.\\nabla\_\{\\theta\}J\(\\theta\)=P\_\{\\theta\}\(R=1\)\\,\\mathbb\{E\}\_\{\\tau\\sim\\pi\_\{\\theta\}\(\\tau\\mid R=1\)\}\\left\[\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}\(\\tau\)\\right\]\.On\-policy RFT samples fromπθold\\pi\_\{\\theta\_\{\\mathrm\{old\}\}\}, keeps successful trajectories, and minimizes

ℒRFT​\(θ\)=−𝔼τ∼πθold​\(τ∣R=1\)​\[log⁡πθ​\(τ\)\]\.\\mathcal\{L\}\_\{\\mathrm\{RFT\}\}\(\\theta\)=\-\\mathbb\{E\}\_\{\\tau\\sim\\pi\_\{\\theta\_\{\\mathrm\{old\}\}\}\(\\tau\\mid R=1\)\}\[\\log\\pi\_\{\\theta\}\(\\tau\)\]\.Evaluated atθ=θold\\theta=\\theta\_\{\\mathrm\{old\}\},

−∇θℒRFT​\(θold\)=1P​\(R=1\)​∇θJ​\(θold\)\.\-\\nabla\_\{\\theta\}\\mathcal\{L\}\_\{\\mathrm\{RFT\}\}\(\\theta\_\{\\mathrm\{old\}\}\)=\\frac\{1\}\{P\(R=1\)\}\\nabla\_\{\\theta\}J\(\\theta\_\{\\mathrm\{old\}\}\)\.Thus ideal on\-policy RFT is first\-order aligned with binary\-reward policy gradient, up to a positive scalar\. This explains why RFT is a strong early baseline\. The later divergence arises in the finite iterative setting: RFT repeatedly clones finite accepted trajectories, while GRPO uses negative advantages from below\-average completions in the same prompt group\.

The same finite\-sample view also sharpens recent accounts of negative samples in RLVR\. Prior work has argued that negative samples can help maintain exploration, preserve diversity, or prevent premature collapse\(Wanget al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib24); Tanget al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib23)\)\. Our setting refines this framing by making the explored behaviors directly classifiable\. Because every generated rewrite can be classified, we can see that RFT already produces abundant non\-primitive behavior; the bottleneck is not exploration volume\. The key difference is that RL filters this explored space: it amplifies non\-primitive rewrites that are valid and reward\-aligned, while suppressing spurious departures from the grammar\. Thus the role of negative samples is not merely to keep the policy diverse, but to make exploration structurally selective\.

![Refer to caption](https://arxiv.org/html/2607.07646v1/x4.png)Figure 4:RL discovers valid non\-primitive strategies while suppressing spurious shortcuts\.\(a,b\)Counts of valid macro and parallel contractions\.\(c\)Count of spurious contractions\.\(d\)Fraction of non\-primitive contractions that are spurious\. RFT generates many non\-primitive actions, but they are mostly invalid; RL produces fewer spurious rewrites and increasingly concentrates behavior into valid macro and parallel contractions\.
## 6RL Expands the Held\-Out Capability Frontier

We first ask whether RL expands what the model can solve relative to the pretrained base policy, or merely reweights solutions already accessible under it\. Our setting lets us answer this in a finite\-budget, fully observable form: we can measure base\-model reach under larger sampling budgets and inspect the structure of the resulting trajectories\. We evaluate on the held\-out difficulty buckets defined above, where higher difficulty corresponds to ordinary grammar\-rule solutions becoming increasingly incompatible with the 256\-token generation budget\.

![Refer to caption](https://arxiv.org/html/2607.07646v1/x5.png)Figure 5:RL exhibits a delayed crossover over RFT, with the largest advantage on harder held\-out problems\. Pass@16 on contraction problems across five difficulty levels and overall\. Mean over three seeds\. RFT improves rapidly early in training but plateaus, while RL improves more gradually and continues climbing through the end of training\.Figure[5](https://arxiv.org/html/2607.07646#S6.F5)shows pass@16 during post\-training\. RFT improves faster at the beginning of training, especially on easier buckets, indicating that on\-policy imitation can amplify solutions the pretrained model already sometimes produces\(Xionget al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib6)\)\. RFT then plateaus, while RL improves more slowly at first but continues climbing after RFT saturates, with the largest gap appearing on the hardest buckets, where primitive contraction paths are least compatible with the generation budget\.

To check whether the harder buckets are merely under\-sampled by the base model, we evaluate the pretrained policy at much larger sampling budgets \(Table[1](https://arxiv.org/html/2607.07646#S6.T1)\)\. Even at pass@1024, base\-model success remains sparse and concentrated in the easiest over\-budget buckets, with Buckets 4–5 remaining at zero\. Thus, under the tested finite budgets, complete hard\-bucket solutions are not practically available from the pretrained model, whereas RL makes them reliably accessible at pass@16\.

This leaves the central mechanistic question: how does RL cross this finite frontier? On the harder buckets, primitive\-only contraction paths exceed the generation budget, so solving them requires some form of shortcut\. Such shortcuts could be invalid rewrites that exploit the outcome\-only final\-symbol reward, or valid compressed procedures assembled from lower\-level reduction behavior\. The next section distinguishes these possibilities by auditing the generated rewrite trajectories\.

Table 1:Base\-model pass@kkon held\-out over\-budget problems\. Overall is over 80 problems; each bucket contains 16 problems\.
## 7Pretraining as the Substrate for Strategy Emergence

The previous sections show that RL eventually discovers and consolidates valid non\-primitive strategies\. We now ask what the base model must already provide — not whether pretraining contains macro or parallel strategies, but whether it organizes primitive competence into reduction procedures that RL can later compress\.

We vary how strongly contractions are locally upweighted during pretraining via a parameterρ\\rho\(Appendix[C](https://arxiv.org/html/2607.07646#A3)\)\. Increasingρ\\rhohas two coupled effects: contractions occur more often overall, and once a reducible state is reached, the next step is more likely to also be a contraction — producing chained primitive reductions rather than isolated contraction events\. To separate these effects, we include a matched\-fraction control: a low\-ρ\\rhorun with marginal contraction rate adjusted to matchρ=2\\rho=2but without the local upweighting that produces chaining\. Figure[6](https://arxiv.org/html/2607.07646#S7.F6)a confirms the design: the control matchesρ=2\\rho=2on overall contraction rate \(solid bars\) but has less chaining \(hatched bars,P​\(Ct=1∣Ct−1=1\)P\(C\_\{t\}=1\\mid C\_\{t\-1\}=1\)\)\.

Figures[6](https://arxiv.org/html/2607.07646#S7.F6)b,c show that this distinction matters\. Low\-ρ\\rhopretraining never reliably enters the macro or parallel regime; higherρ\\rhoproduces earlier and stronger valid non\-primitive strategies; the matched\-fraction control fails to recover theρ=2\\rho=2dynamics despite comparable marginal contraction exposure, behaving similarly toρ=1\\rho=1\. What matters is not how often the model sees contractions, but whether they appear as sustained reduction procedures\.

RL does not upweight a fully\-formed latent strategy already present in the base model\. Pretraining supplies weak procedural ingredients — primitive contractions, reduction states, and short contraction chains — that RL later selects, compresses, and consolidates into reusable higher\-level strategies\.

![Refer to caption](https://arxiv.org/html/2607.07646v1/x6.png)Figure 6:Strategy emergence depends on local contraction structure, not overall contraction frequency\.\(a\)Solid bars \(left axis\): overall contraction rate\. Hatched bars \(right axis\): contraction\-after\-contraction probabilityP​\(Ct=1∣Ct−1=1\)P\(C\_\{t\}=1\\mid C\_\{t\-1\}=1\)\. The matched\-fraction control reaches a comparable overall rate toρ=2\\rho=2but has substantially less chaining\.\(b,c\)Macro and parallel contraction counts during RL post\-training\. Higherρ\\rhoproduces earlier and stronger non\-primitive strategy emergence; the matched\-fraction control fails despite comparable marginal exposure\.
## 8Discussion

The controlled grammar turns the “beyond the base model” question into an inspectable one\. Higher pass@kkin natural\-language post\-training can reflect better sampling of old behaviors, discovery of new procedures, or reward exploitation through invalid traces; here, every generated rewrite can be audited against the known grammar\. This exposes a concrete mechanism: RL strengthens primitive reductions, forms valid compositional procedures, and consolidates them into a reusable repertoire\.

The results point to a form of procedural chunking, or ‘composition’\. Chunking has long been studied in skill acquisition, for example in chess expertise\(Chase and Simon,[1973](https://arxiv.org/html/2607.07646#bib.bib36)\)\. Mathematical practice has a similar flavor: multi\-step derivations become reusable lemmas or standard maneuvers\. Our grammar makes this process directly measurable: macro and parallel contractions are chunks that compress sequential or independent primitive reductions\.

Our results challenge the view that RL merely reweights complete reasoning paths already present in the base distribution\(Yueet al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib1)\)\. In this environment, the complete hard\-bucket solution is not practically present in the base model: even at pass@1024, the pretrained policy gets0%0\\%on Buckets 4–5, while RL later solves them at pass@16\. What is present are ingredients—primitive contractions and weakly supported local reduction chains\. RL turns these ingredients into complete procedures: it first enters a primitive phase, strengthening local contractions and chaining them into longer reductions; only later does it enter a chunking phase, where macro and parallel contractions become reliable\. Thus RL goes beyond the base model not by inventing from nothing\(Wuet al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib13)\), but by constructing usable strategies from weakly supported components\. The base model provides the ingredients; RL builds the procedures\.

This clarifies the comparison to Yuan et al\.\(Yuanet al\.,[2025](https://arxiv.org/html/2607.07646#bib.bib5)\)\. Their setting starts from a large pretrained model, so RL\-induced composition is hard to separate from amplification of compositional patterns already supported by pretraining\. It also leaves open which pretraining structures make composition reachable\. Their task evaluates direct input\-output transformations, whereas reasoning models often rely on extended traces where the procedure itself matters\. Our setting addresses these confounds: pretraining is controlled and ablated, the primitive rule set is known, and the model emits the full rewrite trajectory\. This lets us inspect which strategies make beyond\-base performance possible\.

The pretraining ablation shows that the relevant substrate is not merely exposure to the right primitive facts\. Matching the marginal number of contraction examples does not recover the same downstream behavior\. What matters is whether pretraining organizes primitive competence into reduction procedures that RL can later compress and consolidate\. In this sense, pretraining supplies the procedural ingredients, while RL performs the selection and chunking that turn them into stable strategies\.

The scope is controlled rather than universal: we do not claim that large language models must exhibit the same phases or taxonomy\. But the grammar exposes quantities normally hidden in LLM post\-training, and these results suggest that RL post\-training is not only reward\-driven reweighting; it can also organize weak procedural ingredients into reusable reasoning structure\.

## References

- W\. G\. Chase and H\. A\. Simon \(1973\)Perception in chess\.Cognitive Psychology4\(1\),pp\. 55–81\.Cited by:[§8](https://arxiv.org/html/2607.07646#S8.p2.1)\.
- D\. Cheng, S\. Huang, X\. Zhu, B\. Dai, W\. X\. Zhao, Z\. Zhang, and F\. Wei \(2025\)Reasoning with exploration: an entropy perspective\.arXiv preprint arXiv:2506\.14758\.Cited by:[§4\.1](https://arxiv.org/html/2607.07646#S4.SS1.p1.1)\.
- T\. Chu, Y\. Zhai, J\. Yang, S\. Tong, S\. Xie, D\. Schuurmans, Q\. V\. Le, S\. Levine, and Y\. Ma \(2025\)SFT memorizes, rl generalizes: a comparative study of foundation model post\-training\.arXiv preprint arXiv:2501\.17161\.Cited by:[§1](https://arxiv.org/html/2607.07646#S1.p1.2),[§2](https://arxiv.org/html/2607.07646#S2.SS0.SSS0.Px2.p1.1)\.
- K\. Cobbe, V\. Kosaraju, M\. Bavarian, M\. Chen, H\. Jun, L\. Kaiser, M\. Plappert, J\. Tworek, J\. Hilton, R\. Nakano, C\. Hesse, and J\. Schulman \(2021\)Training verifiers to solve math word problems\.arXiv preprint arXiv:2110\.14168\.Cited by:[§2](https://arxiv.org/html/2607.07646#S2.SS0.SSS0.Px3.p1.1)\.
- DeepSeek\-AI, D\. Guo, D\. Yang, H\. Zhang, J\. Song, R\. Zhang, R\. Xu, Q\. Zhu, S\. Ma, P\. Wang, X\. Bi,et al\.\(2025\)DeepSeek\-r1: incentivizing reasoning capability in llms via reinforcement learning\.arXiv preprint arXiv:2501\.12948\.Cited by:[§4\.1](https://arxiv.org/html/2607.07646#S4.SS1.p1.1)\.
- G\. Konidaris and A\. Barto \(2009\)Skill discovery in continuous reinforcement learning domains using skill chaining\.InAdvances in Neural Information Processing Systems,Vol\.22\.Cited by:[§4\.2](https://arxiv.org/html/2607.07646#S4.SS2.p3.1)\.
- H\. Lightman, V\. Kosaraju, Y\. Burda, H\. Edwards, B\. Baker, T\. Lee, J\. Leike, J\. Schulman, I\. Sutskever, and K\. Cobbe \(2023\)Let’s verify step by step\.arXiv preprint arXiv:2305\.20050\.Cited by:[§2](https://arxiv.org/html/2607.07646#S2.SS0.SSS0.Px3.p1.1)\.
- M\. Liu, S\. Diao, X\. Lu, J\. Hu, X\. Dong, Y\. Choi, J\. Kautz, and Y\. Dong \(2025a\)ProRL: prolonged reinforcement learning expands reasoning boundaries in large language models\.arXiv preprint arXiv:2505\.24864\.Cited by:[§1](https://arxiv.org/html/2607.07646#S1.p1.2),[§2](https://arxiv.org/html/2607.07646#S2.SS0.SSS0.Px1.p1.2)\.
- Z\. Liu, C\. Chen, W\. Li, P\. Qi, T\. Pang, C\. Du, W\. S\. Lee, and M\. Lin \(2025b\)Understanding r1\-zero\-like training: a critical perspective\.arXiv preprint arXiv:2503\.20783\.Cited by:[§2](https://arxiv.org/html/2607.07646#S2.SS0.SSS0.Px3.p1.1)\.
- Z\. Shao, P\. Wang, Q\. Zhu, R\. Xu, J\. Song, M\. Zhang, X\. Bi, H\. Zhang, Y\. K\. Li, Y\. Wu, and D\. Guo \(2024\)DeepSeekMath: pushing the limits of mathematical reasoning in open language models\.arXiv preprint arXiv:2402\.03300\.Cited by:[§3\.3](https://arxiv.org/html/2607.07646#S3.SS3.p1.3),[§3\.3](https://arxiv.org/html/2607.07646#S3.SS3.p2.1)\.
- R\. S\. Sutton, D\. Precup, and S\. Singh \(1999\)Between mdps and semi\-mdps: a framework for temporal abstraction in reinforcement learning\.Artificial Intelligence112\(1–2\),pp\. 181–211\.Cited by:[§4\.2](https://arxiv.org/html/2607.07646#S4.SS2.p3.1)\.
- X\. Tang, Y\. Zhan, Z\. Li, W\. X\. Zhao, Z\. Zhang, Z\. Wen, Z\. Zhang, and J\. Zhou \(2025\)Rethinking sample polarity in reinforcement learning with verifiable rewards\.arXiv preprint arXiv:2512\.21625\.Cited by:[§2](https://arxiv.org/html/2607.07646#S2.SS0.SSS0.Px3.p1.1),[§5](https://arxiv.org/html/2607.07646#S5.p7.1)\.
- J\. Uesato, N\. Kushman, R\. Kumar, F\. Song, N\. Siegel, L\. Wang, A\. Creswell, G\. Irving, and I\. Higgins \(2022\)Solving math word problems with process\- and outcome\-based feedback\.arXiv preprint arXiv:2211\.14275\.Cited by:[§2](https://arxiv.org/html/2607.07646#S2.SS0.SSS0.Px3.p1.1)\.
- H\. Wang, Q\. Xu, C\. Liu, J\. Wu, F\. Lin, and W\. Chen \(2025\)Emergent hierarchical reasoning in llms through reinforcement learning\.arXiv preprint arXiv:2509\.03646\.Cited by:[§2](https://arxiv.org/html/2607.07646#S2.SS0.SSS0.Px3.p1.1),[§4\.1](https://arxiv.org/html/2607.07646#S4.SS1.p1.1),[§5](https://arxiv.org/html/2607.07646#S5.p7.1)\.
- F\. Wu, W\. Xuan, X\. Lu, M\. Liu, Y\. Dong, Z\. Harchaoui, and Y\. Choi \(2025\)The invisible leash: why rlvr may or may not escape its origin\.arXiv preprint arXiv:2507\.14843\.Cited by:[§2](https://arxiv.org/html/2607.07646#S2.SS0.SSS0.Px1.p1.2),[§8](https://arxiv.org/html/2607.07646#S8.p3.1)\.
- W\. Xiong, J\. Yao, Y\. Xu, B\. Pang, L\. Wang, D\. Sahoo, J\. Li, N\. Jiang, T\. Zhang, C\. Xiong, and H\. Dong \(2025\)A minimalist approach to llm reasoning: from rejection sampling to reinforce\.arXiv preprint arXiv:2504\.11343\.Cited by:[§1](https://arxiv.org/html/2607.07646#S1.p1.2),[§2](https://arxiv.org/html/2607.07646#S2.SS0.SSS0.Px2.p1.1),[§6](https://arxiv.org/html/2607.07646#S6.p2.1)\.
- L\. Yuan, W\. Chen, Y\. Zhang, G\. Cui, H\. Wang, Z\. You, N\. Ding, Z\. Liu, M\. Sun, and H\. Peng \(2025\)From f\(x\) and g\(x\) to f\(g\(x\)\): llms learn new skills in rl by composing old ones\.arXiv preprint arXiv:2509\.25123\.Cited by:[§1](https://arxiv.org/html/2607.07646#S1.p1.2),[§2](https://arxiv.org/html/2607.07646#S2.SS0.SSS0.Px1.p1.2),[§8](https://arxiv.org/html/2607.07646#S8.p4.1)\.
- Y\. Yue, Z\. Chen, R\. Lu, A\. Zhao, Z\. Wang, S\. Song, and G\. Huang \(2025\)Does reinforcement learning really incentivize reasoning capacity in llms beyond the base model?\.arXiv preprint arXiv:2504\.13837\.Cited by:[§1](https://arxiv.org/html/2607.07646#S1.p1.2),[§2](https://arxiv.org/html/2607.07646#S2.SS0.SSS0.Px1.p1.2),[§8](https://arxiv.org/html/2607.07646#S8.p3.1)\.
- E\. Zelikman, Y\. Wu, J\. Mu, and N\. D\. Goodman \(2022\)STaR: bootstrapping reasoning with reasoning\.arXiv preprint arXiv:2203\.14465\.Cited by:[§2](https://arxiv.org/html/2607.07646#S2.SS0.SSS0.Px2.p1.1)\.
- R\. Zhao, A\. Meterez, S\. Kakade, C\. Pehlevan, S\. Jelassi, and E\. Malach \(2025\)Echo chamber: rl post\-training amplifies behaviors learned in pretraining\.arXiv preprint arXiv:2504\.07912\.Cited by:[§2](https://arxiv.org/html/2607.07646#S2.SS0.SSS0.Px3.p1.1)\.

## Appendix AAdditional Training and Data Generation Details

#### Grammar generation\.

Alphabet size isN=20N=20\. Each character has between 1 and 3 right\-hand sides drawn uniformly\. Right\-hand\-side lengths follow a truncated Zipfian distribution over\[2,6\]\[2,6\]\. All right\-hand sides are globally unique\.

#### Chain generation\.

Starting\-word lengths are sampled uniformly from\[2,12\]\[2,12\]and chain lengths from\[5,50\]\[5,50\]\. For the default setup, the contraction weight isρ=4\\rho=4\.

#### Model and optimization\.

The pretrained model uses 12 layers, hidden dimension 512, 8 attention heads, an MLP expansion ratio of 4, RoPE positional encoding, QK normalization, and atanh\\tanhsoft\-cap on logits\. Optimization uses AdamW with a warm/flat/cool schedule, peak learning rate8×10−48\\times 10^\{\-4\}, sequence length 512, bfloat16 training, and gradient clipping at norm 1\.0\.

#### Pretraining data generation\.

For each pretraining chain, we first sample a starting word length and a chain length from the configured distributions\. Starting from a random word over the alphabet, the generator repeatedly enumerates all currently valid primitive moves: expansions at characters whose source symbol appears in the grammar, and contractions at substrings matching a right\-hand side\. One move is sampled from the configured rule weights, applied to the current word, and serialized as

lhs\_word \| action \| rhs\_word\.\\texttt\{lhs\\\_word \| action \| rhs\\\_word\}\.The resultingrhs\_wordbecomes the nextlhs\_word\. Thus pretraining chains are stochastic local rewrite trajectories, not solution\-directed demonstrations\. The generator records the start\-word distribution, chain\-length distribution, rule\-weight distribution, contraction weight, and matched\-fraction setting used for each dataset\.

#### Post\-training prompt generation\.

For RL/RFT post\-training, prompts are generated by sampling a target symbolc⋆c^\{\\star\}and applying forward expansions to obtain a prompt wordwpromptw\_\{\\mathrm\{prompt\}\}\. The model sees onlywpromptw\_\{\\mathrm\{prompt\}\}and the target; the expansion path used to construct the prompt is not provided\. Prompts are filtered by the primitive contraction budget: Difficulty 1 fits within the generation budget, while higher difficulties require additional primitive contraction steps beyond the budget\. The same prompt distribution is used for GRPO and RFT; the methods differ only in how sampled completions are used for optimization\.

Unless otherwise stated, learning curves are averaged over three training seeds

#### Compute\.

All experiments were run on a node with4×4\\timesNVIDIA H100 GPUs\.

## Appendix BGRPO and RFT Details

#### Reward\.

The reward is

r=\{1if the trajectory is well\-formed and ends with​c⋆,0otherwise\.r=\\begin\{cases\}1&\\text\{if the trajectory is well\-formed and ends with \}c^\{\\star\},\\\\ 0&\\text\{otherwise\.\}\\end\{cases\}A trajectory is*well\-formed*if it is parseable as a sequence oflhs\_word \| action \| rhs\_wordtriples and each triple’srhs\_wordmatches the next triple’slhs\_word\. This check is syntactic and does not require each intermediate rewrite to be grammar\-valid\.

#### GRPO\.

For each promptxix\_\{i\}, GRPO samplesGGcompletions\{yi,g\}g=1G\\\{y\_\{i,g\}\\\}\_\{g=1\}^\{G\}and assigns each a scalar rewardri,gr\_\{i,g\}\. Advantages are normalized within each prompt group:

Ai,g=ri,g−μiσi\+δ,μi=1G​∑g=1Gri,g,A\_\{i,g\}=\\frac\{r\_\{i,g\}\-\\mu\_\{i\}\}\{\\sigma\_\{i\}\+\\delta\},\\qquad\\mu\_\{i\}=\\frac\{1\}\{G\}\\sum\_\{g=1\}^\{G\}r\_\{i,g\},σi=1G​∑g=1G\(ri,g−μi\)2\.\\sigma\_\{i\}=\\sqrt\{\\frac\{1\}\{G\}\\sum\_\{g=1\}^\{G\}\(r\_\{i,g\}\-\\mu\_\{i\}\)^\{2\}\}\.Let

ρi,g,t​\(θ\)=πθ​\(yi,g,t∣xi,yi,g,<t\)πold​\(yi,g,t∣xi,yi,g,<t\)\.\\rho\_\{i,g,t\}\(\\theta\)=\\frac\{\\pi\_\{\\theta\}\(y\_\{i,g,t\}\\mid x\_\{i\},y\_\{i,g,<t\}\)\}\{\\pi\_\{\\mathrm\{old\}\}\(y\_\{i,g,t\}\\mid x\_\{i\},y\_\{i,g,<t\}\)\}\.The clipped policy\-gradient term is

ℓi,g,tclip​\(θ\)=min⁡\(ρi,g,t​Ai,g,clip⁡\(ρi,g,t,1−ϵ,1\+ϵ\)​Ai,g\)\.\\ell\_\{i,g,t\}^\{\\mathrm\{clip\}\}\(\\theta\)=\\min\\\!\\left\(\\rho\_\{i,g,t\}A\_\{i,g\},\\operatorname\{clip\}\(\\rho\_\{i,g,t\},1\-\\epsilon,1\+\\epsilon\)A\_\{i,g\}\\right\)\.The training loss is

ℒ​\(θ\)=−1∑i,g,tmi,g,t​∑i,g,tmi,g,t​\[ℓi,g,tclip​\(θ\)−β​κi,g,t​\(θ\)\],\\mathcal\{L\}\(\\theta\)=\-\\frac\{1\}\{\\sum\_\{i,g,t\}m\_\{i,g,t\}\}\\sum\_\{i,g,t\}m\_\{i,g,t\}\\left\[\\ell\_\{i,g,t\}^\{\\mathrm\{clip\}\}\(\\theta\)\-\\beta\\kappa\_\{i,g,t\}\(\\theta\)\\right\],wheremi,g,tm\_\{i,g,t\}masks prompt and post\-stop tokens andκi,g,t\\kappa\_\{i,g,t\}is a reverse\-KL penalty to the frozen pretrained reference policy\. In our experiments,G=4G=4,ϵ=0\.2\\epsilon=0\.2,β=10−3\\beta=10^\{\-3\}, temperature is0\.80\.8, top\-kkis55, and the maximum generation length is256256tokens\.

#### RFT\.

RFT uses the same prompt distribution, group sizeG=4G=4, batch size, optimizer, and KL anchor as GRPO\. For each prompt, it samplesGGcompletions, retains those withr=1r=1, and performs next\-token prediction on the accepted rollouts using the same loss maskingmi,g,tm\_\{i,g,t\}\. RFT differs from GRPO only in \(i\) it discards rather than down\-weights failed rollouts, and \(ii\) its update is supervised rather than policy\-gradient\.

## Appendix CPretraining Contraction Weighting

The contraction weightρ\\rhois a local weight multiplier, not a direct contraction\-frequency parameter\. At each pretraining step, the generator enumerates the valid primitive expansion movesE​\(w\)E\(w\)and primitive contraction movesC​\(w\)C\(w\)from the current wordww\. Expansion moves keep their base weights, while contraction moves are multiplied byρ\\rhobefore sampling the next rewrite\.

For example, suppose the current word admits four valid primitive moves: three expansions and one contraction, all with unit base weight\. Withρ=1\\rho=1, all four moves have equal weight, so the contraction probability is

Withρ=4\\rho=4, the three expansions still have weight11each, but the contraction has weight44, so the contraction probability becomes

Thus increasingρ\\rhomakes contractions more likely locally whenever contractions are available\. It does not directly impose a fixed global contraction rate\.

More generally, if each moveaahas base rule weightq​\(a\)q\(a\), then the probability that the next move is a contraction is

Pρ​\(C∣w\)=ρ​∑a∈C​\(w\)q​\(a\)∑a∈E​\(w\)q​\(a\)\+ρ​∑a∈C​\(w\)q​\(a\)\.P\_\{\\rho\}\(C\\mid w\)=\\frac\{\\rho\\sum\_\{a\\in C\(w\)\}q\(a\)\}\{\\sum\_\{a\\in E\(w\)\}q\(a\)\+\\rho\\sum\_\{a\\in C\(w\)\}q\(a\)\}\.The realized fraction of contractions over the full pretraining corpus depends on the grammar, the current word distribution, which moves are available, and the trajectory dynamics\. This is whyρ\\rhoshould be interpreted as a local contraction weight rather than as the realized contraction rate\.

Highρ\\rhoalso changes how contractions are arranged\. Since contraction moves are locally upweighted whenever a reducible state is reached, the generator is more likely to remain in a reduction mode and produce consecutive contraction steps\. Thus highρ\\rhoexposes the model not only to more contractions in aggregate, but also to more chained primitive reductions\.

#### Matched\-fraction control\.

The matched\-fraction control separates aggregate contraction exposure from this local weighting mechanism\. We choose a low\-ρ\\rhogenerator and adjust its direction\-sampling probability so that its realized marginal contraction rate is comparable to theρ=2\\rho=2pretraining run\. After choosing whether the next move is an expansion or contraction, a valid move within that direction is sampled\.

The control is therefore not an unbiasedρ=1\\rho=1generator\. It is intentionally biased to match the marginal number of contraction examples in an intermediate contraction\-weight setting\. What it removes is the local reweighting of every available contraction move by a largerρ\\rho\. Consequently, contractions occur at a comparable overall rate, but they are less likely to appear as sustained contraction chains\.

This distinction is what Figure[6](https://arxiv.org/html/2607.07646#S7.F6)tests\. If strategy emergence were explained only by the marginal number of contraction examples, the matched control should behave like theρ=2\\rho=2model\. Instead, it behaves much closer to the low\-ρ\\rhomodel, suggesting that the organization of contractions across trajectories—especially exposure to reduction\-mode behavior and chained primitive contractions—matters for later strategy emergence under RL\.

## Appendix DExample Grammar and Pretraining Chains

a→\{qs\}b→\{ic,fe,sqjg\}c→\{jaocn\}d→\{ba,nklt,si\}e→\{mj\}f→\{hl,mq\}g→\{hheoj,jd,mi\}h→\{aps,gna\}i→\{paolh\}j→\{qsn,cnr,gd\}k→\{csj\}l→\{dff\}m→\{fc,pt\}n→\{dl,hfd,nq\}o→\{cj,hq\}p→\{fk\}q→\{imr,nd\}r→\{gn\}s→\{iq,bb,fflgj\}t→\{ld,ka\}\.\\begin\{array\}\[\]\{ll\}a\\\!\\to\\\!\\\{\\texttt\{qs\}\\\}&b\\\!\\to\\\!\\\{\\texttt\{ic\},\\texttt\{fe\},\\texttt\{sqjg\}\\\}\\\\ c\\\!\\to\\\!\\\{\\texttt\{jaocn\}\\\}&d\\\!\\to\\\!\\\{\\texttt\{ba\},\\texttt\{nklt\},\\texttt\{si\}\\\}\\\\ e\\\!\\to\\\!\\\{\\texttt\{mj\}\\\}&f\\\!\\to\\\!\\\{\\texttt\{hl\},\\texttt\{mq\}\\\}\\\\ g\\\!\\to\\\!\\\{\\texttt\{hheoj\},\\texttt\{jd\},\\texttt\{mi\}\\\}&h\\\!\\to\\\!\\\{\\texttt\{aps\},\\texttt\{gna\}\\\}\\\\ i\\\!\\to\\\!\\\{\\texttt\{paolh\}\\\}&j\\\!\\to\\\!\\\{\\texttt\{qsn\},\\texttt\{cnr\},\\texttt\{gd\}\\\}\\\\ k\\\!\\to\\\!\\\{\\texttt\{csj\}\\\}&l\\\!\\to\\\!\\\{\\texttt\{dff\}\\\}\\\\ m\\\!\\to\\\!\\\{\\texttt\{fc\},\\texttt\{pt\}\\\}&n\\\!\\to\\\!\\\{\\texttt\{dl\},\\texttt\{hfd\},\\texttt\{nq\}\\\}\\\\ o\\\!\\to\\\!\\\{\\texttt\{cj\},\\texttt\{hq\}\\\}&p\\\!\\to\\\!\\\{\\texttt\{fk\}\\\}\\\\ q\\\!\\to\\\!\\\{\\texttt\{imr\},\\texttt\{nd\}\\\}&r\\\!\\to\\\!\\\{\\texttt\{gn\}\\\}\\\\ s\\\!\\to\\\!\\\{\\texttt\{iq\},\\texttt\{bb\},\\texttt\{fflgj\}\\\}&t\\\!\\to\\\!\\\{\\texttt\{ld\},\\texttt\{ka\}\\\}\.\\end\{array\}A pretraining example is a stochastic chain of local primitive rewrites\. Each line applies one valid expansion or contraction, and the output word becomes the input to the next line\. For example:

```
bqt | 0 E b>fe | feqt
feqt | 2 E q>nd | fendt
fendt | 4 E t>ka | fendka
fendka | 0 1 C b>fe | bndka
bndka | 0 E b>sqjg | sqjgndka
sqjgndka | 6 E k>csj | sqjgndcsja
```

Another sampled snippet is:

```
ltm | 0 E l>dff | dfftm
dfftm | 3 E t>ld | dffldm
dffldm | 5 E m>pt | dffldpt
dffldpt | 3 4 C t>ld | dfftpt
dfftpt | 3 E t>ka | dffkapt
dffkapt | 5 E p>fk | dffkafkt
```

These snippets illustrate the local nature of pretraining: the model sees grammar\-consistent primitive rewrites, not the macro or parallel contractions analyzed in the main text\.

### D\.1Example RL/RFT Post\-Training Prompts

The same prompt distribution is used for RL and RFT post\-training\. For RL, the model samples completions for each prompt and receives a binary reward\. For RFT, successful on\-policy completions from the same prompts are retained as next\-token prediction targets\. The model sees only the final expanded prompt word and the target symbol; the expansion chains below are shown only for exposition\.

For readability, the examples below use an illustrative primitive\-step budgetB=3B=3rather than the 256\-token serialized budget used in the experiments\. Thus Difficulty 1 fits within the budget, Difficulty 2 requires one additional primitive contraction step, and Difficulty 3 requires two additional primitive contraction steps\.

#### Difficulty 1: primitive solution fits within budget\.

Starting from target symbola, one possible prompt construction is:

```
a | 0 E a>qs | qs
qs | 0 E q>nd | nds
nds | 2 E s>iq | ndiq
```

The post\-training prompt is thereforendiq, with targeta\. A primitive contraction solution is:

```
ndiq | 0 1 C q>nd | qiq
qiq | 1 2 C s>iq | qs
qs | 0 1 C a>qs | a
```

This solution uses three primitive contractions, so it fits within the illustrative budgetB=3B=3\.

#### Difficulty 2: one primitive step beyond budget\.

Starting from target symbolb, one possible prompt construction is:

```
b | 0 E b>sqjg | sqjg
sqjg | 0 E s>bb | bbqjg
bbqjg | 2 E q>imr | bbimrjg
bbimrjg | 5 E j>gd | bbimrgdg
```

The post\-training prompt isbbimrgdg, with targetb\. A primitive contraction solution is:

```
bbimrgdg | 2 4 C q>imr | bbqgdg
bbqgdg | 3 4 C j>gd | bbqjg
bbqjg | 0 1 C s>bb | sqjg
sqjg | 0 3 C b>sqjg | b
```

This requires four primitive contractions, one step beyond the illustrative budget\.

#### Difficulty 3: two primitive steps beyond budget\.

Starting from target symbolt, one possible prompt construction is:

```
t | 0 E t>ka | ka
ka | 0 E k>csj | csja
csja | 0 E c>jaocn | jaocnsja
jaocnsja | 5 E s>iq | jaocniqja
jaocniqja | 7 E j>gd | jaocniqgda
```

The post\-training prompt isjaocniqgda, with targett\. A primitive contraction solution is:

```
jaocniqgda | 0 4 C c>jaocn | ciqgda
ciqgda | 1 2 C s>iq | csgda
csgda | 2 3 C j>gd | csja
csja | 0 2 C k>csj | ka
ka | 0 1 C t>ka | t
```

This requires five primitive contractions, two steps beyond the illustrative budget\.

These examples illustrate the post\-training data construction\. RL and RFT use the same prompts and final\-answer reward; they differ only in how sampled rollouts are used for optimization\. GRPO updates from both successful and failed completions through group\-relative advantages, while RFT retains only successful completions as supervised targets\.