Can Dependencies Induced by LLM-Agent Workflows Be Trusted?
Yu Yao, Yiliao (Lia) Song, Yian Xie, Mengdan Fan, Mingyu Guo, Tongliang Liu
LLM-agent systems often decompose a high-level task objective into a subtask-dependency graph, assuming each subtask’s response is conditionally independent of others given its parent responses. However, we find the inaccessible ground-truth responses will violate this assumption during execution, leading to inter-agent misalignment: failures arise from breakdowns in inter-agent interaction and coordination during execution.  Consequently, both quality and runtime efficiency degenerate significantly. Motivated by this finding, we propose SeqCV, a dynamic framework that enables reliable execution under violated conditional independence assumptions. In SeqCV, subtasks are executed sequentially, each conditioned on all prior responses and verified via consistency checks immediately after agents generate a short token sequence. At each checkpoint, the token sequence is considered reliable if it is common knowledge consistently supported across diverse models. An unreliable token sequence is discarded, triggering a recursive splitting mechanism to decompose the subtask into more manageable components. Despite the sequential nature, SeqCV avoids costly misalignment corrections and delivers higher effective throughput than parallel pipelines. On different tasks, SeqCV not only improves accuracy by up to 17%, but also reduces execution time by more than half over six commonly used benchmarking datasets.