BoolMin-RLVR

Training Qwen3-4B to minimize Boolean circuits, then checking whether the result transferred to graduate-level science reasoning.

Ryan Clark · April 2026

Matched-pair zero-shot evaluation. Same base model (Qwen3-4B-Instruct-2507), same algorithm (GRPO via Tinker), same hyperparameters, matched training budget (~250 / ~150 steps; ~$11–15 each). Only the training task varies. n=1 seed per condition; see the limitations section.

The question

The recent RLVR-for-reasoning literature has a soft assumption running through it: that any task with a fast verifier produces transfer to general reasoning, because the structural properties of the training signal (correctness feedback, exploration through rollouts) are what matter. NP-Engine reported +4.1 on GPQA from training on classical NP problems (TSP, knapsack, graph coloring). If the assumption holds, training on any inverse-design task with similar structure should produce similar transfer.

I wanted to actually test that assumption, both with a positive case (does a different NP-complete inverse-design task work?) and a stress test (does an inverse-design task in an unrelated domain work?). The two experiments share an algorithm, a model, a training budget, and an evaluation suite; the only thing that varies is what the model is trained on.

This post is the positive case. The negative case, RNA inverse folding, is written up separately.

Why Boolean minimization

Boolean circuit minimization from a truth table (given the 2^n output bits, find a minimal sum-of-products expression) has three properties that make it a clean RLVR target:

• NP-complete with a fast verifier. Finding the minimum is hard; checking that a candidate expression matches the truth table on all 2^n rows is linear in the table size.
• Distinct from pretraining content. Circuit minimization shows up in CS curricula but as a worked example, not as bulk training data. Karnaugh maps and the Quine–McCluskey method don't appear at scale.
• A continuous quality signal. Beyond correctness, smaller expressions are better. Espresso's gate count gives a natural reference for quality, and rewards can be shaped to encourage minimization without making correctness optional.

The task is structurally close to NP-Engine's targets (combinatorial search with verifiable answers) but in a domain (Boolean algebra) that's distinct enough to make memorization implausible.

Task and reward

The model receives an n-input truth table as text and produces a sum-of-products expression using &, |, ~:

A B C D | Y
0 0 0 0 | 0
0 0 0 1 | 0
0 0 1 0 | 1
... (16 rows)

Output:  Y = (A & ~B) | (C & D)

The reward is two-tiered:

1. Correctness (binary). Parse the expression, evaluate against all 2^n truth-table rows. Any mismatch → reward 0.
2. Quality (continuous, only if correct). min(reference_gate_count / model_gate_count, 1.0), where gate count is the AST node count and the reference is Espresso's output via PyEDA.

Default weights (correctness=1.0, quality=0.5, format=0.1) place most of the signal on correctness. A correct expression matching Espresso's gate count earns ~1.0; a correct-but-bloated expression earns proportionally less.

Difficulty tiers

The eval set freezes 500 instances (125 per tier). For the main training run, I trained on easy-tier-only: partly to keep the budget down, partly because the question was whether transfer could come from a single difficulty tier rather than requiring a curriculum.

Training

• Model: Qwen3-4B-Instruct-2507 via Tinker. The instruct base is a known caveat (the model has already seen RL-flavored instruction tuning), but Tinker doesn't serve smaller base Qwen variants and the budget targeted a 4B model.
• Algorithm: GRPO, LoRA rank 16, learning rate 2e-5, KL coefficient 0.01.
• Batch: 8 prompts × 4 rollouts = 32 trajectories per step.
• Steps: 250 total (50-step smoke, then a 200-step continuation).
• Total spend: $15.15 for training, ~$23 for evaluation, $41.70 all-in.

In-domain results

Evaluated on the frozen 500-instance set:

Training on easy-tier-only produced double-digit improvements on medium and expert tiers, so the model isn't just memorizing easy-tier patterns. Hard tier, on the other hand, remains effectively zero: 2^7 = 128-row truth tables exceed what a 4B model can reason through reliably, so any transfer from hard instances was always going to be limited. The in-domain generalization story rests on the easy → medium/expert jump.

Cross-domain transfer

This is the actual question. Zero-shot evaluation of the trained checkpoint against three reasoning benchmarks:

The number I came in wanting to see was GPQA Diamond, and it climbed +3.5, in the same ballpark as NP-Engine's +4.1 from training on classical NP problems. The gain also grew with more training (+1.5 at 50 steps, +3.5 at 250), consistent with steady learning rather than a noisy point estimate.

MATH-500 was untouched. Two readings are plausible: (a) the 4B model is ceiling-saturated on MATH at 91%, or (b) Boolean minimization and mathematical reasoning engage genuinely different model capacities. I'd bet on (a) given the small headroom but can't distinguish them from the data.

IFEval showed a small consistent regression: a modest alignment tax. The 50-step checkpoint had a small positive shift on IFEval that disappeared by step 250, suggesting whatever IFEval-aligned behavior emerged early was either noise or got optimized away by the longer training. The size is small enough that I'd believe a second seed could reverse it, but the direction is consistent across both eval modes.

The RNA comparison

The question this experiment was built to answer is whether RLVR transfer is task-agnostic. I ran a parallel experiment on RNA inverse folding with the algorithm, model family, training budget, and eval suite held constant. The in-domain story for RNA was good (perfect-solve rate 30% → 52%; written up here). The cross-domain story was the opposite of BoolMin's:

Both runs produced strong in-domain learning. The transfer signs went opposite ways: one helped graduate-level science reasoning, the other actively hurt it.

Takeaways

1. Boolean minimization works as an RLVR signal. +27.2pp on easy, +21.6 on medium (from easy-only training), +3.5 on GPQA, at a $42 total budget on a 4B model.
2. Cross-domain transfer is task-dependent, not algorithm-dependent. Matched-budget runs on two inverse-design tasks produce qualitatively different transfer signs. The implication for anyone designing an RLVR training mix is that "find any task with a fast verifier" isn't sufficient. Task choice carries real selection pressure on what the model generalizes to.
3. Easy-tier-only training produces meaningful out-of-tier generalization. Medium-tier instances are explicitly out-of-distribution during training, and the model still improved by 21.6pp on them. This is a small data point against the "RLVR just optimizes the training distribution" reading.

Caveats

• Instruct-tuned base. Same caveat as RNA. The transfer claim survives because the base baseline was already established; the magnitude could shift on a clean base model.
• Single seed (in-flight: second). +3.5 on a 198-instance benchmark (GPQA Diamond) is a point estimate with non-trivial variance. The two pieces of evidence I have that it's signal rather than noise are: (a) the monotonic growth from +1.5 at step 50 to +3.5 at step 250, where sampling noise wouldn't move in one direction with training, and (b) the matched comparison with RNA produced the opposite sign at the same scale. A second seed (seed-42, 250-step from scratch, configured in circuits/configs/trial_seed42.yaml) is currently running; the two-seed mean will replace the n=1 estimate when it lands.
• Easy-tier-only training. The curriculum was designed in three phases (easy → easy+medium → all tiers). Only phase 1 ran. Whether the transfer effect grows with curriculum exposure, holds steady, or breaks is the open question the next training run should answer.
• 4B scale. Hard-tier in-domain performance is effectively zero. Larger models would let hard-tier instances enter the training distribution, potentially changing what kind of reasoning the model learns.
• The RNA negative-control is informative but not airtight. RNA and BoolMin differ in domain, output format, and reward shape. A cleaner control (e.g., BoolMin with shuffled truth tables, breaking the verifier) would isolate "task structure" from "task content." Worth running.

Open threads

1. Multi-seed replication of the GPQA result. The +3.5 is the single most-cited number from this experiment and it deserves error bars.
2. Curriculum execution. Phase 2 (easy + medium) for ~750 additional steps, evaluated against the same suite. If GPQA continues to climb, that's strong evidence the effect scales; if it plateaus or reverses, equally informative.
3. Disentangling task content from task structure. A shuffled-truth-table control (verifier accepts anything) would test whether the model is learning logic or just learning to produce output the verifier likes. Companion run on a non-NP verifiable task in the same domain.
4. Scaling to 7B. Hard-tier in-domain performance was near zero at 4B; whether a 7B model can both learn hard instances and produce stronger transfer is the natural scaling question.
5. Investigating IFEval drift. The 50-step → 250-step IFEval reversal hints at an optimization-pressure mechanism I'd like to characterize; KL divergence from the base over training would tell us whether instruction-following degrades smoothly or in a phase change.

Code & resources

• Repository: github.com/RyanClark2k/rlvr-transfer-experiments
• Reward function: src/reward/reward_fn.py
• Expression parser and verifier: src/solver/verify.py
• GRPO training loop: src/training/grpo_train.py
• Curriculum scheduler: src/training/curriculum.py
• Results (in-domain and cross-domain): results/eval_indomain/, results/eval_250/
• Experiment design: experiment.md · Baselines summary: baselines.md