CS Paper Radar

Cheaper by the Batch: Shared Traversal for Genotype Graph Editing

Aaron Li, Yifan Li, Drew DeHaas, Giulia Guidi

cs.DS q-bio.PE ·submitted 2026-08-27 00:23 UTC · v2

Abstract

Updating a graph by inserting or replacing nodes while preserving semantics and reusing existing structure is a recurring computational problem. In population genetics, this problem arises in the genotype representation graph (GRG), a directed acyclic graph that losslessly encodes phased genetic variation across hundreds of thousands of samples by sharing subgraph structure for individual mutations. In a GRG, each mutation's carrier set is implicitly encoded as the set of leaf nodes reachable from the node it is assigned to. Updating a mutation is therefore a structural editing problem, and current approaches remap mutations individually. This paper introduces a batched mutation-remapping algorithm that replaces independent reuse-aware traversals with a single shared reverse-topological pass, identifying reuse candidates for an entire batch at once. The pass propagates compact bit-parallel per-mutation state and uses an adaptive sparse/dense carrier set representation spanning rare-to-common variant densities. Batching is the memory-scalable complement to split-based parallelism, which instead replicates graph and traversal state per worker. Our remapping is evaluated on a controlled update workload and on end-to-end allele polarization, a bulk carrier set update that is common in population genetic analysis. Our approach is up to 10.5$\times$ faster than independent remapping while preserving exact carrier-set semantics.

Closest papers

Nearest neighbours by meaning across the whole index.

ShiftCache: Fast and Exact Indel Effect Prediction by Reusing Shifted Reference Encodings

cs.LG cs.DC ·2026-11-09 ·Sina Barazandeh, Arth Banka, Jose Lugo-Martinez
similarity 0.58
Abstract · 31 pages, 7 figures, 8 tables, including appendix

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$\times$ faster than deduplicated dense execution and 1.6 to 2.7$\times$ faster than our adaptation of layer-by-layer reuse to indels. It is 3.5 to 4.1$\times$ faster than dense reimplementations of two published analyses with Borzoi and AlphaGenome, and 2.6$\times$ faster than dense execution with Enformer. Scoring each variant in its own centered 131 kb window makes ShiftCache only 1.36$\times$ 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.

0.32

Dictionary-Guided Mutation Operators for Automated HDL Repair

cs.ET cs.AIcs.ARcs.NE ·2026-09-01 ·Maisha Mastora, Dean Sullivan
benchmark similarity 0.56
Abstract

Automated repair of Hardware Description Language (HDL) designs remains challenging due to the large search space of candidate repairs and the strict syntactic and semantic constraints imposed by HDL grammars. Generic mutation strategies overwhelmingly generate syntactically invalid candidates that waste compilation and simulation budget, while synthesis-driven and template-based approaches impose their own constraints on generality and portability. In this paper, we propose a dictionary-guided HDL repair system that combines ANTLR-derived DUT-specific mutation vocabularies with a simulation-divergence fault localization (FL) module. The mutation operator applies category-constrained token substitutions, insertions, and deletions directly to Verilog source via regex-based matching, without requiring AST manipulation or synthesis. The FL module identifies diverging output wires from a single simulation run and scores source lines by structural proximity to those signals, directing the mutation search toward high-suspicion regions. A deterministic targeted sweep exhausts all dictionary mutations on the highest-scored lines before falling back to a genetic programming (GP) search. Evaluated on the CirFix benchmark suite across six design under test (DUT) families, the proposed approach produces correct oracle-passing repairs on 14 bug variants, including a 6-edit multi-bug instance that CirFix cannot repair, and achieves an 18x speedup over CirFix on a two-edit benchmark variant. These results indicate that dictionary-constrained mutation operators, combined with lightweight simulation-divergence FL, are a practical and competitive approach to automated HDL repair for common bug classes without formal analysis or synthesis dependencies.

0.30

Transformations for Evolving Property Graph Schemas

cs.DB ·2026-09-28 ·Gauvain Devillez, Stefania Dumbrava, Angela Bonifati
top venuebenchmark similarity 0.56
Abstract · To appear in the Proceedings of the VLDB Endowment, Vol. 19, No. 13, 2026, ISSN 2150-8097

Property graph databases are widely used to represent complex and evolving data, yet systematic support for property graph schema evolution remains limited. In practice, schema transformations are typically defined manually, coupled to specific application contexts, and difficult to reuse across schemas or evolution scenarios. We present GRAFT, a logic-based framework that models property graph schema evolution as reusable, order-constrained meta-transformations derived from atomic edits. Schema evolution is formulated as the exploration of a finite meta-graph with schemas as nodes and grounded meta-transformations as edges. To ensure tractability, GRAFT combines similarity-guided search and pruning, guaranteeing duplication-freeness, termination, and correctness. An experimental evaluation on four benchmark and real-world property graph schema evolution scenarios shows that GRAFT efficiently computes high-quality schema transformation sequences. Using greedy exploration, GRAFT reaches the exact target schema on most datasets, producing stable transformation sequences while keeping runtimes low. A qualitative study on both real-world and synthetic large-scale datasets further shows the quality and robustness of the obtained reusable meta-transformations.

0.35

When Edit Flows are Edit Jumps: replicating Edit Flows and EvoFlows

cs.LG stat.ML ·2026-09-16 ·Gabriel Bénédict, Melanie Buechler, Gerard Riera-Solà, Chloé de Ancos, Yves Gaetan Nana Teukam +1 more
code/data similarity 0.54
Abstract

Antibody lead optimization calls for a small, bounded set of edits to an existing candidate: substitutions, but also insertions and deletions. Edit-based generative models are the only ones that allocate such an edit budget without fixing the edit positions, the edit count, or the output length in advance. However, the existing approaches Edit Flows and EvoFlows did not release code or complete training specifications. Here, we show that both methods follow the same underlying process -- edits firing one at a time, at learned rates, in continuous time -- the pure-jump case of generator matching over finite sequences. With EditJumps we introduce the first open implementation of this framework, with a single generalist antibody editor trained on 1.66M Observed Antibody Space homolog pairs to propose homolog-like variants of a seed sequence, editing unseen leads zero-shot, without the per-family retraining original approaches require. Replicating this system from scratch exposes why open code is essential for generative biology: reconciling published edit distributions required reverse-engineering an undocumented rate-scaling hyperparameter that dictates realized mutation counts. Moreover, we show that published evaluation metrics are highly sensitive to reference sample size, frequently flipping method rankings. We release our full codebase, automated test suite, and configurations at: https://github.com/VisiumCH/editjumps

0.30

IMPACT: Constraint-Aware Search for Imperfectly Factorized Accelerator Mappings

cs.AR ·2026-10-28 ·Konstantinos Stavrakakis, Ilgaz Er, Theofilos Spyrou, Dimitrios Stavrakakis, Stephan Wong +2 more
top venue similarity 0.54
Abstract · 7 pages, 6 figures. Accepted for publication in ASP-DAC 2027

The efficiency of Deep Neural Network (DNN) accelerators depends on how each tensor operation is mapped onto the hardware. A mapping specifies how the computation is tiled across the memory hierarchy, ordered, and parallelized across the processing elements. These choices form a combinatorially large search space, where efficient mappings are hard to find. Most violate hardware constraints, and most remaining mappings underutilize the hardware. Existing mappers either search only part of this space to keep the search tractable, excluding the most efficient mappings, or sample the full space randomly, so most mappings they evaluate are infeasible. We present IMPACT, a mapper that searches the full space. IMPACT pairs a genetic algorithm with a constraint-aware repair operator that converts each infeasible mapping into a feasible one instead of discarding it. On a flexible accelerator, IMPACT outperforms state-of-the-art mappers in EDP, latency, and energy on every DeepBench workload. On a compute-in-memory (CIM) accelerator, whose constraints leave few mappings feasible, it reduces EDP by 66%, latency by 47%, and energy by 18% over the strongest prior mapper across five networks, and rivals hand-crafted expert mappings. Across flexible and highly constrained accelerators, IMPACT finds efficient mappings automatically. IMPACT will be released as open source.

0.45

Beyond Flat Walks: Compositional Abstraction for Autoregressive Graph Generation

cs.LG ·2026-11-09 ·Kaiwen Bian, Andrew H. Yang, Yusu Wang, Ali Parviz, Gal Mishne
similarity 0.53
Abstract

Autoregressive graph generators typically linearize graphs through flat node-edge walks, which can obscure higher-order structure in large and complex graphs. We introduce a hierarchical graph abstraction and coarse-to-fine generation pipeline that separates coarsening, tokenization, and decoding. This exposes three design axes: community coarsening, hierarchical tokenization, and order randomization. Across these axes, traversal-based hierarchy consistently improves distributional and structural fidelity, while its V.U.N.\ cost depends strongly on the coarsening and randomization policy. In particular, the fidelity--V.U.N.\ trade-off observed under within-community randomization is substantially reduced when traversal order is randomized across the full hierarchy. With a fixed backbone, training protocol, and matched training time across five molecular and five non-molecular benchmarks, hierarchical serialization yields consistent distributional and structural gains on all molecular datasets, while the non-molecular results further show that these gains depend on how well the supplied hierarchy aligns with structure in the target distribution. Together, these results characterize when and how hierarchical serialization benefits autoregressive graph generation.

0.10

Dynamic Flow, Static Graph: KV Cache Reuse for Efficient LLM Serving on Mobile NPUs

cs.OS cs.AIcs.DB ·2026-09-28 ·Zhengxiang Huang, Shengheng Chen, Chaoyue Niu, Yujie Sun, Zhaode Wang +4 more
published similarity 0.52
Abstract · Accepted at EuroSys 2027 (Spring Cycle)

On-device large language model (LLM) serving is a cornerstone of local-first personal intelligence, offering users data sovereignty, strong privacy guarantees, and freedom from cloud API latency and cost. Although KV caching is widely used to reduce latency in long-context inference, existing designs were primarily optimized for cloud GPUs with dynamic execution environments and abundant memory bandwidth. These architectural assumptions do not hold on mobile NPUs, where computation graphs must be statically compiled and both memory capacity and I/O bandwidth are severely constrained. In this work, we present a compute-storage co-design for mobile-centric prefix and non-prefix KV reuse. We first propose an intra-graph mechanism that maps selective KV recomputation onto static NPU graphs, reconciling algorithmic dynamicity with NPU staticity. We further develop an inter-graph scheduler to optimize chunk merging and minimize padding with dynamic programming. To address mobile bandwidth limitations, we introduce a hierarchical KV manager featuring a tree-hash-semantic hybrid structure, along with cost-aware prefetching and eviction policies. We also build a two-dimensional pipeline that overlaps KV loading, rerotation, and storage with NPU execution, hiding data-movement latency. Experiments across representative on-device workloads and LLMs show that our design reduces time-to-first-token (TTFT) by $40-60\%$ compared with no reuse and prefix-only caching.

0.56

GenomeHarness: Harnessing Al Agents for Reliable Adaptation of Genome Language Models

cs.CE ·2026-08-22 ·Weicai Long, Yusen Hou, Houcheng Su, Junning Feng, Yanlin Zhang
benchmark similarity 0.52
Abstract · 10 pages, 4 figures

Pretrained genome language models provide reusable representations for DNA sequence analysis, but turning them into reliable downstream predictors remains non-trivial. Their practical performance depends strongly on fine-tuning recipes, and default recipes reported in prior studies may be suboptimal for new tasks or model backbones, making weak downstream results difficult to interpret. These requirements place a substantial operational burden on many intended users, whose expertise is often centered on biological questions and interpretation rather than machine-learning engineering. Reliable use of genome language models therefore requires more than conventional AutoML-style tuning: it requires a systematic, budget-aware, and auditable procedure that lowers the barrier to downstream adaptation. We present GenomeHarness, an agentic harness for adapting genome language models through controlled search over fine-tuning recipes. GenomeHarness combines an AI agent for proposing and repairing recipe edits, a harness for protocol-constrained execution, resource management, and test isolation, and a Monte Carlo tree search controller for allocating search effort across recipe lineages. We evaluate GenomeHarness on DNABERT2 and NTv2-100M-Multi across the NT Benchmark and Genomic Benchmarks. Final evaluation is performed using three random seeds after recipe freezing. Across 52 model-task settings, GenomeHarness improves mean test MCC in 47 settings, including 24 of 26 DNABERT2 settings and 23 of 26 NTv2-100M-Multi settings. The gains are especially pronounced on Genomic Benchmarks and on tasks where the root recipe is unstable or poorly matched, such as human ocr ensembl task. Search traces further show that GenomeHarness progressively identifies stronger recipes, turning downstream adaptation into a controlled and auditable workflow rather than a manual tuning process.

0.22