I would like to think that pg_hint_plan is designed in such a way that any hint it accepts must be a valid plan for the query. I’m quite confident that schemes with this property that can also express high quality plans are possible and not even excessively complicated.

This is not to say that it’s possible to genetically verify that a proposed algorithm does what you want it to — that would be undecidable or NP-hard or co-NP-hard depending on how you formulate the question.

`pg_hint_plan` has a debug log so you can verify Postgres actually used the hint or not! Used this during evaluations

You're misunderstanding the setup here. The LLM doesn't modify the query, just some details about how to choose between different ways to break the query into basic operations on the tables. The SQL doesn't change. It's still up to postgres to guarantee that the results match the query. If the proposed plan were nonsense that didn't amount to carrying out the query, postgres would ignore it.

I imagine you can perform operations on query plans to transform them and determine equivalence?

you'll have to prove equivalence through some Lean4 code perhaps? or some weird clause tree comparisons... good question indeed.

Because P!=NP (very probably IMHO) there's a huge class of problem for which LLMs are useful on the expensive and heuristic-y generation side because the verification is relatively inexpensive.

"... make no mistakes" :)