2B training at 1.19x overhead: Witnesses lets trainers prove exactly what data they used

Training Witnesses: Trusting the Training without Trusting the Trainer

Houjun Liu, Pratyusha Sharma

cs.LG, cs.CR

2026-09-28

Witnesses attests LLM training with per-step parameter sketches plus 1% random replay challenges: 1.19x overhead at 2B scale, near-certain detection of poisoning-level data attacks.

What problem this solves

ICLR received 60,000 submissions this year; nobody is reproducing more than a sliver of them. A paper claims a model was trained on dataset D and reached score S, and the reader can either trust it or spend hundreds of thousands of dollars retraining. That burden has sat with the reader, and pretraining made it hopeless. The three existing technical routes all fail: zkSNARK-based proofs of training (zkDL) need close to a second per update on a 10M-parameter model; statistical provenance (Choi et al., 2023) reads memorization traces, so it can show "X was used" but misses undeclared additions; probabilistic audits (Madrigal-Cianci & Chordia, 2026) require frequent checkpointing and replay, expensive for both trainer and verifier. Most are also welded to specific training topologies. This paper flips the burden of proof: the trainer generates a cheap cryptographic certificate during training, any third party can check it at low cost, and the certificate commits only a hash of the training code, so the training technique itself stays private.

Method

Witnesss, the system, writes a record on every training step to an append-only, per-record-signed tape. Each record commits three things: a sketch of the parameters before the update, a sketch after, and a hash of the data batch. Optimizer state is bound with a separate multi-round hash so adjacent records stay continuous and cannot be swapped mid-run.

Three design choices carry the protocol:

• Geometric parameter sketch. Every weight matrix is multiplied by fixed random orthonormal matrices, and the projection is hashed onto the tape. The math is the point: random orthonormal projections are almost surely full spark (every column subset is linearly independent), so an edit that evades the sketch cannot be sparse; it must touch at least l+1 coordinates. Non-sparse edits are exactly what random sampling catches. A cheater is squeezed from both sides: edit sparsely and the sketch catches it, edit densely and the replay challenge does. The step is cheap enough to run at every gradient update.
• Data commitments. Each batch gets a cryptographic hash (making sampling unpredictable with respect to the data) plus a Karp-style rolling hash (letting verifiers match arbitrary fragments). Together they answer both "was sample X used" and "was sample X truly withheld", the latter being beyond statistical methods.
• Random replay challenges. Each step is challenged with probability 1%; a challenged step is replayed in place with the committed update function and the states are compared. Which steps get challenged is derived from the hash chain itself, so the trainer cannot steer cheating away from challenged steps. Replay is feasible because Jax and Torch accelerator compilations are already stateless; the lowered program is extracted and serialized directly.

Engineering adds selective optimizer-state offloading (ZeRO-Offload spirit) overlapped with communication, plus a pipelined Python driver and Rust worker. The root of trust is a white-box-cryptographic obfuscated VM that measures the rest of the system and derives keys.

Results

Performance is best in communication-bound sharded settings, where copies hide under communication:

Detection was evaluated adversarially at 100M parameters with the check rate fixed at 1%:

• Substitution, addition, and removal attacks are all detected with probability near 1 whenever the volume reaches meaningful-poisoning levels, and empirical rates track the theoretical estimate closely. Choi's statistical method largely fails on data addition; Madrigal-Cianci has lower detection at far higher training cost (Fig. 7 shows per-step time on one GPU at 100M, with Witnesses clearly below Madrigal-Cianci; no cost-matched head-to-head table is given).
• Uniformly corrupted parameters are detected with near certainty.
• The strongest experiment: an attacker holding the public sketch vectors runs AdamW in the sketch nullspace while constraining KL on the training distribution. Every attempted point is still caught by the sketch at float32 precision; pushing sketch error down also pushes malicious-sample KL down, collapsing the model toward the training distribution.

Verification is streamable: the certificate costs roughly twenty bytes per token, verification runs at hundreds of microseconds per token, and the verifier's resident memory stays constant around 200 MiB regardless of certificate length.

Why it matters

Pretraining baselines have lived in an each-paper-its-own-world regime, with data, order, and undeclared interventions all opaque. This work offers an affordable credential: the trainer pays 1.19x and any third party can query sample inclusion and exclusion without retraining. For open-weight releases it is a way to prove no stolen data; for compliance (test-set contamination, copyrighted corpora, privacy exclusions) it is the first mechanism answering both inclusion and exclusion queries. A leaderboard (dvbench.org) packages the credential into a public, verifiable submission format. The cold water: this is infrastructure whose value scales with adoption, 2B is two to three orders of magnitude short of frontier runs, and "immediately applicable at academic and open-weight scales" is the authors' own boundary.

Limitations

Author-acknowledged: only the training process is covered; evaluation procedures are attested by serialization but the leaderboard explicitly does not verify the scoring code, so leaderboards can still be gamed on the evaluation side. No claims are made about the initial state θ0 (to keep fine-tuning support), with the assumption that anything smuggled there is visible by inspection. Soundness is probabilistic, with the nonce and the 1% check rate as the grind barrier; the authors estimate an attacker needs on average 100 full training runs to luck into one passing sample.

Open questions: the root of trust is a white-box obfuscated VM, and "cannot be reverse-engineered or forged" is an engineering assumption, not a provable property. White-box cryptography has a long record of published breaks, and only the zkVM route carries the formal guarantees; the paper picks white-box for speed. The 1.47x DDP overhead shows 1.19x is a sharded-setting optimum, not a universal bound. The evaluation covers dense GPT models under DDP/FSDP/TP at 100M-2B; messier real pipelines (RLHF, multi-stage training) are untouched.

Terms

• zkSNARK: succinct non-interactive zero-knowledge proof; proves a computation was done correctly without revealing inputs, at very high proving cost
• PoTD (Proof of Training Data): family of protocols proving a model was trained on claimed data
• Full spark: property of a matrix where every subset of min(rows, cols) columns is linearly independent, so sparse edits cannot hide in the projection nullspace
• Rolling hash: Karp-Rabin style hash computed over a sliding window; matches arbitrary fragments in a stream
• White-box cryptography: hides keys inside obfuscated code under the assumption that an attacker seeing the full implementation still cannot extract them
• DDP/FSDP: two PyTorch distributed training strategies; DDP replicates parameters per rank, FSDP shards them

Source

• arXiv 2609.33915v1
• PDF
• Hugging Face

What people are saying

• Stanford's Training Witnesses: certify ML training runs without trusting the trainer pratyusha_PS

Related papers

• Retrospective distillation lifts Qwen3-14B on ScienceWorld by 59.7% relative
• Qwen3-8B hits 41.5% exact-match tool selection, beating 402B Maverick
• DeepMind fixes two numerical bugs in softmax and cross-entropy, eliminating Slingshot loss spikes
• Unsupervised partner D rises from 61.3% to 85.5% when JEPA reconstructs only C
• GPT-5.6-sol edge kernels: 64.5% correct, only 25.5% faster than tuned TVM
• Subspace Tuning freezes 99% of each weight matrix's spectrum: forgetting drops from 57 points to ~1

All paper explainers