Learning Right Monotone Permutation Matrices for Neural Subsequence Search

Bhavya Kohli, Soutrik Sarangi, Aziz Shameem, Abir De
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:4024-4032, 2026.

Abstract

Subsequence retrieval seeks relevant segments in a large corpus given a short query. Existing pairwise metric-based methods are computationally intensive, hard to parallelize, and tied to domain-specific metrics. In this work, we introduce a neural framework that casts subsequence matching as end-to-end alignment with permutation matrices satisfying monotonicity used as differentiable approximate subsequence selectors. Our framework yields fixed-dimensional embeddings for variable-length inputs, and we prove these embeddings are compatible with standard Approximate Nearest Neighbor search methods such as Locality-sensitive hashing (LSH), enabling scalable retrieval. We also impose structural priors on admissible subsequences and integrate them directly into the scoring function. The approach is domain-agnostic and operates on pre-trained representations across modalities. Experiments on real-world datasets from two different domains show strong retrieval performance and substantial speedups, with high parallelism on GPU-accelerated hardware.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-kohli26a, title = { Learning Right Monotone Permutation Matrices for Neural Subsequence Search }, author = {Kohli, Bhavya and Sarangi, Soutrik and Shameem, Aziz and De, Abir}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {4024--4032}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/kohli26a/kohli26a.pdf}, url = {https://proceedings.mlr.press/v300/kohli26a.html}, abstract = { Subsequence retrieval seeks relevant segments in a large corpus given a short query. Existing pairwise metric-based methods are computationally intensive, hard to parallelize, and tied to domain-specific metrics. In this work, we introduce a neural framework that casts subsequence matching as end-to-end alignment with permutation matrices satisfying monotonicity used as differentiable approximate subsequence selectors. Our framework yields fixed-dimensional embeddings for variable-length inputs, and we prove these embeddings are compatible with standard Approximate Nearest Neighbor search methods such as Locality-sensitive hashing (LSH), enabling scalable retrieval. We also impose structural priors on admissible subsequences and integrate them directly into the scoring function. The approach is domain-agnostic and operates on pre-trained representations across modalities. Experiments on real-world datasets from two different domains show strong retrieval performance and substantial speedups, with high parallelism on GPU-accelerated hardware. } }
Endnote
%0 Conference Paper %T Learning Right Monotone Permutation Matrices for Neural Subsequence Search %A Bhavya Kohli %A Soutrik Sarangi %A Aziz Shameem %A Abir De %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-kohli26a %I PMLR %P 4024--4032 %U https://proceedings.mlr.press/v300/kohli26a.html %V 300 %X Subsequence retrieval seeks relevant segments in a large corpus given a short query. Existing pairwise metric-based methods are computationally intensive, hard to parallelize, and tied to domain-specific metrics. In this work, we introduce a neural framework that casts subsequence matching as end-to-end alignment with permutation matrices satisfying monotonicity used as differentiable approximate subsequence selectors. Our framework yields fixed-dimensional embeddings for variable-length inputs, and we prove these embeddings are compatible with standard Approximate Nearest Neighbor search methods such as Locality-sensitive hashing (LSH), enabling scalable retrieval. We also impose structural priors on admissible subsequences and integrate them directly into the scoring function. The approach is domain-agnostic and operates on pre-trained representations across modalities. Experiments on real-world datasets from two different domains show strong retrieval performance and substantial speedups, with high parallelism on GPU-accelerated hardware.
APA
Kohli, B., Sarangi, S., Shameem, A. & De, A.. (2026). Learning Right Monotone Permutation Matrices for Neural Subsequence Search . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:4024-4032 Available from https://proceedings.mlr.press/v300/kohli26a.html.

Related Material