You have n items with an unknown underlying order. You can query the similarity between any pair and receive a noisy answer. How many queries do you need to recover the order, and which pairs should you query?
The similarity matrix has Robinson structure: entries decrease as you move away from the diagonal in the true ordering. This means nearby items (in the unknown order) are more similar than distant ones. The observation is a noisy version of this Robinson matrix, viewed through an unknown permutation — you don't know which row corresponds to which position in the order.
Passive seriation queries all pairs and recovers the order from the complete noisy matrix. Active seriation chooses which pairs to query adaptively — each query's result informs which pair to query next. The paper shows the adaptive strategy requires substantially fewer queries than the passive one, with matching lower bounds proving the savings are fundamental, not algorithmic.
The algorithm can start with partial knowledge — a rough ordering that's mostly correct but has local errors. This intermediate regime between complete ignorance and full knowledge is where most practical problems live. You know the approximate order (from a preliminary sort, from domain knowledge, from a cheaper measurement) but need to refine it.
Under uniform separation (adjacent items in the true order have similarity gaps that don't vanish), the active algorithm recovers the exact order with high probability using an optimal number of queries. The optimality is over both the error probability and the query count — you can't do better on either axis simultaneously.
Order from adaptive questions. The answer to “which pair to compare next” depends on what you've already learned. Information begets information.