Musubito: Deterministic Execution Lineage for AI-Enabled Python Workflows

AI-enabled software systems built around large language model (LLM) agents increasingly execute as pipelines of prompts, retrieval steps, tools, validators, and aggregation functions. In these settings, expensive operations are often repeated even when the logical inputs and upstream dependencies have not changed. This paper presents Musubito, a Python runtime for execution lineage and dependency-aware replay. The runtime distinguishes deterministic, stochastic, and external-effect steps, each associated with different replay expectations. Its main invariant is a strict node identity in which operation names, canonical input hashes, and sorted upstream node identifiers determine whether a stored artifact is admissible for reuse. Nodes, artifacts, and edges are stored in a relational directed acyclic graph backed by SQLite. Replay is governed by the declared step semantics; fan-in is represented through merge contexts; and downstream staleness is propagated by recursive SQL common table expressions (CTEs, recursive SQL queries used to traverse graphs). In this formulation, deterministic refers to node identity and replay decision logic, not to the semantic determinism of every wrapped operation. The contribution is a producer-sensitive replay contract for ordinary Python calls. It brings deterministic current-node identity, explicit step semantics, historical artifact provenance, multi-parent dependencies, and output-sensitive invalidation into one embedded execution model. In a reproducible five-step agentic pipeline, replay retains millisecond-scale same-process reuse while adding cross-session persistence and durable DAG lineage for incremental recomputation. The evaluation compares this behavior with plain re-execution, in-process memoization, Joblib’s disk-backed function cache, and Prefect’s persisted task cache. A separate producer-substitution experiment tests the case in which unchanged local arguments conceal a changed upstream producer.