AI Research Portal

This paper investigates whether reinforcement learning (RL) post-training amplifies existing primitive skills or composes them into new, higher-level strategies. Using a fully observable rewrite-grammar environment, the authors pretrained a Transformer on primitive symbol-rewrite chains and then post-trained it on a trace-based reasoning task with binary rewards. Their empirical findings suggest that RL reorganizes primitive competence through a phased compositional mechanism, leading to the discovery and consolidation of reusable strategies, which allows it to solve problems that the pretrained model struggles with, even under larger sampling budgets.

The paper addresses the following bottlenecks:

The difficulty in distinguishing whether RL post-training merely reweights latent behaviors or genuinely composes new, higher-level strategies.
The challenge of observing and auditing the mechanisms behind emergent behaviors in post-trained models, making it unclear if new capabilities arise from broader exploration or selective filtering.
The lack of understanding regarding what specific pretraining structures enable the emergence of new strategies during post-training.

A fully observable rewrite-grammar testbed that allows for the exact auditing of generated rewrites, enabling a four-way taxonomy of primitive, macro, parallel, and spurious actions.
Demonstration of a phased procedural chunking mechanism where RL first strengthens primitive reductions and then discovers, reuses, and consolidates valid compositions.
Evidence that RL expands the capability frontier on held-out problems, solving tasks that the pretrained model rarely solves, even with significantly larger sampling budgets.
Insight that RL's advantage stems from selective exploration of valid reusable structures rather than sheer exploration volume, contrasting with rejection fine-tuning which produces more spurious rewrites.
Findings that the emergence of compositional strategies is contingent on pretraining organizing primitive competence into reduction procedures that RL can later compress and reuse.

The method involves a two-stage process: pretraining and post-training.

Pretraining: A Transformer model is trained from scratch on "primitive rewrite chains." This data is generated by repeatedly sampling valid primitive expansion or contraction operations, creating sequences where the output of one step becomes the input for the next. This exposes the model to local, grammar-consistent rewrite dynamics but not to more complex, non-primitive shortcuts. The contraction weight parameter 'p' influences the frequency of contraction moves during pretraining.

Post-training: The pretrained model is then fine-tuned on a "Trace-Based Reasoning Task."

Task Setup: Prompts are generated by expanding a target symbol to a longer word. The model's task is to generate a step-by-step contraction trace that reduces the word back to the target symbol. Difficulty is defined by the number of primitive contraction steps required beyond a 256-token generation budget.
Reward: A binary, outcome-only reward is given: 1 if the trajectory is well-formed (correct sequence of primitive operations) and ends with the target symbol, and 0 otherwise. Intermediate steps are not supervised.
RL Algorithm: Group Relative Policy Optimization (GRPO) is used for RL post-training. GRPO optimizes based on group-relative advantages, considering both successful and failed completions within a prompt group.
Baseline: Rejection Fine-Tuning (RFT) is used as a strong on-policy comparator. RFT samples rollouts, retains successful ones, and performs next-token prediction on them.

Analysis: The key innovation is the ability to audit every generated rewrite against the grammar. This allows for classifying rewrites into primitive, macro (sequential composition), parallel (independent composition), or spurious categories, enabling detailed analysis of strategy emergence.

Grammar: Alphabet size N=20. Each character maps to 1-3 right-hand-side strings of lengths 2-6. Right-hand-side strings are globally unique.
Pretraining Data Generation: Chains of primitive expansion/contraction steps. Contraction weight 'p' is used to locally upweight contraction moves. Default p=4.
Model Architecture: 12 layers, 512 hidden dimension, 8 attention heads, MLP expansion ratio of 4, RoPE positional encoding, QK normalization, tanh soft-cap on logits.
Optimization: AdamW optimizer with a warm/flat/cool schedule. Peak learning rate 8 × 10-4. Sequence length 512. bfloat16 training. Gradient clipping at norm 1.0.
Pretraining Contraction Weight (p): A local weight multiplier for contraction moves. Higher 'p' increases the likelihood of contractions and chained primitive reductions.
Post-training Prompt Generation: Prompts are generated by forward expansion. Difficulty levels are based on the number of primitive contraction steps exceeding a 256-token budget. Training mixture: 60% Difficulty 1, 20% Difficulty 2, 20% Difficulty 3. Evaluation uses held-out problems up to Difficulty 6.
RL Algorithm (GRPO): Group size G=4. Uses group-relative advantages. Temperature=0.8, top-k=5, max generation length=256 tokens. Reverse-KL penalty beta=10-3, epsilon=0.2.
RFT Baseline: Uses same prompt distribution and group size G=4. Retains only successful rollouts (r=1) for supervised next-token prediction.
Compute: Experiments run on nodes with 4× NVIDIA H100 GPUs.

Datasets: Held-out problems spanning Difficulties 1-6, including buckets beyond the training distribution.
Metrics: Pass@k (specifically pass@16 for post-training evaluation, and pass@64, pass@256, pass@1024 for base model evaluation). Trajectory analysis classifying rewrites as primitive, macro, parallel, or spurious.
Baselines: Pretrained model, Rejection Fine-Tuning (RFT).
Numeric Results:
- RL solves held-out problems that the pretrained model rarely solves. For example, at pass@1024, the pretrained model achieves 0% on Buckets 4-5, while RL achieves pass@16 on these harder buckets.
- RFT improves rapidly early in training but plateaus, while RL shows slower initial gains but continues to improve, especially on harder buckets.
- Figure 2 shows a delayed transition in RL: primitive contractions dominate early, followed by macro contractions around iteration 5,000, and parallel contractions emerging later.
- Figure 3 shows RL discovers new macro rules throughout training and increasingly reuses previously discovered rules, indicating consolidation. RFT discovers fewer macro rules and has weaker reuse.
- Figure 4 demonstrates that RL generates fewer spurious contractions and concentrates behavior into valid macro and parallel contractions, whereas RFT generates many non-primitive actions, but a larger fraction are spurious.
Runtime/Training Cost: Not explicitly stated in terms of hours or specific computational resources beyond the GPU type. Learning curves are averaged over three training seeds.

The study is conducted in a controlled, fully observable rewrite-grammar environment, which may not fully generalize to the complexities and ambiguities of natural language reasoning tasks.
The paper acknowledges that the scope is controlled and does not claim that all large language models must exhibit the exact same phases or taxonomy observed.

Method evidence: "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." (section: 1. Introduction)
Result evidence: "Figure 5 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 (Xiong et al., 2025). 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." (section: 6. RL Expands the Held-Out Capability Frontier)
Limitation evidence: "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." (section: 8. Discussion)

RL Post-Training Builds Compositional Reasoning Strategies

Abstract

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Additional Figures