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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Study on Quantitative Modeling of Task Completion Probability in AI Agents Using DAG and State-Machine

Akira Otsuki
Research Square
Reliability and Maintenance Optimization
preprint

Study on Quantitative Modeling of Task Completion Probability in AI Agents Using DAG and State-Machine

Akira Otsuki
preprint en

Abstract

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.

Research Square
Nihon University (JP)
Reliability and Maintenance Optimization
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon