Context first. I make tasks for an evaluation using a frontier model (GPT-class; high reasoning effort; hard 8-hour wall clock; 2 CPUs; 6GB RAM) inside a Lake project that has a single sorry in Main.lean. The goal of the model is to close it. sorry, axiom, native_decide, and all other members of that family are prohibited. After the model completes, the verifier copies the one file into a new project, rebuilds it, runs #print axioms, and then plays back the olean through leanchecker. A task will count toward the benchmark only if the model fails at least one of two runs.
Here's my problem: the model is too good. Every "prove this theorem" task I have made so far has been successfully completed by the model, including one in just 17 minutes. It produces roughly 2,000 lines of verified Lean per hour, and if Mathlib has a related theory, it finds it and uses it.
At present, my best option is the chromatic number of the Kneser graph KG(11,4), which is exactly 5. An upper bound is an explicit coloring; nothing complicated about that. A lower bound needs Lovász, which needs either Borsuk-Ulam or Tucker, and neither of those are available in Mathlib. KG(11,4) also has a fractional chromatic number of 11/4, so there is no small subgraph that can be used to force five colors. What is left is computational: 4-colorability as a SAT instance with 1,320 variables. CaDiCaL refutes it in 0.2 seconds and the LRAT proof is approximately 3,600 steps.
The challenge is getting the kernel to recognize that certificate. I built my own reference, and it took considerable effort. I wrote a bitmask RUP checker with a soundness proof, decoded the original clauses arithmetically from their IDs instead of keeping them, stored the learned clauses in a literal trie, and broke down the certificate into approximately 300 small theorems, since each reduction done by the kernel consumes approximately 17KB and frees nothing during a single theorem. A single-theorem implementation ate up all available RAM and crashed. I also had to use -DElab.async=false because async elaboration keeps around approximately 42MB per kernel-checked theorem until the end of the file. It took approximately 32 minutes to compile on a laptop.
Two fresh agents saw exactly what the model would see and both failed within five hours. One attempted to go the certificate route and its kernel check never finished (the kernel was swapping and the agent interpreted that as slow). The second proved the upper bound and reduced the lower bound to the octahedral Tucker lemma before giving up.
Questions, mostly for those who know the kernel better than I do:
- Is there any way to get a certificate like this to be cheap in the kernel? Maybe Nat.ble on large literals, maybe some sort of reflective setup I don't know about, something that enables an agent to skip the chunking work. I'd prefer to find out now rather than after the evaluation.
- Does Mathlib have anything similar to Borsuk-Ulam for S^3, or a Tucker lemma development I cannot find? In the past I thought "not in Mathlib" and an agent found covering space lifting and proved the S^2 case in 36 minutes.
- Is there a more elegant way to break up a certificate across multiple theorems than what I did (hints per theorem, manually adjusted)?
- For those working on large language models: When one of these models gets an OOM kill during a long kernel check, does it examine the memory model and alter its strategy, or does it continue trying the same thing with slight changes? I'm thinking about either going to KG(12,4) or putting two instances together in one file so that it uses up all its iterations.
I'm not looking for help solving this; it's already solved. I just want to know whether the barrier exists or whether I'm about to be humiliated. If posting my checker design in the comments will assist, I'm happy to do that.