# From Agent Loops to Deterministic Graphs: Execution Lineage for Reproducible AI-Native Work arXiv: https://arxiv.org/abs/2605.06365 ยท HTML: https://mlsanity.com/paper/2605.06365/ ## Key facts - Cited by 2 papers in the map (data through 14 Oct 2026). - Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use. - Builds on 42 of its 50 references that are in the map. - First posted on arXiv 7 May 2026. ## Placed in - LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/) ## Builds on (most cited first, 30 of 42) - [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022) - [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022) - [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022) - [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023) - [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023) - [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023) - [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023) - [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023) - [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023) - [AutoGen: Enabling Next-Gen LLM Applications via Multi-Agent Conversation](https://mlsanity.com/paper/2308.08155/) (2023) - [MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework](https://mlsanity.com/paper/2308.00352/) (2023) - [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022) - [CAMEL: Communicative Agents for "Mind" Exploration of Large Language Model Society](https://mlsanity.com/paper/2303.17760/) (2023) - [OSWorld: Benchmarking Multimodal Agents for Open-Ended Tasks in Real Computer Environments](https://mlsanity.com/paper/2404.07972/) (2024) - [GAIA: a benchmark for General AI Assistants](https://mlsanity.com/paper/2311.12983/) (2023) - [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022) - [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021) - [DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelines](https://mlsanity.com/paper/2310.03714/) (2023) - [A Survey on the Memory Mechanism of Large Language Model based Agents](https://mlsanity.com/paper/2404.13501/) (2024) - [Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models](https://mlsanity.com/paper/2310.04406/) (2023) - [AndroidWorld: A Dynamic Benchmarking Environment for Autonomous Agents](https://mlsanity.com/paper/2405.14573/) (2024) - [Understanding the planning of LLM agents: A survey](https://mlsanity.com/paper/2402.02716/) (2024) - [AppWorld: A Controllable World of Apps and People for Benchmarking Interactive Coding Agents](https://mlsanity.com/paper/2407.18901/) (2024) - [Reinforcement Learning on Web Interfaces Using Workflow-Guided Exploration](https://mlsanity.com/paper/1802.08802/) (2018) - [How is ChatGPT's behavior changing over time?](https://mlsanity.com/paper/2307.09009/) (2023) - [Evaluating Memory in LLM Agents via Incremental Multi-Turn Interactions](https://mlsanity.com/paper/2507.05257/) (2025) - [Memory-R1: Enhancing Large Language Model Agents to Manage and Utilize Memories via Reinforcement Learning](https://mlsanity.com/paper/2508.19828/) (2025) - [Evo-Memory: Benchmarking LLM Agent Test-time Learning with Self-Evolving Memory](https://mlsanity.com/paper/2511.20857/) (2025) - [Prompting Is Programming: A Query Language for Large Language Models](https://mlsanity.com/paper/2212.06094/) (2022) - [LifelongAgentBench: Evaluating LLM Agents as Lifelong Learners](https://mlsanity.com/paper/2505.11942/) (2025) ## Built on by (most cited first, 2 of 2) - [Correct Is Not Governed: Provenance Integrity in Agentic Workflows](https://mlsanity.com/paper/2608.12761/) (2026) - [Intermediate Artifacts as First-Class Citizens: A Data Model for Durable Intermediate Artifacts in Agentic Systems](https://mlsanity.com/paper/2605.12087/) (2026) ## Abstract (arXiv) Large language model systems are increasingly deployed as agentic workflows that interleave reasoning, tool use, memory, and iterative refinement. These systems are effective at producing answers, but they often rely on implicit conversational state, making it difficult to preserve stable work products, isolate irrelevant updates, or propagate changes through intermediate artifacts. We introduce execution lineage: an execution model in which AI-native work is represented as a directed acyclic graph (DAG) of artifact-producing computations with explicit dependencies, stable intermediate boundaries, and identity-based replay. The goal is not to make the model a better one-shot writer, but to make evolving AI-generated work maintainable under change. We compare execution-lineage replay against loop-centric update baselines on two controlled policy-memo update tasks. In an unrelated-branch update, DAG replay preserved the final memo exactly in all runs, with zero churn and zero unrelated-branch contamination, while loop baselines regenerated the memo and frequently imported unrelated context. In an intermediate-artifact edit, all systems reflected the new constraint in the final memo, but only DAG replay achieved perfect upstream preservation, downstream propagation, unaffected-artifact preservation, and cross-artifact consistency. These results show that final answer quality and maintained-state quality are distinct. Strong loop baselines can remain competitive at producing polished final outputs when the task is a bounded synthesis/update problem and all current sources fit in context, but immediate task success can mask partial state inconsistency that may compound over future revisions. Execution lineage provides stronger guarantees about what should change, what should remain stable, and how work evolves across revisions.