category: training · status: draft · updated: 2026-11-02

Rejection Sampling and STaR

Here is the whole idea in one sentence: let the model try the task k times, keep only the attempts that pass a verifier, and fine-tune on the winners. Everything else is refinement.

Think of a basketball player filming free throws. She shoots a hundred, keeps the film of the makes only, studies exactly what her body did on those, and shoots again. Nobody has to explain the biomechanics — the outcome selects the examples. That is rejection sampling for language models, and it's the single best value-per-dollar move in our pipeline because our fleet already has everything it needs: tasks that regenerate on demand (vulhub farm, procedural generator, EVM asserts), and win-condition checkers that say make or miss.

The lineage

• STaR (Self-Taught Reasoner, Zelikman et al. 2022, arXiv:2203.14465) coined the loop: sample rationales, keep those ending in the correct answer, fine-tune, repeat until it stops improving. Its clever trick was rationalization — for problems the model never gets right, hint the answer and let it generate a rationale for that hint, then train on the rationale without the hint. This escapes the "you can only learn what you already sometimes do" trap.
• RFT (Rejection sampling Fine-Tuning, Yuan et al. 2023, arXiv:2308.01825) applied it to math: sample k solutions, keep correct ones — and showed you should de-duplicate reasoning paths, because five token-identical wins teach one thing, five distinct wins teach five. Gains were largest for weaker models.
• ReST-EM and DeepSeek-R1's mid-pipeline SFT stages carry the same DNA: before/around full RL, harvest your own verified successes as training data.

Why it's nearly free compared to full RL

GRPO needs the training loop online: rollouts flow into gradient updates on rented H100s, and you pay trainer rent the whole time. Rejection sampling splits the loop in two halves that don't overlap in time or hardware:

1. Rollout phase — pure inference. No gradients, no optimizer states, no trainer. The 35B-A3B base costs ~3B active params per token under vLLM; even the M5 Max 128GB can run MLX rollouts against local fleet containers overnight. Batch of 16 attempts on 200 procedural tasks is an evening, not a cluster reservation.
2. Train phase — plain SFT on the kept winners. Small data (thousands, not millions), so a LoRA pass, or a short full-param run on a single 8×H100 rental.

The verifier is not new machinery — it's the same ARVO-style differential oracle the fleet uses for everything: PoC must crash the pre-patch build and not the post-patch build; the flag file must appear; the EVM assert must flip; the SOC agent must hit recall on the planted campaign. Verification is a container run, often seconds. So marginal cost per kept trajectory ≈ rollout tokens + sandbox minutes. CyberFactory's rebuild math in our dossier (~50k kept trajectories needs ~150–300k rollouts over 2–4 weeks on a 64–128 vCPU rental) is a teacher-scale budget; self-sampling by an A3B on local hardware is far cheaper still.

What the numbers say

• CTF-Dojo (Amazon Science, arXiv:2508.18370): training on just 486 execution-verified trajectories produced +11.6% absolute gains across InterCode-CTF and NYU CTF baselines. Four hundred and eighty-six. This is the headline fact about trajectory quality vs quantity — a few hundred real, verified attempts beat scraped corpora an order of magnitude larger.
• CyberFactory (arXiv:2608.23181): conditioning the teacher with a written vulnerability-analysis skill plus 5×15-minute attempts moved solve rate 43.3% → 46.5%, roughly 4× cheaper per successful trajectory than 1×60-minute attempts (the paper admits this isn't compute-matched, but the direction held). Multiple short attempts + a keep-the-winners filter is rejection sampling applied to data manufacture. And after SFT on those trajectories, the student internalized the behavior — exploration/validation calls went from ~0 to 1.32/1.05 per trajectory without the skill at inference. Rejection sampling doesn't just collect answers; it distills a procedure out of the survivors.

Worked example (ours)

Friday refresh. The procedural generator emits 200 reskins of this week's vuln class — parameterized SQLi in a fresh scaffold, randomized flag markers, new container digests. The 27B warm-start model samples k=16 per task at temperature 1.0. The oracle re-executes each candidate exploit against pre/post containers. Result: 200 × 16 = 3,200 rollouts, 287 pass, dedupe near-identical paths → 190 distinct winners. A filter drops winners from tasks the base model already solves 100% of the time (CyberFactory's easy-instance filtering — no teaching signal in the makes you never miss). ~140 trajectories join the week's SFT set; a LoRA refresh runs overnight on the M5 Max; Saturday's held-out eval row goes into RESULTS.md. Total marginal cost: sandbox hours and electricity.

Failure modes, honestly

• Ceiling: you can only harvest what the model sometimes does. STaR converges and stops improving; the gap from 46% to 80% is exactly what GRPO/GSPO exists for (see [[sft-vs-dpo-vs-grpo-vs-rlvr]]).
• Distribution collapse: training only on wins makes the model overconfident and narrows entropy, which reduces future win diversity. Remedies: dedupe (RFT), mix in base-model replay data, keep temperature up during sampling.
• Verifier gap: keep only what the oracle actually proves. A trajectory that "looks like" a win but wasn't re-executed is a writeup wearing a costume (see [[trajectories-vs-writeups]]).

Primary sources: STaR · RFT · CTF-Dojo · CyberFactory

See also: [[sft-vs-dpo-vs-grpo-vs-rlvr]] · [[trajectories-vs-writeups]] · [[cyberfactory-openaegis]] · [[landscape-2026]]