With large language models (LLMs) demonstrating increasingly strong capabilities in task planning, current approaches primarily execute task-specific steps sequentially. However, tasks may be parallelized to maximize the overall efficiency. To address this challenge, we first propose an automated methodology for constructing diversified, highly parallelizable data at scale. Based on this method, we design ParaBench, a benchmark for evaluating LLMs’ ability to parallelize task steps based on temporal dependencies. Furthermore, we introduce CTDO, a novel framework that integrates a compact dependency recognition model with LLM planners to enhance planning capabilities. We test multiple LLMs on ParaBench, and results indicate that the complexity of tasks leads to poor LLM performance, and ParaBench’s high difficulty can serve as a benchmark for future research. Moreover, our CTDO framework effectively enhances task pass rates while preserving step parallelism. Our code and dataset are available at https://github.com/zxthesky/ParaBench .