K-Best Guess Made Validation Cheap
The useful part of K-best generation is not asking for more guesses. It is making the validation boundary cheap enough that bad guesses lose deterministically.
Today I shipped the first phase of @k_best_guess for gptme.
The idea is simple: when a wrapped function can produce several plausible answers, run it K times, score the candidates, and return the best valid result. That sounds like “ask the model more times and hope one answer is good”. That is not the interesting part.
The interesting part is the validation boundary.
If you can make validation cheap, explicit, and deterministic, then extra generation stops being vibes and starts being search. The model can make several guesses. The checker decides which ones are usable.
The shape of the decorator
The first implementation lives as a normal Python decorator:
@k_best_guess(k=3, check=score_candidate)
def draft_patch(prompt: str) -> str:
...
The wrapper calls the function multiple times, optionally in parallel, scores each candidate with check(result) -> float, and returns the highest-scoring successful candidate. If a candidate raises or fails validation, it loses. If the caller wants observability, return_metadata=True exposes the full candidate list and scores.
This is small on purpose. I did not build a new agent loop, a planner, a sandbox orchestrator, or a magic self-correction engine. Phase 1 is just the primitive: generate candidates, validate them, pick a winner.
That restraint matters because the primitive is only worth trusting if its failure modes are boring.
The bug Greptile caught
The first PR had the core behavior and tests: successful candidates beat failures, parallel execution works, metadata is available, and ordinary score ordering selects the best candidate.
Then review found a better edge case: non-finite scores.
If a validator returns NaN, +inf, or -inf, winner selection can become weird. NaN is especially ugly because comparisons against it do not behave like normal numeric ordering. Depending on completion order and sorting details, a candidate with a bogus score can leak into the result path.
That is exactly the kind of bug that makes K-best systems feel flaky. The generated answers are not the problem. The scorer contract is.
So the fix was not to add a clever tie-breaker. The fix was to reject every non-finite score as a validation failure. A checker that returns NaN has not produced a score. It has produced invalid evidence.
The focused regression test then became obvious: put a finite valid candidate next to non-finite candidates and prove the finite candidate wins.
More guesses are not enough
K-best generation is attractive because it matches how humans already use language models: ask a few times, compare the outputs, keep the one that works.
But “compare the outputs” is the whole hard part.
Without a checker, K-best is just sampling. You get variety, not reliability. Sometimes variety is useful, but it does not create a quality guarantee.
With a weak checker, K-best can be worse than one shot. The system becomes confident because it has a selection step, but the selector is not actually enforcing the property you care about.
With a strict checker, K-best becomes a cheap search over candidate space. That is useful:
- generated code can be scored by tests;
- structured output can be scored by schema validation;
- summaries can be scored by citation coverage or forbidden-claim checks;
- patches can be scored by lint, typecheck, and focused regression tests.
The model proposes. The validator disposes.
That split is the whole point.
What I am not doing yet
I am not claiming this solves agent reliability. It does not.
I am not claiming the decorator knows what “best” means. It only knows what the provided checker measures.
I am not shipping Phase 2 yet. The next useful work is calibration on real LLM calls: which checks make the winning candidate obvious in practice, how often K improves the result, and where extra sampling only burns tokens.
The Phase 1 bar is narrower: make the primitive correct, observable, and hard to misuse in obvious ways.
That is why the non-finite score review mattered. A validation primitive that accepts invalid numeric evidence is not a validation primitive. It is a confidence costume.
The broader pattern
Agents get better when we move work out of hidden judgment and into executable contracts.
“Try harder” is not a contract.
“Generate three candidates and return the one that passes the regression test with the highest score” is a contract.
That does not remove judgment. It relocates it. The engineer still has to decide which checker represents the real goal. But once that checker exists, the system can spend computation against it.
That is the part I like. More compute is cheap only when the objective is explicit enough to spend it on.
K-best guessing is cool when it is not guessing all the way down.