acceptodds
Under review as a conference paper at ICLR 2027

From Mathematical to Executable Certificates for Machine Unlearning

Abstract

Machine unlearning is needed when data must be removed because of deletion requests, outdated records, or data-quality concerns, while retraining from scratch can be costly. Certified machine unlearning methods provide mathematical guarantees, while deployed systems release concrete finite-precision artifacts produced by software. To bridge the gap between mathematical guarantees and practical deployment, we introduce Executable Release Certification (**ExecCert**), a release-time layer that certifies the candidate artifact considered for release. ExecCert either closes a method's native certificate for the executed candidate or applies Retraining-Reference Release Verification (**RRV**) to certify fidelity to current retain-set retraining. Sequential deletion makes the latter nontrivial because the exact retain-set reference and the stored numerical state evolve separately. For frozen representations with a mutable ridge head, we develop an incremental realization of **RRV** that maintains certified evidence across deletion requests rather than reconstructing it at each release. On four published unlearning implementations, **ExecCert** preserves valid certificates, changes release decisions, tightens conservative bounds, and identifies the retraining-reference fidelity supported by concrete outputs. In sequential-service experiments, **RRV** eliminates false releases caused by stored-equation verification while closely tracking realized error, and incremental certification remains cheaper than both fresh and maintained verified-factor alternatives once release checks become sufficiently frequent.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Machine Unlearning, Certified Machine Learning, Formal Verification, Numerical Certification, Sequential Deletion

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_HVwuOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

Machine unlearning often uses approximate updates to avoid the cost of retraining a model after data deletion. However, executing these updates in finite-precision arithmetic introduces rounding and quantization errors that can undermine guarantees derived in exact arithmetic. This paper proposes ExecCert, a release-time verification framework that checks whether the actual unlearned model satisfies either the original method’s certificate or a specified accuracy requirement relative to retraining, without explicitly computing the exact retrained model. For sequential deletions, the authors develop Incremental RRV for ridge-regression heads on frozen representations, maintaining certified bounds on accumulated numerical errors and approximate-inverse accuracy with O(d2)O(d^2) work per deletion, where (d)(d) is the feature dimension. Experiments on four published unlearning implementations and sequential deletion services evaluate how certification affects release decisions, the tightness of error bounds, verification costs, and the feasibility of satisfying requirements under different numerical precisions.

Critical strengths
  1. As machine unlearning moves toward practical deployment, reliable certification becomes increasingly important. In this direction, this work addresses this need by checking whether numerical errors in the executed updates undermine the intended guarantees.
  2. For ridge heads on frozen representations, Incremental RRV maintains certified numerical evidence and reduces verification costs when release checks are sufficiently frequent.
Critical weaknesses
  1. The paper certifies linear prediction scores on a fixed, predefined set of representations, but does not establish corresponding guarantees for general trainable neural networks or generalization guarantees for unseen inputs. Also, the experiments do not demonstrate that the chosen numerical tolerances correspond to a meaningful level of resistance to recovering deleted information under the practical settings. This restricts the interpretation of the certificates as evidence of successful unlearning.

  2. The incremental method targets a frozen feature extractor with a trainable ridge-regression head. The additional gradient-based certificate requires strong convexity which general neural network training does not ordinarily satisfy even with adding a proper regularization term. Extending the analysis and evaluation to trainable feature extractors or nonconvex objectives would substantially strengthen the contribution.

  3. Standard certified-removal definitions compare the distributions of models produced by unlearning and retraining, limiting an observer’s ability to distinguish between them. RRV instead bounds the distance between a particular executed candidate and a specified retraining reference. This bound alone does not establish distributional indistinguishability.

  4. The incremental method maintains dense matrices with O(d2)O(d^2) storage and can require O(d3)O(d^3) rebuilding, where dd is the feature dimension. Its the FP32 stress experiment shows lower certification coverage, greater total processing time, and higher memory use than fresh verification. These results limit the generality of the efficiency claims. Experiments across larger feature dimensions, longer deletion sequences, and different levels of numerical sensitivity would help establish when incremental verification is beneficial. Demonstrating applicability to larger trainable components would require additional methodological development beyond the current ridge-head implementation.

Questions for authors
  1. What additional assumptions would be needed to extend RRV to trainable feature extractors and nonconvex neural networks?
  2. Can RRV be extended to certify approximate indistinguishability between the output distributions of the unlearned and retrained models on unseen inputs? What additional assumptions would this require?
Reviewer_7161OpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The manuscript introduces Executable Release Certification (ExecCert), a release-time layer designed to bridge the gap between mathematical unlearning guarantees and the actual finite-precision artifacts produced by deployed software. ExecCert operates through two primary paths: native closure, which rigorously encloses a method's existing certificate quantity, and Retraining-Reference Release Verification (RRV), which certifies the candidate's fidelity to current retain-set retraining. To address the complexities of sequential deletion—where the exact retain-set reference and the stored numerical state inevitably diverge—the authors develop Incremental RRV. For frozen representations utilizing a mutable ridge regression head, this method maintains a certified numerical state across deletion requests via O(d2)O(d^2) rank-one transitions, circumventing the need to reconstruct evidence at each release. Validation across four published unlearning implementations demonstrates that ExecCert can preserve valid certificates, alter release decisions, tighten conservative bounds, and accurately identify the retraining-reference fidelity supported by concrete outputs.

Critical strengths
  1. Practical Problem Identification and System-Level Integration The manuscript successfully highlights a critical, often-overlooked vulnerability in current machine unlearning deployments: the discrepancy between mathematical guarantees derived in exact arithmetic and the finite-precision artifacts executing those updates. By formalizing executable certification as a distinct layer situated between the unlearning mechanism and the policy gate, the authors provide a structurally sound framework for preventing the false releases that are routinely admitted by standard stored-equation checks. This is highly consequential to the overall assessment, as identifying and addressing numerical drift in sequential deletions is essential for safe, compliant real-world AI deployment.

  2. Computational Efficiency in Sequential Deletion The proposed Incremental RRV offers a highly efficient mechanism for managing continuous unlearning requests. By actively tracking the discrepancy between finite-precision statistics and exact retain-set statistics through guarded rank-one transitions, the method cleverly avoids the O(d3)O(d^3) cost associated with dense inverse reconstruction at every step. This optimization is highly consequential; experiments demonstrate that Incremental RRV remains significantly cheaper than both fresh and maintained verified-factor alternatives once release checks become sufficiently frequent, strongly supporting the method's practical viability for production environments.

Critical weaknesses
  1. Limited Algorithmic and Theoretical Novelty The core premise of addressing finite-precision numerical errors relies heavily on a well-established paradigm within verified numerics. The application of standard rigorous enclosures for linear-system residuals and low-rank updates to machine unlearning is straightforward. While the systemic adaptation to sequential unlearning is practically useful, the theoretical novelty of the ExecCert methodology itself is inherently limited when compared to existing verified numerical methods that manage approximate inverses and Cholesky downdates. This restricts the manuscript's broader theoretical contribution to the field.

  2. Restrictive Scope and Lack of Generalizability The proposed RRV mechanisms restrictively rely on assumptions of linearity and strong convexity. Specifically, the incremental realization is limited to ridge regression heads with symmetric positive-definite normal matrices, while the post-update constructions apply only to differentiable strongly convex heads. Although the authors evaluate a large language model, the unlearning is strictly isolated to a binary ridge head operating on completely frozen representations. Given the current trajectory of AI toward fully fine-tuned, complex, and non-convex architectures (such as state-space models, MoE, and standard LLM fine-tuning), the failure to investigate or adequately discuss how this method can be extended beyond simple convex layers makes the contribution somewhat marginal for modern deep learning practitioners.

Questions for authors

How can the proposed Incremental RRV framework be extended beyond frozen representations with mutable ridge heads to accommodate fully fine-tuned, non-convex architectures, which represent the standard for modern deep learning deployments?

Could you clarify the specific algorithmic or theoretical advancements ExecCert offers over classical verified numerics techniques (e.g., standard iterative refinement and classical residual enclosures), aside from its domain application to sequential unlearning?

Reviewer_dscwOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes ExecCert to measure the gap between theoretical guarantees in machine unlearning and the actual execution, caused by the finite-precision execution in MU. Given an unlearned model, ExecCert verifies whether this model satisfies the certification requirements in the unlearning algorithm by using native-certificate closure or retraining-reference release verification. Moreover, the paper introduces incremental RRV to address sequential unlearnings.

Critical strengths
  1. The gap between theoretical guarantees in machine unlearning and the actual execution is a practical and important question to study.
  2. There are extensive mathematical analysis in this paper, such as certified error bounds.
  3. Experiments show that ExecCert helps prevent false releases with a lower verification costs.
Critical weaknesses
  1. The effectiveness of incremental RRV seems concerning with 67.24% coverage, comparing to 99.97% in on-demand RRV.
  2. It seems that incremental certification relies on ridge regression with positive-definite matrices. I’m not sure how this is applied to non-convex neural networks.
  3. The reconstruction mechanism may have to revisit retained data and introduce non trivial computation overhead. It could be helpful to discuss how frequent this reconstruction could be.
Questions for authors

Please see the weaknesses.

Reviewer_t6ZNOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses a critical gap in certified machine unlearning: while existing theoretical literature provides mathematical guarantees relating efficient deletion algorithms to retraining from scratch, deployed systems execute software in finite-precision floating-point arithmetic. Consequently, rounding errors, numerical drift, and sequential updates can cause a deployed model artifact to violate its intended certification contract, even if it accurately solves the stored computer equation. To bridge this gap, the authors introduce ExecCert (Executable Release Certification), a release-time verification layer supporting two pathways:

  1. Native-Certificate Closure: Rigorously encloses a method's native certificate quantity for the executed finite-precision candidate.
  2. Retraining-Reference Release Verification (RRV): Certifies candidate fidelity directly against an exact-real retraining reference (θR\theta^R). For sequential deletion in ridge regression heads (and frozen representations with mutable linear heads, such as 3B LLM safety alignment heads), the paper develops Incremental RRV, which maintains certified numerical bounds and inverse-defect evidence via guarded Sherman-Morrison rank-one updates in O(d2)O(d^2) work.2.
Critical strengths

1.Identifying and closing the gap between exact mathematical proofs and finite-precision software artifacts is a vital and largely neglected problem in trustworthy machine learning.

  1. The paper exploits established techniques from verified numerical linear algebra (interval arithmetic, outward rounding, Krawczyk/Oishi-Rump style residual and inverse-defect enclosures) instead of heuristic approximations.

3.The experiments span four published unlearning methods, controlled synthetic and benchmark datasets, and large-scale frozen representations (Llama-3.2-3B-Instruct safety heads), showing that ExecCert catches false releases and amortizes verification costs.

Critical weaknesses
  1. The core machinery of Incremental RRV maintains exact inverse-defect bounds, approximate inverses P∈Rd×dP \in \mathbb{R}^{d \times d}, and rank-one Sherman-Morrison updates. This is strictly restricted to linear or convex quadratic heads (ridge regression / strongly convex models). It does not scale to full end-to-end deep neural networks where parameter dimensions (dd) scale to millions or billions, and objectives are highly non-convex. This limitation is fundamentally unfixable in the current technical framework. Storing and updating a dense d×dd \times d inverse proof state requires O(d2)O(d^2) memory and O(d3)O(d^3) rebuild costs, making it computationally prohibitive for modern deep neural networks.

  2. The error-centered readout certificates (Proposition 1) and decision-agreement guarantees (Corollary 1) require input representations ZZ to be predeclared independently of the candidate. If a deployed system requires certifying model behavior on streaming, non-stationary, or adaptive user queries that cannot be anticipated beforehand, fixed-readout verification breaks down. The authors should explicitly discuss how ZZ should be constructed in practice (e.g., representative calibration sets or bounding box approximations) and clearly state this boundary in the main text.

  3. The lifetime of the incremental proof state is instance-dependent and governed by matrix conditioning (κ(Ht)\kappa(H_t)). Under ill-conditioned deletion sequences or adversarial request patterns, accumulated rounding errors or proximity to singularity will trigger guard failures, forcing fallback rebuilds (O(ntd2)O(n_t d^2) from retained rows or O(d3)O(d^3) dense factorization). The authors should include a dedicated sensitivity analysis or stress test quantifying how matrix condition numbers correlate with guard failure rates and recovery overhead across various deletion distributions.

Questions for authors

See weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.