Paper deep dive
When Is Deletion Ordering Tractable? From Update Dynamics to Permutation Structure
Xinyu Wang, Ziyu Zhao, Yixuan He, Xiaowen Chang Alex Smola
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 10/3/2026, 2:16:49 AM
Summary
This paper investigates the computational structure of deletion ordering in machine learning models, where retraining from scratch is prohibitive. It identifies two independent structural reductions for the permutation objective induced by sequential deletion requests: position additivity (reducing optimization to assignment or sorting) and suffix localization (reducing dependence on distant prefixes). The authors prove these reductions are independent, characterize the quadratic interactions that obstruct additivity under shared affine updates, and show that suffix-conditioned assignment improves approximation rates. Experiments validate these structures in frozen-head and full-network settings, demonstrating that identified structures can predict unseen orders.
Entities (9)
Relation Signals (8)
Xinyu Wang → affiliatedwith → McGill University
confidence 99% · Xinyu Wang1 ... 1McGill University
Ziyu Zhao → affiliatedwith → Arizona State University
confidence 99% · Ziyu Zhao2 ... 2Arizona State University
Position Additivity → isindependentof → Suffix Localization
confidence 98% · We identify two independent reductions... prove the reductions' independence
Position Additivity → reducesto → Assignment Problem
confidence 95% · position additivity represents the objective by request–position costs, reducing optimization to assignment
Position Additivity → reducesto → Sorting
confidence 95% · with a shared positional profile, sorting
Suffix Localization → removesdependenceon → Distant Prefix
confidence 95% · suffix localization removes dependence on the distant prefix
Quadratic Interactions → obstruct → Position Additivity
confidence 90% · characterize the quadratic interactions that obstruct additivity
Damped-Newton → demonstrateseffecton → Objective Structure
confidence 85% · A controlled damped-Newton sweep shows that stronger contraction shifts the objective toward shorter, more suffix-specific dependence
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Given a fixed set of pending deletion requests, retraining from scratch after each request is prohibitive, so a prescribed request-wise policy processes them sequentially. The resulting terminal model can depend on their order. Rather than prescribing an ordering rule, we study the permutation objective induced by the fixed policy and ask when it admits simpler structure. We identify two independent reductions: position additivity represents the objective by request--position costs, reducing optimization to assignment and, with a shared positional profile, sorting; suffix localization removes dependence on the distant prefix while retaining interactions among the surviving requests. Under shared affine updates, we characterize the quadratic interactions that obstruct additivity, prove the reductions' independence, and show that suffix-conditioned assignment improves the approximation rate from O(p^L) toO(p^(2L)). Experiments recover both structures in executed objectives. A controlled damped-Newton sweep shows that stronger contraction shifts the objective toward shorter, more suffix-specific dependence, while two full-network policies exhibit distinct positional and within-suffix structure. Structures identified from compact execution sets also predict unseen orders. These results frame deletion ordering as identifying the computational structure induced by the executed updates.
Tags
Links
- Source: https://arxiv.org/abs/2610.01149v1
- Canonical: https://arxiv.org/abs/2610.01149v1
Trouble viewing inline? Open PDF directly →
Full Text
138,209 characters extracted from source content.
Expand or collapse full text
When Is Deletion Ordering Tractable? From Update Dynamics to Permutation Structure Xinyu Wang1 Ziyu Zhao2,111footnotemark: 1 Yixuan He2 Xiao-Wen Chang1 Alex Smola3 1McGill University 2Arizona State University 3BosonLabs †thanks: Equal contribution.†thanks: Corresponding author. Abstract Given a fixed set of pending deletion requests, retraining from scratch after each request is prohibitive, so a prescribed request-wise policy processes them sequentially. The resulting terminal model can depend on their order. Rather than prescribing an ordering rule, we study the permutation objective induced by the fixed policy and ask when it admits simpler structure. We identify two independent reductions: position additivity represents the objective by request–position costs, reducing optimization to assignment and, with a shared positional profile, sorting; suffix localization removes dependence on the distant prefix while retaining interactions among the surviving requests. Under shared affine updates, we characterize the quadratic interactions that obstruct additivity, prove the reductions’ independence, and show that suffix-conditioned assignment improves the approximation rate from O(ρL)O(ρ^L) to O(ρ2L)O(ρ^2L). Experiments recover both structures in executed objectives. A controlled damped-Newton sweep shows that stronger contraction shifts the objective toward shorter, more suffix-specific dependence, while two full-network policies exhibit distinct positional and within-suffix structure. Structures identified from compact execution sets also predict unseen orders. These results frame deletion ordering as identifying the computational structure induced by the executed updates. 1 Introduction A deployed model is often required to remove specific training data after the fact, and retraining from scratch on every request is prohibitive, so approximate unlearning edits the trained model in place (Guo et al., 2020; Kurmanji et al., 2023; Koloskova et al., 2025). When a prescribed request-wise policy processes a pending set, each request acts on the model produced by its predecessors. The same pending requests can therefore lead to different terminal models under different orders; with the request set, policy, and per-request budget fixed, the order is the decision variable. Existing work has shown that deletion order matters and has proposed schedules based on uncertainty, difficulty, or forgettability (Zhao et al., 2024; Kumar et al., 2026). These rules choose an order, but do not characterize the optimization problem induced by the sequential updates. The objective over the k!k! schedules of k pending requests may reduce to independent request scores, request–position costs, dependence on only the most recent requests, or none of these. Unlike classical scheduling and training-order problems, where the cost structure is prescribed (Smith, 1956; Rajput et al., 2022; Li and Hiratani, 2025), here it is created by composing the deletion updates and evaluating the terminal model. We fix the deletion requests, update policy, and terminal objective, and vary only their order, defining an objective J(π)J(π) over permutations π∈Skπ∈ S_k, where SkS_k is the set of all k!k! request orders. We study two ways in which this objective can be simplified (Figure 1). Position additivity represents J(π)J(π) by request–position costs, reducing order selection to linear assignment and, under a shared positional profile, to sorting. Suffix localization makes the distant prefix irrelevant once the final L requests are fixed, reducing the search to ordered suffixes. The two reductions discard different information. Position additivity removes cross-request interactions across positions, whereas suffix localization removes dependence on the distant prefix. They can therefore hold separately or together. Figure 1: Two independent routes to a simpler ordering problem. Left, position additivity represents the objective by request–position costs. Right, suffix localization discards the distant prefix. Below, the two compose, at the rate Proposition 2(c) gives for shared affine updates. The update dynamics determine which reduction, if any, is available. Even when request responses combine additively at the endpoint, a squared terminal objective introduces pairwise request–position interactions, so endpoint additivity need not imply position additivity. Conversely, contractive updates suppress dependence on the distant prefix without eliminating interactions among the surviving requests. We characterize both mechanisms, prove that the two reductions are independent and composable, and show that contraction can yield a useful approximation without making exact optimization tractable. We then test these structures in executed unlearning objectives. Across frozen-head and full-network settings, the induced objectives occupy different structural regimes. A deterministic damped-Newton intervention, used here because its Jacobian is analytic, shows that stronger contraction shifts dependence toward shorter, more suffix-specific representations, while held-out studies show that structures identified from compact execution sets transfer to unseen orders. The cost of identifying a representation from executions is measured separately from the cost of optimizing once that representation is available. Contributions. We make three contributions: (i) we formulate deletion ordering as an induced permutation objective and identify position additivity and suffix localization as two independent structural reductions; (i) we derive assignment, sorting, and finite-suffix reductions with approximation guarantees, characterize their composition, and establish a boundary for exact optimization under contraction; and (i) we connect these structures to executed frozen-head and full-network dynamics and test their transfer beyond exhaustive small-k tables. 2 Related Work Approximate unlearning uses gradients, curvature, distillation, or parameter saliency (Guo et al., 2020; Kurmanji et al., 2023; Fan et al., 2024; Foster et al., 2024; Koloskova et al., 2025). Reference proximity and behavioral forgetting provide different evidence about an unlearning policy (Mavrothalassitis et al., 2025). We use reference distance as a dense terminal ordering objective and report behavioral gates and deletion trajectories separately. Guo et al. use a Newton correction, with loss perturbation for the general case, whereas Koloskova et al. use noisy fine-tuning on retained data. Our deterministic damped-Newton rule is an intervention chosen for its known Jacobian. Zhao et al. compare one-shot unlearning with sequential processing of difficulty-refined forget subsets, and Kumar et al. study noncommutativity and uncertainty-based forget-set ordering (Zhao et al., 2024; Kumar et al., 2026). These studies establish that request composition and order affect sequential unlearning. Our complementary question is which permutation objective those executions induce and when that objective admits sorting, assignment, or suffix reduction. Request-level scoring corresponds to the scalar-sorting specialization of this framework. Adaptive and continual unlearning address deletion requests that arrive over time, including validity under adaptively chosen requests and utility across repeated language-model updates (Gupta et al., 2021; Gao et al., 2025). Our setting conditions on a finite pending batch and studies the objective over its execution orders, isolating schedule dependence under a fixed sequential policy. Yu et al. study how the order of multi-stage training changes subsequent local unlearning that uses forget-set gradients (Yu et al., 2025). We hold the trained starting state fixed and vary the later deletion history; common deletion suffixes, rather than common training histories, define our memory measure. The changed history and the information available to the unlearning rule are therefore different in the two settings. Classical scheduling derives sorting rules from supplied job costs and processing times, as in Smith’s rule for weighted completion time (Smith, 1956). Research on task and training order studies how curricula, optimization stability, and function composition create history dependence (Li and Hiratani, 2025; Hardt et al., 2016; Singh et al., 2023; Cooper et al., 2023; Kubo et al., 2024; Rajput et al., 2022; Lu et al., 2022). Our tools draw on quadratic assignment and weak-sum linearizability (Wang et al., 2021; Punnen and Kabadi, 2013; Çela et al., 2014). In our setting, the costs are induced by a deletion policy and terminal objective, and each permutation unit is a stateful request that may contain many examples and internal updates. Kubo et al. prove target-composition hardness for general increasing linear maps (Kubo et al., 2024). Our Partition construction instead isolates the shared strict-contraction subclass: every request has linear part ρIρ I and is realized by a positive, non-overshooting gradient step, while the dimension grows with the instance and ρ approaches one. The detailed comparison is in Appendix A.2. 3 Deletion Ordering as an Induced Computational Problem Let the training set be the disjoint union of a final retain set R and deletion requests F1,…,FkF_1,…,F_k. Training on all data initializes the execution state w0w_0. We fix an unlearning policy U and vary only the request permutation. All stochastic choices are bound to request identity, so changing the order changes composition rather than the random draw assigned to a request. Request FiF_i induces a transition UiU_i, where the state w includes both the model and any policy state carried across requests. For π∈Skπ∈ S_k, wπ=Uπk∘⋯∘Uπ1(w0).w_π=U_ _k ·s U_ _1(w_0). (1) Terminal objective. Let Φ be a declared comparison map and zRz_R a retained-data reference. Define the state objective j(w)=‖Φ(w)−zR‖22j(w)=\| (w)-z_R\|_2^2. Our primary permutation objective is J(π)=j(wπ)=‖Φ(wπ)−zR‖22,J(π)=j(w_π)=\| (w_π)-z_R\|_2^2, (2) with lower values preferred. The comparison map lets one formulation cover parameter-, output-, and representation-level terminal objectives. The concrete instantiations appear in Section 5. We define J⋆=minπ∈SkJ(π),ΔJ=π∼Unif(Sk)J(π)−J⋆.J = _π∈ S_kJ(π), _J=E_π (S_k)J(π)-J . Thus ΔJ _J is the improvement available over a uniformly random order. We normalize structural errors only when ΔJ>0 _J>0. Two structural reductions. For position additivity, we approximate the executed objective J by an assignment-form surrogate f(π)=c+∑p=1kCπp,p,f(π)=c+ _p=1^kC_ _p,p, (3) where c∈ℝc and C∈ℝk×kC ^k× k are free coefficients, so Ci,pC_i,p is the cost charged for serving request i at position p. Let A denote the family of all such surrogates. Exact position additivity means that some f∈f satisfies f(π)=J(π)f(π)=J(π) for every π∈Skπ∈ S_k. For suffix localization, write π=σsπ=σ s, where s is an ordered length-L suffix and σ its prefix. For example, for four requests w,x,y,zw,x,y,z, if π=(w,x,y,z)π=(w,x,y,z) and L=2L=2, then σ=(w,x)σ=(w,x) and s=(y,z)s=(y,z). We define WL=maxsmaxσJ(σs)−minσJ(σs).W_L= _s \ _σJ(σ s)- _σJ(σ s) \. (4) The width WLW_L measures how much the objective can still vary with the prefix after the final L requests are fixed. Thus WL=0W_L=0 means that J depends only on the ordered length-L suffix, while interactions within that suffix may still be arbitrary. Uniform structural error. For position additivity, define the normalized assignment error D=2ΔJminf∈maxπ∈Sk|J(π)−f(π)|.D_A= 2 _J _f _π∈ S_k|J(π)-f(π)|. (5) Thus D=0D_A=0 under exact position additivity. For suffix localization, let LS_L be the family of functions that depend only on the ordered length-L suffix. The best constant for each fixed suffix is the midpoint of its objective range, so inff∈L‖J−f‖∞=WL/2 _f _L\|J-f\|_∞=W_L/2. We therefore define DS,L=WLΔJ.D_S,L= W_L _J. (6) Thus DS,L=0D_S,L=0 under exact length-L suffix localization. Throughout, width denotes the raw range WLW_L, while error denotes the corresponding quantity normalized by ΔJ _J. The uniform norm gives a direct decision guarantee. If a surrogate f satisfies ‖J−f‖∞≤ε\|J-f\|_∞≤ and π^∈argminπf(π) π∈ _πf(π), then J(π^)−J⋆≤2ε,J( π)-J ≤ 2 , which we call the uniform regret bound. We therefore normalize uniform structural errors by 2/ΔJ2/ _J. An error below one is sufficient to guarantee that the selected order improves on the uniformly random-order mean. 4 Update Dynamics and Ordering Structure A fixed unlearning policy induces a permutation objective through its update dynamics. We begin with the simplest analyzable case, where all requests share the same linear response, and ask when the resulting ordering problem reduces below exhaustive search over SkS_k. Throughout this section, w denotes the representation in which terminal distance is measured, so Equation 2 has Φ=I =I. Proposition 2(a) separately allows a Lipschitz nonlinear comparison map. 4.1 Squared terminal distance creates interactions Suppose every request has the shared affine transition Ui(w)=Mw+biU_i(w)=Mw+b_i. Repeated application gives the additive endpoint wπ=Mkw0+∑p=1kMk−pbπp.w_π=M^kw_0+ _p=1^kM^k-pb_ _p. (7) Had the terminal cost been linear, substituting Equation 7 would preserve this additivity and give an assignment objective const+∑pCπp,pconst+ _pC_ _p,p with Ci,p=c⊤Mk−pbiC_i,p=c M^k-pb_i. The squared terminal objective instead introduces pairwise interactions. Expanding Equation 2 gives J(π)=c0+∑pCπp,p+2∑p<qπp,πq,p,q,J(π)=c_0+ _pC_ _p,p+2 _p<qK_ _p, _q,p,q, (8) where ijpq=bi⊤(Mk−p)⊤Mk−qbjK_ijpq=b_i (M^k-p) M^k-qb_j and the unary terms absorb the reference and diagonal contributions. Thus endpoint additivity does not imply position additivity of the induced objective. Squared terminal distance couples request pairs with position pairs. For M=λIM=λ I, the norm term is a Koopmans–Beckmann quadratic assignment problem with rank-one positional coefficient matrix Ppq=λ2k−p−qP_pq=λ^2k-p-q. Linear assignment is therefore a special, rather than generic, induced structure. The full expansion, the Gram-matrix reading, and the perturbation bounds that carry a surrogate guarantee over to bounded deviations from the shared response are in Appendix A.1. 4.2 Position additivity yields assignment and sorting Equation 8 locates the obstruction: the coupling between a request pair and a position pair. Ordering reduces to assignment exactly when that coupling can be absorbed into unary request–position costs, on the linearizable boundary characterized by Punnen and Kabadi (2013) and Çela et al. (2014). Exact linearization is a strong requirement, so we instead measure distance from it. Fix a position pair (p,q)(p,q) with p<qp<q. The off-diagonal coefficients of Equation 8 at that pair form a request-pair interaction matrix Tpq:=[2ijpq]i,j∈ℝk×k,T^pq:= [2K_ijpq ]_i,j ^k× k, and this interaction is assignment-compatible when it separates into one term for the request at position p and one for the request at position q. We therefore decompose each entry as Tijpq=aipq+βjpq+Ξijpq,i≠j,T^pq_ij=a^pq_i+β^pq_j+ ^pq_ij, i≠ j, where the first two terms are absorbed into request–position costs and Ξ is the remaining non-additive interaction. Collecting the additive terms over all position pairs yields a projected assignment matrix C C. Assignment collapses further to sorting when its costs share a common monotone positional profile, Ci,p=ai+sihp.C_i,p=a_i+s_ih_p. For any fixed monotone profile h, the rearrangement inequality makes sorting the request scores sis_i optimal. To quantify approximate collapse with a simple closed-form certificate, Proposition 1(b) specializes this profile to the centered linear choice qp=p−(k+1)/2q_p=p-(k+1)/2 and measures the residual from that structure. Proposition 1 (Position reduction). (a) Suppose the executed objective differs uniformly from the shared quadratic surrogate by at most εsurr _ surr. Let π π minimize the projected assignment matrix and set ‖Ξ‖F2=∑p<q∑i≠j(Ξijpq)2\| \|_F^2= _p<q _i≠ j( ^pq_ij)^2. Then J(π^)−minπJ(π)≤2εsurr+2(k2)‖Ξ‖F.J( π)- _πJ(π)≤ 2 _ surr+2 k2\,\| \|_F. (9) (b) Suppose instead that an assignment objective with cost matrix C approximates J uniformly within ε _A. Every permutation pays a request-only and a position-only effect once, so double-center, C¯=HCH C=HCH with H=I−1k⊤H=I- 1k11 . For the centered linear profile qp=p−(k+1)/2q_p=p-(k+1)/2, write C¯=sq⊤+Ξ¯q C=sq + _q as the projection of C¯ C onto the corresponding sorting structure, and let πs _s sort s. Then J(πs)−minπJ(π)≤2ε+2k‖Ξ¯q‖F.J( _s)- _πJ(π)≤ 2 _A+ 2k\,\| _q\|_F. (10) The two parts chain. The assignment matrix that part (a) projects out satisfies ε≤εsurr+(k2)‖Ξ‖F _A≤ _ surr+ k2\,\| \|_F, so substituting this into part (b) bounds the sorted order’s regret by the two residuals together. A small interaction residual therefore certifies approximate position additivity, while a small linear-profile residual certifies that the corresponding scalar sorting rule suffices. The retained-gradient construction is in Appendix A.1, the linearizability details in Appendix A.2, and both projection proofs, together with the scope of the slice projection, in Appendix A.4. 4.3 Contraction localizes prefix dependence and composes with assignment Memory reduction. Contraction provides a different simplification from additivity. A common contractive suffix attenuates differences between states produced by different prefixes. If the terminal objective is Lipschitz on the resulting states, its dependence on the distant history contracts accordingly, while interactions within the suffix remain unrestricted. Proposition 2(a,b) quantifies this, first for Lipschitz updates and then for the affine case. Composition. Simply truncating the prefix also discards its interactions with the retained suffix, leaving an O(ρL)O(ρ^L) error term. A sharper construction fixes the ordered suffix and absorbs these prefix–suffix interactions into unary request–position costs for the remaining requests. The only discarded terms are then prefix–prefix interactions, whose two factors have each been attenuated by at least L subsequent updates. This yields the O(ρ2L)O(ρ^2L) bound in Proposition 2(c). Proposition 2 (Memory reduction and composition). (a) Fix an ordered length-L suffix s. Let sX_s be its reachable pre-suffix states with diameter dsd_s, and suppose the suffix map UsU_s, the composition of the final L updates, is κs _s-Lipschitz on sX_s. If j is Lj,sL_j,s-Lipschitz on Us(s)U_s(X_s), then maxu,v∈s|j(Us(u))−j(Us(v))|≤Lj,sκsds. _u,v _s|j(U_s(u))-j(U_s(v))|≤ L_j,s _sd_s. (11) For the squared objective of Equation 2 with LΦL_ -Lipschitz Φ , one may take Lj,s=2RsLΦL_j,s=2R_sL_ with Rs=supw∈Us(s)‖Φ(w)−zR‖R_s= _w∈ U_s(X_s)\| (w)-z_R\|. (b) Under the shared affine transition with ‖M‖≤ρ<1\|M\|≤ρ<1 and maxi‖bi‖≤B _i\|b_i\|≤ B, retaining only the final L response terms approximates J uniformly over orders to O(ρL)O(ρ^L), so the minimizer of the truncated objective has regret of the same order. (c) Under the hypotheses of (b), write π=σsπ=σ s and define the pointwise surrogate J^L(σs)=‖rs‖2+∑p≤k−LCσp,p(s) J_L(σ s)=\|r_s\|^2+ _p≤ k-LC^(s)_ _p,p, where rsr_s is the residual fixed by s and C(s)C^(s) contains the suffix-conditioned unary prefix costs. Then supπ|J(π)−J^L(π)|≤B2ρ2L(1−ρ)2, _π|J(π)- J_L(π)|≤ B^2ρ^2L(1-ρ)^2, (12) so its minimizer has regret at most 2B2ρ2L/(1−ρ)22B^2ρ^2L/(1-ρ)^2. Minimizing J^L J_L enumerates the ordered suffixes and solves one assignment problem per suffix, at cost O(kL+3)O(k^L+3). At a fixed suffix depth, conditioning on the suffix before assigning the prefix therefore sharpens the affine rate from ρLρ^L to ρ2Lρ^2L. Part (a), separately, establishes suffix localization with no additivity assumption on the surviving requests. For fixed contraction, uniformly bounded response constants, and a last-position decision signal that does not vanish, the depth a fixed tolerance requires is L=O(log(1/τ))L=O( (1/τ)), independent of k. Direct truncation to depth 2L2L has the same affine rate at optimization cost O(k2L)O(k^2L), so the conditioned construction has a smaller exponent in k only when L>3L>3. These costs assume that the structural representation is already available; constructing or identifying it is accounted for separately. The non-asymptotic constants behind (b), the Lipschitz constants for gradient-descent updates, the proofs, the queue-length result, and the contrasting refinement regime are in Appendix A.3. 4.4 Independence and exact complexity Independence. Position additivity and suffix localization capture distinct properties of the induced permutation objective, and neither subsumes the other. A nilpotent contraction yields exact suffix localization while retaining non-additive interactions, whereas an exact assignment objective can retain positive suffix width. Proposition 3 (Independence). Even under shared strict-contraction updates, position additivity and suffix localization do not imply one another, and each separation can cross the sufficient threshold of Section 3. Explicit low-dimensional witnesses, the queue lengths and suffix depths they cover, and their exact constants are in Appendix A.3. Exact complexity. The approximation structure induced by contraction does not determine the complexity of exact optimization. Even a positive, non-overshooting gradient step can induce an NP-hard ordering problem. Proposition 4 (Hardness under arbitrarily weak strict contraction). Deciding whether an order attains a given terminal objective is NP-complete even when every request is one positive, non-overshooting gradient step on a strictly convex quadratic, and hence a strict contraction with factor ρ<1ρ<1 that approaches one as the instance grows. The weak NP-hardness reduction from Partition has ρ→1ρ→ 1 as the instance grows. It separates strict contraction from exact tractability but leaves the complexity for ρ bounded away from one open. The construction, proof, and fixed-contraction approximation are in Appendix A.2. 5 Empirical Structure of Executed Ordering Objectives We ask which structural forms executed objectives take, which update dynamics produce them, and whether the structure can be identified from limited executions and transferred to unseen orders. Settings. We study frozen-head and full-network unlearning. Frozen heads include ridge and softmax classifiers on CIFAR-10 features from an ImageNet-pretrained ResNet-18 (Krizhevsky, 2009; He et al., 2016; Deng et al., 2009), and ridge classifiers on AG News and 20 Newsgroups embeddings from DistilBERT (Zhang et al., 2015; Lang, 1995; Sanh et al., 2019). Full-network experiments delete CIFAR-100 superclasses from a ResNet-18 using NegGrad+ (Kurmanji et al., 2023) and SalUn (Fan et al., 2024). Queue lengths range from four to fifteen; RGD, SMX, NG+, SalUn, and RNewt abbreviate ridge gradient descent, softmax, NegGrad+, SalUn, and ridge Newton, with -ext denoting a queue extension. Frozen heads use squared parameter distance. The full-network objective averages, over a fixed 2,000-example test audit set, squared Euclidean distance between centered 20-superclass-logit vectors and a fixed two-run retain-only reference. It sums coordinates within each example; update and audit data are disjoint. Protocol. Small queues are enumerated exhaustively, whereas longer-queue studies use disjoint identification and evaluation orders. To distinguish suffix-specific dependence from generic low-dimensional positional structure, we compare DS,LD_S,L with equal-capacity prefix and middle controls DP,LD_P,L and DM,LD_M,L, defined by conditioning on the first L positions or on a fixed contiguous middle block. Unless suffix depth is under study, L=2L=2 and we write DSD_S, DPD_P, and DMD_M. All structural errors are normalized by the random-order gap ΔJ _J. Full execution protocols and validity criteria are in Appendix B. Objective anchoring. Reference distance compares completed sequences; utility and forgetting remain separate. On complete full-network surfaces it tracks retained more closely than deleted-group accuracy (Appendix E.2). Two fixed reference-free objectives on three auxiliary replays retain assignment and suffix-22 while matched controls fail (Appendix E.5); this retrospective result is not a prospective pipeline. 5.1 Executed objectives exhibit different structural forms (a) Structural regimes (b) Response-level reconstruction Figure 2: Structural regimes and response-level reconstruction. (a) Assignment and suffix errors across executed settings. Points are medians across instances, whiskers the observed ranges, and the dashed lines mark D=1D=1. Quadrant labels refer to the median point, and -ext marks a queue-extension setting. (b) Reconstruction error 2ε/ΔJ2 / _J and selection regret for four singleton-response constructions, over 4545 complete k=4k=4 fresh-decision surfaces. Executed objectives occupy different regimes (Figure 2a). The exhaustive ridge extension is assignment-only. Complete full-network surfaces support suffix localization; NegGrad+ also supports assignment throughout, while SalUn is more heterogeneous on that axis. Proposition 3 supplies the complementary suffix-only separation. Position axis. A learned shared monotone profile brings NegGrad+ close to unrestricted assignment, while SalUn remains more heterogeneous; a fixed linear profile can therefore understate proximity to sorting. Suffix axis. A low suffix error alone does not establish suffix-specific dependence. For frozen-head gradient objectives, an equal-capacity prefix fit is comparably accurate. On full-network objectives, matched prefix and middle controls separate the suffix structure. On the complete k=4k=4 surfaces, NegGrad+ is localized to the final request, whereas SalUn generally requires the final two (Figure 3b); its additive two-position suffix is also looser, showing residual interactions (Appendix C.3). 5.2 Update dynamics shape the induced structure Figure 3: Update dynamics and positional memory. Points show medians across instances and whiskers the observed ranges, and the dashed line marks the normalized-error threshold D=1D=1. (a) Damped-Newton sweep, plotted against the analytic contraction κ1=1−δ _1=1-δ, with the damping that sets it on the upper axis. (b) NegGrad+ and SalUn compared across the suffix families and their equal-capacity prefix and middle controls. Quadratic interactions. Using the same singleton responses, the quadratic terminal score reconstructs the executed objective substantially more accurately than either its linear part or unary quadratic corrections carrying no interaction term (Figure 2b). Projecting those interactions onto request–position costs retains most of that accuracy and produces a tractable assignment objective. All constructions use no terminal-order observations, and the pattern holds across vision and text representations. A matched step-size intervention independently recovers the predicted second-order scaling, with a fitted slope of 1.971.97 against a predicted 22. Controlled contraction. Varying Newton damping shifts the objective toward shorter, more suffix-specific representations (Figure 3a). For damped Newton the retained Hessian cancels, leaving a Jacobian of (1−δ)I(1-δ)I and hence known contraction κ1=1−δ _1=1-δ. On all five held-out instances, both suffix errors fall as contraction strengthens; the equal-capacity prefix error rises monotonically, and the middle control rises on four of five. Assignment is non-monotone, so the intervention changes where positional memory resides rather than simplifying the objective uniformly. Beyond affine updates. Nonlinear full-network policies show the same localization. After a common two-request suffix, histories from different prefixes retain only 6.9%6.9\% of their median objective difference under NegGrad+ and 10.2%10.2\% under SalUn. At k=4k=4, effective suffix depth is one request for NegGrad+ and generally two for SalUn (Figure 3b). These are finite-execution observations; the causal claim rests on the controlled damping intervention above (Appendix C.2). Composition. On the three complete k=5k=5 NegGrad+ surfaces, we compare rank-50 assignment models conditioned on the first, third, or final request. Four design-only folds hold out 30 cyclic-relabeling-balanced orders each; every 90-order training design has full rank, and fitting uses training-fold normalization. Instance Prefix-cond. Middle-cond. Suffix-cond. seed0 0.4770.477 [0.433,0.522][0.433,0.522] 0.3700.370 [0.347,0.501][0.347,0.501] 0.3080.308 [0.285,0.323][0.285,0.323] seed1 1.5791.579 [1.325,1.941][1.325,1.941] 1.5471.547 [1.215,2.053][1.215,2.053] 0.7240.724 [0.630,0.990][0.630,0.990] seed2 0.3810.381 [0.365,0.409][0.365,0.409] 0.3490.349 [0.299,0.357][0.299,0.357] 0.1700.170 [0.157,0.190][0.157,0.190] Table 1: Matched-rank position conditioning. Entries are the median held-out DtestD test with observed [min,max][ , ] over four design-only folds. Final-request conditioning wins every instance–fold comparison, separating suffix specificity from capacity. The folds are not independent instances, and this one-depth test does not test the nonlinear ρ2Lρ^2L exponent. 5.3 Identified structure transfers to unseen orders (a) Ridge identification and transfer Requests Family Fit executions Held-out error 8 Sorting 8 0.0680.068 8 Assignment 50 0.0550.055 15 Sorting 15 0.1070.107 15 Assignment 197 0.1100.110 (b) Full-network held-out error Figure 4: Structural identification transfers to unseen orders. (a) Sorting and assignment fits identified from compact execution sets and scored on orders held out of the fit, exhaustively at eight requests and on a disjoint 500500-order sample at fifteen. (b) Held-out structural error DtestD test for the full-network prefix, middle, suffix, and assignment families, one point per instance, with the dashed line at Dtest=1D test=1. The ridge identification orders are fixed from the family design matrix before objective values are observed. With eight identification executions, sorting recovers the unique optimum among all 40,320 orders in each of the three k=8k=8 ridge instances. Assignment fits more tightly and recovers the same optima, but requires 50 executions (Figure 4a). At k=15k=15, both families remain accurate on held-out orders. Newly executed minimizers of the fitted assignment objectives outperform every identification and held-out order in all three instances (Appendix D.2), although their global ranks remain unknown. For full-network CIFAR-100, each instance uses 112 identification and 336 disjoint held-out orders. Assignment and suffix fits remain below threshold on held-out orders, whereas matched prefix and middle controls exceed it (Figure 4b). Executed unseen candidates pass the original screens, with mixed realized ranks (Appendix D.4); this tests structural extrapolation, not search efficiency. 6 Discussion and Conclusion Deletion ordering need not admit a universal rule because its computational structure is induced jointly by the update dynamics and terminal objective. Position additivity and suffix localization expose two distinct simplifications: one removes cross-request positional interactions, while the other removes distant history without eliminating interactions among recent requests. This distinction explains why contraction can shorten memory without making the objective additive, and why suffix conditioning can compose with assignment. This also separates approximate from exact tractability: contraction can make recent-history reductions accurate, while strict contraction alone does not guarantee easy exact optimization. Across the executed settings, these structural regimes remain distinguishable under matched controls and can transfer to orders outside the identification set. The resulting perspective is to treat deletion ordering as a structure identification problem before choosing a solver. A shared positional profile supports sorting, request–position costs support assignment, and localized history reduces the search to recent suffixes. Which reduction is appropriate therefore depends on what information the executed dynamics preserve in the terminal objective. A richer family is not automatically preferable: on the complete ridge surfaces, assignment fits more tightly, but sorting reaches the same optimum from fewer identification executions. Useful reductions must also remain predictive beyond their identification executions. Reproducibility statement A public repository will provide the frozen protocols, the raw execution outputs, and the scripts needed to regenerate every reported table and figure and to verify the numerical claims. Analyses that use outcomes retrospectively are identified at first use. Held-out and pre-outcome constructions are versioned in the accompanying protocols, together with the partitions and checkpoints each run is bound to. Use of AI assistants AI assistants were used for research discussion, code development and debugging, experimental analysis, and manuscript editing. The authors verified all code, results, and claims and take responsibility for the content. References Çela et al. (2014) E. Çela, V. G. Deineko, and G. J. Woeginger Linearizable special cases of the QAP. arXiv preprint arXiv:1409.6510. Cited by: §A.2, §2, §4.2. Cooper et al. (2023) A. F. Cooper, W. Guo, D. K. Pham, T. Yuan, C. Ruan, Y. Lu, and C. M. De Sa Coordinating distributed example orders for provably accelerated training. In Advances in Neural Information Processing Systems, Vol. 36. Cited by: §2. Deng et al. (2009) J. Deng, W. Dong, R. Socher, L. Li, K. Li, and L. Fei-Fei ImageNet: a large-scale hierarchical image database. In IEEE Conference on Computer Vision and Pattern Recognition, p. 248–255. Cited by: §5. Fan et al. (2024) C. Fan, J. Liu, Y. Zhang, E. Wong, D. Wei, and S. Liu SalUn: empowering machine unlearning via gradient-based weight saliency in both image classification and generation. In International Conference on Learning Representations, Cited by: §2, §5. Foster et al. (2024) J. Foster, S. Schoepf, and A. Brintrup Fast machine unlearning without retraining through selective synaptic dampening. In AAAI Conference on Artificial Intelligence, Cited by: §2. Gao et al. (2025) C. Gao, L. Wang, K. Ding, C. Weng, X. Wang, and Q. Zhu On large language model continual unlearning. In International Conference on Learning Representations, Cited by: §2. Garey and Johnson (1979) M. R. Garey and D. S. Johnson Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman. Cited by: §A.2. Guo et al. (2020) C. Guo, T. Goldstein, A. Hannun, and L. van der Maaten Certified data removal from machine learning models. In International Conference on Machine Learning, Cited by: §1, §2. Gupta et al. (2021) V. Gupta, C. Jung, S. Neel, A. Roth, S. Sharifi-Malvajerdi, and C. Waites Adaptive machine unlearning. In Advances in Neural Information Processing Systems, Cited by: §2. Hardt et al. (2016) M. Hardt, B. Recht, and Y. Singer Train faster, generalize better: stability of stochastic gradient descent. In Proceedings of the 33rd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 48, p. 1225–1234. Cited by: §2. He et al. (2016) K. He, X. Zhang, S. Ren, and J. Sun Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition, p. 770–778. Cited by: §5. Koloskova et al. (2025) A. Koloskova, Y. Allouah, A. Jha, R. Guerraoui, and S. Koyejo Certified unlearning for neural networks. In Proceedings of the 42nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 267, p. 31275–31298. Cited by: §1, §2. Krizhevsky (2009) A. Krizhevsky Learning multiple layers of features from tiny images. Technical report University of Toronto. Cited by: §5. Kubo et al. (2024) S. Kubo, K. Makino, and S. Sakamoto Composition orderings for linear functions and matrix multiplication orderings. In 35th International Symposium on Algorithms and Computation, Leibniz International Proceedings in Informatics, Vol. 322, p. 44:1–44:14. External Links: Document Cited by: §A.2, §2, §2. Kumar et al. (2026) V. S. Kumar, E. S. Nadimi, and V. C. Gogineni Controlling path dependence in gradient ascent unlearning through forget-set ordering. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, Proceedings of Machine Learning Research, Vol. 337, p. 3224–3236. Cited by: §E.4, §1, §2. Kurmanji et al. (2023) M. Kurmanji, P. Triantafillou, J. Hayes, and E. Triantafillou Towards unbounded machine unlearning. In Advances in Neural Information Processing Systems, Cited by: §1, §2, §5. Lang (1995) K. Lang NewsWeeder: learning to filter netnews. In International Conference on Machine Learning, Cited by: §5. Li and Hiratani (2025) Z. Li and N. Hiratani Optimal task order for continual learning of multiple tasks. In Proceedings of the 42nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 267, p. 34578–34603. Cited by: §1, §2. Lu et al. (2022) Y. Lu, S. Y. Meng, and C. De Sa A general analysis of example-selection for stochastic gradient descent. In International Conference on Learning Representations, External Links: Link Cited by: §2. Mavrothalassitis et al. (2025) I. Mavrothalassitis, P. Puigdemont, N. I. Levi, and V. Cevher Ascent fails to forget. In Advances in Neural Information Processing Systems, Cited by: §2. Punnen and Kabadi (2013) A. P. Punnen and S. N. Kabadi A linear time algorithm for the Koopmans–Beckmann QAP linearization and related problems. Discrete Optimization 10 (3), p. 200–209. Cited by: §A.2, §2, §4.2. Rajput et al. (2022) S. Rajput, K. Lee, and D. Papailiopoulos Permutation-based SGD: is random optimal?. In International Conference on Learning Representations, External Links: Link Cited by: §1, §2. Sanh et al. (2019) V. Sanh, L. Debut, J. Chaumond, and T. Wolf DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter. arXiv preprint arXiv:1910.01108. Cited by: §5. Singh et al. (2023) P. Singh, Y. Li, A. Sikarwar, W. Lei, D. Gao, M. B. Talbot, Y. Sun, M. Z. Shou, G. Kreiman, and M. Zhang Learning to learn: how to continuously teach humans and machines. In Proceedings of the IEEE/CVF International Conference on Computer Vision, p. 11674–11685. Cited by: §2. Smith (1956) W. E. Smith Various optimizers for single-stage production. Naval Research Logistics Quarterly 3 (1–2), p. 59–66. External Links: Document Cited by: §1, §2. Wang et al. (2021) Y. Wang, W. Yang, A. P. Punnen, J. Tian, A. Yin, and Z. Lü The rank-one quadratic assignment problem. INFORMS Journal on Computing 33 (3), p. 979–996. Cited by: §A.2, §2. Yu et al. (2025) J. Yu, Y. He, A. Goyal, and S. Arora On the impossibility of retrain equivalence in machine unlearning. arXiv preprint arXiv:2510.16629. Cited by: §2. Zhang et al. (2015) X. Zhang, J. Zhao, and Y. LeCun Character-level convolutional networks for text classification. In Advances in Neural Information Processing Systems, Cited by: §5. Zhao et al. (2024) K. Zhao, M. Kurmanji, G. Bărbulescu, E. Triantafillou, and P. Triantafillou What makes unlearning hard and what to do about it. In Advances in Neural Information Processing Systems, Cited by: §E.4, §1, §2. Appendix A Proofs and theoretical details A.1 Exact and approximate structure under shared responses Exact assignment under retained-gradient updates. A retained-gradient least-squares instance realizes exact position additivity. Let ℒR(w)=12hR‖w‖2−bR⊤w,ℒi(w)=12h‖w‖2−bi⊤w,L_R(w)= 12h_R\|w\|^2-b_R w, _i(w)= 12h\|w\|^2-b_i w, with hR,h>0h_R,h>0 and bi⊤bj=0b_i b_j=0 for i≠ji≠ j, take the terminal reference to be the retained-data minimizer zR=hR−1bRz_R=h_R^-1b_R, and starting at the full-data minimizer take one fixed-size gradient step on the current retained loss after each deletion. Expanding the recurrence gives wπ=γRbR+∑papbπpw_π= _Rb_R+ _pa_pb_ _p with apa_p depending only on position, so wπ−zR=v+∑papbπpw_π-z_R=v+ _pa_pb_ _p for v=(γR−hR−1)bRv=( _R-h_R^-1)b_R, and orthogonality removes the cross-request terms to leave J(π)=c0+∑p=1kCπp,p,Ci,p=ap2‖bi‖2+2apv⊤bi.J(π)=c_0+ _p=1^kC_ _p,p, C_i,p=a_p^2\|b_i\|^2+2a_pv b_i. Linear assignment returns a global optimum. Writing rt=1−ηhR+(k−t)hr_t=1-η\h_R+(k-t)h\ and Pt=∏u=tkruP_t= _u=t^kr_u with an empty product equal to one, the coefficients are ap=P1/(hR+kh)+η∑t<pPt+1a_p=P_1/(h_R+kh)+η _t<pP_t+1 and γR=P1/(hR+kh)+η∑t≤kPt+1 _R=P_1/(h_R+kh)+η _t≤ kP_t+1. These quadratics are ordinary least-squares blocks. Taking Xi=hIX_i= hI and yi=bi/hy_i=b_i/ h gives Xi⊤Xi=hIX_i X_i=hI and Xi⊤yi=biX_i y_i=b_i, with the retain block analogous. Interactions under general shared responses. Substituting Equation 7 into the squared terminal objective gives Equation 8. Specifically, let Ψp=Mk−p _p=M^k-p, r=Mkw0−zRr=M^kw_0-z_R, c0=‖r‖2,Ci,p=2r⊤Ψpbi+bi⊤Ψp⊤Ψpbi,ijpq=bi⊤Ψp⊤Ψqbj.c_0=\|r\|^2, C_i,p=2r _pb_i+b_i _p _pb_i, _ijpq=b_i _p _qb_j. The squared terminal objective therefore couples request pairs (i,j)(i,j) with position pairs (p,q)(p,q) through the four-index tensor K. For the scalar response M=ρIM=ρ I it factors as ijpq=ρ 2k−p−q⟨bi,bj⟩K_ijpq=ρ^\,2k-p-q b_i,b_j , separating a rank-one positional matrix from the request Gram matrix, which is the form Appendix A.2 uses to discuss linearizability. Robustness to response mismatch. The following uniform bounds quantify the additional surrogate error when the executed responses deviate from the shared-response model. They require the stated bounds to hold uniformly over reachable states, so estimating the same quantities only along realized trajectories gives a finite-execution diagnostic rather than a uniform guarantee. Linear mismatch. Let Ui(w)=(M+Ei)w+biU_i(w)=(M+E_i)w+b_i and U¯i(w)=Mw+bi U_i(w)=Mw+b_i, with ‖M‖≤a\|M\|≤ a, ‖Ei‖≤δ\|E_i\|≤δ, ‖bi‖≤B\|b_i\|≤ B, and a¯=a+δ a=a+δ. Writing M~t=M+Eπt M_t=M+E_ _t for the executed linear parts, the telescoping identity M~m⋯M~1−Mm=∑ℓM~m⋯M~ℓ+1EπℓMℓ−1 M_m·s M_1-M^m= _ M_m·s M_ +1E_ _ M -1 with submultiplicativity gives ∥M~m⋯M~1−Mm∥≤mδa¯m−1\| M_m·s M_1-M^m\|≤ mδ a^\,m-1. Applying it to the initial state, which is multiplied by a product of length k, and to a displacement inserted at position p, which is multiplied by the k−pk-p matrices after it, gives ‖wπ−w¯π‖≤Γk:=kδa¯k−1‖w0‖+Bδ∑m=1k−1ma¯m−1.\|w_π- w_π\|≤ _k:=kδ a^\,k-1\|w_0\|+Bδ _m=1^k-1m a^\,m-1. (13) Expanding ‖wπ−zR‖2−‖w¯π−zR‖2\|w_π-z_R\|^2-\| w_π-z_R\|^2 in eπ=wπ−w¯πe_π=w_π- w_π then bounds the terminal objectives uniformly by 2RkΓk+Γk22R_k _k+ _k^2, where Rk=maxπ‖w¯π−zR‖≤‖Mkw0−zR‖+B∑r<karR_k= _π\| w_π-z_R\|≤\|M^kw_0-z_R\|+B _r<ka^r. Nonlinear mismatch. Fix a common initial state, write v=w−w0v=w-w_0, and suppose that, uniformly over every reachable state v, deletion history S, and next request i, US,i(w0+v)−w0=Mv+bi+ES,iv+dS,i+rS,i(v),U_S,i(w_0+v)-w_0=Mv+b_i+E_S,iv+d_S,i+r_S,i(v), (14) with ‖M‖≤a\|M\|≤ a, ‖ES,i‖≤δ\|E_S,i\|≤δ, ‖dS,i‖≤ζ\|d_S,i\|≤ζ, and ‖rS,i(v)‖≤K‖v‖2/2\|r_S,i(v)\|≤ K\|v\|^2/2. If ‖vt‖≤Qt\|v_t\|≤ Q_t, subtracting the shared surrogate recurrence v¯t+1=Mv¯t+bπt+1 v_t+1=M v_t+b_ _t+1 and inducting on Γt+1=aΓt+δQt+ζ+K2Qt2,Γ0=0, _t+1=a _t+δ Q_t+ζ+ K2Q_t^2, _0=0, (15) gives ‖vt−v¯t‖≤Γt\|v_t- v_t\|≤ _t, and the same expansion as above bounds the terminal objectives by 2R¯kΓk+Γk22 R_k _k+ _k^2 for R¯k=maxπ‖w0+v¯k−zR‖ R_k= _π\|w_0+ v_k-z_R\|. Write JaffJ_ aff for the shared-response objective and let εdyn _ dyn be the bound just obtained, so ‖J−Jaff‖∞≤εdyn\|J-J_ aff\|_∞≤ _ dyn. If a surrogate J J satisfies ‖J^−Jaff‖∞≤εsurr\| J-J_ aff\|_∞≤ _ surr, then ‖J−J^‖∞≤εdyn+εsurr\|J- J\|_∞≤ _ dyn+ _ surr, so the uniform regret bound gives any minimizer of J J regret at most 2(εdyn+εsurr)2( _ dyn+ _ surr). A.2 Assignment reductions and exact hardness Scalar-response linearizability. For M=ρIM=ρ I, let αp=ρk−p _p=ρ^k-p, P=αα⊤P=α , and Gij=⟨bi,bj⟩G_ij= b_i,b_j . Equivalently grouping the diagonal terms back into the quadratic term, the norm-generated part has the Koopmans–Beckmann form ∑p,qPpqGπp,πq. _p,qP_pqG_ _p, _q. The rank-one qualifier here applies to the positional coefficient matrix P=αα⊤P=α . The request Gram matrix G may have higher rank and the request vectors may have arbitrary dimension. Related work studies QAPs with rank-one cost matrices (Wang et al., 2021). Here we state the restriction directly in terms of P and G, and what the hardness construction adds is the realization of such an instance by positive, non-overshooting gradient steps. Linearizability is then a known characterization rather than something we establish. A symmetric Koopmans–Beckmann QAP is linearizable as a linear assignment objective if and only if at least one coefficient matrix is weak-sum, meaning Hij=ui+ujH_ij=u_i+u_j off diagonal (Punnen and Kabadi, 2013; Çela et al., 2014). What is specific to our instances is where that condition fails. For the position product matrix, Ppq+Prs−Ppr−Pqs=(αp−αs)(αq−αr).P_pq+P_rs-P_pr-P_qs=( _p- _s)( _q- _r). Four distinct geometric position weights therefore violate the condition. The same criterion identifies the exceptional request geometries through their Gram matrix G. Proposition 1 measures distance from assignment without assuming a scalar response, and applies here too. Using Tijpq=2ijpqT^pq_ij=2K_ijpq, independently least-squares project every off-diagonal slice onto aipq+βjpqa^pq_i+β^pq_j. Define C^i,p=Ci,p+∑q>paipq+∑q<pβiqp. C_i,p=C_i,p+ _q>pa^pq_i+ _q<pβ^qp_i. Then, up to the order-independent constant, J(π)−∑pC^πp,p=∑p<qΞπp,πqpq.J(π)- _p C_ _p,p= _p<q ^pq_ _p, _q. Every permutation selects exactly (k2) k2 residual entries, hence |∑p<qΞπp,πqpq|≤(k2)(∑p<q∑i≠j(Ξijpq)2)1/2. | _p<q ^pq_ _p, _q |≤ k2 ( _p<q _i≠ j( ^pq_ij)^2 )^1/2. Combining this uniform error with εsurr _ surr and applying the uniform regret bound proves the proposition. More generally, for predicted responses ei,pe_i,p and a quadratic terminal score ⟨g,δ⟩+12⟨δ,Hδ⟩ g,δ + 12 δ,Hδ , use Ci,p=⟨g,ei,p⟩+12⟨ei,p,Hei,p⟩,Tijpq=⟨ei,p,Hej,q⟩.C_i,p= g,e_i,p + 12 e_i,p,He_i,p , T^pq_ij= e_i,p,He_j,q . This is the form used by the projected retained-loss realization. Slice additivity is only sufficient. Cancellations across position pairs can make a tensor linearizable even when this residual is nonzero, and a large bound does not exclude another tractable representation. NP-completeness under positive small steps. To prove Proposition 4, reduce from Partition (Garey and Johnson, 1979). Given positive integers a1,…,aNa_1,…,a_N, set si=2ais_i=2a_i, k=2Nk=2N, and S=∑isiS= _is_i. Let =−(2N−1),…,−3,−1,1,3,…,2N−1C=\-(2N-1),…,-3,-1,1,3,…,2N-1\ be the centered odd position weights. In dimension N+1N+1, with standard basis e0,e1,…,eNe_0,e_1,…,e_N, create two requests for each item: bXi=Ωei+sie0,bYi=−Ωei−sie0,Ω=4NS+1.b_X_i= e_i+s_ie_0, b_Y_i=- e_i-s_ie_0, =4NS+1. Their sum is zero. If XiX_i and YiY_i receive weights cXic_X_i and cYic_Y_i, write di=cXi−cYid_i=c_X_i-c_Y_i. For vπ=∑pcpbπpv_π= _pc_pb_ _p, ‖vπ‖2=Ω2∑i=1Ndi2+(∑i=1Nsidi)2.\|v_π\|^2= ^2 _i=1^Nd_i^2+ ( _i=1^Ns_id_i )^2. (16) Every did_i is a nonzero even integer, so ∑idi2≥4N _id_i^2≥ 4N with equality exactly when |di|=2|d_i|=2. Weights in C differing by two form a path on 2N2N vertices whose perfect matching is unique by endpoint forcing, so equality means adjacent weights are paired and di=2σid_i=2 _i with σi∈−1,1 _i∈\-1,1\. Which pair goes to which item does not enter the objective. A proper pairing therefore has objective 4NΩ2+4(∑iσisi)2≤4NΩ2+4S24N ^2+4( _i _is_i)^2≤ 4N ^2+4S^2, while an improper one has some |di|≥4|d_i|≥ 4 and anchor term at least (4N+12)Ω2(4N+12) ^2. Since 12Ω2>4S212 ^2>4S^2, every global optimum is properly paired and minπ‖vπ‖2=4NΩ2+4minσ∈−1,1N(∑iσisi)2. _π\|v_π\|^2=4N ^2+4 _σ∈\-1,1\^N ( _i _is_i )^2. (17) It remains to embed these centered linear weights in a positive geometric response. Set B=Ω+SB= +S and η=1100B2k6,ρ=1−η.η= 1100B^2k^6, ρ=1-η. For position p=1,…,kp=1,…,k, let cp′=2(k−p)−(k−1)=k+1−2pc _p=2(k-p)-(k-1)=k+1-2p, which traverses C. Because ∑i(bXi+bYi)=0 _i(b_X_i+b_Y_i)=0, the constant term in (1−η)k−p(1-η)^k-p cancels. Taylor’s theorem, with (1−η)j=1−jη+rj(1-η)^j=1-jη+r_j and 0≤rj≤j(j−1)η2/20≤ r_j≤ j(j-1)η^2/2, writes the exact endpoint under Ui(w)=ρw+biU_i(w)=ρ w+b_i as wπ=−η2vπ+ξπw_π=- η2v_π+ _π. Since ∑p|cp′|=k2/2 _p|c _p|=k^2/2 and ‖bi‖≤B\|b_i\|≤ B, this gives ‖vπ‖≤Bk2/2\|v_π\|≤ Bk^2/2 and ‖ξπ‖≤Bk3η2/6\| _π\|≤ Bk^3η^2/6. Uniformly over permutations, |‖wπ‖2−η24‖vπ‖2| |\|w_π\|^2- η^24\|v_π\|^2 | ≤η‖vπ‖‖ξπ‖+‖ξπ‖2 ≤η\|v_π\|\| _π\|+\| _π\|^2 ≤B2k512η3+B2k636η4<η2100. ≤ B^2k^512η^3+ B^2k^636η^4< η^2100. (18) If the Partition instance is positive, Equation 17 has minimum 4NΩ24N ^2. Otherwise, every signed sum of the even sis_i has magnitude at least two, so the minimum is at least 4NΩ2+164N ^2+16. The rational threshold θ=η2(NΩ2+2)θ=η^2(N ^2+2) and Equation 18 strictly separate the two cases. All constructed rationals have polynomial bit length. Given a permutation, its rational endpoint and squared norm can be evaluated exactly with polynomially many bit operations, proving membership in NP. Finally, the opposite request pairs give ∑ibi=0 _ib_i=0, so with LR(w)=12‖w‖2L_R(w)= 12\|w\|^2 and LFi(w)=12‖w+bi/η‖2L_F_i(w)= 12\|w+b_i/η\|^2 both the full-data objective LR+∑iLFiL_R+ _iL_F_i and the final retain objective LRL_R have unique minimizer zero, while w−η∇(2LR(w)−LFi(w))=(1−η)w+biw-η∇(2L_R(w)-L_F_i(w))=(1-η)w+b_i. Each quadratic is an identity-design least-squares block, so the hard instance has an explicit fixed-anchor retain–forget implementation whose update objective has Hessian I, positive response, and step size strictly between zero and one. The construction has d=N+1=k/2+1d=N+1=k/2+1 and an instance-dependent ρ approaching one, and its fixed final-retain anchor is distinct from the prefix-changing retain loader used by NegGrad+. This boundary differs from the target-composition hardness of Kubo et al. (2024). Their strong-hardness construction for increasing linear functions uses translations x↦x+aix x+a_i together with maps whose slope is larger than one. It therefore does not directly cover the shared strict-contraction subclass here. Conversely, our Partition reduction is only weakly NP-hard, uses growing dimension, and lets ρ approach one; it isolates realizability by shared positive gradient steps rather than superseding their broader result. The construction and the small-step tractable regime are two sides of one expansion. A nonzero terminal anchor lets the first-order positional term dominate the O(η2)O(η^2) interactions, which is what makes small steps tractable there. Taking w0=zR=0w_0=z_R=0 removes that anchor, so a positive non-overshooting step alone does not imply easy exact optimization. A.3 Memory bounds and structural separation Nonlinear common-suffix proof. For u,v∈su,v _s, composition of the suffix maps gives ‖Us(u)−Us(v)‖≤κs‖u−v‖≤κsds.\|U_s(u)-U_s(v)\|≤ _s\|u-v\|≤ _sd_s. Applying the state objective’s Lipschitz constant on Us(s)U_s(X_s) gives the general bound Lj,sκsdsL_j,s _sd_s. For the squared objective the output difference is at most LΦκsdsL_ _sd_s, and writing a=Φ(Us(u))−zRa= (U_s(u))-z_R and b=Φ(Us(v))−zRb= (U_s(v))-z_R, |‖a‖2−‖b‖2|=|⟨a+b,a−b⟩|≤(‖a‖+‖b‖)‖a−b‖≤2RsLΦκsds. |\|a\|^2-\|b\|^2 |=| a+b,a-b |≤(\|a\|+\|b\|)\|a-b\|≤ 2R_sL_ _sd_s. Maximizing first within each suffix and then over suffixes proves Proposition 2 with Lj,s=2RsLΦL_j,s=2R_sL_ . The Lipschitz constants νs,t _s,t are available for the update rules used here. For one gradient step of size η on a region with μI⪯∇2ℓ⪯ΛIμ I ∇^2 I, ν≤max|1−ημ|,|1−ηΛ|ν≤ \|1-ημ|,|1-η |\. Affine suffix truncation and quadratic representation. Under the affine assumptions of Proposition 2(b), retain only the final L response terms: w~π,L w_π,L =Mkw0+∑r=0L−1Mrbπk−r, =M^kw_0+ _r=0^L-1M^rb_ _k-r, J~L(π) J_L(π) =‖w~π,L−zR‖22. =\| w_π,L-z_R\|_2^2. The omitted prefix contribution is hπ,L:=wπ−w~π,L=∑r=Lk−1Mrbπk−r.h_π,L:=w_π- w_π,L= _r=L^k-1M^rb_ _k-r. Using ‖M‖≤ρ<1\|M\|≤ρ<1 and ‖bi‖≤B\|b_i\|≤ B, ‖hπ,L‖≤δL:=B∑r=Lk−1ρr=BρL(1−ρk−L)1−ρ.\|h_π,L\|≤ _L:=B _r=L^k-1ρ^r=B ρ^L(1-ρ^k-L)1-ρ. (19) Moreover, ‖w~π,L−zR‖≤‖Mkw0−zR‖+B∑r=0L−1ρr≤‖Mkw0−zR‖+B1−ρ.\| w_π,L-z_R\|≤\|M^kw_0-z_R\|+B _r=0^L-1ρ^r≤\|M^kw_0-z_R\|+ B1-ρ. Since wπ=w~π,L+hπ,Lw_π= w_π,L+h_π,L, |J(π)−J~L(π)| |J(π)- J_L(π)| =|2⟨w~π,L−zR,hπ,L⟩+‖hπ,L‖2| = |2 w_π,L-z_R,h_π,L +\|h_π,L\|^2 | (20) ≤2(‖Mkw0−zR‖+B1−ρ)δL+δL2=:εL. ≤ 2 (\|M^kw_0-z_R\|+ B1-ρ ) _L+ _L^2=: _L. Hence ‖J−J~L‖∞≤εL=O(ρL)\|J- J_L\|_∞≤ _L=O(ρ^L), and the uniform regret bound gives Proposition 2(b). Importantly, truncation removes dependence on the distant prefix without removing interactions among the retained suffix requests. Writing w~π,L−zR=v+∑r<Ldπk−r,r, w_π,L-z_R=v+ _r<Ld_ _k-r,r, and expanding the squared norm gives J~L(π)=‖v‖2+∑r=0L−1(2v⊤dπk−r,r+‖dπk−r,r‖2)+2∑0≤r<s<Ldπk−r,r⊤dπk−s,s. J_L(π)=\|v\|^2+ _r=0^L-1 (2v d_ _k-r,r+\|d_ _k-r,r\|^2 )+2 _0≤ r<s<Ld_ _k-r,r d_ _k-s,s. (21) Thus suffix localization suppresses distant-prefix dependence while preserving arbitrary pairwise interactions within the retained suffix. Suffix-conditioned assignment. Fix an ordered length-L suffix s and write π=(σ,s)π=(σ,s), where σ contains the remaining k−Lk-L requests. Conditioning on s fixes both the suffix response and its interaction with the initial state. Let rs=Mkw0−zR+∑j<LMjbsL−j,ep(i)=Mk−pbi,r_s=M^kw_0-z_R+ _j<LM^jb_s_L-j, e_p(i)=M^k-pb_i, so that wπ−zR=rs+∑p≤k−Lep(σp).w_π-z_R=r_s+ _p≤ k-Le_p( _p). Expanding the squared norm separates the prefix dependence into unary and pairwise terms: J(π)=‖rs‖2+∑p≤k−L(2rs⊤ep(σp)+‖ep(σp)‖2)+2∑p<q≤k−Lep(σp)⊤eq(σq).J(π)=\|r_s\|^2+ _p≤ k-L (2r_s e_p( _p)+\|e_p( _p)\|^2 )+2 _p<q≤ k-Le_p( _p) e_q( _q). (22) The first two groups form an assignment objective over the prefix, with suffix-conditioned costs Ci,p(s)=2rs⊤ep(i)+‖ep(i)‖2.C^(s)_i,p=2r_s e_p(i)+\|e_p(i)\|^2. We therefore define J^L(π)=‖rs‖2+∑pCσp,p(s), J_L(π)=\|r_s\|^2+ _pC^(s)_ _p,p, which keeps the full unary effect of every prefix request and discards only prefix–prefix interactions. This conditioning is sharper than truncating the prefix. Every prefix position satisfies k−p≥Lk-p≥ L, so under ‖M‖≤ρ<1\|M\|≤ρ<1 and ‖bi‖≤B\|b_i\|≤ B, ‖ep(i)‖≤Bρk−p≤BρL.\|e_p(i)\|≤ Bρ^k-p≤ Bρ^L. Hence each discarded interaction contains two responses that have each passed through at least L further updates. Using Cauchy–Schwarz and the geometric series, |J(π)−J^L(π)| |J(π)- J_L(π) | =2|∑p<qep(σp)⊤eq(σq)| =2 | _p<qe_p( _p) e_q( _q) | (23) ≤2B2∑L≤u<t≤k−1ρt+u ≤ 2B^2 _L≤ u<t≤ k-1ρ^t+u (24) ≤B2(∑t≥Lρt)2=B2ρ2L(1−ρ)2. ≤ B^2 ( _t≥ Lρ^t )^2= B^2ρ^2L(1-ρ)^2. (25) Thus conditioning on the suffix improves the affine approximation rate from O(ρL)O(ρ^L) for prefix truncation to O(ρ2L)O(ρ^2L) by retaining the unary prefix effects and discarding only interactions between already attenuated prefix responses. Finally, there are k!/(k−L)!≤kLk!/(k-L)!≤ k^L ordered suffixes, and for each one the remaining prefix requires a single (k−L)×(k−L)(k-L)×(k-L) assignment solve. The resulting search therefore costs O(kL+3)O(k^L+3) for fixed L. Rate check for truncation and conditioning. The two exponents are claims about a rate, which the executed study tests at a single depth. We check them directly under exactly the shared-affine assumptions of Proposition 2, on 4040 synthetic instances at k=30k=30 with a five-dimensional state, fitting logεL _L against LlogρL ρ over L≤k/3L≤ k/3, where the prefix is still long enough for the rate to be observable (Table 2). The fitted exponents follow the predicted separation across all tested contractions, and the certificate B2ρ2L/(1−ρ)2B^2ρ^2L/(1-ρ)^2 holds at every tested length rather than only asymptotically. The errors are suprema over 2,0002,000 sampled orders, which lower-bound the supremum over SkS_k. Table 2: The two affine decay exponents come out as predicted. Fitted slopes of logεL _L against LlogρL ρ at k=30k=30, over 4040 instances per contraction. Proposition 2 predicts 11 for truncation, 22 for suffix-conditioned assignment, and hence a ratio of 22. ρ Truncation Conditioning Ratio 0.3 0.999 1.999 2.000 0.5 1.006 2.002 1.991 0.7 1.007 2.011 1.998 The rate comparison above holds at a fixed suffix depth. Reaching the same O(ρ2L)O(ρ^2L) error by truncating directly to depth 2L2L instead costs O(k2L)O(k^2L), so conditioning has the smaller exponent only for L>3L>3, with equality at L=3L=3. The case for conditioning at small L is therefore that it attains a rate the same depth of truncation does not, not that it is the cheaper route to that rate. Queue-length-uniform bounds. The absolute errors above are controlled by contraction, but the normalized structural errors also divide by the decision scale ΔJ _J. To separate these two effects, define the observable last-position signal μ1(k):=πJ(π)−mini[J(π)∣πk=i]. _1(k):=E_πJ(π)- _iE\! [J(π) _k=i ]. (26) It measures how much the expected objective can improve by choosing only the final request. Since every conditional mean is at least the global minimum, ΔJ=πJ(π)−minπJ(π)≥μ1(k). _J=E_πJ(π)- _πJ(π)≥ _1(k). Thus μ1(k) _1(k) is an observable lower bound on the normalization. Suffix width. If two orders π and π′π share the same ordered length-L suffix, then J~L(π)=J~L(π′) J_L(π)= J_L(π ). Equation 20 therefore gives |J(π)−J(π′)|≤|J(π)−J~L(π)|+|J(π′)−J~L(π′)|≤2εL.|J(π)-J(π )|≤|J(π)- J_L(π)|+|J(π )- J_L(π )|≤ 2 _L. Taking the maximum over orders with a common suffix yields WL≤2εL.W_L≤ 2 _L. (27) Corollary 5 (Queue-length-uniform structural bounds). For an ordered length-L suffix s, let LcondC_L cond contain functions of the form f(σs)=cs+∑p≤k−LCσp,p(s)f(σ s)=c_s+ _p≤ k-LC^(s)_ _p,p, and define Dcond(L):=2ΔJinff∈Lcond‖J−f‖∞.D_ cond(L):= 2 _J _f _L cond\|J-f\|_∞. Under Proposition 2(b), there exists a constant cρc_ρ, depending on ρ, B, and R0=supk‖Mkw0−zR‖R_0= _k\|M^kw_0-z_R\|, but not on k or L, such that DS,L≤2cρρLμ1(k),Dcond(L)≤2B2ρ2L(1−ρ)2μ1(k).D_S,L≤ 2c_ρ^L _1(k), D_ cond(L)≤ 2B^2ρ^2L(1-ρ)^2 _1(k). (28) The second bound applies to the suffix-conditioned family of Proposition 2(c). At L=0L=0, this family reduces to assignment, giving D≤2B2(1−ρ)2μ1(k).D_A≤ 2B^2(1-ρ)^2 _1(k). If, along a sequence of instances, the response constants remain uniformly bounded and the decision scale stays non-degenerate, infkμ1(k)=m>0 _k _1(k)=m>0, then any fixed normalized tolerance τ is achieved with L≥log(2cρ/(mτ))log(1/ρ)=O(log(1/τ)),L≥ (2c_ρ/(mτ)) (1/ρ)=O( (1/τ)), independently of k. The proof is immediate from the previous bounds. Equation 27 gives WL≤2εLW_L≤ 2 _L. Equation 19 gives δL≤BρL/(1−ρ) _L≤ Bρ^L/(1-ρ), and ‖M‖≤ρ<1\|M\|≤ρ<1 keeps R0=supk‖Mkw0−zR‖R_0= _k\|M^kw_0-z_R\| finite, so Equation 20 collapses to εL≤cρρL _L≤ c_ρ^L with cρc_ρ free of k and L. Dividing by ΔJ≥μ1(k) _J≥ _1(k) yields the first inequality. Likewise, dividing Equation 12 by the same lower bound gives the second. The non-degeneracy condition is essential. Contraction controls the numerator, whereas μ1(k) _1(k) controls whether the normalized decision scale remains visible as the queue grows. If every request behaves identically in the final position, then μ1(k)=0 _1(k)=0 and the bound becomes uninformative. This does not imply that ordering itself is irrelevant, only that last-position variation no longer lower-bounds ΔJ _J. The relevant scaling variables are therefore the contraction and the decision scale, rather than queue length by itself. Appending requests while keeping a fixed per-request contraction leaves the bound uniform in k. If the update instead becomes increasingly close to the identity as k grows, the generic argument no longer supplies a queue-length-independent depth, and the factor (1−ρk)−2(1- _k)^-2 also worsens. This deterioration of the upper bound is not an instance-wise lower bound on the suffix depth required. The same separation extends beyond affine dynamics. Under Proposition 2(a), DS,L≤2LΦmaxs(Rsκsds)μ1(k).D_S,L≤ 2L_ _s(R_s _sd_s) _1(k). Hence a policy family with Rsds≤CR_sd_s≤ C and κs≤qL _s≤ q^L uniformly in k inherits the same queue-length-uniform conclusion. We do not certify such uniform constants for the executed full-network policy. The larger-queue study therefore measures these quantities empirically rather than invoking this corollary. Strict separation between memory and additivity. Neither suffix localization nor position additivity implies the other, even under shared affine dynamics. We show the two directions by explicit constructions. Short memory does not imply additivity. Let w0=zR=0w_0=z_R=0 and M=(01/200),bi=(xi,xi)⊤,(x1,x2,x3,x4)=(−2,1,−1,2).M= pmatrix0&1/2\\ 0&0 pmatrix, b_i=(x_i,x_i) , (x_1,x_2,x_3,x_4)=(-2,1,-1,2). (29) Since M2=0M^2=0, only the final two requests affect the terminal state: wπ=Mbπ3+bπ4.w_π=Mb_ _3+b_ _4. Writing a=xπ3a=x_ _3 and b=xπ4b=x_ _4 gives J(π)=2b2+ab+14a2.J(π)=2b^2+ab+ 14a^2. (30) Thus J is constant over all prefixes sharing the same ordered two-request suffix, and hence W2=0W_2=0. The remaining suffix dependence is nevertheless not additive. Consider π(1)=(2,4,3,1),π(2)=(1,3,4,2),π(3)=(2,3,4,1),π(4)=(1,4,3,2).π^(1)=(2,4,3,1), π^(2)=(1,3,4,2), π^(3)=(2,3,4,1), π^(4)=(1,4,3,2). Any assignment objective f(π)=c+∑pCπp,pf(π)=c+ _pC_ _p,p satisfies f(π(1))+f(π(2))−f(π(3))−f(π(4))=0,f(π^(1))+f(π^(2))-f(π^(3))-f(π^(4))=0, (31) because every request–position term cancels in this signed contrast. For the true objective, Equation 30 gives the corresponding values 41/4,5,5,41/4,5,5, and 5/45/4, whose signed contrast is 99. Therefore, if ε=maxπ|J(π)−f(π)| = _π|J(π)-f(π)|, the triangle inequality gives 9≤4ε9≤ 4 , and hence inff∈maxπ|J(π)−f(π)|≥94. _f _π|J(π)-f(π)|≥ 94. (32) Direct enumeration gives πJ(π)=11524,minπJ(π)=1,ΔJ=9124,E_πJ(π)= 11524, _πJ(π)=1, _J= 9124, so D≥10891>1.D_A≥ 10891>1. Thus exact two-request suffix localization can coexist with a substantial failure of position additivity. Additivity does not imply short memory. For the reverse direction, take the one-dimensional instance M=45,w0=0,zR=1,b1=1,b2=b3=b4=0.M= 45, w_0=0, z_R=1, b_1=1, b_2=b_3=b_4=0. If request 11 occupies position p, then J(π)=[(45)4−p−1]2.J(π)= [ ( 45 )^4-p-1 ]^2. The objective therefore depends only on the request–position assignment, so D=0D_A=0. Its four position values, in units of 1/156251/15625, are 3721,2025,625,3721,2025,625, and 00, which gives ΔJ=637162500. _J= 637162500. However, fixing an ordered suffix of length two does not determine the objective: when request 11 lies outside the suffix, it may still occupy prefix position 11 or 22. Consequently, W2=3721−202515625=169615625,W2ΔJ=67846371>1.W_2= 3721-202515625= 169615625, W_2 _J= 67846371>1. Hence exact position additivity can coexist with substantial residual dependence on the prefix. A.4 From assignment to scalar sorting Scope of the slice projection. Proposition 1 certifies position additivity through one specific route, an independent additive projection of each request-pair slice. A small residual is therefore sufficient for approximate position additivity but not necessary. A coefficient tensor can be linearizable by a construction this projection does not find, so a large residual leaves the case uncertified rather than settled. How tight is the sorting certificate? Equation 10 is a sufficient bound, so a large value leaves a case uncertified rather than unstructured. Table 3 compares best-family error, the specific sorting surrogate, its certificate, and realized decision regret on the complete k=4k=4 surfaces. The certificate is conservative where the family fits. The worst softmax cases nevertheless lose more than the random-order gap, whereas the reported SalUn cases do not; median performance therefore does not make sorting uniformly safe. Double centering does not change the decision, only what the bound charges for it. Charging the position-only effect to the residual inflates the certificate by a median of 81%81\% across the 9595 complete surfaces the audit refits, with a range of 55 to 99%99\%, while leaving every selected order, every realized regret, and every centered score unchanged. Table 3: The sorting certificate is conservative where the family fits. Entries are medians with observed [min,max][ , ] across the complete k=4k=4 surfaces of each setting, all normalized by the random-order gap. D_A is the best assignment family’s uniform error, the sorting error is that of the surrogate sq⊤sq itself, the certificate is the right-hand side of Equation 10, and the realized regret is what the sorted order loses on the complete table. Setting Inst. D_A Sorting error Certificate Realized regret Frozen ridge, vision 15 0.0100.010 [0.001,0.066][0.001,0.066] 0.0590.059 [0.015,0.266][0.015,0.266] 0.0800.080 [0.021,0.375][0.021,0.375] 0.0000.000 [0.000,0.000][0.000,0.000] Frozen ridge, AG News 15 0.0180.018 [0.002,0.068][0.002,0.068] 0.0620.062 [0.017,0.319][0.017,0.319] 0.0820.082 [0.023,0.446][0.023,0.446] 0.0000.000 [0.000,0.092][0.000,0.092] Frozen ridge, 20 Newsgroups 15 0.0220.022 [0.002,0.126][0.002,0.126] 0.0740.074 [0.015,0.321][0.015,0.321] 0.1160.116 [0.022,0.473][0.022,0.473] 0.0000.000 [0.000,0.000][0.000,0.000] Direct softmax head 15 0.0350.035 [0.005,0.634][0.005,0.634] 0.0810.081 [0.017,2.616][0.017,2.616] 0.1300.130 [0.021,4.005][0.021,4.005] 0.0000.000 [0.000,1.248][0.000,1.248] Factorized softmax head 15 0.0650.065 [0.010,0.686][0.010,0.686] 0.5840.584 [0.117,2.523][0.117,2.523] 0.8720.872 [0.184,4.059][0.184,4.059] 0.0090.009 [0.000,1.789][0.000,1.789] NegGrad+ 10 0.2360.236 [0.119,0.391][0.119,0.391] 1.8671.867 [1.189,2.998][1.189,2.998] 2.6722.672 [1.807,4.966][1.807,4.966] 0.1220.122 [0.000,0.309][0.000,0.309] SalUn 10 0.6730.673 [0.215,1.030][0.215,1.030] 1.7341.734 [1.225,2.686][1.225,2.686] 2.2872.287 [1.655,4.297][1.655,4.297] 0.3220.322 [0.000,0.775][0.000,0.775] Linear-position projection proofs. For p=1,…,kp=1,…,k, let qp=p−(k+1)/2q_p=p-(k+1)/2, so ‖q‖22=k(k2−1)/12\|q\|_2^2=k(k^2-1)/12, and let H=I−1k⊤H=I- 1k11 . Writing a for the row means of C, b for its column means and m for its grand mean, C=HCH+a⊤+b⊤−m⊤,C=HCH+a1 +1b -m11 , and for any permutation Φa⊤(π)=∑iai _a1 (π)= _ia_i, Φb⊤(π)=∑pbp _1b (π)= _pb_p are constants, because each request and each position is used exactly once. Comparing permutations under C is therefore the same as comparing them under C¯=HCH C=HCH. Write C¯=P+Ξ¯q C=P+ _q with P=sq⊤P=sq and Ξ¯q=Ξ¯qq=0 _q1= _qq=0, which also leaves Ξ¯q _q column-centered since C¯ C is. For any permutation π, ΦP(π)=∑psπpqp. _P(π)= _ps_ _pq_p. Because qpq_p is strictly increasing, the rearrangement inequality shows that sorting sis_i nonincreasingly minimizes ΦP _P. This proves exact scalar collapse when Ξ¯q=0 _q=0. The centering never loosens the certificate. If C=a⊤+sq⊤+ΞqC=a1 +sq + _q is the one-sided projection, then applying H on both sides gives C¯=(Hs)q⊤+HΞqH C=(Hs)q +H _qH, since Hq=qHq=q and ⊤H=01 H=0. As Ξ¯q _q is the residual of the best such fit and H is an orthogonal projection, ‖Ξ¯q‖F≤‖HΞqH‖F≤‖Ξq‖F\| _q\|_F≤\|H _qH\|_F≤\| _q\|_F. The two projections also induce the same ordering, because they differ in s only by a constant shift, which the rearrangement inequality ignores. For the approximate result, let πC _C minimize ΦC¯ _ C and πs _s minimize ΦP _P. Then ΦC¯(πs)−ΦC¯(πC)≤ΦΞ¯q(πs)−ΦΞ¯q(πC)≤rangeπΦΞ¯q(π). _ C( _s)- _ C( _C)≤ _ _q( _s)- _ _q( _C) _π _ _q(π). If XπX_π is the permutation matrix selecting the entries summed by π, then ΦΞ¯q(π)−ΦΞ¯q(σ)=⟨Ξ¯q,Xπ−Xσ⟩≤‖Ξ¯q‖F‖Xπ−Xσ‖F≤2k‖Ξ¯q‖F. _ _q(π)- _ _q(σ)= _q,X_π-X_σ ≤\| _q\|_F\|X_π-X_σ\|_F≤ 2k\,\| _q\|_F. The last inequality uses that two permutation matrices differ in at most 2k2k unit entries. This bounds the regret of πs _s against the assignment objective ΦC _C. Adding the two uniform errors between J and ΦC _C, one at the selected order and one at the true optimum, gives Equation 10 with ε _A in place of the surrogate mismatch. Chaining part (a) supplies ε≤εsurr+(k2)‖Ξ‖F _A≤ _ surr+ k2\,\| \|_F, since the projected assignment differs from the shared quadratic surrogate by the interaction residual and the surrogate differs from J by εsurr _ surr. The alternative entrywise bound is rangeπΦΞ¯q(π)≤2k‖Ξ¯q‖∞range_π _ _q(π)≤ 2k\| _q\|_∞. Appendix B Experimental protocols This section defines how each experimental setting is executed and which executions count as valid. A setting fixes a policy, model, and data configuration, while an instance additionally fixes the requests, checkpoint, reference, and request-bound randomness. Permutations are deletion orders within an instance. Complete permutation surfaces support uniform statements over SkS_k, whereas identification and held-out splits support only statements on their declared samples. Frozen-head objectives are deterministic in double precision, and fixed-randomness repeats reproduce the full-network terminal objectives exactly. Results are reported in Appendices C and D. Table 4 records which full-network analyses reuse an instance. Seed labels are local identifiers: the same number at different queue lengths does not denote the same request set. Table 4: Full-network instance correspondence. “Main” means the complete k=4k=4 cohort used for structural summaries. Analysis Instances Relation to main k=4k=4 cohort NegGrad+ budget development seeds 0–2, k=4k=4 Same requests; alternate budgets NegGrad+ main seeds 0–9, k=4k=4 Complete 24-order surfaces SalUn pilot/replication seeds 0–2 / 3–9, k=4k=4 Matched request partitions by seed Composition seeds 0–2, k=5k=5 New five-request queues Held-out identification seeds 0–2, k=8k=8 New eight-request sampled designs Second tape / reference-free seeds 0–2, k=4k=4 Same requests/reference; separate 10,00010,000-audit replays Pooled policy control seeds 0–9, k=4k=4 Reuse NegGrad+ main instances Sampled versus uniform claims. When SkS_k is too large to enumerate, the largest residual observed on a sampled evaluation set is only a sample-level statistic. It does not certify the maximum over all permutations. We therefore restrict sampled errors to their declared evaluation sets. Uniform quantities such as D_A and DS,LD_S,L inherit the uniform regret guarantee only when their underlying error is controlled uniformly. At large k, such uniform control comes from Section 4, not from treating a sampled maximum as exhaustive. Information used by each construction. The structural constructions use different information regimes. A dynamics-based construction follows directly from the update equations. A reference-assisted construction uses terminal objectives together with a retraining reference to fit or evaluate a structural family. A probe-based construction instead uses the base model, request data, retained-data derivatives, and declared singleton probes. Constructions fixed on development executions before a new queue are prospective on that queue. Complete-table fits are retrospective. We separate reference generation, identification executions, offline fitting and solving, and candidate execution. One terminal-order query executes the full k-request sequence and evaluates its terminal objective. Identification executions are disjoint from held-out or newly executed evaluation orders. Table 5 reports counts, not FLOPs or wall-clock time; those depend on batch composition, forward/backward work, and evaluation and were not benchmarked here. Table 5: Information and execution costs by construction. “Seq.” counts terminal-order executions. Parentheses give optimizer updates when they follow directly from the protocol. Reference-assisted workflows include reference generation and are not claimed to be cheaper than retraining. Construction TreferenceT_ reference TidentificationT_ identification Tfit/solveT_ fit/solve TcandidateT_ candidate Ridge sorting Exact retain solve k seq. Least squares, sort 11 seq. Ridge assignment Exact retain solve (k−1)2+1(k-1)^2+1 seq. Minimax, Hungarian 11 seq. NegGrad+ k=8k=8 Two retain-only runs 112112 seq. (10,75210,752) Minimax, solve 11 seq. (9696) Head reconstruction Exact retain solve 00 seq.; k probes Construct, solve 11 seq. B.1 Frozen heads Ridge provides an exact retained reference for measuring endpoint prediction error and ordering regret. CIFAR-10 uses normalized penultimate features from a public ImageNet-pretrained ResNet-18 and a two-output ridge head with bias and λ=0.01λ=0.01. AG News and 20 Newsgroups use mean-pooled frozen DistilBERT embeddings, a shared data-independent 256-dimensional projection, and per-example normalization. The protocol fixes request size, train/validation splits, and the retained reference before selection. B.2 Full-network NegGrad+ Terminal comparison map. For each main-cohort instance, the first 2,000 examples of the fixed CIFAR-100 test split form the audit set; the remainder is used only for reported accuracies. The classifier predicts the 20 CIFAR-100 superclasses. If zw(x)∈ℝ20z_w(x) ^20 denotes its logits, the comparison map subtracts the mean across the 20 coordinates separately for each example. The terminal objective is j(w)=1||∑x∈‖zw(x)−z¯w(x)−(zR(x)−z¯R(x))‖22.j(w)= 1|A| _x \|z_w(x)- z_w(x)1- (z_R(x)- z_R(x)1 ) \|_2^2. Here zRz_R is the pointwise mean of two models trained from the declared initialization on the final retained training set. The audit examples and reference are fixed across every order of an instance. Only training data are used for request updates; the test audit set is read at terminal evaluation. The second-tape and reference-free controls reuse the seed-indexed requests and reference files but come from separate replays evaluated on all 10,000 test examples. They are therefore distinct policy–objective instances from the main 2,000-example cohort, even when their request labels match. Execution. Each request uses 12 NegGrad+ steps with learning rate 3×10−33× 10^-3 and minibatch size 256. The loss weights retained and forget cross-entropy by 0.950.95 and −0.05-0.05, respectively. Each request starts a fresh SGD optimizer with momentum 0.90.9 and weight decay 5×10−45× 10^-4. The updated model weights and batch-normalization state pass to the next request. Retain batches use the run’s CIFAR augmentation and forget batches do not. Operating point and validity. The 12-step operating point was fixed by the preceding pilot calibration using retained utility and order-mean progress toward the retraining reference; no ordering statistic or deleted-group screen selected it. The four-budget 3,12,24,48\3,12,24,48\ sweep was run afterward with model, requests, reference, and request-bound randomness held fixed. Under the three screens reported here, 12 steps is the only tested budget that passes on all three development instances. The deleted-group screen is therefore a retrospective audit, not a backdated selection rule. Per-instance values for the retain-weight sweep at fixed step size are in the repository. Structure across the budget sweep. The same four budgets also carry structural coordinates, which the selection did not look at (Table 6). Nominal update count does not order suffix attenuation monotonically, and assignment error has no corresponding trend. The effective suffix depth changes across the sweep, but all alternative budgets fail at least one deletion-quality screen. We therefore treat this as operating-region sensitivity and ground the causal mechanism claim on the damped-Newton intervention of Appendix C.2, where contraction is fixed before execution. Table 6: Structural coordinates across the update-strength sweep. Entries are medians with observed [min,max][ , ] over the same three development instances, on complete k=4k=4 surfaces. “Valid seeds” counts the instances passing all three reported screens. History retention is the measured matched-history attenuation, and DS,1D_S,1 and DS,2D_S,2 are the suffix errors at one and two positions. Steps/request Valid seeds History retention DS,1D_S,1 DS,2D_S,2 D_A 3 0/3 0.3180.318 [0.312,0.321][0.312,0.321] 1.3621.362 [0.843,1.399][0.843,1.399] 0.5150.515 [0.341,0.531][0.341,0.531] 0.4430.443 [0.260,0.512][0.260,0.512] 12 3/3 0.0650.065 [0.059,0.066][0.059,0.066] 0.5980.598 [0.573,0.883][0.573,0.883] 0.2210.221 [0.204,0.286][0.204,0.286] 0.3020.302 [0.265,0.441][0.265,0.441] 24 2/3 0.1180.118 [0.108,0.127][0.108,0.127] 0.3940.394 [0.363,0.417][0.363,0.417] 0.1490.149 [0.117,0.202][0.117,0.202] 0.2210.221 [0.166,0.229][0.166,0.229] 48 0/3 0.2780.278 [0.225,0.312][0.225,0.312] 0.9930.993 [0.840,1.167][0.840,1.167] 0.6730.673 [0.497,0.892][0.497,0.892] 0.2560.256 [0.198,0.378][0.198,0.378] At step t the retain loader is the complement of every request deleted through that step, Rt=∖⋃s≤tFπsR_t=D _s≤ tF_ _s, so deleted samples are never reintroduced as retain data. All ten reported instances satisfy the retained-utility criterion, worst-order retain accuracy at least min(Abase,Aretrain)−0.05 (A_ base,A_ retrain)-0.05, and the reference-progress criterion, order-mean terminal output closer to the retraining reference than the base output. The deleted-group accuracy screen is reported as an additional retrospective check. All ten pass, with a smallest decrease of 0.1200.120, so the measured rebound reflects recovery under later updates. B.3 Full-network SalUn Execution. SalUn is executed from the authors’ implementation. Each request uses 12 steps with learning rate 10−410^-4 and minibatch size 256, a fresh SGD optimizer per request with momentum 0.90.9 and weight decay 5×10−45× 10^-4, retain-only augmentation, and batch-normalization in training mode. The updated weights and batch-normalization state pass to the next request, as for NegGrad+. At every request, the mask is recomputed from the current model by accumulating absolute gradients of the negated forget loss and globally selecting the top 50%50\% of parameter coordinates. The authors’ random-label update is then applied only on those coordinates. Its NumPy and PyTorch draws are seeded from the request-bound generator; forget examples are unaugmented, and a retained sample fills the fixed 12×25612× 256-example pass. Operating point and validity. SalUn uses the 12-step budget fixed previously by the full-network protocol rather than a SalUn-specific sweep. At this operating point all ten instances satisfy the same retained-utility, reference-progress and deleted-group checks, with worst-order retain accuracy 0.8470.847–0.8980.898, reference-distance ratios of 0.6310.631–0.7530.753, and deleted-group accuracy falling by 0.1140.114–0.1750.175 against the screen’s 0.050.05. No structural diagnostic enters any of these checks. Appendix C Mechanisms and structural diagnostics This appendix carries the evidence for where the observed reductions come from and the controls that separate them from family flexibility. The ledgers below record the diagnostics summarized by Figure 2. Table 7 compares the structural regimes on surfaces enumerated in full. The settings do not share a single sufficient family: position additivity dominates the frozen-head surfaces, while suffix localization distinguishes the complete full-network surfaces from the ridge extension. Objectives and normalizations are setting-specific, so entries compare instances within a setting rather than across settings. For complete permutation surfaces, D_A is the exact best assignment-family error over all k!k! orders and DSD_S the exact suffix family error. The two sampled designs carry a different quantity and are reported with the identification results in Appendix D. Table 7: Structural regimes on the completely enumerated surfaces. Entries are medians across instances with observed [min,max][ , ]. Gap is 100ΔJ/J¯100 _J/ J, every error is exact over all k!k! orders, and the last two columns count the instances whose assignment and suffix errors fall below one. All suffix fits condition on the final two requests. Setting Req. Inst. Gap (%) D_A DSD_S A pass S pass Ridge head 4 45 0.8780.878 [0.063,11.659][0.063,11.659] 0.0180.018 [0.001,0.126][0.001,0.126] 0.5620.562 [0.427,0.658][0.427,0.658] 45/45 45/45 Direct head 4 15 0.0760.076 [0.003,1.055][0.003,1.055] 0.0350.035 [0.005,0.634][0.005,0.634] 0.5890.589 [0.492,1.700][0.492,1.700] 15/15 13/15 Factorized head 4 15 0.8110.811 [0.073,1.446][0.073,1.446] 0.0650.065 [0.010,0.686][0.010,0.686] 0.5470.547 [0.383,1.303][0.383,1.303] 15/15 14/15 Ridge head 8 3 0.8380.838 [0.824,0.996][0.824,0.996] 0.0170.017 [0.015,0.021][0.015,0.021] 1.2901.290 [1.287,1.318][1.287,1.318] 3/3 0/3 NegGrad+ 4 10 9.2859.285 [3.407,15.201][3.407,15.201] 0.2360.236 [0.119,0.391][0.119,0.391] 0.1480.148 [0.055,0.477][0.055,0.477] 10/10 10/10 NegGrad+ 5 3 9.6479.647 [3.660,13.805][3.660,13.805] 0.1860.186 [0.150,0.771][0.150,0.771] 0.2380.238 [0.227,0.582][0.227,0.582] 3/3 3/3 SalUn 4 10 8.4888.488 [5.831,13.501][5.831,13.501] 0.6730.673 [0.215,1.030][0.215,1.030] 0.2600.260 [0.185,0.510][0.185,0.510] 9/10 10/10 C.1 Position additivity from update dynamics Cumulative-response construction. Let uiu_i be the singleton displacement and set M=(I−ηHR)TM=(I-η H_R)^T for a budget of T steps. A request deleted at position p remains absent in every later stage, giving the shared-curvature response ei,p=∑t=0k−pMtui,p=1,…,k.e_i,p= _t=0^k-pM^tu_i, p=1,…,k. (33) For 1≤p≤k−21≤ p≤ k-2, direct subtraction yields ei,p+2−2ei,p+1+ei,p=Mk−p−1(M−I)ui.e_i,p+2-2e_i,p+1+e_i,p=M^k-p-1(M-I)u_i. (34) The telescoping identity for M implies ‖M−I‖≤Tη‖HR‖max1,‖I−ηHR‖T−1.\|M-I\|≤ Tη\|H_R\| \1,\|I-η H_R\|\^T-1. If the singleton gradient norm is at most GiG_i along its T steps, then ‖ui‖≤TηGi\|u_i\|≤ Tη G_i and ‖ei,p+2−2ei,p+1+ei,p‖≤T2η2‖M‖k−p−1‖HR‖Gimax1,‖I−ηHR‖T−1.\|e_i,p+2-2e_i,p+1+e_i,p\|≤ T^2η^2\|M\|^k-p-1\|H_R\|G_i \1,\|I-η H_R\|\^T-1. (35) Thus the cumulative response is affine in position up to second order in the step size for fixed T and k. From the retained recurrence to the terminal objective. The executed ridge policy minimizes a mean retained loss, so its normalization changes with the stage. Let the full training set have size N, let every request have size m, and let nt=N−tmn_t=N-tm after stage t. If rir_i is the sum of the unregularized per-example gradients in request i, expansion of the actual T-step recurrence at the full-data optimum gives, uniformly over the finite set of orders, wπ(η)=w0+ηc+Tη∑p=1khprπp+O(η2),hp=∑t=pk1nt,w_π(η)=w_0+η c+Tη _p=1^kh_pr_ _p+O(η^2), h_p= _t=p^k 1n_t, (36) where c is independent of π. Expanding the squared-distance objective around w0w_0 therefore gives a scalar request–position objective with profile h plus an O(η2)O(η^2) remainder. The exact profile is not fixed-q because ntn_t changes. For fixed k, hp=(k−p+1)/N+O(m/N2)h_p=(k-p+1)/N+O(m/N^2). Consequently, projection onto fixed-q has both a small first-order normalization term and a second-order dynamics term. If the first-order order variation is nonzero, ΔJ=Θ(η) _J= (η), while DsortD_ sort need not scale quadratically. This derivation is specific to the matched ridge recurrence and does not convert the finite-sample sweep into an asymptotic certificate. Matched step-size intervention. We fixed T=4T=4 gradient steps per request, the five held-out CIFAR-10 request partitions, the base ridge head, and every exact retained-data reference, and varied only the learning rate over 0.5η00.5 _0, η0 _0, 1.5η01.5 _0, and 2η02 _0, where η0=0.526 _0=0.526. All 20 matched configurations contained 65 independently replayed prefixes and 24 finite terminal objective values. The largest product of learning rate and retained Hessian eigenvalue was 1.801<21.801<2. The recurrence-specific residual has fixed-effect log–log slope 1.9711.971. Its near-quadratic growth is consistent with the positional-curvature calculation in Equation 35 and the second-order remainder in Equation 36. Figure 5: Positional-profile error grows at the second-order rate predicted by the update expansion. The upper panel shows absolute order gap and profile residual against learning rate, and the lower panel the same residual normalized by the gap. Figure 5 shows every configuration of that sweep, in absolute terms and normalized by each configuration’s gap. Here h is the recurrence-specific profile in Equation 36. Its residual is smaller than the fixed linear-position profile in all 20 matched partition–step-size configurations. Shared-response quadratic closure. We reused the singleton displacements and shared response from the pre-outcome analysis, and used the exact retained reference only for this retrospective comparison. The linear surrogate scores the predicted displacement by its first-order inner product with w0−wRw_0-w_R. The quadratic surrogate instead evaluates the exact squared norm of that same predicted endpoint, thereby adding precisely the interactions in Equation 8. Nothing about the response model, requests, or reference changed between the two columns. This comparison tests the terminal-objective consequence of the derived shared response, but does not assert that the actual ridge execution has one fixed response matrix. Its retained Hessian changes with the deleted request set. Table 8 reports the two scorings. Table 8: Quadratic terminal scoring captures interactions missed by linear scoring. Entries are medians over five partitions and three update budgets. Errors are normalized as 2ε/ΔJ2 / _J. Domain Linear terminal Quadratic terminal Residual ratio Vision 0.1450.145 0.0060.006 0.0410.041 AG News 0.1410.141 0.0060.006 0.0430.043 20 Newsgroups 0.2120.212 0.0090.009 0.0450.045 C.2 Suffix localization from contraction Exact contraction under damped Newton. Both frozen-ridge update rules are affine in the weights, so the Lipschitz constants that Proposition 2(a) multiplies are not estimated. Writing Ht=Xr⊤Xr/nr+λIH_t=X_r X_r/n_r+λ I for the retained Hessian and g=Htw−btg=H_tw-b_t for the gradient, T gradient steps give Mt=(I−ηHt)TM_t=(I-η H_t)^T, while the damped Newton step w↦w−δHt−1gw w-δ H_t^-1g gives Mt=I−δHt−1Ht=(1−δ)I.M_t=I-δ H_t^-1H_t=(1-δ)I. The Hessian cancels, so at δ=0.5δ=0.5 the ordered-suffix products are κ1=0.5 _1=0.5 and κ2=0.25 _2=0.25 for every partition, request and suffix. Each step’s Jacobian depends only on which requests have been deleted when it runs, and for a fixed ordered suffix that set does not depend on the prefix, which is why the suffix map is well defined. Measuring the realized attenuation ‖Us(u)−Us(v)‖/‖u−v‖\|U_s(u)-U_s(v)\|/\|u-v\| of every pair of prefixes entering the same suffix reproduces these constants exactly under Newton and never exceeds them under gradient descent, where κ1 _1 is 0.99470.9947 at one step and 0.91900.9190 at sixteen. Matched gradient–Newton intervention. Development used three instances. The prediction was then frozen before any held-out Newton table existed. Two things were frozen, and they carry different weight. Reproducing the analytic constants above is an implementation check. The Jacobian is (1−δ)I(1-δ)I by construction, so a run disagreeing with it indicates a fault in the harness. The prespecified structural prediction is separate and falsifiable, and concerns the relative movement of the suffix errors against their equal-capacity prefix and middle controls as the contraction changes. The bound of Proposition 2(a) also involves RsR_s and dsd_s, and it predicts nothing about the direction the controls take. The five held-out partitions are matched to the archived gradient instances on checkpoint, feature extractor, request sample ids, λ, learning rate and step scale. Only the preconditioner differs. The held-out intervention supports the prespecified separation: stronger analytic contraction favors the suffix family relative to its matched positional controls. The archived gradient surfaces do not show that separation, so the result concerns where positional memory resides rather than a uniform reduction in family error (Table 9). Table 9: Matched gradient descent and damped Newton differ in which positional families suffice. Entries are medians with observed [min,max][ , ] across the five held-out partitions. Scale is 100ΔJ/J¯100 _J/ J. Update rule Scale (%) D_A DS,1D_S,1 DS,2D_S,2 DP,2D_P,2 Gradient descent 0.5650.565 0.0030.003 1.0951.095 0.5430.543 0.5590.559 [0.416,0.806][0.416,0.806] [0.001,0.005][0.001,0.005] [1.000,1.169][1.000,1.169] [0.496,0.579][0.496,0.579] [0.512,0.599][0.512,0.599] Damped Newton 31.68431.684 0.1110.111 0.5970.597 0.1430.143 1.4881.488 [29.902,47.809][29.902,47.809] [0.052,0.283][0.052,0.283] [0.555,0.768][0.555,0.768] [0.133,0.203][0.133,0.203] [1.268,1.605][1.268,1.605] Damping sweep. The damped Newton Jacobian is (1−δ)I(1-δ)I, so the one-step contraction κ1=1−δ _1=1-δ is set by the damping and known before execution. The same five partitions were re-executed at three further damping values, changing nothing else. Those three were fixed before their outcomes were observed, and δ=0.5δ=0.5 had been evaluated previously. Table 10 reports every partition at every damping. Table 10: Analytically stronger Newton contraction progressively favors suffix-localized structure. Entries are medians with observed [min,max][ , ] across the same five instances, with both scale columns in percent and j0=j(w0)j_0=j(w_0) the objective at the undeleted state. κ1 _1 δ ΔJ/J¯ _J/ J ΔJ/j0 _J/j_0 D_A DS,1D_S,1 DS,2D_S,2 DP,2D_P,2 DM,2D_M,2 0.900.90 0.100.10 8.2638.263 [6.563,11.721][6.563,11.721] 5.0385.038 [3.999,7.118][3.999,7.118] 0.0220.022 [0.011,0.059][0.011,0.059] 1.0631.063 [0.951,1.105][0.951,1.105] 0.4870.487 [0.431,0.495][0.431,0.495] 0.7200.720 [0.614,0.740][0.614,0.740] 1.7551.755 [1.559,1.840][1.559,1.840] 0.750.75 0.250.25 19.49219.492 [16.593,28.456][16.593,28.456] 5.7695.769 [4.890,8.202][4.890,8.202] 0.0600.060 [0.028,0.159][0.028,0.159] 0.9100.910 [0.819,1.015][0.819,1.015] 0.3470.347 [0.312,0.368][0.312,0.368] 0.9910.991 [0.810,1.016][0.810,1.016] 1.8081.808 [1.602,1.957][1.602,1.957] 0.500.50 0.500.50 31.68431.684 [29.902,47.809][29.902,47.809] 2.8372.837 [2.561,3.885][2.561,3.885] 0.1110.111 [0.052,0.283][0.052,0.283] 0.5970.597 [0.555,0.768][0.555,0.768] 0.1430.143 [0.133,0.203][0.133,0.203] 1.4881.488 [1.268,1.605][1.268,1.605] 2.0512.051 [1.742,2.182][1.742,2.182] 0.250.25 0.750.75 37.59537.595 [34.761,56.612][34.761,56.612] 0.7100.710 [0.555,0.905][0.555,0.905] 0.0930.093 [0.047,0.221][0.047,0.221] 0.2470.247 [0.222,0.408][0.222,0.408] 0.0350.035 [0.032,0.067][0.032,0.067] 1.8691.869 [1.795,2.124][1.795,2.124] 2.0592.059 [1.946,2.325][1.946,2.325] The two scale columns move differently: stronger damping sharpens the structure of the ordering problem while eventually shrinking what ordering is worth relative to the fixed starting distance. The intervention therefore separates structural simplicity from decision scale rather than supporting a claim about deployment value. The realized contractions match their analytic values on every instance–damping pair. Stronger damping separates the suffix families from the equal-capacity positional controls, whereas assignment error is non-monotone. Absolute suffix width is non-monotone as well, so the separation is not an effect of the shared normalization. Matched-history attenuation. We compare histories that delete the same two requests in opposite orders and then apply the same two-request suffix with request-bound randomness (Table 11). Table 11: Matched histories contract in output space and in the terminal objective under a common suffix. Statistics aggregate 120 matched paths from ten request sets. Output separation is RMS logit distance, and alignment is the absolute objective difference divided by its Cauchy bound 2‖m−zR‖RMS‖d‖RMS2\|m-z_R\|_ RMS\|d\|_ RMS, whereas jRMSj_ RMS is a mean squared distance. Common suffix Output RMS |jRMS(z)−jRMS(z′)||j_ RMS(z)-j_ RMS(z )| Cauchy bound Alignment Before 2.025 0.621 12.664 0.052 After one request 0.211 0.079 1.292 0.069 After two requests 0.130 0.045 0.760 0.058 Let dz=20||d_z=20|A| be the number of centered-logit coordinates and define jRMS(z)=dz−1‖z−zR‖22j_ RMS(z)=d_z^-1\|z-z_R\|_2^2. The main full-network objective is j(z)=20jRMS(z)j(z)=20j_ RMS(z): it averages squared Euclidean distance across audit examples but sums over the 20 superclass coordinates. This constant factor does not affect attenuation ratios or alignment, while the absolute objective differences and bounds in Table 11 use per-coordinate MSE units. For d=z−z′d=z-z and m=(z+z′)/2m=(z+z )/2, the exact identity jRMS(z)−jRMS(z′)=(2/dz)⟨m−zR,d⟩j_ RMS(z)-j_ RMS(z )=(2/d_z) m-z_R,d holds on every pair. From the initial prefix to the completed common suffix, median output retention is 6.62%6.62\% and median absolute-objective-difference retention is 6.69%6.69\%. Their agreement, together with the stable alignment fraction, attributes the smaller objective width primarily to output attenuation. Because d is observed, this is a finite-execution consistency analysis. Run on the three matched pilots per policy that store prefix states, the same comparison leaves a median objective-difference retention of 6.9%6.9\% under NegGrad+, observed range [6.5,7.2][6.5,7.2], and 10.2%10.2\% under SalUn, observed range [10.1,10.5][10.1,10.5]. The next experiment evaluates held-out transitions. Conditioning versus truncation. Proposition 2 states two rates at a fixed suffix depth, O(ρL)O(ρ^L) for truncation and O(ρ2L)O(ρ^2L) for conditioning, and this is where the two are measured against each other on executed surfaces. The comparison needs a design the conditional family cannot saturate. At k=4k=4 with L=2L=2 each suffix leaves two prefix orders that an assignment fits exactly, so an error of zero there would report capacity. We therefore use the complete k=5k=5 NegGrad+ surfaces at L=1L=1, where each of the five suffixes leaves 2424 prefix orders against ten free parameters, 5050 in rank across the 120120 orders. Conditioning is more accurate than either nested comparator on every instance. This checks the construction at one depth on a design where the conditional family has ample room to miss. Establishing the exponent would require varying L or ρ. Because the three nested complete-table families have unequal rank, the main text separately compares first-, third-, and final-position conditioning at matched rank 50. Its four folds are fixed from cyclic relabeling orbits before outcomes are read; every 90-order training design has full rank and balanced conditioned-request counts. For fold f, define the training-only center and scale J¯ftrain=1|Tftrain|∑π∈TftrainJ(π),Δftrain=J¯ftrain−minπ∈TftrainJ(π), J_f train= 1|T_f train| _π∈ T_f trainJ(π), _f train= J_f train- _π∈ T_f trainJ(π), and J~ftrain(π)=(J(π)−J¯ftrain)/Δftrain J_f train(π)=(J(π)- J_f train)/ _f train. Each family ℱrF_r is fitted by g^r,f∈argming∈ℱrmaxπ∈Tftrain|J~ftrain(π)−g(π)|,J^r,f(π)=J¯ftrain+Δftraing^r,f(π). g_r,f∈ _g _r _π∈ T_f train| J_f train(π)-g(π)|, J_r,f(π)= J_f train+ _f train g_r,f(π). If the minimax solution is nonunique, a pre-fixed tie rule minimizes the prediction norm ∑π∈S5g(π)2 _π∈ S_5g(π)^2; this uses the complete permutation design but no held-out outcome. Only evaluation uses the complete-surface headroom ΔJ _J: Dr,ftest=2ΔJmaxπ∈Tf|J(π)−J^r,f(π)|.D_r,f test= 2 _J _π∈ T_f|J(π)- J_r,f(π)|. Thus the fitted original-scale predictions depend only on the training outcomes. The final-position model wins both controls in every instance–fold comparison. This supports positional specificity, not the affine decay exponent. C.3 Separation of structural families Nested position families. Table 12 compares three nested position families. The linear family fixes the shared positional profile, the monotone family learns that profile jointly with one score per request, and assignment allows an unrestricted request–position cost matrix. The monotone fit is retrospective and non-convex. The reported value is the best of the two search procedures fixed in advance, which agree to 5×10−55× 10^-5 on every surface. Table 12: Nested position families separate fixed-profile sorting, learned-profile sorting, and unrestricted assignment. DlinD_ lin fixes a shared linear positional profile, DmonoD_ mono learns a shared monotone profile, and D_A is unrestricted. R is the normalized regret of the selected order. The last column counts instances meeting, on, and failing the criterion for DmonoD_ mono, with the boundary band [0.95,1.05][0.95,1.05]. Setting Instances DlinD_ lin DmonoD_ mono D_A RmonoR_ mono R_A m/b/f Frozen ridge, vision 15 0.0560.056 0.0110.011 0.0100.010 0.0000.000 0.0000.000 15/0/0 Frozen ridge, AG News 15 0.0550.055 0.0260.026 0.0180.018 0.0000.000 0.0000.000 15/0/0 Frozen ridge, 20 Newsgroups 15 0.0610.061 0.0550.055 0.0220.022 0.0000.000 0.0000.000 15/0/0 Direct softmax head 15 0.0710.071 0.0680.068 0.0350.035 0.0000.000 0.0000.000 14/0/1 Factorized softmax head 15 0.5450.545 0.3050.305 0.0650.065 0.0090.009 0.0000.000 13/0/2 NegGrad+ 10 1.5821.582 0.2810.281 0.2360.236 0.1220.122 0.0640.064 10/0/0 SalUn 10 1.3461.346 0.8570.857 0.6730.673 0.3480.348 0.2560.256 6/1/3 The learned profile nearly closes the gap to assignment for NegGrad+, whereas SalUn exhibits substantially greater instance-to-instance variation. The apparent failure of scalar sorting under a fixed linear profile therefore does not extend to the more general shared-profile family. Matched parameterization intervention. We compare direct logistic regression with its function-matched factorization W=VUW=VU on held-out request unions. All configurations passed the frozen validity criteria. Factorization increased the paired order range in 14/15 instances and changed the optimal order in 8/15. Assignment met D<1D_A<1 in every instance and was substantially tighter than scalar sorting. The initial predictor and executed objective were matched, so the contrast isolates the update parameterization. Within-suffix interaction. The suffix criterion can be met for two different reasons. Either the final two positions contribute additively, in which case the suffix structure is the tail of an assignment cost matrix, or the two surviving requests interact. Table 13 separates them by restricting the same family to c+uπk−1+vπkc+u_ _k-1+v_ _k. The additive family is contained in the general one, so the difference is exactly the within-suffix interaction, and it is contained in assignment, so D_A lower-bounds it. Table 13: General suffix localization can retain interactions that an additive suffix cannot represent. Entries are medians across instances with observed [min,max][ , ] on complete full-network permutation surfaces. All suffix fits condition on the final two requests. Setting Instances DSD_S DSaddD_S add D_A NegGrad+ 10 0.1480.148 [0.055,0.477][0.055,0.477] 0.2930.293 [0.146,0.489][0.146,0.489] 0.2360.236 [0.119,0.391][0.119,0.391] NegGrad+ (k=5k=5) 3 0.2380.238 [0.227,0.582][0.227,0.582] 0.2380.238 [0.230,0.924][0.230,0.924] 0.1860.186 [0.150,0.771][0.150,0.771] SalUn 10 0.2600.260 [0.185,0.510][0.185,0.510] 0.7460.746 [0.335,1.139][0.335,1.139] 0.6730.673 [0.215,1.030][0.215,1.030] SalUn shows a material gap between general and additive suffix fits, unlike NegGrad+. Its localized dependence therefore retains interactions that cannot be represented as separate costs for the final two positions. Equal-capacity positional controls. To test whether suffix fits are favored merely by flexibility, we compare them with arbitrary functions of the requests occupying the first L positions or a fixed contiguous middle block. Each family has k!/(k−L)!k!/(k-L)! groups, and all widths use the same ΔJ _J normalization (Table 14). Table 14: Equal-capacity positional controls distinguish suffix localization from generic low-dimensional dependence. Prefix, middle, and suffix families condition on the same number of ordered positions and use the same ΔJ _J normalization. Instances L Prefix Middle Suffix k=4k=4 (10) 1 2.137 2.192 0.368 2 1.926 2.096 0.148 k=5k=5 (3) 1 2.254 2.244 0.331 2 2.232 2.243 0.238 The matched controls favor suffix localization overall, although less uniformly than the damped-Newton intervention. This comparison isolates recency from generic conditioning capacity but does not construct an online suffix score. Queue-length extension at k=5k=5. The extension keeps the NegGrad+ policy fixed and changes only the number of superclass requests from four to five. Each seed contains all 120 orders and 325 nonempty prefix executions, and Table 15 gives the resulting widths. Table 15: At k=5k=5, the general suffix error separates prefix memory from additive suffix structure. All entries are normalized by the total ordering gap ΔJ _J. Seed Suffix L=1L=1 General suffix L=2L=2 Additive suffix L=2L=2 Assignment 0 0.327 0.227 0.230 0.186 1 1.005 0.582 0.924 0.771 2 0.331 0.238 0.238 0.150 The extension supports suffix localization while leaving room for within-suffix interactions. The strict separation is supplied by Proposition 3; this experiment does not estimate a contraction parameter. C.4 Nonlinear reach of the suffix bound Direct-head analytic bound. Proposition 2(a) is the one quantitative result that covers updates which are not affine, so how much it delivers on an executed nonlinear head sets what we are entitled to say about the full-network policies. The direct head appends a constant feature for bias and regularizes the entire two-class weight matrix, including that coordinate. Each deletion transition uses one, four, or sixteen ordinary full-batch SGD steps with learning rate 0.050.05, mean cross-entropy, λ=10−4λ=10^-4, and fresh optimizer state. For a retained design X, the softmax Hessian therefore lies between λIλ I and (λ+‖X‖22/(2n))I(λ+\|X\|_2^2/(2n))I. We compute the resulting contraction factor separately for the two retained sets in every ordered suffix and use the exact operator norm of the validation design as LΦL_ . The comparison uses every one of the 15 matched direct-head instances. None is selected by its gap or by bound tightness. Median analytic two-stage contraction factors are 0.999990.99999, 0.999960.99996, and 0.999840.99984 across the three budgets, and the corresponding finite-pair endpoint ratios are 0.9960.996, 0.9780.978, and 0.9190.919. The latter are trajectory diagnostics rather than regional Lipschitz constants. The global objective bound holds for every suffix in every instance, and Table 16 reports how conservative it is on absolute and decision-normalized scales. The analytic bound remains valid but conservative on the executed nonlinear heads. We therefore use it as a sufficient-condition check, ground the mechanism claim in the matched Newton intervention, and treat full-network attenuation as finite-execution evidence. Table 16: The analytic common-suffix bound holds on executed direct-head trajectories with roughly an order of magnitude to spare. Entries are medians over five partitions. Curvature constants are global to each retained design, while reachable-state diameters and target radii are evaluated on the executed instances. ℬ2B_2 is the bound of Equation 11. Steps W2W_2 ℬ2B_2 ℬ2/W2B_2/W_2 DSD_S ℬ2/ΔJB_2/ _J 1 2.39×10−82.39×10^-8 1.68×10−71.68×10^-7 9.24 0.623 5.85 4 8.84×10−88.84×10^-8 6.66×10−76.66×10^-7 9.78 0.614 6.05 16 2.65×10−72.65×10^-7 2.51×10−62.51×10^-6 11.93 0.575 6.86 Appendix D Out-of-sample structural identification This appendix asks whether structural families identified from limited information continue to predict orders that were not used to construct them. The budgets run from no terminal-order queries at all, through bases of size O(k)O(k) and O(k2)O(k^2), to a balanced 112-query full-network design. Table 18 carries the structural diagnostics for the two settings whose order space is too large to enumerate. D.1 Probe-based structural reconstruction The lowest budget uses no terminal-order queries at all. The constructions in Figure 2b read the k singleton responses and the retained derivatives, and their values are reported on queues held out of the earlier retained-loss development. The unary quadratic construction carries no cross-request interaction and is the one the interaction term separates from (Table 17). The comparative ordering of the four remains the same on the held-out queues, although their numerical values also change. Fitting the assignment family directly to the complete terminal-objective table instead of to singleton responses gives 0.0190.019 and 0.0170.017, so the response-level construction is the more accurate of the two here despite seeing no order. Errors are instance medians, only an order-independent constant is removed before aligning them, and no score scale is refitted. The comparison is reference-assisted and retrospective. Table 17: The four singleton-response constructions on the calibration queues. Medians across instances of 2ε/ΔJ2 / _J, with the mean normalized regret of the order each construction selects. Figure 2b reports the same constructions on the fresh-decision queues. Construction Reconstruction error Selection regret Linear 0.1510.151 0.00510.0051 Unary quad. 0.0980.098 0.00050.0005 Projected quad. 0.0210.021 0.00010.0001 Full quad. 0.0060.006 0.00000.0000 Table 18: The same diagnostics on the two sampled designs. Entries are medians across instances with observed [min,max][ , ]. Every error is fitted on the identification orders and evaluated on the declared held-out split, so it describes that split rather than SkS_k. The k=15k=15 design carries no suffix axis because W2W_2 was not estimated there. Setting Design Req. Inst. Gap (%) DtestD_A test DStestD_S test Ridge head 197/500 15 3 2.6512.651 [1.835,2.785][1.835,2.785] 0.1100.110 [0.101,0.160][0.101,0.160] — NegGrad+ 112/336 8 3 11.88611.886 [11.024,16.399][11.024,16.399] 0.4460.446 [0.392,0.520][0.392,0.520] 0.5700.570 [0.551,0.713][0.551,0.713] D.2 Large-queue position-structure identification Large-k structural identification. The large-queue study uses three fixed CIFAR-10 request partitions and the one-step retained-gradient policy with an exact retained reference. Pivoted QR selects the assignment basis before any objective value is observed. Because the basis is saturated, all structural evaluation uses disjoint orders, the remaining complete surface at k=8k=8 and a sampled set at k=15k=15, against a capacity-matched shuffle on the same evaluated orders and objective values (Table 19). Assignment generalizes beyond its saturated basis, whereas the matched shuffle does not. Table 20 separately audits the order returned by solving each fitted k=8k=8 model against the complete surface. The recovery comes from extrapolating the fitted family rather than observing the returned order in the identification basis. Table 19: Identification budgets and held-out fit for the two queue lengths. Medians across the three partitions. The held-out error is 2ε/Δ2 / on the evaluation orders, and the last three columns describe the assignment fit, which the sorting tiers do not report. Shuffle R2R^2 is the capacity-matched permutation of the same objective values. The k-order and assignment rows are the ones Figure 4a carries. Req. Basis Orders Held-out error Evaluated R2R^2 NRMSE Shuffle R2R^2 8 Sorting, k 8 0.0680.068 — — — — 8 Sorting, k+1k+1 9 0.0660.066 — — — — 8 Assignment 50 0.0550.055 40,270 0.99970.9997 0.0170.017 −3.69-3.69 15 Sorting, k 15 0.1070.107 — — — — 15 Sorting, k+1k+1 16 0.0940.094 — — — — 15 Assignment 197 0.1100.110 500 0.99710.9971 0.0540.054 −10.61-10.61 Sorting bases for the same surfaces. The sorting comparison in Figure 4a chooses its identification orders by the same pivoted-QR rule applied to the sorting design alone. The basis is drawn from S8S_8 at k=8k=8, and at k=15k=15, where no complete surface exists, from the 197197 executed identification orders, which asks whether fifteen of those queries would have served. At k=8k=8, the fitted score is minimized over all of S8S_8 and audited on the complete surface. At k=15k=15, it is minimized only over the disjoint 500-order evaluation sample, so the reported rank is not a global statement over S15S_15. The extra basis order does not change the qualitative comparison, while assignment remains the tighter description on the complete k=8k=8 surface. Table 20: True rank of the orders returned by the fitted k=8k=8 families. Each fitted score is minimized over the complete permutation space; regret and uniqueness are then evaluated on the stored surface. Instance Family Queries True rank RcandR_ cand Unique 0 Sorting 8 1/40,320 0 Yes 0 Assignment 50 1/40,320 0 Yes 1 Sorting 8 1/40,320 0 Yes 1 Assignment 50 1/40,320 0 Yes 2 Sorting 8 1/40,320 0 Yes 2 Assignment 50 1/40,320 0 Yes After fitting, we also solved each k=15k=15 assignment globally with the Hungarian algorithm and executed that one predicted order. None of the three orders had been evaluated during identification or sampled testing (Table 21). Table 21: The fitted k=15k=15 assignment minimizer improves on both identification and sampled evaluation orders when executed. Values are squared distances to the exact retained ridge optimum. Improvement is measured relative to the mean sampled held-out objective. Partition Selected Best identification Best sampled Improvement 0 ×10−42.2670\!×\!10^-4 ×10−42.2880\!×\!10^-4 ×10−42.2826\!×\!10^-4 3.32%3.32\% 1 ×10−42.2730\!×\!10^-4 ×10−42.2873\!×\!10^-4 ×10−42.2796\!×\!10^-4 3.07%3.07\% 2 ×10−42.2877\!×\!10^-4 ×10−42.3055\!×\!10^-4 ×10−42.3023\!×\!10^-4 2.46%2.46\% D.3 Full-network held-out prediction Balanced sampled design at k=8k=8. We used a balanced 112/336 identification/held-out design in which every ordered request pair occurs equally often at each tested position pair. The nonoverlapping order sets are disjoint orbits of a fixed affine permutation group. This construction gives exact request-pair balance at each tested position pair. For each position-pair family, the value of a request-pair group was the midpoint of its two identification executions. The assignment coefficients were instead obtained by a minimax fit using only the same 112 identification executions. No coefficient, offset, family, or orientation was adjusted using the held-out executions. All seeds used the same order split and request partition. Three seeds changed the model/execution instance. For a fitted family ℱF with surrogate J^ℱ J_F, the held-out error is Dℱtest=2maxπ∈|J(π)−J^ℱ(π)|Δsample,D_F test= 2 _π |J(π)- J_F(π)| _ sample, where T is the held-out set and Δsample _ sample is the mean-to-minimum gap across all 448 sampled orders. This denominator is an evaluation scale, not an input to fitting. Each of the three 448-order seed tables passed the validity screen on all sampled orders. All three positional families condition on two ordered positions and therefore have equal capacity. Their held-out comparison is reported in Table 22. Table 22: At k=8k=8, assignment and suffix structure generalize to held-out full-network orders while equal-capacity controls do not. Each instance uses 112 identification and 336 held-out orders with exact pair balance. Reported errors are evaluated only on the held-out design, and the last column is the observed suffix error, the width normalized by the sampled gap. Instance Prefix Middle Suffix Assignment Observed DSD_S 0 2.775 3.578 0.551 0.392 0.300 1 2.592 2.743 0.570 0.520 0.376 2 4.505 4.505 0.713 0.446 0.418 D.4 Validation on unseen executions Candidate transfer. We fixed each fitted family and its tie-breaking rule before executing the returned candidates: the original 112 identification executions, the minimax assignment and suffix fits, lexicographic tie breaking, and an ascending request-ID completion for the unspecified prefix. Executing the two candidates per instance under the original request-bound randomness, all six passed the validity screen (Table 23). Candidate quality is mixed across both families and instances, so these runs do not establish a stable search advantage at matched budget. Their role is to verify that a model fitted on one set of executions can produce a valid unseen candidate; the structural comparison remains the held-out prediction result in Figure 4. Table 23: Executed candidates against the fixed 448448-order design. Rank 11 is the best order in that pool. Regret is normalized by the sampled gap, so a negative value means the candidate beats every order in the pool. The last column is the exact probability that 113 draws without replacement from this finite design match or beat the candidate; it is not a probability under uniform search over S8S_8. Instance Family Rank Regret Random-search match 0 Assignment 20 +0.121+0.121 0.9970.997 0 Suffix 19 +0.114+0.114 0.9950.995 1 Assignment 2 +0.013+0.013 0.2520.252 1 Suffix 13 +0.116+0.116 0.9710.971 2 Assignment 1 −0.038-0.038 0.0000.000 2 Suffix 46 +0.129+0.129 1.0001.000 Appendix E Additional controls and diagnostics This appendix asks whether the structure reported in Appendices C and D could instead be explained by family capacity, by the choice of terminal objective, or by the normalization the errors use. E.1 Capacity controls Capacity-matched nulls. For each head instance, we shuffled the 24 terminal objectives across permutations 1,000 times and refit the same minimax assignment family. The null leaves the objective multiset, gap, and assignment design unchanged. We evaluate both separation from this capacity-matched null and the realized objective regret of the fitted assignment optimizer (Table 24). The latter is not bounded tightly by D<1D_A<1 alone. Table 24: Assignment structure exceeds a capacity-matched shuffled-label baseline and usually selects a near-optimal order. “Optimal” counts instances whose fitted assignment minimizer attains the terminal-objective minimum. Regret is (J(π^)−J(π⋆))/ΔJ(J( π)-J(π ))/ _J. Setting Instances Shuffle p Optimal Max. regret Frozen ridge 45 ≤0.001≤ 0.001 44/45 0.00070.0007 Direct head 15 ≤0.001≤ 0.001 13/15 0.1510.151 Factorized head 15 ≤0.001≤ 0.001 10/15 0.4520.452 We permuted each table’s objective labels 1,000 times and re-fit the identical suffix L=1L=1, suffix L=2L=2, and assignment families, which retains the objective distribution and gap while destroying the request–position association. On the exhaustive surfaces all three families beat every one of the 1,000 shuffles in all ten instances and all three at k=5k=5. None of the 1,0001,000 capacity-matched shuffles matched the observed errors. The separation from the shuffled fits shows that the observed localization contains request–position information beyond family capacity. E.2 Behavioural anchoring of the terminal objective The terminal objective is a dense structural-analysis objective, chosen so that the induced permutation problem is measurable on every order. This subsection asks what accompanies the ordering variation it exposes, using the executions already reported and adding none. The complete k=4k=4 full-network surfaces record retained and deleted-group accuracy for each of the 2424 orders, so both quantities are available beside each objective value. Every quantity below is measured within one policy and one instance. The two policies optimise different things, so an order effect under one of them describes that policy alone, and the table places their accuracies on a common scale only to the extent of asking whether an effect is present. The contrasts are differences from the random-order mean of the same surface, and the rank correlation is Spearman’s between the 2424 objective values and the 2424 accuracies of one instance (Table 25). Retained accuracy is more closely aligned with the objective than deleted-group accuracy under both policies. The latter varies more across orders but has little rank alignment with the objective. Terminal reference distance is therefore a utility-anchored comparison objective, not a forgetting metric; a deployment would pair it with a separate forgetting criterion. Table 25: Ordering variation in the terminal objective is accompanied by a consistent retained-accuracy effect within each policy. Entries are medians with observed [min,max][ , ] over ten complete k=4k=4 surfaces per policy. The first two columns are percentage-point differences from the random-order mean of the same surface, the third is the observed spread across its 2424 orders, and the last is the within-instance Spearman correlation between objective and accuracy. Rows describe one policy at a time. Policy Quantity J-best J-worst Range Rank corr. NegGrad+ Retained acc. +0.603+0.603 −0.569-0.569 1.9131.913 −0.670-0.670 Deleted-group acc. +0.583+0.583 +0.660+0.660 4.5334.533 −0.166-0.166 SalUn Retained acc. +0.772+0.772 −0.711-0.711 2.1892.189 −0.833-0.833 Deleted-group acc. +0.502+0.502 −0.801-0.801 5.3975.397 −0.087-0.087 Absolute levels and the screens they are compared with are reported in Table 26. The deleted-group screen requires the largest terminal AFA_F over all orders to be at most AFbase−0.05A_F base-0.05 and is checked retrospectively. The retained screen requires the smallest terminal retained accuracy to exceed min(ARbase,ARretrain)−0.05 (A_R base,A_R retrain)-0.05. Reference progress requires the order-mean terminal distance to be below the base-model distance and was used, with the retained screen, in operating-point selection. These checks are not a privacy guarantee. Table 26: Absolute deleted-group accuracy and declared screens. Entries are medians over ten complete k=4k=4 surfaces per policy. The bracket in AFunlearnA_F unlearn is the range over every terminal order and instance; dU/d0d_U/d_0 is the order-mean reference distance divided by the base distance. The F screen and R floor columns report the median instance thresholds. Policy AFbaseA_F base AFretrainA_F retrain AFunlearnA_F unlearn F screen R floor dU/d0d_U/d_0 NegGrad+ 0.8930.893 0.0000.000 0.6950.695 [0.569,0.835][0.569,0.835] 0.8430.843 0.8480.848 0.6170.617 SalUn 0.9000.900 0.0000.000 0.7370.737 [0.613,0.839][0.613,0.839] 0.8500.850 0.8480.848 0.7080.708 The unlearned deleted-group accuracies remain well above their retraining counterparts. The screens establish a decrease, retained utility, and reference progress at the tested operating points; they do not establish retraining-equivalent forgetting. E.3 Robustness to execution randomness Repeating a fixed order under the same request-bound tape reproduces the terminal objective exactly, so the question here is not numerical reproducibility but whether the ordering signal survives a different draw. We paired two separate replays of all 2424 orders for three k=4k=4 NegGrad+ request sets, holding the model, requests, reference, budget, and 10,000-example audit fixed while changing the request-bound tape (Table 27). The two tapes select the same best order in only one of the three instances, whereas their assignment and suffix verdicts agree. Thus the exact ranking is less stable than the supported structural family. Only NegGrad+ was paired in this way, so this diagnostic does not establish the same behavior for SalUn or coefficient-level stability across tapes. Table 27: A different request-bound tape moves individual objective values but not the structural verdict. Entries are medians with observed [min,max][ , ] over three paired complete k=4k=4 NegGrad+ surfaces. The first block is measured between the two tapes, normalized by the random-order gap. The second reports each family’s error under each tape separately. Quantity Median [min,max][ , ] RMS objective disagreement 0.1930.193 [0.180,0.270][0.180,0.270] Largest objective disagreement 0.4090.409 [0.357,0.519][0.357,0.519] Rank correlation between tapes 0.8670.867 [0.862,0.945][0.862,0.945] D_A, first tape 0.3020.302 [0.265,0.441][0.265,0.441] D_A, second tape 0.2670.267 [0.189,0.347][0.189,0.347] DS,2D_S,2, first tape 0.2210.221 [0.204,0.286][0.204,0.286] DS,2D_S,2, second tape 0.2040.204 [0.126,0.276][0.126,0.276] E.4 Relation to existing ordering rules Kumar et al. (2026) order a forget set by base-model predictive uncertainty. That rule acts on the object this paper permutes, a fixed request set whose order is the decision, so it can be placed on our surfaces directly. Zhao et al. (2024) instead vary how a forget set is decomposed into sequential requests. That changes the request set rather than the order of a fixed one, so it is not a permutation rule on the same SkS_k, and we do not treat it as one here. The uncertainty rule was executed reference-free on ten full-network instances, reading one base-model forward pass per request, loading no retraining reference and issuing no terminal-order query. Those ten instances also have complete 2424-order surfaces, so the order it selects can be scored exactly without executing anything further (Table 28). The uncertainty rule neither selects competitive orders consistently nor tracks the scalar score induced by the terminal-distance objective. This is a matched comparison on the same request sets, but the rule was designed for a different objective. Its reference-free information advantage therefore motivates the fixed-objective audit in the next subsection rather than a claim that uncertainty ordering fails for its intended use. Table 28: An existing uncertainty rule, scored exactly on the complete surfaces. Ten complete k=4k=4 NegGrad+ surfaces, the same instances on which the rule was executed reference-free. Rank 11 is the best of the 2424 orders, regret is normalized by the random-order gap so that 11 is the random-order mean, and the correlation is Spearman’s between the rule’s per-request scores and the scalar sorting score of Proposition 1(b). Quantity Median [min,max][ , ] Rank among the 2424 orders 15 [7,24][7,24] Normalized regret 1.4551.455 [0.177,2.999][0.177,2.999] Better than the random-order mean 3/10 Correlation with the induced score 0.3000.300 [−0.400,1.000][-0.400,1.000] E.5 Structure under reference-free terminal objectives The terminal objective compares an executed model with a retraining reference, which a deployment does not have. We therefore used three separate 12-step replays with the same seed-indexed requests and reference files as the first three main-cohort instances, but evaluated on the full 10,000-example test split. On each replay we recomputed the structure under two fixed objectives that need no retraining. Let cy(x,w)c_y(x;w) be the terminal softmax probability of the true label. For request i, let F^idel F_i del be the empirical CDF of this score on its deleted training examples and let F^inm F_i nm use fixed CIFAR-100 test examples from the same superclass. With qb=b/10q_b=b/10, b=1,…,9b=1,…,9, we define JNM(w)=∑i∑b=19(F^idel(qb)−F^inm(qb))2.J_ NM(w)= _i _b=1^9 ( F_i del(q_b)- F_i nm(q_b) )^2. The second objective is the policy loss on fixed sets, Jpol(w)=0.95CE(w,Reval)−0.05CE(w,Funion),J_ pol(w)=0.95\,CE(w;R_ eval)-0.05\,CE(w;F_ union), where RevalR_ eval is one fixed 5,000-example permanent-retain sample and FunionF_ union is the union of all four deleted groups. The same examples, thresholds, and weights are used for every permutation. Each objective is audited against the same capacity-matched shuffle (Table 29). Both substitutions preserve the assignment and suffix verdict while the matched prefix and middle controls fail. Thus the retraining reference is not the sole carrier of the observed structure. This retrospective evaluation of complete stored replays does not provide a prospective reference-free identification procedure for a new queue. Table 29: Separate replays carry the same structural verdict under two objectives that need no retraining reference. Entries are medians with observed [min,max][ , ] over three complete k=4k=4 NegGrad+ surfaces. DP,2D_P,2 and DM,2D_M,2 are equal-capacity positional controls. “Separated” counts Holm-adjusted lower-tail comparisons with p<0.05p<0.05 over the 1,0001,000 capacity-matched shuffles. Objective Needs reference D_A DS,2D_S,2 DP,2D_P,2 DM,2D_M,2 Separated JrefJ_ ref Yes 0.3020.302 [0.265,0.441][0.265,0.441] 0.2210.221 [0.204,0.286][0.204,0.286] 2.2462.246 [1.423,2.437][1.423,2.437] 2.5802.580 [1.550,3.029][1.550,3.029] 3/3 JNMJ_ NM No 0.2340.234 [0.116,0.376][0.116,0.376] 0.3200.320 [0.189,0.377][0.189,0.377] 1.6341.634 [1.544,1.794][1.544,1.794] 1.8721.872 [1.494,2.012][1.494,2.012] 3/3 JpolJ_ pol No 0.1900.190 [0.119,0.773][0.119,0.773] 0.2420.242 [0.101,0.835][0.101,0.835] 1.9631.963 [1.693,2.119][1.693,2.119] 2.1572.157 [1.790,2.428][1.790,2.428] 3/3 E.6 Sequential ordering versus pooled execution This is a policy-scope control, not an ordering result. The paper fixes a sequential policy and asks which order to run it in. A deployment that may instead aggregate the requests is choosing a different policy. On the same ten complete k=4k=4 NegGrad+ instances, we executed a single pooled update over the union of the four request sets under a matched total budget of 4848 steps, with the same base model, reference and hyperparameters. All ten pooled executions satisfy the validity screens, and each reaches a terminal objective below the best of its own 2424 sequential orders, a median reduction of 37.8%37.8\% (30.630.6–44.2%44.2\%) against the best sequential order. When aggregation is available, changing the execution policy can therefore dominate reordering within a fixed sequential policy. This does not bear on the structural claims, which are about the permutation problem a fixed request-wise policy induces. That fixed policy is a modeling scope, not a claim that pooling is unavailable in every deployment. E.7 Queue-length diagnostics Attenuation across queue lengths. Corollary 5 says the quantities to watch as a queue grows are the contraction and the decision scale, not k. Holding the NegGrad+ policy and its budget fixed, the measured two-request attenuation is nearly unchanged across k=4k=4, 55 and 88, with medians 0.0690.069, 0.0710.071 and 0.0650.065 and between-queue variation smaller than the within-queue range. This finite-execution attenuation diagnostic therefore does not drift with k over the range we execute. Decision-scale diagnostics. Corollary 5 puts every queue-length dependence into μ1(k) _1(k) of Equation 26, which the complete surfaces measure directly. On the full-network settings the last position alone carries most of the available signal, μ1/ΔJ=0.89 _1/ _J=0.89 at k=4k=4 and 0.930.93 at k=5k=5, and the scale itself does not shrink with the queue. μ1 _1 is 8.31%8.31\% of the mean objective at k=4k=4 and 8.98%8.98\% at k=5k=5. The decision scale is therefore non-degenerate over the queue lengths we execute, which is weaker than the uniform condition infkμ1(k)>0 _k _1(k)>0 that Corollary 5 assumes. Appendix F Limitations and Scope Our analysis conditions on a fixed request-wise policy and terminal objective. Changing the policy, including pooling requests, is a separate decision and can dominate reordering in the tested setting (Appendix E.6). Reference distance is used as a dense structural objective rather than a complete forgetting or privacy criterion (Appendices E.2 and E.5). Exact optimal orders are more sensitive to execution randomness than the structural families studied here (Appendix E.3). Complete permutation surfaces are limited to modest queue sizes, while larger-k results rely on held-out evaluation (Appendix D). Adaptive arrivals, joint policy selection, and exact complexity under contraction bounded away from one remain open; the last boundary is detailed in Appendix A.2.