Active Seriation: Efficient Ordering Recovery with Statistical Guarantees
Authors: James Cheshire
Yann Issartel
Venue: NeurIPS 2025 poster ()
Keywords: Seriation
Sorting
Active learning
Ranking
Primary area: general_machine_learning

Abstract: Active seriation aims at recovering an unknown ordering of $n$ items by adaptively querying pairwise similarities. 
The observations are noisy measurements of entries of an underlying $n \times n$ permuted Robinson matrix, whose permutation encodes the latent ordering. The framework allows the algorithm to start with partial information on the latent ordering, including seriation from scratch as a special case. We propose an active seriation algorithm that provably recovers the latent ordering with high probability. Under a uniform separation condition on the similarity matrix, optimal performance guarantees are established, both in terms of the probability of error and the number of observations required for successful recovery.

Active Seriation: Efficient Ordering Recovery with Statistical Guarantees
James Cheshire
Yann Issartel
LTCI, Télécom Paris, Institut Polytechnique de Paris
Abstract
Active seriation aims at recovering an unknown ordering of n items by adaptively querying pairwise similarities. The observations are noisy measurements of entries an underlying n n permuted Robinson matrix, whose permutation encodes the latent ordering. The framework allows the algorithm to start with partial information on the latent ordering, including seriation from scratch as a special case. We propose active seriation algorithm that provably recovers the latent ordering with high probability. Under a uniform separation condition on the similarity matrix, optimal performance guarantees established, both in terms the probability of error and the number of observations required for successful recovery.
Introduction
The seriation problem involves ordering items based on noisy measurements of pairwise similarities. This reordering problem originates in archaeology, where was used for the chronological dating of graves [Robinson, 1951]. More recently, it has found applications in data science across various domains, including envelope reduction for sparse matrices [Barnard et al., 1995). read alignment in de novo sequencing [Garriga al., 2011 Recanati al., 2017). time synchronization in distributed networks [Elson et al., 2004 Giridhar and Kumar, 2006), and interval graph identification [Fulkerson and Gross, 1965).
In many of these settings, pairwise measurements can be made in an adaptive fashion, leveraging information from previously chosen pairs. Motivated by these applications. study the problem of recovering an accurate item ordering from a sequence of actively selected pairwise measurements.
The classical seriation problem has attracted substantial attention in the theoretical literature [Atkins cet al., 1998 Fogel et al., 2013 Janssen and Smith, 2022 Giraud al., 2023 Cai and Ma, 2023 Issartel al., 2024] In this line of work, the learner receives single batch of observations, whereas in the active setting considered in this paper, the algorithm can adaptively select which pairs to observe; to the best of our knowledge, this active seriation setting has not been previously analyzed.
Related problems include adaptive ranking and sorting under noisy observations [Jamieson and Nowak, 2011 Braverman and Mossel, 2009 Heckel et al., 2019). However, these problems typically rely on pairwise comparisons (c.g., is item preferred to item j?? to infer total order. contrast, seriation builds pairwise similarity scores that encode proximity in the underlying ordering. This distinction leads to different statistical and algorithmic challenges.
Problem setup. In the seriation paradigm, we assume the existence of an unknown symmetric matrix M representing pairwise similarities between a collection of items. The matrix A is structured so that the similarities M, are correlated with an unknown underlying ordering of the items, which is encoded by permutation π (œ),-.. ,,,,) of [n). The similarity Mi between
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

items i and j tends to be large when their positions n; and πy are close, and small when they are far apart. To model this structure formally, the literature assumes that M is Robinson matrix whose rows and columns have been permuted by the latent permutation [Fogel et al., 2013 Recanati et al.; 2018 Janssen and Smith, 2022, Giraud et al., 2023]; see Section 2.1 for a formal presentation.
We consider a general framework in which the algorithm may be initialized with partial information on the latent ordering π. Specifically,, it can be provided with correct ordering of subset of the items that is consistent with x. This setting includes seriation from scratch as the special case where no such information is given initially.
The algorithm adaptively selects pairs of items and observes noisy measurements of their similarities. A total of T such observations are collected, and the noise is controlled by an unknown parameter The goal is to recover the latent ordering π of the n items from these 'T' observations. We evaluate the performance of estimator by its probability of failing to identify л. See Section for details.
Contribution. We introduce Active Seriation by Iterative Insertion (ASII), an active procedure for estimating the ordering æ. Unlike most existing seriation methods, which are non-active, ASII is remarkably simple, runs in polynomial time, and yet achieves optimality guarantees both in terms of error probability and sample complexity.
In the general framework considered in this paper, we analyze the performance of ASII and es- tablish exponential upper bounds on its probability of error. In the special case of seriation from scratch, where no prior ordering information is available, we provide a sharp characterization of the statistical difficulty of ordering recovery over the class of similarity matrices with minimal gap A between adjacent coefficients. This difficulty is governed by the signal-ter signal-to-noise ratio (SNR) of order (OT n)., which can be interpreted as the number of observations per item, T/n, multiplied by the SNR per observation, (A/o)². Our results identify a phase transition at the critical level SNR x In n: below this threshold, ordering recovery is iofommttion-thhortiiiie achieves recovery with a probability of error that decays exponentially fast with the SNR. Moreover, we show that no algorithm can achieve a faster decay rate, establishing optimality this regime.
impossible, while above it, ASII
Finally, we illustrate the performance of ASII through numerical experiments and a real-data applica- tion.
1.1 Related work
Classical seriation. The non-active seriation problem was first addressed by [Atkins et al., 1998 in the noiseless setting, using a spectral algorithm. Subsequent works analyzed this approach under noise [Fogel et al., 2013, Giraud et al., 2023 Natik and Smith, 2021]. typically relying on strong spectral assumptions to establish statistical guarantees. More recent contributions proposed alternative polynomial time algorithms with guarantees under different and sometimes weaker assumptions [Janssen and Smith, 2022, Giraud et al., 2023] Cai and Ma, 2023 Issartel et al.. 2024). Our analysis falls within the line of work on Lipschitz-type assumptions GGraud et al., 2023 Issartel eet al., 2024), as our A A-separation condition can be viewed as a lower Lipschitz requirement.
Statistical-compe compluatooooottt gaps. Prior studies have suggested
gaps in the
non-active seriation problem |Giraud et al., 2023 Cai and Ma, 2023 Berenfeld et al., 2024], where known polynomial-tmme algorithms fall short of achieving statistically optimal rates under certain noise regimes or structural assumptions. While some of these gaps have recently been closed [Issartel et al., 2024], the resulting algorithms tend to be complex and may not scale well in practice. In contrast, in the active setting, we show that a simple and computationally efficient algorithm achieves statistically optimal performance.
Bandit models. In classical multi-armed bandits (MAB) [Bubeck and Cesa- Bianchi, 2012), each arm yields independent rewards, and the goal is to maximize cumulative reward identily the best arm. In contrast, in active seriation, each query (i.j) measures the similarity between two interdependent items, and all measurements must be consistent with single latent ordering. This interdependence prevents a direct application of standard MAB algorithms such as UCB or Thompson Sampling, which treat arms as independent and do not exploit structural relationships between them.
Algorithmically, our approach is related to noisy binary search and thresholding bandits [Feige et al., 1994 Karp and Kleinberg, 2007 Ben-Or and Hassidim, 2008 Nowak, 2009, Emamjomeh

---

Zadeh et al., 2016 Cheshire et al., 2020, Cheshire et al., 202T], which rely on adaptive querying under uncertainty. However, these methods operate on low-dimensional parametric models, whereas seriation involves combinatorial ordering that must remain globally consistent across item pairs.
Active ranking. A related but distinct problem is active ranking (Heckel al., 2019 Shah and Wainwright, 2017], where a learner infers total order based on noisy pairwise comparisons or latent score estimates. Extensions include Borda, expert, and bipartite ranking [Saad al., 2023 Cheshire et al., 2023]. These methods typically assume that each item is associated with an intrinsic scalar score, and that pairwise feedback expresses directional preference between items. In contrast, seriation relies on pairwise similarity information, which encodes proximity rather than preference. Recovering the latent ordering therefore requires global consistency among pairwise similarities, making the problem more constrained and structurally different from standard ranking tasks.
2 Active Seriation: Problem Setup
2.1 Similarity matrix and ordering
Given collection of items [ni] ;= {I,..... m. let M = -Mij]isiss denote the (unknown) similarity matrix, where the coefficient Miy E measures the similarity between items and j. Our structural assumption on M is related to the class of Robinson matrices, introduced below.
Definition 2.1. A matrix R Ruxa is called Robinson matrix (or R-matrix) it is symmetric and
Rig > RG-15 and Big Ris+1,
for all i S the upper triangle of R.
The entries of Robinson matrix decrease one moves away from the (main) diagonal (see Figure left). In other words, each row / column is unimodal and attains its maximum on the diagonal. Following [Atkins al., 1998), matrix said to be pre-R it it can be transformed into an R-matrix by simul- taneously permuting its rows and columns (Figure right). In this paper, we assume the similarity matrix M is pre-R, i.e.,
M Rr := (RT,,
(1)
for some R-matrix R and some permutation (TI...., ,T) ) of [n]. The permutation æ represents the latent ordering of the items.
Figure R-matrix & permuted version.
In (T). the similarities M,j reflect the ordering æ as follows: Mi tends be larger when the positions π, and x, close together, and smaller when they are far apart.
Remark 1. The items have exactly orderings: if is ordering, then the reverse permuta- tion Te, defined by कश = a n ns, is also an ordering. Indeed, if M = Ra. then M Ry where Rees is obtained by reversing the rows and columns of R. In the sequel, we refer either of these two orderings as the latent ordering.
2.2 Active observation model
In the active seriation problem, the algorithm sequentially queries T pairs of items and receives noisy observations of their pairwise similarities, encoded by the unknown similarity matrix M in (T) The goal is to recover the latent ordering of the items from these noisy observations.
Initially, the algorithm is provided with partial information on the latent ordering æ: receives as input correct ordering म of the items (1...,, , nj. corresponding to the restriction of to this subset. This framework interpolates between online seriation (ń 1), where single item inserted into existing ordering, and scriation from scratch (ñ n)).

---

More precisely. for some ń E [n]. the algorithm is given permutation म = (f1....,,f An-R) of [n ń satisfying"
V4 E [n n].
<<<g n
(2)
In other words, the input permutation # preserves the relative order of the items {1, (1,...,7. n n) in the latent ordering π.
At each round t = I,.... T, the algorithm selects pair (4) with & * jt. possibly depending the outcomes of previous queries. It then receives a noisy observation of the similarity Mijj given by a Suuu-aassiian random variable" with mean Maj.. This sub-Gaussian setting covers standard observation models, including Gaussian noise and bounded random variables.
After 7 queries, the algorithm outputs a permutation of [n] as estimate of the latent ordering m
2.3 Error probability and minimal gap
The algorithm is considered successful if á recovers either и its reverse g both permutations are valid orderings (Remark []. The probability of error is thus defined as
PM.T == M.T { A т and *
(3)
where the probability is over the randomness in the T observations collected on the matrix M.
A key quantity in our analysis of (3) is the separation between consecutive entries in the underlying R-matrix. Specifically, for any pre-R matrix M as in (T). we define its minimal gap
A M
min KKKjER-1
{(R Ra-15)) A (Ri. Raj+1))
where A denotes the minimum. The quantity (4) measures the smallest difference between neighbor- ing entries in the R-matrix associated with M. Note that AM > 0 (by Definition 2.1 and that AM is well-defined even though M can be associated with different R-matrices (Remark
Some of our guarantees are stated over classes of matrices with a prescribed minimal gap. Namely, for any A > 0, we introduce
Ma == (M E RRxx; M is pre-R, and Aus 2 A},
(5)
as the set of pre-R matrices with minimal gap at least A.
To simplify the presentation of our findings, we focus on the challenging regime where
11, (o 0).
(6)
i.e. the gegnal-to-noise ratio per observation is at most 1. This excludes mildly stochastic regimes where the problem has essentially the same difficulty as in the noiseless case.
3 Seriation procedure
ASII (Active Seriation by Iterative Insertion) reconstructs the underlying ordering by iteratively inserting each new item into an already ordered list. At iteration k; given current estimated ordering ((k-1) of the items (I...., is - 1}. the algorithm inserts item k at its correct position to form an updated ordering (40) of (1, .4....,k k). This process is repeated until the full ordering of all items is obtained. The ulgorithm is fully data-driven: it takes as input only the sampling budget T; it does not rely on any knowledge of the noise parameter a, the similarity matrix M, nor its minimal gap AM.
To perform this insertion efficiently, two key subroutines are used:
In full generality, condition 2 should be assumed to hold either for the latent ordering or for its reverse "<; for simplicity of exposition, state it in terms of n, this distinction plays no essential role in the sequel.
A random variable X is said o-sub- Gaussian if exx((xX)] S exp ".""" for E
This lack of identifiability between N and rey persists in the seriation from scratch case, since condition 2 is vacuous.

---

(i) Local comparison rule. To decide where to insert k. the algorithm must compare its position relative to items already ordered ((k-1), This is achieved through the subroutine TEST, which determines whether & lies to the left, in the middle, or to the right of two reference items (I.r).
(ii) Efficient insertion strategy. To minimize the number of comparisons, the algorithm performs binary search over the current ordering, where each comparison is made via TEST. Because these tests are noisy, the procedure further stabilized through backtracking mechanism.
(i) Local comparison rule. Given two items (l.r) such that कं < Tr. the goal to determine whether k lies to the left, in the middle, or to the right of (1,r) ) in the unknown ordering x. Formally, this means deciding whether n < Ti, or TT E (MT, Tr), or Tek > ny, respectively.
The subroutine TEST is based on the following property of Robinson matrices: and r, its similarity to both / and tends to be higher than the similarity between / and themselves. Accordingly, TEST compares the three empirical similarities Ma. Mar. and Mi., and identifies the smallest one the pair of items that are farthest apart. For example, if Mr is the smallest, then & lies in the middle. The pseudocode of TEST is provided in Appendix B.
when k lies between /
Each call to the subroutine TEST is performed with a limited sampling budget, typically of order ( log, k)), in order to be sampling-efficient. With such a budget, individual tests are not designed to be reliable with high probability. Higher reliability is required only at few critical steps of ASII (e.g., during the initialization of the binary search), where a larger budget of order O(T /n) is allocated to ensure correctness with high probability. This design trades local test accuracy for global budget efficiency; occasional incorrect tests are later corrected by a backtracking mechanism.
(ii) Efficient insertion strategy. The idea of incorporating backtracking into a noisy search has appeared in several studies, e.g., [Feige et al., 1994 Ben-Or and Hassidim, 2008 [Emamjomeh-Zadel ctt al., 2016 Cheshire et al., 2021]. J. Here, we adopt this general principle to design a robust insertion mechanism that remains reliable under noisy relational feedback.
At this stage of the algorithm, the items (1,...,, A t have already been placed into an estimated ordering (k-11) (#) (#( = constructed so far. To insert the new item k into this list, we use the subroutine BINARY & BACKTRACKING SEARCH BBS). which determines the relative position of k within the current ordering ( The search proceeds by repeatedly using the subroutine TEST to decide whether & lies in the left or right half of candidate interval, thereby narrowing down the possible insertion range.
Because the outcomes of TEST are noisy, even a single incorrect decision can misguide the search and lead an erroneous final placement. A naive fix would be to allocate many samples per TEST to ensure highly reliable outcomes, but this would increase the sample complexity and undermine the benefit of active sampling. Instead, BBS uses a small number of samples per TEST, of order k)), just enough ensure constant success probability (e.g., around 3/4). Backtracking then acts as a corrective mechanism that prevents local errors from propagating irreversibly.
(f log,
just
The backtracking mechanism operates as follows: the algorithm keeps track of previously explored intervals and performs sanity checks each step to detect inconsistencies in the search path. When an inconsistency is detected, it backtracks to an earlier interval and resumes the search. This prevents local mistakes from propagating irreversibly. Theoretical analysis shows that, as long as the number of correct local decisions outweighs the number of incorrect ones an event that occurs with high probability under the assumption M E MM the final insertion position is accurate.
Hence, the backtracking mechanism allows the algorithm to detect and correct occasional local errors. As a result, we can use only a small number of samples per call to TEST, while still ensuring correct insertions at the global level. The ASII procedure thus provides both sampling efficiency and robustness despite noisy observations. A pseudocode of this procedure is given in Appendix B.
4 Performance analysis
We study the fundamental limits of ordering recovery active seriation, deriving information- thcoretic lower bounds and algorithmic upper bounds on the error probability defined in (
5

---

4.1 Upper bounds for ASII
We analyze the performance of [ when the algorithm is provided with permutation म of the items f1....,7 ? fit, consistent with the latent ordering π of the items. The following theorem gives an upper bound on the error probability of ASII for recovering æ. proof is in Appendix C.
Theorem 4.1 (Upper bound with partial information). There exists absolute constant > 0 such that the following holds. Let n 2 and [nl, and assume that the input permutation of [n 7 satisfies 2 Let (A, T,) be such that condition (6) holds and
AT
Co lnn..
If M. E Ma then the enror probability of ASII satisfie
T
PM.T S exp
800
Once the SNR, (o))( exceeds logarithmic threshold in n, the error probability of ASII decays exponentially fast with the SNR. We emphasize that ASII achieves this performance without requiring any knowledge of the model parameters (A,
Beyond this uniform guarantee over the class Ma. the performance of ASII admits finer, instance- dependent characterization. The same bound holds with A replaced by the true minimal gap AM of the underlying matrix M (defined in (4). Precisely, for the instance-dependee A T/ (ooT((" ni. the bound becomes PM.T I exp(- (rp(-SNRR//800) whenever SNRM 2 Co nn
SNRM
4.2 Minimax optimal rates for seriation from scratch
We establish matching information-theoree (ñ = 11), where no prior ordering information is available. This analysis identifies two regimes, depending on whether the SNR is below or above a critical threshold.
lower bounds in the case of active seriation from scratch
A'T < Inn, algorithm can recover 4.2.1 Impossibility regime. When the SNR satisfies a the ordering with vanishing error probability. The following theorem formalizes this impossibility, establishing constant lower bound on the error probability 3
for any algorithm in this regime.
Theorem 4.2 (Impossibility regime). There exists an absolute constant Cj holds. Let n 2 9 and (A, o, T') be such that
such that the following
A oan
< Ci Inn.
Then, for any algorithm A, there exists matrix M E MA such that the error probability of A satisfies PMrT 1/2.
As expected, the impossibility regime is more pronounced when the minimal gap A small or when the noise parameter is large. To escape this regime, the number of observations per item, T T/n, must grow at least quadratically with a A (up to logarithmic factors). The proof is in Appendix F.
4.2.2 Recovery regime. In the complementary regime where the SNR satisfies ATT 2 In exact n" recovery becomes achievable. The ASII algorithm attains an exponentially small error probability, and this rate is minimax optimal over the class MA. up to absolute constants in the exponent.
Specifically, the upper bound in this regime follows directly from Theorem by taking n.
ATT
Co Inn,
(8)
2
where co is the same absolute constant as in Theorem 4.1
then for any M Ma.
2T
PM.T S exp
800
o²n
Conversely, the next theorem gives a matching lower bound, showing that no algorithm can achieve faster error decay than exponential in the SNR. Its proof is in Appendix F.

---

Theorem 4.3 (Recovery regime), Let n 2 4 and (A. be such that condition g holds. Then, for any algorithm there exists M MM such that the error probability of A satisfies
T O
PMT 2 exp
Together, Theorem 4.2 and 4.3 delineate the statistical landscape of active seriation from scratch, establishing a sharp phase transition between impossibility and recovery at the critical SNR level Inn.
A
4.2.3 Discussion: intrinsic hardness and invariance to model assumptions. Both lower bounds (Theorems 4.2 and 4.3) are established under Gaussian noise model with centered, homoscedastic entries of variance o², whereas our upper bound is proved in the more general sub-Gaussian setting allowing heterogeneous noise levels. Since these bounds match, potential heterogeneity in the noise variances does not affect the minimax rates (at least in terms of exponential decay in SNR).
Moreover, the lower bounds derived for the simple, affine, Toeplitz matrix
Ray (n 1----h -in-li- 1n--i--j144 jl)
yet the attainable rates coincide with those obtained under the general assumption M MMs- Hence, allowing heterogeneous, non-Toeplitz matrices comes at no statistical cost. This may appear surprising, since the Toeplitz assumption is classical in batch seriation (e.g.. (Cai and Ma, 2023]).
Even when the latent matrix is fully known, as in the one-parameter family (9) with known param- eter A, the attainable rates remain unchanged. This indicates that the hardness of active seriation arises from the combinatorial nature of the latent ordering, rather than from uncertainty about the latent matrix.
4.3 Sample complexity for high probability recovery
We summarize our results in terms of sample complexity, defined as the number of observations required achieve exact recovery with probability least 1 1/n².. Combining the impossibility result of Theorem (42 with the recovery guarantee of Theorem 4.1 we obtain a sharp characterization of the sample complexity in the from-scratch case (ñi n)).
Corollary 4.4 (Sample complexity). Let and [n:] and assume that the input permutation т (n n] satisfies (2). Then ASII achieves exact recovery with probability at least 1 - 1/n², if
Ninn 2
T>
In particular, in the from-scratch case = n, the minimax- opttimal number of observations required for exact recovery with probability at least 1 - 1/n2, satisfies T > a2aln
Thus, in active seriation from scratch, ASII attains the minimax- which depends transparently on the problem parameters (A, n). Crucially, ASII can achieve high probability recovery with a number of queries T < n²,, highlighting a substantial advantage over the classical batch setting where all n² pairwise similarities are observed.
sample complexity T**
4.4 Extension beyond uniform separation
Our analysis so far has focused on exact recovery under the uniform separation assumption M E MMs While this assumption is natural for characterizing the fundamental limits of exact recovery, it is also idealized: in practice, some items may be nearly indistinguishable in terms of their pairwise similarities, making their relative ordering statistically impossible to recover.
We therefore consider arbitrary pre-R matrices M, as defined in model ① without any separation assumption. Even in this setting, direct extension of the ASII procedure continues to provide meaningful and statistically optimal guarantees: it correctly recovers the relative ordering of items that are sufficiently well separated.

---

Algorithmic extension of ASII The procedure follows the same iterative insertion scheme as our ASII algorithm, but takes as input a tolerance parameter > 0, which sets the resolution at which the algorithm attempts to distinguish items. Now, when ASII identifies a candidate insertion location for new item in the current ordering, this location is checked through an additional high-probabiliyy validation test at precision A/2. The item is inserted if the test succeeds; otherwise it is discarded and does not appear in the final output.
As consequence, this extension no longer outputs a permutation ğ of all items. Instead, it returns subset S C [n] together with a permutation सs of S, which serves as an estimator of the relative ordering of the items in S. The corresponding pseudo-code is deferred to the appendix.
Robustness beyond uniform separation. We now state robustness guarantees for the extension described above. To this end, we introduce a notion of A-maximality, inspired by the class MA defined in ( Specifically, for any subset S [n]] we write Ms for the submatrix of the similarity matrix M restricted to the items S. By a slight abuse of notation, we write Mg E MM to mean that Ms is pre-R and satisfies AMs A, where AMs is the minimal gap defined in (4).
Definition 4.5 (A-maximal subset). For any A > 0, subset S C [n]] is said to be A-maximal if Ms Ma and MSu(R} M& for all k [n] S.
Intuitively, a A-maximal subset cannot enlarged without adding items that are too similar (within A) to those already in S.
We now show that the guarantee of Theorem 4.1 can be extended beyond the uniformly separated setting, to any pre-R matrix M, by operating at user-chosen resolution level Å. The conditions on the parameters are the same in Theorem 4.1 with A replaced by the input parameter Å.
Theorem 4.6 (Guarantees beyond uniform separation). There exist absolute constants c. c' >> O such that the following holds. Let n 2 A S, T) be such that Á/o < 1 and extension of ASII outputs, with probability at least 1 1- -eeppp== A )
[n] and the input permutation π of ñl] satisfy (2). Let
a 2 clnn. Then, for any pre-R matrix M E R the
A-maximal subset S C [n]
the sense of Definition 4.5 and correct ordering & of the items S.
Empirical results
We illustrate the behavior of ASII through numerical experiments and real-data example.
Numerical simulations. We assess the empirical behavior of ASII on synthetic data and compare it to three benchmark methods: (i) the batch seriation algorithm ADAPTIVE SAMPLING [Cai and Ma 2023], (ii) the batch SPECTRAL SERIATION [Atkins al., 1998), and (iii) an active, naive insertion variant of ASII without backtracking. Since, to the best of our knowledge, the literature does not contain seriation methods designed for the active setting, these three procedures serve as reference points. All methods are evaluated under identical sampling budgets on four representative scenarios, covering both homogeneous (Toeplitz) and nonhhomogeneous noeplit.,,,,,). Robinson matrices. Full experimental details are deferred to Appendix
Figure 2 provides visual illustration of the four scenarios considered. Scenario (1) corresponds to a Toeplitz Robinson structure, while the remaining scenarios (2-3-4) depart from the Toeplitz assumption and exhibit more heterogeneous Robinson geometries.
5
5
Figure 2: Robinson matrices for scenarios (1)-(4), from left right.
Figure reports the empirical probability of error of methods as function of the minimal gap A. Across all four scenarios, ASII consistently outperforms the naive iterative insertion procedure,
8

---

highlighting the benefits of its backtracking corrections; these gains are consistent with the logarithmii improvement predicted by our theoretical analysis.
As expected, in scenario (I), where the underlying matrix is Toeplitz, ASII performs below the two batch methods, which are known perform well in this setting. This behavior can be attributed to the fact that ASII is designed for general Robinson matrices and does not exploit Toeplitz regularity (unlike its competitors); moreover, its sampling budget distributed across multiple binary-search iterations, which can be less efficient than batch sampling. This does not contradict our theoretical guarantees, which establish rates up to absolute constants that are not characterized by the analysis and may be large for active, iterative procedures such as ASII.
In contrast, in the heterogeneous (non-Toeplitz scenarios (2-3-4), ASII remains consistently accurate, whereas both batch methods exhibit unstable behavior and may fail entirely in some cases.
Overall, these experiments illustrate that ASII maintains stable empirical performance across various scenarios, and can be particularly effective on matrices with localized variations (scenarios 2-3-4), where batch methods tend to struggle.
Figure 3: Empirical error probabilities for ASII and three benchmark methods as the parameter A varies. Scenarios (1-2-3-4) are displayed from left to right and top to bottom. Each experiment uses 10 items and T = 10,000 observations. For each value of A, 100 Monte Carlo runs are split into 10 equal groups; error bars show the 0.1 and 0.9 quantiles of the empirical error across groups
Application to real data. We further assess the robustness of ASII on real single-cell RNA sequencing data (human primordial germ cells, from [Guo et al., 2013), previously analyzed by CCa and Ma. 2023]). Although such biological data depart substantially from the idcalized Robinson models assumed in our theory, ASII still produces a meaningful reordering of the empirical similarity matrix, revealing coherent developmental trajectories among cells. This example highlights the potential practical relevance of the proposed approach beyond the stylized assumptions of our theoretical framework. Full experimental details are provided in Appendix H
Figure 4: Similarity matrix of a single-cell RNA-seq dataset before and after reordering by ASII.

---

6
Discussion
This work introduces an active-learning formulation of the seriation problem, together with sharp theoretical guarantees and a simple polynomial-time algorithm. We characterize phase transition in sample complexity governed by the SNR = 2²T/(a"" (a'n): recovery is impossible when SNR 2 In n, while ASSI] achieves near optimal performances once this threshold is exceeded. Our analysis highlights how adaptive sampling combined with corrective backtracking can substantially improve statistical efficiency. We now turn to a discussion of several complementary aspects of the problem.
Noise regimes. Our analysis focused on the stochastic regime where the per-observation signal-to- noise ratio A/o is at most 1, which captures the most challenging setting for active seriation. The results, however, extend naturally to less noisy regimes (A/a > 1): in that case, accurate recovery requires only T Z In queries, reflecting the intrinsic O(n In n) cost of performing adaptive binary insertions. Further details are provided in Appendix A.I
Gain from active learning. Our active framework enables recovery of the underlying ordering without observing the entire similarity matrix. Whereas batch approaches require O(n²) observations, our active algorithm ASII succeeds with only T 2 (a/A)²n In n samples. This corresponds fraction Inn of the full matrix and yields substantial reduction in sample complexity, provided that A/a remains bounded away from zero. This gain arises from the ability of adaptive sampling to draw information from a well-chosen, small subset of pairwise similarities, from which the entire matrix can be reordered, achieving strong statistical guarantees under limited sampling budgets.
(A/a)²n
In certain scenarios, when differences between candidate orderings are highly localized, our active algorithm can succeed under weaker signal conditions than some batch methods, see Appendix A.2 for a detailed comparative example.
Fixed-budget formulations. Throughout this work, we focused on the fixed-budget setting, where the total number of samples T' is fixed in advance and the objective is to minimize the error probability within this budget. This way, the algorithm does not require prior knowledge of the noise parameter a, nor of the minimal signal gap Au of the latent matrix M; it simply allocates the available budget T across tests. Yet, its performance depends on the unknown a and AM through the signal-to-note ratio SNR = ( n)) which determines the achievable accuracy.
Potential applications. Seriation techniques are broadly relevant in domains where pairwise simi- larity information reflects a latent one-dimensional structure. Examples include genomic sequence alignment, where seriation helps reorder genetic fragments by similarity, and recommendation sys- tems, where item-item similarity matrices can reveal latent preference orderings. We also illustrated, on real single-cell RNA sequencing data, that ASII can recover biologically meaningful trajectories despite the data departing strongly from theoretical model. These settings often involve noisy or costly pairwise measurements, for which active scriation provides an appealing alternative to batch reordering methods.
Future directions. We also proposed an extension to settings where the uniform separation as- sumption does not hold, in which (STl outputs an ordering of a subset of well-separated items. How to exploit more global ordering structure beyond this setting is an important open question.
Another natural extension is to study the exeedcoofidence setting, where the algorithm must adaptively decide when to stop sampling in order to achieve a prescribed confidence level. Such a formulation would typically require variance-aware sampling policies and data-driven stopping rules, possibly involving online estimation of a. Developing such an adaptive, fixed-confidence version of ASI is an interesting avenue for future work.
Acknowledgements
The work of J. Cheshire is supported by the FMJH, ANR-22-EXES--001.
10

---

References
[Atkins et al., 1998] Atkins, J. E., Boman, G., and Hendrickson, B. (1998). A spectral algorithm for seriation and the consecutive ones problem. SIAM Journal on Computing, 28(1):297-310.
[Barnard et al.. 1995] Barnard, S. T., Pothen, A., and Simon, H. (1995). A spectral algorithm for envelope reduction of sparse matrices. Numerical linear algebra with applications, 2(4)3317-334.
[Ben-Or, 1983] Ben-Or, M. (1983). Lower bounds for algebraic computation trees. Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC '83.
[Ben-Or and Hassidim, 2008] Ben-Or, M. and Hassidim, A. (2008). The bayesian leamnr is optimal for noisy binary search (and pretty good for quantum well). In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 221 2-30. IEEE.
[Berenfeld et al., 2024] Berenfeld, C., Carpentier, A., and Verzelen, N. (2024). Seriation of t }e plitz and latent position matrices: optimal rates and computational trade-offs. arXiv preprint
arXiv:2408.100 10004.
[Braverman and Mossel, 2009] Braverman, M. and Mossel, E. (2009). Sorting from noisy informa- tion. arXiv preprint arXiv:0910.1199
[Bubeck and
2012] Bubeck, S. and Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armedbandii problems.
[Cai and Ma, 2023] Cai, T. T. and Ma, R. (2023). Matrix reordering for noisy disordered matrices:
Optimality and computationally efficient algorithms. IEEE transactions on information theory, 70(1):509-531.
[Cheshire and Clémençon, 2025] Cheshire, J. and Clémençon, S. (2025). Active bipartite ranking with smooth posterior distributions. In The 28th International Conference on Artificial Intelligence and Statistics.
[Cheshire et al., 2023] Cheshire, J., Laurent, V., and Clémençon, S. (2023). Active bipartite ranking. In Thirty-seventh Conference Neural Information Processing Systems.
[Cheshire et al., 2020] Cheshire, J., Ménard, P., and Carpentier, A. (2020). The influence of shape constraints on the thresholding bandit problem. In Conference on Learning Theory, pages 1228- 1275. PMLR.
[Cheshire et al., 2021] Cheshire, J., Ménard, P., and Carpentier, A. (2021). Problem dependent view on structured thresholding bandit problems. In International Conference on Machine Learning, pages 1846-1854 PMLR.
[Cormen et al., 2009] Cormen, T. H. Leiserson, C. E., Rivest, R. L., and Stein, C. (2009).
Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition.
[Elson et al., 2004] Elson, J., Karp, R. M., Papadimitriou, C. H., and Shenker, S. (2004). Global synchronization in sensornets. In Farach-Colton, M., editor, LATIN 2004: Theoretical Informatics, pages 609-624, Berlin, Heidelberg. Springer Berlin Heidelberg.
Sanamjomeh-Zadeh et al., 2016] Emamjomeh-Zadch,, E., Kempe, D., and Singhal, V. (2016). De- terministic and probabilistic binary search in graphs. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 519-532. ACM.
[Falahatgar et al., 2017] Falahatgar, M., Orlitsky, A., Pichapati, V., and Suresh, A. T. (2017). Max- imum selection and ranking under noisy comparisons. In Proceedings of the 34th International Conference on Machine Learning.
[Feige et al., 1994] Feige, U., Raghavan, P., Peleg, D., and Upfal, E. (1994). Computing with noisy information. SIAM Journal on Computing, 23(5):1001-101
[Fogel et al., 2013] Fogel, F,, Jenatton, R., Bach, F., and d' Aspremont, A. (2013). Convex relaxations for permutation problems. In Advances in Neural Information Processing Systems, pages 1016- 1024.
[Fulkerson and Gross, 1965] Fulkerson, D. and Gross, O. (1965). Incidence matrices and interval graphs. Pacific journal of mathematics. 15(3):835-855,
[Garivier et al., 2019] Garivier, A., Ménard, P., and Stoltz, G. (2019). Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2):377-399
11

---

[Garriga et al., 2011] Garriga, G. C., Junttila, E., and Mannila, H. (2011). Banded structure in binary matrices. Knowledge and information systems, 28(1):197-226.
[Gerchinovitz al., 2020] Gerchinovitz, S., Ménard, P., and Stoltz, G. (2020). Fano's inequality for random variables. Statistical Science, 35(2):178-25
[Giraud et al., 2023] Giraud, C., Issartel, Y., and Verzelen, N. (2023). Localization in 1d non-
parametrie latent space models from pairwise affinities. Electronic Journal of Statisties,
17(1):1587-166..
[Giridhar and Kumar, 2006] Giridhar, A. and Kumar, R. (2006). Distributed clock synchronization over wireless networks: Algorithms and analysis. In Proceedings of the 45th IEEE Conference on Decision and Control, pages 1920.
[Gu and Xu, 2023] Gu, Y. and Xu, Y. (2023). Optimal bounds for noisy sorting. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1502-1515.
[Guo et al., 2015] Guo, F., Yan, L., Guo, H., Li, L., Hu, B., Zhao, Y., Yong, J.. Hu, Y., Wang, X.,
Wei, Y., et al. (2015). The transcriptome and dna methylome landscapes of human primordial germ cells. Cell, (61(6):1437-1452
(Hao et al., 2023] Hao, Y., Stuart, T., Kowalski, M. H., Choudhary, S., Hoffman, P., Hartman, A., Srivastava, A., Molla, G., Madad, S., Fernandez-Grranda, C., and Satija, R. (2023), Dictionary learning for integrative, multimodal and scalable single-cell analysis. Nature Biotechnology.
[Heckel al., 2019] Heckel, R., Shah, N. B., Ramchandran, K., and Wainwright, M. J. (2019).
Active ranking from pairwise comparisons and when parametric assumptions do not help.
[Issartel et al., 2024] Issartel, Y., Giraud, C., and Verzelen, N. (2024). Minimax optimal seriation in polynomial time. arXiv preprint Siti::20050087433
[Jamieson and Nowak, 2011] 1] Jamieson, K. G. and Nowak, R. (2011). Active ranking using pairwise comparisons. Advances in neural information processing systems, 24.
[Janssen and Smith, 2022] Janssen, and Smith. A. (2022). Reconstruction of line-embeddings of graphons. Electronic Journal of Statistics, 16(1):3114477
(Karp and Kleinherg, 2007] Karp, R. M. and Kleinberg, R. (2007). Noisy binary search and its appli- cations. In Proceedings of the eighteenth annual ACM-SIAM symposium Discrete algorithms, pages 881-890. Society for Industrial and Applied Mathematics.
[Lattimore and Szepesvári, 2020] Lattimore, T. and Szepesvári, C. (2020). Bandit algorithms. Cam- bridge University Press.
[Natik and Smith, 2021] Natik, A. and Smith, A. (2021). Consistency of spectral seriation. arXiv preprint arXiv:21 12.04408.
[Nowak, 2009] Nowak, R. (2009). The geometry of generalized binary search. arXic preprint arXiv:0910.4397..
[Recanati et al., 2017] Recanati, A., Brüls, T., and d' A'prrmmnn,, A. (2017). A spectral algorithm for fast de novo layout of uncorrected long nanopore reads. Bioinformatics, 33(20):3 188-3198
[Recanati et al., 2018] Recanati, A., Kerdreux, T., and d' Aspremont, A. (2018). Reconstructing latent orderings by spectral clustering. arXiv preprint arXiv:1807.07122.
(Ren al., 2019] Ren, W., Liu, J. K., and Shroff, N. (2019). On sample complexity upper and lower bounds for exact ranking from noisy comparisons. Advances Neural Information Processing
Systems, 32.
[Robinson, 1951] Robinson, W. S. (1951). A method for chronologically ordering archacological deposits. American Antiquity, 16(4):293-30.
[Saad et al., 2023] Saad, F. M., Verzelen, N., and Carpentier, (2023). Active ranking of experts based on their performances in many tasks. In Proceedings of the 40th International Conference on Machine Learning.
[Shah and Wainwright, 2017] Shah, N. B. and Wainwright, M. J. (2017). Simple, robust and optimal ranking from pairwise comparisons. The Journal of Machine Learning Research, 18(1):7246- 7283.
[Soch et al., 2023] Soch et al., J. (2023). The book of statistical proofs.
12

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
All theoretical results referenced in abstract are clearly stated in main text.
Guidelines:
The answer NA 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
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Yes both theoretical and practical limitations are discussed
Guidelines:
The answer NA 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 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 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Assumptions are clearly stated in main text with corresponding proofs in appendix
Justification:
Guidelines:
The answer NA 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 proof's 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 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 properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
All code used to generate empirical results is provided.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, 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 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 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 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 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 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer:
[Yes]
Justification:
All code used to produce empirical results is provided
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c) cc/
public guscc//guieesseeee http://idde///eeeuuiiomm Coteeuomeem ss onPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.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?
//nips. //npssccppubbll wttpcccppppppppcteeeceecccccccep cesiic//uiee///eeeeeeeoeo.eeeeee ies CodeeSume ss ciooooolliii ooooicyyy icy) 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 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 supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: 'Experimental section is clearly explained. All code used to produce empirical results is provided
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Error bars are provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall 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).
15

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 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 figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: Experiments are purely illustrative as this a theoretically focused work
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 't make it into the paper).
9. Code of ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///waaa........ooooo..////a
Question:
Answer: [Yes]
Justification:
No ethical concerns
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Limited potential impact the work is theoretically focused
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact 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.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No risk posed
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [Yes]
Justification: Competing algorithms clearly referenced
Guidelines:
The answer NA means that the paper does not 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papers thcode com dataaetteett has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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.
14. Crowdsoureing and research with human subjects
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 details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing or research with human subjects
Guidelines:
The answer NA 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 contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According 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.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
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?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: No involvement of LLMs
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (ht /tte:::///urrppppp /tt.arrppp.ccccooofeeeeeee/////e 2025/ LLM) for what should or should not be described.
19


Reviews:
[{"review_id": "5nlL9lSu6i", "reviewer": "Reviewer_FHVh", "summary": "This paper explores the active seriation problems. On the one hand, it demonstrates the impossibility of solving active seriation problems when the SNR value is smaller than $\\log n$ orderwise, where $n$ denotes the number of items, indicating the difficulty of this problem. On the other hand, when SNR exceeds $\\log n$, this paper proposes Active Seriation by Iterative Insertion (ASII) algorithm, which matches the lower bound of the error metric. In addition, some numerical results also validate the effectiveness of the proposed algorithm.", "questions": "Please try to answer the following questions:\n\n1. (Main) I believe the active seriation problem is closely related to MAB problems based on my experience: The sub-Gaussian assumption, noisy observations, and the form of the upper and lower bounds are quite similar to those in the MAB literature. Although the authors also briefly mentioned this point in Line 55, the subsequent discussion is missing. My questions regarding this connection are twofold: (1) Theoretically, can the authors provide more discussions about their similarities and differences? I wonder if this problem can even be formulated as an MAB problem? If not, what is the key distinction? (2) Experimentally, can some popular MAB algorithms such as UCB, TS, be adopted as baselines here? A comparison with these methods might help demonstrate the effectiveness of the proposed algorithm.\n\n2. For the experiments: (1) The Fig. 3 cannot reflect how parameters $\\sigma, n, T$ impact the performance of ASII, which are key components in the theorem. (2) In scenario 3, AS algorithm dramatically outperforms the others, and achieves small errors ($\\le 0.2$) when $\\beta$ is small. Does this violate Theorem 3.1? (3) Can the authors provide the error bar to show the robustness of the proposed algorithm?\n\n3. Can the authors give some real-world applications to strengthen the significance of this paper?", "limitations": "Please focus on Questions. I think there are no additional limitations.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. This discussion of SNR $\\sim \\log n$ and the results on lower bound make this paper complete. When SNR is small, the difficulty of active seriation problems is well clarified, delineating the boundaries of problem solvability. In addition, the proposed lower bound strengthens the theoretical foundation of ASII algorithm.\n\n2. The proposed ASII algorithm is both elegant and effective. Although the underlying idea is quite simple, the analysis is concrete, the detailed design, such as the improved binary search, is dedicated, the theoretical results are strong (matching the lower bound orderwisely), and the numerical results are also convincing.\n\nWeaknesses:\n\n1. The presentation is somewhat unclear. The structure of the paper is confusing, for example, the theoretical analysis of ASII algorithm appears before the statement of the algorithm itself. Moreover, many typos lead to confusions and reduce readability, e.g., (1) Should $\\Delta(M)$ be $\\Delta_M$ in Line 126? (2) How many scenarios are considered in numerical experiments, as the caption of Fig. 2 seems inconsistent with the discussion? (3) There are some minor grammar mistakes, such as “exists” in Line 274.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We apologize for the issues with the presentation and organization of the manuscript. In response, we have rewritten several sections of the paper. We hope these revisions have greatly improved its clarity and readability.\n\n---\n\n\n#  Response to Reviewer's Comment on MAB (Question 1):\n\nWhile Multi-Armed Bandit (MAB) algorithms focus on selecting arms based on independent observations to maximize cumulative rewards (or identify the best arm in best-arm identification), the active seriation problem has a fundamentally different goal. In MAB, each arm provides an independent reward, and the objective is to identify the arm with the highest expected reward over time. Classical algorithms like UCB or TS are designed to concentrate sampling on the best arms (those with the highest expected rewards).\n\nIn contrast, active seriation involves interdependent observations: the similarity between two items reflects their relative positions in an underlying ordering. Querying one pair of items can thus influence how we interpret the similarity of other pairs, because the relationships between all pairs must be consistent with the underlying ordering. This interdependence makes the problem more complex than simply optimizing individual rewards, as the goal is to recover the entire ordering (permutation) of the items. Unlike MAB, which optimizes individual rewards, seriation's challenge is to determine this global ordering from pairwise measurements, making it a fundamentally different problem.\n\nThus, while both problems are sequential and involve repeated querying, active seriation aims to recover a permutation of items, a combinatorial task, which differs from maximizing rewards or identifying the best arm in MAB. This is why classical MAB algorithms like UCB or TS, which assume independent rewards, cannot be directly applied to seriation.\n\nA more closely related problem in the literature is active ranking [Heckel et al., 2019], where the goal is to rank items based on their expected rewards using pairwise comparisons. However, ranking problems often assign intrinsic scores to individual items, whereas seriation does not. Instead, seriation focuses on recovering the relative ordering of items, which requires considering interdependencies between all pairwise similarities. For this reason, classical ranking methods based on pairwise comparisons cannot be directly applied to seriation either.\n\n---\n\n#  Response to Reviewer's Comment on Experiments (Question 2):\n\n**Clarification:** The primary contribution of our work is the development of an active seriation algorithm, which, to our knowledge, is the first of its kind. In the numerical experiments, we compare our algorithm to existing batch methods, which require the full $n \\times n$ matrix upfront. While we place our algorithm in a batch setting for comparison, it's important to note that this setting is not directly relevant to our active approach, where observations are collected sequentially. For instance, if only $T$ observations are available with $T < n^2$, batch algorithms cannot function, whereas our algorithm can still proceed and yield meaningful results.\n\n \n\n**Improvement of the Experimental Section:** We  apologize for the shortcomings in the experimental section of our original submission.  Since the submission, we have completely rewritten and significantly improved the experimental section, incorporating new simulations that  highlight the strengths of our ASII algorithm.\n\nIn particular, we focused on addressing one of the major limitations of previous work: the reliance on the Toeplitz assumption for certain algorithms, such as the AS algorithm (Cai and Ma, 2022). Our experiments now demonstrate that the performance of ASII is independent of the Toeplitz structure, making it applicable to a much broader class of matrices. In contrast, the AS algorithm performs poorly on heterogeneous matrices, due to its reliance on properties specific to Toeplitz matrices.\n\nWe also introduced the famous spectral seriation algorithm as a new competitor in our experiments. However, as noted in prior work (e.g., Cai and Ma, 2022), the spectral algorithm does not have strong theoretical guarantees for general matrix classes, and this is reflected in its performance outside the Toeplitz setting. We believe that these new simulations and insights provide a clearer, more rigorous comparison between algorithms and better illustrate the advantages of our proposed method.\n \n\n## 1) Impact of Parameters $\\sigma, n, T$ on Performance:\n\nWe appreciate the reviewer's suggestion to explore the impact of the parameters $\\sigma$, $n$, and $T$ more explicitly in our experiments. In the revised version of the paper, we have conducted additional experiments to better illustrate how these parameters influence the performance of the ASII algorithm.\n\n\n\n## 2) Performance of AS Algorithm in Scenario 3 and Violation of Theorem 3.1?\n\nRegarding the observed performance of the AS algorithm in Scenario 3, where it dramatically outperforms the others and achieves small errors when $\\beta$ is small, this scenario is extremely favorable for the AS algorithm and unfavorable for the ASII procedure. The performance of the AS algorithm depends on a global signal in the matrix (specifically, variations in the $L_1$-distance between rows), while the ASII procedure relies on a local signal in the matrix (the minimal gap $\\Delta$ as defined in the paper). \n\nIn this scenario, where $\\beta = \\Delta$, the local signal diminishes as $\\Delta \\rightarrow 0$, while the global signal remains large, regardless of $\\Delta$ values. This explains why the AS algorithm outperforms ASII in this case.\n\nWe acknowledge that this numeric example may have been misleading and not well-chosen. We have revised our numerical section to clarify this point. Importantly, the above experiment does not contradict the lower bound of Theorem 3.1. Recall the notation $\\mathcal{M}\\_{\\Delta}$ for the class of similarity matrices with minimal gap $\\Delta$ (and $\\mathcal{R}\\_{\\Delta}$, which was incorrectly used in the original manuscript as a typo). The impossibility result (Theorem 3.1) represents a worst-case analysis over the class $\\mathcal{M}\\_{\\Delta}$: the lower bound is proved for a specific instance in the class $\\mathcal{M}\\_{\\Delta}$. For example, when $\\Delta = 0$, the instance is the null matrix $M = \\mathbf{0}_{n \\times n}$, which indeed belongs to $\\mathcal{M}_0$. However, the matrix considered in Scenario 3 of our experiment is not the null matrix when $\\beta = \\Delta = 0$, and therefore, Theorem~3.1 does not apply to this matrix. Hence, there is no contradiction between Theorem 3.1 and our original experiments.\n\n\n\n##  3) Error Bar for Robustness:\n\nWe acknowledge the importance of demonstrating the robustness of the proposed algorithm through error bars. In the revised paper, we will include error bars in our experimental results.\n\n\n---\n\n#   Response to Reviewer's Comment on Real-World Applications (Question 3)\n\nWe appreciate the reviewer's suggestion to highlight real-world applications of our method. To strengthen the significance of our work, we refer to the recent study by Cai and Ma (2022), which applies seriation reordering techniques to real-world biological data. In their study, two datasets were analyzed to infer the temporal ordering of cells in single-cell RNA sequencing experiments. We plan to apply our active seriation algorithm to these same datasets and present our results in the updated version of our paper, comparing the performance with that of Cai and Ma’s method.\n\n1. **Real Dataset 1:** It consists of 372 primary human skeletal muscle myoblasts undergoing differentiation at 24-hour intervals. The goal was to infer the temporal order of cells during differentiation. By constructing similarity matrices and applying a seriation algorithm,  Cai and Ma (2022) demonstrated the good performance of their algorithm in recovering the true temporal order.\n    \n2. **Real Dataset 2:** It involves 149 human primordial germ cells from various ages ranging from 4 to 19 weeks. A similar methodology was used to infer the temporal order of these cells. \n\n\nThese real-world applications highlight the practical utility of seriation algorithms in analyzing complex, noisy, and high-dimensional biological data~[1]. The ability to recover latent temporal or sequential structures from such datasets is a crucial problem in computational biology. Our method offers a computationally efficient and statistically robust solution. \nMoreover, one of the key advantages of our active seriation algorithm is its ability to achieve accurate results with fewer similarity measurements, which can be of practical interest in scenarios where obtaining large amounts of pairwise comparisons may be costly or time-consuming.\n\nAdditionally, we highlight several other domains where our seriation method can be applied to enhance real-world systems:\n\n\n 1. **Genomic Sequence Alignment:** Seriation can be applied to reorder genomic sequences based on pairwise similarity metrics, such as sequence alignments or genetic distances. \n\n2. **Recommendation Systems:** Seriation can be employed in recommendation systems to identify item rankings based on pairwise similarities between items (e.g., products or movies). For example, if a product is liked by users who also like another product, the seriation algorithm can place these products closer together in the reordered similarity matrix, improving the overall accuracy of the recommendations.\n\n\n[1] scPrisma infers, filters and enhances\ntopological signals in single-cell data using\nspectral template matching, Jonathan et al., 2023, Nature Biotechnology"}, {"review_id": "l0YatyHasN", "reviewer": "Reviewer_HzA5", "summary": "This paper studies the active seriation problem: i) there are n items with a hidden true ranking; ii) the learner can query two items each time, and each query returns a noisy sample of the similarity of them; iii) If in the true ranking, two items are closer, then the similarities are closer. The learner wants to recover the full ranking with high probability by actively selecting pairs to query, and tries to use the least amount of queries. \n\nThe authors gives the lower bound and upper bound on the sample complexity (O(n\\log(n)), and proposes a new algorithm achieving the optimal sample complexity.", "questions": "Maybe give some concrete examples to explain the real-world use case of this paper's setting?", "limitations": "No negative social impacts found", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n-The problem studies in this paper is interesting and fundamental in my opinion, and the authors give clear and optimal results on the lower and upper bounds. The settings are more general than previous works. Overall, the results and novelty of this paper are pretty good. I find no major flaws\n\nWeakness\n-For readers not quite familiar with this problem, maybe give more concrete real-world examples about this paper's setting.", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer’s Comment on Real-World Applications (Question)\n\n We appreciate the reviewer's suggestion to highlight real-world applications of our method. To strengthen the significance of our work, we refer to the recent study by Cai and Ma (2022), which applies seriation reordering techniques to real-world biological data. In their study, two datasets were analyzed to infer the temporal ordering of cells in single-cell RNA sequencing experiments. We plan to apply our active seriation algorithm to these same datasets and present our results in the updated version of our paper, comparing the performance with that of Cai and Ma’s method.\n\n1. **Real Dataset 1:** The first dataset consists of 372 primary human skeletal muscle myoblasts undergoing differentiation at 24-hour intervals. The goal was to infer the temporal order of cells during differentiation. By constructing similarity matrices and applying a seriation algorithm,  Cai and Ma (2022) demonstrated the good performance of their algorithm in recovering the true temporal order.\n    \n2. **Real Dataset 2:** The second dataset involves 149 human primordial germ cells from various ages ranging from 4 to 19 weeks. A similar methodology was used to infer the temporal order of these cells. \n\n\nThese real-world applications highlight the practical utility of seriation algorithms in analyzing complex, noisy, and high-dimensional biological data. The ability to recover latent temporal or sequential structures from such datasets is a crucial problem in computational biology. Our method offers a computationally efficient and statistically robust solution, particularly when data is  noisy. Moreover, one of the key advantages of our active seriation algorithm is its ability to achieve accurate results with fewer similarity measurements, which can be of practical interest in scenarios where obtaining large amounts of pairwise comparisons may be costly or time-consuming.\n\nAdditionally, we highlight several other domains where our seriation method can be applied to enhance real-world systems:\n\n\n 1. **Genomic Sequence Alignment:** Seriation can be applied to reorder genomic sequences based on pairwise similarity metrics, such as sequence alignments or genetic distances. By grouping similar sequences together, seriation helps improve the alignment process, especially in noisy or incomplete datasets, making it more efficient and robust for large-scale genomic comparisons.\n\n    \n2. **Recommendation Systems:** Seriation can be employed in recommendation systems to identify item rankings based on pairwise similarities between items (e.g., products or movies). A similarity matrix, derived from user-item interactions (e.g., ratings, clicks, or purchases), allows the algorithm to reorder items based on how similarly users interact with them. This approach helps uncover latent relationships between items, facilitating personalized recommendations even when the data is noisy. For example, if a product is liked by users who also like another product, the seriation algorithm can place these products closer together in the reordered similarity matrix, improving the overall accuracy of the recommendations."}, {"review_id": "gzIMO4nmxu", "reviewer": "Reviewer_5WRt", "summary": "This paper considers the problem of seriation, a noisy variant of sorting, from an active learning angle. The basic setting is as follows. There is an unknown ordering/ranking of $n$ items, where items that are closer to each other in the ranking are more similar than ones that are far apart. Specifically the similarities are encoded by a Robinson matrix, which is a symmetric matrix $A$ that is \"monotone toward the diagonal\". That is, any path in $A$ that starts at the entry $A_{n,1}$, ends at a diagonal entry, and only goes upward or to the right is monotone. Since the ordering is unknown, the algorithm only gets noisy access to some fixed permuted copy $M$ of such a Robinson matrix.\n\nIn the active seriation problem, the algorithm is active/adaptive, and in each of the $T$ rounds it selects a pair $i,j$ and obtains an independent draw from a $\\sigma$-subgaussian random variable of mean $M_{ij}$. The goal is to retrieve the permutation (over the rows) exactly.\nThis paper assumes that there is a universal lower bound $\\Delta$ on the similarities between elements and obtains tight results parameterized by this assumption. Specifically, the authors identify the SNR $\\Delta^2 T / \\sigma^2 n$ as the key quantity. They show that when this quantity is smaller than a constant times $\\log n$, any algorithm fails with constant probability. On the other hand, they devise an algorithm whose failure probability is of order $e^{-O(SNR)}$. The algorithm is based on noisy binary search and includes an interesting ingredient of backtracking, that goes backwards in the search if it detects a possible violation. I did not go over the analysis (which appears only in the appendix).", "questions": "* There seems to be incompatibility between Theorem 3.1 and 3.2, specifically in the $\\log n$ term. In Theorem 3.1 you claim that any algorithm where the SNR is less than $\\log n$ fails with constant failure probability, whereas in Theorem 3.2 you obtain an algorithm that achieves constant failure prob already when the SNR is a constant. Please explain how these settings differ.\n\n* Why does the backtracking work? I was curious about more details about the theoretical analysis (and in contrast am not that interested in the experiments). Backtracking is not that common in noisy binary search approaches, and introducing such a technique could be a valuable contribution in your paper, which you don't emphasize enough.\n\n* How would your results change if you only asked for a ranking that is approximately monotone?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "+ The studied problem is interesting, and natural for an active approach.\n\n- Technical novelty is not very high. Noisy binary search is probably the first technique that one would try in such a setting, and the analysis does not seem to carry with it very deep lessons or surprises.\n\n- The dependence in the minimum similarity $\\Delta$ seems rather limiting. For example, it could be the case that we rank a large set of elements where some pairs of them are near-identicals, and we wish to get a good ranking at least for those elements that are far enough. It would be better if you can extend your results to this regime (which I believe shouldn't be too hard).\n\n-+ There are some issues in terms of writing, although overall it is decent. One example of an issue is my first question to the authors (which claims to Theorems 3.1 and 3.2 are not completely compatible with each other). Also, given that the technical analysis is claimed to be the main contribution in this work, at least a snippet of it should appear in the main body.", "was_revised": true, "final_justification": "I still view it as a borderline paper, but given the positive reception by others, flipped it from a weak reject to a weak accept score. In essence, there are interesting and novel theoretical contribution (the backtracking algorithm), and on the other hand the bottom line results (and the dependence in the parameters) are perhaps a slight weakness.", "rebuttal": "Thank you for your thoughtful feedback, and for taking the time to review our work. We have addressed your concerns by rewriting the entire paper, especially the algorithm section, to provide clearer intuition on how and why the algorithm works. We hope the revised version of the paper will better explain the key contributions.  \n\n---\n\n# Response to Reviewer's Comment on Incompatibility between Theorems (1st Question)\n\nWe understand the source of confusion and would like to clarify that the regimes in Theorem 3.1 and Theorem 3.2 are complementary, and *not* incompatible. Specifically:\n\n 1. In **Theorem 3.1**, we consider the *impossibility regime*, where the signal-to-noise ratio (SNR) satisfies\n    $\\frac{\\Delta^2 T}{\\sigma^2 n} \\lesssim \\log n \\enspace.$\n    In this setting, we show that no algorithm can recover the correct ordering with vanishing error probability.  \n\n2. In contrast, **Theorem 3.2(a)** addresses the *recovery regime*, where\n    $\\frac{\\Delta^2 T}{\\sigma^2 n} \\gtrsim \\log n \\enspace.$\n    Under this condition, we provide performance guarantees for our ASII algorithm, showing that the error probability decays exponentially fast with the SNR.\n\n\nWe acknowledge that **Theorem 3.2(b)**, which provides a lower bound on the error rate for any algorithm, could be confusing, as it overlaps with the regime in **Theorem 3.1** by applying when $\\frac{\\Delta^2 T}{\\sigma^2 n} \\gtrsim 1$.\n\nHowever, this does not contradict **Theorem 3.1**. Instead, it complements it: **Theorem 3.2(b)** shows that in the recovery regime 2 (above), no algorithm can achieve error decay faster than exponential in the SNR, while **Theorem 3.1** asserts that in the complementary regime  1 (above), the error probability remains lower bounded by a constant. \n\nTo enhance clarity, we will revise the statements of Theorems 3.1 and 3.2 to explicitly state the respective conditions of the regimes 1 and 2 (above) as *numbered equations* within the theorems themselves. We also recognize that stating **Theorem 3.2(b)** under the more general condition \n$\\frac{\\Delta^2 T}{\\sigma^2 n} \\gtrsim 1$, \nrather than the recovery regime 2 (above), may have caused confusion without adding benefit, and we will revise accordingly.\n\n---\n\n# Response to Reviewer's Comment on the Backtracking Mechanism (2nd Question)\n\nThank you for your insightful comment. We are glad that you find the backtracking approach intriguing, and we are happy to provide further clarification on its role in our **Binary-\\&-Backtracking-Search (BBS)** subroutine.\n\nIn noisy binary search, incorrect decisions at any step can propagate and lead to compounding errors, ultimately resulting in incorrect item placement. Traditional methods mitigate this by increasing the number of samples per test to reduce error probability, but this approach can be sample-inefficient. In contrast, our method uses a fixed, small number of samples per test, ensuring constant accuracy (e.g., a correct decision probability of at least $3/4$). This means there is a small probability of error at each decision point.\n\nBacktracking serves as a corrective mechanism to address these errors. The algorithm maintains a history of explored intervals and performs sanity checks at each step. If an inconsistency is detected, the algorithm backtracks to a previous interval and resumes the search. This prevents a single mistake from permanently misguiding the process.\n\nThe combination of low-sample testing and backtracking ensures that, despite occasional errors, the overall number of correct decisions dominates the incorrect ones over the search path. As a result, the algorithm achieves a high probability of correct insertion while maintaining near-optimal sample efficiency.\n\nWe will expand this discussion of this mechanism in the revised manuscript to more clearly explain how it works and its importance in the procedure.\n\nAdditional clarification on the backtracking mechanism::\n\n\n1. Using backtracking in our binary search algorithm allows us to tolerate a certain number of mistakes, as long as enough good decisions are made to offset them. Specifically, if we perform enough steps, even a constant proportion of mistakes can be corrected by backtracking, ensuring that the final result is correct. The key point here is that we can afford some mistakes, as long as they are balanced by correct decisions that guide us to the correct point of insertion.\n2. In contrast, if we remove backtracking, the algorithm becomes more sensitive to mistakes at each stage. Without the corrective mechanism, an error at any step could result in an incorrect placement. This would make the algorithm less reliable than the version with backtracking.\n\n\n--- \n\n# Response to Reviewer's Comment on Extension to Approximate Seriation (3rd Question)\n\nThank you for this insightful comment. We agree that the dependence on the minimum similarity can be limiting in some cases. While our current analysis focuses on exact monotonicity, we acknowledge that extending the results to approximately monotone rankings --only reordering elements that are sufficiently dissimilar-- is an important direction.\n\nUnfortunately, our current binary search method struggles in this case. When items are too close to each other (less than $\\Delta$ apart), there are no longer guarantees of a \"correct answer\" in the tests performed along the search, and the binary and backtracking search can become unpredictable, leading to instability in the ordering.\n\nWe see two potential approaches to address this issue:\n1. **Simple, Sub-Optimal Solution:** A straightforward method would be to remove backtracking and sample $\\ln n$ times more per test. This would ensure high-probability correctness at each decision, resulting in a simple algorithm that works for items sufficiently far apart. While this solution is less sample-efficient (increasing the number of samples by an extra logarithmic factor), it provides a reasonable approach for handling very similar items. For example, if the items are partitioned into groups $G_1, \\dots, G_K$, with items in the same group being identical, the algorithm would correctly reorder items between groups that are at least $\\Delta$ apart (i.e., $R_{i,j} - R_{i,k} \\geq \\Delta$ whenever $j$ and $k$ are from different groups, for all $i$).\n2. **Difficult, Optimal Solution:** A more challenging extension would involve modifying the binary and backtracking search. Instead of placing an item at the last visited interval, we would track all small intervals visited and place the item in the \"median\" of those intervals. This would allow the algorithm to better handle identical or near-identical items, but it would require significant theoretical development of our current proofs. While we cannot promise this will appear in the camera-ready version of the paper, we are committed to exploring this direction and sincerely hope to obtain concrete results before the final submission."}, {"review_id": "8UchIBRpwd", "reviewer": "Reviewer_1ga3", "summary": "The paper addresses the problem of recovering the correct order of items using noisy pairwise similarity comparisons, where the comparisons are chosen actively. It introduces a simple and efficient algorithm called ASII (Active Seriation by Iterative Insertion), which incrementally builds the ordering using binary search with backtracking. The authors provide theoretical guarantees showing that ASII achieves optimal recovery rates under certain signal-to-noise conditions, and they validate its performance through simulations.", "questions": "1.\tCould the authors clarify whether the algorithm assumes sigma is known, and if not, how T_0 is chosen in practice? If sigma is unknown, can the algorithm be made adaptive to it?\n2.\tThe algorithm’s performance degrades when the minimal gap (delta) is small or varies across the matrix, while batch methods like Adaptive Sorting are more robust in such cases. Can the authors comment on whether ASII could be modified to incorporate more global or aggregate information to improve robustness in heterogeneous matrices? Even a heuristic or hybrid approach that combines local and global signals could be valuable.\n3.\tCould ASII be extended to handle partial or missing similarity data?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths – \n1.\tThe paper introduces and formalizes the problem of active seriation, which is a natural and important extension of classical seriation to settings where pairwise similarities can be queried adaptively.\n2.\tThe authors provide clear and tight theoretical guarantees. They show exactly when recovery is possible and when it’s not, and their algorithm matches these limits up to constants.\n3.\tThe link to multi-armed bandits, especially thresholding bandits, is clever and helps ground the analysis. \n4.\tThe paper does a good job of providing intuitive explanations alongside the formal results. For example, the discussion around how the minimal gap (delta) and the noise level (sigma) affect the ability to recover the true ordering helps the reader build a solid understanding of the underlying difficulty of the problem. These kinds of insights make the theoretical contributions more accessible and meaningful.\n5.\tThe supplementary material includes detailed and well-organized proofs. It’s clear the authors have done a careful job with the analysis.\n6.\tThe paper is well-written and easy to follow. Definitions, algorithms, and results are all clearly presented.\n\n\n\nWeaknesses – \n1.\tAll experiments are conducted on synthetic data. The absence of real-world datasets makes it difficult to assess the practical utility and robustness of the method.\n2.\tWhile the paper compares ASII to Adaptive Sorting and Spectral Seriation, it does not benchmark against more recent or diverse active learning or ranking algorithms.\n3.\tThe algorithm and its guarantees (look like) assume knowledge of the noise variance (sigma), which may not be available or easy to estimate in practice. In the ‘Test’ subroutine, the number of samples T_0 used per test is chosen to ensure high-probability correctness, which should depend on the noise level (sigma).\n4.\tWhile the algorithm is adaptive to the unknown minimal gap (delta), it does not adapt to unknown noise levels. This limits its applicability in settings where sigma is not known or cannot be estimated reliably.\n5.\tWhile ASII performs well when the minimal gap (delta) is reasonably large and uniform, its reliance on local comparisons makes it less effective when (delta) is very small or varies significantly across the matrix. In such cases, batch algorithms like Adaptive Sorting, which leverage aggregate information across the entire matrix, can be more robust. This is evident in the experimental results (e.g., Scenario 2), where ASII’s performance degrades more sharply than that of its batch counterparts.", "was_revised": true, "final_justification": "I have reviewed the authors' response, added additional questions, and also read the other reviews. I have decided to maintain my score.", "rebuttal": "Thank you for your thoughtful feedback, and for taking the time to review our work. \n\n---\n\n#  Response to Reviewer's Comment on Noise Variance $\\sigma$ (Weaknesses 3 and 4, Question 1)\n\nOur algorithm does *not* assume prior knowledge of the noise variance\n $\\sigma$. \nInstead, the sample size \n$T_0$\n used in the **Test** subroutine is determined adaptively based on the total sample budget \n$T$,\nwhich is allocated as \n1. $T_0 = \\left\\lfloor \\frac{T}{3n} \\right\\rfloor$ for the initial tests, and \n2. $T_0 = \\left\\lfloor \\frac{T}{3n T_k} \\right\\rfloor = \\left\\lfloor \\frac{T}{9 n \\log k} \\right\\rfloor$ for tests within the **Binary \\& Backtracking Search** subroutine.\n\nThis approach does not require explicit knowledge of \n$\\sigma$. Instead, the total budget\n $T$\n should be large enough (e.g., satisfying $T \\gtrsim \\frac{\\Delta^2 n \\log n}{\\sigma^2}$ as in Theorem 3.2(a)) to ensure that each test in 2 (above)  obtains a sufficiently accurate estimate with constant probability of success (better than random guessing). \n\nAn exception is the initial test 1 (above), which decides whether to invoke the **Binary \\& Backtracking Search** subroutine. Since this decision is not revisited, the test must be sufficiently reliable to avoid incorrect branching. This initial test outcome will be correct with high probability once the total budget satisfies $T \\gtrsim \\frac{\\Delta^2 n \\ln n}{\\sigma^2}$  as in Theorem 3.2(a).\n\nIn practice, this means that \n$T_0$\n scales with the total budget \n$T$\n and number of items\n $n$, \nallowing the algorithm to adapt implicitly to the noise level without needing \n$\\sigma$\nas an input parameter.\n\nWe acknowledge that this point was not sufficiently emphasized in the submitted version of the paper. We will revise the manuscript accordingly .\n\n---\n\n\n\n#  Response to Reviewer’s Comment on Dependence on Minimal Gap $\\Delta$ (Weakness 5, Question 2)\n\nWe agree that robustness to variations in the minimal gap $\\Delta$ is an important issue. The current **ASII** algorithm relies heavily on local measurements, such as pairwise comparisons between items. Specifically, to find the relative position of item $k$ with respect to a pair $(l,r)$ of reference items, the **Test** subroutine compares the corresponding pairwise similarities $M_{k,l}, M_{k,r}, M_{l, r}$. This approach can be sensitive to variations in the minimal gap, particularly when $\\Delta$ is small. As a result, when $\\Delta$ decays, the algorithm may struggle to maintain stable performance.\n\nTo improve robustness, one potential solution is to modify the **Test** subroutine to incorporate more global information. For instance, instead of just comparing pairwise associations ($M_{k,l}, M_{k,r}, M_{l, r}$), we could compute global distances such as the $L_1$ distance between items. Specifically, we could define the $L_1$ distance between items $k$ and $l$ as the difference between their respective rows in the matrix, i.e., $D_{k,l} = \\lVert M_{k} - M_{l} \\rVert_1$. By using these distances, we could compare $D_{k,l}, D_{k,r}, D_{l,r}$ rather than directly comparing the pairwise associations ($M_{k,l}, M_{k,r}, M_{l, r}$). This hybrid approach, inspired by the batch algorithm of Cai and Ma (2022), could offer more robust performance in heterogeneous matrices.\n\nHowever, since our method is active and aimed at reducing sample complexity, we must balance the incorporation of global measurements with the need to minimize the number of samples. To achieve this, we propose estimating global measurements via random subsampling, using a small number of entries (e.g., $\\log(n)$ samples) to estimate the $L_1$ distance. This would allow us to incorporate global signals while keeping the computational cost low compared to batch methods\n\nWe plan to include numerical experiments with this more robust method in the revised version of the paper and, ideally, to provide theoretical results on its performance. \n\n\n---\n\n# Response to Reviewer’s Comment on Missing Data (Question 3)\n\nYes, it is possible to extend the **ASII** algorithm to handle partial or missing similarity data. As mentioned in our response to the previous question, one approach is to modify the **Test** subroutine to incorporate more global measurements, such as the $L_1$ distance between items, using random subsampling. This technique could  be adapted to handle missing data. By drawing a subsample of data points (e.g., $\\log(n)$ entries), we can estimate  distances, even when some values are missing.\n\nTo ensure robustness in the presence of missing data, we would need to make certain assumptions about the proportion of missing entries. Specifically, as long as the proportion of missing data is small, we can select a sufficiently large subsample to ensure that the remaining valid data points are representative. This approach would allow the algorithm to continue making decisions with a reasonably high probability of success, while mitigating the effects of missing data.\n\nWe plan to explore this extension in our numerical experiments and, if possible, include a theoretical analysis of this method.\n\n---\n\n# Response to Reviewer’s Comment on Real-World Applications (Weaknesses 1)\n\nWe appreciate the reviewer's suggestion to highlight real-world applications of our method. To strengthen the significance of our work, we refer to the recent study by Cai and Ma (2022), which applies seriation reordering techniques to real-world biological data. In their study, two datasets were analyzed to infer the temporal ordering of cells in single-cell RNA sequencing experiments. We plan to apply our active seriation algorithm to these same datasets and present our results in the updated version of our paper, comparing the performance with that of Cai and Ma’s method.\n\n1. **Real Dataset 1:** The first dataset consists of 372 primary human skeletal muscle myoblasts undergoing differentiation at 24-hour intervals. The goal was to infer the temporal order of cells during differentiation. By constructing similarity matrices and applying a seriation algorithm,  Cai and Ma (2022) demonstrated the good performance of their algorithm in recovering the true temporal order.\n    \n2. **Real Dataset 2:** The second dataset involves 149 human primordial germ cells from various ages ranging from 4 to 19 weeks. A similar methodology was used to infer the temporal order of these cells. \n\n\nThese real-world applications highlight the practical utility of seriation algorithms in analyzing complex, noisy, and high-dimensional biological data. The ability to recover latent temporal or sequential structures from such datasets is a crucial problem in computational biology. Our method offers a computationally efficient and statistically robust solution, particularly when data is  noisy. Moreover, one of the key advantages of our active seriation algorithm is its ability to achieve accurate results with fewer similarity measurements, which can be of practical interest in scenarios where obtaining large amounts of pairwise comparisons may be costly or time-consuming.\n\nAdditionally, we highlight several other domains where our seriation method can be applied to enhance real-world systems:\n\n1. **Genomic Sequence Alignment:** Seriation can be applied to reorder genomic sequences based on pairwise similarity metrics, such as sequence alignments or genetic distances. By grouping similar sequences together, seriation helps improve the alignment process. \n    \n2. **Recommendation Systems:** Seriation can be employed in recommendation systems to identify item rankings based on pairwise similarities between items (e.g., products or movies). A similarity matrix, derived from user-item interactions (e.g., ratings, clicks, or purchases), allows the algorithm to reorder items based on how similarly users interact with them. This approach helps uncover latent relationships between items, facilitating personalized recommendations even when the data is noisy. For example, if a product is liked by users who also like another product, the seriation algorithm can place these products closer together in the reordered similarity matrix, improving the overall accuracy of the recommendations.\n\n---\n\n#  Response to Reviewer’s Comment on Numerical Experiments (Weaknesses 2):\n\nWe agree with the reviewer and acknowledge that this point needs further clarification.  The primary contribution of our work is the development of an active seriation algorithm, which, to our knowledge, is the first of its kind. While we compare our algorithm to existing batch methods like Adaptive Sorting and Spectral Seriation in the (new) numerical experiments, it's important to note that these batch methods require the entire $n \\times n$ matrix upfront. In contrast, our algorithm operates in an active setting where observations are sequentially collected, making the direct comparison somewhat limited.\n\nRegarding your comment on active learning or ranking algorithms, we would like to emphasize that there are no existing active seriation algorithms to compare against, as seriation and ranking are fundamentally different tasks. Active ranking algorithms, such as those proposed by Heckel et al. (2019), typically aim to rank items based on pairwise comparisons, often assigning intrinsic scores to individual items. However, seriation focuses on determining the relative ordering of items, which requires considering interdependencies between all pairwise similarities. Therefore, classical ranking methods based on pairwise comparisons cannot be directly applied to the seriation problem."}]

Author rebuttal:

Meta-review: This paper considers a novel problem of active, sequential hypothesis testing: how to query pairs of items, observe (noisily) a signal about (the magnitude of) their relative similarity, and use this information to rank-order them so that their relative positions correlate with their true underlying similarities. It carries out a comprehensive study in the sense of (a) providing an information-theoretic limit for low-error recovery by any procedure and (b) proposing an efficient algorithm, based on a backtracking approach and a generalization of insertion sorting, that is proven to be optimal when the signal in the problem is above the information-theoretic SNR limit. 

The paper's initial reviews asked for clarifications on several points, including connections with the multi-armed bandit literature, real-world motivating applications for the active seriation model, the relationship between the achievability and converse results of the paper, and the possibility of deriving schemes under only approximate monotonocity and highly skewed similarity structures. The authors responded with detailed clarifications on many of these points, which was noted positively by the reviewers.

Overall, barring the concerns about practical motivating situations for this rather general ordering model (which seems to be weaker than explicit win-loss feedback), the reviewers unanimously lean positive about the paper's contributions and its potential impact in introducing a new decision-making model. In view of the consensus and the strengths of the paper, I am happy to recommend acceptance.
Decision: Accept (poster)