Observe
Collect successful linearized traces from agents and workflows.
ICML 2026 Poster Companion · COEX Seoul
De-Linearizing Agent Traces: Bayesian Inference of Latent Partial Orders for Efficient Execution
Linear agent traces are noisy serializations, not workflows. BPOP recovers the latent executable partial order and compiles it into efficient frontier execution.
- Cloud-IaC Edge-F1
- 0.95
- Execution validity
- 0.85
- Fallback at high IP-Cov
- 0%
- Tokens/task at high IP-Cov
- ~583
Trace Puzzle
Different successful orders are evidence, not a nuisance.
In a single-threaded log, independent actions must still appear in some order. When the same task succeeds with both orders, BPOP treats the disagreement as evidence for concurrency.
Trace 1
→
→
→
→
Trace 2
→
→
→
→
Trace 3
→
→
→
→
Pair evidence
VSW || SG
Both relative orders appear in successful traces, so the pair is treated as incomparable rather than a hard dependency.
Method
Observe traces, infer a posterior graph, compile execution.
BPOP is an offline workflow-compilation step. It learns a reusable dependency abstraction from historical successes, then uses that graph to avoid repeated per-step LLM planning.
Infer
Use a frontier-softmax likelihood over feasible actions instead of marginalizing over all linear extensions.
Compile
Convert posterior edge probabilities into a frontier-based graph execution engine with fallback when needed.
p(y_t | y_<t, h)
= softmax over feasible frontier actions
Polynomial likelihood evaluation, avoiding #P-hard linear-extension marginalization.
Cloud-IaC Replay
A compiled graph executor advances by feasible frontiers.
The local demo uses precomputed scenario graphs from the paper. It is designed as a stable conference replay, not a live cloud API run.
Step 1
Current frontier: CreateVpc
Nodes in the frontier are feasible because all prerequisites have already completed.
Results
Trace diversity is the switch from reactive planning to compiled execution.
Once diverse traces expose enough incomparable pairs, BPOP recovers a high-quality graph and fallback reasoning collapses.
- Edge-F1
- 0.872
- Complete
- 100.0%
- Fallback
- 0.0%
- LLM calls/task
- 1.0
- Tokens/task
- ~583
Structural Recovery
Execution Modes
| Mode | Success | Avg tokens |
|---|---|---|
| Expert | 66.7% | ~583 |
| Hybrid | 100.0% | 13,234 |
| Explore No CoT | 50.0% | 38,999 |
| Explore CoT | 66.7% | 63,632 |
Beyond CloudOps
On WFCommons, BPOP recovers scientific workflow structure with Edge-F1 0.91 on SRASearch and 0.79 on Epigenomics while preserving execution validity.
Compilation Safety
The threshold is a risk-efficiency knob.
Extra edges reduce parallelism but remain safe. Missed dependencies can trigger premature execution, missing inputs, or runtime failure.
Correct
Extra constraint
Missed dependency
Around alpha = 1/3, compilation keeps a conservative bias toward dependency recall while preserving useful concurrency.
Resources
Paper, code, and citation.
The website is built as a static poster companion, so these links can be mirrored directly to OSS static hosting.
@inproceedings{li2026delinearizing,
title={De-Linearizing Agent Traces: Bayesian Inference of Latent Partial Orders for Efficient Execution},
author={Li, Dongqing and Cheng, Zheqiao and Nicholls, Geoff K. and Kong, Quyu},
booktitle={Proceedings of the 43rd International Conference on Machine Learning},
year={2026}
}