Homology search on object storage

DRAFT — AUTHOR REVIEW BEFORE PUBLISHING. No placeholders remain, and every number below is sourced: the catalog-scan attribution (~98% of wall time; 42.6 s → 236 ms) from docs/blueprints/dandelion-verify-compute-at-scale.md, the ≥99.973% frontier-preservation result from ThermoAlign/evidence/cath-s100-compact-vector-ladder-20260723.v2.json, and public corpus figures as cited.

Two things need your eyes. The opening account is written from the documented profiling result, not from a personal recollection — confirm it matches how it actually went. And the architecture described here is specified and partially built, so the piece is deliberately written in the present tense about design rather than about deployed capability. Remove this banner when both check out.

Biological search has quietly become a storage problem wearing an algorithms costume.

We found that out by being wrong about it. We had already built a homology search engine that kept its index in object storage, and it worked. It was also slower than we wanted, so we went looking for the hot spot with a clear hypothesis about where it would be: Smith-Waterman. Alignment is the quadratic stage, it is the part every profiler in this field has historically pointed at, and it is the part that looks expensive. We had spent months making it fast.

It was not Smith-Waterman. It was not the alignment stage at all. Nearly all of the time was going into the prefilter's own bookkeeping — reconstructing the seed-routing table and the posting-bucket directory, over and over, before any biology happened. The stage we had optimised hardest turned out to be statistically invisible in the profile.

That result reframed the whole project. The expensive thing about searching a large corpus from object storage is not comparing sequences. It is deciding which sequences to compare, and specifically the data structure you use to decide. Once we took that seriously, the question stopped being how to make our existing prefilter survive a blob store and became which prefilter belongs there in the first place.

What follows is the architecture that came out of it, and the reasoning that got us there.

Searching biology is a storage problem

The corpus stopped being the interesting part

The numbers are no longer in dispute. GenBank's 2025 update reports 34 trillion base pairs across more than 4.7 billion nucleotide sequences. UniProt release 2024_04 holds roughly 246 million UniProtKB records — and that is after deliberate filtering to limit redundant imports. The Sequence Read Archive passed 25.6 petabase pairs across more than 14.8 million public runs by September 2021. AlphaFold DB went from about 300,000 predicted structures in 2021 to over 214 million by 2024.

Those are the public corpora. They sit beside private pharmaceutical, clinical, metagenomic, screening, and design collections that nobody publishes counts for.

Growth alone is not an argument for changing anything. Plenty of systems absorb a 100× corpus by buying a bigger machine. The argument is what growth does to the shape of the cost.

Every tool we trust assumes the index is resident

BLAST, MMseqs2, and Foldseek made sequence and structure search practical at extraordinary scale, and none of this is a criticism of them — they are the reason the field can search at all, and they remain our comparison targets.

But look at what their strongest deployment traditions have in common. Prepared searchable representations get bound to memory, to local disks, to an HPC filesystem, to a GPU transfer path, or to a warm server. MMseqs2 earns its speed partly through carefully engineered database layouts that reward being close to the CPU. Foldseek's move — projecting structure into the 3Di alphabet so structure search becomes sequence search — inherits the same deployment shape. GPU acceleration pushes further in that direction, because GPUs reward large fixed batches and high arithmetic intensity.

Cloud offerings mostly distribute this workload rather than change it. ElasticBLAST is the honest version of that idea: take an existing search workload and spread it across cloud resources. The searchable state is still resident somewhere; you are renting the somewhere.

So the operating assumption across the whole field is: to search a corpus, you must first put it somewhere expensive, and keep it there.

The workload is idle-heavy, and nobody prices for that

Here is the part that took us longest to take seriously.

A lab does not query continuously. It queries in bursts — during annotation, during a screen, during a design loop — and then goes quiet for hours or days. Meanwhile it wants many corpus releases to stay searchable: this month's build, last quarter's build for comparison, two public references, and three private sets.

Serverless research outside biology has already characterized this shape. Production traces from a large cloud provider show workloads dominated by burstiness and highly skewed invocation rates, which is exactly why cold starts and idle cost became first-class design concerns there.

Under a resident-index architecture, that shape is the worst possible one. You pay for every release, continuously, whether or not anyone is searching. Idle capacity is not a rounding error in this model — for a bursty workload it is most of the bill. And because it is most of the bill, it silently decides science: which corpora stay searchable, how often they get refreshed, and how many releases can coexist.

That is the sentence worth sitting with. At sufficient corpus size, economics stop being an operational detail and become part of the algorithmic substrate.

The same pressure already moved every other kind of search

This is not a novel insight; it is an overdue import.

Analytical databases hit this wall and separated storage from compute — Snowflake made shared storage with independent elastic compute a defining property of a cloud warehouse. Dremel and BigQuery organized interactive analysis over very large datasets through distributed execution and columnar layout. More recent database work executes analytics directly over cloud object storage. In retrieval, turbopuffer applied the pattern to vector and full-text search: durable state lives in object storage, with memory and NVMe demoted to cache.

The storage tiers are what make the argument. Object storage is roughly two orders of magnitude cheaper per byte than memory, and roughly an order of magnitude cheaper than replicated SSD at realistic utilization. If your durable state is 200 TB and your query rate is bursty, the difference between those tiers is not an optimization — it is the difference between a corpus being searchable and not.

Biological search has the same corpus pressure, the same idle-heavy demand, and the same cascade structure. It did not get the same architecture.

Identifying the bottleneck

Before moving anything, we needed to know what a homology search actually spends its time and money on. The answer decided the entire design.

Here is the claim, and it is the load-bearing one in this whole post:

The filter stage decides your storage shape.

Not the aligner, not the scoring function, not the significance model — those are compute, and compute is portable. The filter is the only stage that has to touch the whole corpus, so its access pattern is the system's access pattern. Everything downstream is negotiable. That is not.

What an inverted index costs on object storage

Classical prefilters are built from exact symbol structure — k-mers, seeds, diagonals — and that machinery is an inverted index: a vocabulary on one side, posting lists of target ids on the other. It is the same structure that powers full-text search, and it has four properties that object storage punishes.

Fan-out. A query of length L emits on the order of L seeds, each a lookup into a different posting list living somewhere else. That is hundreds to thousands of independent reads for one query. On local NVMe you issue them and barely notice. Against a blob store each is a request with its own latency and its own price, and no batching trick turns a thousand unrelated key lookups into one sequential read.

Skew. Seed frequency in protein space is severely non-uniform. Common seeds have enormous posting lists and rare ones have almost nothing, so no single block size suits the vocabulary.

No bound on the unread. This is the deep one. Given a posting list you have not fetched, nothing in an inverted index tells you the best score it could possibly contain. You cannot prove it is safe to skip. Classical engines therefore prune heuristically — seed-count thresholds, ungapped extension cutoffs — which works beautifully when a wrong guess costs a cache miss and badly when it costs a paid round trip.

Locality by symbol, not by similarity. Two proteins sharing a common k-mer are frequently unrelated, so the list you fetch is organized by the token rather than by whether its entries are plausible answers. You pay object-storage prices for bytes you discard.

What we actually measured

We did not deduce this; we measured it, and the result was more lopsided than we expected. Profiling our own sequence engine at scale, we assumed the hotspot would be Smith-Waterman — it is quadratic, it is the part that looks expensive. It was not. Re-materializing the seed-routing table and posting-bucket directory was roughly 98% of wall time, while diagonal aggregation and Smith-Waterman were each below 0.1%. Materializing that metadata once per prepared release and sharing it read-only across a batch collapsed per-query catalog scan from about 42.6 seconds to about 236 milliseconds.

The fix was routine. The shape of the finding was not. In a seed-routed engine most of what you spend goes on the filter's own bookkeeping — and that bookkeeping is precisely the part that does not want to live in a blob store.

So the interesting question was never how to make k-mer postings survive object storage. It was whether a different filter has a natural access pattern that object storage already rewards.

Embeddings to narrow the search space

Object storage did not get cheap this year. The thing that changed is what a router can be — and the rest of the industry built the replacement while we were looking elsewhere.

If the filter is a learned residue embedding rather than a discrete seed, candidate generation stops being a vocabulary lookup and becomes approximate nearest-neighbour search over a continuous space. That is a different structure with different physics — and it is the exact structure every vector database of the last four years has been optimizing for blob storage.

The canonical shape is SPANN: partition the vectors into clusters, keep the centroids resident, put the posting lists on disk, and at query time score against the small centroid head first, then read only the lists it selects. SPFresh extends the same family with in-place incremental updates, splitting oversized and merging undersized clusters as the corpus moves.

Against the four properties above:

	k-mer postings	centroid hierarchy
Reads per query	hundreds–thousands, scattered	a handful, contiguous
Block sizing	Zipfian, no good choice	uniform by construction
Skipping	heuristic	geometrically provable
Locality	by symbol	by similarity

The last row compounds. When vectors are clustered by similarity and packed into contiguous blocks, the bytes you fetch are bytes you wanted.

This is the infrastructural case for embeddings in homology search, and it is not the case usually made. The usual argument is sensitivity — that learned representations find remote homologs seeds miss. That may well be true, and we measure it separately. The storage argument is independent and, for us, larger: embeddings put candidate generation into a shape that a mature, published body of systems work already knows how to serve cheaply from a blob store. We did not have to invent a storage engine for biology. We got to inherit one.

Learned residue embeddings change the economics of the first stage. Our default cascade is:

query
  -> ESM2-8M residue embedding
  -> recall-oriented object-native ANN
  -> exact bidirectional salience-weighted MaxSim
  -> embedding-scored affine Smith-Waterman
  -> database-aware significance

Each stage is a progressively more expensive and more faithful comparison, and each owns exactly one job. The embedding represents contextual residue compatibility. The ANN proposes a broad candidate set and is never the final biological score. MaxSim performs real residue-level late interaction without imposing order. Smith-Waterman restores order, affine gaps, coordinates, and coverage. Significance calibrates survivors against the space actually searched.

One clarification, because it is easy to over-claim here: we do not think the evidence shows embeddings learn diagonals. What it shows is narrower and more useful — global late interaction preserves enough local correspondence that ordered dynamic programming can recover the order signal downstream. That is why there is no default k-mer or diagonal lane. A new lane has to independently improve the frozen frontier at a justified cost, not merely exist because another system has one.

More vectors can make late interaction worse

There is an appealing but wrong extrapolation from this architecture: if residue embeddings are useful, retaining every residue and giving every one an equal vote must be best. We tested that directly, and it is not.

The simplest exact late-interaction score is a sum of query-to-target maxima:

On a frozen ASTRAL95 experiment with 35,494 targets, 100 queries, and ESM2-8M residue vectors, we increased each query from its 8 most salient residues to 16, 32, 64, and finally every available residue. Targets stayed fixed at their 32 most salient residues, so the experiment isolates what happens when the query side becomes indiscriminate.

Query representation	Exact top-100 candidate survival	Direct nDCG@10	Direct Recall@100	ANN bytes read
Top 32 residues	97.95%	0.4529	0.6648	305.1 MB
Top 64 residues	96.41%	0.4448	0.6745	307.2 MB
Every residue	93.72%	0.3982	0.6074	307.7 MB

The all-residue run is not losing because object storage refuses to supply more data. Read volume changes by less than one percent from 32 residues to all residues. It loses twice: useful candidates are displaced during routing, and the final exact score becomes less discriminative.

The reason is an extreme-value effect. For an uninformative query residue, one of a target's residue vectors will often have a moderately positive cosine by chance. MaxSim deliberately selects that accidental maximum, positive clipping prevents negative evidence from cancelling it, and summing across hundreds of low-salience query residues accumulates a document-dependent background score. The conserved residues still contribute signal; they are now competing with much more structured noise.

Routing suffers from the same effect one stage earlier. A fixed set of shared coarse parents is selected from the strongest token-to-centroid matches. With every residue eligible, an unusual or low-salience token can win a parent slot through one extreme match and displace a partition that represented the conserved core. More query vectors then mean more competition for the same routing budget, not automatically more evidence.

This experiment is asymmetric — every query residue is compared with only the top 32 target residues — and that makes the failure sharper. A low-salience query residue whose real counterpart was omitted from the target representation must match something unrelated. Restoring every target residue may recover some of those correspondences, but it does not remove MaxSim's extreme-value background. That requires the representation and the aggregation rule to be trained together.

The architectural conclusion is not to retreat to one-vector retrieval. It is to separate having a rich representation from giving every vector equal authority. Route with a compact, learned or salience-selected subset; verify the survivors with a richer bidirectional interaction; and weight or train that interaction so conserved residues dominate. Full late interaction is a model design problem as much as an indexing problem.

A router that can bound what it hasn't read

Our ANN engine is a small standalone Rust library for immutable object storage, implementing one algorithm: two-level spherical IVF over normalized vectors, with coarse routing partitions and independently bounded microblocks. That is the SPANN lineage, made object-native and given two properties we needed.

The query path is a funnel that narrows before it reads:

query vector
  -> exact cosine over the small coarse-centroid head
  -> retain coarse partitions to a row target
  -> exact cosine over their micro-centroids
  -> nearest microblocks to a candidate/byte target
  -> one-bit residual sketches for cheap ordering
  -> estimate request waves and bytes from a storage profile
  -> choose candidate ranges or exhaustive scan
  -> fetch and exact-score only the selected rows

The skip bound is a proof, not a heuristic. Every unread microblock carries a conservative upper bound on the best score it could contain, from the spherical triangle inequality:

min(1, cos(max(0, acos(query · centroid) - leaf_angular_radius)) + margin)

A block is skipped only when that bound falls below the current kth exact score. This is the property an inverted index cannot give you at any price, and it is the difference between "we stopped because the budget ran out" and "we can demonstrate that nothing unread could have changed the answer." The engine makes that explicit: a strict mode fails the query outright rather than returning a frontier it could not prove within the byte budget, and the permissive mode still reports the remaining bound and the count of unresolved microblocks.

Bytes are forecast, not discovered. Because the geometry is known before any payload is fetched, the engine estimates request waves and byte volume against a release-bound storage profile, then chooses — candidate ranges when they are cheaper, a sequential scan when they are not. An index that predicts its own consumption is an index you can put a budget on, and the budget is what makes the thing operable.

There is a third property that is easy to miss and is arguably the entire thesis in one line. The engine has no protein, residue, late-interaction, alignment, significance, or ranking logic in it. It takes opaque ids and vectors and returns opaque ids and cosine similarities. Once the filter is embeddings, the index does not need to know it is doing biology. That is what inheriting the infrastructure actually means: the hard, general, well-studied part stays general, and the biology lives entirely in the stages above it.

Does the router cost us anything?

An approximate filter is only worth having if you can say precisely what it loses, so we measured it against the exhaustive answer.

On CATH-S100 4.4.0 — 122,651 targets, 600 queries, five group-disjoint folds — we compared the returned frontier against exact exhaustive retrieval over the same compact vectors, across eight representation arms. The router preserved at least 99.973% of the exact top-2,048 frontier in every arm.

That number is the point of the exercise. The object-storage ANN is, for practical purposes, not where the error is. Whatever we still lose against a perfect system, we are not losing it in routing — and we should not spend the next year optimizing the index. For an infrastructure argument, "our infrastructure is not the bottleneck" is the strongest available result.

Putting it all together...

Durable search state is an immutable release in object storage. Query workers are allocated for a demand window and released afterward. Cache is a latency optimization and never a correctness requirement.

We use "serverless" in a narrow systems sense, with four invariants you can actually check:

1. An idle release has zero query-worker allocation.
2. A cold query starts from the release manifest and a bounded set of routing objects — no warm state required.
3. Every response records its physical execution: object reads, bytes read, cache state, candidate counts, verifier work, warnings, and versions.
4. Adding concurrent queries adds workers, and leaves release identity fixed.

A release is a small set of object kinds:

Release object	Contents
Manifest	corpus identity, source hashes, object graph, versions, parameters
Routing directory	compact summaries for coarse shard selection
Shard synopsis	feature ranges, token buckets, candidate-count estimates
Candidate blocks	record identifiers and low-cost evidence for verification
Payload blocks	sequence, token, residue, and coordinate data for kernels
Verifier bundle	kernel version, thresholds, scoring parameters, warnings

The bridge to data systems is deliberate and worth stating plainly: the release is durable state, the worker is elastic compute, and the read plan is the query plan.

Every query walks the same path. Pin a release. Extract query features. Read the routing directory. Select shard synopses under a budget. Read candidate blocks. Enumerate records. Fetch payload blocks. Verify.

The planner declares a budget before executing:

B(q) = (max_objects, max_bytes, max_candidates, max_verify_work)

and the response reports what actually happened:

R(q) = (objects_read, bytes_read, candidates, verify_work, cache_state)

Those two tuples are the whole discipline. Coarse routing keeps the first read set small. Shard synopses estimate candidate yield before paying for payload bytes. Candidate blocks defer the large biological payloads until something has earned them. Verification consumes the expensive inputs only after routing has cut the corpus down.

This is where storage/compute separation stops being a slogan: the query pays for the bytes it selected and the verifier work it ran. The rest of the corpus stays durable and costs storage.

Approximation you can audit

Moving an index into object storage introduces a real temptation: quietly let "we read fewer bytes" become "we returned fewer answers," and report the same score field either way.

So every execution ends with exactly one typed outcome, and two of them matter here:

• complete_exact — exhaustive under the named semantic profile and target universe.
• complete_for_policy — deterministic and complete under a named approximate search policy.

complete_for_policy is never relabeled as exact. A partial frontier is never returned as a successful scientific result because a budget expired. And the exhaustive path stays permanently callable, as a differential reference, after the fast approximate paths exist — which is the only way a recall claim about an approximation means anything.

What it costs

The comparison uses identical units on both sides. For a release with N measured queries:

C_query = C_worker + C_verify + C_get + C_bytes + C_cache + C_build/N

The resident baseline pays provisioned memory, provisioned local storage, replication, and idle serving capacity across the window. The serverless execution pays worker milliseconds, verifier time, object requests, transferred bytes, optional cache footprint, and amortized release construction.

Written this way, the model also states its own conditions for winning: many searchable releases, bursty demand, large corpora, bounded candidate payloads, and verification that only runs after routing. It states its losing conditions just as clearly, which is the point of writing it down before measuring.

We are not going to put a benchmark table here yet. The comparison that matters is a matched one — same corpora, same baselines with their real parameters, recall against those baselines, cold and warm read volumes, resident memory, cost per query, and idle cost per release per day, all moving together. We have the cost model and the harness; we do not yet have that table in a form we would defend in public, and publishing a partial version of it would be exactly the selective reporting the next section argues against.

One admission we can make without it: object storage has a real cold-path cost. A first query against an unwarmed release pays centroid-head and routing reads that a resident index simply does not, and no amount of clever planning removes that floor — it only bounds it.

...until the router becomes the whole argument

It would be dishonest to present this as a free win, so here is where we would tell you to use something else.

Start with the cost we introduced. A k-mer prefilter is deterministic string extraction — effectively free, on ingest and at query time. We replaced it with a neural forward pass, which has to run over every record in the corpus when a release is built and over every query when one arrives. That is a real new expense, and it lands in exactly the place a resident-index engine would never have paid it. The trade is only favourable because object reads were dominating so completely that moving work out of the storage layer and into compute was worth doing at almost any price. On a corpus small enough that the index fits in memory, that trade is simply bad.

Which is the first place we would tell you to use something else. This architecture is also weakest for microsecond-latency services; for exhaustive all-against-all verification, where routing has nothing to prune; and for GPU kernels that need large fixed batches to be worth their transfer cost. It is exposed to object-store tail latency in a way a resident index simply is not.

Most importantly, it is sensitive to routing quality in a way that compounds. A weak router increases bytes read, candidate counts, verifier work, and tail latency — all before recall starts improving. Under a resident index a mediocre prefilter costs you some CPU. Here it costs you the entire economic argument.

That is the trade this design makes, stated plainly. We moved the cost of a homology search out of the aligner and into the router, and everything now rests on how good that router is.

That is also why we refuse to report these measurements separately. Recall alone hides an expensive read plan. Latency alone hides degraded search. Cost alone hides scientific loss. The claim only holds if recall, latency, read volume, resident memory, idle cost, and cost per query move together.

Conclusion

We set out to make a known workload cheaper. What we got was a different design surface.

Classical sequence and structure search methods were shaped by the memory hierarchy of local machines, HPC filesystems, and resident indexes. Once durable state is an immutable release and execution is an explicit read plan, other things become tunable: release builders can materialize several routing resolutions side by side; planners can spend more bytes on ambiguous queries and fewer on easy ones; verification kernels stop being coupled to durable storage.

And routers — deterministic, learned, sequence-feature, structure-token, residue-level, hybrid — all become comparable under one envelope, because they are all just read-plan policies attached to a reproducible release.

That last point is the one we are most interested in. The algorithmic object stops being "an index" and becomes a measurable read-plan policy.

Three deep dives follow, each on one mechanism:

• One vector is almost enough — mean-pooling a protein should destroy the domain-level evidence homology search exists to find. We built the compact-vector ladder to fix that, measured it, and found sharply diminishing returns and a learned split that did not beat a deterministic one.
• E-values you can actually defend — why a pairwise p-value multiplied by a database size is not a significance estimate, and what it takes to calibrate against the space a search policy actually touched.
• Approximate to find, exact to score — quantized routing with lossless residual reconstruction, so the exact score survives bit for bit.