Ask an agent to plan something that cannot be done, and it rarely says so. It writes a plan that quietly breaks one of your limits, or it keeps searching until it runs out of tokens. I ran two small reinforcement learning (RL) experiments to see which reward teaches a model to say “not possible” when that is true, and only when that is true. The short answer: a reward can only teach what it can check.
Each task asks for a one-day outing for a group: pick one option in each of four slots (transport, museum, lunch, evening), four options per slot, so 256 combinations. Every task has three limits: a total budget, a finishing time, and one excluded tag (“no option may contain nuts”). About a third of the tasks are impossible. Because the world is closed, a program can enumerate all 256 combinations, so I always know whether “not possible” is the right answer.
In both experiments the policy was trained with GRPO (a group of answers per task, each scored against the group average), with LoRA adapters on Tinker. The test set, the rewards and the reading rules were written down before training, and each test set was used once.
Qwen3-8B was trained for 20 steps (128 answers per step) under four rewards:
| reward | says “not possible” on impossible tasks | solves possible tasks | says “not possible” on possible tasks | tokens per answer |
|---|---|---|---|---|
| none (base model, sampled twice) | 9–13 % | 74–76 % | 4 % | 1,210 |
| judge | 72.5 % | 84 % | 7 % | 645 |
| checker, “cannot verify” = 0 | 5 % | 90 % | 1 % | 1,176 |
| checker, “cannot verify” = −0.5 | 11 % | 78 % | 6 % | 1,193 |
| checker, then judge | 44 % | 89 % | 3 % | 1,022 |
The judge taught the model to stop and say “not possible”; its answers also halved in length. The checker taught it nothing about refusing, while giving the best results on tasks that can be done. The reason is in what each reward pays. Under the checker, an honest “not possible” scores exactly the same as running out of tokens, since neither can be checked without a search, while a plan that breaks one of the three limits still earns +1/3. Nothing in that reward is worth more than admitting, so the model never moved toward it. OpenAI's Why language models hallucinate makes the same point about benchmarks: when “I don't know” scores zero and a guess sometimes scores, guessing always wins.
The judge had a price as well: on possible tasks the trained model said “not possible” more often (from 4 % to 7 %), usually after an arithmetic slip.
If the checker cannot confirm a refusal, ask the model to prove it. The proof splits the options of one slot into cases and closes each case with a reason that can be checked from the catalog: a fixed option carries the excluded tag; or the cheapest allowed choice in every other slot already breaks the budget; or the quickest already finishes too late. A case can be split again on a second slot. Checking a line means scanning four options per slot, never the 256 combinations. I tested that the checker is sound: on possible tasks, no proof — random, or the strongest honest attempt — is ever accepted. The reward: +1 for a proof whose every line is true and whose cases cover everything, −1 for any false line, 0 for an incomplete proof. The control reward gives every “not possible” 0.
The first model could not do it. Qwen3-8B wrote no valid proof in 72 answers to impossible tasks, so the +1 never appears and RL has nothing to strengthen. I switched to Inkling-Small, a reasoning model, and trained its reasoning tokens as well.
The second model was already honest. Before any training, Inkling-Small said “not possible” on about 90 % of impossible tasks and never on a possible one. What it lacked was correct evidence. Here is one task (9 people, start 13:00, budget $665, finish by 17:30, no nuts), where the conclusion is right and one line is false:
FINAL PLAN: NOT POSSIBLE — no allowed combination satisfies both the $665 budget and the 17:30 deadline. PROOF: CASE E1: cheapest T3 M2 L2 E1 = $972 > $665 CASE E2: contains nuts CASE E3: SPLIT Transport CASE E3 T3: shortest T3 M2 L2 E3 ends 19:00 > 17:30 ...
M2 is the slowest museum (145 minutes), not the quickest. With the quickest museum and lunch, T3 + M1 + L1 + E3 takes 260 minutes and ends at 17:20, in time. The conclusion survives only because that combination costs $828. On the test set, about one “not possible” in five came with a proof that checked out, and about one in three contained a false step — most often an option called “cheapest” or “quickest” that was not. A grader that checks only the conclusion would mark all of these correct.
My first checker was wrong in a different way. It was strict about notation and accepted none of the 68 proofs Inkling-Small wrote on the development tasks. A checker with the same soundness that tolerates notation — a slot letter instead of its name, the arithmetic shown on the line, cases nested one level deeper — accepted 15 of them. Trained against the strict one, RL would have taught a notation, and I would have reported that the model cannot prove infeasibility.
Ten steps of RL changed nothing. Both rewards, 10 steps each, tested once on 60 new tasks (4 answers per task):
| Inkling-Small | says “not possible” on impossible tasks | with a proof that checks out | proofs with a false step | solves possible tasks |
|---|---|---|---|---|
| no training (sampled twice) | 89–95 % | 15–19 % | 36–41 % | 96–99 % |
| control reward | 89 % | 14 % | 32 % | 96 % |
| proof reward | 90 % | 19 % | 38 % | 96 % |
The reward differed between answers in up to half of the task groups each step, so there was a learning signal, and the model did not move. On the training samples the share of proofs with a false step even rose, from 29 % to 36 %. With 10 steps and one seed I cannot tell “too little training” from “this reward does not teach it”.
Limits of these results: a small closed world, English only, one training seed per reward, 10–20 steps, about $50 of compute in total. The experiments were pre-registered, and both negative results are reported as measured.