Finding distant evolutionary relatives of a protein means comparing it against millions of database sequences that may share less than 30% of their amino acids with it. The best recent neural approach keeps one vector per amino acid (residue) and scores a pair of proteins by letting each query residue find its best-matching database residue. That score beats averaging residues into a single vector by a wide margin, but it stores hundreds of vectors per protein and costs a residue-by-residue comparison for every candidate. We propose storing each database protein as one fixed-length vector, the sum of its residues passed through orthogonal random features. Random features are a randomized map under which dot products approximate a chosen similarity function. With the exponential kernel $\exp(q\cdot d/\tau)$ as that similarity, one database vector is enough to recover, in expectation, a soft version of the best-match score. Here $\tau$ is a temperature: small values make the soft match behave like a hard maximum.
The catch is a single knob with two competing effects. Lowering $\tau$ brings the score closer to exact best-match scoring, but it inflates the variance of the random-feature estimate. The best $\tau$ therefore depends on how many features you can afford to store. We tune $\tau$, and per-dimension scales of the feature map, by gradient descent on a held-out loss inside the one training run, instead of running an outer search over many trainings. We use orthogonal rather than independent random directions because they reduce exactly the variance that limits how small $\tau$ can go. The claim is that this recovers most of the gap between single-vector and residue-level retrieval at single-vector memory, without truncating database sequences and without paying for a hyperparameter sweep.
Core Claim
The three input directions play different roles. Remote homology detection is the application regime. Orthogonal random features are the core mechanism. Hyperparameter-optimization overhead is a constraint, because the method is only worth having if its one sensitive continuous knob can be set for roughly the cost of one training run.
Let $q_1,\dots,q_{L_Q}$ be the query's residue embeddings and $d_1,\dots,d_{L_D}$ the database protein's residue embeddings. The target score is a soft version of the late-interaction score used by ProtoCol:
$$s_\tau(Q,D)=\sum_{i=1}^{L_Q}\tau\log\sum_{j=1}^{L_D}\exp\!\left(\frac{q_i\cdot d_j}{\tau}\right).$$
As $\tau\to 0$ this tends to ProtoCol's score, which sums each query residue's maximum dot product $\max_j q_i\cdot d_j$ over the query. Now let $\phi$ be a positive random-feature map of dimension $m$, of the kind used in Rethinking Attention with Performers, whose dot products are unbiased for $\exp(q\cdot d/\tau)$. Then each database protein collapses to a single stored vector:
$$Z_D=\sum_{j=1}^{L_D}\phi(d_j),\qquad \hat s_\tau(Q,D)=\sum_{i}\tau\log\big(\phi(q_i)\cdot Z_D\big).$$
Each $\phi(q_i)\cdot Z_D$ is an unbiased estimate of the inner sum. The logarithm then adds a bias roughly equal to the estimator's relative variance. That relative variance grows as $\tau$ shrinks, because the exponent's scale grows as $1/\tau$. So there is an interior optimum $\tau^*(m)$, and orthogonal directions move it lower. Orthogonal sampling provably lowers variance for this kernel family, as shown in Orthogonal Random Features and the charm of a kernel.
Two properties make this useful for search. First, the database side costs $m$ floats per protein regardless of length, so there is no reason to cut sequences to 256 residues as ProtoCol does. The protein language model's own context limit still applies. Second, the pooled query $Z_Q$ gives a symmetric single-vector score $Z_Q\cdot Z_D$ that off-the-shelf approximate nearest-neighbor indexes can serve as a first stage. The per-residue soft score then reranks a shortlist at $L_Q\cdot m$ operations per candidate.
Relation to Prior Work
Two papers motivate the gap. ProtoCol shows that keeping per-residue embeddings and scoring with best-match late interaction reaches Capped Recall@1 of 0.946 on SCOPe superfamily retrieval. The next best baseline, a mean-pooled 650M ESM-2, trails by nearly 7 points. The same paper notes that the per-residue storage forces truncation and would need specialized multi-vector indexing to scale. Nearest neighbor search on embeddings shows that mean-pooled ProtT5 vectors collapse on full-length multi-domain proteins, with Pfam20 AUC1 of 0.367 against 0.520 for MMseqs2. Our score lets each query residue find its match anywhere in the database protein, which should help here.
The mechanism comes from the orthogonal random feature line. Orthogonal Random Features supplies the dense orthogonal construction and the fast Hadamard-based variant, SORF. Rethinking Attention with Performers and Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformers supply positive orthogonal features for the exponential kernel. Those papers use the features inside attention for masked language modeling. We use them to pool a set of residues into a similarity-preserving index vector for discriminative retrieval, which none of them attempt.
The tuning method comes from Scalable Gradient-Based Tuning of Continuous Regularization Hyperparameters. That paper tunes continuous hyperparameters on a validation split during one run, at about 30% extra compute. Three papers constrain the design. Hyperparameter optimization for randomized algorithms tunes random-feature distributions with ensemble Kalman inversion over many evaluations. It also suggests tuning with few features and deploying with many. We test that suggestion directly, because we expect $\tau^*$ to depend on $m$. Learning Adaptive Random Features learns the random directions themselves, which gives up orthogonality. We learn only a temperature and a diagonal scale, so the orthogonal structure survives. In the twilight zone of protein sequence homology finds that HHblits beats zero-shot protein language models on AUPRC. That result forces us to report false-positive-sensitive metrics, not only recall.
Research Program
The first stage is a pure approximation study with no retraining. We take ProtoCol's released ESM-2 35M residue embeddings (ProtoCol code) and compute $\hat s_\tau$ for a grid of $\tau$ and $m\in\{256,\dots,8192\}$. We compare independent Gaussian, dense orthogonal and SORF directions. For each $\tau$ we measure three things: the rank correlation of $\hat s_\tau$ with exact best-match scores, retrieval quality, and the empirical relative variance. This maps $\tau^*(m)$ and tests whether orthogonality lowers it.
The second stage trains end to end. We fine-tune the backbone with ProtoCol's contrastive objective, with $\hat s_\tau$ replacing the best-match score. The features are redrawn periodically, as in Performers. A validation split is held out, grouped by superfamily so that no superfamily appears on both sides. Every ten weight steps, $\log\tau$ and the diagonal scale are updated with the greedy validation hypergradient of Luketina et al.. The validation loss is the same contrastive loss on that split. We pre-register a check of whether it tracks Recall@1, since that paper warns that validation loss and the metric of interest can diverge.
The third stage builds the two-stage search system and measures memory per protein, latency per query and recall.
Baselines
The naive reference point is mean pooling. We use ProtoCol's trained mean-pooled single-vector model and the frozen mean-pooled ESM-2 650M, both from the released repository. On the same SCOPe split, the pooled 650M baseline sits nearly 7 points below ProtoCol's 0.946 Capped Recall@1, which puts it near 0.88 (ProtoCol). We count as a success any result that closes at least half of that gap at $m$ floats per protein.
The strongest existing method is ProtoCol itself, with exact best-match scoring and Capped Recall@1 of 0.946. It is the ceiling we approach, not a system we expect to beat on recall. Beating it means matching it within 1–2 points at a fraction of its per-protein storage, or exceeding it once untruncated database sequences are used. We run it from the released code on identical splits and backbone, with the same training steps.
A second strong competitor is a single vector with a learned attention-weighted pooling layer, trained with the same loss, steps and GPU budget. It is the obvious learned way to escape mean pooling. ProtSent-style contrastive single vectors (ProtSent) report only relative gains; no absolute Capped Recall@1 on this split was found on Lacuna. We therefore retrain a comparable contrastive single-vector model ourselves rather than cite a number.
We use MMseqs2 through ProtoCol's wrapper as the alignment reference. It reports over 1000 ms per query against ProtoCol's ~24 ms. On Pfam20 we reference MMseqs2's AUC1 of 0.520 (Nearest neighbor search on embeddings). No HHblits AUPRC number for our splits was found on Lacuna, so we run HHblits where compute permits.
Two ablations isolate the key ingredients. The first swaps orthogonal directions for independent Gaussian ones at equal $m$ and equal tuning. The second sets $\tau$ by grid search and by BOHB (BOHB), each given 8 full training runs, against a single hypergradient run. Hypergradient tuning wins if it lands within 0.5 points of the best searched configuration at under 1.5× one run's GPU-hours.
Why not just…?
Why not just use independent random Fourier features? The whole method rests on reaching small $\tau$ before variance swamps the log-estimate. Independent directions have strictly higher variance for this kernel family (charm of a kernel), and in Performers they were numerically unstable. The ablation settles this directly. If independent features reach the same $\tau^*$ and recall at equal $m$, orthogonality is not load-bearing and we will say so.
Why not just train a better single-vector embedding, as ProtSent does? This is a real threat. A learned attention-pooling vector has the same memory cost and may absorb much of the gain. Our argument is structural. A symmetric single vector cannot express "each query residue matches its best partner anywhere," and that should matter most on multi-domain Pfam20 and in the lowest identity bins. If learned pooling matches us there too, the random-feature construction adds nothing.
Why not just compress ProtoCol's residue vectors, for example by keeping k-means centroids per protein? Centroid or quantized multi-vector storage is the natural competitor at matched memory. We will compare against $k$ centroids with $k\cdot d = m$. Our advantage, if it exists, is an unbiased estimate of the inner sum with a single-vector first stage. A centroid set still needs multi-vector indexing.
Why not just grid-search $\tau$? With one knob, grid search is cheap relative to pretraining. It is less cheap once per-dimension scales are added and each point costs a full fine-tune. The overhead comparison above measures this directly. If an 8-run grid is both better and affordable, hypergradient tuning is a convenience, not a contribution.
Proposed Experiments
The first benchmark is SCOPe superfamily retrieval and Pfam clan retrieval under ProtoCol's group-disjoint splits, reported as Capped Recall@1. The second is CATH20 normalized top-1 accuracy, with MMseqs2 at 34.5% and knnProtT5 at 57.5% as reference points (Nearest neighbor search on embeddings). The third is Pfam20 AUC1 on full-length multi-domain proteins, with MMseqs2 at 0.520 and knnProtT5 at 0.367. We also stratify SCOPe by maximum sequence identity in bins of 10%, 20%, 30% and 40%, following In the twilight zone of protein sequence homology, and report AUROC and AUPRC per bin. Systems costs are bytes per protein, latency per query and tuning GPU-hours.
The decisive checks are four. First, the curve of recall against $\tau$ should show an interior optimum that moves to smaller $\tau$ under orthogonal features. If it does not, the variance story is wrong. Second, a $\tau$ tuned at $m_{\text{tune}}=512$ and deployed at $m=4096$ should underperform $\tau$ retuned at 4096. That would show the few-features-for-tuning shortcut of ensemble Kalman inversion tuning fails when the knob trades bias against variance. If the gap is negligible, we adopt the shortcut and say so. Third, on Pfam20 the soft per-residue score should beat learned single-vector pooling, since long multi-domain proteins are where storing one vector per protein is most tempting and mean pooling is weakest. Fourth, AUPRC in the 10% identity bin should not fall below that of mean-pooled models, so that recall gains are not paid for in false positives.
References
- ProtoCol: Late Interaction Retrieval for Protein Homolog Search
- Rethinking Attention with Performers
- Orthogonal Random Features
- The Geometry of Random Features.
- Nearest neighbor search on embeddings rapidly identifies distant protein relations
- Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformers
- Scalable Gradient-Based Tuning of Continuous Regularization Hyperparameters
- Hyperparameter optimization for randomized algorithms: a case study on random features
- Learning Adaptive Random Features.
- In the twilight zone of protein sequence homology: do protein language models learn protein structure?
- ProtSent: Protein Sentence Transformers
- BOHB: Robust and Efficient Hyperparameter Optimization at Scale