Generate-and-Verify: What P vs NP Teaches Us About AI Reasoning

At university, the P versus NP question arrived as a kind of magic trick that turned out not to be a trick at all. Checking an answer is easy; finding one can be brutally hard. Hand me a completed Sudoku and I can check it in seconds; completing a partially filled grid is a different kind of effort — and for the generalised n×n version, that completion problem is provably NP-complete. That gap between checking and solving felt like a curiosity back then. It is now, quietly, one of the load-bearing ideas in how we get more out of AI models.

This is the third post in a series that reads modern AI through the lens of the algorithms toolkit every computer science graduate already owns. It stands on its own, but if you enjoyed the earlier look at where token cost actually comes from, this one is about spending that cost wisely: put your compute into the search, and let a cheap check confirm the result [1].

The asymmetry at the heart of NP

The Clay Mathematics Institute states the P versus NP problem in one sentence: if it is easy to check that a solution to a problem is correct, is it also easy to solve the problem [2]? In its precise form, NP is about decision problems: a problem is in NP if, for a yes-instance, there is a certificate of length polynomial in the input size n that a deterministic verifier can check in time polynomial in n. The search versions this post cares about — actually producing such a certificate rather than just deciding one exists — sit alongside those decision problems through standard reductions. The open question, unproven since Cook and Levin posed it independently in 1971, is whether being easy to check implies being easy to solve. Almost everyone believes it does not, but nobody has proved it [2].

The Clay write-up gives a concrete picture: choosing 100 compatible students from 400 applicants when some pairs are forbidden. Checking a proposed list of 100 against the forbidden pairs is trivial. Generating a valid list from scratch is the hard part; the Clay write-up illustrates the blow-up by noting the number of possible groups exceeds the atoms in the known universe [2] — a vast search space is what makes brute force hopeless, though search-space size alone is an illustration, not a formal hardness proof. Classic NP-complete decision problems — Boolean satisfiability (SAT), independent set, or travelling-salesman-with-a-distance-bound — share this shape: a proposed certificate is checkable in poly(n), while no polynomial-time algorithm to find one is known.

Two precautions matter before mapping this onto AI, because this is where overclaiming usually starts. First, P versus NP is unproven; the presumed intractability of NP-complete problems is a very well-founded belief, not a theorem. Second, and more important for what follows, language models do not “solve” NP-hard problems. They heuristically search a space of candidate answers. The verification-is-cheap intuition is a lens for understanding why certain AI patterns pay off, not a claim that a model has cracked an intractable class.

The same asymmetry, running your reasoning models

Once you carry that asymmetry into AI, three familiar patterns line up as the same idea.

Test-time compute is the search half. Instead of accepting a model’s first answer, you let it spend more inference effort on hard instances: sample several candidates, explore a tree of reasoning steps, or think in longer chains. Snell and colleagues studied exactly this and found that how much test-time compute helps depends heavily on the difficulty of the prompt, which is why a compute-optimal strategy allocates the extra effort where it actually pays [3].

Verifiers are the check half. A separate model or rule scores candidates and picks the good ones, and it is often far smaller and cheaper than the generator. Lightman and colleagues showed that a process-supervised reward model, one that checks each reasoning step rather than only the final answer, significantly improves reliability on hard mathematics problems [4]. The checker does not need to be able to produce the solution; it only needs to recognise a good one, which is the cheap side of the asymmetry. It is worth being precise about what “recognise” means. A checkable test — a unit test’s assertions, a type checker, a schema, a tool that confirms a fact against a system of record — establishes exactly the property it encodes and nothing more (a unit test covers the executions it runs, not every possible one). A learned judge or reward model does not certify correctness at all; it predicts a score and can be confidently wrong. Both are useful in practice, but only the former behaves like a verifier in the complexity-theoretic sense. And in the AI setting “cheap” is an empirical property — the verifier runs smaller and faster than the generator — rather than a proven polynomial-time bound; the NP analogy is the intuition, not a formal guarantee.

Agent loops combine the two. Propose a candidate, an NP-style guess, then verify it with a P-style check (a test suite, a type checker, a tool call, a smaller judge model), and iterate on what fails. Most reliable agent workflows I have seen have this shape somewhere, because it is the practical form of “search is expensive, checking is cheap.”

Why this is such a good deal

The asymmetry is not just tidy; it can be economical. If checking is genuinely much cheaper than generating, a small, reliable verifier in front of a strong generator can raise quality for less added compute than making the generator bigger. Whether it also lowers your dollar cost and latency is a separate question — extra samples and verifier calls add tokens, wall-clock time, and billed invocations — so treat “cheaper” as something to measure end-to-end, not assume.

The published evidence is striking, with an honest boundary attached. In a compute-matched comparison — equal inference compute, not equal dollar cost or latency — Snell and colleagues found that spending that compute on test-time search let a smaller base model outperform a model roughly fourteen times its size, on problems where the smaller model already had a non-trivial success rate, and improved efficiency by more than four times over a simple best-of-N baseline [3]. The qualifier is the whole point: search amplifies a model that can already sometimes get there. It does not conjure capability from nothing.

This reframes a common instinct. The default move when quality is short is to reach for a bigger model. The asymmetry suggests a second option that is often cheaper: keep the generator, add a good verifier, and spend a controlled amount of extra search. When a reliable check exists and you have measured the full cost, that combination is often the better trade on compute — though not automatically on latency or billing.

The honest limits

Complexity theory also warns you where the trick stops working, and the warnings are practical.

The checker has to be cheap and reliable. The whole advantage comes from verification being genuinely easier than generation. If your only way to check an answer is to have an equally expensive model re-derive it, the asymmetry collapses and you are just paying twice.

Not everything is cleanly verifiable. NP is defined around problems with efficiently checkable certificates. A great deal of real work — open-ended writing, judgment calls, questions of taste — often lacks a cheap, objective checker. For those, generate-and-verify is weak exactly because there is no reliable P-style test to lean on. Code, maths, structured extraction, and anything with tests or a ground truth are where it shines.

A wrong verifier can be worse than no verifier. A checker that confidently accepts bad answers actively steers the search toward them. This is the failure mode behind naive “AI grades AI” setups, and it is why the reliability of the verifier, not just its cost, is what matters. A cheap check you cannot trust is a liability, not a saving.

If You’re Running This on AWS

Generate-and-verify maps directly onto how you compose models on Amazon Bedrock. Use a strong model as the generator, and put a cheaper, faster model or a deterministic check in the verifier seat: a smaller model scoring candidates, a schema or unit-test validation, or a tool call that confirms a fact against a system of record. Because the verifier is smaller and often runs fewer tokens, the loop can raise reliability without the cost of simply upgrading to a larger generator everywhere.

The building blocks are a mix of native model features and your own orchestration: model choice for the generator-versus-verifier split, and — where the selected model supports them — structured outputs and tool use for deterministic checks. The retry-against-a-cheap-judge-before-escalating loop is application logic you write around those calls, not a single platform switch. Treat that composability as the capability it is, check the current Bedrock documentation for which features a given model exposes, and remember the win is architectural rather than a product setting. As always, whether a given verifier earns its place is a measurement question against your task, your success criteria, and your latency budget, and the verifier has to be trustworthy on your data before you let it gate anything.

A thread worth pulling

The lightbulb from that university problem set has not dimmed. Solving is hard, checking is easy, and an enormous amount of practical AI engineering is figuring out how to lean on the cheap side of that gap: search more where it helps, check with something small and reliable, and loop. The discipline is the same one this series keeps returning to: name what is actually expensive, name what is actually cheap, and design around the difference rather than reaching reflexively for more of everything.

A companion post takes the idea one step further, into what happens when your “check” is not a separate verifier at all but a majority vote across several samples. For now, the question worth sitting with: in your own workflows, where is verification genuinely cheaper than generation, and are you spending your compute on the right half of that gap?

Sources

• [1] Stefan Christoph, “Why AI Tokens Are So Expensive — and What Actually Makes Them Cheaper” — where inference cost comes from, and why more search means more tokens.
• [2] Clay Mathematics Institute, “P vs NP” — the problem statement: easy to check versus easy to solve; formulated by Cook and Levin in 1971 and still unproven.
• [3] Snell et al., “Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters” — 2024; compute-optimal test-time search, and a smaller model with search outperforming a ~14× larger one on problems it can already sometimes solve.
• [4] Lightman et al., “Let’s Verify Step by Step” — 2023; a process-supervised verifier that checks each reasoning step improves reliability on hard maths.
• [5] Wang et al., “Self-Consistency Improves Chain of Thought Reasoning in Language Models” — 2022; the majority-vote-over-samples strategy explored in the companion post.

About the Author

Stefan Christoph is a Principal Solutions Architect at AWS, focused on agentic AI, media & entertainment, and helping builders move from demo to production. He writes about AI architecture, developer productivity, and the future of software.

This is a personal blog. Opinions expressed here are my own and do not represent the views or positions of my employer.

Learn more →

• AI
• LLMs
• AgenticAI
• Reasoning
• AmazonBedrock