A Scalable Trie Building Algorithm for High-Throughput Phyloanalysis of Wafer-Scale Digital Evolution Experiments
Vivaan Singhvi, Joey Wagner, Emily Dolson, Luis Zaman, Matthew Andres Moreno · 2025
Read A Scalable Trie Building Algorithm for High-Throughput Phyloanalysis of Wafer-Scale Digital Evolution Experiments by Vivaan Singhvi, Joey Wagner, Emily Dolson, Luis Zaman, Matthew Andres Moreno (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-15074.txt.
Introduction
Vivaan Singhvi and colleagues sped up family-tree reconstruction for digital evolution experiments in a 2025 paper. Simulated organisms on wafer-scale chips, with hundreds of thousands of processors, leave ancestry records too large to track naively under tight memory limits. Hereditary stratigraphy solves tracking by embedding compact genetic markers in each organism, but rebuilding full phylogenies from those markers had become the bottleneck at scale.
Their scalable trie-building algorithm organizes the markers into a prefix tree whose construction keeps pace with wafer-scale output. Faster reconstruction unlocks high-throughput studies of evolvability and open-ended evolution, and gives bioinformatics methods a ground-truth testbed where the true tree is known exactly. Hardware scale and analysis scale can finally grow together.
Catalog record
| CREATOR | Vivaan Singhvi, Joey Wagner, Emily Dolson, Luis Zaman, Matthew Andres Moreno |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-15074
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Scalable Trie Building Algorithm for High-Throughput Phyloanalysis of Wafer-Scale Digital Evolution Experiments Vivaan Singhvi, Joey Wagner, Emily Dolson, Luis Zaman, Matthew Andres Moreno Abstract Agent-based simulation platforms play a key role in enabling fast-to-run evolution experiments that can be precisely controlled and observed in detail. Availability of high-resolution snapshots of lineage ancestries from digital experiments, in particular, is key to investigations of evolvability and open-ended evolution, as well as in providing a validation testbed for bioinformatics method development. Ongoing advances in AI/ML hardware accelerator devices, such as the 850,000-processor Cerebras Wafer-Scale Engine (WSE), are poised to broaden the scope of evolutionary questions that can be investigated in silico . However, constraints in memory capacity and locality characteristic of these systems introduce difficulties in exhaustively tracking phylogenies at runtime. To overcome these challenges, recent work on hereditary stratigraphy algorithms has developed space-efficient genetic markers to facilitate fully decentralized estimation of relatedness among digital organisms. However, in existing work, compute time to reconstruct phylogenies from these genetic markers has proven a limiting factor in achieving large-scale phyloanalyses. Here, we detail an improved trie-building algorithm designed to produce reconstructions equivalent to existing approaches. For modestly-sized 10,000-tip trees, the proposed approach achieves a 300-fold speedup versus existing state-of-the-art. Finally, using 1 billion genome datasets drawn from WSE simulations encompassing 954 trillion replication events, we report a pair of large-scale phylogeny reconstruction trials, achieving end-to-end reconstruction times of 2.6 and 2.9 hours. In substantially improving reconstruction scaling and throughput, presented work establishes a key foundation to enable powerful high-throughput phyloanalysis techniques in large-scale digital evolution experiments. Introduction Key aspects of the study of evolution, whether biological or digital, revolve around understanding the flow of genetic material among large populations of organisms. As such, phylogenetic analyses assessing ancestry trees representing organisms’ evolutionary histories are a core tool in evolutionary biology. In biology, phylogeny estimations are typically reconstructed through post hoc analysis of genetic similarities among organisms. In contrast, direct, exact tracking at runtime is typical in in silico experiments. However, in memory-constrained parallel and distributed computing contexts, post hoc reconstruction approaches can become advantageous owing to runtime synchronization and storage costs of direct tracking. Akin to biological studies, efficacy of phylogenetic analysis in such digital experiments hinges on fast, accurate methods to estimate ancestry trees from genome data. In this work, we present a novel trie-building algorithm that greatly reduces compute time necessary to reconstruct phylogenies from special-purpose markers on digital genomes, while producing results equivalent to a naive approach. Applications of Phylogenetic Analysis Phylogenetic analyses provide key means to characterize and quantify a broad array of evolutionary processes. Classically, these analyses have been applied to investigation of species-level macroevolutionary dynamics revolving around speciation and extinction rates; however, population- and organism-level dynamics can also be inferred, such as the spread of beneficial mutations within a population or fitness parameters like growth rate and probability of survival ( Genthon et al., 2023 ; Levy et al., 2015 ; Stadler, 2013 ) . Phylogenetic analysis is also crucial in the field of epidemiology, playing a key role in informing public health interventions. In this context, phylogenetic methods can be used to determine transmission history, pinpointing where and how chains of infection unfold ( Wang et al., 2020 ) . In this vein, phylogenies are also key in assessing the prevalence of “super-spreader” dynamics wherein disease spread is driven by a small set of high-risk individuals ( Colijn & Gardy, 2014 ) . Phylogenies and Digital Evolution In some cases, aspects of biological evolution can be difficult or infeasible to observe on human timescales; laboratory experiments may take years, or even decades, to complete ( Wiser et al., 2013 ; Stroud & Ratcliff, 2025 ) . By simulating the behavior of a population, some experiments can instead be conducted digitally — often completing in a fraction of the time. Digital experiments can model key characteristics of biological populations, such as variation, natural selection, ecological interactions, spatial distribution, and more ( Dolson & Ofria, 2021 ; Haller & Messer, 2023 ) . As such, conclusions from digital evolution experiments can contribute meaningfully to understanding biology ( Pennock, 2007 ) . In digital evolution contexts, phylogenies have likewise proven valuable. In application-oriented contexts, phylogeny-based biodiversity metrics have been shown as predictive of solution quality outcomes for evolutionary computation-based optimization ( Hernandez et al., 2022 ) . Phylogeny-based methods can also be applied to characterize more general aspects of ecology, spatial structure, and selection pressure within in silico populations ( Moreno et al., 2023 ) . Digital evolution approaches can also serve as a testbed to assess bioinformatics methodologies. The Aevol_4b system, for instance, uses a genetic system corresponding to that of DNA, allowing any genetic information to be processed using methods directly from bioinformatics ( Daudey et al., 2024 ) . Likewise, population genetics work often incorporates SLiM, which supports sophisticated continuous-space modeling of single- and multi-species systems ( Haller & Messer, 2023 ) . Given the programmatic observability of digital simulations, digital evolution platforms typically incorporate direct tracking methods that record lineage ancestry as the simulation runs. General-purpose phylogeny-tracking libraries exist for this purpose ( Dolson et al., 2024 ) , although many platforms simply incorporate bespoke implementations into their own software ( Ofria & Wilke, 2004 ) . Scaling Up Digital Evolution Experiments To achieve large-scale digital evolution experiments, it is necessary to move from a single-processor system to a more distributed approach with many computing units ( Moreno et al., 2024b ) . In large-scale, many-processor simulations, however, challenges arise in managing a comprehensive record of ancestry. To control memory use, it is typically necessary to trim away records of extinct lineages when performing direct tracking. Detecting extinctions, however, introduces implementation complexity and overhead costs when lineage histories span across multiple processors. Exhaustive tracking is also sensitive to data loss from crashed hardware or dropped messages, which has been highlighted as a key consideration in achieving very large-scale artificial life systems ( Ackley, 2016 ; Ackley & Small, 2014 ) . Challenges associated with comprehensive tracking are especially acute in specialized hardware accelerator devices, which represent a promising emerging direction in high-performance computing ( Emani et al., 2024 ) . In incorporating thousands of processor cores per device, these hardware architectures impose trade-offs in memory capacity limitations and data locality restrictions that limit the feasibility of comprehensive tracking. In such contexts, reconstruction-based approaches can provide an attractive balance between data fidelity and data collection overhead. Hereditary Stratigraphy (a) evolve (b) sample (c) reconstruct Figure 1: Overview of hereditary stratigraphy. At runtime, genomes are annotated with randomly-generated heritable markers (panel 1 ). To maintain fixed-memory footprint, some markers are overwritten. Genomes of interest are sampled at runtime and from end state (panel 1 ). Decoded genome markers enable estimation of evolutionary relatedness (panel 1 ), subject to error from marker-value collisions and discarded markers. Under controlled conditions, such as laboratory experiments or evolution simulations, genetic material may be engineered to facilitate the accuracy and efficiency of estimating phylogenetic relatedness ( Li et al., 2024 ; Ackley, 2023 ) . 1 1 1 Notably, Ackley has applied barcoding approaches to track recent ancestry among emergent replicators in a distributed