Checkpoint-replay verification of a training run is not merely buggy: making it provably robust reduces to open problems in learning theory, and spoofing already forges valid logs cheaply. The only floor that does not rest on unsolved theory is a zero-knowledge proof of training.
A model owner releases a set of weights and makes a claim about them: these are the genuine result of training, on this data, by this procedure. Someone has to check that claim — two parties contest who trained the model and ownership turns on it, or a distributed-training pool pays workers per update and needs to know the updates are real. Either way the question is the same: how do you verify that a training run happened as claimed, when re-running the whole thing yourself is the expensive computation you were trying to avoid?
There is a cheap, popular answer most teams reach for. Have the trainer log checkpoints along the way; have the verifier pick a few segments, re-derive a handful of optimizer steps from one logged checkpoint, and confirm they land on the next. No exotic cryptography, no proving system — just a spot-check that the claimed path through weight-space is one gradient descent could have walked. This is Proof-of-Learning, and its original pitch was that forging such a log is no cheaper than training the model honestly.
That pitch is false, and the way it is false is the subject of this post. The checkpoint-replay verifier is not merely buggy — buggy implies a fix exists. The result that matters is sharper: making this verification provably robust reduces to open problems in optimization and learning theory, while reproducible spoofing already forges valid logs for a fraction of honest training cost. So the non-cryptographic verifier is unfixable in a precise, load-bearing sense, the only training-integrity guarantee that does not depend on an unsolved theory question is a zero-knowledge proof of training, and that cryptographic floor has a price worth stating.
What Proof-of-Learning is, stated by its authors, is the whole story, because of the design choice it makes. Proof-of-Learning: Definitions and Practice (arXiv 2103.05633) introduces the scheme on an observation about stochastic gradient descent itself: the authors “observe how a seminal training algorithm, stochastic gradient descent, accumulates secret information due to its stochasticity,” and argue that “this produces a natural construction for a proof-of-learning which demonstrates that a party has expended the compute require to obtain a set of model parameters correctly.” The trainer’s random path through weight-space encodes information an imitator does not have, so a verifier who re-derives a few steps from the logged checkpoints can be convinced the path was really walked.
The design is deliberately non-cryptographic, and that is not an accident to be patched — it is the point. The follow-up analysis in Proof-of-Learning is Currently More Broken Than You Think (arXiv 2208.03567) states the trade in one line: the authors of PoL “forego cryptographic approaches and trade rigorous security guarantees for scalability to deep learning.” You give up a proof, you get something that scales to a real deep network, and you lean on the hope that an honest re-derivation is hard to fake.
The security claim that justifies the trade is precisely the claim that later breaks. The original paper asserts that “an adversary seeking to illegitimately manufacture a proof-of-learning needs to perform at least as much work than is needed for gradient descent itself.” If that held, the scheme would be enough: a rational adversary facing a forging cost as high as honest training would simply train. Everything downstream depends on that inequality being true.
And this is not a toy target. Proof-of-Learning was pitched for exactly the high-stakes integrity uses that make verification worth doing: the original paper says it “would simplify ownership resolution when multiple parties contest ownership of a specific model,” and “would also facilitate the distributed training across untrusted workers where Byzantine workers might otherwise mount a denial-of-service by returning incorrect model updates.” Ownership of released weights and Byzantine-resistant distributed training are real problems with real money attached. An unverifiable Proof-of-Learning is a gap in production-relevant infrastructure, not an academic footnote.
The inequality does not hold. The same paper, Proof-of-Learning is Currently More Broken Than You Think (arXiv 2208.03567), is blunt about the status of the original empirical argument: the authors “empirically argued the benefit of this approach by showing how spoofing — computing a proof for a stolen model — is as expensive as obtaining the proof honestly by training the model. However, recent work has provided a counter-example and thus has invalidated this observation.” The “spoofing is as expensive as training” claim — the one thing holding the scheme up — was already counter-exampled before this paper even began.
What this paper adds is worse for the scheme, because it removes the escape hatch of “that one attack was a special case.” Earlier spoofs could be dismissed as brittle — tuned to one verification setting, breakable by changing the verifier’s parameters. This work closes that door, introducing “the first spoofing strategies that can be reproduced across different configurations of the PoL verification and can be done for a fraction of the cost of previous spoofing strategies.” Two words carry the weight. Reproduced: the spoof survives the verifier changing its checks. Fraction: forging a valid log costs materially less than honest training, the exact inverse of the security claim the scheme was sold on.
Put those together: an adversary holding a stolen set of weights manufactures a checkpoint log, the verifier re-derives its sampled segments, they check out, and the log is a fabrication produced for less than the cost of training. The thing the scheme exists to prevent is cheaper than doing the run honestly. This is not a tail bug; it is the central guarantee, inverted.
The natural engineering reflex is to harden the verifier. Sample more segments. Check more steps per segment. Add cleverer consistency tests between checkpoints. That reflex fails permanently, not until the next patch, and the reason is the load-bearing result.
Proof-of-Learning is Currently More Broken Than You Think (arXiv 2208.03567) does not just exhibit a better attack; it characterizes what a robust verifier would need and shows that need is unmet theory. To make the verification provably robust, you have to assume things about how SGD moves through weight-space — that an honestly-trained trajectory is distinguishable, in a checkable way, from a cheaply-fabricated one. The paper’s finding is that “realizing these assumptions reduces to open problems in learning theory.” The properties a robust verifier depends on are open questions about optimization in deep learning, not yet known to be true.
The authors state the conclusion plainly: “one cannot develop a provably robust PoL verification mechanism without further understanding of optimization in deep learning.” The robustness of the cheap verifier is not blocked by an unwritten patch or an unfound parameter setting; it is blocked by an unsolved problem in learning theory. Until someone advances the theory of how gradient descent traverses loss landscapes, there is no checkpoint-replay verifier with a robustness proof — only verifiers that have not yet been spoofed in the configuration you happened to test.
This is the difference between “buggy” and “unfixable.” A buggy scheme has a fix in reach; Proof-of-Learning’s defect is that the assumptions its robustness would require are themselves open theory, and you cannot ship around an open problem. Every hardening you can build — more segments, more steps, cleverer checks — raises the spoofing cost without reaching a proof. That is the non-cryptographic verifier as a floor that is not a floor: it can be made harder, never sound.
If the cheap verifier’s soundness is gated on learning theory, the way out is a verification whose soundness is gated on cryptography instead — something whose security argument does not route through any claim about how SGD behaves. That object exists, and it is its own first-class task: the zero-knowledge proof of training. The survey A Survey of Zero-Knowledge Proof Based Verifiable Machine Learning (arXiv 2502.18535) sets out to “organize existing studies into three core tasks: verifiable training, verifiable testing, and verifiable inference” — verifiable training distinct from the inference-proving that gets the attention, not a stretch of it. And ZKPs “allow one party to certify that a training, testing, or inference result was produced by the claimed computation without revealing sensitive data or proprietary model parameters”: certify that the computation produced the result, without re-executing it and without seeing the model or the data — exactly the property a checkpoint-replay verifier cannot offer.
Zero-Knowledge Proofs of Training for Deep Neural Networks (the Kaizen system, CCS 2024) states the strong version of the claim: a zero-knowledge proof of training “enables a party to prove that they have correctly trained a committed model based on a committed dataset without revealing any additional information about the model or the dataset.” Nobody re-derives an optimizer step, and nobody assumes anything about the shape of the loss landscape — soundness comes from the proof system, full stop. There is no open learning-theory question standing between this verifier and its guarantee, and that is the entire reason it is the floor.
Crucially, this is demonstrably real and not a whiteboard hope. Kaizen “can handle the training of complex models such as VGG-11 with 10 million parameters and batch size 16, with a proof size of 1.63 megabytes and verifier runtime of only 130 milliseconds, where both are independent of the number of iterations and the size of the dataset.” Ten million parameters is a genuine network, not a linear probe, and the succinctness is the property a verifier needs: a 130-millisecond check settles the claim whether the run was a thousand steps or a million — a verification you can actually deploy, with a guarantee that does not rest on theory nobody has finished.
A floor sold as free loses the reader who knows the field, so state plainly where this one is expensive and where it stops short.
The cost is the prover, and it is steep today. Kaizen’s own numbers say so: the “prover runtime is 15 minutes per iteration, which is 24x faster than generic recursive proofs, with prover memory overhead 27x lower.” Fifteen minutes per training iteration is enormous — a real run is many thousands of iterations, which puts proving a full modern training run far outside routine practice. The 24× and 27× figures tell you the engineering is moving fast, and that a large speedup over the generic baseline still lands at fifteen minutes a step. But the bottleneck is prover cost, not soundness — the open engineering problem, in contrast to the open theory problem that gates the cheap verifier. It is the same impossible-to-expensive shift that moved proving a transformer’s inference from a research aspiration to a cost line: expensive is a problem you engineer down; a theory gate is not.
The survey corroborates that the blockers are economic, not foundational. A Survey of Zero-Knowledge Proof Based Verifiable Machine Learning (arXiv 2502.18535) names “the main implementation bottlenecks, including limited circuit expressiveness, high proving cost, and deployment complexity” — costs, not soundness gaps. The floor is real and priced, not free.
Two more qualifications keep the claim from overstating.
First, the cheap verifier is not worthless — it is just not a floor. A spot-checking scheme raises the cost of a careless forger and is a reasonable speed bump where the threat is low and the stakes are modest. The claim is not “checkpoint replay catches nothing,” but that it has no robustness proof, its central inequality is already inverted, and it cannot be made sound without advancing theory — so it cannot be what a high-stakes system rests on.
Second, non-cryptographic training verification has a stronger branch than vanilla Proof-of-Learning, and even it treats PoL spoofing as the adversary to beat. Tools for Verifying Neural Models’ Training Data (arXiv 2307.00682) introduces Proof-of-Training-Data and reports that its “verification procedures can catch a wide variety of attacks, including all known attacks from the Proof-of-Learning literature” — benchmarking against PoL’s spoofs is itself the tell that their spoofability is the accepted baseline problem. But the scheme leans on “a method for the model-trainer to verifiably pre-commit to a random seed used in training, and a method that exploits models’ tendency to temporarily overfit to training data in order to detect whether a given data-point was included in training.” A seed pre-commitment and an overfitting signal are heuristics — empirically strong against today’s attacks, still not a proof, their soundness measured rather than proven. Stronger speed bump, same category.
You cannot get a checkpoint-replay verifier and a robustness proof at once, because the proof is gated on open theory. You can choose deliberately and name what your guarantee rests on.
Match the guarantee to the stakes, and name what its soundness depends on. Proof-of-Learning is a heuristic whose central security claim is already inverted and whose robustness is gated on unsolved learning theory; treat it as a low-stakes speed bump, not as what a contested-ownership case or a paid distributed-training pool rests on. A zero-knowledge proof of training is the only guarantee whose soundness routes through cryptography rather than a claim about SGD’s behavior — reserve it for where its cost is survivable.
Do not confuse “harder to spoof” with “sound.” If a design’s safety argument is “we sample enough that spoofing is impractical,” it is a heuristic argument — and reproducible spoofing for a fraction of honest cost is the published evidence it does not hold across the configurations an attacker can choose.
Price the cryptographic floor as a prover-cost problem, on your own model. Fifteen minutes per iteration is the published per-step figure for a ten-million-parameter network, and total proving cost scales with iteration count — so the floor is reachable for small, fixed models in high-assurance, low-frequency settings, and out of reach for routinely proving a frontier-scale run today. It is the same small-and-fixed, high-stakes shape where the cryptographic option already pays for itself: the cost is engineering, not soundness, and it falls with better systems work — the opposite of the learning-theory gate the cheap verifier waits on.
Separate the training-integrity question from the inference-integrity one. Verifying a model was trained as claimed is a different and harder problem than verifying a deployed model ran as claimed — the verifiable-inference decision between cryptographic and game-theoretic finality is about re-running an output, while training verification is a provable-unverifiability problem for the non-cryptographic verifier. Decide which property a stakeholder actually needs before reaching for a scheme.
You cannot check that someone trained a model by replaying their checkpoints, and the reason is not that the replay is buggy. Its security claim is already inverted by spoofs that reproduce across configurations for a fraction of honest cost, and making it provably robust waits on an open optimization-theory question no patch can close. The only training-integrity guarantee that does not depend on an unsolved learning-theory question is a zero-knowledge proof of training — expensive at fifteen minutes a step today, gated on prover cost rather than soundness, and real enough to settle a ten-million-parameter run in a 130-millisecond check. Choose the heuristic for the low-stakes speed bump if you like. Just do not call it a floor, because the floor is the proof.
A membership-inference attack that separates your book from a held-out one is usually reading the calendar, not the weights. A successful attack is not a sound proof — and the null it would need to test against cannot be sampled.
17 min →
Unlearning promises a model can forget specific data without a full retrain. What it delivers is output suppression: a small benign relearning set — or simply quantizing the model — brings the 'forgotten' knowledge back.
14 min →
The EU AI Act requires AI output to be marked in a robust, reliable way. A formal impossibility theorem says strong watermarking cannot exist. Five words in the statute carry the collision.
13 min →