Skip to content

Make It Checkable

Published: at 02:11 AM
0 views

Fifty-two milliseconds to find one valid answer. Thirty-five microseconds to check whether it was right. Same machine, same instance, one after the other.

The problem was random 3-SAT, generated at the clause-to-variable ratio where these instances are hardest, about 4.26. I wrote a local search to find a satisfying assignment and a single linear pass to check one, then ran both across fifteen instances at three sizes.

variablesclausesfind, medianfind, 10th to 90thcheck, medianratio
401702.7 ms0.7 to 9.0 ms12.4 µs214
7029814.5 ms5.4 to 86 ms22.1 µs657
11046952 ms14 to 3,400 ms34.5 µs1,494

Two things in that table matter more than the ratios.

The check is boring. Going from 170 clauses to 469 is a factor of 2.8, and the check time went from 12.4 to 34.5 microseconds, a factor of 2.8. It is linear in the size of the thing being checked, and it does not care how the answer was produced.

The search is not boring at all. Going from 40 variables to 110 is under a factor of three, and the median search took twenty times longer. At 110 variables the 90th percentile run took about 240 times longer than the 10th percentile run. Finding is expensive and unpredictable. Checking is cheap and steady. Those are different kinds of cost, and only one of them is easy to budget for.

The definition was always this

The pattern is older than my script. In 1971 Stephen Cook defined the problems whose proposed answers can be checked in polynomial time, and that definition is still the most useful sentence in the field. A certificate you can verify cheaply is the entire idea. The search is allowed to be hopeless. The check is not.

For years I treated that as a fact about algorithms. This year it started setting my priorities.

What the training signal actually is

The clearest place to watch the asymmetry is in how models get better.

In 2017, Christiano and colleagues taught an RL agent to play Atari and to move a simulated robot without ever writing down a reward function. They did it by showing a human pairs of short clips and asking which was better. The humans looked at less than one percent of the agent’s interactions with the environment. That is a check, not a demonstration, and it was enough.

Six years later, Lightman and colleagues compared two ways to train a model to do competition math. Outcome supervision grades the final answer. Process supervision grades every step. The process-supervised model, which is checked at every step, solved 78 percent of a representative slice of the MATH test set and beat outcome supervision on the same budget. Checking more finely worked better than checking less.

Jason Wei gave the pattern a name and a rule of thumb: the ease of training AI on a task is proportional to how verifiable the task is. That is a rule of thumb rather than a theorem, and it lines up with both of the results above. Grading is the lever. When grading is cheap, the machine can practice. When it is not, the machine stalls.

Verifiability is a choice

The part I keep coming back to is that the asymmetry is something you decide.

Wei points out that you can improve it by front-loading work. A competition problem is trivial to grade if you already have the answer key. A piece of code is tedious to read but quick to test if you wrote the test cases first. In both cases somebody spent effort earlier so the check would be cheap later. That is a design decision, made by a person, before any of the interesting work happened.

I built Glide that way and did not fully understand why until I looked at it through this lens. The model does not hand the user an answer. It hands over a proposal with the evidence attached, and the user accepts or rejects it in one gesture. The rejection is the training signal. The interface exists to make the check cost one click, because a check that costs one click is one a person will actually run.

I wrote in The Idle Machine that a deterministic check is the cheapest verifier there is. This post is the long version of that sentence. A deterministic check has the property the table above is really about: its cost is known before you run it. Sentinel runs hundreds of them before anything ships, and the reason is not that they are clever. The reason is that they are cheap enough to run on everything.

When you cannot check, you trust

The asymmetry has a dark side, and it is old.

In 1984 Ken Thompson gave a Turing Award lecture about a compiler that could insert a backdoor into any program it compiled, including the compiler that compiled it. His point was not that you should be paranoid. His point was that you cannot trust code you did not create yourself, and that the places where verification is expensive are exactly the places where trust gets substituted in.

That substitution is the thing to watch. When the check is cheap, you check. When the check is expensive, you buy a brand, or a process, or a signature, and the thing you bought is now doing work that nobody verified. Every expensive-to-check domain has a version of this. The check did not disappear. It moved, and it moved to somewhere you are not looking.

Organizations do the same thing with their own output. A company that cannot cheaply check what it produces will still learn from what it produces. I have written about that before, and it is the same shape as model collapse: unverified output that comes back around as training input, until the thing the system knows is a copy of its own mistakes.

What I ask about a new tool

The question I now ask about any new tool is what it costs me to be sure the output is right. Not how fast it makes things. Not how good the demo looks. The check.

A tool that produces a thousand things I cannot check has produced nothing I can use, because the cost of trusting it lands on me eventually and it lands all at once. I would rather have a slow generator with a fast check than a fast generator I have to read line by line.

Generation is getting cheaper every month. That is the easy half. The half that decides what actually ships is whether anybody built the check first.


Next Post
More Sums Than Differences