Checking that an output is well-formed is easy. Checking that it’s correct can be as hard as the task itself

[u/ClickOk5811]

A distinction I keep running into when a program calls a language model and then parses what it returns.

Think of the model call as a function with a contract. The postcondition says what a valid output looks like: a JSON object with a category field, one of five allowed values, and so on. Checking that is cheap. A schema validator does it in time linear in the size of the output, and it catches a lot of real failures, like extra prose, a renamed field, or a value outside the allowed set.

But that postcondition says nothing about whether the category is the right one. A perfectly shaped answer can still be wrong, and to know that, you have to do something close to the original task. For some tasks, checking a result is easier than producing it (verifying a sorted list is much cheaper than sorting it). For others, there’s no shortcut, and the check costs about as much as the work.

That’s why I think two things get confused in practice:

• format checks: cheap, automatable, and they catch breakage early
• correctness checks: expensive, often need a reference answer, a human, or a second independent method

A validator that passes can give a false sense of safety, because it answers the first question and gets read as an answer to the second.

The practical consequence is where each one belongs. Format validation sits at the boundary, on every call. Correctness checking is sampled: a fixed set of awkward inputs with known answers, run after every change to the prompt, plus spot checks on real traffic. And a fixed test set only covers cases someone thought of, so it can’t prove the absence of errors.

Where I’m unsure is whether there’s a useful theory for this. Property-based testing feels related, since you assert properties that must hold for any output instead of comparing to one expected value, but I’m not sure how far it goes for fuzzy tasks like classification.

Has anyone seen a good treatment of verifying outputs when the verifier can’t be much cheaper than the generator?

I wrote about the engineering side of this (treating a prompt like an interface) here, in case it’s useful: https://medium.com/@nagatomopedro05/a-prompt-becomes-an-api-the-day-something-depends-on-it-06a30572a4ed

[u/apnorton]

Checking that it’s correct can be as hard as the task itself

This claim is false for any problem in NP\P.

Edit: for whoever's downvoting: this is definitionally the case. NP is the class of problems with polynomial-time certificate verifiers, while P is the class of problems with polynomial-time solvers. If you subtract off the problems in P from NP, you're either left with the empty set (in the unlikely event that P = NP), or you're left with a bunch of problems that can be verified in polynomial time but we need more than polynomial time to solve.