CS Paper Radar

SparseDesign: Scaling Exact Coding-Sequence Design

Hao Lin, Jingjin Yu

cs.DS ·submitted 2026-09-26 07:08 UTC · v1
theory

Abstract

Exact optimization of synonymous coding sequences under a joint folding-energy and codon-usage objective is limited by expensive dynamic-programming splits and large working sets. \textsc{SparseDesign} applies candidate sparsification to the multiloop recurrence of a Turner~2004 dangle-0 solver over a weighted codon automaton. A direct branch is retained only when it strictly improves on every partitionable or endpoint-unpaired realization of the same endpoint states. We prove equivalence to the dense recurrence in real arithmetic, under an explicit scalar branch-interface assumption. With $N$ automaton states, edge set $E$ and $Z$ retained candidates, multiloop work is $O(N^2+N|E|+NZ)$; worst-case time remains cubic for bounded-width automata and total memory remains quadratic. Endpoint ownership permits parallel candidate construction without locks. While synthetic stress families can benefit little from sparsification and exhibit near-quadratic candidate growth, natural proteins show substantial candidate-count reductions. In our 7,600-task campaign, the 2,000-protein human-table panel has median retention of only 3.53\% at $λ=0$ and 2.15\% at $λ=4$, corresponding to approximately 28.3-fold and 46.4-fold reductions relative to all feasible direct intervals. The primary performance experiments use an AMD EPYC 7313 server. For human Dp427c (11,031 nt, $λ=0$), 16-thread packed \textsc{SparseDesign} achieves five-run medians of 236.54 seconds wall-clock time and 14.43 GiB peak RSS. Compared with the single-thread local dense LinearDesign fork on the same server (4,912 seconds, 402.10 GiB RSS), this gives a 20.8-fold wall-clock speedup and a 27.9-fold peak-memory reduction. On a Core i9-14900KF commodity PC with 64 GiB RAM, the same input, layout and thread count achieve 126.42 seconds and 14.43 GiB RSS.

Closest papers

Nearest neighbours by meaning across the whole index.

A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond $N^{4/3}$

cs.CC cs.DScs.LG ·2026-09-24 ·Bo Liu
theory similarity 0.60
Abstract · 25 pages, 2 tables; full proof and technical appendix

Choosing Shellsort gaps is a well-known open problem. For over sixty years, successful sequences have relied on human-designed formulas, numerical searches, or number-theoretic constructions. Although stronger general bounds exist for dense or mainly theoretical families, the worst-case upper bound for a short, sparse, and practically competitive construction has not advanced beyond $N^{4/3}$ for decades. We ask whether the sequence itself can instead be learned from execution. We present an RL-driven, self-supervised system that searches over executable gap generators. Every proposal is valid by construction, and executed candidates return exact comparison and move counts; no classical sequence is used as a target. Across five independent searches, the system discovers a common rational-geometric family. A second self-supervised stage tunes only a finite prefix, producing the practical sequence $1,3,8,20,47,116,300,585,1416,3303,\ldots$. Once frozen, it obtains the lowest equal-task average operation count among seven classical baselines on 25 large tasks with $10^7<N\leq 10^8$. We complete the learned tail without changing its practical behavior: only beyond $10^{1000}$, a zero-density set of unit companions $h_s+1$ removes the remaining congruence barriers. The resulting sparse sequence has matching polynomial upper and lower exponents, up to polylogarithmic factors: $Ω(N^{1.024296451657\ldots}) \leq T(N) \leq O(N^{1.024296451657\ldots}\operatorname{polylog} N)$. The lower bound follows from Zang's recent theorem for rational-geometric sequences; our contribution is the matching upper bound. Thus one exact sequence connects self-supervised discovery, large-scale practical performance, and a substantial step below the classical $N^{4/3}$ bound for sparse practical Shellsort sequences.

0.54

DanLing NestedTensor: Composable Multi-Ragged Tensors for Deep Learning

cs.LG cs.AIcs.PF ·2026-09-24 ·Zhiyuan Chen
similarity 0.59
Abstract

Variable-size inputs are common in deep learning, but dense batching allocates a shared envelope and spends computation on padding. The cost multiplies across varying axes: an explicit pair state allocates $BN_{\max}^2$ positions instead of $\sum_i N_i^2$. Packing removes that waste, but composing packed operations still requires the logical axes and sample boundaries a flat buffer no longer exposes. We present DanLing NestedTensor, a PyTorch tensor abstraction that makes multi-ragged structure a property of the tensor itself. Packed values carry tensor-backed partitions and logical dimension order, so broadcasting creates ragged axes, feature transformations retain them, and reductions consume them. The same representation carries through autograd and both eager and compiled execution. On an A100, the geometric-mean speedup over same-mode padding is 2.74$\times$ eager and 3.39$\times$ compiled across four BERT scales, and 1.97$\times$ eager across four FCN backbones. A four-block Pairformer-style workload runs 2.40-4.32$\times$ faster than a padded reference using native PyTorch kernels across square length regimes in eager execution, with peak allocation falling from 38.08 to 5.41 GiB on its high-variation batch. The tensor interface lets model code built from its supported operators compose efficient variable-size computation without managing offsets at any call site. Code will be released publicly upon publication.

0.27

Step Recursion: Resource Profiles and Descent Quotients

cs.CC cs.LO ·2026-08-23 ·Kirill Osipov
similarity 0.59
Abstract · Companion to arXiv:2608.04871

We develop a resource representation for step recursion in which mutable-state width and recursion descent are explicit and independent parameters. A width bound $u$ controls the size of the encoded machine state, while an effective descent $ρ$ determines the available recursion depth $δ_ρ(u)$. For generalized-inverse descents, we derive the depth directly from generator growth and characterize the increasing sequences that can occur as generator orbits. We then connect this depth--width geometry to standard finite-branching computation. Every deterministic bounded-state dynamics is realizable by a single ordinary bounded step recursion over a fixed finite numerical basis. Using deterministic, existential, universal, or alternating aggregation on the same local dynamics yields the corresponding machine semantics. After closure under the width reparameterizations needed to absorb fixed local cost, the resulting language classes are exactly the machine time--space classes on profiles $(δ_ρ(u),u)$. Finally, profile domination quotients effective descents by admissible width reparameterization. Some depth curves collapse, yet polynomial widths support an explicit infinite strict hierarchy between the canonical polynomial- and exponential-depth profiles. Thus descent remains a nonredundant resource coordinate after polynomial width reparameterization; standard complexity classes are calibration points.

0.33

ProtLingo: Efficient Protein Language Modeling via Conditional Memory and Expert Routing

cs.AI ·2026-09-04 ·Mingrui Li, Sixian Shen, Minzhang Li, Ruiyi Zhang, Kexin Zhang +2 more
similarity 0.59
Abstract

Proteins perform diverse cellular functions, and even single amino-acid substitutions can alter stability, activity, or molecular interactions. Protein language models (PLMs) provide a scalable approach for modeling such sequence--function relationships from unlabeled sequences, but increasing the size of dense Transformer backbones often brings substantial computational cost without consistently improving mutation-sensitive prediction. We introduce ProtLingo, an efficient PLM framework that augments a pretrained single-sequence backbone with conditional local memory and sparse expert routing. ProtLingo maps contextual residue representations into route-specific discrete codes, composes centered local windows into latent $N$-gram addresses, and retrieves reusable residual signals associated with recurring local sequence contexts. In parallel, selected feed-forward blocks are upcycled into sparse Mixture-of-Experts layers with shared and routed experts, enabling residue-dependent computation while activating only a subset of parameters. Experiments on protein fitness prediction, FLIP benchmarks, and supervised contact prediction show that ProtLingo achieves competitive performance with a 150M-scale backbone, including strong parameter efficiency on mutation-effect prediction and preserved long-range structural representations.

0.18

A Factor-5 Conversion to Internal Collage Systems

cs.DS ·2026-10-03 ·Simone Faro
similarity 0.58
Abstract

A collage system is a grammar-based compression model that extends straight-line programs with repetition and substring truncation. Internal collage systems additionally require every nonterminal to be structurally reachable from the start symbol. Migita, Uehata, and I (CPM 2026) showed that any collage system of size $m$ can be converted into an internal one generating the same string with size at most $9m$, and left the improvement of this constant as an open problem. We show that a simple refinement of their top-down conversion reduces the bound to $5m$. The proof combines three elementary ideas: canonicalization of generated truncations that remain aligned with a target endpoint; a repetition decomposition that absorbs every complete copy of the repetition base into a maximal core; and monotonicity of structural reachability, which prevents an input truncation rule from both becoming structurally reachable and later acting as a hidden target at which endpoint alignment is lost. The conversion runs in deterministic $O(m^2)$ worst-case time in the stated unit-cost random-access machine model. Consequently, for every string, the minimum size of an internal collage system is at most five times the minimum size of a general collage system.

0.23

LinearKnot: Linear-Time Approximation of the Pseudoknot Partition Function

cs.DS ·2026-11-12 ·Milan Gautam, David H. Mathews, Liang Huang
code/data similarity 0.58
Abstract

Pseudoknots, where two or more helices cross, are central to many functional RNAs, including frameshifting signals, telomerase RNA, riboswitches and viral genomes. With arbitrary pseudoknots, finding the minimum free energy structure is NP-hard, so most RNA secondary structure prediction tools only consider pseudoknot-free structures. Dirks and Pierce (DP03) pioneered the first pseudoknot partition function, which underlies NUPACK's pseudoknot model, but it takes $O(n^5)$ time and $O(n^4)$ memory, making it practical only for very short sequences. Linear-time approximate dynamic programming, as in LinearFold and LinearPartition, does not transfer easily to DP03: a partial pseudoknot leaves a gap filled by its crossing partner, whose complementary sequence may still lie ahead of the scan, so it cannot be ranked by its inside weight. We present LinearKnot, a linear-time approximation of DP03 in three passes: (a) LinearPartition gives pseudoknot-free weights; (b) a second pass builds tables that estimate each partial stem's crossing partner; and (c) a third scans a left-to-right reformulation of DP03 that reserves the 5' nucleotides in the pseudoknot helix for subsequent pairing, keeping the states with the largest estimated contribution. Without pruning, this reformulation computes DP03's pseudoknot recursion exactly, so the only approximation is which states the beam keeps. End-to-end, time grows linearly ($n^{1.01}$) and memory marginally above linear ($n^{1.15}$) from 1,000 to 9,392 nt. LinearKnot folds the 9,392 nt Rous sarcoma virus genome in 2.4 hours and 90.5 GB, where exact DP03 would need an estimated 40,000 years and 54 million GB, and matches exact DP03 base-pair probabilities on 418 PseudoBase RNAs with a median RMSD of $9.2\times10^{-7}$. Our code is available at https://github.com/gautammilan/LinearKnot.

0.38

DScale: Scaling Block-Diffusion Speculative Decoding with Adaptive Verification

cs.DC cs.AI ·2026-09-29 ·Rongjian Chen, Minxian Xu, Zhengxin Fang, Kejiang Ye, Chengzhong Xu
similarity 0.57
Abstract · 12 pages

Growing large language model applications demand efficient inference. At high concurrency, block-diffusion speculative decoding suffers from verification padding, rejected candidates, and incompatibility between variable prefixes and fixed-shape graphs. Uniform truncation sacrifices acceptable tokens. We present DScale, preserving drafter architecture, weights, and full draft length. A separate 112K-parameter predictor requires neither confidence calibration nor hardware speed-curve preparation. Path-aware tiles reduce padding. Dynamic verify-length (DVL) allocation packs scored prefixes into half the native verification capacity. Fixed-address workspaces propagate changing boundaries through verification and acceptance while reusing captured graphs. On A100-40GB with tensor parallelism 1, Qwen3-8B and Qwen3-4B cover four datasets and concurrency 8-32, reusing each target's frozen predictor. Geometric-mean throughput gains across these configurations are respectively 43.9% and 48.8% over DFlash, 22.2% and 37.7% over DSpark, and 24.4% and 32.0% over Domino, with lower request latency. Cumulative ablations show that adding the three mechanisms successively increases geometric-mean throughput, while budget adjustment improves accepted-token retention. GPU profiling shows that complete decode-step time on GSM8K decreases by 30.8-52.5% relative to DFlash

0.23

When Parallel Drafter Meets Parallel Speculative Decoding

cs.CL ·2026-09-23 ·Fuliang Liu, Xue Li, Kun Qian, Zhibin Wang, Wanchun Dou +2 more
similarity 0.57
Abstract

DSpark-style parallel drafters have made speculative decoding highly effective, yet their draft phase remains serialized on the critical path of every round. Parallel speculative decoding (PSD) overlaps drafting with verification, yet existing methods must guess the accepted prefix and bonus token in advance: a wrong guess reverts the whole batch to serial drafting. We present DPara, a PSD framework that reuses effective parallel drafters yet guarantees backbone--verification overlap in every round, thereby eliminating this probabilistic fallback altogether. While the target verifies, DPara's diffusion backbone precomputes draft representations for every acceptance boundary with the bonus left unspecified; a lightweight autoregressive head then combines the revealed verification outcome with the matching precomputed representation to emit the next round's draft tokens almost instantly---fully parallelizing the dominant backbone forward with verification and leaving only the negligible head cost serial. Experiments on Qwen3-8B and Qwen3-14B across seven math, coding, and chat benchmarks show that DPara achieves average speedups of $3.21\times$ and $3.52\times$ over autoregressive decoding, surpassing the strongest serial and parallel speculative decoding baselines alike.

0.44