ACCORDION: Breaking Dependency Barriers in Multi-Agent LLM Workflows via Context Speculation

Hierarchical multi-agent workflows typically enforce strict parent–child dependency barriers: a child starts decoding only after its parent finishes, making end-to-end latency dominated by the longest dependency chain. We identify a key source of slack: children can begin decoding under partial parent context, and revise only when new parent content arrives. The core challenge lies in controlling speculative waste from context updates. To address this, we propose ACCORDION, a context-level speculative decoding framework for dependency-constrained workflows. The parent streams its output as incremental prompt commits, while each child decodes in parallel under its current partial context. After each commit, the child verifies drafted tokens against the updated context, preserves the longest accepted prefix, and rolls back from the first rejection. We further give an information-theoretic view of prefix reuse: under an ideal maximal-reuse verifier, expected acceptance after an update is lower-bounded by a decreasing function of the update's conditional entropy, while the parent's self-surprisal provides an online proxy under a stated calibration assumption, yielding a surprisal-triggered commit rule that trades off reuse and rollback. Across diverse workloads, ACCORDION reduces end-to-end latency by up to 46.6% relative to sequential execution and achieves a more stable speed–accuracy trade-off than heuristic streaming baselines while maintaining comparable task performance. It further composes with model-level speculative decoding.