acceptodds
Under review as a conference paper at ICLR 2027

Deciding Response-Update Feasibility from Incomplete Covariance Information

Abstract

Updating a model under explicit response budgets requires deciding whether a requested change can be fitted without excessive interference or update size. A compact covariance sketch makes this decision depend on retained information as well as on the request. We develop a three-way feasibility interface for fixed features at one linear projection. A realizable Frequent Directions construction gives identical sketches, shrink values and residual traces with opposite answers to the same request. Given additional covariance-vector actions, classical positive semidefinite (PSD) interpolation of the residual and its complement yields attainable cost endpoints for a radius-and-column completion set, uniformly over adaptively selected updates. An upper-feasible candidate and a full-residual-corrected lower value then give a witness, an exclusion or an unresolved interval for unregularized target error. The same budgets apply jointly to shared responses and to complete cumulative updates. A captured GPT-2 shared-response problem exhibits all three outcomes at one target tolerance; its intermediate request remains unresolved despite a feasible full-information reference. A saved-state analysis of 32 factual requests finds nearly equal first-witness costs for optimistic queries and strong Krylov after the initial sketch pass is counted, despite differences in fitting accuracy. Native factual evaluation and cumulative candidate rejections expose the limits of finite-feature protection. The results connect covariance information to actionable response decisions without turning candidate failure into a claim of infeasibility.

Primary area:
optimization
Keywords:
knowledge editing, covariance sketching, PSD completion, constrained optimization, feasibility certification, response protection

Reviews

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

This paper essentially works on knowledge editing for LLMs, in the locate-then-edit setting of ROME/MEMIT/AlphaEdit. An edit is a weight change D to a single linear layer (an MLP output projection). It should (i) move the layer's outputs at the edited keys toward desired values (ii) barely change the outputs on a set of "protected" keys and (iii) keep the update small. The question the paper asks is how to decide whether such an edit exists when the covariance matrix Q is not stored exactly. Instead, Q is known only through a Frequent Directions sketch with a residual bound, plus a few exact covariance-vector products Qv.

The paper makes three theoretical points. First, two streams of protected keys can produce identical Frequent Directions sketches but opposite answers about whether a given edit request is feasible (Proposition 1), so a sketch alone cannot always decide. Second, given exact products Qv on a set of directions, classical PSD completion yields the tightest lower and upper bounds on the unknown part of Q, uniformly over all candidate edits (Proposition 2). Third, combining an edit that is feasible under the upper bound with a weak-duality lower value computed under the lower bound gives a three-way decision (Proposition 3): a "witness" (the request is feasible), an "exclusion" (no edit satisfies all three budgets), or "unresolved". The authors also discuss batch edits (one update serving several targets) and sequential edits, where the budgets must be checked on the cumulative update.

The GPT-2 experiments are illustrative. They show that all three outcomes can occur on a real editing problem, and that "unresolved" differs from "infeasible". They also show that covariance-vector queries are needed beyond the sketch, but the proposed query policies perform about the same as a Krylov baseline. Finally, a witness for the layer-level budgets does not guarantee preserved model behavior on unrelated facts.

Critical strengths
  1. source code is provided which is good for reproduction.
  2. simple and correct technical results. The bounds are easy to verify.
Critical weaknesses
  1. Very poor readability. The paper is hard to follow. To name a few,
  • The introduction never states the concrete problem. It speaks of "modifying a model at a linear projection", "protected feature rows" and "requested responses", but never says that the edit is a weight update to a single MLP output projection of a transformer, what the protected features and new features are (MLP inputs at calibration positions and at the edited subject tokens), or where the requested responses come from (target output vectors optimized as in ROME). The word "MLP" first appears in Section 3, and the layer and model actually edited only in Section 5 and Appendix B. Nor does the introduction explain in what practical situation the key covariance cannot be stored, which is the premise of the entire paper. The reader has to reverse-engineer from Sections 2-5 and the appendix that the setting is locate-then-edit knowledge editing as in ROME/MEMIT.

  • Many technical terms in the main text are used without definition. Examples:

    • "accumulated shrink values" and "residual traces" (Introduction, Proposition 1). These are Frequent Directions internals, and Proposition 1 depends on them, but the FD update is never described.
    • "complete protected prefixes, including answer paths" and "untied projection" (Introduction).
    • "upper-feasible candidate", "full-residual-corrected lower value" and "witness", all used in the Introduction before Section 2.4 defines them.
    • "native" evaluation versus non-native, "physical response units" (Sections 4-5, Figure 1).
  • The setting is standard locate-then-edit knowledge editing, but the paper renames nearly every standard concept without relating it to the established terms. The "protected covariance" Q is the uncentered key covariance used by ROME (C=KKTC = KK^T) and MEMIT (C0=K0K0TC_0 = K_0 K_0^T), and the "protected response cost" is their term for preserving previously stored associations. The new features K and requested changes R coincide with MEMIT's new keys K1K_1 and residual R=M1−W0K1R = M_1 - W_0 K_1. "Shared responses" is batch (mass) editing as in MEMIT, "cumulative admission" is sequential editing as studied by AlphaEdit, and "rewrite/paraphrase/neighborhood preference" are CounterFact's efficacy, paraphrase and neighborhood scores (ES/PS/NS in ROME). The term "protected features" also suggests a privacy or fairness setting, which is not what the paper is about.

  1. The setting is not realistic: storing Q is feasible, so the motivation for sketching is unclear.

The paper motivates the sketch by the quadratic cost of storing the key covariance Q=ATAQ = A^T A. At the scale studied, this cost is small:

  • Q for the edited GPT-2 layer is 3072 x 3072, about 38 MB in fp32. ROME/MEMIT routinely precompute and store exactly this matrix. Even for MLP widths of order 10^4 in larger models, the covariance of one layer remains well within a single accelerator's memory.

  • In the experiments, Q is built from only n = 512 protected positions. Storing A itself (512 x 3072, which the paper reports as 12.6 MB) gives Q exactly. More generally, exact Q is always available at a storage cost of min⁡(nd,d2)\min(nd, d^2). The query policies store 4.6-7.2 MB, so the memory saving over exact information is only about 2-3x.

  • The method is not actually sketch-only. Each covariance-vector action Qv=AT(Av)Qv = A^T(Av) requires another full pass over the protected features, and the experiments use up to 33 passes. So the method still needs either A or the ability to recompute A by rerunning the model. The implied regime (Q too large to store, yet repeated passes over the protected features affordable) is never motivated or measured with a concrete memory or compute budget.

  • The paper does not compare against the obvious alternative of simply storing Q, or A, and solving the editing problem exactly, as ROME/MEMIT/AlphaEdit do. Without such a comparison, or experiments in a regime where Q genuinely cannot be stored (larger models, many protected keys, a tight memory budget), it is unclear when the proposed interface would be preferable in practice.

Questions for authors

In what concrete setting is storing the key covariance Q infeasible while a sketch plus covariance-vector queries is affordable? For the GPT-2 layer studied, Q is 3072 x 3072 (about 38 MB in fp32), and it is built from only 512 protected positions, so storing A itself (12.6 MB as reported) gives Q exactly. Could you specify the model size, number of protected keys, and memory budget where the proposed interface is preferable, and report measurements in that regime?

2 comments
AuthorsOpenReview ↗

Reviewer tRrf

The full-information comparison is important for understanding what is lost when covariance information is incomplete. The submitted paper includes objective references for this comparison. Section 5.1 reports the full-information target errors for the shared-response problem, and Figure 1 plots them against the decision intervals. Section 5.2 uses 96 full-information scalar solutions as objective references across the 32 factual requests and three protection caps. At relative tolerance 0.5 in Figure 1, the squared threshold is 1235.766 and the intermediate request has a full-information target error of 1200.896. Its retained-information interval is [1175.352, 1963.695], so the interface correctly leaves it unresolved.

To make the setting behind these comparisons concrete, the editing operation changes the weight matrix of one transformer MLP output projection. Protected keys are MLP inputs at calibration positions, new keys are inputs at the editing positions, and target responses specify the desired output changes. For the factual study, these targets are optimized latent vectors following the locate-then-edit construction. Equation (1) asks whether one update meets the target-fit, calibration-response and update-norm budgets jointly. We will put this example and its connection to standard key-covariance notation in the introduction, and define the FD accumulated shrink and residual trace when first used.

The information constraint has a precise consequence even when a full-information solve is available for evaluation. Proposition 1 constructs two realizable streams with identical FD sketches, accumulated shrink and residual trace, for which the same request has opposite feasibility answers. Proposition 2 then characterizes the protection costs consistent with the retained radius and acquired columns, uniformly over all candidate updates. Together these results establish what additional covariance information can settle and why a sound decision rule sometimes returns unresolved.

The cost of accessing this information is central to the practical question. For the measured GPT-2 layer, retaining the 512 × 3072 FP64 feature array costs about 12.6 MB, the dense FP32 covariance costs about 37.7 MB, and the policy uses up to 33 feature passes including FD setup. The intended operating regime has a bounded resident covariance state and access to streamed or recomputed features. The submitted objective references quantify the effect of incomplete information on the editing solution.

Finally, the review describes the technical results as “simple and correct” and the bounds as easy to verify, while assigning soundness 1. Could the reviewer identify the specific mathematical statement or proof step underlying that rating? This would let us address the validity concern directly.

Thanks for your response. I have increased the soundness score, but my concern over real scenario improvement is not addressed, and I would like to keep my evaluation.

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

This paper considers whether a requested update to a fixed linear projection can meet a target-response tolerance, a protected-response covariance budget, and a Frobenius-norm budget when the protected covariance is only partially retained. It proposes a three-way interface that admits a feasible update, excludes a request, or returns an unresolved status. Proposition 1 constructs two feature streams with identical Frequent Directions (FD) summaries but opposite feasibility outcomes. Proposition 2 derives attainable PSD lower/upper residual completions from covariance-vector queries, and Proposition 3 combines an upper-feasible candidate with a full-residual-corrected dual lower bound for the unregularized target error. The formulation also covers shared response targets and cumulative updates at one fixed projection. Experiments on a small GPT-2 model include one rank-16 shared-response instance, 32 CounterFact development requests, comparisons with scalar/block Krylov controls, and 128 cumulative candidate-admission attempts.

Critical strengths
  1. The paper formulates three explicit budgets and correctly separates an attainable witness, a request-level exclusion, and an unresolved interval. The realizable equal-FD-state construction shows why discarded covariance directions can make a binary sketch-only decision impossible. The proof structure also makes clear that a valid exclusion must use a full-space lower bound and remove the regularization term before comparison with the target-error tolerance. This is a coherent and potentially useful decision perspective for fixed-feature editing.

  2. The paper distinguishes finite projection-response guarantees from downstream model behavior, and it explicitly notes where PSD endpoint sharpness, floating-point certificates, and sequential preservation do not extend. Counting the initial FD pass, adding strong scalar and rank-aware block Krylov comparisons, and retaining rejected cumulative proposals make the empirical discussion more credible than a comparison against weak sketch-only baselines.

Critical weaknesses
  1. The main contribution appears to be an information-aware decision formulation rather than a substantially new mathematical or algorithmic result. Proposition 1 gives a realizable but relatively simple indistinguishability example; Proposition 2 obtains PSD completion endpoints through classical Nyström/Schur-complement arguments applied to the residual and its complement; and Proposition 3 combines feasible-upper and dual-lower bounds with a necessary regularization correction. The cumulative and exact-prefix arguments also rely on established projection-based ideas (e.g., Fang et al., 2025; Lyu et al., 2026). Although the synthesis is coherent, the manuscript does not clearly quantify its additional decision value over simpler covariance bounds or structure-matched baseline checks at comparable information costs. Moreover, endpoint sharpness is shown for the radius-and-column completion set, which may be looser than the full retained FD information state when trace or history is available. This limits the demonstrated significance of the theoretical advance, without calling the stated results incorrect.

  2. The empirical evidence for the practical benefit of three-way admission remains limited. All three statuses are illustrated within one rank-16 shared-response instance, using target tolerances selected retrospectively. The 32 factual requests appropriately measure witness-finding rather than exclusion, since every request has a full-information witness; at the primary tolerance, optimistic queries and strong Krylov have nearly identical first-witness feature-pass costs after counting the FD setup pass. In the cumulative study, only four of 128 tested candidate insertions are admitted and no trajectory commits two edits. The other 124 outcomes reject those candidates, not necessarily the underlying requests, so this experiment cannot substantiate nontrivial multi-edit preservation. The single small GPT-2 model and limited feature-protection setting also leave the broader applicability of the decisions insufficiently tested.

Questions for authors
  1. Can the authors quantify the added decision value of the two-sided PSD completion over simpler radius-only covariance bounds, using matched covariance-action and storage budgets? It would also help to clarify whether incorporating the known FD residual trace materially changes the decision intervals?

  2. The cumulative study rejects 124 of 128 candidate insertions, but these rejections do not establish infeasibility of the corresponding requests. Could the authors provide diagnostics separating limitations of the candidate construction and budget choices from potentially conservative checks, and indicate whether a nontrivial trajectory with multiple committed edits is attainable in a comparable setting.

  3. Could the authors test the decision interface on a few additional independently selected shared-response instances, or provide other evidence of robustness beyond the single rank-16 problem? Reporting decision outcomes and first-decision feature-access/storage costs against the existing rank-aware block Krylov control would help assess how consistently the proposed interface is useful.

2 comments
AuthorsOpenReview ↗

Reviewer gnxz

The known FD residual trace is an important part of the retained information. In the regime of our shared-response experiment, incorporating it does not change the optimistic endpoint. We have established the following extension for the nonempty radius–column–trace completion set. If the residual trace is ℓρ\ell\rho, there are qq acquired directions, and d≥ℓ+r+qd\ge\ell+r+q, then every candidate DD of rank at most rr has a completion EDE_D satisfying

tr⁡ED=ℓρ,tr⁡(DEDD⊤)=tr⁡(DE−D⊤).\operatorname{tr}E_D=\ell\rho,\qquad \operatorname{tr}(D E_D D^\top)=\operatorname{tr}(D E_- D^\top).

The construction places the remaining trace in admissible completion directions annihilated by DD. The attaining completion may depend on DD. Projecting updates onto the column space of the target matrix gives the same optimistic target-fit optimum under the added trace constraint when r=rank⁡Rr=\operatorname{rank}R. Our instance has d=3072d=3072, ℓ=8\ell=8, r=16r=16 and q≤32q\le32, satisfying the condition. The result uses radius, queried columns and trace as its information class. Trace can still tighten the upper endpoint. This answers which side of the interval the known trace can improve in the experiment.

The acquired columns also have a direct decision role. Proposition 2 gives the attainable protection endpoints for every candidate consistent with the radius-and-column information, including candidates chosen after the actions are observed. In Figure 1 at q=32, the three intervals are [1394.888, 3628.743], [1175.352, 1963.695] and [800.896, 802.894]. At the common threshold 1235.766 they yield an exclusion, an unresolved request and a witness. The corresponding full-information errors are 1507.545, 1200.896 and 801.120.

The submitted rank-aware block comparison also quantifies the accuracy and storage tradeoff at the same covariance-action counts. The optimistic policy has a lower regularized objective in all nine comparisons. At q=32, the block control's objective/full ratios are 2.65037, 2.09937 and 1.01614, with 2,896,008 stored bytes compared with 7,196,688 for the policy.

The cumulative experiment addresses a different question: whether proposed insertions can be admitted under a shared protection budget. Under the fixed 3% protection cap, the recorded outcomes are 124 rejected candidates and four admissions, with no trajectory committing two edits. The checks apply to the entire accumulated update, including its cross terms. The result identifies a protection-budget obstacle for the constructed proposals.

The independent-request evidence consists of 32 separately selected factual requests, whose median first-witness costs are 10, 5.5 and 2 feature passes for both optimistic queries and strong Krylov at the primary tolerance. Figure 1 contributes 198 states of one rank-16 shared-response problem evaluated at three retrospective tolerances, yielding 594 decisions. Sections 5.1–5.2 report these respective experimental units alongside the decision and access-cost results.

Thank you for the detailed response. We appreciate the authors' clarifications, particularly the additional theoretical result concerning the FD residual trace. The response addresses some of our concerns and provides further justification for the proposed framework. However, it does not fully establish the practical advantages of the method over existing tools and strong baselines. In particular, the limited evidence from independent shared-response instances and the lack of nontrivial cumulative editing results remain concerns. Therefore, I'll keep my current scores.

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

The paper asks when an edit D to one linear projection can be accepted under three budgets: target fit ‖DK−R‖, protected cost tr(DQDᵀ), and ‖D‖_F. The decision uses only a Frequent Directions sketch of Q, a residual radius ρ, and some covariance-vector products Qv. Prop. 1 builds two streams that share an FD state but give opposite answers. Prop. 2 uses Nystrom-type PSD completion to get lower and upper residual operators E−, E+. Prop. 3 combines an upper-feasible candidate with a weak-duality lower value to return a witness, an exclusion, or "unresolved". Experiments on GPT-2 small cover one 16-column shared-response problem (all three outcomes appear), 32 CounterFact edits (first-witness cost vs. a Krylov control), and a sequential-admission study.

Critical strengths

Writing is clear.

Critical weaknesses
  • The experiments never reach the regime that motivates the method, and the decisions do not change anything in practice. The motivation is that keeping a dense covariance is too costly. Yet protection uses n = 512 rows with d = 3072. By the paper's own count, the raw rows take 12.58 MB, and they give exact Qv products and an exact decision. The policies keep 4.6–5.8 MB, only about 2–3× less. ROME/MEMIT, by contrast, estimate covariance from 100,000 Wikitext samples. In the 32-case study, every lower value is zero, and first-witness cost equals the classical Krylov control's (Table 4), which stores 1.76 MB and needs no FD pass. Natively, the unconstrained covariance-ridge and calibration-nullspace references reach 50.0% neighbourhood preference, at least as high as every constrained method (Table 1). The cumulative study admits 4/128 edits. The only demonstration where the three outcomes differ is a single problem with tolerances chosen after the run.

  • The technical contribution is very thin, and the lower bound seems looser than needed. The authors say the components are established, and each proposition is a short corollary. Prop. 3 bounds tr(GH⁻¹Gᵀ) by ‖G‖²/(γ+µ). But H = (γ+µ)I + KKᵀ + λ(C+E−) is identity plus a matrix of rank ≤ k+ℓ+q. That makes the exact dual function computable cheaply with Woodbury, and it dominates ℓ(Z) for every Z. Some of the "unresolved" outputs, and the 8/9 negative block lower values, may come from this relaxation rather than from missing information. Subtracting γτ² is the same as using norm multiplier γ+µ.

Questions for authors
  • Why use ℓ(Z) rather than the exact dual function, which costs little given H's identity-plus-low-rank structure? How many of the 260 unresolved outputs in Fig. 1 change under the exact dual?
2 comments
AuthorsOpenReview ↗

Reviewer ys2Y

The exact dual addresses your question about whether the scalar correction leaves decisions unresolved. In the replay, zero of the 260 unresolved outputs in Figure 1 becomes an exclusion. We evaluated all 198 saved states using their original multipliers. Across the three thresholds, all 594 decisions remain unchanged, comprising 215 exclusions, 119 witnesses and 260 unresolved outputs. The maximum absolute change in the lower bound is 2.16×10−112.16\times10^{-11}. The computation uses a low-rank solve with full-coordinate residual correction and the original FP64 decision guard.

Equation (8) uses a scalar curvature bound to turn the full-space gradient residual into a lower-value correction. The identity-plus-low-rank structure permits the tighter evaluation you propose at the same covariance-action budget. Writing the quadratic Hessian factor as HH and the gradient residual as GG, exact minimization gives

Lexact=L−(Z)−tr⁡(GH−1G⊤)−γτ2.L_{\rm exact}=L_-(Z)-\operatorname{tr}(GH^{-1}G^\top)-\gamma\tau^2.

Since H⪰(γ+μ)IH\succeq(\gamma+\mu)I, its inverse correction is at most ∥G∥F2/(γ+μ)\|G\|_F^2/(\gamma+\mu). Taking the maximum with zero gives a lower bound on unregularized target error. The subtraction of γτ2\gamma\tau^2 removes the possible ridge contribution over the norm ball. Our replay establishes that replacing the scalar correction by this exact quadratic evaluation is numerically inactive for the Figure 1 states at their saved multipliers. We will include the tighter formula and the replay result.

The information available to the decision rule also matters when interpreting these unresolved outcomes. Proposition 1 establishes opposite feasibility answers for realizable streams with identical retained FD state, including shrink and trace. Proposition 2 supplies attainable endpoints throughout its radius-and-column completion class, uniformly over adaptively selected updates. The Figure 1 comparison with full information then identifies a feasible request whose finite-information interval straddles the target threshold. A witness permits committing an update within the three budgets, an exclusion establishes that the request requires a budget or target change, and an unresolved interval identifies a need for further work before committing.

The submitted controls quantify where the current policies gain accuracy and what they cost. In the rank-16 comparison the optimistic policy improves the regularized objective in all nine comparisons with block Krylov, whose q=32 objective/full ratios are 2.65037, 2.09937 and 1.01614. The block stores 2,896,008 bytes and the policy stores 7,196,688. In the scalar study, optimistic queries and strong Krylov have the same median first-witness pass counts at the primary tolerance. The calibration arrays contain 512 rows, and the reported native evaluation measures the resulting neighborhood preferences separately from the finite-response budgets.

Thank you for the response. My main concerns are not addressed so I'll keep my current scores.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.