Learning to Revise Rules from Graded Debugging Traces

Language models are better at proposing a rule from a few examples than at fixing a rule that turns out to be wrong. A common recipe for few-shot rule induction is to have the model write a candidate rule as a Python program, run it on the given examples, and feed the failures back for another attempt. This loop helps, but the gains stop after two or three rounds. Training data cannot easily fix this, because almost no text anywhere records the useful process: "my rule predicted X on this input, the right answer is Y, so the rule is missing this case, here is the corrected program." Rule-learning benchmarks give inputs and outputs only. Human annotation of such traces is expensive and noisy.

We propose to manufacture these traces where they can be checked step by step. When we generate a training task ourselves by sampling a hidden ground-truth program and executing it, we know the true rule. So we can grade every intermediate revision a model makes, not only its final answer, by measuring how much closer each revised program behaves to the hidden one. We let a model attempt and repeatedly debug thousands of such self-generated tasks. We keep only the revision steps that verifiably move it toward the truth, and we keep only explanations whose factual claims about program behavior an interpreter confirms. Then we fine-tune on these graded trajectories. The claim is that a model trained this way learns the skill of revising under counterexamples. It should keep improving past the usual three-round plateau and reach the true rule more often than models trained on final answers alone, at matched inference cost.

Core Claim and How It Differs

The closest work falls into three groups, and each lacks one piece. Inference-only refinement loops supply the method we reuse. Phenomenal Yet Puzzling proposes, executes, and refines rule hypotheses with counterexample feedback, raising MiniSCAN task accuracy from 0% to 85%. It also shows that models fail to execute their own correct rules in nearly 20% of cases. Analysis of Error Sources in LLM-based Hypothesis Search adds natural-language hypotheses and up to 3 rounds of code repair, reaching 0.487 mean test accuracy on List Functions. Its costs are high: up to 257 calls per task, and roughly half of the programs that passed its single held-out test were wrong about the true rule. Neither paper trains anything. Both cap refinement because further rounds rarely help.

Synthetic-data methods address explanation scarcity but throw away the revision process. ItD samples rules, deduces input-output pairs, and trains a model to predict the rule. This is entirely in natural language, with no interpreter and no notion of fixing a wrong guess. Template-based Data Generation verifies generated math solutions by execution and discards failures instead of debugging them. LaTRO optimizes rationales against final answers only.

RefCritic is the closest in spirit. It rewards a critic when its feedback lets a policy fix a wrong solution. It is single-turn, works on problems with a known answer rather than induction from few examples, and grades only whether the fix succeeded. Our difference from all of these is a dense, execution-based grade on every turn of a multi-turn revision, made possible by knowing the hidden program. That grade is used to select training trajectories for an inductor.

The grade is simple. For a candidate program $g$ and the hidden program $f$, let

$$d(g, f) = \frac{1}{|P|}\sum_{x \in P} \mathbb{1}[g(x) \neq f(x)],$$

where $P$ is a large probe set of inputs drawn from the task's input distribution, never shown to the model. A revision step $g_t \to g_{t+1}$ is kept only if $d(g_{t+1}, f) < d(g_t, f)$. Steps that do not improve are rolled back, borrowing the rollback idea that MEIC uses to escape the "new error trap" in hardware debugging. The rolled-back step, paired with its rejected alternative, is retained as preference data.

Research Program

Task generation. For List Functions-style tasks, a generator model writes candidate list-transformation programs. We remove any program whose outputs on a fixed fingerprint set of inputs match a benchmark task. This blocks contamination by behavior rather than by text. For cellular automata, we use the 95k-task training split of CellARC as the source of hidden rules. Its de Bruijn-graph oracle labels each input neighborhood as determined by the examples, determined by the rule, or ambiguous. That label lets us exclude counterexamples that no rule could have predicted, so the model is never trained to "fix" an information-theoretically unfixable miss.

Trajectory collection. An open 7–14B code model attempts each task in a loop of up to 8 turns. The model sees few-shot examples. The interpreter returns failing examples. When all shown examples pass but $d > 0$, a distinguishing input from $P$ is surfaced as a fresh counterexample; this targets the overfitting that the Parab et al. analysis exposed. Each turn has two parts. The first is a short natural-language diagnosis that must state what the current program outputs on the counterexample. The second is a revised program.

Two filters. The diagnosis's stated output is checked against the interpreter. This filters out unfaithful explanations, which directly targets the execution gap. The revision itself is checked with $d$.

Training. We fine-tune on the surviving trajectories. A second stage applies preference optimization on kept-versus-rolled-back steps.

Natural language versus code. We also test whether the natural-language diagnosis helps or hurts. The hypothesis-search results favor stating rules in language before writing code. CodeTransOcean reports that language-based reasoning degrades code tasks by making models myopic. We treat this as an empirical question settled by ablation, not an assumption.

Baselines

The naive reference point is direct input-output prompting of the same base model. Qiu et al. report it at 0% on MiniSCAN. We also report the untrained base model inside our exact 8-turn loop with the same counterexample oracle. This isolates training from the scaffold.

The strongest existing inference method is the Parab et al. hypothesis-search pipeline. On List Functions it reports 0.487 mean test accuracy, against a human average of 0.521 and 0.359 for direct GPT-4o program generation. We run it with the same base model at its published budget. We also run a compute-matched version: our model gets the same number of calls, and the pipeline gets our call count. On MiniSCAN, the comparison point is iterative hypothesis refinement at 85% task accuracy (Qiu et al.). Beating these baselines means higher accuracy under both scorings at an equal or smaller number of model calls. The two scorings are the original single-held-out-example scoring, kept for comparability, and true-rule accuracy on a probe set of several hundred inputs per task, our primary metric. On CellARC, the reference points are hand-coded symbolic solvers at about 88% token accuracy, GPT-5 at 48.1% on the extrapolation split, and a vanilla transformer at about 29%. Closing a meaningful share of the gap between the latter two and the solvers is the target. No reported result was found on Lacuna for MiniARC, so there we compare only against our own runs.

The data-matched competitors are trained on the same hidden programs with the same training tokens and tuning budget. The first is ItD-style forward data: examples paired with the correct program, with no revisions. ItD reports a 10% relative gain on List Functions but gives no absolute number in the file. The second is outcome-only rejection sampling, which keeps only the final correct program from successful trajectories.

Two ablations isolate the key ingredient. One keeps every trajectory that ends correct but drops the per-step $d$ filter. The other drops the natural-language diagnosis and trains on code-only revisions.

Why not just…?

Why not just train on forward-generated data, as ItD does? This is the most serious threat. Correct programs paired with their examples are cheap, perfectly verified, and plentiful, and a strong guesser might make revision unnecessary. Our bet is that forward data teaches first guesses but not how to use a counterexample. That would show up as flat accuracy after turn 2 when the forward-trained model is placed in the loop. If the forward-trained model, run in the same 8-turn loop, matches our model in true-rule accuracy, the revision-trace claim is wrong and we will report it as such.

Why not just spend more test-time samples on hypothesis search? The Parab et al. pipeline already approaches human accuracy, but at up to 257 calls per task. It also mostly fails when the generated hypotheses are wrong, which is the bottleneck those authors identify. The compute-matched comparison answers this directly. If extra samples buy more than training does per call, amortization through training is not worth it.

Why not just reward final correctness, as LaTRO-style or rejection-sampling training does? Outcome-only selection keeps trajectories that wander or regress and then recover by luck. It also keeps diagnoses that are wrong about program behavior. The no-step-filter ablation measures exactly what the per-turn grade adds. If that ablation ties the full method, dense grading is unnecessary and the simpler recipe should be preferred.

Why not just train a separate critic, as RefCritic does? RefCritic shows that critics trained by refinement reward improve, reaching 77.1 F1 on ProcessBench. It grades a single turn by success or failure. We include a RefCritic-style critic, trained on our tasks and paired with the base policy, as an additional baseline. Our expectation is that a graded, multi-turn signal on one model beats a binary single-turn signal split across two models. That expectation is testable rather than assumed.

Decisive Checks

Three results would settle the proposal. The first is the accuracy-by-turn curve on held-out List Functions and the CellARC extrapolation split. The trained model should keep gaining from turns 4 to 8 while every baseline, including the forward-data model in the same loop, flattens by turn 3. The second is a reduction in the share of programs that pass the shown examples but fail the probe set, compared with the roughly 50% rate the Parab et al. analysis reported. The third is the code-only ablation, which tells us whether checked natural-language diagnoses earn their tokens in rule revision, or whether the concern raised by CodeTransOcean about language-based reasoning in code tasks holds here too.