Despite decades of work, there is still considerable uncertainty regarding the major components of the solid-electrolyte interface (SEI) and its dynamic formation mechanism as a function of electrolyte and anode composition. Here we present a new data-driven first-principles framework using a combination of high-throughput calculations, reaction networks, machine learning and microkinetic modeling. Our automated methodology is based on a systematic generation of relevant species using a general fragmentation/recombination procedure which provides the basis for a vast thermodynamic reaction landscape, calculated with density functional theory. We explore this landscape using stochastic methods and shortest pathfinding algorithms, which yield the most likely reaction pathways which are then refined with transition state calculations and kinetic information. The results of the framework show promise in being able to automatically recover previous insights on single reaction pathways, as well as successfully predicting the early dynamics and competitive nature of the SEI formation. As examples, we present formation mechanisms of LEMC as compared to LEDC and recover the Peled-like separation of the SEI into inorganic and organic domains resulting from rich reactive competition. By conducting accelerated simulations at elevated temperature, we track SEI evolution, confirming the postulated reduction of lithium ethylene monocarbonate to dilithium ethylene monocarbonate and hydrogen gas. These findings furnish fundamental insights into the dynamics of SEI formation and demonstrate a path forward toward a predictive understanding of electrochemical passivation.