De-Linearizing Agent Traces: Bayesian Inference of Latent Partial Orders for Efficient Execution

AI agents increasingly execute procedural workflows as sequential action traces, which obscures latent concurrency and induces repeated step-by-step reasoning. We introduce BPOP, a Bayesian framework that infers a latent dependency partial order from noisy linearized traces. BPOP models traces as stochastic linear extensions of an underlying graph and performs efficient MCMC inference via a tractable frontier-softmax likelihood that avoids #P-hard marginalization over linear extensions. We evaluate on our open-sourced Cloud-IaC-6, a suite of cloud provisioning tasks with heterogeneous LLM-generated traces, and WFCommons scientific workflows. BPOP recovers dependency structure more accurately than trace-only and process-mining baselines, and the inferred graphs support a compiled executor that prunes irrelevant context, yielding substantial reductions in token usage and execution time.

AI agents are increasingly used for multi-step tasks such as cloud infrastructure provisioning and scientific workflows. However, many agents still plan one action at a time, even when they have completed similar tasks many times before. This repeated planning is slow, costly, and can introduce avoidable mistakes. This paper asks whether agents can reuse the structure hidden in their past successful executions. Instead of treating an execution trace as a rigid script, we view it as one possible ordering of an underlying partial order: some actions must happen before others, while independent actions can be safely reordered or run in parallel. For example, two cloud setup steps may appear in different orders across successful runs because neither truly depends on the other. Our method, BPOP, learns this hidden partial order from previous traces and compiles it into a reusable execution plan. Once learned, the agent can follow this structure directly instead of asking a language model to rethink every routine step. This reduces token use and execution time, while making the workflow more explicit, inspectable, and easier to audit.