Query Decomposition

A decomposition strategy where sub-queries are executed in a strict, ordered pipeline. The output of one sub-query serves as a necessary input parameter for the next. This is critical for multi-hop reasoning tasks where a fact must be established before it can be used.

• Mechanism: Directed Acyclic Graph (DAG) execution
• Example: "What is the market cap of the company that makes the chip in the latest iPad?" → Q1: "What chip is in the latest iPad?" → A1: "M4" → Q2: "Who manufactures the M4 chip?" → A2: "TSMC" → Q3: "What is the market cap of TSMC?"
• Failure Mode: A hallucination in an early step cascades and corrupts all downstream answers.

A strategy where a complex query is split into multiple independent sub-queries that can be executed simultaneously. The final answer is synthesized by aggregating the results from all parallel branches.

• Mechanism: Map-Reduce pattern
• Example: "Compare the battery life, camera specs, and price of the Pixel 9 Pro and iPhone 16 Pro." → Q1: "Pixel 9 Pro battery life" | Q2: "iPhone 16 Pro battery life" | Q3: "Pixel 9 Pro camera specs" | Q4: "iPhone 16 Pro camera specs" | Q5: "Pixel 9 Pro price" | Q6: "iPhone 16 Pro price"
• Optimization: Reduces end-to-end latency by avoiding sequential bottlenecks.

A few-shot prompting technique where the model is instructed to first decompose a problem into simpler sub-problems, then solve each sub-problem sequentially, using the solutions to prior sub-problems to facilitate solving harder ones.

• Origin: Zhou et al., 2022
• Key Distinction: Unlike standard chain-of-thought, the decomposition step is explicit and the model is prompted to solve "easy" sub-problems first.
• Example: "How many times does 'e' appear if you concatenate the words 'apple', 'elephant', and 'egg'?" → Sub-1: Count 'e' in 'apple' (1). Sub-2: Count 'e' in 'elephant' (2). Sub-3: Count 'e' in 'egg' (1). Sub-4: Sum the counts (1+2+1=4).

A decomposition paradigm for retrieval-augmented generation that interleaves chain-of-thought reasoning steps with retrieval calls. Each reasoning step generates a sub-query, retrieves information, and then uses that information to inform the next reasoning step.

• Mechanism: CoT Step → Retrieval → CoT Step → Retrieval
• Advantage: Dynamically adapts the decomposition based on retrieved information rather than relying on a static, pre-planned decomposition.
• Use Case: Complex multi-hop questions over large corpora where the retrieval path cannot be fully anticipated.

A modular approach where a complex task is decomposed by a 'decomposer' LLM into a program of simpler sub-tasks, each handled by a specialized 'sub-handler'. This allows different prompts, models, or even tools to be used for each sub-task.

• Architecture: Decomposer LLM → [Handler A, Handler B, Handler C] → Aggregator
• Example: Writing a research paper → Decompose into: Outline generation, Section 1 drafting, Section 2 drafting, Citation formatting, Abstract synthesis.
• Benefit: Enables delegation of sub-tasks to smaller, cheaper, or fine-tuned models optimized for a specific function.

A zero-shot decomposition strategy where the model is prompted to first devise a plan to solve the problem, then execute that plan step-by-step. This separates the reasoning about the structure of the solution from the execution of the calculations.

• Prompt: "Let's first understand the problem and devise a plan to solve it. Then, let's carry out the plan and solve the problem step by step."
• Advantage: Reduces calculation errors and missing-step errors common in standard zero-shot chain-of-thought.
• Refinement: 'Plan-and-Solve+ (PS+)' adds more detailed instructions, such as extracting relevant variables and calculating intermediate results explicitly.

The downstream synthesis process that consumes the output of query decomposition. Once a complex query is broken into atomic sub-queries, multi-hop reasoning traverses the answers to each sub-query, chaining them together to build a final composite answer.

• Sequential dependency: The answer to sub-query A is required to formulate sub-query B.
• Graph traversal: Often implemented by walking a knowledge graph or iteratively calling a vector store.
• Contrast with single-hop: A single-hop question requires only one retrieval step; multi-hop requires aggregating evidence across multiple sources.

A formal approach to query decomposition that converts natural language into a logical form such as SPARQL, SQL, or lambda calculus. This structured representation explicitly defines the sub-tasks and their dependencies.

• Text-to-SQL: Decomposes a question like 'Which employees in the London office were hired after 2020?' into a structured query with filters and joins.
• Executable precision: The logical form can be run directly against a database, eliminating retrieval ambiguity.
• Grammar-based: Relies on a defined grammar or neural semantic parser to map language to logical predicates.

A prompting strategy that induces a language model to perform on-the-fly query decomposition. The model is first asked to break a complex problem into simpler sub-problems, then solve each sequentially, with the solution to prior sub-problems provided as context for later ones.

• Two-stage process: Decomposition phase followed by sequential solving phase.
• Scaffolding: The prompt structure provides explicit 'Problem:' and 'Sub-problems:' sections.
• Provenance: Demonstrated to significantly improve performance on compositional generalization benchmarks requiring symbolic manipulation and multi-step math.

A structured decomposition technique used in task-oriented dialogue systems. A complex user intent is mapped to a predefined frame with slots that must be populated to execute a command.

• Example: Booking a flight requires slots for origin, destination, departure_date, and passenger_count.
• Iterative clarification: If a slot is missing, the system generates a targeted sub-question to the user.
• Contrast: Unlike open-ended decomposition, slot filling operates within a fixed ontology of possible intents and parameters.

A retrieval-centric approach where a complex query is decomposed into sub-queries optimized for a search engine. Each sub-query is independently executed against a document index, and the retrieved passages are aggregated for final synthesis.

• Pseudo-relevance feedback loop: Initial sub-query results can inform the formulation of subsequent sub-queries.
• Parallel execution: Sub-queries without sequential dependencies are run concurrently to minimize latency.
• Keyword generation: Sub-queries are often phrased as keyword-rich search strings rather than natural language questions to maximize BM25 recall.

An evolution of decomposition prompting where the model is explicitly instructed to generate a plan before executing any reasoning steps. The plan serves as a high-level decomposition of the task into a sequence of actions.

• Plan-then-execute: Separates the reasoning about 'what to do' from the actual computation.
• Error correction: If execution deviates, the plan provides a reference for recovery.
• Tool integration: Plans can include steps like 'Search for X' or 'Calculate Y', making it a natural fit for agentic systems that decompose goals into tool calls.