The Stochastic Gap: A Markovian Framework for Pre-Deployment Reliability and Oversight-Cost Auditing in Agentic Artificial Intelligence

Paper: 2603.24582 Authors: Biplab Pal, Santanu Bhattacharya Categories: cs.AI

Abstract

Agentic artificial intelligence in organizations is a sequential decision problem constrained by reliability and oversight cost. When deterministic workflows are replaced by stochastic policies operating over event logs, it becomes hard to know how much uncertainty remains before the next action. This paper introduces a Markovian framework for pre-deployment auditing that quantifies blind spots in state coverage, action uncertainty, and human-escalation cost. Evaluated on a large enterprise purchase-to-pay log, the approach shows that a compact workflow view can hide substantial next-step uncertainty, while a richer state representation exposes it more clearly.

Key Contributions

• Formalizes agentic workflow auditing as a Markov-style sequential decision problem
• Defines measures for hidden uncertainty, action coverage, and escalation cost
• Introduces a human-review trigger based on uncertainty
• Evaluates the framework on the BPI Challenge 2019 procurement log
• Shows that richer state definitions reveal more next-action ambiguity

Methodology

The framework treats an organization’s workflow as a sequence of state transitions. Instead of asking whether an agent is generally reliable, it asks a narrower question: given the current state, how much uncertainty remains about the next action, and how much oversight would be needed if the system is allowed to continue autonomously?

That shift matters because state design changes the audit outcome. A compact representation can make a workflow look more certain than it really is. By widening the state, the model surfaces hidden uncertainty that a coarse abstraction would miss.

Results

On the BPI Challenge 2019 purchase-to-pay log, the authors find that expanding the state from 42 variables to 668 variables increases the measured state-action blind mass substantially. In other words, the richer state reveals more unresolved decision uncertainty.

The framework also aligns reasonably well with observed behavior on held-out data: the model’s maximum action probability tracks actual autonomous-step accuracy within a few percentage points on average. That makes it useful as a pre-deployment audit tool rather than just a theoretical construct.

Takeaways

1. Agentic workflow reliability can be audited as a sequential decision problem
2. Oversight cost and action uncertainty should be measured together
3. Coarse states can hide next-step ambiguity in real enterprise workflows
4. Richer state descriptions expose more of the true uncertainty budget
5. Pre-deployment auditing can help estimate how much autonomy a workflow can safely support