Select-Then-Decompose: From Empirical Analysis to Adaptive Selection Strategy for Task Decomposition in Large Language Models

Shuodi Liu, Yingzhuo Liu, Zi Wang, Yusheng Wang, Huijia Wu, Liuyu Xiang, Zhaofeng He

TL;DR

Current LLM task decomposition strategies face a severe performance–cost trade-off: lightweight single-call prompting degrades on complex open-ended tasks, while multi-call explicit decomposition consumes up to $10\times$ more tokens. To solve this, the authors introduce Select-Then-Decompose (S&D), an adaptive, closed-loop framework that analyzes task characteristics, dynamically routes problems to the most suitable decomposition strategy, and verifies candidate outputs before escalating to more expensive pipelines.

What Problem Does This Paper Address?

Breaking complex problems into subtasks is a standard way to boost LLM reasoning and planning. However, existing strategies fall into two extremes:

  1. Implicit methods (e.g., zero-shot Chain-of-Thought or Plan-and-Solve) resolve tasks in a single prompt. They are computationally cheap but degrade on non-linear or open-ended tasks like multi-hop reasoning and creative writing.
  2. Explicit methods (e.g., ReAct, Plan-and-Execute, DAG-based planners) break tasks down across multiple API calls and structured execution loops. While they handle complexity well, their token and API call costs can be prohibitive—often 4× to 10× higher.

Most prior work concentrates on adding tools, memory, or domain-specific workflows without examining this performance–cost dilemma or how task structure maps to decomposition style.

Methods

The authors first formalize a taxonomy classifying decomposition along six dimensions:

  • Interleaving sequence (Decomposition-First vs. Interleaved)
  • Calling frequency (Implicit vs. Explicit)
  • Topology (Linear vs. Directed Acyclic Graph / DAG)
  • Format (Text vs. Code)
  • Subtask selection space (Predefined vs. Open)
  • Tool integration (Tool-augmented vs. Pure LLM)

Focusing on general-purpose, pure-LLM text workflows, they evaluate five representative strategies: CoT, Plan-and-Solve (P&S), ReAct, Plan-and-Execute (P&E), and P&E (DAG) alongside direct prompting (IO).

Building on their empirical findings, they introduce Select-Then-Decompose (S&D), a three-stage closed-loop architecture:

  • Selection Module: Prompted with problem semantics, an LLM evaluates whether the task demands strict deductive logic, iterative trial-and-error, or divergent synthesis, picking an initial decomposition method.
  • Execution Module: Executes the chosen decomposition method to produce a candidate solution.
  • Validation Module: An evaluator LLM scores the solution's confidence $C \in [0, 1]$. If $C \ge T$ (set to $0.7$), the solution is accepted. If verification fails, the system executes a staged escalation protocol (fallback order: $\text{IO} \rightarrow \text{Implicit} \rightarrow \text{Explicit}$) for up to 3 switching attempts.

Datasets

The authors evaluate on both objective and subjective benchmarks across diverse reasoning styles:

  • GSM8K: Elementary math word problems (arithmetic reasoning; full test set).
  • MATH: High-difficulty competition math (level-5 problems across 4 categories; 617 problems).
  • HumanEval: Python coding benchmark (pass@1).
  • Trivia Creative Writing: Topic-based narrative generation integrating answers to 5 or 10 trivia questions ($N=5, 10$; 200 instances total).
  • HotpotQA: Multi-hop question answering requiring cross-document synthesis (1,000 sampled questions; measured by F1 score).
  • DROP: Discrete paragraph-level reasoning (arithmetic/comparison; used for generalization testing).
  • MT-Bench: Multi-turn conversational evaluation (50 open-ended tasks across 5 categories rated 0–10 by Claude-3.5-Sonnet).

Key Insights and Ideas

  • Task cognitive demands dictate decomposition topology:
  • Strict logical deduction (math/arithmetic) favors linear, cohesive steps (CoT, P&E).
  • Iterative adjustment with feedback (coding) benefits most from interleaved reasoning and action (ReAct).
  • Divergent information gathering and multi-constraint synthesis (story writing, multi-hop QA) perform best with parallel DAG structures.
  • Execution models matter far more than decomposition models: In cross-model scaling experiments with Qwen2.5 (1.5B to 14B), scaling the execution model drove almost all downstream accuracy gains. The decomposition model only requires basic instruction-following capability.
  • Reasoning models trade structural compliance for depth: While DeepSeek-R1 distilled models substantially outperformed non-reasoning counterparts during subtask execution, larger reasoning models (14B) occasionally failed strict JSON formatting during DAG decomposition due to verbose generation.

Key Results

  • Pareto Optimality Across Benchmarks: Across GSM8K, MATH, HumanEval, Trivia Creative Writing, and HotpotQA, S&D consistently occupied the Pareto frontier, matching or exceeding explicit method performance at a fraction of the token cost.
  • Massive Token Savings: On HumanEval and HotpotQA, S&D achieved near-optimal accuracy (88.55% pass@1 on HumanEval and 65.26 F1 on HotpotQA) while using only 24.8% of the token consumption typically required by explicit decomposition pipelines.
  • Cheap Defaults, Targeted Escalation: Across all benchmark runs, S&D settled on lightweight implicit methods ~85% of the time, selectively escalating to expensive explicit methods (~15%) only for verified difficult failures.
  • Validation & Routing Ablations: Removing the selection module (reverting to random starts) increased token costs by +228.99%. Omitting the validation module led to an immediate 2.9% drop in accuracy, confirming the value of closed-loop verification.

Limitations and Future Work

  • Exclusion of Tools and Code Representations: The empirical exploration focused strictly on pure-LLM, text-based decomposition, leaving out external code interpreters, web search tools, and domain-specific sandboxes.
  • Reliance on Prompt-Based Meta-Reasoning: The selection module relies entirely on zero-shot in-context prompting. If a smaller or weaker LLM is used as the controller, selection quality and format compliance degrade.
  • Future Directions: Training dedicated, lightweight classifier heads or router models to assign decomposition strategies without extra prompt tokens, and expanding the framework to tool-augmented agents.

Summary updated

Abstract

Large language models (LLMs) have demonstrated remarkable reasoning and planning capabilities, driving extensive research into task decomposition. Existing task decomposition methods focus primarily on memory, tool usage, and feedback mechanisms, achieving notable success in specific domains, but they often overlook the trade-off between performance and cost. In this study, we first conduct a comprehensive investigation on task decomposition, identifying six categorization schemes. Then, we perform an empirical analysis of three factors that influence the performance and cost of task decomposition: categories of approaches, characteristics of tasks, and configuration of decomposition and execution models, uncovering three critical insights and summarizing a set of practical principles. Building on this analysis, we propose the Select-Then-Decompose strategy, which establishes a closed-loop problem-solving process composed of three stages: selection, execution, and verification. This strategy dynamically selects the most suitable decomposition approach based on task characteristics and enhances the reliability of the results through a verification module. Comprehensive evaluations across multiple benchmarks show that the Select-Then-Decompose consistently lies on the Pareto frontier, demonstrating an optimal balance between performance and cost. Our code is publicly available at https://github.com/summervvind/Select-Then-Decompose.
BibTeX
@inproceedings{liu2025select,
  author = {Shuodi Liu and Yingzhuo Liu and Zi Wang and Yusheng Wang and Huijia Wu and Liuyu Xiang and Zhaofeng He},
  title = {{Select-Then-Decompose: From Empirical Analysis to Adaptive Selection Strategy for Task Decomposition in Large Language Models}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
  url = {https://openreview.net/forum?id=DZxes8lA7z},
}

Loading related content...

Figure