If you've ever asked an AI assistant to help draft something, then come back the next day and asked it to "tweak that report we worked on," you've bumped into a frustrating problem: the AI doesn't really remember in any structured way. It has a fuzzy chat history, but no clear record of which intermediate result fed into which next step. Change one input and you can't propagate the fix downstream — you basically start over.

This paper proposes a fix called execution lineage. The core idea: instead of treating AI work as a long, messy conversation, treat it as a directed acyclic graph (DAG) — the same kind of structure that build systems like Make or data pipelines like Airflow use. Each node is a unit of work (a prompt, a tool call, a generated artifact), and edges record what depended on what.

Why does that matter? Three big payoffs:

• Stable work products. The output of "summarize section 3" is a node you can point to, not something buried in chat scrollback that mutates every time you nudge the agent.
• Change propagation. If you edit an upstream input — say, swapping the source document — the system knows exactly which downstream artifacts are now stale and need re-running, and which are unaffected. Just like make only rebuilds what changed.
• Isolation from irrelevant updates. Random conversational tangents don't pollute serious work products, because they're not in the graph's dependency chain.

The key insight is borrowing a lesson software engineers learned decades ago: implicit state is the enemy of reproducibility. Build systems, version control, and data pipelines all replaced "just remember what you did" with explicit dependency graphs. Today's AI agents have regressed to the implicit-state era — they keep everything in conversational memory, which is opaque and lossy. Making the dependency structure explicit turns flaky agent loops into something you can audit, replay, and incrementally update.

Practically, this means an "AI-native" document, codebase, or analysis becomes a graph artifact you can version, branch, and diff — not a chat transcript you have to re-prompt your way through. It also opens the door to caching: if a node's inputs haven't changed, reuse its previous output instead of paying the LLM again.