De-Linearizing Agent Traces: Bayesian Inference of Latent Partial Orders for Efficient Execution
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916044192350208 |
|---|---|
| author | Li, Dongqing Cheng, Zheqiao Nicholls, Geoff K. Kong, Quyu |
| author_facet | Li, Dongqing Cheng, Zheqiao Nicholls, Geoff K. Kong, Quyu |
| contents | 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 Bayesianframework 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 recover 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_02806 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | De-Linearizing Agent Traces: Bayesian Inference of Latent Partial Orders for Efficient Execution Li, Dongqing Cheng, Zheqiao Nicholls, Geoff K. Kong, Quyu Applications 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 Bayesianframework 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 recover 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. |
| title | De-Linearizing Agent Traces: Bayesian Inference of Latent Partial Orders for Efficient Execution |
| topic | Applications |
| url | https://arxiv.org/abs/2602.02806 |