Parallelizing LLM Agent Execution with Contrastive Task Allocation

LLM agents solve complex tasks by executing multi-step workflows that interleave LLM inference with external tool calls, yet execution efficiency is often the dominant bottleneck in real deployments because LLM-generated workflows are typically chain-structured and inherently sequential, limiting parallelism and underutilizing available compute resources. We propose CoAct, a training-free framework that parallelizes agent workflows by casting execution as an online task allocation problem: CoAct prompts the LLM to generate a pool of discrete subtasks and performs online dispatch by selecting, whenever a worker becomes available, the next task that minimizes an incremental task-contrastive objective, encouraging high similarity among tasks executed on the same path (positive pairs) and low similarity across different paths (negative pairs) to reduce cross-worker interaction and synchronization. CoAct further supports speculative redundancy via selective re-execution to improve robustness and mitigate tail latency. Experiments on tool-augmented agent workloads show that CoAct improves per-step execution efficiency and resource utilization while achieving competitive or superior task accuracy, demonstrating that contrastive online dispatch can expose substantial parallelism in LLM-agent workflows without retraining the underlying model.