TIPEX separates replica parallelism from structural parallelism and finds mid-difficulty tasks benefit most

arXiv·medium signalXBlueskyLinkedInCopy link

This ICML 2026 paper (arXiv 2608.05791, submitted August 6) models inference-time parallelism in multi-agent LLM systems as two distinct decision levels — Replica Parallelism, which explores multiple complete solution paths at the task level, and Structural Parallelism, which runs concurrent work inside a single path via task decomposition — and unifies both under one controllable execution semantics. Systematic experiments on GAIA show parallelism significantly improves accuracy and cuts end-to-end latency at the cost of higher token consumption, but the effects are not monotonic: the two forms are complementary across task complexities, tasks of intermediate difficulty gain most from coordinating them, and overly aggressive parallel strategies do not reliably perform better. That last result is the useful one for anyone tuning fan-out width in a production orchestrator.