Pattern-Based Matrix Analysis Under Permutations

arXiv cs.LG Papers

Summary

This paper introduces a pattern distance measuring how close a matrix is to a geometric pattern (band, block-diagonal, arrowhead) after optimal row/column permutations, an alternating Linear Assignment algorithm to compute it, and a pattern-plus-low-rank (PatLR) decomposition evaluated on synthetic, real correlation/graph matrices, and transformer attention heads.

arXiv:2611.17674v1 Announce Type: new Abstract: Low-rank approximation captures one important notion of matrix simplicity: a matrix is simple if it is well described by a low-dimensional linear model. This paper studies a complementary notion. We consider matrices that become structurally simple only after permuting rows and columns, so that their mass concentrates in a prescribed geometric pattern such as a band, block-diagonal, arrowhead, or related form. We introduce a pattern distance that measures how close a matrix is to a given pattern after optimal reordering, giving a common framework for structural problems such as latent ordering, community detection, and bandwidth minimization. The problem is NP-hard in general; we derive an alternating algorithm based on Linear Assignment subproblems. We further introduce a pattern-plus-low-rank decomposition that combines permutation-structured fitting with a low-rank residual, whose permutation step is pattern fitting on the residual; its gains across pattern families persist at a matched parameter budget and are substantially reduced under a density-matched random-mask control. We evaluate the framework on synthetic recovery tasks, real correlation and graph adjacency matrices, and transformer attention heads, showing that a single universal algorithm recovers qualitatively different forms of matrix structure.
Original Article
View Cached Full Text

Cached at: 11/16/26, 08:45 AM

# Pattern-Based Matrix Analysis Under Permutations
Source: [https://arxiv.org/html/2611.17674](https://arxiv.org/html/2611.17674)
###### Abstract

Low\-rank approximation captures one important notion of matrix simplicity: a matrix is simple if it is well described by a low\-dimensional linear model\. This paper studies a complementary notion\. We consider matrices that become structurally simple only after permuting rows and columns, so that their mass concentrates in a prescribed geometric pattern such as a band, block\-diagonal, arrowhead, or related form\. We introduce a pattern distance that measures how close a matrix is to a given pattern after optimal reordering, giving a common framework for structural problems such as latent ordering, community detection, and bandwidth minimization\. The problem is NP\-hard in general; we derive an alternating algorithm based on Linear Assignment subproblems\. We further introduce a pattern\-plus\-low\-rank decomposition that combines permutation\-structured fitting with a low\-rank residual, whose permutation step is pattern fitting on the residual; its gains across pattern families persist at a matched parameter budget and are substantially reduced under a density\-matched random\-mask control\. We evaluate the framework on synthetic recovery tasks, real correlation and graph adjacency matrices, and transformer attention heads, showing that a single universal algorithm recovers qualitatively different forms of matrix structure\.

## 1Introduction

A basic question in matrix analysis is what structure a matrix has\. The standard answer is low\-rank: the SVD gives the best rank\-kkapproximation and reveals latent linear factors\. But many matrices are simple in another sense: after reordering rows and columns they show an interpretable geometric form, blocks, bands, chains or hierarchies\. Seriation\([Atkins et al\., 1998](https://arxiv.org/html/2611.17674#bib.bib4);[Fogel et al\., 2013](https://arxiv.org/html/2611.17674#bib.bib21)\), community detection\([Newman, 2006](https://arxiv.org/html/2611.17674#bib.bib40);[Holland et al\., 1983](https://arxiv.org/html/2611.17674#bib.bib30)\)and bandwidth minimization\([Cuthill and McKee, 1969](https://arxiv.org/html/2611.17674#bib.bib16);[George, 1973](https://arxiv.org/html/2611.17674#bib.bib24)\)are usually studied separately yet share this intuition\.[Goldengorin and Krushinsky \(2017\)](https://arxiv.org/html/2611.17674#bib.bib27)make it precise: many combinatorial problems \(LAP, TSP, linear ordering, matching, cut\) reduce to finding a permutation that aligns a matrix with a geometric*pattern*, and fixing one permutation reduces the remaining search to a Linear Assignment Problem\.

This paper turns that combinatorial idea into a matrix\-analysis tool\. A binary*pattern mask*MMspecifies the target geometry; the*pattern distance*dM​\(A\)d\_\{M\}\(A\)is the off\-pattern mass after the best row/column permutations\. This viewpoint, which we call*permutation\-structural simplicity*, complements low\-rank approximation: a matrix may have clear geometric organization after reordering even when no low\-rank model fits, and vice versa; the target geometry, the discrepancy measure and the search over permutations become independent ingredients of one formalism\.

### 1\.1Contributions

1. 1\.Pattern\-based framework\.We define the*pattern distance*dMd\_\{M\}, the off\-pattern Frobenius mass after optimal reordering, and use it to formalize permutation\-structural simplicity\.
2. 2\.Alternating LAP algorithm\.An alternating procedure built on the auxiliary\-matrix construction of[Goldengorin and Krushinsky \(2017\)](https://arxiv.org/html/2611.17674#bib.bib27)performs exact one\-sided updates ofdMd\_\{M\}inO⁡\(n3\)O\(n^\{3\}\), applicable to any binary mask without changes to the solver\.
3. 3\.Pattern\-plus\-low\-rank \(PatLR\) decomposition\.A hybrid model combining permutation\-structured fitting with a low\-rank residual, with exact closed\-form updates for both parts and a monotone alternating algorithm\.
4. 4\.Adaptive pattern selection\.When the pattern is unknown, a simulated\-annealing search jointly optimizes the pattern and the permutation against a density\-normalized score\.
5. 5\.Experimental validation\.On synthetic and real data the same algorithm recovers qualitatively different structures, scored by the metrics of latent ordering, consecutive ones and block recovery against the methods developed for them; on the attention heads of three transformers the same score gives labels with a shared depth profile\.

### 1\.2Related Work

Structure after reordering\.Several literatures study matrices that become simple once rows and columns are permuted, each around one geometry\. Seriation seeks a Robinson order by spectral\([Robinson, 1951](https://arxiv.org/html/2611.17674#bib.bib47);[Atkins et al\., 1998](https://arxiv.org/html/2611.17674#bib.bib4)\)or convex\([Fogel et al\., 2013](https://arxiv.org/html/2611.17674#bib.bib21)\)methods, with the consecutive\-ones property\([Booth and Lueker, 1976](https://arxiv.org/html/2611.17674#bib.bib9);[Kendall, 1971](https://arxiv.org/html/2611.17674#bib.bib31)\)and circular seriation\([Recanati et al\., 2018](https://arxiv.org/html/2611.17674#bib.bib46)\)as its interval and cyclic forms\. Community detection seeks block\-diagonal structure, by modularity and spectral methods\([Girvan and Newman, 2002](https://arxiv.org/html/2611.17674#bib.bib26);[von Luxburg, 2007](https://arxiv.org/html/2611.17674#bib.bib57)\)or under the stochastic block model, where belief propagation and its spectral linearizations are optimal near the detectability threshold\([Holland et al\., 1983](https://arxiv.org/html/2611.17674#bib.bib30);[Decelle et al\., 2011](https://arxiv.org/html/2611.17674#bib.bib19);[Krzakala et al\., 2013](https://arxiv.org/html/2611.17674#bib.bib34);[Saade et al\., 2014](https://arxiv.org/html/2611.17674#bib.bib49)\)\. Bandwidth and profile reduction seek near\-diagonal sparsity\([Cuthill and McKee, 1969](https://arxiv.org/html/2611.17674#bib.bib16);[Gibbs et al\., 1976](https://arxiv.org/html/2611.17674#bib.bib25);[George, 1973](https://arxiv.org/html/2611.17674#bib.bib24)\); nestedness\([Brualdi and Sanderson, 1999](https://arxiv.org/html/2611.17674#bib.bib10)\), bordered block\-diagonal forms\([Aykanat et al\., 2004](https://arxiv.org/html/2611.17674#bib.bib5)\), chordal sparsity\([Vandenberghe and Andersen, 2015](https://arxiv.org/html/2611.17674#bib.bib54)\), core–periphery structure\([Rombach et al\., 2014](https://arxiv.org/html/2611.17674#bib.bib48)\)and biclustering\([Hartigan, 1972](https://arxiv.org/html/2611.17674#bib.bib29)\)are further such geometries \(Table[2](https://arxiv.org/html/2611.17674#A1.T2)\)\. Robust PCA separates a low\-rank part from a sparse one\([Candès et al\., 2011](https://arxiv.org/html/2611.17674#bib.bib11)\)with no permutation; GoDec\([Zhou and Tao, 2011](https://arxiv.org/html/2611.17674#bib.bib62)\)alternates low\-rank and sparse approximation, whereas PatLR restricts the support of the second component to a geometric mask under unknown permutations\.

A common optimization core\.[Goldengorin and Krushinsky \(2017\)](https://arxiv.org/html/2611.17674#bib.bib27)introduced patterns as a description of the input matrices of combinatorial optimization problems\. For a fixed pattern the alignment is a Koopmans–Beckmann quadratic assignment problem\([Koopmans and Beckmann, 1957](https://arxiv.org/html/2611.17674#bib.bib33);[Lawler, 1963](https://arxiv.org/html/2611.17674#bib.bib35);[Çela, 1998](https://arxiv.org/html/2611.17674#bib.bib12)\), with two permutations a bilinear assignment problem\([Ćustić et al\., 2017](https://arxiv.org/html/2611.17674#bib.bib15)\), for which alternating LAP heuristics are studied by[Sokol et al\. \(2020\)](https://arxiv.org/html/2611.17674#bib.bib51)\. Generic solvers are the FAQ heuristic\([Vogelstein et al\., 2015](https://arxiv.org/html/2611.17674#bib.bib55)\)and Birkhoff\-polytope relaxations\([Fogel et al\., 2013](https://arxiv.org/html/2611.17674#bib.bib21);[Cuturi, 2013](https://arxiv.org/html/2611.17674#bib.bib17);[Mena et al\., 2018](https://arxiv.org/html/2611.17674#bib.bib38)\)\. In this paper the pattern is the interface between these literatures: the same solver serves every mask, and PatLR extends it with a low\-rank residual\.

![Refer to caption](https://arxiv.org/html/2611.17674v1/fig_pattern_gallery.png)Figure 1:Gallery of patterns, one representative per structural hypothesis \(each cell is the binary maskMM, blue=1=1\), grouped by the kind of structure they encode: order, grouping, nesting, separability, branching, self\-similarity\. Daggers mark the families used in our experiments; Table[2](https://arxiv.org/html/2611.17674#A1.T2)gives the classical problem behind each pattern\. Masks are shown up to the permutations the framework optimizes over \(an anti\-diagonal band equals a band under column reversal\)\. Any binary mask is admissible:MMencodes the structure hypothesized for an application or is selected from a vocabulary\.

## 2Theory of Patterns

A*pattern*is a target structure \(a band, block\-diagonal, arrowhead, etc\.\), encoded by a binary*mask*M∈\{0,1\}n×nM\\in\\\{0,1\\\}^\{n\\times n\}marking the positions it allows; we use “pattern” for the structural hypothesis and “mask” for the matrixMM\. A permutationπ∈𝒮n\\pi\\in\\mathcal\{S\}\_\{n\}maps an original index to its new position,\(Pπ\)i​j=𝟏\{i=π\(j\)\}\(P\_\{\\pi\}\)\_\{ij\}=\\mathbf\{1\}\\\{i=\\pi\(j\)\\\}, so the\(π,σ\)\(\\pi,\\sigma\)\-reordered matrixAπ,σ:=Pπ​A​Pσ⊤A^\{\\pi,\\sigma\}:=P\_\{\\pi\}AP\_\{\\sigma\}^\{\\top\}has entriesAπ−1​\(i\),σ−1​\(j\)A\_\{\\pi^\{\-1\}\(i\),\\sigma^\{\-1\}\(j\)\};ΠM​\(X\):=M⊙X\\Pi\_\{M\}\(X\):=M\\odot Xis the masking operator\. For fixed row and column permutations the*off\-pattern mass*is

dM\(A;π,σ\):=∥\(I−ΠM\)\(Aπ,σ\)∥F2=∑\(i,j\):Mi​j=0\(Ai​jπ,σ\)2\.d\_\{M\}\(A;\\pi,\\sigma\)\\;:=\\;\\bigl\\\|\(I\-\\Pi\_\{M\}\)\(A^\{\\pi,\\sigma\}\)\\bigr\\\|\_\{F\}^\{2\}\\;=\\;\\sum\_\{\(i,j\):\\,M\_\{ij\}=0\}\\bigl\(A^\{\\pi,\\sigma\}\_\{ij\}\\bigr\)^\{2\}\.\(1\)
###### Definition 1\(Pattern distance\)\.

The pattern distance ofA∈ℝn×nA\\in\\mathbb\{R\}^\{n\\times n\}from the maskM∈\{0,1\}n×nM\\in\\\{0,1\\\}^\{n\\times n\}is the smallest off\-pattern mass over row and column permutations,

dM​\(A\):=minπ,σ∈𝒮n⁡dM​\(A,π,σ\)\.d\_\{M\}\(A\)\\;:=\\;\\min\_\{\\pi,\\sigma\\in\\mathcal\{S\}\_\{n\}\}d\_\{M\}\(A;\\pi,\\sigma\)\.\(2\)

ForA≠0A\\neq 0the*explained pattern variance*νM​\(A\):=1−dM​\(A\)/‖A‖F2∈\[0,1\]\\nu\_\{M\}\(A\):=1\-d\_\{M\}\(A\)/\\\|A\\\|\_\{F\}^\{2\}\\in\[0,1\]is the fraction of matrix energy placed inside the pattern after optimal reordering\. For symmetric matrices and for the attention matrices we also minimize over a common permutation,dMcom​\(A\):=minπ⁡dM​\(A,π,π\)d\_\{M\}^\{\\mathrm\{com\}\}\(A\):=\\min\_\{\\pi\}d\_\{M\}\(A;\\pi,\\pi\)\(the caseσ=π\\sigma=\\pi\), writingdM​\(A,π\):=dM​\(A,π,π\)d\_\{M\}\(A;\\pi\):=d\_\{M\}\(A;\\pi,\\pi\)at a fixedπ\\pi; the restriction shrinks the feasible set, sodMcom​\(A\)≥dM​\(A\)d\_\{M\}^\{\\mathrm\{com\}\}\(A\)\\geq d\_\{M\}\(A\)\. The mask density isρM:=\|M\|1/n2\\rho\_\{M\}:=\|M\|\_\{1\}/n^\{2\}\(\|M\|1\|M\|\_\{1\}the number of ones\)\.dM​\(A\)=0d\_\{M\}\(A\)=0iffAAfits insideMMafter some reordering, and under independent uniform row and column permutations a fractionρM\\rho\_\{M\}of the energy lies inside the mask in expectation \(Appendix[B\.2](https://arxiv.org/html/2611.17674#A2.SS2)\)\.

Example \(two notions of matrix simplicity\)\.Pattern simplicity and low rank are independent: neither bounds the other\. LetA=P​S0​P⊤A=PS\_\{0\}P^\{\\top\}withS0S\_\{0\}kk\-block\-diagonal, constant blocks of sizeb=n/kb=n/kand entriesμ\>0\\mu\>0\. Thekk\-block mask fitsAAexactly,dM​\(A\)=0d\_\{M\}\(A\)=0, whileAAhaskkequal singular valuesμ​b\\mu b, so its best rank\-rrapproximation has squared Frobenius error\(k−r\)​b2​μ2\(k\-r\)\\,b^\{2\}\\mu^\{2\}for everyr<kr<k: what the mask describes by its support, low rank describes only at rankkk\. Conversely a generic rank\-oneu​u⊤uu^\{\\top\}, the simplest matrix for the SVD, fits no mask that leaves an entry out,dM​\(u​u⊤\)\>0d\_\{M\}\(uu^\{\\top\}\)\>0\. A matrix can thus be simple in one sense and not in the other, which is why Section[4](https://arxiv.org/html/2611.17674#S4)fits both parts jointly instead of choosing one\.

##### Hardness\.

###### Theorem 1\(NP\-hardness of pattern distance\)\.

ComputingdM​\(A\)d\_\{M\}\(A\)exactly is NP\-hard for the22\-block\-diagonal mask, for independent\(π,σ\)\(\\pi,\\sigma\)as well as underσ=π\\sigma=\\pi\.

*Proof sketch\.*Reduction fromMinimum Bisection\([Garey and Johnson, 1979](https://arxiv.org/html/2611.17674#bib.bib23)\)through the adjacency matrix of the graph with a heavy diagonal, which forces the row and column bisections to coincide; the band of width11underσ=π\\sigma=\\piis NP\-hard too, as a maximum\-weight Hamiltonian path \(Appendix[B\.5](https://arxiv.org/html/2611.17674#A2.SS5.SSS0.Px1)\)\. Hardness is mask\-specific: the arrowhead underσ=π\\sigma=\\piand the diagonal and anti\-diagonal masks with two permutations are solved exactly \(Appendix[C\.3](https://arxiv.org/html/2611.17674#A3.SS3)\)\.

##### Permutation ambiguities\.

An exact ordering need not be unique\. If a noiseless signal is nonzero at every position allowed by the mask and zero elsewhere, all zero\-error orderings differ only by symmetries of that mask \(Appendix[B\.6](https://arxiv.org/html/2611.17674#A2.SS6)\)\. Under a common row/column permutation these include the reversal of a banded order and arbitrary reorderings within blocks and among equal\-sized blocks; for an arrowhead mask withn≥3n\\geq 3the hub is identifiable, but the remaining indices have no identifiable order\.

## 3Alternating LAP

ComputingdM​\(A\)d\_\{M\}\(A\)is a search over two permutations at once: since permutations preserve∥⋅∥F\\\|\\cdot\\\|\_\{F\},dM​\(A\)=‖A‖F2−max⁡∑i,jπ,σ⁡Mi​j​Aπ−1​\(i\),σ−1​\(j\)2d\_\{M\}\(A\)=\\\|A\\\|\_\{F\}^\{2\}\-\\max\_\{\\pi,\\sigma\}\\sum\_\{i,j\}M\_\{ij\}\\,A\_\{\\pi^\{\-1\}\(i\),\\sigma^\{\-1\}\(j\)\}^\{2\}, a bilinear assignment objective, a QAP underσ=π\\sigma=\\pi\(NP\-hard, Theorem[1](https://arxiv.org/html/2611.17674#Thmtheorem1)\)\. Building on the alternating LAP schemes of[Goldengorin and Krushinsky \(2017\)](https://arxiv.org/html/2611.17674#bib.bib27)and[Sokol et al\. \(2020\)](https://arxiv.org/html/2611.17674#bib.bib51), we derive its assignment updates\.

###### Lemma 1\(Column\-separability\)\.

Fixπr\\pi\_\{r\}and letB=Pπr​AB=P\_\{\\pi\_\{r\}\}A\. WithQp,c:=∑i\(1−Mi,p\)​Bi,c2Q\_\{p,c\}:=\\sum\_\{i\}\(1\-M\_\{i,p\}\)\\,B\_\{i,c\}^\{2\},

minσ∈𝒮n⁡‖\(I−ΠM\)​\(B​Pσ⊤\)‖F2=min⁡∑cσ∈𝒮n⁡Qσ⁡\(c\),c,\\min\_\{\\sigma\\in\\mathcal\{S\}\_\{n\}\}\\bigl\\\|\(I\-\\Pi\_\{M\}\)\(BP\_\{\\sigma\}^\{\\top\}\)\\bigr\\\|\_\{F\}^\{2\}\\;=\\;\\min\_\{\\sigma\\in\\mathcal\{S\}\_\{n\}\}\\sum\_\{c\}Q\_\{\\sigma\(c\),c\},\(3\)a Linear Assignment Problem whose solutionLAP⁡\(Q\)\\mathrm\{LAP\}\(Q\)assigns each original columnccits positionσ⁡\(c\)\\sigma\(c\)\. The row case is symmetric \(Appendix[B](https://arxiv.org/html/2611.17674#A2)\)\.

HereQQis the auxiliary cost matrix of[Goldengorin and Krushinsky \(2017\)](https://arxiv.org/html/2611.17674#bib.bib27):Qp,cQ\_\{p,c\}is the off\-pattern cost of placing original columnccat positionppunder the fixed row order; since these costs do not depend on where the other columns go, choosing the column permutation is exactly a linear assignment problem\. Alternating the two one\-sided problems gives Algorithm[1](https://arxiv.org/html/2611.17674#alg1): from a spectral start \(the Fiedler order\([Barnard et al\., 1995](https://arxiv.org/html/2611.17674#bib.bib6)\); Appendix[D\.1](https://arxiv.org/html/2611.17674#A4.SS1)\), fix the rows and solve a column LAP, fix the columns and solve a row LAP, and repeat; random restarts guard against poor local minima\. A step costsO⁡\(n3\)O\(n^\{3\}\)\(auxiliary matrix and Hungarian solver\), a runO⁡\(R​T​n3\)O\(RTn^\{3\}\)forRRrestarts ofTTiterations\. Below,AltLAP​\(A,M,T,\(π0,σ0\)\)\\textsc\{AltLAP\}\(A,M,T;\\,\(\\pi\_\{0\},\\sigma\_\{0\}\)\)denotesTTiterations of Algorithm[1](https://arxiv.org/html/2611.17674#alg1)from\(π0,σ0\)\(\\pi\_\{0\},\\sigma\_\{0\}\)\(spectral start if the pair is omitted\)\.

Algorithm 1Alternating LAP \(worked example in Appendix[A\.2](https://arxiv.org/html/2611.17674#A1.SS2)\)0:

A∈ℝn×nA\\in\\mathbb\{R\}^\{n\\times n\}, mask

MM, iterations

TT, restarts

RR
1:

π^←\\hat\{\\pi\}\\leftarrowFiedler ordering

2:for

r=1,…,Rr=1,\\ldots,Rdo

3:

π0←π^\\pi\_\{0\}\\leftarrow\\hat\{\\pi\}if

r=1r\{=\}1, else a random permutation;

\(π,σ\)←\(π0,π0\)\(\\pi,\\sigma\)\\leftarrow\(\\pi\_\{0\},\\pi\_\{0\}\)
4:for

t=1,…,Tt=1,\\ldots,Tdo

5:

Qp​c←∑i\(1−Mi​p\)​\(Pπ​A\)i​c2Q\_\{pc\}\\leftarrow\\sum\_\{i\}\(1\{\-\}M\_\{ip\}\)\\,\(P\_\{\\pi\}A\)\_\{ic\}^\{2\};

σ←LAP⁡\(Q\)\\sigma\\leftarrow\\mathrm\{LAP\}\(Q\)
6:

Qp​irow←∑j\(1−Mp​j\)​\(A​Pσ⊤\)i​j2Q^\{\\mathrm\{row\}\}\_\{pi\}\\leftarrow\\sum\_\{j\}\(1\{\-\}M\_\{pj\}\)\\,\(AP\_\{\\sigma\}^\{\\top\}\)\_\{ij\}^\{2\};

π←LAP⁡\(Qrow\)\\pi\\leftarrow\\mathrm\{LAP\}\(Q^\{\\mathrm\{row\}\}\)
7:endfor

8:Update

\(π∗,σ∗\)\(\\pi^\{\*\},\\sigma^\{\*\}\)if

F⁡\(π,σ\)F\(\\pi,\\sigma\)improved;

π^←\\hat\{\\pi\}\\leftarrowbest

τ∈\{π^,π0,π,σ\}\\tau\\in\\\{\\hat\{\\pi\},\\pi\_\{0\},\\pi,\\sigma\\\}by

dM​\(A,τ,τ\)d\_\{M\}\(A;\\tau,\\tau\)
9:endfor

10:for

σ=π\\sigma=\\pi:Exchange: apply pairwise swaps to

π^\\hat\{\\pi\}while they lower

dM​\(A,π^,π^\)d\_\{M\}\(A;\\hat\{\\pi\},\\hat\{\\pi\}\)
11:returnbest

\(π∗,σ∗\)\(\\pi^\{\*\},\\sigma^\{\*\}\), or

π^\\hat\{\\pi\}

###### Proposition 1\(Monotone convergence\)\.

Each LAP sub\-step is a global minimizer of the one\-sided objective \(Lemma[1](https://arxiv.org/html/2611.17674#Thmlemma1)\), so the iterates satisfyF⁡\(π\(t\+1\),σ\(t\+1\)\)≤F⁡\(π\(t\),σ\(t\)\)F\(\\pi^\{\(t\+1\)\},\\sigma^\{\(t\+1\)\}\)\\leq F\(\\pi^\{\(t\)\},\\sigma^\{\(t\)\}\)withF⁡\(π,σ\)=‖\(I−ΠM\)​\(Pπ​A​Pσ⊤\)‖F2F\(\\pi,\\sigma\)=\\\|\(I\{\-\}\\Pi\_\{M\}\)\(P\_\{\\pi\}AP\_\{\\sigma\}^\{\\top\}\)\\\|\_\{F\}^\{2\}, and theFF\-values stabilize after finitely many steps; if ties in the LAP are broken in favour of the current permutation, the iterates themselves stop at a coordinate\-wise local minimum\. For a common permutation the exchange phase strictly decreasesdM​\(A,π,π\)d\_\{M\}\(A;\\pi,\\pi\)and stops at an order that no pairwise exchange improves\.

##### Common permutation\.

Forσ=π\\sigma=\\pithe two\-sided iterate is rounded to one permutation and finished by an exchange descent ondM​\(A,π,π\)d\_\{M\}\(A;\\pi,\\pi\): the change of an exchange has a closed form, two matrix products score alln2n^\{2\}exchanges, and improving ones are applied until none remains \(Appendix[D\.1](https://arxiv.org/html/2611.17674#A4.SS1)\)\. The LAP steps move whole rows and columns and stall on the ties a\{0,1\}\\\{0,1\\\}input induces inQQ; the exchanges move one pair at a time and finish the descent \(Appendix[E\.1](https://arxiv.org/html/2611.17674#A5.SS1)\)\.

##### Variants\.

The lemma uses only that the cost is a sum of per\-entry weights, so Algorithm[1](https://arxiv.org/html/2611.17674#alg1)runs on any separable score∑i​j\(1−Mi​j\)​Wπ−1​\(i\),σ−1​\(j\)\\sum\_\{ij\}\(1\-M\_\{ij\}\)\\,W\_\{\\pi^\{\-1\}\(i\),\\sigma^\{\-1\}\(j\)\}:W=A⊙AW=A\\odot Ais the pattern distance;W=AW=A\(AltLAP\-lin\) is the likelihood criterion for a mean shift rather than an energy contrast \(Section[5\.2](https://arxiv.org/html/2611.17674#S5.SS2)\)\.

## 4Pattern \+ Low\-Rank Decomposition

##### Formulation\.

ThePatLR decompositionapproximatesPπ​A​Pσ⊤P\_\{\\pi\}AP\_\{\\sigma\}^\{\\top\}by a pattern\-supported componentSS\(Si​j=0S\_\{ij\}=0whenMi​j=0M\_\{ij\}=0\) and a low\-rank componentU​V⊤UV^\{\\top\}of rank≤k\\leq k\. WritingX=Pπ⊤​U​V⊤​PσX=P\_\{\\pi\}^\{\\top\}UV^\{\\top\}P\_\{\\sigma\}for the low\-rank part in the original coordinates, the objective is

infπ,σ,S,X‖Pπ​\(A−X\)​PσT−S‖F2s\.t\.S⊙\(1−M\)=0,rank⁡\(X\)≤k\.\\inf\_\{\\pi,\\,\\sigma,\\,S,\\,X\}\\left\\\|P\_\{\\pi\}\(A\-X\)P\_\{\\sigma\}^\{T\}\-S\\right\\\|\_\{F\}^\{2\}\\quad\\text\{s\.t\.\}\\quad S\\odot\(1\-M\)=0,\\;\\;\\rank\(X\)\\leq k\.\(4\)For fixed\(π,σ,X\)\(\\pi,\\sigma,X\)the optimalSSis the mask projection of the permuted residual, and substituting it back gives

minS:S⊙\(1−M\)=0‖Pπ\(A−X\)PσT−S‖F2=dM\(A−X;π,σ\),\\min\_\{S:\\,S\\odot\(1\-M\)=0\}\\;\\left\\\|P\_\{\\pi\}\(A\-X\)P\_\{\\sigma\}^\{T\}\-S\\right\\\|\_\{F\}^\{2\}\\;=\\;d\_\{M\}\(A\-X;\\pi,\\sigma\),\(5\)so PatLR looks for a low\-rank component after whose removal the residual fits the pattern\. Algorithm[2](https://arxiv.org/html/2611.17674#alg2)alternates the two closed\-form updates,SSby mask projection andXXby the rank\-kkSVD ofAAminus the pattern part, with a*safeguarded*permutation update:AltLAP​\(A−X,M,TLAP,\(π,σ\)\)\\textsc\{AltLAP\}\(A\-X,M,T\_\{\\mathrm\{LAP\}\};\\,\(\\pi,\\sigma\)\)on the residual from the current pair is accepted only if it lowersdM​\(A−X,⋅\)d\_\{M\}\(A\-X;\\cdot\), andSSis then re\-synchronized\. For a common permutation the update takes the common\-permutation output of Algorithm[1](https://arxiv.org/html/2611.17674#alg1), setsσ=π\\sigma=\\piand comparesdM​\(A−X,π,π\)d\_\{M\}\(A\-X;\\pi,\\pi\); Proposition[2](https://arxiv.org/html/2611.17674#Thmproposition2)is unchanged\. The infimum need not be attained and the split betweenSSandXXneed not be unique: PatLR is a structured approximation model, scored by its reconstruction\. Sinceπ=σ=id\\pi=\\sigma=\\mathrm\{id\}withS=0S=0is feasible, the infimum never exceeds the rank\-kkSVD error, and the example of Section[2](https://arxiv.org/html/2611.17674#S2)shows that the gap can be large\.

Algorithm 2PatLR: Safeguarded Pattern \+ Low\-Rank Decomposition0:

A∈ℝn×nA\\in\\mathbb\{R\}^\{n\\times n\}, mask

MM, rank

kk, outer iterations

TT, LAP iterations

TLAPT\_\{\\mathrm\{LAP\}\}
1:

\(π,σ\)←AltLAP​\(A,M,TLAP\)\(\\pi,\\sigma\)\\leftarrow\\textsc\{AltLAP\}\(A,M,T\_\{\\mathrm\{LAP\}\}\);

X←0X\\leftarrow 0;

S←ΠM​\(Pπ​A​Pσ⊤\)S\\leftarrow\\Pi\_\{M\}\(P\_\{\\pi\}AP\_\{\\sigma\}^\{\\top\}\)
2:for

t=1,…,Tt=1,\\ldots,Tdo

3:

B←Pπ​\(A−X\)​Pσ⊤B\\leftarrow P\_\{\\pi\}\(A\{\-\}X\)P\_\{\\sigma\}^\{\\top\};

S←ΠM​\(B\)S\\leftarrow\\Pi\_\{M\}\(B\)
4:

X←SVDk​\(A−Pπ⊤​S​Pσ\)X\\leftarrow\\mathrm\{SVD\}\_\{k\}\(A\-P\_\{\\pi\}^\{\\top\}SP\_\{\\sigma\}\)
5:

\(π~,σ~\)←AltLAP​\(A−X,M,TLAP,\(π,σ\)\)\(\\tilde\{\\pi\},\\tilde\{\\sigma\}\)\\leftarrow\\textsc\{AltLAP\}\(A\-X,\\;M,\\;T\_\{\\mathrm\{LAP\}\};\\,\(\\pi,\\sigma\)\)
6:if

dM​\(A−X,π~,σ~\)<dM​\(A−X,π,σ\)d\_\{M\}\(A\{\-\}X;\\tilde\{\\pi\},\\tilde\{\\sigma\}\)<d\_\{M\}\(A\{\-\}X;\\pi,\\sigma\)then

\(π,σ\)←\(π~,σ~\)\(\\pi,\\sigma\)\\leftarrow\(\\tilde\{\\pi\},\\tilde\{\\sigma\}\)
7:

S←ΠM​\(Pπ​\(A−X\)​Pσ⊤\)S\\leftarrow\\Pi\_\{M\}\\bigl\(P\_\{\\pi\}\(A\{\-\}X\)P\_\{\\sigma\}^\{\\top\}\\bigr\)\{re\-synchronize

SSwith the accepted

\(π,σ\)\(\\pi,\\sigma\)\}

8:endfor

9:return

\(π,σ\),S,X\(\\pi,\\sigma\),\\;S,\\;X

###### Proposition 2\(Monotone convergence ofPatLR\)\.

ForF⁡\(π,σ,S,X\)=‖Pπ​\(A−X\)​Pσ⊤−S‖F2F\(\\pi,\\sigma,S,X\)=\\\|P\_\{\\pi\}\(A\-X\)P\_\{\\sigma\}^\{\\top\}\-S\\\|\_\{F\}^\{2\}subject toS⊙\(1−M\)=0S\\odot\(1\{\-\}M\)=0andrank⁡\(X\)≤k\\mathrm\{rank\}\(X\)\\leq k, Algorithm[2](https://arxiv.org/html/2611.17674#alg2)yields a non\-increasing sequence ofFF\-values, which therefore converges \(Appendix[C\.1](https://arxiv.org/html/2611.17674#A3.SS1)\)\. BecauseXXis continuous we do not claim finite termination or convergence of the iterates\(S,X\)\(S,X\)themselves; the algorithm stops at a toleranceε\\varepsilonon the decrease ofFFor a capped iteration count\.

### 4\.1Adaptive Pattern Selection

PatternMMis rarely known a priori\. We select it jointly with the permutations from a fixed vocabulary𝒱=\{M1,…,MK\}\\mathcal\{V\}=\\\{M\_\{1\},\\dots,M\_\{K\}\\\}by the*density\-normalized score*\(forA≠0A\\neq 0,ρM<1\\rho\_\{M\}<1\)

s~M​\(A,π,σ\):=dM​\(A,π,σ\)‖A‖F2⋅\(1−ρM\)3/2,s~M​\(A\):=minπ,σ⁡s~M​\(A,π,σ\)\.\\tilde\{s\}\_\{M\}\(A;\\pi,\\sigma\):=\\frac\{d\_\{M\}\(A;\\pi,\\sigma\)\}\{\\\|A\\\|\_\{F\}^\{2\}\\cdot\(1\-\\rho\_\{M\}\)^\{3/2\}\}\\,,\\qquad\\tilde\{s\}\_\{M\}\(A\):=\\min\_\{\\pi,\\sigma\}\\tilde\{s\}\_\{M\}\(A;\\pi,\\sigma\)\.\(6\)The denominator is a reference against independent uniform row and column permutations, which place a fractionρM\\rho\_\{M\}of the energy inside the mask in expectation \(Section[2](https://arxiv.org/html/2611.17674#S2)\); its superlinear exponent penalizes dense masks beyond this coverage advantage\. Under a common permutation the random\-permutation reference also depends on the split of the energy between the diagonal and the off\-diagonal entries \(Appendix[B\.2](https://arxiv.org/html/2611.17674#A2.SS2)\); the normalization is used as stated in both settings\. Without noise a mask and every mask containing it score00alike, so the identified geometry need not be unique \(Appendix[C\.2](https://arxiv.org/html/2611.17674#A3.SS2)\)\. The default vocabulary has nine masks, blocksk∈\{2,3,4,6\}k\\in\\\{2,3,4,6\\\}, bandsw∈\{1,2,4\}w\\in\\\{1,2,4\\\}, arrowhead and block\+band \(k=3k\{=\}3,w=2w\{=\}2\); any binary mask can be added\.

##### Adaptive PatLR\.

Pattern and permutation are searched jointly by simulated annealing over𝒱\\mathcal\{V\}with Metropolis acceptance ons~M\\tilde\{s\}\_\{M\}\(Algorithm[3](https://arxiv.org/html/2611.17674#alg3), Appendix[D\.2](https://arxiv.org/html/2611.17674#A4.SS2)\)\. The current\(π,σ\)\(\\pi,\\sigma\)is a warm start for*any*proposed pattern: good permutations for similar patterns are correlated, so a candidateMj′M\_\{j^\{\\prime\}\}is evaluated withℓ=3\\ell\{=\}3LAP steps instead of a fullAltLAPrun \(exchange phase andPatLRonly on the selected mask\)\. After screening every mask withℓ\\ellLAP steps \(O⁡\(K​ℓ​n3\)O\(K\\ell n^\{3\}\)\), theN=80N\{=\}80search iterations costO⁡\(N⁡\(1\+ℓ\)​n3\)O\(N\(1\{\+\}\\ell\)n^\{3\}\)independently ofKK; in practice the selection costs about onePatLRcall \(Appendix[E\.8](https://arxiv.org/html/2611.17674#A5.SS8)\)\.

## 5Experiments

Together, the experiments test whether one solver recovers different geometric structures, whether these structures complement low\-rank approximation, and whether they can be selected and interpreted on real data\. Unless stated otherwise we use a common row/column permutation \(σ=π\\sigma\{=\}\\pi\)\. We report our objective where the planted order is known and, where a task has its own literature, its metric alongside the methods developed for it\. Comparisons are paired over2020seeds with95%95\\%bootstrap intervals; Figure[2](https://arxiv.org/html/2611.17674#S5.F2)illustrates the outputs; setups, baselines and full grids are in Appendix[E](https://arxiv.org/html/2611.17674#A5)\.

![Refer to caption](https://arxiv.org/html/2611.17674v1/fig_showcase.png)Figure 2:Outputs of the framework on one input of each kind \(not a comparison\)\. Top: the input in its given order; bottom: the order found by Alternating LAP for the named pattern \(mask outlined in red\), with the in\-mask energy fraction1−dM​\(A,π\)/‖A‖F21\-d\_\{M\}\(A;\\pi\)/\\\|A\\\|\_\{F\}^\{2\}before and after\. The consecutive\-ones column uses two permutations; the attention head is atn=128n\{=\}128on a square\-root colour scale; the last column is the PatLR reconstructionS\+U​V⊤S\+UV^\{\\top\}\(rank33\) in the found order, with its explained variance\.### 5\.1Ordering Structures

Banded recovery \(our objective\)\.We first ask whether the generic solver optimizes the pattern distance as well as a general QAP solver and classical ordering heuristics do\. On randomly permuted banded targets in a Gaussian and a sparse\-graph regime, Table[1](https://arxiv.org/html/2611.17674#S5.T1)reports the error reduction \(ER, the fraction of the input’s off\-pattern mass removed by the found order\) of Alternating LAP next to reverse Cuthill–McKee\([Cuthill and McKee, 1969](https://arxiv.org/html/2611.17674#bib.bib16)\)\(RCM\), Fiedler ordering plus greedy 2\-SUM swaps \(F\+greedy\) and QAP\-FAQ\([Vogelstein et al\., 2015](https://arxiv.org/html/2611.17674#bib.bib55)\)\. Alternating LAP gives the largest reduction on the Gaussian inputs at everynnand on the sparse graphs atw=5w\{=\}5; FAQ is ahead by0\.040\.04–0\.060\.06on the sparsew=2w\{=\}2graphs, where the ties induced by binary inputs stall the LAP steps and the exchange phase carries the fit \(Appendix[E\.1](https://arxiv.org/html/2611.17674#A5.SS1)\)\. RCM and GPS reduce the bandwidth, a criterion that saturates on noisy inputs, rather than the off\-band mass \(Appendix[E\.2](https://arxiv.org/html/2611.17674#A5.SS2)\)\.

Table 1:Error reduction \(ER; higher = better\) on banded patterns,2020seeds\. RCM \(via KNN sparsification on dense inputs\) and F\+greedy \(Fiedler order plus greedy 2\-SUM swaps\) optimize other criteria; FAQ \(three starts\) and AltLAP \(five restarts\) both minimizedMd\_\{M\}\.Figure 3:Four classical tasks scored by their own metrics \(means,95%95\\%bootstrap intervals,2020seeds\)\. “Ours” is Alternating LAP on the mask of the task: \(a\) band of width2525from the spectral order; latent ordering,n=300n\{=\}300, correlation length2525\(yy\-axis from0\.920\.92\)\. \(b\) staircase of interval length1212from random restarts, with the same run on a random mask as control; noisy consecutive ones,60×6060\\times 60\. \(c\) equal\-size block mask; sparse SBM,k=4k\{=\}4, mean degree1616, drawn as the error1−ARI1\-\\mathrm\{ARI\}on a log axis \(lower is better; dotted: detectability threshold\)\. \(d\) block mask on the linear score, from random restarts and from the spectral partition; weighted planted partition,k=4k\{=\}4\.Latent ordering \(Figure[3](https://arxiv.org/html/2611.17674#S5.F3)a\)\.A lower pattern distance need not mean a more accurate order, so the remaining tasks are scored by their own metrics\. Planted Robinson matrices, scrambled and noised, scored by Kendall\|τ\|\|\\tau\|against the planted order, next to spectral seriation\([Atkins et al\., 1998](https://arxiv.org/html/2611.17674#bib.bib4)\)and the convex relaxation of[Fogel et al\. \(2013\)](https://arxiv.org/html/2611.17674#bib.bib21)\. Over2424configurations one Alternating LAP run from the spectral order, with the band width set to the generator’s correlation length, improves on spectral seriation in1818cells and matches or exceeds the convex relaxation in1919, the gain growing with noise and withnn; the exceptions are the cells atℓ=25\\ell\{=\}25,n=100n\{=\}100, where every method is nearτ=1\\tau\{=\}1, and one cell atℓ=6\\ell\{=\}6,n=100n\{=\}100where the relaxation leads by0\.040\.04\(Appendix Table[12](https://arxiv.org/html/2611.17674#A5.T12)\)\.

Consecutive ones \(Figure[3](https://arxiv.org/html/2611.17674#S5.F3)b\)\.The consecutive\-ones property \(every row an interval after a column order\([Booth and Lueker, 1976](https://arxiv.org/html/2611.17674#bib.bib9);[Kendall, 1971](https://arxiv.org/html/2611.17674#bib.bib31)\)\) is the staircase band in a rectangular matrix, fitted with independent row and column permutations \(Appendix[B\.1](https://arxiv.org/html/2611.17674#A2.SS1)\)\. On planted instances with flip noise, Alternating LAP from random restarts recovers the column order with a higherτ\\tauand fewer edits than convex seriation on every seed at every noise level, while a random or a block mask of the same density recovers almost nothing: the gain is the geometry of the mask\.

Circular seriation and the sensitivity of these fits to the mask width and to the generator are in Appendix[E\.6](https://arxiv.org/html/2611.17674#A5.SS6), as are nested matrices, a boundary case: where the marginals already determine the order, the general optimizer does not improve over the specialized one\.

### 5\.2Block Structures

We turn from order to grouping, where the block\-mask objective is the likelihood criterion of the planted models; on the weighted matrices the solver runs on the linear score \(AltLAP\-lin, Section[3](https://arxiv.org/html/2611.17674#S3)\)\.

Sparse and weighted block models \(Figure[3](https://arxiv.org/html/2611.17674#S5.F3)c,d\)\.On the sparse SBM at the detectability scale \(λ=1\\lambda\{=\}1the threshold\([Decelle et al\., 2011](https://arxiv.org/html/2611.17674#bib.bib19)\)\) the block\-mask objective is the maximum\-likelihood criterion\([Abbe, 2018](https://arxiv.org/html/2611.17674#bib.bib1)\), and two regimes appear: belowλ≈1\.5\\lambda\\approx 1\.5a better criterion value does not give a better partition \(Alternating LAP is below the Bethe Hessian in ARI, above it when started from its partition\); above this regime Alternating LAP is competitive with the specialized methods, with the highest ARI in most cells, and atc≥16c\\geq 16fromλ=1\.6\\lambda\{=\}1\.6on it matches or exceeds the spectral baselines \(Appendix Table[18](https://arxiv.org/html/2611.17674#A5.T18)\)\. On a weighted planted partition the linear score is the likelihood criterion and AltLAP\-lin is above spectral clustering fromμ=0\.35\\mu\{=\}0\.35on \(Appendix Table[19](https://arxiv.org/html/2611.17674#A5.T19)\)\. The spectral baselines receive the truekk; our mask also assumes equal block sizes, and under unequal planted sizes, sizes estimated from a spectral partition recover most of the gap \(Appendix Table[20](https://arxiv.org/html/2611.17674#A5.T20)\)\.

Composite target: a band inside blocks\.The band*inside*the blocks \(Figure[2](https://arxiv.org/html/2611.17674#S5.F2), third column\) tests the joint refinement of communities and their internal order: two structural hypotheses combined in one mask and refined by one criterion\. On1616planted configurations we compare the natural pipeline, spectral clustering then seriation inside each cluster, with the same pipeline followed by one Alternating LAP pass on the composite mask, with block boundaries re\-estimated from the order\. The pass raises the error reduction on the target in every configuration, from a median45%45\\%of the planted order’s value to94%94\\%, keeps the blocks exact and improves the within\-block order where the band is wide enough to determine it \(w=3w\{=\}3\); similar ER gains hold with convex seriation inside the clusters\. From a cold start the composite mask alone recovers the blocks only in part: the pipeline supplies the start and the mask the target \(Appendix Table[23](https://arxiv.org/html/2611.17674#A5.T23)\)\.

Labelled networks\.On four networks with published communities no single panel method is best; PatLR with rank11recovers the karate\-club split exactly \(Appendix Table[21](https://arxiv.org/html/2611.17674#A5.T21)\)\.

### 5\.3Pattern \+ Low\-Rank Decomposition

The experiments above test whether permutations reveal structure; we now ask whether representing it explicitly improves reconstruction beyond low rank\. We measuredenoising quality\(DQ\)=1−‖A^−Atrue‖F2/‖Atrue‖F2=1\-\\\|\\hat\{A\}\-A\_\{\\text\{true\}\}\\\|\_\{F\}^\{2\}/\\\|A\_\{\\text\{true\}\}\\\|\_\{F\}^\{2\}of reconstructionsA^\\hat\{A\}fromAtrue\+EA\_\{\\text\{true\}\}\+E\(EEsymmetric Gaussian\), against SVD and Robust PCA, on planted matrices whose family is known \(PatLR receives its mask\)\.

Planted structure at SNR 1 \(Figure[4](https://arxiv.org/html/2611.17674#S5.F4)\)\.Seven pattern families atn=200n\{=\}200, each planted alone and together with a rank\-33component of equal energy, scrambled, with noise atSNR=‖Atrue‖F2/‖E‖F2=1\\mathrm\{SNR\}=\\\|A\_\{\\text\{true\}\}\\\|\_\{F\}^\{2\}/\\\|E\\\|\_\{F\}^\{2\}=1, so that the noisy input has DQ00\. On the pattern alone the mask removes most of the noise and the low\-rank estimates little\. On pattern plus low rank no single component suffices, and PatLR reconstructs the combined signal more accurately than either estimate alone on the masks of density≤0\.25\\leq 0\.25\. On the two half\-dense masks every estimate that copies the in\-mask entries also copies their noise, and PatLR ends0\.030\.03–0\.040\.04below SVD \(bound in Appendix[E\.4](https://arxiv.org/html/2611.17674#A5.SS4)\)\.

Two controls\.A random mask of the same density, solver and rank stays0\.20\.2–0\.50\.5DQ below the planted mask \(0\.10\.1–0\.40\.4with the rank\-33component\), but above the SVD level on the band and anti\-diagonal masks\. Part of the gain is therefore mass that a free permutation packs into\|M\|\|M\|entries; the rest is the geometry\. At matched nominal parameter budgets PatLR has a higher mean DQ than SVD and spectral co\-clustering on all seven families \(Appendix Table[10](https://arxiv.org/html/2611.17674#A5.T10)\)\.

Figure 4:Denoising quality at SNR11\(n=200n\{=\}200,2020seeds,95%95\\%bootstrap intervals; the noisy input has DQ00\)\. \(a\) Planted pattern\. \(b\) Planted pattern plus a rank\-33component of equal energy\. SVD at the rank that maximizes DQ; RPCA; the pattern alone \(PatLR at rank00\); PatLR at rank33; and PatLR with a random mask of the same density as control\.Real data\.Where no truth is planted, Figure[2](https://arxiv.org/html/2611.17674#S5.F2)shows the decomposition of Les Misérables\([Knuth, 1993](https://arxiv.org/html/2611.17674#bib.bib32)\)under a four\-block template; Appendix Figure[8](https://arxiv.org/html/2611.17674#A5.F8)follows it step by step on this network, on the karate club\([Zachary, 1977](https://arxiv.org/html/2611.17674#bib.bib60)\)and on three feature\-correlation matrices: the pattern part takes the community blocks, the band and the feature groups, and the low\-rank part the hubs and the general correlation factor\.

### 5\.4Adaptive Pattern Selection

The experiments above give PatLR its mask; Algorithm[3](https://arxiv.org/html/2611.17674#alg3)selects it jointly with the permutation, and the experiment asks how much reconstruction quality this costs and whether the planted geometry is identified\. We plant each of the nine masks of the default vocabulary \(n=200n\{=\}200, with and without a rank\-3 component, SNR44and11;540540instances\) and compare Adaptive PatLR, run over these nine masks plus three gallery distractors, with Oracle PatLR \(the planted mask\), brute force over the same vocabulary and SVD at its best rank \(Figure[5](https://arxiv.org/html/2611.17674#S5.F5); Appendix[E\.5\.1](https://arxiv.org/html/2611.17674#A5.SS5.SSS1)\)\.

Quality \(Figure[5](https://arxiv.org/html/2611.17674#S5.F5)c\)\.Adaptive PatLR reaches the oracle’s denoising quality on essentially every instance \(median ratio1\.001\.00,55th percentile0\.920\.92\), where SVD at its best rank averages less than half of the oracle’s value at SNR11\.

Identification \(Figure[5](https://arxiv.org/html/2611.17674#S5.F5)a,b\)\.The outcome varies by family: arrowhead, block\+band and the block templatesk≥4k\\geq 4are recovered reliably, whereas thin bands and blockk=3k\{=\}3often select a broader or alternative mask \(a wider band, a block template or block\+band\) within0\.070\.07of the oracle’s DQ; good reconstruction therefore does not imply exact recovery of the geometry\. The anti\-diagonal and triangular distractors are never selected\.

Brute force\.An exhaustive scan of the vocabulary with the LAP phase gives the same reconstruction \(within0\.010\.01\) and similar selections at a cost growing with\|𝒱\|\|\\mathcal\{V\}\|; the search costs one PatLR call\.

![Refer to caption](https://arxiv.org/html/2611.17674v1/fig_adaptive_full.png)Figure 5:Adaptive pattern selection \(n=200n\{=\}200,540540instances\)\. \(a, b\) Mask selected by Adaptive PatLR \(columns; the checkerboard is counted with blockk=2k\{=\}2\) for each planted mask \(rows\) at SNR44and SNR11, in % of instances over both generators; red frames: the selected mask contains the planted one \(block\+band covers blockk=3k\{=\}3up to two rows\)\. \(c\) DQ of Adaptive against Oracle PatLR per instance\. Per\-family numbers: Appendix Table[11](https://arxiv.org/html/2611.17674#A5.T11)\.
### 5\.5Attention Heads

We use attention matrices to test whether pattern labels are stable across prompts and context lengths, whether the reordering adds information beyond the native token order, in which the literature describes head types, and whether the layerwise profile of labels is shared across three models\.

##### Setup\.

We score every head of GPT\-2, Qwen2\.5\-0\.5B andQwen2\.5\-7Bagainst a vocabulary of nine geometric masks \(bands, blocks, arrowhead, block\+band, diagonal\), applied to the causal attention matrices without requiring the reordered matrix to stay causal, with the density\-normalized score \([6](https://arxiv.org/html/2611.17674#S4.E6)\), on2020WikiText\-2 passages atn∈\{128,512\}n\\in\\\{128,512\\\}tokens; the native token order is a candidate for every mask, and the label of a \(head, prompt\) pair is the mask with the lowest score \(Appendix[E\.7](https://arxiv.org/html/2611.17674#A5.SS7)\)\.

##### Labels and layer organization\.

Arrowhead, the geometry of the attention sink\([Xiao et al\., 2024](https://arxiv.org/html/2611.17674#bib.bib59);[Zhai et al\., 2023](https://arxiv.org/html/2611.17674#bib.bib61)\), is the label of69%69\\%/67%67\\%/80%80\\%of the \(head, prompt\) pairs of GPT\-2 / Qwen2\.5\-0\.5B / Qwen2\.5\-7B atn=512n\{=\}512; block masks take most of the rest, thin bands and the diagonal a few percent\. The label is a fit, not the best of a poor set: the selected mask’s score is about an order of magnitude below its random\-permutation level\. By layer \(Figure[6](https://arxiv.org/html/2611.17674#S5.F6)a\), the first three to four layers of every model carry block labels and the later layers arrowhead; on Qwen2\.5\-0\.5B the last two layers return to block\-kk2\. Most block\-labelled pairs are wide local heads in the native token order, labelled by the block mask containing their window \(Appendix Figure[13](https://arxiv.org/html/2611.17674#A5.F13)\)\.

![Refer to caption](https://arxiv.org/html/2611.17674v1/fig_attention_main.png)Figure 6:Attention heads atn=512n\{=\}512, unified scoring\. \(a\) Qwen2\.5\-7B: share of the top\-11label per layer over2020prompts\. \(b\) Modal label per relative\-depth bin for the three models; markers show the bins where all three agree\. \(c\) Arrowhead share under the native token order and with reordering, with the share of \(head, prompt\) labels that change \(Appendix[E\.7\.4](https://arxiv.org/html/2611.17674#A5.SS7.SSS4)\)\.
##### Are the permutations needed?

Scoring the same pairs in their native token order \(Figure[6](https://arxiv.org/html/2611.17674#S5.F6)c\) changes a few percent of the labels on GPT\-2 and Qwen2\.5\-0\.5B; on Qwen2\.5\-7B the arrowhead share rises from0\.610\.61to0\.800\.80and23%23\\%of the labels change\. The reason is that on a quarter of the passages the sink is not the first token: there the native\-order arrowhead share is below2%2\\%, and the reordering restores the label \(Appendix[E\.7\.4](https://arxiv.org/html/2611.17674#A5.SS7.SSS4)\)\. The reordering thus buys a label independent of where the sink sits\.

##### Stability\.

The mean agreement of a head’s label with its modal label over the2020prompts is0\.960\.96–0\.990\.99for arrowhead heads and0\.640\.64–0\.740\.74for the others\. Betweenn=128n\{=\}128andn=512n\{=\}512the modal label of a head is unchanged for more than nine heads in ten\. On a shared1010\-bin relative\-depth grid the per\-layer modal label agrees across the three models in8/108/10bins \(Figure[6](https://arxiv.org/html/2611.17674#S5.F6)b\): blocks in the first tenth and arrowhead thereafter \(Appendix[E\.7\.3](https://arxiv.org/html/2611.17674#A5.SS7.SSS3)\)\.

## 6Discussion and Limitations

##### Limitations\.

The dense implementation costsO⁡\(n3\)O\(n^\{3\}\)per LAP step and per exchange round, which makes large\-matrix and long\-context analyses costly \(Appendix[E\.8](https://arxiv.org/html/2611.17674#A5.SS8)\)\. The permutation search is heuristic and does not guarantee global optimality \(Section[3](https://arxiv.org/html/2611.17674#S3)\)\. Adaptive selection operates within a supplied mask vocabulary: a selected label is the best fit among the candidates, not an identification of the generating geometry \(Section[5\.4](https://arxiv.org/html/2611.17674#S5.SS4)\)\. Our theoretical guarantees concern optimization, while recovery under noise is evaluated empirically\. The attention study covers three decoder\-only models at128128and512512tokens; other architectures and longer contexts remain future work\.

## 7Conclusion

We introduced*permutation\-structural simplicity*as an axis of matrix structure complementary to low rank: the pattern distance relates a dozen classical reordering problems to one objective \(Table[2](https://arxiv.org/html/2611.17674#A1.T2)\), Alternating LAP is one solver for any binary mask, PatLR adds a low\-rank residual, Adaptive PatLR selects the pattern from a vocabulary, and on attention heads the same score gives stable labels with one depth profile across three models\.

## Acknowledgments and Disclosure of Funding

We thank the anonymous reviewers and the area chair for suggestions that led to the specialized baselines, the capacity controls, and the hardness statement\. This work received no third\-party funding\. The authors declare no competing interests\.

## References

- Abbe \[2018\]Emmanuel Abbe\.Community detection and stochastic block models: Recent developments\.*Journal of Machine Learning Research*, 18\(177\):1–86, 2018\.URL[http://jmlr\.org/papers/v18/16\-480\.html](http://jmlr.org/papers/v18/16-480.html)\.
- Aeberhard and Forina \[1992\]Stefan Aeberhard and M\. Forina\.Wine\.UCI Machine Learning Repository, 1992\.
- Alpaydin and Kaynak \[1998\]E\. Alpaydin and C\. Kaynak\.Optical recognition of handwritten digits\.UCI Machine Learning Repository, 1998\.
- Atkins et al\. \[1998\]Jonathan E\. Atkins, Erik G\. Boman, and Bruce Hendrickson\.A spectral algorithm for seriation and the consecutive ones problem\.*SIAM Journal on Computing*, 28\(1\):297–310, 1998\.doi:10\.1137/S0097539795285771\.
- Aykanat et al\. \[2004\]Cevdet Aykanat, Ali Pinar, and Ümit V\. Çatalyürek\.Permuting sparse rectangular matrices into block\-diagonal form\.*SIAM Journal on Scientific Computing*, 25\(6\):1860–1879, 2004\.
- Barnard et al\. \[1995\]Stephen T\. Barnard, Alex Pothen, and Horst Simon\.A spectral algorithm for envelope reduction of sparse matrices\.*Numerical Linear Algebra with Applications*, 2\(4\):317–334, 1995\.doi:10\.1002/nla\.1680020402\.
- Berger and Schreck \[2017\]Annabell Berger and Berit Schreck\.The isomorphic version of Brualdi’s and Sanderson’s nestedness\.*Algorithms*, 10\(3\):74, 2017\.
- Bertsekas \[1988\]Dimitri P\. Bertsekas\.The auction algorithm: A distributed relaxation method for the assignment problem\.*Annals of Operations Research*, 14\(1\):105–123, 1988\.doi:10\.1007/BF02186476\.
- Booth and Lueker \[1976\]Kellogg S\. Booth and George S\. Lueker\.Testing for the consecutive ones property, interval graphs, and graph planarity using PQ\-tree algorithms\.*Journal of Computer and System Sciences*, 13\(3\):335–379, 1976\.
- Brualdi and Sanderson \[1999\]Richard A\. Brualdi and James G\. Sanderson\.Nested species subsets, gaps, and discrepancy\.*Oecologia*, 119\(2\):256–264, 1999\.
- Candès et al\. \[2011\]Emmanuel J\. Candès, Xiaodong Li, Yi Ma, and John Wright\.Robust principal component analysis?*Journal of the ACM*, 58\(3\):1–37, 2011\.doi:10\.1145/1970392\.1970395\.
- Çela \[1998\]Eranda Çela\.*The Quadratic Assignment Problem: Theory and Algorithms*\.Kluwer Academic Publishers, 1998\.
- Child et al\. \[2019\]Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever\.Generating long sequences with sparse transformers\.*arXiv preprint arXiv:1904\.10509*, 2019\.
- Clark et al\. \[2019\]Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D\. Manning\.What does BERT look at? An analysis of BERT’s attention\.In*Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP*, pages 276–286\. Association for Computational Linguistics, 2019\.doi:10\.18653/v1/W19\-4828\.
- Ćustić et al\. \[2017\]Ante Ćustić, Vladyslav Sokol, Abraham P\. Punnen, and Binay Bhattacharya\.The bilinear assignment problem: complexity and polynomially solvable special cases\.*Mathematical Programming*, 166:185–205, 2017\.
- Cuthill and McKee \[1969\]E\. Cuthill and J\. McKee\.Reducing the bandwidth of sparse symmetric matrices\.In*Proceedings of the 24th ACM National Conference*, pages 157–172, 1969\.doi:10\.1145/800195\.805928\.
- Cuturi \[2013\]Marco Cuturi\.Sinkhorn distances: Lightspeed computation of optimal transport\.In*Advances in Neural Information Processing Systems*, volume 26, 2013\.
- Davis et al\. \[1941\]Allison Davis, Burleigh B\. Gardner, and Mary R\. Gardner\.*Deep South: A Social Anthropological Study of Caste and Class*\.University of Chicago Press, Chicago, 1941\.
- Decelle et al\. \[2011\]Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová\.Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications\.*Physical Review E*, 84:066106, 2011\.
- Dhillon \[2001\]Inderjit S\. Dhillon\.Co\-clustering documents and words using bipartite spectral graph partitioning\.In*Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, pages 269–274, 2001\.
- Fogel et al\. \[2013\]Fajwel Fogel, Rodolphe Jenatton, Francis Bach, and Alexandre d’Aspremont\.Convex relaxations for permutation problems\.In*Advances in Neural Information Processing Systems*, volume 26, 2013\.
- Freeman \[2003\]Linton C\. Freeman\.Finding social groups: A meta\-analysis of the Southern Women data\.In Ronald Breiger, Kathleen Carley, and Philippa Pattison, editors,*Dynamic Social Network Modeling and Analysis: Workshop Summary and Papers*, pages 39–97\. National Academies Press, Washington, DC, 2003\.doi:10\.17226/10735\.
- Garey and Johnson \[1979\]Michael R\. Garey and David S\. Johnson\.*Computers and Intractability: A Guide to the Theory of NP\-Completeness*\.W\. H\. Freeman, 1979\.
- George \[1973\]Alan George\.Nested dissection of a regular finite element mesh\.*SIAM Journal on Numerical Analysis*, 10\(2\):345–363, 1973\.doi:10\.1137/0710032\.
- Gibbs et al\. \[1976\]Norman E\. Gibbs, William G\. Poole, and Paul K\. Stockmeyer\.An algorithm for reducing the bandwidth and profile of a sparse matrix\.*SIAM Journal on Numerical Analysis*, 13\(2\):236–250, 1976\.
- Girvan and Newman \[2002\]Michelle Girvan and M\. E\. J\. Newman\.Community structure in social and biological networks\.*Proceedings of the National Academy of Sciences*, 99\(12\):7821–7826, 2002\.doi:10\.1073/pnas\.122653799\.
- Goldengorin and Krushinsky \[2017\]Boris Goldengorin and Dmitry Krushinsky\.Linear assignment problems in combinatorial optimization\.In Sergiy Butenko, Panos M\. Pardalos, and Volodymyr Shylo, editors,*Optimization Methods and Applications: In Honor of Ivan V\. Sergienko’s 80th Birthday*, volume 130 of*Springer Optimization and Its Applications*, pages 183–216\. Springer, Cham, 2017\.doi:10\.1007/978\-3\-319\-68640\-0\_9\.
- Hajek et al\. \[2018\]Bruce Hajek, Yihong Wu, and Jiaming Xu\.Submatrix localization via message passing\.*Journal of Machine Learning Research*, 18\(186\):1–52, 2018\.
- Hartigan \[1972\]John A\. Hartigan\.Direct clustering of a data matrix\.*Journal of the American Statistical Association*, 67\(337\):123–129, 1972\.
- Holland et al\. \[1983\]Paul W\. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt\.Stochastic blockmodels: first steps\.*Social Networks*, 5\(2\):109–137, 1983\.doi:10\.1016/0378\-8733\(83\)90021\-7\.
- Kendall \[1971\]David G\. Kendall\.Seriation from abundance matrices\.In F\. R\. Hodson, D\. G\. Kendall, and P\. Tăutu, editors,*Mathematics in the Archaeological and Historical Sciences*, pages 215–252\. Edinburgh University Press, 1971\.
- Knuth \[1993\]Donald E\. Knuth\.*The Stanford GraphBase: A Platform for Combinatorial Computing*\.ACM Press / Addison\-Wesley, New York, 1993\.
- Koopmans and Beckmann \[1957\]Tjalling C\. Koopmans and Martin Beckmann\.Assignment problems and the location of economic activities\.*Econometrica*, 25\(1\):53–76, 1957\.doi:10\.2307/1907742\.
- Krzakala et al\. \[2013\]Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang\.Spectral redemption in clustering sparse networks\.*Proceedings of the National Academy of Sciences*, 110\(52\):20935–20940, 2013\.
- Lawler \[1963\]Eugene L\. Lawler\.The quadratic assignment problem\.*Management Science*, 9\(4\):586–599, 1963\.
- Leskovec et al\. \[2010\]Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani\.Kronecker graphs: An approach to modeling networks\.*Journal of Machine Learning Research*, 11:985–1042, 2010\.
- McConnell \[2004\]Ross M\. McConnell\.A certifying algorithm for the consecutive\-ones property\.In*Proceedings of the Fifteenth Annual ACM\-SIAM Symposium on Discrete Algorithms \(SODA\)*, pages 768–777, 2004\.
- Mena et al\. \[2018\]Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek\.Learning latent permutations with Gumbel\-Sinkhorn networks\.In*International Conference on Learning Representations*, 2018\.
- Merity et al\. \[2017\]Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher\.Pointer sentinel mixture models\.In*International Conference on Learning Representations*, 2017\.
- Newman \[2006\]M\. E\. J\. Newman\.Modularity and community structure in networks\.*Proceedings of the National Academy of Sciences*, 103\(23\):8577–8582, 2006\.doi:10\.1073/pnas\.0601602103\.
- Pool and Yu \[2021\]Jeff Pool and Chong Yu\.Channel permutations for N:M sparsity\.In*Advances in Neural Information Processing Systems*, volume 34, 2021\.
- Pothen and Fan \[1990\]Alex Pothen and Chin\-Ju Fan\.Computing the block triangular form of a sparse matrix\.*ACM Transactions on Mathematical Software*, 16\(4\):303–324, 1990\.
- Qin and Rohe \[2013\]Tai Qin and Karl Rohe\.Regularized spectral clustering under the degree\-corrected stochastic blockmodel\.In*Advances in Neural Information Processing Systems*, volume 26, 2013\.
- Qwen Team \[2024\]Qwen Team\.Qwen2\.5 technical report\.*arXiv preprint arXiv:2412\.15115*, 2024\.
- Radford et al\. \[2019\]Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever\.Language models are unsupervised multitask learners\.Technical report, OpenAI, 2019\.
- Recanati et al\. \[2018\]Antoine Recanati, Thomas Kerdreux, and Alexandre d’Aspremont\.Reconstructing latent orderings by spectral clustering\.*arXiv preprint arXiv:1807\.07122*, 2018\.
- Robinson \[1951\]W\. S\. Robinson\.A method for chronologically ordering archaeological deposits\.*American Antiquity*, 16\(4\):293–301, 1951\.doi:10\.2307/276978\.
- Rombach et al\. \[2014\]M\. Puck Rombach, Mason A\. Porter, James H\. Fowler, and Peter J\. Mucha\.Core\-periphery structure in networks\.*SIAM Journal on Applied Mathematics*, 74\(1\):167–190, 2014\.
- Saade et al\. \[2014\]Alaa Saade, Florent Krzakala, and Lenka Zdeborová\.Spectral clustering of graphs with the Bethe Hessian\.In*Advances in Neural Information Processing Systems*, volume 27, 2014\.
- Saxe \[1980\]James B\. Saxe\.Dynamic\-programming algorithms for recognizing small\-bandwidth graphs in polynomial time\.*SIAM Journal on Algebraic and Discrete Methods*, 1\(4\):363–369, 1980\.
- Sokol et al\. \[2020\]Vladyslav Sokol, Ante Ćustić, Abraham P\. Punnen, and Binay Bhattacharya\.Bilinear assignment problem: Large neighborhoods and experimental analysis of algorithms\.*INFORMS Journal on Computing*, 32\(3\):730–746, 2020\.doi:10\.1287/ijoc\.2019\.0893\.
- Tanner et al\. \[2019\]Jared Tanner, Andrew Thompson, and Simon Vary\.Matrix rigidity and the ill\-posedness of robust PCA and matrix completion\.*SIAM Journal on Mathematics of Data Science*, 1\(3\):537–554, 2019\.
- Traag et al\. \[2019\]Vincent A\. Traag, Ludo Waltman, and Nees Jan van Eck\.From Louvain to Leiden: guaranteeing well\-connected communities\.*Scientific Reports*, 9:5233, 2019\.
- Vandenberghe and Andersen \[2015\]Lieven Vandenberghe and Martin S\. Andersen\.Chordal graphs and semidefinite optimization\.*Foundations and Trends in Optimization*, 1\(4\):241–433, 2015\.
- Vogelstein et al\. \[2015\]Joshua T\. Vogelstein, John M\. Conroy, Vince Lyzinski, Louis J\. Podrazik, Steven G\. Kratzer, Eric T\. Harley, Donniell E\. Fishkind, R\. Jacob Vogelstein, and Carey E\. Priebe\.Fast approximate quadratic programming for graph matching\.*PLOS ONE*, 10\(4\):e0121002, 2015\.
- Voita et al\. \[2019\]Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov\.Analyzing multi\-head self\-attention: Specialized heads do the heavy lifting, the rest can be pruned\.In*Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics*, pages 5797–5808\. Association for Computational Linguistics, 2019\.doi:10\.18653/v1/P19\-1580\.
- von Luxburg \[2007\]Ulrike von Luxburg\.A tutorial on spectral clustering\.*Statistics and Computing*, 17\(4\):395–416, 2007\.doi:10\.1007/s11222\-007\-9033\-z\.
- Wolberg et al\. \[1993\]William Wolberg, Olvi Mangasarian, Nick Street, and W\. Street\.Breast cancer Wisconsin \(diagnostic\)\.UCI Machine Learning Repository, 1993\.
- Xiao et al\. \[2024\]Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis\.Efficient streaming language models with attention sinks\.In*International Conference on Learning Representations \(ICLR\)*, 2024\.
- Zachary \[1977\]Wayne W\. Zachary\.An information flow model for conflict and fission in small groups\.*Journal of Anthropological Research*, 33\(4\):452–473, 1977\.doi:10\.1086/jar\.33\.4\.3629752\.
- Zhai et al\. \[2023\]Shuangfei Zhai, Tatiana Likhomanenko, Etai Littwin, Dan Busbridge, Jason Ramapuram, Yizhe Zhang, Jiatao Gu, and Joshua M\. Susskind\.Stabilizing transformer training by preventing attention entropy collapse\.In*Proceedings of the 40th International Conference on Machine Learning \(ICML\)*, volume 202 of*PMLR*, pages 40770–40803, 2023\.
- Zhou and Tao \[2011\]Tianyi Zhou and Dacheng Tao\.GoDec: Randomized low\-rank & sparse matrix decomposition in noisy case\.In*Proceedings of the 28th International Conference on Machine Learning \(ICML\)*, pages 33–40, 2011\.

## Appendix APattern Dictionary, Worked Example and Notation

### A\.1Pattern dictionary

Table[2](https://arxiv.org/html/2611.17674#A1.T2)lists the pattern families of Figure[1](https://arxiv.org/html/2611.17674#S1.F1)together with the classical problems they encode; families used in our experiments are marked with a dagger, the others are included to delineate the scope of the formulation and are not analysed here\. Table[3](https://arxiv.org/html/2611.17674#A1.T3)relates the masks to the established problems and to the specialized methods used as baselines\.

Table 2:Pattern dictionary: mask families, the structure they encode and the classical problem behind each \(†\\dagger: used in our experiments\)\. The last column records only what this paper establishes about computingdMd\_\{M\}\(Theorem[1](https://arxiv.org/html/2611.17674#Thmtheorem1)and exact special cases\); dashes: not analysed here\.PatternMMShapeClassical problemdMd\_\{M\}in this paper*Order and locality*Diagonal†δi​j\\delta\_\{ij\}Linear assignment \(LAP\)one LAP§§Banded \(ww\)†\|i−j\|≤w\|i\-j\|\\leq wSeriation, bandwidth min\.\[[Atkins et al\., 1998](https://arxiv.org/html/2611.17674#bib.bib4),[Cuthill and McKee, 1969](https://arxiv.org/html/2611.17674#bib.bib16)\]NP\-hard atw=1w\{=\}1,σ=π\\sigma\{=\}\\pi\(App\.[B\.5](https://arxiv.org/html/2611.17674#A2.SS5.SSS0.Px1)\)Anti\-diagonal†i\+j=n\+1i\+j=n\+1Reverse ordering \(diagonal under column reversal\)one LAP§§Cyclic band†min⁡\(\|i−j\|,n−\|i−j\|\)≤w\\min\(\|i\-j\|,n\-\|i\-j\|\)\\leq wCircular seriation\[[Recanati et al\., 2018](https://arxiv.org/html/2611.17674#bib.bib46)\]–Upper triangular†i≤ji\\leq jLinear ordering / feedback arc set–¶2D grid stencil‖u−v‖1≤1\\\|u\-v\\\|\_\{1\}\\leq 1on a gridMesh / PDE orderings\[[George, 1973](https://arxiv.org/html/2611.17674#bib.bib24)\]–*Grouping and coupling*Block\-diagonal \(kk\)†kkdiagonal blocksCommunity detection, SBM\[[Holland et al\., 1983](https://arxiv.org/html/2611.17674#bib.bib30)\]NP\-hard, Thm\.[1](https://arxiv.org/html/2611.17674#Thmtheorem1)Block \+ band†blocks∪\\cupbandModular networks with local structure–Band\-in\-block†blocks∩\\capbandComposite target \(Sec\.[5\.2](https://arxiv.org/html/2611.17674#S5.SS2)\)–Bordered block\-diagonalblocks \+ coupling borderDecomposition for parallel LA / LP\[[Aykanat et al\., 2004](https://arxiv.org/html/2611.17674#bib.bib5)\]–Core–peripheryJc​c,Jc​p,Jp​cJ\_\{cc\},J\_\{cp\},J\_\{pc\},0p​p0\_\{pp\}Core–periphery structure\[[Rombach et al\., 2014](https://arxiv.org/html/2611.17674#bib.bib48)\]–Block\-triangularkkblocks, upper partDulmage–Mendelsohn decomposition\[[Pothen and Fan, 1990](https://arxiv.org/html/2611.17674#bib.bib42)\]–††*Hubs, nesting, intervals, localization*Arrowhead†row/col00\+ diagonalHub / sink structureO⁡\(n2\)O\(n^\{2\}\)underσ=π\\sigma\{=\}\\pi\(App\.[C\.3](https://arxiv.org/html/2611.17674#A3.SS3)\)Ferrers \(nested\)†𝟏\[j≤ri\]\\mathbf\{1\}\[j\\leq r\_\{i\}\],rrnon\-incr\.Nestedness\[[Brualdi and Sanderson, 1999](https://arxiv.org/html/2611.17674#bib.bib10),[Berger and Schreck, 2017](https://arxiv.org/html/2611.17674#bib.bib7)\]–♮Interval envelope†𝟏\[ℓi≤j≤ri\]\\mathbf\{1\}\[\\ell\_\{i\}\\leq j\\leq r\_\{i\}\]Consecutive ones, interval graphs\[[Booth and Lueker, 1976](https://arxiv.org/html/2611.17674#bib.bib9),[McConnell, 2004](https://arxiv.org/html/2611.17674#bib.bib37)\]–♮Localized biclusterk×ℓk\\times\\ellrectangleSubmatrix localization, biclustering\[[Hartigan, 1972](https://arxiv.org/html/2611.17674#bib.bib29),[Hajek et al\., 2018](https://arxiv.org/html/2611.17674#bib.bib28)\]–*Hierarchy, branching, self\-similarity, parity*Nested dissectionrecursive separatorsFill\-reducing orderings\[[George, 1973](https://arxiv.org/html/2611.17674#bib.bib24)\]–Clique treeoverlapping cliques on a treeChordal sparsity, GGMs\[[Vandenberghe and Andersen, 2015](https://arxiv.org/html/2611.17674#bib.bib54)\]–Kronecker supportK⊗qK^\{\\otimes q\}Kronecker graphs\[[Leskovec et al\., 2010](https://arxiv.org/html/2611.17674#bib.bib36)\]–Checkerboard†i\+ji\+jevenBalanced bisection \(the22\-block mask under the even/odd relabeling\)as22blocks‡Local \+ stridedband∪\\cupperiodic columnsSparse attention layouts\[[Child et al\., 2019](https://arxiv.org/html/2611.17674#bib.bib13)\]–§§With two permutations any permutation\-matrix mask is a single LAP \(Lemma[1](https://arxiv.org/html/2611.17674#Thmlemma1)\); underσ=π\\sigma=\\pithe diagonal objective is constant and the anti\-diagonal is a maximum\-weight matching\. The anti\-diagonal*band*of Section[5\.3](https://arxiv.org/html/2611.17674#S5.SS3)is the banded mask under column reversal\.¶Underσ=π\\sigma=\\pithe off\-pattern mass is the weight of the backward arcs, the linear\-ordering objective \(constant for symmetricAA\)\.††Dulmage–Mendelsohn computes the finest block\-triangular form in polynomial time; fitting a prescribed block profile with given sizes is a different problem\.♮Exact recognition of the noiseless structure is polynomial \([Berger and Schreck, 2017](https://arxiv.org/html/2611.17674#bib.bib7);[Booth and Lueker, 1976](https://arxiv.org/html/2611.17674#bib.bib9)\); our experiments concern the noisy fixed\-profile versions \(Appendix[E\.6\.2](https://arxiv.org/html/2611.17674#A5.SS6.SSS2)\)\.‡The same\-parity mask \(ones wherei\+ji\+jis even, including the diagonal\) is the22\-block mask under the even/odd relabeling, sodMd\_\{M\}coincides with the22\-block case; the opposite\-parity mask \(zero diagonal\) would correspond to maximum bisection instead and is not used\.Table 3:Correspondence between pattern masks and established problems, with the specialized methods used as baselines in this paper\.
### A\.2A6×66\\times 6example

Taken=6n=6, the band maskMi​j=1M\_\{ij\}=1iff\|i−j\|≤1\|i\-j\|\\leq 1, and the reference matrixBi​j=max⁡\(0,5−2​\|i−j\|\)B\_\{ij\}=\\max\(0,\\,5\-2\|i\-j\|\)\. Scramble it byp=\(0,2,4,1,3,5\)p=\(0,2,4,1,3,5\)\(zero\-based\), i\.e\.Ai​j=Bpi,pjA\_\{ij\}=B\_\{p\_\{i\},p\_\{j\}\}:

BB\(reference\)AA\(scrambled\)\(531000353100135310013531001353000135\)\\begin\{pmatrix\}5&3&1&0&0&0\\\\ 3&5&3&1&0&0\\\\ 1&3&5&3&1&0\\\\ 0&1&3&5&3&1\\\\ 0&0&1&3&5&3\\\\ 0&0&0&1&3&5\\end\{pmatrix\}\(510300151330015033330510033151003015\)\\begin\{pmatrix\}5&1&0&3&0&0\\\\ 1&5&1&3&3&0\\\\ 0&1&5&0&3&3\\\\ 3&3&0&5&1&0\\\\ 0&3&3&1&5&1\\\\ 0&0&3&0&1&5\\end\{pmatrix\}BBis concentrated near the diagonal but not exactly supported on the mask: its eight entries at\|i−j\|=2\|i\-j\|=2have magnitude one, so the optimum isdM​\(A\)=dM​\(B\)=8d\_\{M\}\(A\)=d\_\{M\}\(B\)=8, while the objective at the identity ordering is‖\(1−M\)⊙A‖F2=90\\\|\(1\-M\)\\odot A\\\|\_\{F\}^\{2\}=90\.*One step\.*With rows fixed, placing columnccat positionqqcostsQq,c=∑i\(1−Mi​q\)​Ai​c2Q\_\{q,c\}=\\sum\_\{i\}\(1\-M\_\{iq\}\)\\,A\_\{ic\}^\{2\}, the off\-pattern mass this placement would create \(Lemma[1](https://arxiv.org/html/2611.17674#Thmlemma1)\):

MM\(band,w=1w=1\)QQ\(rows==positionsqq, columns=c=c\)\(110000111000011100001110000111000011\)\\begin\{pmatrix\}1&1&0&0&0&0\\\\ 1&1&1&0&0&0\\\\ 0&1&1&1&0&0\\\\ 0&0&1&1&1&0\\\\ 0&0&0&1&1&1\\\\ 0&0&0&0&1&1\\end\{pmatrix\}\(91943263635918182627262510181026262626101810252627261818935362643199\)\\begin\{pmatrix\}9&19&43&26&36&35\\\\ 9&18&18&26&27&26\\\\ 25&10&18&10&26&26\\\\ 26&26&10&18&10&25\\\\ 26&27&26&18&18&9\\\\ 35&36&26&43&19&9\\end\{pmatrix\}An optimal assignment onQQorders the columns\(0,1,3,2,4,5\)\(0,1,3,2,4,5\)at cost7474, exactly the off\-pattern mass after the move; the row step is symmetric\.*Run\.*The successive exact one\-sided minimizations give90→74→40→890\\to 74\\to 40\\to 8, and both final orders equal\(0,3,1,4,2,5\)=p−1\(0,3,1,4,2,5\)=p^\{\-1\}, so the reordered matrix is exactlyBB\. Each step is the global optimum of its subproblem, so the objective never increases \(Proposition[1](https://arxiv.org/html/2611.17674#Thmproposition1)\); this does not imply global convergence in general, since other initializations or tied assignments can end at coordinatewise local minima, which is what the spectral initialization and the restarts address\.

### A\.3Notation and terminology

Table 4:Symbols and terms used throughout; standard notions \(LAP, QAP, Fiedler vector, ARI, Kendallτ\\tau\) are used in their usual sense\.

## Appendix BDeferred Proofs

### B\.1Basic identities and scope of the formulation

We use the conventionsAπ,σ:=Pπ​A​Pσ⊤A^\{\\pi,\\sigma\}:=P\_\{\\pi\}AP\_\{\\sigma\}^\{\\top\},\(Aπ,σ\)i​j=Aπ−1​\(i\),σ−1​\(j\)\(A^\{\\pi,\\sigma\}\)\_\{ij\}=A\_\{\\pi^\{\-1\}\(i\),\\sigma^\{\-1\}\(j\)\};ΠM​\(X\):=M⊙X\\Pi\_\{M\}\(X\):=M\\odot Xis the masking operator and\(I−ΠM\)​\(X\)=\(1−M\)⊙X\(I\-\\Pi\_\{M\}\)\(X\)=\(1\-M\)\\odot Xextracts the off\-pattern part\. For rectangularA,M∈ℝm×nA,M\\in\\mathbb\{R\}^\{m\\times n\}the same definitions apply withπ∈Sm\\pi\\in S\_\{m\},σ∈Sn\\sigma\\in S\_\{n\}andρM=\|M\|1/\(m​n\)\\rho\_\{M\}=\|M\|\_\{1\}/\(mn\); Lemma[1](https://arxiv.org/html/2611.17674#Thmlemma1)and Algorithm[1](https://arxiv.org/html/2611.17674#alg1)are unchanged, the two LAPs having sizesnnandmm\. The restrictionσ=π\\sigma=\\pigives the common\-permutation distancedMcom​\(A\)=minπ⁡dM​\(A,π\)d\_\{M\}^\{\\mathrm\{com\}\}\(A\)=\\min\_\{\\pi\}d\_\{M\}\(A;\\pi\)withdM​\(A,π\):=‖\(I−ΠM\)​\(Aπ\)‖F2d\_\{M\}\(A;\\pi\):=\\\|\(I\-\\Pi\_\{M\}\)\(A^\{\\pi\}\)\\\|\_\{F\}^\{2\}; it is natural for symmetricA=A⊤A=A^\{\\top\},M=M⊤M=M^\{\\top\}and is also imposed on the asymmetric attention matrices \(Section[5\.5](https://arxiv.org/html/2611.17674#S5.SS5)\)\. Because‖Aπ,σ‖F=‖A‖F\\\|A^\{\\pi,\\sigma\}\\\|\_\{F\}=\\\|A\\\|\_\{F\}, the partition of entries byMMyields the in\-pattern reformulationdM​\(A\)=‖A‖F2−maxπ,σ⁡‖ΠM​\(Aπ,σ\)‖F2d\_\{M\}\(A\)=\\\|A\\\|\_\{F\}^\{2\}\-\\max\_\{\\pi,\\sigma\}\\\|\\Pi\_\{M\}\(A^\{\\pi,\\sigma\}\)\\\|\_\{F\}^\{2\}\(Section[2](https://arxiv.org/html/2611.17674#S2)\), which we use freely in the proofs below\.

##### The boundary of the formulation\.

Masks whose objective does not depend on the permutation \(the full mask; underσ=π\\sigma=\\pithe diagonal and, for symmetricAA, the triangle\) are collected in Appendix[C\.3](https://arxiv.org/html/2611.17674#A3.SS3)\. Some classical notions of structure after reordering are not fixed binary supports and therefore fall outside Definition[1](https://arxiv.org/html/2611.17674#Thmdefinition1)as stated: Monge and Robinson matrices are ordering constraints on the*values*ofAA\(a Robinson matrix is banded only approximately, which is why Section[5\.1](https://arxiv.org/html/2611.17674#S5.SS1)fits a band of the correlation length to it\); a nested hierarchy of blocks coincides, as a binary mask, with its coarsest level, so the hierarchy is visible in a support only through separators \(nested dissection\); andN:MN\{:\}Msparsity\[[Pool and Yu, 2021](https://arxiv.org/html/2611.17674#bib.bib41)\]is a*family*of masks whose allowed positions differ between rows and groups, fitted by alternating the permutation with a per\-group selection of the support rather than with one mask\.

### B\.2Basic properties ofdMd\_\{M\}

\(i\) Nonnegativityfollows from the Frobenius norm being nonnegative\. EqualitydM​\(A\)=0d\_\{M\}\(A\)=0iff some\(π,σ\)\(\\pi,\\sigma\)places every off\-pattern entry ofAπ,σA^\{\\pi,\\sigma\}at zero, i\.e\.Aπ,σA^\{\\pi,\\sigma\}isMM\-supported\.

\(ii\) Upper bound\.By the in\-pattern reformulation of \([2](https://arxiv.org/html/2611.17674#S2.E2)\),dM​\(A\)=‖A‖F2−maxπ,σ⁡‖ΠM​\(Aπ,σ\)‖F2≤‖A‖F2d\_\{M\}\(A\)=\\\|A\\\|\_\{F\}^\{2\}\-\\max\_\{\\pi,\\sigma\}\\\|\\Pi\_\{M\}\(A^\{\\pi,\\sigma\}\)\\\|\_\{F\}^\{2\}\\leq\\\|A\\\|\_\{F\}^\{2\}\. For the tighter bound, average over\(π,σ\)∈𝒮n×𝒮n\(\\pi,\\sigma\)\\in\\mathcal\{S\}\_\{n\}\\times\\mathcal\{S\}\_\{n\}: each entryAk​l2A\_\{kl\}^\{2\}appears at each position\(i,j\)\(i,j\)with equal probability, so𝔼π,σ​\[‖ΠM​\(Aπ,σ\)‖F2\]=ρM​‖A‖F2\\mathbb\{E\}\_\{\\pi,\\sigma\}\[\\\|\\Pi\_\{M\}\(A^\{\\pi,\\sigma\}\)\\\|\_\{F\}^\{2\}\]=\\rho\_\{M\}\\\|A\\\|\_\{F\}^\{2\}\. Hencemaxπ,σ⁡‖ΠM​\(Aπ,σ\)‖F2≥ρM​‖A‖F2\\max\_\{\\pi,\\sigma\}\\\|\\Pi\_\{M\}\(A^\{\\pi,\\sigma\}\)\\\|\_\{F\}^\{2\}\\geq\\rho\_\{M\}\\\|A\\\|\_\{F\}^\{2\}, givingdM​\(A\)≤\(1−ρM\)​‖A‖F2d\_\{M\}\(A\)\\leq\(1\-\\rho\_\{M\}\)\\\|A\\\|\_\{F\}^\{2\}\. The averaging argument uses independentπ\\piandσ\\sigma\. Under the restrictionσ=π\\sigma=\\pia common permutation never moves a diagonal entry off the diagonal, so withDA=∑iAi​i2D\_\{A\}=\\sum\_\{i\}A\_\{ii\}^\{2\},OA=∑i≠jAi​j2O\_\{A\}=\\sum\_\{i\\neq j\}A\_\{ij\}^\{2\}andmdiagm\_\{\\mathrm\{diag\}\},moffm\_\{\\mathrm\{off\}\}the numbers of diagonal and off\-diagonal positions ofMM,𝔼π​‖ΠM​\(Aπ,π\)‖F2=mdiagn​DA\+moffn⁡\(n−1\)​OA\\mathbb\{E\}\_\{\\pi\}\\\|\\Pi\_\{M\}\(A^\{\\pi,\\pi\}\)\\\|\_\{F\}^\{2\}=\\tfrac\{m\_\{\\mathrm\{diag\}\}\}\{n\}D\_\{A\}\+\\tfrac\{m\_\{\\mathrm\{off\}\}\}\{n\(n\-1\)\}O\_\{A\}, and the bound\(1−ρM\)​‖A‖F2\(1\-\\rho\_\{M\}\)\\\|A\\\|\_\{F\}^\{2\}can fail: forA=\(0110\)A=\\bigl\(\\begin\{smallmatrix\}0&1\\\\ 1&0\\end\{smallmatrix\}\\bigr\)andM=I2M=I\_\{2\},minπ⁡dM​\(A,π,π\)=2\>\(1−ρM\)​‖A‖F2=1\\min\_\{\\pi\}d\_\{M\}\(A;\\pi,\\pi\)=2\>\(1\-\\rho\_\{M\}\)\\\|A\\\|\_\{F\}^\{2\}=1\. The same remark applies to the expectationρM​‖A‖F2\\rho\_\{M\}\\\|A\\\|\_\{F\}^\{2\}used to motivate the density normalization in Section[4\.1](https://arxiv.org/html/2611.17674#S4.SS1)\. More generally the common\-permutation distance is a restriction of the feasible set: it is never belowdM​\(A\)d\_\{M\}\(A\)and can exceed it even for symmetricAAandMM\(the same example hasdM​\(A\)=0d\_\{M\}\(A\)=0with two permutations and22under one\), so statements proved for independent permutations transfer to the caseσ=π\\sigma=\\pionly where this is said\.

\(iii\) Permutation invariance\.dM​\(Pα​A​PβT\)=minπ,σ⁡‖\(I−ΠM\)​\(Pπ​Pα​A​PβT​PσT\)‖F2=minπ,σ⁡‖\(I−ΠM\)​\(Pπ​α​A​Pσ​βT\)‖F2=minπ′,σ′⁡dM​\(A,π′,σ′\)=dM​\(A\)d\_\{M\}\(P\_\{\\alpha\}AP\_\{\\beta\}^\{T\}\)=\\min\_\{\\pi,\\sigma\}\\\|\(I\{\-\}\\Pi\_\{M\}\)\(P\_\{\\pi\}P\_\{\\alpha\}AP\_\{\\beta\}^\{T\}P\_\{\\sigma\}^\{T\}\)\\\|\_\{F\}^\{2\}=\\min\_\{\\pi,\\sigma\}\\\|\(I\{\-\}\\Pi\_\{M\}\)\(P\_\{\\pi\\alpha\}\\,A\\,P\_\{\\sigma\\beta\}^\{T\}\)\\\|\_\{F\}^\{2\}=\\min\_\{\\pi^\{\\prime\},\\sigma^\{\\prime\}\}d\_\{M\}\(A;\\pi^\{\\prime\},\\sigma^\{\\prime\}\)=d\_\{M\}\(A\), reparametrisingπ′=π​α\\pi^\{\\prime\}=\\pi\\alpha,σ′=σ​β\\sigma^\{\\prime\}=\\sigma\\beta\.□\\square

### B\.3Proof of Lemma[1](https://arxiv.org/html/2611.17674#Thmlemma1)\(Column\-separability\)

Expand the off\-pattern mass with rows fixed atπr\\pi\_\{r\}and columns atσ\\sigma:

∑i,j\(1−Mi​j\)​\(Pπr​A​PσT\)i​j2\\displaystyle\\sum\_\{i,j\}\(1\-M\_\{ij\}\)\\,\(P\_\{\\pi\_\{r\}\}AP\_\{\\sigma\}^\{T\}\)\_\{ij\}^\{2\}=∑i,j\(1−Mi​j\)​Aπr−1​\(i\),σ−1​\(j\)2=∑i,j\(1−Mi​j\)​Bi,σ−1​\(j\)2\.\\displaystyle=\\sum\_\{i,j\}\(1\-M\_\{ij\}\)\\,A\_\{\\pi\_\{r\}^\{\-1\}\(i\),\\,\\sigma^\{\-1\}\(j\)\}^\{2\}=\\sum\_\{i,j\}\(1\-M\_\{ij\}\)\\,B\_\{i,\\,\\sigma^\{\-1\}\(j\)\}^\{2\}\.\(7\)Substitutingp=jp=j\(target position\) andc=σ−1​\(j\)c=\\sigma^\{\-1\}\(j\)\(original column placed at positionjj\):

\([7](https://arxiv.org/html/2611.17674#A2.E7)\)=∑p=1n∑i=1n\(1−Mi​p\)​Bi,σ−1​\(p\)2=∑c=1n∑i=1n\(1−Mi,σ⁡\(c\)\)​Bi,c2=∑c=1nQσ⁡\(c\),c,\\displaystyle=\\sum\_\{p=1\}^\{n\}\\sum\_\{i=1\}^\{n\}\(1\-M\_\{ip\}\)\\,B\_\{i,\\,\\sigma^\{\-1\}\(p\)\}^\{2\}=\\sum\_\{c=1\}^\{n\}\\sum\_\{i=1\}^\{n\}\(1\-M\_\{i,\\sigma\(c\)\}\)\\,B\_\{i,c\}^\{2\}=\\sum\_\{c=1\}^\{n\}Q\_\{\\sigma\(c\),\\,c\}\\,,\(8\)usingQp,c=∑i\(1−Mi​p\)​Bi​c2Q\_\{p,c\}=\\sum\_\{i\}\(1\-M\_\{ip\}\)B\_\{ic\}^\{2\}\. The expression∑cQσ⁡\(c\),c\\sum\_\{c\}Q\_\{\\sigma\(c\),c\}over bijectionsσ:\[n\]→\[n\]\\sigma\\colon\[n\]\\to\[n\]is exactly a Linear Assignment Problem\. The row case follows identically with rows and columns exchanged\.□\\square

### B\.4Proof of Proposition[1](https://arxiv.org/html/2611.17674#Thmproposition1)\(Monotone convergence\)

DefineF⁡\(πr,σ\):=‖\(I−ΠM\)​\(Pπr​A​PσT\)‖F2F\(\\pi\_\{r\},\\sigma\):=\\left\\\|\(I\-\\Pi\_\{M\}\)\(P\_\{\\pi\_\{r\}\}AP\_\{\\sigma\}^\{T\}\)\\right\\\|\_\{F\}^\{2\}\. At each half\-step, one permutation is fixed and the other is set to the*global*minimizer of the resulting LAP \(Lemma[1](https://arxiv.org/html/2611.17674#Thmlemma1)\):

σ\(t\+1\)=arg⁡minσ⁡F⁡\(πr\(t\),σ\)⇒F⁡\(πr\(t\),σ\(t\+1\)\)≤F⁡\(πr\(t\),σ\(t\)\)\.\\sigma^\{\(t\+1\)\}=\\arg\\min\_\{\\sigma\}F\(\\pi\_\{r\}^\{\(t\)\},\\sigma\)\\;\\;\\Rightarrow\\;\\;F\(\\pi\_\{r\}^\{\(t\)\},\\sigma^\{\(t\+1\)\}\)\\leq F\(\\pi\_\{r\}^\{\(t\)\},\\sigma^\{\(t\)\}\)\.Similarly,πr\(t\+1\)=arg⁡minπr⁡F⁡\(πr,σ\(t\+1\)\)\\pi\_\{r\}^\{\(t\+1\)\}=\\arg\\min\_\{\\pi\_\{r\}\}F\(\\pi\_\{r\},\\sigma^\{\(t\+1\)\}\)givesF⁡\(πr\(t\+1\),σ\(t\+1\)\)≤F⁡\(πr\(t\),σ\(t\+1\)\)F\(\\pi\_\{r\}^\{\(t\+1\)\},\\sigma^\{\(t\+1\)\}\)\\leq F\(\\pi\_\{r\}^\{\(t\)\},\\sigma^\{\(t\+1\)\}\)\. Each full iteration reduces \(or maintains\)FF\. SinceFFtakes values in the finite set\{F\(π,σ\):π,σ∈𝒮n\}\\\{F\(\\pi,\\sigma\):\\pi,\\sigma\\in\\mathcal\{S\}\_\{n\}\\\}, the sequence of values is eventually constant\. Stabilization of the values alone does not stop the iterates: when the LAP has several optimal assignments the permutations can keep moving on a plateau of constantFF\. If ties are broken by keeping the current permutation whenever it already attains the LAP optimum, every change of a permutation strictly decreasesFF, so only finitely many changes occur and the final pair is a coordinate\-wise local minimum \(neither one\-sided LAP can improve it\)\.□\\square

### B\.5Proof of Theorem[1](https://arxiv.org/html/2611.17674#Thmtheorem1)\(NP\-hardness\)

Throughout,G=\(V,E\)G=\(V,E\)is a simple graph with\|V\|=n\|V\|=nand\|E\|=m\|E\|=m, andAGA\_\{G\}its\{0,1\}\\\{0,1\\\}adjacency matrix\. Restricting the feasible set toσ=π\\sigma=\\pichanges the problem, so hardness of the symmetric problem does not by itself imply hardness of the two\-permutation problem; the reduction treats both cases\. For a pair\(π,σ\)\(\\pi,\\sigma\)the entryAu​vA\_\{uv\}is placed at position\(π⁡\(u\),σ⁡\(v\)\)\(\\pi\(u\),\\sigma\(v\)\)\.

We reduce fromMinimum Bisection\[[Garey and Johnson, 1979](https://arxiv.org/html/2611.17674#bib.bib23)\]: givenGGwithnneven, find\|S\|=n/2\|S\|=n/2minimizingcut⁡\(S,S¯\)\\mathrm\{cut\}\(S,\\bar\{S\}\)\. LetMMbe the22\-block mask with blocks of sizen/2n/2and set

A=AG\+\(m\+1\)​I\.A\\;=\\;A\_\{G\}\+\(m\+1\)\\,I\.For\(π,σ\)\(\\pi,\\sigma\)letSSbe the set of vertices thatπ\\piplaces in the firstn/2n/2row positions andTTthe set thatσ\\sigmaplaces in the firstn/2n/2column positions\. An entry is off\-pattern iff its row and column positions lie in different blocks, so

dM​\(A,π,σ\)=\(m\+1\)2​\|S​△​T\|\+∑u∈S,v∉T\(AG\)u​v\+∑u∉S,v∈T\(AG\)u​v\.d\_\{M\}\(A;\\pi,\\sigma\)\\;=\\;\(m\+1\)^\{2\}\\,\|S\\,\\triangle\\,T\|\\;\+\\;\\sum\_\{u\\in S,\\,v\\notin T\}\(A\_\{G\}\)\_\{uv\}\\;\+\\;\\sum\_\{u\\notin S,\\,v\\in T\}\(A\_\{G\}\)\_\{uv\}\.The two edge sums together are at most2​m2m\. IfS≠TS\\neq Tthen, because\|S\|=\|T\|\|S\|=\|T\|,\|S​△​T\|≥2\|S\\triangle T\|\\geq 2anddM​\(A,π,σ\)≥2​\(m\+1\)2\>2​md\_\{M\}\(A;\\pi,\\sigma\)\\geq 2\(m\+1\)^\{2\}\>2m, whereas any pair withS=TS=Tcosts exactly2​cut​\(S,S¯\)≤2​m2\\,\\mathrm\{cut\}\(S,\\bar\{S\}\)\\leq 2m\. Hence every minimizer hasS=TS=TanddM​\(A\)=2​min\|S\|=n/2⁡cut⁡\(S,S¯\)d\_\{M\}\(A\)=2\\min\_\{\|S\|=n/2\}\\mathrm\{cut\}\(S,\\bar\{S\}\)\. The same identity holds underσ=π\\sigma=\\pi\(whereS=TS=Tautomatically\), which is the original symmetric reduction\.□\\square

##### The band of width11underσ=π\\sigma=\\pi\.

LetAAbe symmetric andMMthe banded mask withw=1w=1\. Underσ=π\\sigma=\\pithe in\-band mass is

∑\|i−j\|≤1Aπ−1​\(i\),π−1​\(j\)2=∑uAu​u2\+2​∑i=1n−1Aπ−1​\(i\),π−1​\(i\+1\)2,\\sum\_\{\|i\-j\|\\leq 1\}A^\{2\}\_\{\\pi^\{\-1\}\(i\),\\pi^\{\-1\}\(j\)\}\\;=\\;\\sum\_\{u\}A\_\{uu\}^\{2\}\\;\+\\;2\\sum\_\{i=1\}^\{n\-1\}A^\{2\}\_\{\\pi^\{\-1\}\(i\),\\pi^\{\-1\}\(i\+1\)\},so by the in\-pattern reformulation \(Section[2](https://arxiv.org/html/2611.17674#S2)\) minimizingdMd\_\{M\}is equivalent to maximizing∑iAπ−1​\(i\),π−1​\(i\+1\)2\\sum\_\{i\}A^\{2\}\_\{\\pi^\{\-1\}\(i\),\\pi^\{\-1\}\(i\+1\)\}over orderings, i\.e\. finding a maximum\-weight Hamiltonian path in the complete graph with edge weightsAu​v2A\_\{uv\}^\{2\}\. ForA=AGA=A\_\{G\}this sum equalsn−1n\-1iffGGhas a Hamiltonian path, so even\{0,1\}\\\{0,1\\\}weights suffice and computing the value ofdMd\_\{M\}is NP\-hard\[[Garey and Johnson, 1979](https://arxiv.org/html/2611.17674#bib.bib23)\]\. Deciding whetherdM=0d\_\{M\}=0\(bandwidth11\) is polynomial\[[Saxe, 1980](https://arxiv.org/html/2611.17674#bib.bib50)\]; the hardness concerns the value ofdMd\_\{M\}when it is positive, and we do not claim it for independent permutations\.□\\square

### B\.6Permutation ambiguities: automorphisms of a mask

In words: a planted instance has zero error at the planted permutations; any other zero\-error pair must place the whole support of the signal inside the mask; and when the signal fills the mask, such a pair can only be a symmetry of the mask\. Formally, letAut\(M\):=\{\(α,β\)∈𝒮n2:Mα⁡\(i\),β⁡\(j\)=Mi​j∀i,j\}\\Aut\(M\):=\\\{\(\\alpha,\\beta\)\\in\\mathcal\{S\}\_\{n\}^\{2\}:M\_\{\\alpha\(i\),\\beta\(j\)\}=M\_\{ij\}\\;\\forall i,j\\\}be the joint automorphism group ofMM\(the pairs of row and column permutations that map the mask onto itself\), andAutsym⁡\(M\):=\{σ∈𝒮n:Mσ⁡\(i\),σ⁡\(j\)=Mi​j\}\\Aut^\{\\mathrm\{sym\}\}\(M\):=\\\{\\sigma\\in\\mathcal\{S\}\_\{n\}:M\_\{\\sigma\(i\),\\sigma\(j\)\}=M\_\{ij\}\\\}its single\-permutation version forM=M⊤M=M^\{\\top\}\.

###### Proposition 3\(Zero\-error permutations\)\.

LetS0S\_\{0\}beMM\-supported andA=Pπ∗⊤​S0​Pσ∗A=P\_\{\\pi^\{\*\}\}^\{\\top\}S\_\{0\}\\,P\_\{\\sigma^\{\*\}\}\. ThendM​\(A\)=0d\_\{M\}\(A\)=0, attained at\(π∗,σ∗\)\(\\pi^\{\*\},\\sigma^\{\*\}\); every pair withdM​\(A,π^,σ^\)=0d\_\{M\}\(A;\\hat\{\\pi\},\\hat\{\\sigma\}\)=0has relative permutations\(α,β\)=\(π^∘\(π∗\)−1,σ^∘\(σ∗\)−1\)\(\\alpha,\\beta\)=\(\\hat\{\\pi\}\\circ\(\\pi^\{\*\}\)^\{\-1\},\\hat\{\\sigma\}\\circ\(\\sigma^\{\*\}\)^\{\-1\}\), the found pair expressed relative to the planted one, for whichPα​S0​Pβ⊤P\_\{\\alpha\}S\_\{0\}P\_\{\\beta\}^\{\\top\}isMM\-supported; and ifsupp⁡\(S0\)=supp⁡\(M\)\\supp\(S\_\{0\}\)=\\supp\(M\), then\(α,β\)∈Aut⁡\(M\)\(\\alpha,\\beta\)\\in\\Aut\(M\)\. Underσ=π\\sigma=\\pithe same holds for instances planted by one permutation,A=Pπ∗⊤​S0​Pπ∗A=P\_\{\\pi^\{\*\}\}^\{\\top\}S\_\{0\}P\_\{\\pi^\{\*\}\}, withAutsym⁡\(M\)\\Aut^\{\\mathrm\{sym\}\}\(M\)in place ofAut⁡\(M\)\\Aut\(M\)\(an instance planted by two different permutations need not havedM​\(A,π\)=0d\_\{M\}\(A;\\pi\)=0for anyπ\\pi\)\.

###### Proof\.

dM​\(A,π∗,σ∗\)=‖\(I−ΠM\)​\(S0\)‖F2=0d\_\{M\}\(A;\\pi^\{\*\},\\sigma^\{\*\}\)=\\left\\\|\(I\-\\Pi\_\{M\}\)\(S\_\{0\}\)\\right\\\|\_\{F\}^\{2\}=0by the support condition\. IfdM​\(A,π^,σ^\)=0d\_\{M\}\(A;\\hat\{\\pi\},\\hat\{\\sigma\}\)=0thenPπ^​A​Pσ^⊤=Pα​S0​Pβ⊤P\_\{\\hat\{\\pi\}\}AP\_\{\\hat\{\\sigma\}\}^\{\\top\}=P\_\{\\alpha\}S\_\{0\}P\_\{\\beta\}^\{\\top\}isMM\-supported\. If moreoversupp⁡\(S0\)=supp⁡\(M\)\\supp\(S\_\{0\}\)=\\supp\(M\), thensupp⁡\(Pα​S0​Pβ⊤\)=\{\(α⁡\(i\),β⁡\(j\)\):Mi​j=1\}⊆supp⁡\(M\)\\supp\(P\_\{\\alpha\}S\_\{0\}P\_\{\\beta\}^\{\\top\}\)=\\\{\(\\alpha\(i\),\\beta\(j\)\):M\_\{ij\}=1\\\}\\subseteq\\supp\(M\), and since permutations preserve cardinality the containment is an equality, i\.e\.Mα⁡\(i\),β⁡\(j\)=Mi​jM\_\{\\alpha\(i\),\\beta\(j\)\}=M\_\{ij\}for alli,ji,j\. The symmetric case is the same argument withα=β\\alpha=\\beta\. Note thatAut⁡\(M\)\\Aut\(M\)is the joint row×\\timescolumn action, in general strictly larger than the product of the row and column stabilizers: forM=InM=I\_\{n\}it is the diagonal copy of𝒮n\\mathcal\{S\}\_\{n\}, while the only purely row\-preserving permutation is the identity\. ∎

###### Proposition 4\(Automorphism groups of symmetric patterns\)\.

In the symmetric case \(σ=π\\sigma=\\pi,M=M⊤M=M^\{\\top\}\) the ambiguities of the three main families are the following\.

1. \(i\)Banded mask\(Mi​j=𝟏\[\|i−j\|≤w\]M\_\{ij\}=\\mathbf\{1\}\[\|i\{\-\}j\|\\leq w\],w≥1w\\geq 1,n\>2​w\+1n\>2w\{\+\}1\): the only symmetries are the identity and the reversali↦n\+1−ii\\mapsto n\{\+\}1\{\-\}i, so an order is recoverable up to global reversal;Autsym⁡\(M\)=\{id,rev\}\\Aut^\{\\mathrm\{sym\}\}\(M\)=\\\{\\mathrm\{id\},\\,\\mathrm\{rev\}\\\}\.
2. \(ii\)kk\-block mask\(equal blocks of sizeb=n/kb=n/k\): the symmetries are arbitrary permutations of thekkblocks combined with arbitrary permutations within each block, so the partition into blocks is recoverable and the order within a block is not;Autsym⁡\(M\)≅\(Sb\)k⋊Sk\\Aut^\{\\mathrm\{sym\}\}\(M\)\\cong\(S\_\{b\}\)^\{k\}\\rtimes S\_\{k\}, the wreath productSb≀SkS\_\{b\}\\wr S\_\{k\}\.
3. \(iii\)Arrowhead mask\(n≥3n\\geq 3\): every permutation fixing the hub is a symmetry and no other is, so only the hub is identifiable;Autsym⁡\(M\)≅Sn−1\\Aut^\{\\mathrm\{sym\}\}\(M\)\\cong S\_\{n\-1\}\.

These ambiguities fix what recovery can mean, and the experiments score accordingly: an order by\|τ\|\|\\tau\|, i\.e\. up to reversal \(Section[5\.1](https://arxiv.org/html/2611.17674#S5.SS1)\), a partition by ARI \(Section[5\.2](https://arxiv.org/html/2611.17674#S5.SS2)\), and an arrowhead fit as the identification of a hub\.

###### Proof\.

For \(i\): in the simple graph on\{1,…,n\}\\\{1,\\dots,n\\\}defined by the off\-diagonal support ofMM\(i∼ji\\sim jiff1≤\|i−j\|≤w1\\leq\|i\-j\|\\leq w; the diagonal is preserved by every permutation\), the vertices of minimum degreewware exactly11andnn\(forw≥1w\\geq 1andn\>2​w\+1n\>2w\{\+\}1every interior vertex has degree≥w\+1\\geq w\{\+\}1\), so an automorphism fixes or swaps them; composing withrev\\mathrm\{rev\}we may assumeσ⁡\(1\)=1\\sigma\(1\)=1\. The neighbours2,…,w\+12,\\dots,w\{\+\}1of vertex11have the distinct degreesw\+1,…,2​ww\{\+\}1,\\dots,2w, so each is fixed, and forj=2,…,n−wj=2,\\dots,n\{\-\}wthe closed neighbourhood of the fixed vertexjjcontains exactly one vertex not yet fixed,j\+wj\{\+\}w, which is therefore fixed as well\. Henceσ=id\\sigma=\\mathrm\{id\}\. \(Atw=0w=0the mask isInI\_\{n\}and every permutation is an automorphism\.\) For \(ii\):Mi​j=1M\_\{ij\}=1iff⌈i/b⌉=⌈j/b⌉\\lceil i/b\\rceil=\\lceil j/b\\rceil, so the off\-diagonal support is a disjoint union ofkkcliques of sizebb; an automorphism maps cliques to cliques, hence permutes the blocks and acts by an arbitrary permutation within each\. For \(iii\): anyσ\\sigmawithσ⁡\(1\)=1\\sigma\(1\)=1preservesMM, and forn≥3n\\geq 3the hub is the only vertex adjacent to all others, so every automorphism fixes it \(atn=2n=2the arrowhead is the full mask\)\. ∎

## Appendix CFurther Properties of the Framework

### C\.1PatLR updates and proof of monotone convergence

The infimum in \([4](https://arxiv.org/html/2611.17674#S4.E4)\) need not be attained: the set of sumsS\+U​V⊤S\+UV^\{\\top\}is not closed, as for low\-rank plus sparse models\[[Tanner et al\., 2019](https://arxiv.org/html/2611.17674#bib.bib52)\]; the algorithm uses only the conditional minimizers inSSandXX, which exist, and a safeguarded proposal in the permutations\. Nor is the split unique: for an in\-mask position\(i,j\)\(i,j\)andH=ei​ej⊤H=e\_\{i\}e\_\{j\}^\{\\top\}, every pairS=t​HS=tH,X=\(1−t\)​HX=\(1\-t\)HreconstructsA=HA=Hexactly, so without further constraints the components are a decomposition of the fit, not identified parts, and the experiments score the reconstructionS\+U​V⊤S\+UV^\{\\top\}\. For fixed permutations, both inner updates are exact\. Writing

F⁡\(π,σ,S,X\):=‖Pπ​\(A−X\)​PσT−S‖F2F\(\\pi,\\sigma,S,X\):=\\left\\\|P\_\{\\pi\}\(A\-X\)P\_\{\\sigma\}^\{T\}\-S\\right\\\|\_\{F\}^\{2\}withS⊙\(1−M\)=0S\\odot\(1\-M\)=0andrank⁡\(X\)≤k\\rank\(X\)\\leq k:

1. \(i\)the pattern step is the projectionS∗=ΠM​\(Pπ​\(A−X\)​PσT\)S^\{\*\}=\\Pi\_\{M\}\(P\_\{\\pi\}\(A\-X\)P\_\{\\sigma\}^\{T\}\);
2. \(ii\)the low\-rank step is the rank\-kktruncationX∗=SVDk​\(A−PπT​S​Pσ\)X^\{\*\}=\\mathrm\{SVD\}\_\{k\}\(A\-P\_\{\\pi\}^\{T\}SP\_\{\\sigma\}\)by Eckart–Young \(using‖Pπ​\(A−X\)​Pσ⊤−S‖F2=‖\(A−X\)−Pπ⊤​S​Pσ‖F2\\left\\\|P\_\{\\pi\}\(A\-X\)P\_\{\\sigma\}^\{\\top\}\-S\\right\\\|\_\{F\}^\{2\}=\\left\\\|\(A\-X\)\-P\_\{\\pi\}^\{\\top\}SP\_\{\\sigma\}\\right\\\|\_\{F\}^\{2\}\)\.

##### Useful identity\.

For any\(π,σ,X\)\(\\pi,\\sigma,X\)the optimalSSgiven the rest isS∗=ΠM​\(Pπ​\(A−X\)​Pσ⊤\)S^\{\*\}=\\Pi\_\{M\}\(P\_\{\\pi\}\(A\-X\)P\_\{\\sigma\}^\{\\top\}\), and substituting back yields equation \([5](https://arxiv.org/html/2611.17674#S4.E5)\) of Section[4](https://arxiv.org/html/2611.17674#S4), restated here for the proof:

minS:S⊙\(1−M\)=0F\(π,σ,S,X\)=‖\(I−ΠM\)\(Pπ\(A−X\)Pσ⊤\)‖F2=dM\(A−X;π,σ\)\.\\min\_\{S:\\;S\\odot\(1\-M\)=0\}F\(\\pi,\\sigma,S,X\)=\\left\\\|\(I\-\\Pi\_\{M\}\)\(P\_\{\\pi\}\(A\-X\)P\_\{\\sigma\}^\{\\top\}\)\\right\\\|\_\{F\}^\{2\}=d\_\{M\}\(A\-X;\\pi,\\sigma\)\.

##### Proof of Proposition[2](https://arxiv.org/html/2611.17674#Thmproposition2)\.

Index iterations byttand write the state at the start of iterationttas\(πt,σt,St,Xt\)\(\\pi\_\{t\},\\sigma\_\{t\},S\_\{t\},X\_\{t\}\)\. The body of the loop performs three updates\.

1. \(1\)*Pattern step\.*St\+1=ΠM​\(Pπt​\(A−Xt\)​Pσt⊤\)S\_\{t\+1\}=\\Pi\_\{M\}\(P\_\{\\pi\_\{t\}\}\(A\-X\_\{t\}\)P\_\{\\sigma\_\{t\}\}^\{\\top\}\)is the exact minimizer ofFFoverMM\-supportedSS, soF⁡\(πt,σt,St\+1,Xt\)≤F⁡\(πt,σt,St,Xt\)F\(\\pi\_\{t\},\\sigma\_\{t\},S\_\{t\+1\},X\_\{t\}\)\\leq F\(\\pi\_\{t\},\\sigma\_\{t\},S\_\{t\},X\_\{t\}\)\.
2. \(2\)*Low\-rank step\.*Xt\+1=SVDk​\(A−Pπt⊤​St\+1​Pσt\)X\_\{t\+1\}=\\mathrm\{SVD\}\_\{k\}\(A\-P\_\{\\pi\_\{t\}\}^\{\\top\}S\_\{t\+1\}P\_\{\\sigma\_\{t\}\}\)is the global minimizer over rank\-kkXX\(Eckart–Young\), soF⁡\(πt,σt,St\+1,Xt\+1\)≤F⁡\(πt,σt,St\+1,Xt\)F\(\\pi\_\{t\},\\sigma\_\{t\},S\_\{t\+1\},X\_\{t\+1\}\)\\leq F\(\\pi\_\{t\},\\sigma\_\{t\},S\_\{t\+1\},X\_\{t\}\)\.
3. \(3\)*Safeguarded permutation step, followed by re\-synchronization ofSS\.*A candidate\(π~,σ~\)\(\\tilde\{\\pi\},\\tilde\{\\sigma\}\)is produced byAltLAPonA−Xt\+1A\-X\_\{t\+1\}and accepted only ifdM​\(A−Xt\+1,π~,σ~\)<dM​\(A−Xt\+1,πt,σt\)d\_\{M\}\(A\-X\_\{t\+1\};\\tilde\{\\pi\},\\tilde\{\\sigma\}\)<d\_\{M\}\(A\-X\_\{t\+1\};\\pi\_\{t\},\\sigma\_\{t\}\)\. By \([5](https://arxiv.org/html/2611.17674#S4.E5)\) this compares the reduced objectivesminS⁡F⁡\(π~,σ~,S,Xt\+1\)\\min\_\{S\}F\(\\tilde\{\\pi\},\\tilde\{\\sigma\},S,X\_\{t\+1\}\)andminS⁡F⁡\(πt,σt,S,Xt\+1\)\\min\_\{S\}F\(\\pi\_\{t\},\\sigma\_\{t\},S,X\_\{t\+1\}\)\. The algorithm then recomputesSt\+1′=ΠM​\(Pπt\+1​\(A−Xt\+1\)​Pσt\+1⊤\)S\_\{t\+1\}^\{\\prime\}=\\Pi\_\{M\}\(P\_\{\\pi\_\{t\+1\}\}\(A\-X\_\{t\+1\}\)P\_\{\\sigma\_\{t\+1\}\}^\{\\top\}\)for the accepted pair, which is the minimizer in \([5](https://arxiv.org/html/2611.17674#S4.E5)\), so F⁡\(πt\+1,σt\+1,St\+1′,Xt\+1\)\\displaystyle F\(\\pi\_\{t\+1\},\\sigma\_\{t\+1\},S\_\{t\+1\}^\{\\prime\},X\_\{t\+1\}\)=minS⁡F⁡\(πt\+1,σt\+1,S,Xt\+1\)\\displaystyle=\\min\_\{S\}F\(\\pi\_\{t\+1\},\\sigma\_\{t\+1\},S,X\_\{t\+1\}\)≤minS⁡F⁡\(πt,σt,S,Xt\+1\)≤F⁡\(πt,σt,St\+1,Xt\+1\)\.\\displaystyle\\leq\\min\_\{S\}F\(\\pi\_\{t\},\\sigma\_\{t\},S,X\_\{t\+1\}\)\\leq F\(\\pi\_\{t\},\\sigma\_\{t\},S\_\{t\+1\},X\_\{t\+1\}\)\.If the proposal is rejected,\(πt\+1,σt\+1\)=\(πt,σt\)\(\\pi\_\{t\+1\},\\sigma\_\{t\+1\}\)=\(\\pi\_\{t\},\\sigma\_\{t\}\)and the same chain holds with equality\. The recomputation matters: without it the storedSt\+1S\_\{t\+1\}belongs to the old pair andF⁡\(πt\+1,σt\+1,St\+1,Xt\+1\)F\(\\pi\_\{t\+1\},\\sigma\_\{t\+1\},S\_\{t\+1\},X\_\{t\+1\}\)can exceed the previous value even though the reduced objective decreased\.

Combining the three inequalities,F⁡\(πt\+1,σt\+1,St\+1′,Xt\+1\)≤F⁡\(πt,σt,St,Xt\)F\(\\pi\_\{t\+1\},\\sigma\_\{t\+1\},S\_\{t\+1\}^\{\\prime\},X\_\{t\+1\}\)\\leq F\(\\pi\_\{t\},\\sigma\_\{t\},S\_\{t\},X\_\{t\}\), where the left\-hand side is exactly the state the loop carries into the next iteration and returns at termination\. The sequence ofFF\-values is therefore non\-increasing and bounded below by00, hence convergent\.□\\square

Unlike Proposition[1](https://arxiv.org/html/2611.17674#Thmproposition1), this does not give finite termination: the permutations range over the finite set𝒮n×𝒮n\\mathcal\{S\}\_\{n\}\\times\\mathcal\{S\}\_\{n\}, butXXis continuous, and for fixed\(π,σ\)\(\\pi,\\sigma\)the alternatingSS/XXupdates are alternating projections that converge in value without necessarily reaching a fixed point in finitely many steps\. The algorithm stops when the decrease ofFFfalls below a toleranceε\\varepsilonor after a capped number of iterations\.

##### Coordinates ofXX\.

The low\-rank factorXXis kept in the original \(unpermuted\) coordinates across iterations: when\(π,σ\)\(\\pi,\\sigma\)changes,XXdoes not need to be relabeled, whereas a copy stored in the permuted frame would become inconsistent with the new\(π,σ\)\(\\pi,\\sigma\)and break monotonicity\.

### C\.2Identifiability limits of the pattern score

The scores~M​\(A,π,σ\)\\tilde\{s\}\_\{M\}\(A;\\pi,\\sigma\)and its minimised forms~M​\(A\)\\tilde\{s\}\_\{M\}\(A\)are those of equation \([6](https://arxiv.org/html/2611.17674#S4.E6)\)\. LetA=Pπ∗⊤​S0​Pσ∗A=P\_\{\\pi^\{\*\}\}^\{\\top\}S\_\{0\}\\,P\_\{\\sigma^\{\*\}\}withsupp⁡\(S0\)=supp⁡\(M∗\)\\supp\(S\_\{0\}\)=\\supp\(M^\{\*\}\)\. ThendM∗​\(A\)=0d\_\{M^\{\*\}\}\(A\)=0\(the planted pair places every entry ofS0S\_\{0\}insideM∗M^\{\*\}\), sos~M∗​\(A\)=0\\tilde\{s\}\_\{M^\{\*\}\}\(A\)=0\. For a candidateM′M^\{\\prime\},Pπ^​A​Pσ^⊤=Pα​S0​Pβ⊤P\_\{\\hat\{\\pi\}\}AP\_\{\\hat\{\\sigma\}\}^\{\\top\}=P\_\{\\alpha\}S\_\{0\}P\_\{\\beta\}^\{\\top\}withα=π^​\(π∗\)−1\\alpha=\\hat\{\\pi\}\(\\pi^\{\*\}\)^\{\-1\},β=σ^​\(σ∗\)−1\\beta=\\hat\{\\sigma\}\(\\sigma^\{\*\}\)^\{\-1\}, sodM′​\(A,π^,σ^\)=0d\_\{M^\{\\prime\}\}\(A;\\hat\{\\pi\},\\hat\{\\sigma\}\)=0exactly whenPα​M∗​Pβ⊤≤M′P\_\{\\alpha\}M^\{\*\}P\_\{\\beta\}^\{\\top\}\\leq M^\{\\prime\}entrywise\. Hence every mask that contains a row/column\-permuted copy ofM∗M^\{\*\}also scores exactly00, and every mask that does not scores strictly more, for any strictly positive density penaltyg⁡\(ρM\)g\(\\rho\_\{M\}\)in place of\(1−ρM\)3/2\(1\-\\rho\_\{M\}\)^\{3/2\}; a sufficient condition for the latter is\|M′\|1<\|M∗\|1\|M^\{\\prime\}\|\_\{1\}<\|M^\{\*\}\|\_\{1\}\. Among the zero\-score masks the score does not distinguish at all:00divided by any penalty is00, so the planted mask and its containers tie, and preferring the sparsest of them is a separate convention, not a property of the score\. The remark concerns exact support only: a zero residual cannot distinguish a mask from its containers, whatever the density factor\.

Role of the exponent\.Under noise the containers acquire positive scores and the density factor becomes active\. The exponent3/23/2is a heuristic over\-correction of coverage, not a derived constant: under independent uniform row and column permutations𝔼⁡\[dM​\(A,π,σ\)\]=\(1−ρM\)​‖A‖F2\\mathbb\{E\}\[d\_\{M\}\(A;\\pi,\\sigma\)\]=\(1\-\\rho\_\{M\}\)\\\|A\\\|\_\{F\}^\{2\}\(Appendix[B\.2](https://arxiv.org/html/2611.17674#A2.SS2)\), so the normalized null level is\(1−ρM\)−1/2\(1\-\\rho\_\{M\}\)^\{\-1/2\}and denser masks receive a larger null score, whereas the exponent11would equalize the null level across densities\. Whether this is enough once the permutations are optimized is an empirical question, measured in Appendix[E\.5\.1](https://arxiv.org/html/2611.17674#A5.SS5.SSS1)\.

### C\.3Special masks: permutation\-invariant objectives and exact solutions

Table[5](https://arxiv.org/html/2611.17674#A3.T5)summarizes the cases; the derivations follow\.

Table 5:Masks for which the objective is permutation\-invariant or exactly solvable\.Objectives that do not depend on the permutation\.ForM=𝟏M=\\mathbf\{1\},dM​\(A,π,σ\)=0d\_\{M\}\(A;\\pi,\\sigma\)=0for everyAA,π\\pi,σ\\sigma\. Under a common permutation \(σ=π\\sigma=\\pi\) and for anyAA, the diagonal mask givesdM​\(A,π\)=∑i≠jAπ−1​\(i\),π−1​\(j\)2=∑a≠bAa​b2d\_\{M\}\(A;\\pi\)=\\sum\_\{i\\neq j\}A\_\{\\pi^\{\-1\}\(i\),\\pi^\{\-1\}\(j\)\}^\{2\}=\\sum\_\{a\\neq b\}A\_\{ab\}^\{2\}, since the pairs\(π−1​\(i\),π−1​\(j\)\)\(\\pi^\{\-1\}\(i\),\\pi^\{\-1\}\(j\)\)withi≠ji\\neq jrange over all ordered pairsa≠ba\\neq b\. Underσ=π\\sigma=\\piand for*symmetric*AA, the upper\-triangular mask givesdM​\(A,π\)=∑i\>jAπ−1​\(i\),π−1​\(j\)2=12​∑a≠bAa​b2d\_\{M\}\(A;\\pi\)=\\sum\_\{i\>j\}A\_\{\\pi^\{\-1\}\(i\),\\pi^\{\-1\}\(j\)\}^\{2\}=\\tfrac\{1\}\{2\}\\sum\_\{a\\neq b\}A\_\{ab\}^\{2\}, becauseAa​b2=Ab​a2A\_\{ab\}^\{2\}=A\_\{ba\}^\{2\}and the pairsi\>ji\>jcover every unordered pair once; for an asymmetricAAthe same quantity is the weight of the backward arcs of the ordering, the linear\-ordering objective\. With independent permutations the diagonal and triangular masks are no longer trivial: the diagonal and the anti\-diagonal are single LAPs \(Lemma[1](https://arxiv.org/html/2611.17674#Thmlemma1)\), and the triangle is not constant\.

Exact solution for the arrowhead mask underσ=π\\sigma=\\pi\.The diagonal is invariant under a common permutation, so the only choice is which index becomes the hubhh:

maxπ⁡‖ΠM​\(Aπ,π\)‖F2=∑iAi​i2\+max⁡∑j≠hh⁡\(Ah​j2\+Aj​h2\),\\max\_\{\\pi\}\\\|\\Pi\_\{M\}\(A^\{\\pi,\\pi\}\)\\\|\_\{F\}^\{2\}\\;=\\;\\sum\_\{i\}A\_\{ii\}^\{2\}\+\\max\_\{h\}\\sum\_\{j\\neq h\}\\bigl\(A\_\{hj\}^\{2\}\+A\_\{jh\}^\{2\}\\bigr\),computable inO⁡\(n2\)O\(n^\{2\}\)\. The attention pipeline of Appendix[E\.7](https://arxiv.org/html/2611.17674#A5.SS7)uses this value as the arrowhead score and as a check on the solver\.

## Appendix DAlgorithmic Details

### D\.1Initialization and the exchange phase

Initialization\.The default start for every mask is the Fiedler vector of the graph LaplacianL=D−\|A\|L=D\-\|A\|,D=diag⁡\(\|A\|​𝟏\)D=\\diag\(\|A\|\\mathbf\{1\}\): ordering vertices by their spectral embedding aligns with bandwidth\-minimal orderings\[[Barnard et al\., 1995](https://arxiv.org/html/2611.17674#bib.bib6)\]\. For the anti\-diagonal band the Fiedler order of the folded path is unfolded from both ends and the two starts are kept as candidates; experiments that start a block fit from a spectral or Bethe\-Hessian partition say so where they are reported \(Appendix[E\.6\.3](https://arxiv.org/html/2611.17674#A5.SS6.SSS3)\)\. Random restarts mitigate the residual local\-minimum issue\.

Common permutation\.Forσ=π\\sigma=\\pithe two\-sided iterate of a restart is rounded to one permutation,π^∈arg​minπ∈\{π0,π∗,σ∗\}⁡dM​\(A,π\)\\hat\{\\pi\}\\in\\argmin\_\{\\pi\\in\\\{\\pi\_\{0\},\\pi^\{\*\},\\sigma^\{\*\}\\\}\}d\_\{M\}\(A;\\pi\)withπ0\\pi\_\{0\}the start \(rounding alone can lose ground, so the start is kept as a candidate\), and the bestπ^\\hat\{\\pi\}over restarts is finished by the exchange descent\. WithCCthe permuted weight matrix \(C=B⊙BC=B\\odot Bfor the pattern distance,C=BC=Bfor the linear score,B=Pπ^​A​Pπ^⊤B=P\_\{\\hat\{\\pi\}\}AP\_\{\\hat\{\\pi\}\}^\{\\top\}\) andD=1−MD=1\-M, exchanging positionsppandqqchanges the objective∑i​jDi​j​Ci​j\\sum\_\{ij\}D\_\{ij\}C\_\{ij\}by

Δp​q=∑j≠p,q\[\(Dp​j−Dq​j\)​\(Cq​j−Cp​j\)\+\(Dj​p−Dj​q\)​\(Cj​q−Cj​p\)\]\\displaystyle\\Delta\_\{pq\}\\;=\\;\\sum\_\{j\\neq p,q\}\\bigl\[\(D\_\{pj\}\-D\_\{qj\}\)\(C\_\{qj\}\-C\_\{pj\}\)\+\(D\_\{jp\}\-D\_\{jq\}\)\(C\_\{jq\}\-C\_\{jp\}\)\\bigr\]\+\(Dp​q−Dq​p\)​\(Cq​p−Cp​q\)\+\(Dp​p−Dq​q\)​\(Cq​q−Cp​p\),\\displaystyle\+\\;\(D\_\{pq\}\-D\_\{qp\}\)\(C\_\{qp\}\-C\_\{pq\}\)\+\(D\_\{pp\}\-D\_\{qq\}\)\(C\_\{qq\}\-C\_\{pp\}\),valid for asymmetricAAas well; the matrix\(Δp​q\)\(\\Delta\_\{pq\}\)is two productsD​C⊤DC^\{\\top\}andD⊤​CD^\{\\top\}Cplus entrywise terms,O⁡\(n3\)O\(n^\{3\}\)per evaluation\. A round evaluatesΔ\\Delta, then applies the improving exchanges in order of gain on disjoint positions, at mostn/32n/32per round, each re\-checked exactly inO⁡\(n\)O\(n\)under the current order before it is applied; rounds continue while an exchange improves\. The output is never worse than the start and no exchange of two positions improves it \(Proposition[1](https://arxiv.org/html/2611.17674#Thmproposition1)\)\. With several starts the LAP phase runs from each start and the exchange phase from the best rounded permutation; on the sparse graphs of Appendix[E\.6\.3](https://arxiv.org/html/2611.17674#A5.SS6.SSS3), where the LAP steps stall early, the two phases are interleaved per start \(three rounds\)\. The exchange phase costs about11s atn=500n\{=\}500and77s atn=1000n\{=\}1000on one core \(Appendix[E\.8](https://arxiv.org/html/2611.17674#A5.SS8)\)\.

### D\.2Adaptive PatLR: joint pattern–permutation search

Algorithm 3Adaptive PatLR0:

AA, rank

kk, vocabulary

𝒱=\{M1,…,MK\}\\mathcal\{V\}\{=\}\\\{M\_\{1\},\\dots,M\_\{K\}\\\}, budget

NN, cooling

γ\\gamma, exploration floor

pminp\_\{\\min\}, proposal steps

ℓ\\ell; write

f⁡\(j,π,σ\):=s~Mj​\(A,π,σ\)f\(j,\\pi,\\sigma\):=\\tilde\{s\}\_\{M\_\{j\}\}\(A;\\pi,\\sigma\)
1:

π0←FiedlerInit​\(A\)\\pi\_\{0\}\\leftarrow\\textsc\{FiedlerInit\}\(A\); for every

j′j^\{\\prime\}:

\(πj′,σj′\)←AltLAP​\(A,Mj′,ℓ,\(π0,π0\)\)\(\\pi\_\{j^\{\\prime\}\},\\sigma\_\{j^\{\\prime\}\}\)\\leftarrow\\textsc\{AltLAP\}\(A,M\_\{j^\{\\prime\}\},\\ell;\\,\(\\pi\_\{0\},\\pi\_\{0\}\)\)\{screening\}

2:

j←arg​minj′⁡f​\(j′,πj′,σj′\)j\\leftarrow\\argmin\_\{j^\{\\prime\}\}f\(j^\{\\prime\},\\pi\_\{j^\{\\prime\}\},\\sigma\_\{j^\{\\prime\}\}\);

\(π,σ\)←\(πj,σj\)\(\\pi,\\sigma\)\\leftarrow\(\\pi\_\{j\},\\sigma\_\{j\}\);

T←T0\>0T\\leftarrow T\_\{0\}\>0
3:

\(j∗,π∗,σ∗\)←\(j,π,σ\)\(j^\{\*\},\\pi^\{\*\},\\sigma^\{\*\}\)\\leftarrow\(j,\\pi,\\sigma\)\{incumbent: best visited state\}

4:for

t=1,…,Nt=1,\\dots,Ndo

5:

\(π,σ\)←AltLAP​\(A,Mj,1,\(π,σ\)\)\(\\pi,\\sigma\)\\leftarrow\\textsc\{AltLAP\}\(A,M\_\{j\},1;\\,\(\\pi,\\sigma\)\)
6:if

f⁡\(j,π,σ\)<f⁡\(j∗,π∗,σ∗\)f\(j,\\pi,\\sigma\)<f\(j^\{\*\},\\pi^\{\*\},\\sigma^\{\*\}\)then

\(j∗,π∗,σ∗\)←\(j,π,σ\)\(j^\{\*\},\\pi^\{\*\},\\sigma^\{\*\}\)\\leftarrow\(j,\\pi,\\sigma\)\{update incumbent\}

7:with prob\.

p⁡\(T\)=max⁡\(pmin,T/T0\)p\(T\)\{=\}\\max\(p\_\{\\min\},T/T\_\{0\}\):

8:

j′∼Uniform⁡\[K\]j^\{\\prime\}\\sim\\mathrm\{Uniform\}\[K\];

\(π′,σ′\)←AltLAP​\(A,Mj′,ℓ,\(π,σ\)\)\(\\pi^\{\\prime\},\\sigma^\{\\prime\}\)\\leftarrow\\textsc\{AltLAP\}\(A,M\_\{j^\{\\prime\}\},\\ell;\\,\(\\pi,\\sigma\)\)
9:

Δ←f⁡\(j′,π′,σ′\)−f⁡\(j,π,σ\)\\Delta\\leftarrow f\(j^\{\\prime\},\\pi^\{\\prime\},\\sigma^\{\\prime\}\)\-f\(j,\\pi,\\sigma\)
10:if

Δ<0\\Delta<0or

rand\(\)<e−Δ/T\\mathrm\{rand\}\(\)<e^\{\-\\Delta/T\}then

\(j,π,σ\)←\(j′,π′,σ′\)\(j,\\pi,\\sigma\)\\leftarrow\(j^\{\\prime\},\\pi^\{\\prime\},\\sigma^\{\\prime\}\)
11:if

f⁡\(j,π,σ\)<f⁡\(j∗,π∗,σ∗\)f\(j,\\pi,\\sigma\)<f\(j^\{\*\},\\pi^\{\*\},\\sigma^\{\*\}\)then

\(j∗,π∗,σ∗\)←\(j,π,σ\)\(j^\{\*\},\\pi^\{\*\},\\sigma^\{\*\}\)\\leftarrow\(j,\\pi,\\sigma\)\{update incumbent\}

12:

T←γ​TT\\leftarrow\\gamma\\,T
13:endfor

14:return

PatLR​\(A,Mj∗,k\)\\textsc\{PatLR\}\(A,M\_\{j^\{\*\}\},k\)started from

\(π∗,σ∗\)\(\\pi^\{\*\},\\sigma^\{\*\}\)\{Alg\.[2](https://arxiv.org/html/2611.17674#alg2); a freshAltLAPstart on

Mj∗M\_\{j^\{\*\}\}is also tried and the better kept\}

Settings not stated in Section[4\.1](https://arxiv.org/html/2611.17674#S4.SS1): the default vocabulary is blocksk∈\{2,3,4,6\}k\\in\\\{2,3,4,6\\\}, bandsw∈\{1,2,4\}w\\in\\\{1,2,4\\\}, arrowhead and block\+band \(k=3k\{=\}3,w=2w\{=\}2\), nine masks with fixed parameters \(the attention study uses the nine\-mask vocabulary of Section[5\.5](https://arxiv.org/html/2611.17674#S5.SS5)\); the exploration probability isp⁡\(T\)=max⁡\(pmin,T/T0\)p\(T\)=\\max\(p\_\{\\min\},\\,T/T\_\{0\}\)withpmin=0\.15p\_\{\\min\}\{=\}0\.15,T0T\_\{0\}is calibrated from the score spread at the Fiedler initialization \(floored at a small positive constant\),γ=0\.95\\gamma\{=\}0\.95, and a proposal is evaluated withℓ=3\\ell\{=\}3LAP steps from the current pair \(a permutation pair optimized for blockk=6k\{=\}6is already a reasonable start for blockk=4k\{=\}4or block\+band\)\. TheAltLAPcalls inside the search are the LAP phase of Algorithm[1](https://arxiv.org/html/2611.17674#alg1), without the exchange phase: the search compares many masks under a small budget, and finishing every proposal at a local minimum would turn each cheap evaluation into a full fit\. The exchange phase, a fresh three\-restart fit andPatLRare applied to the selected mask only\. The incumbent updates make the output the best visited state; whether the finite search selects the planted mask is the empirical question of Section[5\.4](https://arxiv.org/html/2611.17674#S5.SS4)and Appendix[E\.5\.1](https://arxiv.org/html/2611.17674#A5.SS5.SSS1)\.

##### Out\-of\-vocabulary structure\.

The selector never rejects: it returns the best\-scoring visited state, so a structure outside the vocabulary \(unequal or nested blocks, a hybrid shape\) is approximated by the closest available mask; in our planted experiments the nearest single\-family mask is selected rather than a noise\-level answer\. Two practical remedies follow\. A best score close to the random\-permutation level indicates that no mask in the vocabulary explains the matrix\. That level is not a universal constant: for independent random permutations and no optimization,𝔼\[s~M\]=\(1−ρM\)/\(1−ρM\)3/2=\(1−ρM\)−1/2\\mathbb\{E\}\[\\tilde\{s\}\_\{M\}\]=\(1\-\\rho\_\{M\}\)/\(1\-\\rho\_\{M\}\)^\{3/2\}=\(1\-\\rho\_\{M\}\)^\{\-1/2\}, underσ=π\\sigma=\\piit depends on the split of the mass between the diagonal and the off\-diagonal \(Appendix[B](https://arxiv.org/html/2611.17674#A2)\), and optimizing over permutations lowers it further, so a threshold on it is a heuristic calibrated per mask rather than a derived rejection rule;A=0A=0andρM=1\\rho\_\{M\}=1are excluded by convention\. The vocabulary is extended by adding a mask, at a cost linear in\|𝒱\|\|\\mathcal\{V\}\|\. Estimating mask parameters from the data instead of enumerating fixed masks \(e\.g\. block boundaries by change\-point segmentation of the reordered matrix, alternated with the permutation step\), and calibrating each mask’s score against its own random\-permutation null rather than a density correction, are left for future work\.

## Appendix EExperimental Details and Additional Results

For the experiments summarized in Section[5](https://arxiv.org/html/2611.17674#S5)this appendix gives the generators, the information available to each method, the baseline settings, the full grids and the paired intervals; it also reports the experiments that appear only here \(the compute\-budget ablation, the circular and nested ordering geometries, block\-size estimation, the long\-context control and wall\-clock scaling\), each with the question it answers\. Unless stated otherwise, comparisons are paired on identical instances over2020seeds with95%95\\%bootstrap intervals of the paired difference\.

### E\.1Ablation: Initialization, Restarts, and Compute Budget

Figure[7](https://arxiv.org/html/2611.17674#A5.F7)runs the solvers of Table[1](https://arxiv.org/html/2611.17674#S5.T1)on the same instances with increasing budgets and records the running best error reduction against cumulative wall\-clock: Alternating LAP from the Fiedler order plus random restarts \(the protocol of Table[1](https://arxiv.org/html/2611.17674#S5.T1), five restarts there\) and from random restarts only, up to2020restarts, and FAQ with11to1010starts\. Three things are visible\. The first run accounts for almost all of the gain over the Fiedler order alone; additional restarts add at most0\.040\.04over2020restarts, and random starts reach the values of the Fiedler start on all but one panel \(Gaussw=5w\{=\}5,n=200n\{=\}200, where the Fiedler start stays0\.050\.05ahead\), so on these planted instances the descent, not the spectral start, does the work\. On the sparse\{0,1\}\\\{0,1\\\}graphs the restart budget adds about0\.010\.01: the LAP steps stall on the many ties induced by sparse binary inputs \(the same stalling appears without any noise on thew=1w\{=\}1band, the Hamiltonian\-path case of Appendix[B\.5](https://arxiv.org/html/2611.17674#A2.SS5.SSS0.Px1)\) and the exchange phase supplies the remaining descent \(next paragraph\)\. FAQ with one start is weak there and owes its final value to its randomized starts; on the Gaussian inputs Alternating LAP is above FAQ at every budget\.

Figure 7:Error reduction against cumulative wall\-clock on the instances of Table[1](https://arxiv.org/html/2611.17674#S5.T1)\(2020seeds,95%95\\%bootstrap intervals; single CPU core\)\. Markers: AltLAP after1,2,3,5,10,201,2,3,5,10,20restarts \(Fiedler start plus random, or random only\), FAQ after1,3,5,101,3,5,10starts; the open circle is the Fiedler order without any LAP step\.##### Without the exchange phase\.

Running Algorithm[1](https://arxiv.org/html/2611.17674#alg1)with the exchange phase disabled, on the instances and budget of Table[1](https://arxiv.org/html/2611.17674#S5.T1), separates the two phases\. The LAP phase alone reaches ER0\.61/0\.50/0\.410\.61/0\.50/0\.41\(Gaussw=2w\{=\}2\),0\.78/0\.65/0\.550\.78/0\.65/0\.55\(Gaussw=5w\{=\}5\),0\.15/0\.06/0\.010\.15/0\.06/0\.01\(sparsew=2w\{=\}2\) and0\.63/0\.48/0\.290\.63/0\.48/0\.29\(sparsew=5w\{=\}5\) atn=100/200/500n\{=\}100/200/500; the exchange phase raises these to0\.69/0\.61/0\.520\.69/0\.61/0\.52,0\.87/0\.75/0\.610\.87/0\.75/0\.61,0\.45/0\.30/0\.150\.45/0\.30/0\.15and0\.69/0\.53/0\.340\.69/0\.53/0\.34, the values of Table[1](https://arxiv.org/html/2611.17674#S5.T1)\. On the Gaussian inputs it adds0\.060\.06–0\.110\.11and on the sparse graphs it supplies most of the reduction, since the LAP steps stall on the ties induced by binary inputs, the same stalling as on the sparse SBM graphs of Section[5\.2](https://arxiv.org/html/2611.17674#S5.SS2)\. Atn=500n\{=\}500the phase takes about a third of the run time on the Gaussian instances and about a tenth on the sparse graphs \(runtimes in Appendix[E\.2](https://arxiv.org/html/2611.17674#A5.SS2)\)\.

### E\.2Banded Baselines from the Seriation, QAP, and Bandwidth Literatures

Table[6](https://arxiv.org/html/2611.17674#A5.T6)extends Table[1](https://arxiv.org/html/2611.17674#S5.T1)with all methods and both of our metrics \(ER / BE\), and Table[7](https://arxiv.org/html/2611.17674#A5.T7)scores the same orderings by the bandwidth family’s own criteria\. Methods: RCM\[[Cuthill and McKee, 1969](https://arxiv.org/html/2611.17674#bib.bib16)\]and Gibbs–Poole–Stockmeyer \(GPS\)\[[Gibbs et al\., 1976](https://arxiv.org/html/2611.17674#bib.bib25)\]on the\{0,1\}\\\{0,1\\\}support \(the graph itself in the sparse regime; the KNN\-2020sparsification in the Gaussian regime\); F\+greedy \(Fiedler order plus greedy adjacent swaps on 2\-SUM\); the plain spectral 2\-SUM order of[Atkins et al\. \[1998\]](https://arxiv.org/html/2611.17674#bib.bib4)\(the Fiedler ordering itself\); convex seriation\[[Fogel et al\., 2013](https://arxiv.org/html/2611.17674#bib.bib21)\]\(Frank–Wolfe over the permutahedron with the concave vertex\-pulling term, penalty weight and start chosen by the 2\-SUM value\); QAP\-FAQ with three starts; FAQ followed by AltLAP \(keeping the better of the two\); AltLAP with one restart \(equal\-budget variant\) and with five\. Our objective and FAQ’s are the same QAP, but the two heuristics solve different inner problems: FAQ relaxes the single\-permutation problem, whereas AltLAP descends on the two\-sided objective, rounds to one permutation and finishes with the exchange descent; the rounding can lose ground, which is why the start is kept as a candidate\. The two are closely related: at a permutationPπP\_\{\\pi\}the FAQ gradient∇Ptr​\(M⊤​P​W​P⊤\)=2​M​Pπ​W\\nabla\_\{P\}\\,\\mathrm\{tr\}\(M^\{\\top\}PWP^\{\\top\}\)=2MP\_\{\\pi\}Wequals−2​Q\-2Qof Lemma[1](https://arxiv.org/html/2611.17674#Thmlemma1)up to a constant per column, so the first FAQ direction\-finding step from a permutation is the LAP step of Algorithm[1](https://arxiv.org/html/2611.17674#alg1); FAQ then takes a fractional step inside the Birkhoff polytope, while AltLAP moves to the vertex and alternates sides\. Warm\-starting AltLAP from the FAQ order \(the FAQ\+AltLAP column of Table[6](https://arxiv.org/html/2611.17674#A5.T6)\) adds0\.020\.02–0\.120\.12on the Gaussian inputs, where the LAP steps rarely move the FAQ order and the gain is the exchange phase, and at most0\.010\.01on the sparse graphs\.

Table 6:Banded recovery, ER / BE \(higher = better\),2020seeds\. Bold marks the best ER per row \(ties within0\.0050\.005\)\.Two metric families, one support\.Bandwidthmax⁡\{\|i−j\|:Si​j=1\}\\max\\\{\|i\-j\|:S\_\{ij\}=1\\\}and profile∑i\(i−min⁡\{j≤i:Si​j=1\}\)\\sum\_\{i\}\(i\-\\min\\\{j\\leq i:S\_\{ij\}=1\\\}\)need a discrete support, so every ordering is scored on the same\{0,1\}\\\{0,1\\\}support that RCM and GPS are given\. GPS is the better bandwidth reducer, as expected, and neither bandwidth method reduces off\-band mass\. Conversely our methods barely reduce bandwidth: a few small entries far from the diagonal cost almost no mass but fixmax⁡\|i−j\|\\max\|i\-j\|\. On noisy inputs the classical criterion saturates \(atn=500n\{=\}500in the Gaussian regime every ordering, including the identity, has a bandwidth close to the maximum\), because the signal falls below the noise at\|i−j\|≈7\|i\-j\|\\approx 7and the support beyond is noise, so the criterion is set by the farthest noise entries while the pattern distance measures the mass concentration\.

Table 7:The same orderings scored by the bandwidth family: bandwidth \(lower = better; identity order and six methods\) and profile for RCM, GPS and AltLAP, means over2020seeds on the shared\{0,1\}\\\{0,1\\\}support\.Runtimes atn=500n\{=\}500\(one EPYC core\): RCM, GPS and the spectral order0\.010\.01–0\.020\.02s; convex seriation0\.450\.45–0\.550\.55s; F\+greedy0\.70\.7s; FAQ \(three starts\)2\.02\.0–2\.82\.8s; AltLAP with one restart0\.80\.8–1\.21\.2s and with five1\.71\.7–4\.14\.1s \(the exchange phase runs once, from the best restart\)\.

### E\.3PatLR Decomposition Visualizations

Figure[8](https://arxiv.org/html/2611.17674#A5.F8)follows the decomposition on one synthetic instance of the experiment of Figure[4](https://arxiv.org/html/2611.17674#S5.F4), where the planted parts are known and can be compared with the recovered ones, and, without added noise, on the two real networks of Section[5\.3](https://arxiv.org/html/2611.17674#S5.SS3)and on three feature\-correlation matrices from the UCI repository\[[Aeberhard and Forina, 1992](https://arxiv.org/html/2611.17674#bib.bib2),[Wolberg et al\., 1993](https://arxiv.org/html/2611.17674#bib.bib58),[Alpaydin and Kaynak, 1998](https://arxiv.org/html/2611.17674#bib.bib3), Wine, Breast Cancer Wisconsin \(Diagnostic\) and Optical Recognition of Handwritten Digits;\], each with the mask of the default vocabulary that fits it best at rank11\. The first column shows each matrix in its native order \(node numbering of the graph, feature order of the dataset\), the second the random order given to the solver\. The row norm of the low\-rank part follows the row mass on Les Misérables, Wine and Breast Cancer; on the karate club the rank\-11part concentrates on the two highest\-degree nodes, the two faction leaders\.

![Refer to caption](https://arxiv.org/html/2611.17674v1/fig_patlr_real.png)Figure 8:PatLR step by step\. Top row: a synthetic instance with known truth \(bandedw=3w\{=\}3pattern plus a rank\-33component of equal energy,n=100n\{=\}100, scrambled, SNR11\): the plantedS0S\_\{0\}andL0L\_\{0\}, the noisy input, the input in the found order, the recoveredSSandU​V⊤UV^\{\\top\}and their sum with its DQ\. Remaining rows: real matrices without added noise, karate club \(weighted adjacency,block⁡\(18,16\)\\mathrm\{block\}\(18,16\)from the two factions, rank11\); Les Misérables \(co\-occurrence weights scaled to\[0,1\]\[0,1\],block⁡\(19,19,19,20\)\\mathrm\{block\}\(19,19,19,20\)template, rank33\); and the signed feature\-correlation matrices of Wine \(bandw=4w\{=\}4\), Breast Cancer \(block⁡\(15,15\)\\mathrm\{block\}\(15,15\)\) and Digits \(pixel correlations,block⁡\(32,32\)\\mathrm\{block\}\(32,32\)\), rank11; left to right: the input in its native order; the input in the random order given to the solver; the input in the order found by PatLR, mask outlined; the pattern partSS; the low\-rank partU​V⊤UV^\{\\top\}; their sum with its explained variance; the row norm ofU​V⊤UV^\{\\top\}against the row mass∑j\|Ai​j\|\\sum\_\{j\}\|A\_\{ij\}\|\(weighted degree for the graphs, total absolute correlation for the features\)\. Graphs on a white\-to\-blue scale, signed matrices andU​V⊤UV^\{\\top\}on a diverging scale \(blue positive\);rris the correlation in the last column\.
### E\.4PatLR: Full Denoising Grid, Ablations and Capacity Control

##### Setup of Figure[4](https://arxiv.org/html/2611.17674#S5.F4), remaining details\.

The pattern part isS0=2​M⊙R\+0\.15​\(1−M\)⊙RS\_\{0\}=2\\,M\\odot R\+0\.15\\,\(1\-M\)\\odot Rfor one symmetric Gaussian matrixRR, with the diagonal set to\|Ri​i\|\+0\.3\|R\_\{ii\}\|\+0\.3\(the generator of the capacity control below\);S0S\_\{0\}is symmetric for the six symmetric masks, while for the upper\-triangular mask it is asymmetric \(upper triangle at scale22, lower at0\.150\.15\), so under the common permutation its objective is the linear\-ordering problem of Table[2](https://arxiv.org/html/2611.17674#A1.T2), not the constant it would be for a symmetric matrix\. The low\-rank part isL0=U​U⊤L\_\{0\}=UU^\{\\top\}withU∈ℝn×3U\\in\\mathbb\{R\}^\{n\\times 3\}Gaussian, scaled to a fractionffof the clean energy \(f=0\.5f\{=\}0\.5in Figure[4](https://arxiv.org/html/2611.17674#S5.F4)\); the noise is scaled per instance toSNR=‖A‖F2/‖E‖F2\\mathrm\{SNR\}=\\\|A\\\|\_\{F\}^\{2\}/\\\|E\\\|\_\{F\}^\{2\}, so the noisy input has DQ1−1/SNR1\-1/\\mathrm\{SNR\}\. RPCA is principal component pursuit with its low\-rank part as the estimate; SVD\-dof is the SVD at the rank with the parameter count of PatLR \(rule below\); PatLR runs from the Fiedler order and from its unfolding \(one random restart each\) and keeps the lower objective; PatLR\-rnd uses a random mask of the same density; the oracle column fixes the permutation to the planted one and alternatesSSandXXonly\.

Table[8](https://arxiv.org/html/2611.17674#A5.T8)gives the full grid\. Three regularities hold across it\. An estimate that copies the in\-mask entries, i\.e\.C^=M⊙\(C\+E\)\+\(1−M\)⊙X\\hat\{C\}=M\\odot\(C\+E\)\+\(1\-M\)\\odot Xin the coordinates of the mask \(pattern alone withX=0X=0, PatLR and the oracle with the rank\-33XX\), has error‖M⊙E‖F2\+‖\(1−M\)⊙\(X−C\)‖F2\\\|M\\odot E\\\|\_\{F\}^\{2\}\+\\\|\(1\-M\)\\odot\(X\-C\)\\\|\_\{F\}^\{2\}exactly, the two terms having disjoint supports, so its DQ is at most1−‖M⊙E‖F2/‖C‖F21\-\\\|M\\odot E\\\|\_\{F\}^\{2\}/\\\|C\\\|\_\{F\}^\{2\}\. For a mask placed independently of the noise the in\-mask noise energy isρM​‖E‖F2\\rho\_\{M\}\\\|E\\\|\_\{F\}^\{2\}in expectation, which gives the value1−ρM/SNR1\-\\rho\_\{M\}/\\mathrm\{SNR\}; a permutation chosen from the data tends to place more noise inside the mask, not less\. The off\-mask term is the clean energy outside the mask for the pattern\-only estimate \(X=0X=0\) and‖\(1−M\)⊙\(X−C\)‖F2\\\|\(1\-M\)\\odot\(X\-C\)\\\|\_\{F\}^\{2\}for PatLR, which is smaller whenCChas low\-rank structure outside the mask and larger whenXXfits noise\. On the pattern\-only families the off\-mask clean values are i\.i\.d\. and carry no low\-rank structure, so on the five families whose order the solver recovers the rank\-33oracle lands below the pattern\-only value by0\.010\.01at SNR44,0\.050\.05at SNR11and0\.070\.07–0\.110\.11at SNR0\.50\.5\(on the band and the anti\-diagonal the oracle’s planted order puts it above the pattern\-only estimate, whose order is the solver’s\)\. The gap between PatLR and the oracle is concentrated on the banded and anti\-diagonal families, i\.e\. in the permutation search on sparse masks, and grows as the SNR falls\. The random\-mask control PatLR\-rnd lies0\.20\.2–0\.50\.5below PatLR on the planted pattern and0\.10\.1–0\.40\.4below it with the rank\-3 component at SNR11; it stays above the SVD level where random positions can absorb signal mass under a free permutation \(the band, anti\-diagonal, block and block\+band families on the planted pattern, the band and anti\-diagonal with the rank\-3 component\) and within0\.050\.05of it or below elsewhere\. With80%80\\%of the clean energy in the low\-rank part, SVD\-best is the better estimate on the dense masks, and with20%20\\%PatLR is the best estimate on every family: the mask pays for the in\-mask noise it copies only while the pattern carries enough of the signal\.

Table 8:Denoising quality on the seven families, all settings of the experiment of Figure[4](https://arxiv.org/html/2611.17674#S5.F4)\(n=200n\{=\}200;2020seeds unless stated; best of SVD\-dof, SVD\-best, RPCA, pattern only, PatLR and PatLR\-rnd per row in bold; “oracle” is PatLR at the planted permutation\)\.
##### Ablation of the permutation\.

Table[9](https://arxiv.org/html/2611.17674#A5.T9)fixes the permutation instead of searching it, on the planted\-pattern matrices atσ=0\.3\\sigma\{=\}0\.3\(scrambled\)\. With the permutation fixed to the input order the effect differs between families: block, checkerboard, block\+band, anti\-diagonal and triangular fall below the SVD level, whereas the masks that contain the diagonal keep what a symmetric scrambling leaves in place; the band stays above SVD on the diagonal entries alone, and the arrowhead reaches the searched value because its hub row and column form a rank\-22matrix that the low\-rank term absorbs at any order\. With the permutation fixed to the planted order PatLR is high on every family\. The joint solver attains the planted\-order value on five families and stays below it on banded and anti\-diagonal, the two sparse masks whose order is hardest to recover\.

Table 9:PatLR with the permutation searched, fixed to the input order, or fixed to the planted order \(DQ,n=200n\{=\}200,σ=0\.3\\sigma\{=\}0\.3, scrambled inputs,2020seeds\)\.
##### Capacity control at a matched parameter count\.

Table[10](https://arxiv.org/html/2611.17674#A5.T10)compares the models at an equal nominal parameter count on the planted\-pattern matrices atσ=0\.3\\sigma\{=\}0\.3in their planted order \(the scrambled version changes no entry by more than0\.010\.01\)\. PatLR with maskMMand residual rankrrhasdf=\|M\|\+r⁡\(2​n−r\)\\mathrm\{df\}=\|M\|\+r\(2n\-r\)free parameters \(the in\-mask entries plus a rank\-rrfactorization\)\. SVD\-dof receives the rankr′=round⁡\(n−max⁡\(n2−df,0\)\)r^\{\\prime\}=\\mathrm\{round\}\\bigl\(n\-\\sqrt\{\\max\(n^\{2\}\-\\mathrm\{df\},0\)\}\\bigr\)clipped to\[1,n\]\[1,n\], which has the same count; SVD\-33is the fixed\-rank estimate\. The blockmodel baseline is spectral co\-clustering\[[Dhillon, 2001](https://arxiv.org/html/2611.17674#bib.bib20)\]:kk\-means on the leading singular vectors of rows and of columns, then block means\. “BM” choosesk∈\{2,3,4,5,6,8\}k\\in\\\{2,3,4,5,6,8\\\}by the best DQ \(an oracle choice, generous to the baseline\); “BM\-dof” usesk=round⁡\(df\)k=\\mathrm\{round\}\(\\sqrt\{\\mathrm\{df\}\}\), the same nominal budget as PatLR\. PatLR\-rnd replaces the planted mask by a random mask of the same density, redrawn per seed, with an otherwise identical pipeline\. Atσ=0\.3\\sigma\{=\}0\.3the noise carries up to half of the energy of these matrices \(column “input”\), so the table measures which model class retains a full\-rank in\-mask structure at a given parameter count rather than noise removal; the i\.i\.d\. in\-mask values are a model mismatch for the blockmodel, which is why it sits at the SVD\-dof level at matched budget\. The hierarchical pattern of Table[2](https://arxiv.org/html/2611.17674#A1.T2)is omitted: as a binary mask a two\-level hierarchy coincides with its coarsest level\.

Table 10:Capacity control, DQ atn=200n\{=\}200,σ=0\.3\\sigma\{=\}0\.3,2020seeds:ρM\\rho\_\{M\}is the mask density,r′r^\{\\prime\}the matched SVD rank,k′k^\{\\prime\}the matched number of co\-clusters, “input” the DQ of the noisy matrix itself\.

### E\.5Adaptive PatLR: Additional Analysis

#### E\.5\.1Selection, Identification and Cost on Planted Matrices

##### Setup\.

Each of the nine masks of the default vocabulary is planted atn=200n\{=\}200with the generator of Figure[4](https://arxiv.org/html/2611.17674#S5.F4)\(i\.i\.d\. Gaussian values of scale22on the mask and0\.150\.15off it\), either alone \(*pattern only*\) or plus a rank\-3 PSD component of equal energy \(*pattern \+ rank\-3*\); the matrix is scrambled by a random permutation and symmetric Gaussian noise is added at SNR44and SNR11\(1010and2020seeds;540540instances\)\. The selector’s vocabulary has1212masks: the nine planted families and three gallery masks \(parity checkerboard, anti\-diagonal band of width1010, upper triangular\)\. The parity checkerboard is a row/column\-permuted copy of the two\-block mask \(reorder even and odd indices\), so the density\-normalized score cannot and should not separate the two; it is counted with blockk=2k\{=\}2throughout\. Methods: Oracle PatLR \(rank33, planted mask;1212iterations,33restarts\); Adaptive PatLR \(Algorithm[3](https://arxiv.org/html/2611.17674#alg3),N=80N\{=\}80,ℓ=3\\ell\{=\}3, rank33\); brute force \(every mask fitted by the LAP phase of Alternating LAP,1515iterations from33restarts, i\.e\. the search’s LAP\-only evaluation at a full budget per mask; the mask with the lowest density\-normalized score kept, then PatLR with it\); SVD at the rank with the highest DQ\. DQ is measured against the clean matrix in its planted order\. Times are single\-core seconds on an Apple M3 \(six instances at SNR11\)\.

##### Results \(Table[11](https://arxiv.org/html/2611.17674#A5.T11), Figure[5](https://arxiv.org/html/2611.17674#S5.F5)\)\.

Across the540540instances the ratioDQadapt/DQoracle\\mathrm\{DQ\}\_\{\\text\{adapt\}\}/\\mathrm\{DQ\}\_\{\\text\{oracle\}\}has median1\.001\.00,55th percentile0\.920\.92and minimum0\.760\.76\(a bandw=4w\{=\}4instance at SNR11, planted alone, for which block\+band was selected\); it exceeds11in a third of the instances\. SVD at its best rank averages DQ0\.290\.29against the oracle’s0\.680\.68at SNR11and0\.750\.75\(the noisy input itself\) against0\.870\.87at SNR44\. Brute force has median ratio1\.001\.00and minimum0\.740\.74; its DQ is within0\.010\.01of the search’s in every \(family, generator, SNR\) cell, and its selection frequencies agree with the search’s within10%10\\%in2929of the3636cells, the larger differences being between masks of equal DQ \(blockk=3k\{=\}3against block\+band; on blockk=2k\{=\}2with the rank\-3 component at SNR11, blockk=6k\{=\}6against bandw=4w\{=\}4\)\. It takes3\.73\.7s against2\.92\.9s for the search and2\.52\.5s for the oracle; its cost grows with\|𝒱\|\|\\mathcal\{V\}\|, whereas after the initial vocabulary screening the search uses a fixed budget ofNNiterations rather than fully fitting every mask\. Fitting every mask with the full solver \(exchange phase included\) before comparing scores is not better: the wide band then attains the lowest normalized score more often, and on blockk=3k\{=\}3, arrowhead and block\+band with the rank\-3 component at SNR11the selected mask has a lower DQ \(0\.530\.53,0\.790\.79,0\.530\.53against0\.610\.61,0\.850\.85,0\.620\.62\), the exact minimizer of the heuristic score not being the best\-reconstructing mask \(Appendix[C\.2](https://arxiv.org/html/2611.17674#A3.SS2)\)\. On six real matrices \(the feature correlations of Iris, Wine, Breast Cancer and Digits, the karate club and Les Misérables\), where no planted mask exists, the adaptively selected mask matches the best fixed mask of the vocabulary in explained variance within0\.0250\.025in2424of2929\(matrix, rank\) cells, the exceptions being a sparser choice at rank≤3\\leq 3on Digits and rank≤2\\leq 2on Les Misérables\. Identification \(Figure[5](https://arxiv.org/html/2611.17674#S5.F5)a,b and the last columns of Table[11](https://arxiv.org/html/2611.17674#A5.T11)\) splits by the geometry of the vocabulary\. Arrowhead, block\+band and the block templatesk=4k\{=\}4andk=6k\{=\}6are identified in nearly every instance, although blockk=4k\{=\}4fits inside blockk=2k\{=\}2and blockk=6k\{=\}6inside blockk=3k\{=\}3: under noise the denser container’s smaller residual does not pay back its density penalty\. The few misses go to a neighbouring block size and all occur at SNR11\. Blockk=2k\{=\}2is identified whenever the pattern is planted alone and at SNR44with the rank\-3 component; at SNR11with the rank\-3 component the selector prefers a sparser mask \(blockk=6k\{=\}6or bandw=4w\{=\}4\) at the oracle’s DQ, the low\-rank term absorbing the two dense blocks so that the density penalty of the half\-dense mask is no longer paid back\. The nested families go to a larger mask in most instances \(narrow bands to the wide band; blockk=3k\{=\}3to block\+band, whose blocks cover those of blockk=3k\{=\}3up to two rows\), within0\.040\.04of the oracle’s DQ\. The remaining non\-exact choices are the thin bands without a low\-rank part: their order is recovered only partially at this budget, the planted mask then copies a misaligned band, and the selector prefers wider masks \(blockk=6k\{=\}6, block\+band\), which tolerate the misalignment; at SNR44they reach a higher DQ than the planted mask and at SNR11a DQ0\.020\.02–0\.070\.07below it\. With the rank\-3 component the wide band is identified in most instances\.

Table 11:Adaptive pattern selection on planted matrices \(n=200n\{=\}200\)\. DQ of Oracle PatLR \(planted mask\), Adaptive PatLR and SVD at its best rank, and the share of instances \(%\) in which Adaptive PatLR selects the planted mask \(second number where present: a mask containing the planted one, a wider band for the bands and blockk=3k\{=\}3for blockk=6k\{=\}6, or block\+band for blockk=3k\{=\}3, whose blocks it covers up to two rows\)\. At SNR44the noisy input itself hasDQ=1−1/SNR=0\.75\\mathrm\{DQ\}=1\-1/\\mathrm\{SNR\}=0\.75\.1010seeds at SNR44,2020at SNR11\.SNR 4SNR 1planted maskOracleAdaptiveSVDexact / cont\.OracleAdaptiveSVDexact / cont\.*pattern only*blockk=2k\{=\}20\.860\.860\.751000\.440\.460\.01100blockk=3k\{=\}30\.890\.890\.7540 / 600\.600\.600\.0145 / 55blockk=4k\{=\}40\.910\.910\.751000\.680\.680\.02100blockk=6k\{=\}60\.920\.920\.751000\.750\.740\.0395 / 5bandw=1w\{=\}10\.770\.780\.750 / 400\.690\.670\.125 / 95bandw=2w\{=\}20\.770\.790\.750 / 600\.670\.630\.0910 / 55bandw=4w\{=\}40\.760\.790\.7500\.630\.560\.0510arrowhead0\.780\.780\.751000\.730\.720\.28100block\+band0\.890\.890\.751000\.600\.600\.01100*pattern \+ rank\-3 component*blockk=2k\{=\}20\.860\.800\.751000\.460\.470\.490blockk=3k\{=\}30\.900\.900\.7510 / 900\.630\.610\.490 / 70blockk=4k\{=\}40\.920\.920\.751000\.710\.700\.4990blockk=6k\{=\}60\.940\.940\.751000\.790\.790\.50100bandw=1w\{=\}10\.880\.880\.750 / 1000\.810\.770\.5110 / 90bandw=2w\{=\}20\.870\.880\.7510 / 900\.790\.780\.5140 / 55bandw=4w\{=\}40\.860\.850\.75600\.750\.740\.5090arrowhead0\.890\.890\.761000\.850\.850\.63100block\+band0\.900\.900\.751000\.630\.620\.4970

#### E\.5\.2Sensitivity to the Residual Rank

Figure[9](https://arxiv.org/html/2611.17674#A5.F9)shows DQ against the residual rankrron the setup of Figure[4](https://arxiv.org/html/2611.17674#S5.F4)\(n=200n\{=\}200, the planted pattern alone and with a rank\-3 component of equal energy, SNR44and11,2020seeds\) for PatLR with the planted mask, SVD at the same rank and Adaptive PatLR\. With a rank\-3 component in the data, DQ peaks at the true rank for PatLR and declines slowly beyond it, while SVD needs a higher rank to reach a lower plateau\. With the pattern alone every unit of rank costs DQ at SNR11\(the low\-rank term fits noise\) and little at SNR44\. Adaptive PatLR follows PatLR within0\.050\.05at every rank; the largest differences are on the band planted alone, where it selects a wider mask \(Appendix[E\.5\.1](https://arxiv.org/html/2611.17674#A5.SS5.SSS1)\) and lies0\.040\.04above PatLR at SNR44and0\.040\.04–0\.050\.05below it at SNR11\. The rank is a budget to be chosen, not a free improvement\.

Figure 9:Denoising quality against the residual rankrron the setup of Figure[4](https://arxiv.org/html/2611.17674#S5.F4)\(2020seeds,95%95\\%intervals shaded\): PatLR with the planted mask and SVD at the same rank, for the planted pattern alone \(solid\) and with a rank\-3 component \(dashed\); markers are Adaptive PatLR\. The vertical line marks the planted rank33\.

### E\.6Ordering and Block\-Structure Benchmarks: Full Results

This appendix gives the full grids behind Figure[3](https://arxiv.org/html/2611.17674#S5.F3)and Sections[5\.1](https://arxiv.org/html/2611.17674#S5.SS1)–[5\.2](https://arxiv.org/html/2611.17674#S5.SS2), and two ordering geometries reported only here, circular seriation and nestedness \(Appendix[E\.6\.2](https://arxiv.org/html/2611.17674#A5.SS6.SSS2)\)\. Counting the cells of each grid by the sign of the paired difference to the named reference \(positive / interval containing zero / negative\): latent ordering18/2/418/2/4against spectral and9/10/59/10/5against convex seriation \(2424cells\); consecutive ones4/0/04/0/0; circular seriation2/2/02/2/0; sparse SBM8/1/38/1/3against the Bethe Hessian \(1212cells, the negative ones atλ=1\.3\\lambda\{=\}1\.3\); weighted partition4/1/04/1/0against spectral clustering; band\-in\-block16/0/016/0/0for the refining pass against the pipeline\. In the tables, “seeds\+\+/−\-” counts the seeds on which the paired difference is positive / negative\.

#### E\.6\.1Latent\-order recovery

Setup\.Bi​j=exp\(−\(i−j\)2/2ℓ2\)B\_\{ij\}=\\exp\(\-\(i\-j\)^\{2\}/2\\ell^\{2\}\)is a Robinson matrix with correlation lengthℓ\\ell; it is scrambled by a uniformly random permutationppand symmetric Gaussian noise of standard deviationσ\\sigmais added\. The target is the banded mask of widthw=ℓw=\\ell\. The metric is\|τ\|\|\\tau\|, the absolute Kendall correlation between the recovered and the planted latent positions \(absolute because reversing an order preserves banded structure\)\. Baselines: spectral seriation \(Fiedler order of the Laplacian of\|A\|\|A\|\[[Atkins et al\., 1998](https://arxiv.org/html/2611.17674#bib.bib4)\]\); convex seriation\[[Fogel et al\., 2013](https://arxiv.org/html/2611.17674#bib.bib21)\], implemented as Frank–Wolfe on the 2\-SUM objective over the permutahedron with the concave vertex\-pulling term−μ​var​\(y\)\-\\mu\\,\\mathrm\{var\}\(y\), the penalty weightμ∈\{0\.1,0\.3,0\.5,1,2\}\\mu\\in\\\{0\.1,0\.3,0\.5,1,2\\\}and the start \(spectral or two random\) selected by the 2\-SUM value itself, never byτ\\tau\(on noiseless inputs it recovers the planted order exactly\); QAP\-FAQ with three starts; and a single run of Alternating LAP initialized from the spectral order \(AltLAP\-r1; five restarts change no conclusion\)\. Grid:ℓ∈\{6,12,25\}\\ell\\in\\\{6,12,25\\\},n∈\{100,300\}n\\in\\\{100,300\\\},σ∈\{0\.05,0\.1,0\.2,0\.3\}\\sigma\\in\\\{0\.05,0\.1,0\.2,0\.3\\\}\.

Results\.Table[12](https://arxiv.org/html/2611.17674#A5.T12)lists the2424cells behind the counts of Section[5\.1](https://arxiv.org/html/2611.17674#S5.SS1)\. The four negative cells areℓ=w=25\\ell=w=25atn=100n=100, where the band covers44\.5%44\.5\\%of the matrix; the two ties areℓ=6\\ell=6,n=300n=300atσ≥0\.2\\sigma\\geq 0\.2, where the correlation length is short relative tonn, the global order is weakly identified and all methods are poor \(τ\\taubetween0\.250\.25and0\.340\.34\)\. Runtimes atn=300n=300\(one EPYC core\): spectral0\.0020\.002s, convex≈0\.25\\approx 0\.25s, FAQ0\.60\.6–1\.11\.1s, AltLAP\-r10\.10\.1–0\.20\.2s, of which the exchange phase is the larger part\.

Table 12:Latent\-order recovery, all2424cells:\|τ\|\|\\tau\|against the planted order \(mean over2020seeds; best of spectral, convex and ours in bold\) and paired differences of AltLAP\-r1 against spectral and convex seriation\. FAQ optimizes the same pattern objective from its default starts\.##### Mask width\.

The band width given to the solver is the correlation length of the generator\. Table[13](https://arxiv.org/html/2611.17674#A5.T13)repeats AltLAP\-r1 with the width halved and doubled: a factor\-two error in either direction changesτ\\tauby less than0\.010\.01in most cells and by up to0\.060\.06\(doubled width atℓ=12\\ell\{=\}12,n=100n\{=\}100,σ=0\.3\\sigma\{=\}0\.3\), where the lead over convex seriation is lost; a four\-fold overestimate \(w=25w\{=\}25atℓ=6\\ell\{=\}6,n=100n\{=\}100\) falls below the spectral order\. Choosing the width by the density\-normalized score of Section[4\.1](https://arxiv.org/html/2611.17674#S4.SS1)is not an option on these smooth kernels: the score never selects a width below the correlation length and picks a wider candidate whenever one is available, sowwis a user input here\.

Table 13:Latent\-order recovery with the band width halved and doubled \(\|τ\|\|\\tau\|, mean over2020seeds; the paper’s widthw=ℓw\{=\}\\ellin bold\)\. Atn=100n\{=\}100the doubled width5050is omitted\.

#### E\.6\.2Consecutive ones, circular seriation, and nestedness

Consecutive ones \(fixed\-width staircase recovery\)\.The consecutive\-ones property \(Section[5\.1](https://arxiv.org/html/2611.17674#S5.SS1)\) is decided in linear time by PQ\-trees\[[Booth and Lueker, 1976](https://arxiv.org/html/2611.17674#bib.bib9)\], but recognition is brittle \(one corrupted entry can destroy the property\), so the applied literature, from physical mapping to archaeological seriation\[[Kendall, 1971](https://arxiv.org/html/2611.17674#bib.bib31)\], orders the matrix with heuristics: barycentre reordering, spectral\[[Atkins et al\., 1998](https://arxiv.org/html/2611.17674#bib.bib4)\]and convex\[[Fogel et al\., 2013](https://arxiv.org/html/2611.17674#bib.bib21)\]seriation\. Our target is the staircase bandMi​j=𝟏\[si≤j<si\+w\]M\_\{ij\}=\\mathbf\{1\}\[s\_\{i\}\\leq j<s\_\{i\}\+w\]with non\-decreasing startssis\_\{i\}, fitted with independent row and column permutations; for a matrix whose rows all carrywwones,AAhas the C1P iffdM​\(A\)=0d\_\{M\}\(A\)=0for some mask of this family \(ordering rows by the start of their interval makes the starts non\-decreasing\)\. General C1P with varying interval lengths is a larger class and would require a search over the start and length profiles; what we test is the noisy recovery of the fixed\-width model, with the evenly spaced profilesis\_\{i\}and its sensitivity below\. Instances: planted60×6060\\times 60staircases withw=12w=12and independent flip noise at rateff,2020seeds\. Our solver runs from random restarts only and keeps the candidate with the best mask fit, which uses no labels\. Metrics:\|τ\|\|\\tau\|of the recovered row and column orders against the planted ones, and*edits*, the minimum number of entries that must be changed to make every row contiguous under the returned ordering\.

Table 14:Noisy consecutive ones \(60×6060\\times 60,w=12w=12,2020seeds\): row\|τ\|\|\\tau\|/ column\|τ\|\|\\tau\|/ edits\. Controls use the identical protocol and restart budget with a random or a block mask of the same density\.Paired against convex seriation, the columnτ\\tauof the staircase fit is higher by\+0\.075\+0\.075\[\+0\.063,\+0\.088\+0\.063,\+0\.088\],\+0\.136\+0\.136\[\+0\.118,\+0\.157\+0\.118,\+0\.157\],\+0\.280\+0\.280\[\+0\.220,\+0\.358\+0\.220,\+0\.358\] and\+0\.377\+0\.377\[\+0\.300,\+0\.469\+0\.300,\+0\.469\] atf=0\.02f=0\.02,0\.050\.05,0\.100\.10,0\.150\.15, and the edit count lower by9797\[89,10689,106\],148148\[137,160137,160\],215215\[194,238194,238\] and216216\[202,232202,232\], on2020of2020seeds at every level\. An insertion local search on the 2\-SUM criterion needs114114–201201more edits than the staircase fit on2020of2020seeds, so the gain is not produced by refinement as such\. Row totals are constant by construction and column totals vary only near the boundary, which is why sorting by marginals carries almost no information\. Runtimes:0\.030\.03s spectral,0\.180\.18s convex,0\.30\.3–0\.50\.5s local search,0\.50\.5–11s ours\.

Table[15](https://arxiv.org/html/2611.17674#A5.T15)repeats the comparison with the shape of the matrix, the start profile and the interval lengths varied\. The fixed staircase keeps the higherτ\\tauand the lower edit count for rectangular matrices, for an irregular start profile and for interval lengths jittered by up to±8\\pm 8, with the smallest margins under the irregular profile and the largest jitter\. Re\-estimating the mask from the data after the cold fit, one interval per row \(the interval\-envelope pattern of Figure[1](https://arxiv.org/html/2611.17674#S1.F1)\), lowers the edit count slightly and restores the row order under the irregular profile\.

Table 15:Noisy consecutive ones under changes of the generator \(2020seeds\): column\|τ\|\|\\tau\|/ edits for convex seriation, the fixed staircase mask and the mask re\-estimated as one interval per row; “noise” is the number of entries flipped during corruption\.Circular seriation\.A latent order can be cyclic rather than linear: similarities between points on a closed curve are banded modulonn, and spectral seriation needs a dedicated circular embedding for this case\[[Recanati et al\., 2018](https://arxiv.org/html/2611.17674#bib.bib46)\]\. The question is whether the same solver covers the cyclic geometry by changing only the mask\. Forn=120n=120points on a circle with a decaying kernel and Gaussian noise, the target is the cyclic band mask of width1010and the reference is the spectral circular embedding; the metric is circular Kendallτ\\tauup to rotation and reflection \(2020seeds\)\. Ours is the better of128128cold restarts and a coarse\-to\-fine run, chosen by the objective\. In Table[16](https://arxiv.org/html/2611.17674#A5.T16)both methods recover the order at low noise \(the difference is within±0\.01\\pm 0\.01\); at noise0\.50\.5and0\.70\.7the cyclic band is ahead \(\+0\.035\+0\.035and\+0\.103\+0\.103, on1313and1818of2020seeds\), and at noise1\.01\.0neither recovers the order and the interval contains zero\. The linear spectral order is far below throughout, so the cyclic mask, not a generic ordering, carries the result; the gain over the circular embedding is concentrated at moderate noise\.

Table 16:Circular seriation \(n=120n\{=\}120, cyclic bandw=10w\{=\}10\): circular Kendallτ\\tau, mean over2020seeds, and the paired difference of ours against the circular spectral embedding\.Nestedness: a boundary case\.In a nested \(Ferrers\) matrix the ones of each row contain those of every row with a smaller degree, the structure of species\-by\-site and similar ecological matrices\[[Brualdi and Sanderson, 1999](https://arxiv.org/html/2611.17674#bib.bib10)\]\. The question here is whether a general reordering objective adds anything where a one\-pass specialized method exists: sorting rows and columns by their marginals recovers a noiseless nested matrix exactly and, although under flip noise it need not minimize our objective, it is the reference\. For planted60×8060\\times 80Ferrers matrices with flip rateff, the two\-sided AltLAP uses the nested mask with its profile estimated from the row degrees \(no oracle information\); Table[17](https://arxiv.org/html/2611.17674#A5.T17)gives the column\|τ\|\|\\tau\|and the flips to a nested matrix \(2020seeds\)\. The mask fit reproduces the degree order atf≤0\.02f\\leq 0\.02and falls below it fromf=0\.05f=0\.05on, by0\.060\.06inτ\\tauatf=0\.15f=0\.15with a similar flip count; warm\-starting from the degree order does not help, and a larger restart budget does not change the values\. Where degree sorting already recovers the structure, the mask objective adds nothing; this is the boundary case noted in Section[5\.1](https://arxiv.org/html/2611.17674#S5.SS1)\.

Table 17:Nestedness \(60×8060\\times 80planted Ferrers matrices, flip rateff,2020seeds\): column\|τ\|\|\\tau\|/ flips to a nested matrix under the returned order \(lower is better\)\.
#### E\.6\.3Block models against the state of the art

Sparse binary SBM at the detectability scale\.Symmetric SBM withk=4k=4equal blocks,n=500n=500,cin=c\+\(k−1\)​λ​cc\_\{\\mathrm\{in\}\}=c\+\(k\-1\)\\lambda\\sqrt\{c\}andcout=c−λ​cc\_\{\\mathrm\{out\}\}=c\-\\lambda\\sqrt\{c\}, soλ=1\\lambda=1is the asymptotic \(Kesten–Stigum\) detectability threshold\[[Decelle et al\., 2011](https://arxiv.org/html/2611.17674#bib.bib19)\]; mean degreec∈\{8,16,32\}c\\in\\\{8,16,32\\\},2020seeds\. Panel: Bethe HessianH⁡\(r\)=\(r2−1\)​I−r​A\+DH\(r\)=\(r^\{2\}\-1\)I\-rA\+Dwithr=cr=\\sqrt\{c\}\[[Saade et al\., 2014](https://arxiv.org/html/2611.17674#bib.bib49)\]; the non\-backtracking operator in Ihara–Bass form\[[Krzakala et al\., 2013](https://arxiv.org/html/2611.17674#bib.bib34)\]; regularized spectral clustering\[[Qin and Rohe, 2013](https://arxiv.org/html/2611.17674#bib.bib43)\]; Leiden\[[Traag et al\., 2019](https://arxiv.org/html/2611.17674#bib.bib53)\], which estimateskkitself; the block mask fitted by Alternating LAP from eight random starts, the LAP and exchange phases interleaved per start \(three rounds\) and the best start kept by the criterion \(“ours”\); and the same run started from the Bethe\-Hessian partition\. All methods except Leiden receive the truekk; our mask also encodes equal block sizes, which the planted model satisfies and the spectral methods do not use\. On sparse\{0,1\}\\\{0,1\\\}graphs the LAP phase alone stalls early \(ARI0\.560\.56atλ=1\.6\\lambda=1\.6,c=16c=16, with the exchange phase disabled,3232starts\); with the exchange phase the fit reaches0\.820\.82\.

Table 18:Sparse SBM,k=4k=4,n=500n=500, mean ARI over2020seeds\. “Ours” is Alternating LAP from random starts; “swap only” is a Kernighan–Lin\-style exchange search alone from random balanced partitions \(same criterion and block sizes\); the paired difference is against the Bethe Hessian, with the best panel method per row in bold\.With equal block sizes the number of within\-block pairs is fixed, so maximizing the within\-block edge count, which is our criterion on a\{0,1\}\\\{0,1\\\}matrix, is the maximum\-likelihood objective for the planted partition at anynnand anyp\>qp\>q\(forp<qp<qthe sign reverses; fork=2k=2it is minimum bisection;[Abbe, 2018](https://arxiv.org/html/2611.17674#bib.bib1)\)\. The crossover of Section[5\.2](https://arxiv.org/html/2611.17674#S5.SS2)moves with the mean degree \(Table[18](https://arxiv.org/html/2611.17674#A5.T18)\)\. Below it the criterion values are0\.330\.33\(ours\) against0\.240\.24\(Bethe\-Hessian partition\) in error reduction atc=16c=16,λ=1\.3\\lambda=1\.3, with the ARIs in the opposite order; the gap between the MAP and the Bayes\-optimal \(belief\-propagation\) estimator near the threshold is the reason belief propagation and its spectral linearizations were introduced\[[Decelle et al\., 2011](https://arxiv.org/html/2611.17674#bib.bib19),[Krzakala et al\., 2013](https://arxiv.org/html/2611.17674#bib.bib34),[Saade et al\., 2014](https://arxiv.org/html/2611.17674#bib.bib49)\]\. We do not establish inconsistency of the criterion at thisnn, nor that the search reaches its global optimum\. Refining the Bethe\-Hessian partition with our criterion costs0\.30\.3–0\.50\.5s on top of its0\.040\.04s\.

Weighted planted partition\.A=μ⋅𝟏​\[same block\]\+EA=\\mu\\cdot\\mathbf\{1\}\[\\text\{same block\}\]\+Ewithμ\>0\\mu\>0andEEsymmetric with i\.i\.d\.𝒩⁡\(0,σ2\)\\mathcal\{N\}\(0,\\sigma^\{2\}\)upper\-triangular entries,σ=1\\sigma=1,n=300n=300,k=4k=4equal blocks,2020seeds\. This is the regime of the block experiments in the paper, where minimizing the*signed*off\-mask mass is the maximum\-likelihood criterion for the partition\. Spectral clustering on the weighted matrix is the natural baseline; the graph methods are defined for graphs and receive the matrix sparsified at its strongest10%10\\%of entries\. The squared loss rewards large negative off\-mask entries as if they were structure, which is why it fails on this generator, whose blocks differ in mean but not in variance \(the ablation column\); the linear loss, which on a\{0,1\}\\\{0,1\\\}matrix coincides with the squared one, is the likelihood here\. A Kernighan–Lin\-style swap search on the same linear criterion tracks the cold run fromμ=0\.4\\mu\{=\}0\.4on and lies0\.020\.02–0\.030\.03below it at the two weakest signals, so on these dense matrices the criterion, not the particular optimizer, carries the result\.

Table 19:Weighted planted partition \(n=300n=300,k=4k=4,σ=1\\sigma=1\), mean ARI over2020seeds; paired difference of ours \(AltLAP\-lin, cold start\) against spectral clustering\. “Squared” is AltLAP on the squared loss of Definition[1](https://arxiv.org/html/2611.17674#Thmdefinition1)\(the ablation row\); “KL \(lin\.\)” is a Kernighan–Lin\-style swap search on the same linear criterion from random balanced starts, an alternative optimizer of our objective\.At the weakest signal the cold run is within the interval of spectral clustering and the spectral\-started run is the entry that pays:\+0\.154\+0\.154\[\+0\.118,\+0\.188\+0\.118,\+0\.188\] and\+0\.159\+0\.159\[\+0\.135,\+0\.182\+0\.135,\+0\.182\] over spectral clustering atμ=0\.30\\mu=0\.30and0\.350\.35\.

##### Block sizes\.

The block mask fixes the block sizes, which above are the planted \(equal\) ones\. Table[20](https://arxiv.org/html/2611.17674#A5.T20)plants blocks of sizes1:1:2:21\{:\}1\{:\}2\{:\}2as well and gives the solver the equal\-size mask, the true sizes, or sizes estimated as the cluster sizes of the size\-free spectral method in the same panel \(regularized spectral clustering on the graphs, spectral clustering on the weighted matrices; no labels\), next to the size\-free baselines, the Kernighan–Lin\-style swap search on the same criterion with the true sizes \(KL\) and Alternating LAP started from the Bethe\-Hessian partition\. With equal planted blocks the estimated sizes cost almost nothing\. With unequal blocks the equal\-size mask is misspecified and falls below the size\-free methods, the true sizes give the best result in the panel, and the estimated sizes recover most of the gap, above the partition they were taken from\. The swap search from random starts needs the dense signal of the weighted matrices and stays low on the sparse graphs, so the LAP steps, not the exchanges alone, do the work there\.

Table 20:Block recovery with the block sizes in the mask equal, true, or estimated from a spectral partition \(ARI\)\. Top: sparse SBM,n=500n\{=\}500,k=4k\{=\}4,c=16c\{=\}16,2020seeds, ours==Alternating LAP\. Bottom: weighted planted partition,n=300n\{=\}300,k=4k\{=\}4,σ=1\\sigma\{=\}1,1010seeds,1616restarts, ours==AltLAP\-lin\.Real labelled networks\.The same panel on standard networks with published communities \(Table[21](https://arxiv.org/html/2611.17674#A5.T21); equal\-size masks, or “\+sizes”: block sizes re\-estimated from the order by change\-point segmentation, three rounds, no oracle information\)\. Reference partitions: the two factions of Zachary’s karate club\[[Zachary, 1977](https://arxiv.org/html/2611.17674#bib.bib60)\]; the two groups of nine women of the Davis Southern Women data\[[Davis et al\., 1941](https://arxiv.org/html/2611.17674#bib.bib18),[Freeman, 2003](https://arxiv.org/html/2611.17674#bib.bib22)\], with the bipartite women–events graph used as a symmetric adjacency on all3232nodes and ARI computed on the1818women; the three classes of the political\-books network \(compiled by V\. Krebs;[Newman, 2006](https://arxiv.org/html/2611.17674#bib.bib40)\) and the twelve conferences of the football network\[[Girvan and Newman, 2002](https://arxiv.org/html/2611.17674#bib.bib26)\]\. All methods receivekk; PatLR uses rank11; results are means over1010seeds \(standard deviations≤0\.03\\leq 0\.03, zero for the deterministic methods\)\. Les Misérables has no published partition \(theblock⁡\(19,19,19,20\)\\mathrm\{block\}\(19,19,19,20\)mask of Section[5\.3](https://arxiv.org/html/2611.17674#S5.SS3)is an equal split, not a ground truth\) and is not scored here\. Two details behind Section[5\.2](https://arxiv.org/html/2611.17674#S5.SS2): on Karate the low\-rank term of PatLR carries the degree profile, which the plain block fit has to place inside the blocks; on polbooks \(49/43/1349/43/13\) the equal\-size mask improves the error reduction while the ARI does not move, a balanced partition being a different problem from community detection\.

Table 21:Community recovery on labelled networks \(ARI\)\. “\+sizes”: block sizes re\-estimated from the order \(change\-point segmentation\) instead of equal sizes; “BH→\\to” initializes from the Bethe\-Hessian partition\. PatLR uses rank11\.

#### E\.6\.4Composite target: a band inside blocks

Planted matrices withk∈\{3,5\}k\\in\\\{3,5\\\}blocks \(equal or unequal sizes\), a band of widthw∈\{1,3\}w\\in\\\{1,3\\\}inside each block, noiseσ∈\{0\.1,0\.3\}\\sigma\\in\\\{0\.1,0\.3\\\},n=150n=150,2020seeds:1616configurations\. The target mask is the band*inside*the blocks \(block AND band\); the union mask would be blind to the within\-block order\. Metrics: error reduction on the target mask, ARI of the block assignment read off the order, and within\-block Kendallτ\\tau\. Methods: spectral clustering \(blocks only\), global Fiedler ordering, a two\-stage pipeline \(cluster, then spectral order within each cluster\), QAP\-FAQ and AltLAP on the composite mask, AltLAP with a change\-point estimate of the block boundaries \(for unequal sizes\), and AltLAP warm\-started from the two\-stage pipeline\.

Table 22:Composite band\-in\-block target, averages over the1616configurations and2020seeds; per\-configuration values in Table[23](https://arxiv.org/html/2611.17674#A5.T23)\.Methodtarget ERblock ARIwithin\-blockτ\\tauSpectral clustering0\.0571\.0000\.09Fiedler ordering0\.0500\.8390\.10Two\-stage \(cluster, then order\)0\.1151\.0000\.45QAP\-FAQ \(composite mask\)0\.1370\.1810\.18AltLAP \(composite mask\)0\.1710\.7810\.20AltLAP \+ boundary estimation0\.1730\.8770\.20Two\-stage, then AltLAP0\.1901\.0000\.47Two\-stage, convex seriation inside0\.1241\.0000\.46Two\-stage \(convex\), then AltLAP0\.1931\.0000\.48Table[22](https://arxiv.org/html/2611.17674#A5.T22)averages over the configurations and Table[23](https://arxiv.org/html/2611.17674#A5.T23)gives each one with its paired interval; the summary is in Section[5\.2](https://arxiv.org/html/2611.17674#S5.SS2)\. Details: the refining pass re\-estimates the block boundaries from the order by change\-point segmentation, so the block sizes are not given; it raises the target error reduction by\+17%\+17\\%to\+257%\+257\\%relative \(median\+96%\+96\\%\), from a median45%45\\%of the planted order’s value for the pipeline to94%94\\%for the refined run \(9090–99%99\\%atw=3w\{=\}3,σ=0\.1\\sigma\{=\}0\.1\), and by\+11%\+11\\%to\+227%\+227\\%when the pipeline uses convex seriation inside the clusters; the within\-blockτ\\taugain atw=3w\{=\}3is\+0\.02\+0\.02to\+0\.09\+0\.09with the interval above zero in77of88configurations, and atw=1w\{=\}1it is within±0\.02\\pm 0\.02, a band of width one determining little of the order\. From a cold start the composite mask alone gives block ARI0\.780\.78, and0\.880\.88with the boundary estimate \(e\.g\.0\.45→0\.890\.45\\to 0\.89onk=3k=3, unequal,w=3w=3,σ=0\.3\\sigma=0\.3\); for the within\-block order the hard mask truncates the smooth decay, and the pipeline’s seriation is the better starting point, which is why the two are combined\. FAQ from its default starts does not recover the blocks \(Table[22](https://arxiv.org/html/2611.17674#A5.T22)\)\.

Table 23:Composite target per configuration \(2020seeds\): the two\-stage pipeline \(spectral clustering, spectral seriation inside each cluster\) and the same pipeline followed by one AltLAP pass on the band\-in\-block mask; “oracle” is the error reduction of the planted order on that mask\. Paired differences with95%95\\%bootstrap intervals; block ARI is1\.001\.00for both in every configuration\. The last two columns repeat the ER for the pipeline with convex seriation inside the clusters \.

### E\.7Attention Head Analysis: Full Details

This appendix gives the pipeline behind Section[5\.5](https://arxiv.org/html/2611.17674#S5.SS5), the per\-model results, and the identity\-order control\. All numbers come from one run of the unified scoring described below\.

#### E\.7\.1Score, Vocabulary and a Synthetic Check

The scores~M​\(A\)\\tilde\{s\}\_\{M\}\(A\)of \([6](https://arxiv.org/html/2611.17674#S4.E6)\) on a causal attention matrix \(rows queries, columns keys\) is the minimum mass outside the mask after a common reordering of queries and keys, normalized by‖A‖F2​\(1−ρM\)3/2\\\|A\\\|\_\{F\}^\{2\}\(1\-\\rho\_\{M\}\)^\{3/2\}\(equation \([6](https://arxiv.org/html/2611.17674#S4.E6)\)\)\. The strict upper triangle is identically zero and contributes nothing todMd\_\{M\}for any mask and permutation, so no symmetrization is needed\. The masks are the plain geometric masks of Section[2](https://arxiv.org/html/2611.17674#S2), not their intersection with the lower triangle \(the arrowhead is the full hub row, hub column and diagonal, which is what the closed form of Appendix[C\.3](https://arxiv.org/html/2611.17674#A3.SS3)assumes\); a common permutation does not preserve the causal triangle itself, and the structural labels describe the reordered matrix\. The nine masks of Section[5\.5](https://arxiv.org/html/2611.17674#S5.SS5)were fixed ahead of time to span the regimes of the standard taxonomy of attention\[[Clark et al\., 2019](https://arxiv.org/html/2611.17674#bib.bib14),[Voita et al\., 2019](https://arxiv.org/html/2611.17674#bib.bib56),[Xiao et al\., 2024](https://arxiv.org/html/2611.17674#bib.bib59)\]: local routing \(bands of width11,22,44\), segment\- or topic\-level grouping \(blocks,k=2,3,4k=2,3,4\), sink\-like global routing of every query to a few distinguished keys such as BOS \(arrowhead\), modular\-local heads \(three blocks plus the band\|i−j\|≤2\|i\-j\|\\leq 2\) and pure self\-loops \(diagonal\)\. The vocabulary is a controlled basis set, not an exhaustive one\. Atn=512n\{=\}512the block\+band mask \(blocks of170170plus a remainder block of22, plus the band\) differs from block\-kk3 \(blocks of170170,170170,172172\) in0\.3%0\.3\\%of the entries, so near\-ties between the two labels are expected and the two are read together below\.

##### Synthetic check\.

Four head types with a constructed ground truth are scored with the full pipeline atn=128n\{=\}128\(2020instances each, scrambled by a random permutation; Table[24](https://arxiv.org/html/2611.17674#A5.T24), Figure[10](https://arxiv.org/html/2611.17674#A5.F10)\): a local head \(Gaussian kernel of width1\.51\.5tokens plus noise, so that the band\|i−j\|≤4\|i\-j\|\\leq 4holds99%99\\%of the kernel mass\), a topic head \(three equal blocks plus noise\), a global head \(every query attends the first key, plus a diagonal and noise\) and a self head \(a dominant diagonal plus noise\)\. The global and topic heads are identified in every instance, the topic head either as block\-kk3 or as the block\+band mask that contains its blocks; the local head is identified in most instances, with block masks selected otherwise at a small margin \(the noise carries two thirds of the energy of these instances\)\. The self head is a boundary case of the vocabulary: every mask that contains the diagonal fits it, the optimized thin bands pack slightly more noise than the diagonal alone, and the label is a thin band in every instance, by a small margin\. A pure self\-loop head is therefore reported by this pipeline as a thin band, and the band labels of real heads should be read as covering it\.

Table 24:Synthetic attention heads scored with the paper’s pipeline \(9\-mask vocabulary, density\-normalized score, identity candidate,n=128n\{=\}128,2020instances per type\): instances in which the true mask is the label, the labels selected, and the median relative margin of the selected mask over the runner\-up\.![Refer to caption](https://arxiv.org/html/2611.17674v1/fig_attention_synthetic.png)Figure 10:Synthetic attention heads, one instance per type: the scrambled input \(top\) and the same matrix in the order returned for the selected mask, mask outlined \(bottom\), with the density\-normalized scores of the selected and, where different, of the true mask\.

#### E\.7\.2Pipeline

Models and prompts\.GPT\-2\[[Radford et al\., 2019](https://arxiv.org/html/2611.17674#bib.bib45),117117M parameters,1212layers×\\times1212heads;\], Qwen2\.5\-0\.5B \(24×1424\{\\times\}14\) and Qwen2\.5\-7B \(28×2828\{\\times\}28\)\[[Qwen Team, 2024](https://arxiv.org/html/2611.17674#bib.bib44)\], loaded from the Hugging Face hub \(gpt2,Qwen/Qwen2\.5\-0\.5B,Qwen/Qwen2\.5\-7B\)\. The prompts are the first2020passages of at least5​n5ncharacters formed from consecutive non\-heading lines of the WikiText\-2 validation split\[[Merity et al\., 2017](https://arxiv.org/html/2611.17674#bib.bib39)\]\(its first two to five articles\), tokenized by each model’s tokenizer and truncated ton∈\{128,512\}n\\in\\\{128,512\\\}tokens \(two passages fall a few tokens short of512512\); the passages differ between the two lengths\.

Extraction\.One forward pass per \(model, prompt, length\) on a single GPU \(one H100; about two hours for the full grid of models, prompts and lengths\) returns theL×H×n×nL\{\\times\}H\{\\times\}n\{\\times\}ntensor of post\-softmax attention weights \(fp16 for the Qwen models, fp32 for GPT\-2; non\-finite rows, which occur in≤0\.1%\\leq 0\.1\\%of the rows of Qwen2\.5\-7B, are zeroed\)\.

Scoring\.For every \(layer, head, prompt\) and every mask of the vocabulary we compute \(i\) the optimized score, Alternating LAP from a spectral start with88iterations and22restarts atn=512n\{=\}512\(1212and33atn=128n\{=\}128\)\. On a causalAAthe symmetric eigensolver of Appendix[D\.1](https://arxiv.org/html/2611.17674#A4.SS1)reads the lower triangle, so the operator it diagonalizes isD−WD\-WwithW=A\+A⊤−diag​AW=A\+A^\{\\top\}\-\\mathrm\{diag\}\\,AandD=diag⁡\(A​𝟏\)D=\\mathrm\{diag\}\(A\\mathbf\{1\}\), the identity for softmax rows; the start is therefore the order by the second\-largest eigenvector of the symmetrized attention matrixWW, not the Fiedler vector of its graph Laplacian \(whose degree matrix would bediag⁡\(W​𝟏\)\\mathrm\{diag\}\(W\\mathbf\{1\}\)\)\. The objective itself is not symmetrized\. \(ii\) The identity score, under the native token order, and \(iii\) the mean score under five random permutations \(the null level\)\. The score of a mask is the lower of \(i\) and \(ii\); for the arrowhead mask the closed\-form optimum of Appendix[C\.3](https://arxiv.org/html/2611.17674#A3.SS3)is taken as well \(it is attained to within1%1\\%by the solver for99\.699\.6–99\.9%99\.9\\%of the pairs\)\. The label of a pair is the mask with the lowest score; its margin is the relative gap to the runner\-up\. Scoring one512512\-token head takes about1212core\-seconds \(Appendix[E\.8](https://arxiv.org/html/2611.17674#A5.SS8)\)\.

Intervals\.All intervals are95%95\\%bootstrap intervals over prompts \(the2020prompts resampled with replacement, the statistic recomputed on all heads\), i\.e\. they treat the prompt, not the \(head, prompt\) pair, as the unit of replication\.

#### E\.7\.3Per\-Model Results

Table[25](https://arxiv.org/html/2611.17674#A5.T25)gives the per\-model numbers behind Section[5\.5](https://arxiv.org/html/2611.17674#S5.SS5)at both lengths; Figure[11](https://arxiv.org/html/2611.17674#A5.F11)the per\-layer label shares and Figure[12](https://arxiv.org/html/2611.17674#A5.F12)the per\-head modal label, its agreement over prompts and its margin\. The depth profile is the same in all six \(model, length\) cells: block labels in the first three to four layers, arrowhead after them, with Qwen2\.5\-0\.5B returning to block\-kk2 in its last two layers at both lengths\. Within a model the label shares move by a few points betweenn=128n\{=\}128andn=512n\{=\}512, and the modal label of a head is the same at both lengths for9191–95%95\\%of the heads \(0\.700\.70–0\.770\.77among the heads whose modal label is not arrowhead at both lengths, so the block\-type labels are less stable than the arrowhead label and the layer profile\)\. On the1010\-bin relative\-depth grid the three models agree in8/108/10bins at both lengths; pairwise agreement is0\.90\.9for GPT\-2 vs\. Qwen2\.5\-7B and for Qwen2\.5\-0\.5B vs\. Qwen2\.5\-7B and0\.80\.8for GPT\-2 vs\. Qwen2\.5\-0\.5B\. The last column of Table[25](https://arxiv.org/html/2611.17674#A5.T25)is the accuracy of a multinomial logistic regression that predicts the label of a pair from four scalar descriptors of the head on that prompt \(row entropy, mean maximum weight, sparsity, mean distance from the diagonal\), trained on1919prompts and tested on the held\-out one; it is well above the majority label and well below one, so these descriptors partially predict the labels under the tested logistic\-regression model\. About three quarters of the pairs carry a confident label, a margin over the runner\-up above20%20\\%\(column “confident”\)\. Figure[13](https://arxiv.org/html/2611.17674#A5.F13)shows representative heads before and after reordering: the block\-labelled heads of the first layers are wide local heads whose mass already lies in the diagonal blocks in the native order \(the native order is within1%1\\%of the optimum for7474–84%84\\%of the block\-labelled pairs atn=512n\{=\}512,5757–71%71\\%atn=128n\{=\}128\), and on the Qwen2\.5\-7B passages whose sink is not the first token the reordering moves the sink key to the front\.

Table 25:Per\-model attention results \(unified scoring\)\. Label shares in % of \(head, prompt\) pairs: arrowhead with its95%95\\%interval over prompts, block\-kk2, the other block masks and block\+band together, bands and diagonal together\. Agreement: mean per\-head agreement with the head’s modal label over the2020prompts, for all heads, for the heads whose modal label is arrowhead, and for the others\. Confident: share of pairs whose margin over the runner\-up exceeds20%20\\%\. Null: median ratio of the selected mask’s score to its score under random permutations\. Scalars: leave\-one\-prompt\-out accuracy of predicting the label from four scalar descriptors / majority baseline\.Figure 11:Share of the top\-11label per layer for the three models \(columns\) atn=512n\{=\}512\(top\) andn=128n\{=\}128\(bottom\),2020prompts\.![Refer to caption](https://arxiv.org/html/2611.17674v1/fig_attention_headmap.png)Figure 12:Per\-head view atn=512n\{=\}512, one row per model: the modal label over the2020prompts \(left\), the share of prompts carrying that label \(middle\) and the median relative margin of the selected mask over the runner\-up \(right\)\.![Refer to caption](https://arxiv.org/html/2611.17674v1/fig_app_permuted.png)Figure 13:Representative heads of each model atn=128n\{=\}128\(one passage per model\), logarithmic colour scale: a block\-labelled head \(left pair\) and an arrowhead head \(right pair\), each in the native token order and in the order found for the selected mask, mask outlined, with the density\-normalized score\. The block\-labelled heads are wide local heads, fitted by the native order; the Qwen2\.5\-7B arrowhead head has its sink at a key other than the first token \(identity score1\.021\.02\), which the reordering brings to the front\.
#### E\.7\.4Identity\-Order Control and Long\-Context Control

Are the permutations needed?Table[26](https://arxiv.org/html/2611.17674#A5.T26)scores every \(head, prompt\) pair atn=512n\{=\}512under three rules: the identity order only, the optimized order only \(spectral start, no identity candidate\), and the unified rule that keeps the identity as a candidate for every mask\. The optimized score of a mask can be worse than its identity score, because the solver is started from the spectral start and not from the identity, and on causal attention the native order already is the band; comparing identity labels with optimized\-only labels therefore counts label changes caused by competing masks getting worse\. Under the unified rule only a few percent of the labels of GPT\-2 and Qwen2\.5\-0\.5B change, against about a fifth under the optimized\-only rule\. On Qwen2\.5\-7B the change is concentrated on particular passages: on1515of the2020passages atn=512n\{=\}512\(1414atn=128n\{=\}128\) the native\-order arrowhead share is0\.820\.82and33–5%5\\%of the labels change, as on the smaller models; on the remaining passages, all of which begin with the token “The”, the sink is not the first token, the native\-order arrowhead share is below0\.020\.02, and8383–85%85\\%of the labels change\. With reordering the arrowhead share is0\.770\.77–0\.830\.83on every Qwen2\.5\-7B passage\. This is also why the interval over prompts of the Qwen2\.5\-7B label\-change rate in Table[26](https://arxiv.org/html/2611.17674#A5.T26)is wide\. The last column checks the solver against the closed\-form arrowhead optimum \(Appendix[C\.3](https://arxiv.org/html/2611.17674#A3.SS3)\)\.

Table 26:Identity\-order control atn=512n\{=\}512,2020prompts\. Arrowhead share of the \(head, prompt\) labels under the identity order, under the optimized order only, and under the unified rule \(identity kept as a candidate\); share of labels that differ from the identity labels under the unified rule \(95%95\\%interval over prompts\) and under the optimized\-only rule; share of pairs on which the solver’s arrowhead score is within1%1\\%of the closed\-form optimum\.Position subsampling does not transfer\.A tempting shortcut for long contexts is to score a random subset of128128of the512512positions\. The label obtained this way agrees with the full\-length label for only0\.400\.40/0\.410\.41/0\.410\.41of \(head, prompt\) pairs \(GPT\-2 / Qwen2\.5\-0\.5B / Qwen2\.5\-7B;55prompts, two draws each, unified scoring at the sub\-length budget\), and the per\-head modal label over these draws agrees with the full\-length one for about half of the heads, against0\.910\.91–0\.950\.95agreement of the per\-head modal label between the contiguousn=128n\{=\}128andn=512n\{=\}512contexts\. Non\-contiguous subsampling destroys the band and block geometry; long contexts should be analysed on contiguous windows or with the scaling routes of Appendix[E\.8](https://arxiv.org/html/2611.17674#A5.SS8)\.

### E\.8Wall\-Clock Scaling of Alternating LAP

Planted banded instances in the Gaussian regime of Section[5\.1](https://arxiv.org/html/2611.17674#S5.SS1)\(w=5w\{=\}5\), one Fiedler\-initialized run of the LAP phase with an iteration cap of1010,33seeds at everynn; the exchange phase is timed separately below\. All times are single\-thread wall\-clock seconds \(BLAS and the assignment solver pinned to one core\) on an Apple M3 with1818GB of memory; peak resident memory is the maximum over the three runs\. Two noise series are reported: the per\-entry noise fixed atσn=0\.05\\sigma\_\{n\}\{=\}0\.05\(the regime of Table[1](https://arxiv.org/html/2611.17674#S5.T1)\), under which the band holds a1/n1/nfraction of the energy and the error reduction of the planted order itself falls from0\.800\.80to0\.200\.20; and the noise scaled asσn∝n−1/2\\sigma\_\{n\}\\propto n^\{\-1/2\}, which keeps the planted order’s error reduction at0\.800\.80for everynn\. Table[27](https://arxiv.org/html/2611.17674#A5.T27)gives the measurements\.

Table 27:Wall\-clock scaling of the LAP phase of one Alternating LAP run \(single thread, Apple M3\)\. Times in seconds; “LAPs” is the part of an iteration spent in the two assignment solves; ER is the error reduction of the solver and, in parentheses, of the planted order\. FAQ: one run of QAP\-FAQ on the same instances and objective\. Means over33seeds \(FAQ atn≥4000n\\geq 4000and the fixed\-SNR series atn=8000n\{=\}8000: one seed\)\.##### Cost\.

An iteration of the LAP phase is twoO⁡\(n3\)O\(n^\{3\}\)cost\-matrix products and two assignment solves; the solves take three quarters of it at smallnnand half atn=8000n\{=\}8000, and the iteration time decreases as the iterates converge \(first and last iteration atn=8000n\{=\}8000:7878s and2222s\), so the total grows by44–8×8\\timesper doubling ofnn\. The dense Fiedler start \(a full eigendecomposition\) becomes a fifth of the total at the largest size\. Memory is a handful of densen×nn\\times ndoubles\. FAQ on the same objective costs22–4×4\\timesmore and reaches a similar error reduction from one start\.

##### Exchange phase\.

On the same instances, started from the output of the LAP phase above, the exchange descent of Appendix[D\.1](https://arxiv.org/html/2611.17674#A4.SS1)takes0\.80\.8–1\.11\.1s atn=500n\{=\}500\(2020–2828rounds\),6\.46\.4–7\.67\.6s atn=1000n\{=\}1000\(3232–3939rounds\) and2424–4848s atn=2000n\{=\}2000\(2525–4848rounds\), and raises the error reduction by0\.070\.07–0\.080\.08,0\.060\.06–0\.070\.07and0\.040\.04–0\.050\.05\. A round is dominated by the gain evaluation, twon×nn\\times nproducts:0\.40\.4s atn=2000n\{=\}2000,2\.72\.7s atn=4000n\{=\}4000and2020s atn=8000n\{=\}8000on this machine, so at the observed2525–5050rounds the phase would take a few minutes atn=4000n\{=\}4000and of the order of1010–2020minutes atn=8000n\{=\}8000, comparable with the LAP phase; it was not run at these two sizes\. On the same machine PatLR \(rank33,1212iterations,33restarts\) takes3\.03\.0s atn=200n\{=\}200,2222s atn=500n\{=\}500and134134s atn=1000n\{=\}1000; Adaptive PatLR \(N=80N\{=\}80,ℓ=3\\ell\{=\}3, default vocabulary\)2\.92\.9s atn=200n\{=\}200and3131s atn=500n\{=\}500, i\.e\.11–1\.4×1\.4\\timesthe cost of one PatLR call\. The benchmark panels and the attention scoring run as single\-threaded processes on a2424\-core AMD EPYC; scoring one512×512512\\times 512attention head against the99\-mask vocabulary \(88iterations,22restarts per mask, plus the identity and five random permutations\) takes about1212core\-seconds there, so the full grid of Section[5\.5](https://arxiv.org/html/2611.17674#S5.SS5)\(1,2641\{,\}264heads×\\times2020prompts atn=512n\{=\}512, and again atn=128n\{=\}128\) is about8585core\-hours \(2222processes\)\.

##### Scaling routes\.

On one M3 core a solve on a planted banded instance thus takes about two seconds atn=500n\{=\}500and, for the LAP phase alone, minutes atn=8000n\{=\}8000\(Table[27](https://arxiv.org/html/2611.17674#A5.T27)\), and a vocabulary scan of a single80008000\-token matrix would take hours per head\. The cost matrix is dense \(a banded mask only makes itO⁡\(n2\)O\(n^\{2\}\)to assemble\), so the assignment solve is the bottleneck; sparse assignment with restricted candidates, coarsen\-then\-refine, and GPU Sinkhorn or auction solvers\[[Cuturi, 2013](https://arxiv.org/html/2611.17674#bib.bib17),[Bertsekas, 1988](https://arxiv.org/html/2611.17674#bib.bib8)\]are left for future work\.

##### Quality againstnn\.

The iteration cap is not binding: with the cap raised to3030the solver stops by its own convergence test after99–1212iterations atn≤2000n\\leq 2000and the error reduction changes by less than0\.0010\.001\. Under fixed per\-entry noise the error reduction falls withnnbecause the attainable reduction falls: the solver reaches a stable two thirds to three quarters of the planted order’s value at everynn\. With the matrix SNR held fixed the error reduction does not degrade with size; it rises slowly withnn\. Under fixed per\-entry noise the Fiedler start alone reduces the error by0\.10\.1atn=500n\{=\}500and by less than0\.040\.04atn≥1000n\\geq 1000\(the Laplacian of\|A\|\|A\|is dominated by the dense noise\), so the reduction is produced by the LAP iterations\.

## NeurIPS Paper Checklist

1. 1\.Claims
2. Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?
3. Answer:\[Yes\]
4. Justification: Claims match Sections[2](https://arxiv.org/html/2611.17674#S2)–[5](https://arxiv.org/html/2611.17674#S5)and the appendices\.
5. Guidelines: - •The answer\[N/A\]means that the abstract and introduction do not include the claims made in the paper\. - •The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations\. A\[No\]or\[N/A\]answer to this question will not be perceived well by the reviewers\. - •The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings\. - •It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper\.
6. 2\.Limitations
7. Question: Does the paper discuss the limitations of the work performed by the authors?
8. Answer:\[Yes\]
9. Justification: Section[6](https://arxiv.org/html/2611.17674#S6): cost, local optima, vocabulary scope, proxy objective, theory scope\.
10. Guidelines: - •The answer\[N/A\]means that the paper has no limitation while the answer\[No\]means that the paper has limitations, but those are not discussed in the paper\. - •The authors are encouraged to create a separate “Limitations” section in their paper\. - •The paper should point out any strong assumptions and how robust the results are to violations of these assumptions \(e\.g\., independence assumptions, noiseless settings, model well\-specification, asymptotic approximations only holding locally\)\. The authors should reflect on how these assumptions might be violated in practice and what the implications would be\. - •The authors should reflect on the scope of the claims made, e\.g\., if the approach was only tested on a few datasets or with a few runs\. In general, empirical results often depend on implicit assumptions, which should be articulated\. - •The authors should reflect on the factors that influence the performance of the approach\. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting\. Or a speech\-to\-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon\. - •The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size\. - •If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness\. - •While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper\. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community\. Reviewers will be specifically instructed to not penalize honesty concerning limitations\.
11. 3\.Theory assumptions and proofs
12. Question: For each theoretical result, does the paper provide the full set of assumptions and a complete \(and correct\) proof?
13. Answer:\[Yes\]
14. Justification: Full proofs in Appendices[B](https://arxiv.org/html/2611.17674#A2)–[C](https://arxiv.org/html/2611.17674#A3); assumptions stated with each result\.
15. Guidelines: - •The answer\[N/A\]means that the paper does not include theoretical results\. - •All the theorems, formulas, and proofs in the paper should be numbered and cross\-referenced\. - •All assumptions should be clearly stated or referenced in the statement of any theorems\. - •The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition\. - •Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material\. - •Theorems and Lemmas that the proof relies upon should be properly referenced\.
16. 4\.Experimental result reproducibility
17. Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper \(regardless of whether the code and data are provided or not\)?
18. Answer:\[Yes\]
19. Justification: Setups, hyperparameters and seed counts per experiment \(typically2020, exceptions stated\) in Section[5](https://arxiv.org/html/2611.17674#S5)and Appendix[E](https://arxiv.org/html/2611.17674#A5)\.
20. Guidelines: - •The answer\[N/A\]means that the paper does not include experiments\. - •If the paper includes experiments, a\[No\]answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not\. - •If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable\. - •Depending on the contribution, reproducibility can be accomplished in various ways\. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model\. In general\. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model \(e\.g\., in the case of a large language model\), releasing of a model checkpoint, or other means that are appropriate to the research performed\. - •While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution\. For example 1. \(a\)If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm\. 2. \(b\)If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully\. 3. \(c\)If the contribution is a new model \(e\.g\., a large language model\), then there should either be a way to access this model for reproducing the results or a way to reproduce the model \(e\.g\., with an open\-source dataset or instructions for how to construct the dataset\)\. 4. \(d\)We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility\. In the case of closed\-source models, it may be that access to the model is limited in some way \(e\.g\., to registered users\), but it should be possible for other researchers to have some path to reproducing or verifying the results\.
21. 5\.Open access to data and code
22. Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
23. Answer:\[No\]
24. Justification: No code release; Algorithms[1](https://arxiv.org/html/2611.17674#alg1)–[3](https://arxiv.org/html/2611.17674#alg3)fully specified; all data public\.
25. Guidelines: - •The answer\[N/A\]means that paper does not include experiments requiring code\. - • - •While we encourage the release of code and data, we understand that this might not be possible, so\[No\]is an acceptable answer\. Papers cannot be rejected simply for not including code, unless this is central to the contribution \(e\.g\., for a new open\-source benchmark\)\. - •The instructions should contain the exact command and environment needed to run to reproduce the results\. See the NeurIPS code and data submission guidelines \([https://neurips\.cc/public/guides/CodeSubmissionPolicy](https://neurips.cc/public/guides/CodeSubmissionPolicy)\) for more details\. - •The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc\. - •The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines\. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why\. - •At submission time, to preserve anonymity, the authors should release anonymized versions \(if applicable\)\. - •Providing as much information as possible in supplemental material \(appended to the paper\) is recommended, but including URLs to data and code is permitted\.
26. 6\.Experimental setting/details
27. Question: Does the paper specify all the training and test details \(e\.g\., data splits, hyperparameters, how they were chosen, type of optimizer\) necessary to understand the results?
28. Answer:\[Yes\]
29. Justification: Section[5](https://arxiv.org/html/2611.17674#S5)and Appendix[E](https://arxiv.org/html/2611.17674#A5)\.
30. Guidelines: - •The answer\[N/A\]means that the paper does not include experiments\. - •The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them\. - •The full details can be provided either with the code, in appendix, or as supplemental material\.
31. 7\.Experiment statistical significance
32. Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
33. Answer:\[Yes\]
34. Justification:95%95\\%bootstrap intervals: over seeds \(typically2020\) for the benchmarks, over the2020prompts for attention\.
35. Guidelines: - •The answer\[N/A\]means that the paper does not include experiments\. - •The authors should answer\[Yes\]if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper\. - •The factors of variability that the error bars are capturing should be clearly stated \(for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions\)\. - •The method for calculating the error bars should be explained \(closed form formula, call to a library function, bootstrap, etc\.\) - •The assumptions made should be given \(e\.g\., Normally distributed errors\)\. - •It should be clear whether the error bar is the standard deviation or the standard error of the mean\. - •It is OK to report 1\-sigma error bars, but one should state it\. The authors should preferably report a 2\-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified\. - •For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range \(e\.g\., negative error rates\)\. - •If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text\.
36. 8\.Experiments compute resources
37. Question: For each experiment, does the paper provide sufficient information on the computer resources \(type of compute workers, memory, time of execution\) needed to reproduce the experiments?
38. Answer:\[Yes\]
39. Justification: Attention extraction: one H100, about22hours\. Benchmark panels and attention scoring: AMD EPYC, single\-threaded processes, about8585core\-hours\. Scaling study and PatLR timings: Apple M3 \(Appendix[E\.8](https://arxiv.org/html/2611.17674#A5.SS8)\)\.
40. Guidelines: - •The answer\[N/A\]means that the paper does not include experiments\. - •The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage\. - •The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute\. - •The paper should disclose whether the full research project required more compute than the experiments reported in the paper \(e\.g\., preliminary or failed experiments that didn’t make it into the paper\)\.
41. 9\.Code of ethics
43. Answer:\[Yes\]
44. Justification: Conforms\.
45. Guidelines: - •The answer\[N/A\]means that the authors have not reviewed the NeurIPS Code of Ethics\. - •If the authors answer\[No\], they should explain the special circumstances that require a deviation from the Code of Ethics\. - •The authors should make sure to preserve anonymity \(e\.g\., if there is a special consideration due to laws or regulations in their jurisdiction\)\.
46. 10\.Broader impacts
47. Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
48. Answer:\[N/A\]
49. Justification: Foundational matrix analysis; no direct societal impact\.
50. Guidelines: - •The answer\[N/A\]means that there is no societal impact of the work performed\. - •If the authors answer\[N/A\]or\[No\], they should explain why their work has no societal impact or why the paper does not address societal impact\. - •Examples of negative societal impacts include potential malicious or unintended uses \(e\.g\., disinformation, generating fake profiles, surveillance\), fairness considerations \(e\.g\., deployment of technologies that could make decisions that unfairly impact specific groups\), privacy considerations, and security considerations\. - •The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments\. However, if there is a direct path to any negative applications, the authors should point it out\. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate Deepfakes for disinformation\. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster\. - •The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from \(intentional or unintentional\) misuse of the technology\. - •If there are negative societal impacts, the authors could also discuss possible mitigation strategies \(e\.g\., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML\)\.
51. 11\.Safeguards
52. Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse \(e\.g\., pre\-trained language models, image generators, or scraped datasets\)?
53. Answer:\[N/A\]
54. Justification: No such assets released\.
55. Guidelines: - •The answer\[N/A\]means that the paper poses no such risks\. - •Released models that have a high risk for misuse or dual\-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters\. - •Datasets that have been scraped from the Internet could pose safety risks\. The authors should describe how they avoided releasing unsafe images\. - •We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort\.
56. 12\.Licenses for existing assets
57. Question: Are the creators or original owners of assets \(e\.g\., code, data, models\), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
58. Answer:\[Yes\]
59. Justification: All assets public and cited; UCI CC BY 4\.0, GPT\-2 MIT, Qwen2\.5 Apache 2\.0, WikiText\-2 CC BY\-SA 3\.0\.
60. Guidelines: - •The answer\[N/A\]means that the paper does not use existing assets\. - •The authors should cite the original paper that produced the code package or dataset\. - •The authors should state which version of the asset is used and, if possible, include a URL\. - •The name of the license \(e\.g\., CC\-BY 4\.0\) should be included for each asset\. - •For scraped data from a particular source \(e\.g\., website\), the copyright and terms of service of that source should be provided\. - •If assets are released, the license, copyright information, and terms of use in the package should be provided\. For popular datasets,[paperswithcode\.com/datasets](https://paperswithcode.com/datasets)has curated licenses for some datasets\. Their licensing guide can help determine the license of a dataset\. - •For existing datasets that are re\-packaged, both the original license and the license of the derived asset \(if it has changed\) should be provided\. - •If this information is not available online, the authors are encouraged to reach out to the asset’s creators\.
61. 13\.New assets
62. Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
63. Answer:\[N/A\]
64. Justification: None released\.
65. Guidelines: - •The answer\[N/A\]means that the paper does not release new assets\. - •Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates\. This includes details about training, license, limitations, etc\. - •The paper should discuss whether and how consent was obtained from people whose asset is used\. - •At submission time, remember to anonymize your assets \(if applicable\)\. You can either create an anonymized URL or include an anonymized zip file\.
66. 14\.Crowdsourcing and research with human subjects
67. Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation \(if any\)?
68. Answer:\[N/A\]
69. Justification: None\.
70. Guidelines: - •The answer\[N/A\]means that the paper does not involve crowdsourcing nor research with human subjects\. - •Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper\. - •According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector\.
71. 15\.Institutional review board \(IRB\) approvals or equivalent for research with human subjects
72. Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board \(IRB\) approvals \(or an equivalent approval/review based on the requirements of your country or institution\) were obtained?
73. Answer:\[N/A\]
74. Justification: Not applicable\.
75. Guidelines: - •The answer\[N/A\]means that the paper does not involve crowdsourcing nor research with human subjects\. - •Depending on the country in which research is conducted, IRB approval \(or equivalent\) may be required for any human subjects research\. If you obtained IRB approval, you should clearly state this in the paper\. - •We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution\. - •For initial submissions, do not include any information that would break anonymity \(if applicable\), such as the institution conducting the review\.
76. 16\.Declaration of LLM usage
77. Question: Does the paper describe the usage of LLMs if it is an important, original, or non\-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does*not*impact the core methodology, scientific rigor, or originality of the research, declaration is not required\.
78. Answer:\[N/A\]
79. Justification: LLMs are study subjects only\.
80. Guidelines: - •The answer\[N/A\]means that the core method development in this research does not involve LLMs as any important, original, or non\-standard components\. - •Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described\.

Similar Articles

Low-rank Distributional Matrix Completion

arXiv cs.LG

This paper introduces a distributional generalization of matrix completion where each entry is a probability distribution rather than a scalar, using kernel mean embeddings and Tucker rank to capture low-rank structure. The authors propose a novel estimator with non-asymptotic error bounds and demonstrate effectiveness on synthetic and real-world data.

Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits

arXiv cs.LG

This paper introduces Lexi-LowGLM, an efficient algorithm for generalized low-rank matrix bandits with multiple prioritized objectives, using online Newton updates to reduce computational complexity and achieve regret bounds depending on effective low-rank dimensions.