When Is Deletion Ordering Tractable? From Update Dynamics to Permutation Structure

Xinyu Wang; Ziyu Zhao; Yixuan He; Xiaowen Chang Alex Smola

cs.DSOct 1, 2026

When Is Deletion Ordering Tractable? From Update Dynamics to Permutation Structure

Authors: Xinyu Wang, Ziyu Zhao, Yixuan He, Xiaowen Chang Alex Smola

Organizations: McGill University · Arizona State University

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.

Figures & tables

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.

Panel of Figure 2 — 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=1$ . Quadrant labels refer to the median point, and -ext marks a queue-extension setting. (b) Reconstruction error $2\varepsilon/\Delta_{J}$ and selection regret for four singleton-response constructions, over $45$ complete $k=4$ fresh-decision surfaces.

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=1

. (a) Damped-Newton sweep, plotted against the analytic contraction

\kappa_{1}=1-\delta

, 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.

Instance	Prefix-cond.	Middle-cond.	Suffix-cond.
seed0	$0.477$ $[0.433,0.522]$	$0.370$ $[0.347,0.501]$	$0.308$ $[0.285,0.323]$
seed1	$1.579$ $[1.325,1.941]$	$1.547$ $[1.215,2.053]$	$0.724$ $[0.630,0.990]$
seed2	$0.381$ $[0.365,0.409]$	$0.349$ $[0.299,0.357]$	$0.170$ $[0.157,0.190]$

Table 1: Matched-rank position conditioning. Entries are the median held-out

D^{\rm test}

with observed

[\min,\max]

over four design-only folds.

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

500

-order sample at fifteen. (b) Held-out structural error

D^{\rm test}

for the full-network prefix, middle, suffix, and assignment families, one point per instance, with the dashed line at

D^{\rm test}=1

Appendix figures & tables29 assets

Supplementary material from the paper’s appendix.

Appendix

$\rho$	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

Appendix

Table 2: The two affine decay exponents come out as predicted. Fitted slopes of

\log\varepsilon_{L}

against

L\log\rho

k=30

, over

40

instances per contraction. Proposition 2 predicts

1

for truncation,

2

for suffix-conditioned assignment, and hence a ratio of

2

Setting	Inst.	$D_{\mathcal{A}}$	Sorting error	Certificate	Realized regret
Frozen ridge, vision	15	$0.010$ $[0.001,0.066]$	$0.059$ $[0.015,0.266]$	$0.080$ $[0.021,0.375]$	$0.000$ $[0.000,0.000]$
Frozen ridge, AG News	15	$0.018$ $[0.002,0.068]$	$0.062$ $[0.017,0.319]$	$0.082$ $[0.023,0.446]$	$0.000$ $[0.000,0.092]$
Frozen ridge, 20 Newsgroups	15	$0.022$ $[0.002,0.126]$	$0.074$ $[0.015,0.321]$	$0.116$ $[0.022,0.473]$	$0.000$ $[0.000,0.000]$
Direct softmax head	15	$0.035$ $[0.005,0.634]$	$0.081$ $[0.017,2.616]$	$0.130$ $[0.021,4.005]$	$0.000$ $[0.000,1.248]$
Factorized softmax head	15	$0.065$ $[0.010,0.686]$	$0.584$ $[0.117,2.523]$	$0.872$ $[0.184,4.059]$	$0.009$ $[0.000,1.789]$
NegGrad+	10	$0.236$ $[0.119,0.391]$	$1.867$ $[1.189,2.998]$	$2.672$ $[1.807,4.966]$	$0.122$ $[0.000,0.309]$

Appendix

Table 3: The sorting certificate is conservative where the family fits. Entries are medians with observed

[\min,\max]

across the complete

k=4

surfaces of each setting, all normalized by the random-order gap.

D_{\mathcal{A}}

is the best assignment family’s uniform error, the sorting error is that of the surrogate

sq^{\top}

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.

Analysis	Instances	Relation to main $k=4$ cohort
NegGrad+ budget development	seeds 0–2, $k=4$	Same requests; alternate budgets
NegGrad+ main	seeds 0–9, $k=4$	Complete 24-order surfaces
SalUn pilot/replication	seeds 0–2 / 3–9, $k=4$	Matched request partitions by seed
Composition	seeds 0–2, $k=5$	New five-request queues
Held-out identification	seeds 0–2, $k=8$	New eight-request sampled designs
Second tape / reference-free	seeds 0–2, $k=4$	Same requests/reference; separate $10{,}000$ -audit replays

Appendix

Table 4: Full-network instance correspondence. “Main” means the complete

k=4

cohort used for structural summaries.

Construction	$T_{\rm reference}$	$T_{\rm identification}$	$T_{\rm fit/solve}$	$T_{\rm candidate}$
Ridge sorting	Exact retain solve	$k$ seq.	Least squares, sort	$1$ seq.
Ridge assignment	Exact retain solve	$(k-1)^{2}+1$ seq.	Minimax, Hungarian	$1$ seq.
NegGrad+ $k=8$	Two retain-only runs	$112$ seq. ( $10{,}752$ )	Minimax, solve	$1$ seq. ( $96$ )
Head reconstruction	Exact retain solve	$0$ seq.; $k$ probes	Construct, solve	$1$ seq.

Appendix

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.

Steps/request	Valid seeds	History retention	$D_{S,1}$	$D_{S,2}$	$D_{\mathcal{A}}$
3	0/3	$0.318$ $[0.312,0.321]$	$1.362$ $[0.843,1.399]$	$0.515$ $[0.341,0.531]$	$0.443$ $[0.260,0.512]$
12	3/3	$0.065$ $[0.059,0.066]$	$0.598$ $[0.573,0.883]$	$0.221$ $[0.204,0.286]$	$0.302$ $[0.265,0.441]$
24	2/3	$0.118$ $[0.108,0.127]$	$0.394$ $[0.363,0.417]$	$0.149$ $[0.117,0.202]$	$0.221$ $[0.166,0.229]$
48	0/3	$0.278$ $[0.225,0.312]$	$0.993$ $[0.840,1.167]$	$0.673$ $[0.497,0.892]$	$0.256$ $[0.198,0.378]$

Appendix

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=4

surfaces. “Valid seeds” counts the instances passing all three reported screens. History retention is the measured matched-history attenuation, and

D_{S,1}

and

D_{S,2}

are the suffix errors at one and two positions.

Setting	Req.	Inst.	Gap (%)	$D_{\mathcal{A}}$	$D_{S}$	A pass	S pass
Ridge head	4	45	$0.878$ $[0.063,11.659]$	$0.018$ $[0.001,0.126]$	$0.562$ $[0.427,0.658]$	45/45	45/45
Direct head	4	15	$0.076$ $[0.003,1.055]$	$0.035$ $[0.005,0.634]$	$0.589$ $[0.492,1.700]$	15/15	13/15
Factorized head	4	15	$0.811$ $[0.073,1.446]$	$0.065$ $[0.010,0.686]$	$0.547$ $[0.383,1.303]$	15/15	14/15
Ridge head	8	3	$0.838$ $[0.824,0.996]$	$0.017$ $[0.015,0.021]$	$1.290$ $[1.287,1.318]$	3/3	0/3
NegGrad+	4	10	$9.285$ $[3.407,15.201]$	$0.236$ $[0.119,0.391]$	$0.148$ $[0.055,0.477]$	10/10	10/10
NegGrad+	5	3	$9.647$ $[3.660,13.805]$	$0.186$ $[0.150,0.771]$	$0.238$ $[0.227,0.582]$	3/3	3/3

Appendix

Table 7: Structural regimes on the completely enumerated surfaces. Entries are medians across instances with observed

[\min,\max]

. Gap is

100\Delta_{J}/\bar{J}

, every error is exact over all

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.

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.

Domain	Linear terminal	Quadratic terminal	Residual ratio
Vision	$0.145$	$0.006$	$0.041$
AG News	$0.141$	$0.006$	$0.043$
20 Newsgroups	$0.212$	$0.009$	$0.045$

Appendix

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\varepsilon/\Delta_{J}

Update rule	Scale (%)	$D_{\mathcal{A}}$	$D_{S,1}$	$D_{S,2}$	$D_{P,2}$
Gradient descent	$0.565$	$0.003$	$1.095$	$0.543$	$0.559$
	$[0.416,0.806]$	$[0.001,0.005]$	$[1.000,1.169]$	$[0.496,0.579]$	$[0.512,0.599]$
Damped Newton	$31.684$	$0.111$	$0.597$	$0.143$	$1.488$
	$[29.902,47.809]$	$[0.052,0.283]$	$[0.555,0.768]$	$[0.133,0.203]$	$[1.268,1.605]$

Appendix

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\Delta_{J}/\bar{J}

$\kappa_{1}$	$\delta$	$\Delta_{J}/\bar{J}$	$\Delta_{J}/j_{0}$	$D_{\mathcal{A}}$	$D_{S,1}$	$D_{S,2}$	$D_{P,2}$	$D_{M,2}$
$0.90$	$0.10$	$8.263$ $[6.563,11.721]$	$5.038$ $[3.999,7.118]$	$0.022$ $[0.011,0.059]$	$1.063$ $[0.951,1.105]$	$0.487$ $[0.431,0.495]$	$0.720$ $[0.614,0.740]$	$1.755$ $[1.559,1.840]$
$0.75$	$0.25$	$19.492$ $[16.593,28.456]$	$5.769$ $[4.890,8.202]$	$0.060$ $[0.028,0.159]$	$0.910$ $[0.819,1.015]$	$0.347$ $[0.312,0.368]$	$0.991$ $[0.810,1.016]$	$1.808$ $[1.602,1.957]$
$0.50$	$0.50$	$31.684$ $[29.902,47.809]$	$2.837$ $[2.561,3.885]$	$0.111$ $[0.052,0.283]$	$0.597$ $[0.555,0.768]$	$0.143$ $[0.133,0.203]$	$1.488$ $[1.268,1.605]$	$2.051$ $[1.742,2.182]$
$0.25$	$0.75$	$37.595$ $[34.761,56.612]$	$0.710$ $[0.555,0.905]$	$0.093$ $[0.047,0.221]$	$0.247$ $[0.222,0.408]$	$0.035$ $[0.032,0.067]$	$1.869$ $[1.795,2.124]$	$2.059$ $[1.946,2.325]$

Appendix

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

j_{0}=j(w_{0})

the objective at the undeleted state.

Common suffix	Output RMS	$\|j_{\rm RMS}(z)-j_{\rm RMS}(z^{\prime})\|$	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

Appendix

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-z_{R}\|_{\rm RMS}\|d\|_{\rm RMS}

, whereas

j_{\rm RMS}

is a mean squared distance.

Setting	Instances	$D_{\rm lin}$	$D_{\rm mono}$	$D_{\mathcal{A}}$	$R_{\rm mono}$	$R_{\mathcal{A}}$	m/b/f
Frozen ridge, vision	15	$0.056$	$0.011$	$0.010$	$0.000$	$0.000$	15/0/0
Frozen ridge, AG News	15	$0.055$	$0.026$	$0.018$	$0.000$	$0.000$	15/0/0
Frozen ridge, 20 Newsgroups	15	$0.061$	$0.055$	$0.022$	$0.000$	$0.000$	15/0/0
Direct softmax head	15	$0.071$	$0.068$	$0.035$	$0.000$	$0.000$	14/0/1
Factorized softmax head	15	$0.545$	$0.305$	$0.065$	$0.009$	$0.000$	13/0/2
NegGrad+	10	$1.582$	$0.281$	$0.236$	$0.122$	$0.064$	10/0/0

Appendix

Table 12: Nested position families separate fixed-profile sorting, learned-profile sorting, and unrestricted assignment.

D_{\rm lin}

fixes a shared linear positional profile,

D_{\rm mono}

learns a shared monotone profile, and

D_{\mathcal{A}}

is unrestricted.

R

is the normalized regret of the selected order. The last column counts instances meeting, on, and failing the criterion for

D_{\rm mono}

, with the boundary band

[0.95,1.05]

Setting	Instances	$D_{S}$	$D_{S}^{\rm add}$	$D_{\mathcal{A}}$
NegGrad+	10	$0.148$ $[0.055,0.477]$	$0.293$ $[0.146,0.489]$	$0.236$ $[0.119,0.391]$
NegGrad+ ( $k=5$ )	3	$0.238$ $[0.227,0.582]$	$0.238$ $[0.230,0.924]$	$0.186$ $[0.150,0.771]$
SalUn	10	$0.260$ $[0.185,0.510]$	$0.746$ $[0.335,1.139]$	$0.673$ $[0.215,1.030]$

Appendix

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.

Instances	$L$	Prefix	Middle	Suffix
$k=4$ (10)	1	2.137	2.192	0.368
	2	1.926	2.096	0.148
$k=5$ (3)	1	2.254	2.244	0.331
	2	2.232	2.243	0.238

Appendix

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

\Delta_{J}

normalization.

Seed	Suffix $L{=}1$	General suffix $L{=}2$	Additive suffix $L{=}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

Appendix

Table 15: At

k=5

, the general suffix error separates prefix memory from additive suffix structure. All entries are normalized by the total ordering gap

\Delta_{J}

Steps	$W_{2}$	$\mathcal{B}_{2}$	$\mathcal{B}_{2}/W_{2}$	$D_{S}$	$\mathcal{B}_{2}/\Delta_{J}$
1	$2.39{\times}10^{-8}$	$1.68{\times}10^{-7}$	9.24	0.623	5.85
4	$8.84{\times}10^{-8}$	$6.66{\times}10^{-7}$	9.78	0.614	6.05
16	$2.65{\times}10^{-7}$	$2.51{\times}10^{-6}$	11.93	0.575	6.86

Appendix

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.

\mathcal{B}_{2}

is the bound of Equation 11 .

Construction	Reconstruction error	Selection regret
Linear	$0.151$	$0.0051$
Unary quad.	$0.098$	$0.0005$
Projected quad.	$0.021$	$0.0001$
Full quad.	$0.006$	$0.0000$

Appendix

Table 17: The four singleton-response constructions on the calibration queues. Medians across instances of

2\varepsilon/\Delta_{J}

, with the mean normalized regret of the order each construction selects. Figure 2 b reports the same constructions on the fresh-decision queues.

Setting	Design	Req.	Inst.	Gap (%)	$D_{\mathcal{A}}^{\rm test}$	$D_{S}^{\rm test}$
Ridge head	197/500	15	3	$2.651$ $[1.835,2.785]$	$0.110$ $[0.101,0.160]$	—
NegGrad+	112/336	8	3	$11.886$ $[11.024,16.399]$	$0.446$ $[0.392,0.520]$	$0.570$ $[0.551,0.713]$

Appendix

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

S_{k}

. The

k=15

design carries no suffix axis because

W_{2}

was not estimated there.

Req.	Basis	Orders	Held-out error	Evaluated	$R^{2}$	NRMSE	Shuffle $R^{2}$
8	Sorting, $k$	8	$0.068$	—	—	—	—
8	Sorting, $k{+}1$	9	$0.066$	—	—	—	—
8	Assignment	50	$0.055$	40,270	$0.9997$	$0.017$	$-3.69$
15	Sorting, $k$	15	$0.107$	—	—	—	—
15	Sorting, $k{+}1$	16	$0.094$	—	—	—	—
15	Assignment	197	$0.110$	500	$0.9971$	$0.054$	$-10.61$

Appendix

Table 19: Identification budgets and held-out fit for the two queue lengths. Medians across the three partitions. The held-out error is

2\varepsilon/\Delta

on the evaluation orders, and the last three columns describe the assignment fit, which the sorting tiers do not report. Shuffle

R^{2}

is the capacity-matched permutation of the same objective values. The

k

-order and assignment rows are the ones Figure 4 a carries.

Instance	Family	Queries	True rank	Unique
0	Sorting	8	1/40,320	Yes
0	Assignment	50	1/40,320	Yes
1	Sorting	8	1/40,320	Yes
1	Assignment	50	1/40,320	Yes
2	Sorting	8	1/40,320	Yes
2	Assignment	50	1/40,320	Yes

Appendix

Table 20: True rank of the orders returned by the fitted

k=8

families. Each fitted score is minimized over the complete permutation space; regret and uniqueness are then evaluated on the stored surface.

Partition	Selected	Best identification	Best sampled	Improvement
0	$2.2670\!\times\!10^{-4}$	$2.2880\!\times\!10^{-4}$	$2.2826\!\times\!10^{-4}$	$3.32\%$
1	$2.2730\!\times\!10^{-4}$	$2.2873\!\times\!10^{-4}$	$2.2796\!\times\!10^{-4}$	$3.07\%$
2	$2.2877\!\times\!10^{-4}$	$2.3055\!\times\!10^{-4}$	$2.3023\!\times\!10^{-4}$	$2.46\%$

Appendix

Table 21: The fitted

k=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.

Instance	Prefix	Middle	Suffix	Assignment	Observed $D_{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

Appendix

Table 22: At

k=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	Family	Rank	Regret	Random-search match
0	Assignment	20	$+0.121$	$0.997$
0	Suffix	19	$+0.114$	$0.995$
1	Assignment	2	$+0.013$	$0.252$
1	Suffix	13	$+0.116$	$0.971$
2	Assignment	1	$-0.038$	$0.000$
2	Suffix	46	$+0.129$	$1.000$

Appendix

Table 23: Executed candidates against the fixed

448

-order design. Rank

1

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

S_{8}

Setting	Instances	Shuffle $p$	Optimal	Max. regret
Frozen ridge	45	$\leq 0.001$	44/45	$0.0007$
Direct head	15	$\leq 0.001$	13/15	$0.151$
Factorized head	15	$\leq 0.001$	10/15	$0.452$

Appendix

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(\widehat{\pi})-J(\pi^{\star}))/\Delta_{J}

Policy	Quantity	$J$ -best	$J$ -worst	Range	Rank corr.
NegGrad+	Retained acc.	$+0.603$	$-0.569$	$1.913$	$-0.670$
	Deleted-group acc.	$+0.583$	$+0.660$	$4.533$	$-0.166$
SalUn	Retained acc.	$+0.772$	$-0.711$	$2.189$	$-0.833$
	Deleted-group acc.	$+0.502$	$-0.801$	$5.397$	$-0.087$

Appendix

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=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

24

orders, and the last is the within-instance Spearman correlation between objective and accuracy. Rows describe one policy at a time.

Policy	$A_{F}^{\rm base}$	$A_{F}^{\rm retrain}$	$A_{F}^{\rm unlearn}$	$F$ screen	$R$ floor	$d_{U}/d_{0}$
NegGrad+	$0.893$	$0.000$	$0.695$ $[0.569,0.835]$	$0.843$	$0.848$	$0.617$
SalUn	$0.900$	$0.000$	$0.737$ $[0.613,0.839]$	$0.850$	$0.848$	$0.708$

Appendix

Table 26: Absolute deleted-group accuracy and declared screens. Entries are medians over ten complete

k=4

surfaces per policy. The bracket in

A_{F}^{\rm unlearn}

is the range over every terminal order and instance;

d_{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.

Quantity	Median $[\min,\max]$
RMS objective disagreement	$0.193$ $[0.180,0.270]$
Largest objective disagreement	$0.409$ $[0.357,0.519]$
Rank correlation between tapes	$0.867$ $[0.862,0.945]$
$D_{\mathcal{A}}$ , first tape	$0.302$ $[0.265,0.441]$
$D_{\mathcal{A}}$ , second tape	$0.267$ $[0.189,0.347]$
$D_{S,2}$ , first tape	$0.221$ $[0.204,0.286]$

Appendix

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=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]$
Rank among the $24$ orders	15 $[7,24]$
Normalized regret	$1.455$ $[0.177,2.999]$
Better than the random-order mean	3/10
Correlation with the induced score	$0.300$ $[-0.400,1.000]$

Appendix

Table 28: An existing uncertainty rule, scored exactly on the complete surfaces. Ten complete

k=4

NegGrad+ surfaces, the same instances on which the rule was executed reference-free. Rank

1

is the best of the

24

orders, regret is normalized by the random-order gap so that

1

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).

Objective	Needs reference	$D_{\mathcal{A}}$	$D_{S,2}$	$D_{P,2}$	$D_{M,2}$	Separated
$J_{\rm ref}$	Yes	$0.302$ $[0.265,0.441]$	$0.221$ $[0.204,0.286]$	$2.246$ $[1.423,2.437]$	$2.580$ $[1.550,3.029]$	3/3
$J_{\rm NM}$	No	$0.234$ $[0.116,0.376]$	$0.320$ $[0.189,0.377]$	$1.634$ $[1.544,1.794]$	$1.872$ $[1.494,2.012]$	3/3
$J_{\rm pol}$	No	$0.190$ $[0.119,0.773]$	$0.242$ $[0.101,0.835]$	$1.963$ $[1.693,2.119]$	$2.157$ $[1.790,2.428]$	3/3

Appendix

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=4

NegGrad+ surfaces.

D_{P,2}

and

D_{M,2}

are equal-capacity positional controls. “Separated” counts Holm-adjusted lower-tail comparisons with

p<0.05

over the

1{,}000

capacity-matched shuffles.

Explore similar work

Apr 24, 2026cs.LG

Shape of Memory: a Geometric Analysis of Machine Unlearning in Second-Order Optimizers

We argue that current definitions of machine unlearning are underspecified for second-order optimizers. We compare first-order and second-order learners for their ability to handle the data deletion task with varying degrees of eigendecomposition to mimic the loss model memory. While both first and second-order methods realign with the ideal counterfactul in terms of performance and gradient, the second-order optimizer shows significant volatility in the optimizer state. This indicates residual information, supposedly deleted, that isn't detectable by first-order analysis. Various eigendecay treatments show that stability and information loss is regained only under controlled state pertubation where geometric information (or memory) is erased.

Kennon Stewart

Second Street Labs, Detroit, MI, USA · Department of Statistics, University of Michigan, Ann Arbor, MI, USA

Machine Unlearning Zeroth-Order Optimization Adaptive Optimizers

Ask PDF

Apr 15, 2026cs.LG

From Order to Distribution: An Exact Operator Framework for Forgetting in Continual Learning

A central challenge in continual learning is forgetting: the loss of performance on previously learned tasks after learning new ones. Prior theory has analyzed forgetting under random orderings of fixed task collections in overparameterized linear regression. We shift the focus from task order to task distribution, asking how its structure determines forgetting. In the linear setting with a shared solution, i.i.d. task sampling, and sequential exact fitting, we derive an exact operator identity expressing historical forgetting directly in terms of the task distribution. Building on this identity, we establish an exponential decay guarantee for expected historical forgetting under every fixed task distribution in finite dimensions, characterize its asymptotic behavior, and relate decay to the distribution's coverage of observable directions. For an individual learned task, we show that subsequent tasks can collectively support recovery without exact revisits. We derive a lower bound on recovery time and construct a task distribution attaining its inverse-coverage scaling.

Zonghuan Xu, Xingjun Ma

Institute of Trustworthy Embodied AI, Fudan University, Shanghai, China · Shanghai Key Laboratory of Multimodal Embodied AI, Shanghai, China

Continual Learning Learning-Augmented Algorithms Forgetting Distributions Exact History

Ask PDF

May 25, 2026cs.LG

Learning Permutation from Structure Without Supervision

Many learning problems require uncovering a hidden ordering that reveals structure in unordered data, such as monotonicity in sorting or spatial continuity in jigsaw reconstruction. In these settings, permutations can be learned as latent operators by optimizing objectives defined directly on the reordered output, often without access to ground-truth orderings. Differentiable relaxations such as Gumbel-Sinkhorn make this approach practical by approximating permutation matrices with doubly stochastic matrices. However, learning from structure without supervision induces a non-uniform uncertainty: some assignments become confident early, while others remain ambiguous. Existing methods control this process using a single global temperature, forcing all assignments to sharpen or diffuse simultaneously and leading to instability at scale. We introduce an entropy-adaptive formulation of Gumbel-Sinkhorn that locally modulates temperature based on assignment uncertainty. This allows confident assignments to discretize early while preserving exploration where uncertainty remains. Across sorting and jigsaw reconstruction tasks and in routing-style settings, adaptive entropy control improves training stability and final permutation quality relative to fixed-temperature baselines, particularly as problem size and assignment ambiguity increase.

Ran Eisenberg, Ofir Lindenbaum

Faculty of Engineering, Bar-Ilan University, Ramat Gan, Israel. · Faculty of Engineering, Bar-Ilan

Permutation Equivariant Learning Puzzle Uncertainty

Ask PDF