Sprune: Training-Free Credit-and-Act for Agentic Workflows

Agentic workflows are graphs of operators, prompts, and edges that pass drafts between operators. Automated methods improve such workflows mostly by searching over candidate graphs and returning one, which leaves open how much each component contributes and discards components that later tasks may still need. A growing number of methods instead tie actions to per-component credit, but this coupling has not been named or treated as a design space of its own. We call it credit-and-act (CrAct) and describe it by three parts: a credit estimator, an accumulation rule, and an action set. We then present Sprune, a training-free CrAct method that values operators, prompts, and edges jointly with Owen values over three a priori unions, estimated by permutation sampling and smoothed into running scores by an exponential moving average. The running score archives weak components without deleting them, restores them when their score recovers, and, in a second variant, selects prompts to rewrite and decides whether operators proposed by a language model stay. Because every action reads this score, the attribution that Sprune reports is the signal behind its decisions. Across six benchmarks in code generation, mathematical reasoning, and question answering and three open-weight backbones, Sprune is competitive with seven workflow-search methods that share its backbone. An analysis of the credit recorded in nearly a thousand runs, most of them from the hyperparameter search, shows that operators carry most of the credit, that credit rankings are stable across seeds on five of the six benchmarks, and that most operators ending with the highest credit had been archived and restored along the way. Code is available at https://anonymous.4open.science/r/sprune-iclr.