Study on Quantitative Modeling of Task Completion Probability in AI Agents Using DAG and State-Machine
Autonomous AI agents increasingly decompose user instructions into task lists, but widely used approaches (AutoGPT, BabyAGI, MetaGPT) generate simple linear, ID-ordered sequences that cannot express conditional branching or parallel execution. Newer orchestration frameworks such as LangGraph, the LLM Compiler, and the Claude Agent SDK add DAG (Directed Acyclic Graph) or state-machine execution control for non-linear workflows, yet none provides a quantitative, probabilistic estimate of how likely a plan is to succeed, or how much a redundant (alternative) path improves that likelihood. This study integrates DAG-based dependency modeling, prompt engineering for conditional branching, and a state-machine execution engine, and formulates the resulting task-completion probability P(Goal) with reliability engineering. The model is generalized to 1-out-of-n (parallel) path redundancy and to general DAG topologies with parallel branching and AND-joins, and a cost-constrained redundancy-allocation problem and a Beta-prior estimator of path success probabilities from execution logs are given. Assuming independent task outcomes, Monte Carlo simulations (10,000–100,000 trials) of a retrieval-and-summarization task (72.7% completion for the linear model, 84.4% with redundancy) agree with the closed-form predictions to within 0.18 percentage points across 24 parameter combinations and within 1 point under all conditions. Redundancy at the bottleneck stage yields about 3.9 times the gain at the most reliable stage, as the marginal-utility formula predicts. Alternative paths help most when failures are persistent; correlated failures reduce the gain. With a real LLM agent (100 runs), completion rates predicted from probabilities estimated on half the runs fell within the 95% intervals observed on the other half.
Authors
- Akira Otsuki (ORCID: https://orcid.org/0000-0001-8005-4460)
Institutions
- Nihon University (JP)
Publication Details
- Journal
- Research Square
- Published
- 2026-11-19
- DOI
- https://doi.org/10.21203/rs.3.rs-11565438/v1
- Primary Topic
- Reliability and Maintenance Optimization
- Type
- preprint