Understanding Reasoning Uncertainty in Workflow Optimization of Self-Evolving Agents: A Stochastic Search Perspective

Workflow optimization for self-evolving agents uses execution feedback to search for better task-execution procedures under a limited budget. Uncertainty-guided reasoning methods, adapted to this search, concentrate proposals by lowering rea- soning uncertainty, whereas program-search optimizers judge each candidate only by its own evaluation. Neither suffices: lower reasoning uncertainty is not bet- ter search, since concentration can discard every high-quality workflow, and per- candidate scores cannot show which unevaluated workflows are safe to skip. We give, to our knowledge, the first mathematical framework for reasoning uncer- tainty in workflow optimization, modeling it as stochastic search over history- conditioned proposal distributions, with reasoning uncertainty as their entropy over functionally distinct workflow groups and uncertainty-guided methods as operators that reshape them. Concentration helps only if it retains target-quality workflows, which we certify with a hypergraph over design choices: it pools eval- uations across workflows sharing combinations of choices, bounds unevaluated workflows, and skips only groups whose bounds rule out any target. With high probability, this pruning retains every target workflow in its certified domain and reduces the expected draws to reach one; under sufficient conditions, it returns a workflow better than the unpruned search’s at the same budget. On five systems tasks, it improves task scores over OpenEvolve by 4.7%–18.2%, outperforming uncertainty-guided variants.