ShiftCache: Fast and Exact Indel Effect Prediction by Reusing Shifted Reference Encodings
Authors: Sina Barazandeh, Arth Banka, Jose Lugo-Martinez
Organizations: Ray and Stephanie Lane Computational Biology Department, Kenneth C. Griffin School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA · Department of Immunology, University of Pittsburgh School of Medicine, Pittsburgh, PA, USA
Sequence-to-function models such as AlphaGenome and Borzoi read up to a megabase of DNA and score a genetic variant by comparing their predictions for the reference and alternate sequences. Insertions and deletions (indels) are costly to score, because an indel usually shifts the unchanged DNA after it onto a different pooling grid, which prevents direct reuse of the reference's encoder activations. The AlphaGenome Atlas scored more than 100 million indels with three full model passes each, although the DNA after an indel matches the reference shifted by the indel's length. We present ShiftCache, an exact reuse system that encodes each shifted reference once and shares it among all variants scored in the same window with the same shift. ShiftCache copies every encoder output a variant can reuse and recomputes the rest in batched tiles. On held-out AlphaGenome windows shared by many indels, in strict fp32 on one A6000, ShiftCache is 3.5 to 6.5× faster than deduplicated dense execution and 1.6 to 2.7× faster than our adaptation of layer-by-layer reuse to indels. It is 3.5 to 4.1× faster than dense reimplementations of two published analyses with Borzoi and AlphaGenome, and 2.6× faster than dense execution with Enformer. Scoring each variant in its own centered 131 kb window makes ShiftCache only 1.36× faster than deduplicated dense execution, and highly diverse insertion lengths or many dispersed edits can make it slower than layer-by-layer reuse or dense execution. For encoders that meet our conditions, ShiftCache computes the same predictions as dense execution in exact arithmetic. On an A6000, every checked output of the default AlphaGenome and Borzoi runs matches dense execution within an absolute and relative tolerance of 10−5. With larger tile batches, with Enformer or on an H100, a small fraction of values exceeds this tolerance.
Figures & tables
Figure 1: One shifted encoding serves many requests. To assemble a deletion’s left-anchored alternate encoding, bins whose dependency intervals lie before the deletion are copied from the reference, and bins whose intervals lie after it are copied from the reference shifted left by k . This shifted encoding is built once and shared by every request with the same offset, such as a deletion of k bases elsewhere in the window (row E(alt′) ), and also serves as the stitching protocol’s right-matched reference. For AlphaGenome, about nine bins have dependency intervals that cross the edit and are recomputed in stride-aligned tiles with a five-bin halo. The inset shows that deleting an input base changes the pooling groups, while S−k matches the alternate’s groups. Copying an output bin requires its entire dependency interval to match.
Figure 2: ShiftCache is 3.5 to 6.5 × faster than Dedup dense (dashed line) and 1.6 to 2.7 × faster than layer-local reuse. Speedup over Dedup dense on held-out stitched AlphaGenome campaigns (RTX A6000, strict fp32, geometric mean of four windows, 95% intervals). Table 1 lists the times, and Figure 6 plots them.
Figure 3: Shared views shrink encoder work, and transformer and head time stays the same. Time per campaign by component, AlphaGenome, 256 real indels, 131 kb, one A6000, mean of four held-out windows. Dedup dense’s encoder and tail run together inside its full passes.
Figure 4: Larger campaigns spread view construction over more requests. ShiftCache speedup by campaign size on held-out 131 kb windows (AlphaGenome, one A6000; both axes logarithmic). Solid lines show the speedup over Dedup dense and dashed lines the speedup over Three-pass dense; faint points are per-window ratios over Dedup dense.
Figure 5: Seconds per stitched campaign of 128 random insertions whose lengths take D distinct values (geometric mean of two held-out windows, 131 kb). Building views stops saving time when too few requests share an offset.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
256 real indels
512 deletions
Setting
Dedup dense
ShiftCache
Dedup dense
ShiftCache
Default (batch 8, chunk 32)
82.8
17.2
84.4
14.3
Batch 1
83.3
16.9
82.9
13.7
Batch 2
83.9
17.4
83.4
14.1
Chunk 16
83.6
17.2
88.1
14.8
Chunk 128
81.4
17.0
82.0
14.1
Appendix
Table 3: Seconds per campaign for Dedup dense and ShiftCache on the first development window at 131 kb, as the median of three campaigns (RTX A6000, strict fp32). The table shows selected settings of the sweep. Batch is the number of sequences per full pass, and chunk is the number of requests stitched together.
Method
First campaign
Later campaigns
Three-pass dense
238
n/a
Dedup dense
222
78
ShiftCache, saved cost table
194
17
ShiftCache, calibrating in process
347
17
Appendix
Table 4: Each first-use run starts in a fresh process with empty compilation caches. It scores 256 real indels in the first held-out window at 131 kb (RTX A6000, strict fp32). Times are seconds per campaign and exclude model loading, which takes about 7 s.
Figure 6: Seconds per stitched campaign on four held-out windows (geometric mean), with AlphaGenome in fp32 on one RTX A6000. Here n is the number of requests. Labels give ShiftCache’s speedup over Dedup dense, and Table 1 gives the 95% intervals of these speedups. Three-pass dense was measured separately on the same windows, and all other methods were measured together.
Tile sizes, tile batch
Real indels
Deletion scan
Matched insertions
Failing fraction
32/128, 16 (default)
1.00 (40.3 s)
1.00 (36.5 s)
1.00 (16.6 s)
0
32/128, 8
1.02
1.01
1.02
0
16/64, 16
1.01
0.99
0.95
0
16/128, 16
0.98
0.97
0.94
0
64/256, 8
1.09
1.19
1.23
0
64/256, 16
1.08
1.18
1.21
0
Appendix
Table 5: Campaign time relative to default layer-local reuse, on two development windows at 131 kb (geometric mean over windows). Each row gives the small and large tile sizes in trunk bins, then the tile batch. The default uses 32-bin and 128-bin tiles with a tile batch of 16. With tile batches above 16, outputs fail the tolerance against Dedup dense. The last column gives the fraction of reference and alternate output values that fail, pooled over both windows and all three workloads. ShiftCache keeps a tile batch of 16 for the same reason.
Configuration
Real indels
Deletion scan
Default (tiles 32/128, partial views)
4.83
5.88
Transformer batch 4
4.90
5.96
Transformer batch 16
4.89
5.90
Tiles 16/64
4.33
5.10
Tiles 64/256
4.30
5.09
Full-length views only
4.93
5.88
Appendix
Table 6: ShiftCache speedup over Dedup dense on the first development window at 131 kb, with static view selection. The last row gives the time of greedy view selection divided by the time of static view selection, so a smaller value is better. Tile sizes are in trunk bins.
Workload
Over Dedup dense [95%]
Over Three-pass dense
Real indels (37 to 59 per window)
1.67 [1.62, 1.71]
2.5
Deletion scan (256)
1.93
4.1
Matched insertions (64)
1.92
2.9
Appendix
Table 8: ShiftCache speedups for Borzoi on held-out 524 kb windows with baskerville’s stitching convention. Output comparisons use each track’s sum over positions. The 95% interval is reported for real indels.
Figure 7: Per-base deletion scores from ShiftCache’s outputs against MPRA-measured deletion effects, for positions measured with at least 10 barcoded reporter copies. Each score is the mean of log2(At+1)−log2(Rt+1) over the tracks that the published protocol selects, which are K562 tracks for HBG1 and adrenal gland tracks for LDLR. For track t , At and Rt are the alternate and reference signals summed over the central 4 kb, using only bins that overlap the gene’s exons for RNA tracks. A negative score means that the deletion lowers predicted activity. Each point is one deleted base, r is the Pearson correlation, and the two panels use different axis ranges.
Genome foundation models are growing into sparse mixture-of-experts (MoE) networks whose expert weights no longer fit on the machines that hold the sequences, yet sending a private genome to rented accelerators exposes it: we show that a single server hosting one expert recovers the input nucleotides with 99.8% top-1 accuracy. We present CipherGenome, a protocol that keeps the embedding, attention and router of a 15.1B-parameter MoE genome model on a trusted thin client and outsources every expert projection, 95.8% of the parameters, to untrusted and possibly colluding GPU servers under module-LWE encryption. The design exploits three structural facts: expert layers are linear between two SwiGLU gates, expert weights are public, and GPU integer tensor cores can evaluate a ciphertext-weight product exactly modulo 248 in a single GEMM. The client evaluates the nonlinearity exactly and re-encrypts with fresh secrets, so no polynomial approximation or bootstrapping is ever needed. On 72 windows from 12 bacterial genomes, encryption adds 2.54×10−4 nats per token of KL divergence (95% CI upper bound 3.95×10−4), below a pre-registered non-inferiority margin and indistinguishable from bf16 inference, while the same inversion attack falls to chance level. A reusable public hint cuts end-to-end latency by 3.54 times, wire compression reduces traffic 6.8 times, per-layer padding reduces routing leakage from 54.9% to 8.9% accuracy, and HE-compatible int4 experts remain non-inferior to their plaintext counterparts. Per expert and token, the server-side cost is more than six orders of magnitude below a CKKS baseline.
Guang Yang, Fengchen Liu
University of California, Los Angeles · University of California, Berkeley
Cross-context KV-cache reuse predicts a shared segment's keys and values under a new prefix instead of recomputing them, and has been reported to do so without quality loss. We find otherwise, and identify two problems. (1) A hidden cost: on MMLU and GSM8K, reuse costs substantial accuracy. (2) A decision at the wrong unit: no rule for deciding whether to reuse a cache removes that cost. What does help is choosing which parts of the cache to recompute, and the value of choosing well falls as the unit of choice grows: informed selection removes 49.5% of the cache error beyond chance at single rows (one token's keys and values), 10.6% at 64-token chunks, and nothing at the level of whole calls. Budgeted Cache Repair (BCR) acts at the unit where selection still pays. It drafts two tokens from the assembled cache, ranks cache rows by the attention those tokens pay them, and recomputes a fixed budget of rows exactly, in one of three layouts. The cost is paid rather than predicted away, and the draft that fails as a gate succeeds as a selector. BCR restores GSM8K to dense-prefill accuracy while still serving most calls from cache, and its best layout outperforms every reuse baseline's mean in the reference grid. The draft also beats a coin-flip selector at the same budget - a control prior evaluations lack.
Long-context agentic workflows have emerged as a defining use case for large language models, making attention efficiency critical for both inference speed and serving cost. Sparse attention addresses this challenge effectively, and DeepSeek Sparse Attention (DSA) is a representative production-grade solution: a lightweight lightning indexer selects the top-k most relevant tokens per query, reducing core attention from O(L2) to O(Lk). However, the indexer itself retains O(L2) complexity and must run independently at every layer, despite the fact that the resulting top-k selections are highly similar across consecutive layers. We present IndexCache, which exploits this cross-layer redundancy by partitioning layers into a small set of Full layers that run their own indexers and a majority of Shared layers that simply reuse the nearest Full layer's top-k indices. We propose two complementary approaches to determine and optimize this configuration. Training-free IndexCache applies a greedy search algorithm that selects which layers to retain indexers by directly minimizing language modeling loss on a calibration set, requiring no weight updates. Training-aware IndexCache introduces a multi-layer distillation loss that trains each retained indexer against the averaged attention distributions of all layers it serves, enabling even simple interleaved patterns to match full-indexer accuracy. Experimental results on a 30B DSA model show that IndexCache can remove 75% of indexer computations with negligible quality degradation, achieving up to 1.82× prefill speedup and 1.48× decode speedup compared to standard DSA. These positive results are further confirmed by our preliminary experiments on the production-scale GLM-5 model (Figure 1).