Live data from Hacker News

Show HN: Formally verified 3D CSG: Trust 93 lines spec, not 1000 lines AI code

github.com

21–30 of 57 posts

Re: Show HN: Formally verified 3D CSG: Trust 93 lines spec, not 1000 lines AI code

#21
post #20

Honestly I think I'd have an easier time understanding 1000s of lines of slop than 93 lines of proofs lol. Does anyone have any recommended learning resources for this type of thing? Skimming the repo, it looks like a lot of unicode and math terminology, but this project seems really compelling to me.

I learned working with the Isabelle proof assistant in a university course. There were weekly exercises and a group project at the end. (Actually proving things by hand, no LLM.) That really helped. Before that course it was also hard for me to get into this.

Other than that you can also read introductory material for set theory. There the meaning of all of the unicode symbols you can see in the spec should be explained.

Re: Show HN: Formally verified 3D CSG: Trust 93 lines spec, not 1000 lines AI code

#23

> A human reviewer only needs to read 93 lines of formal specification and run the Lean checker to certify the correctness of the kernel, skipping the intricate 1000+ lines of AI-written implementation. To prove correctness, AI autonomously wrote over 60,000 lines of Lean proofs, which also never have to be inspected by a human. I am curious about the approach as I find claims like this hard to believe. There is a th…

Think of Lean proofs as a kind of inductive proof where if you trust the kernel then you trust every proof the kernel says is true.

Re: Show HN: Formally verified 3D CSG: Trust 93 lines spec, not 1000 lines AI code

#24

This seems like very cool work. I'm sorry if I missed it: I'm still not sure how we go from verified proof (Great!) to an implementation (by LLM or by Human) which you're sure actually conforms to the proof? How do we know that the implementation maps precisely to the description within the proof?

The code generation for Lean is not AFAIK verified in any way. It uses C as a portable assembler, and uses too many fancy C constructs to be compiled by CompCert C, which is the only fully verified compiler.

So you can have the strange situation of proof that the Lean code is correct, but no way of proving that the running machine code corresponds with the same program.

There is also the problem of knowing whether the microprocessor works according to its spec, and I don't think we have anything public about modern multi core processors about that.

Re: Show HN: Formally verified 3D CSG: Trust 93 lines spec, not 1000 lines AI code

#25
post #11

The issue I have with all these formally verified numerical algorithms is that, at the end of the day, I need this implemented using actual floating point. It's great that it's verified, but not for the case that is practically meaningful. Unless it's implemented using hardware accelerated floating point, most of these algorithms are not sufficiently performant to be practically useful.

There are plenty of proof systems that can handle floating point? The proof doesn't happen during execution...

Re: Show HN: Formally verified 3D CSG: Trust 93 lines spec, not 1000 lines AI code

#26

This seems like very cool work. I'm sorry if I missed it: I'm still not sure how we go from verified proof (Great!) to an implementation (by LLM or by Human) which you're sure actually conforms to the proof? How do we know that the implementation maps precisely to the description within the proof?

The code generation for Lean is not AFAIK verified in any way. It uses C as a portable assembler, and uses too many fancy C constructs to be compiled by CompCert C, which is the only fully verified compiler. So you can have the strange situation of proof that the Lean code is correct, but no way of proving that the running machine code corresponds with the same program. There is also the problem of knowing whether th…

Still, this is not a bad situation overall. If you are forced to trust the C compiler to correctly compile C, and the hardware to correctly implement the instructions in the documentation, well, you're already forced to trust both of those every day.

So this doesn't give you an absolute proof of correctness. But it does substantially reduce the size of the problem, which is now limited to (1) verifying that you actually proved what you think you did, and (2) all the stuff you were normally trusting anyway. (Some of the stuff you were trust anyway is broken, of course.) But this is a smaller problem than trusting 1,000 lines of highly-optimized CSG code written by a model we don't actually understand.

Re: Show HN: Formally verified 3D CSG: Trust 93 lines spec, not 1000 lines AI code

#27
post #12

> A human reviewer only needs to read 93 lines of formal specification and run the Lean checker to certify the correctness of the kernel, skipping the intricate 1000+ lines of AI-written implementation. To prove correctness, AI autonomously wrote over 60,000 lines of Lean proofs, which also never have to be inspected by a human. I am curious about the approach as I find claims like this hard to believe. There is a th…

Maybe what you mean is that kernels of proof assistants must be small. Here I am referring to a geometry processing kernel (that is formally verified by a proof assistant). The implementation of the algorithm can be very long, the proof that it conforms to the spec can be very long. But lean checks the proof. And so you only have to trust the spec and that the lean proof assistant is correct. In the 93 lines I assume…

What I’m wondering about is why we don’t need to understand/verify the generated kernel and only the spec?

Is there an implicit trust we must put in that kernel?

Re: Show HN: Formally verified 3D CSG: Trust 93 lines spec, not 1000 lines AI code

#28

> A human reviewer only needs to read 93 lines of formal specification and run the Lean checker to certify the correctness of the kernel, skipping the intricate 1000+ lines of AI-written implementation. To prove correctness, AI autonomously wrote over 60,000 lines of Lean proofs, which also never have to be inspected by a human. I am curious about the approach as I find claims like this hard to believe. There is a th…

Think of Lean proofs as a kind of inductive proof where if you trust the kernel then you trust every proof the kernel says is true.

Right, I’m thinking of the de Bruijin criterion applied to the generated kernel in this case. That generated kernel sounds large, and being generated, I’m curious as to why or how we don’t have to verify/understand it?

Re: Show HN: Formally verified 3D CSG: Trust 93 lines spec, not 1000 lines AI code

#30

This seems like very cool work. I'm sorry if I missed it: I'm still not sure how we go from verified proof (Great!) to an implementation (by LLM or by Human) which you're sure actually conforms to the proof? How do we know that the implementation maps precisely to the description within the proof?

I haven't actually used Lean or other proof assistants, so take this with a grain of salt, but I think the basic idea is to use (complicated) function argument and return types to "encode" the spec, and rely on the compiler's typechecking to detect spec violations.

To get the feel of this it might help to start with a simpler example: If you declare a function in ordinary old Java with return type int, the Java compiler will complain unless every path through that function returns either an int or something that can be converted to it (or throws). Lean is similar but uses a much more powerful type system called dependent types, which gives you extreme control over the values that are permitted in a type: For example, in Lean it's possible to define a type that consists of just the even integers, or even just the prime numbers. If you define such a PrimeNumber type, and then declare a function that returns a PrimeNumber, the Lean compiler will complain if the function could ever return a number that is not prime. IOW, if your function compiles with no errors, it is proven to always return a prime number.

I expect that OP's code defines a function named something like intersect(), and which takes 2 arguments of a type named something like Mesh, and returns not simply another Mesh but in fact a more complicated type: specifically, a Mesh that is somehow constrained to be a sub-mesh of each of the first and second arguments. Since mesh intersection is deterministic, I expect that this more complicated type will turn out to be inhabited by just a single value (mesh) -- similar to a type FortyTwo whose only value value is the integer 42. (I'm assuming here that a mesh can only be represented in one canonical way; this might not be true.) Then, Lean will complain at compile time if there exists any conceivable pair of input meshes for which the function would construct the wrong intersection.

Post reply on HN