DiGnosis: Verification and Repair of Task Plans via Conditional Graph Diffusion Models

Task planning frameworks solve complex user queries by selecting a set of available tools and their dependencies, naturally represented as a plan graph. Whether they rely on large language models (LLMs), prompted or fine-tuned, or augment them with graph-based components, task planners can produce incorrect plan graphs, with steps of the query left uncovered, missing tool dependencies, or tools absent from the catalog. Verifying plan graphs before execution is therefore essential, yet most existing verifiers still rely on LLMs, which may be just as prone to errors as the planners they are meant to check. In this work, we propose DiGnosis, a planner-agnostic verifier that exploits the graph structure of the produced plans and recasts their verification as a graph denoising task. Concretely, we train a discrete graph diffusion model only on correct plan graphs, conditioned on the query that generated them. From this single denoiser, DiGnosis derives three signals for a candidate plan graph: a brokenness score, a per-node and per-edge diagnosis with preferred alternatives, and a one-shot repair. Score and diagnosis never involve an LLM, which merely proposes a repair candidate guided by the diagnosis, accepted only if it lowers the brokenness score. Extensive experiments on three datasets and four task planners of different nature show that DiGnosis improves the raw plan graph more often and by larger margins than four existing verifiers. Moreover, when the planner is fine-tuned on the same correct plan graphs, DiGnosis recognizes that its plans are largely correct and therefore abstains from repairing them.