DecoSearch: Complexity-Aware Routing and Plan-Level Repair for Text-to-SQL

# DecoSearch: Complexity-Aware Routing and Plan-Level Repair for Text-to-SQL
Source: [https://arxiv.org/html/2606.17821](https://arxiv.org/html/2606.17821)
Xu ZhengFlorida International UniversityHojat Allah SalehiFlorida International UniversityZhuomin ChenFlorida International UniversityMo ShaFlorida International UniversityWei ChengNEC\-LabsDongsheng LuoSingapore Management University

###### Abstract

Large Language Models \(LLMs\) have demonstrated remarkable capabilities in translating natural language to SQL, yet existing methods still falter on complex queries requiring multi\-step, data\-aware reasoning\. We introduce DecoSearch, a training\-free framework that addresses this by routing each query to the appropriate level of reasoning effort\. A lightweight Schema Selector first prunes the full database schema to the relevant tables and columns\. An LLM Judger then decides whether the question requires decomposition: straightforward questions follow a direct generation path and complex ones are escalated to a Directed Acyclic Graph \(DAG\) of atomic sub\-questions, each solved by a targeted SQL generation step\. A RAG component grounds the decomposer with semantically similar training examples, and a Topology Refiner restructures the reasoning plan when execution failures signal a flawed decomposition rather than a fixable SQL error\. DecoSearch achieves 70\.53% execution accuracy on BIRD and 88\.31% on Spider with a DeepSeek backbone, surpassing all training\-free baselines while consuming an order of magnitude fewer tokens than competing methods\. It also functions as a model\-agnostic wrapper, consistently improving fine\-tuned SQL generation backbones without any modification to the pipeline\.

DecoSearch: Complexity\-Aware Routing and Plan\-Level Repair for Text\-to\-SQL

## 1Introduction

The conversion of natural language questions into executable SQL \(Text\-to\-SQL\) is a fundamental challenge at the intersection of natural language understanding and database systemsKatsogiannis\-Meimarakis and Koutrika \([2023](https://arxiv.org/html/2606.17821#bib.bib2)\); Luoet al\.\([2025](https://arxiv.org/html/2606.17821#bib.bib25)\); Yuet al\.\([2018](https://arxiv.org/html/2606.17821#bib.bib7)\); Liet al\.\([2023](https://arxiv.org/html/2606.17821#bib.bib6)\)\. The advent of Large Language Models \(LLMs\) has marked a new era of capability in this domain, enabling zero\-shot or few\-shot translation with impressive fluencyRajkumaret al\.\([2022](https://arxiv.org/html/2606.17821#bib.bib26)\); Gaoet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib8)\); Pourreza and Rafiei \([2023](https://arxiv.org/html/2606.17821#bib.bib3)\); Talaeiet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib5)\)\. However, the performance of these models degrades significantly when confronted with complex questions, those requiring nested queries, multi\-step logical inference, or an awareness of the database’s underlying content and structureLiet al\.\([2023](https://arxiv.org/html/2606.17821#bib.bib6),[2024](https://arxiv.org/html/2606.17821#bib.bib27)\), or large databases with multiple tables that requires complex SQL queries with multiple JOIN operationsYuet al\.\([2018](https://arxiv.org/html/2606.17821#bib.bib7)\); Liet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib27)\)\. For these problems, a single\-pass, autoregressive generation process is often insufficientScholaket al\.\([2021](https://arxiv.org/html/2606.17821#bib.bib28)\); Pourreza and Rafiei \([2023](https://arxiv.org/html/2606.17821#bib.bib3)\); Talaeiet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib5)\); Pourrezaet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib4)\), as it fails to explore the vast combinatorial space of possible SQL queries and cannot recover from early generation errors\.

Recent work has attacked this brittleness from several angles\. Decomposition\-based methods break a complex question into simpler sub\-problems, improving the tractability of each stepPourreza and Rafiei \([2023](https://arxiv.org/html/2606.17821#bib.bib3)\); Zhouet al\.\([2023](https://arxiv.org/html/2606.17821#bib.bib19)\); Eyalet al\.\([2023](https://arxiv.org/html/2606.17821#bib.bib29)\); Wanget al\.\([2025a](https://arxiv.org/html/2606.17821#bib.bib30)\); Xieet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib40)\)\. Self\-refinement approaches use execution feedback to iteratively debug generated SQLMadaanet al\.\([2023](https://arxiv.org/html/2606.17821#bib.bib20)\); Gouet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib21)\); Chenet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib31)\); Askariet al\.\([2025](https://arxiv.org/html/2606.17821#bib.bib32)\); Zhaiet al\.\([2025](https://arxiv.org/html/2606.17821#bib.bib42)\)\. Multi\-candidate frameworks generate diverse SQL candidates and select the best oneWanget al\.\([2023](https://arxiv.org/html/2606.17821#bib.bib14)\); Pourrezaet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib4)\); Sunet al\.\([2023](https://arxiv.org/html/2606.17821#bib.bib33)\); Leeet al\.\([2025](https://arxiv.org/html/2606.17821#bib.bib34)\); Borchmann and Wydmuch \([2025](https://arxiv.org/html/2606.17821#bib.bib38)\)\. Complexity\-aware routing strategies allocate different pipelines to queries of different difficultyZhuet al\.\([2025](https://arxiv.org/html/2606.17821#bib.bib37)\); Guoet al\.\([2025](https://arxiv.org/html/2606.17821#bib.bib43)\)\. Each of these strategies addresses a real failure mode, but each operates at a single level of the problem\. A self\-debugging system can fix a syntactic error in a SQL query, but it cannot recognize that the underlying reasoning plan was flawed\. A decomposition system can produce a sensible plan, but if one sub\-problem turns out to be unsolvable as posed, it has no mechanism to revise its own plan\. A multi\-candidate system offers breadth, but it does not adaptively concentrate its computational budget on the most promising direction\.

We observe that failures in complex Text\-to\-SQL generation are not monolithic\. They arise from qualitatively different root causes that demand different interventions\. Some failures are*implementation\-level*: the SQL contains a bug such as a wrong join condition or an incorrect filter, and an LLM debugger equipped with execution feedback can repair it directly\. Other failures are*strategy\-level*: the chosen SQL formulation style \(e\.g\., nested subqueries versus CTEs\) is a poor fit for the problem, and a structurally different approach would succeed where iterative debugging of the current one would not\. Still other failures are*plan\-level*: the high\-level reasoning plan itself is flawed, a dependency is missing, or the decomposition is too coarse, and no amount of SQL\-level repair can compensate\. Existing methods typically address at most one of these failure types\. No current Text\-to\-SQL framework systematically diagnoses the level at which a failure occurs and routes it to the appropriate repair mechanism\.

We introduce DecoSearch, a training\-free framework that organizes Text\-to\-SQL generation as a multi\-stage adaptive workflow with hierarchical failure routing\. The framework employs a Judger\-led escalation strategy: for every question, a specialized LLM judger evaluates whether the query can be solved directly or requires structural decomposition\. For manageable questions, the system follows a Direct Path that generates and executes a single SQL query, keeping latency and cost low\. For queries judged as complex, DecoSearch escalates to the plan level, decomposing the question into a Directed Acyclic Graph \(DAG\)\. Each sub\-question is solved independently, and persistent execution failures at the query level trigger automatic topology refinement to restructure the reasoning plan\. This ensures computational resources are spent proportionally to the depth of the failure\.

Our primary contributions are as follows:

- •We identify that failures in complex Text\-to\-SQL arise at distinct levels of abstraction \(implementation, strategy, and planning\) and introduce a hierarchical failure\-routing architecture with a Judger\-led direct path that efficiently resolves manageable queries while routing genuinely complex ones to structured decomposition\.
- •We introduce a plan\-level repair mechanism that identifies persistent query failures as signs of a flawed decomposition, automatically restructuring the reasoning DAG in response\. Evaluating on the BIRD and Spider benchmarks, DecoSearch achieves execution accuracies of 70\.53% and 88\.31%, respectively\. Without any supervised fine\-tuning, it successfully recovers a significant portion of the queries where direct generation baselines fail\.

![Refer to caption](https://arxiv.org/html/2606.17821v1/x1.png)Figure 1:The pipeline begins with Pre\-Processing via evidence\-aware schema pruning\. A Judger determines if the question is manageable; if so, the Direct Path generates and executes a single SQL query and exits if successful\. Otherwise, the Decomposer produces a DAG of atomic sub\-questions linked by@\[n\]dependency placeholders\. At the Sub\-Question Solving stage, each node is executed in topological order; upstream results are resolved as inline value lists for small result sets or materialized as temporary tables for large ones before the downstream SQL is generated\. Persistent execution failures trigger the Topology Refiner to rewrite the DAG and retry\.
## 2Related Work

Text\-to\-SQL with LLMs\.Early Text\-to\-SQL systems relied on semantic parsing and schema\-aware neural encodersWanget al\.\([2020](https://arxiv.org/html/2606.17821#bib.bib23)\); Cai and Wan \([2020](https://arxiv.org/html/2606.17821#bib.bib22)\)\. The rise of large\-scale LLMs shifted the paradigm toward in\-context learning, enabling strong zero\-shot and few\-shot performanceRajkumaret al\.\([2022](https://arxiv.org/html/2606.17821#bib.bib26)\); Gaoet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib8)\)\. However, single\-pass generation remains brittle on complex queries requiring multi\-table joins or data\-aware reasoningLiet al\.\([2023](https://arxiv.org/html/2606.17821#bib.bib6),[2024](https://arxiv.org/html/2606.17821#bib.bib27)\), a challenge made even more acute by newer, harder benchmarks such as Spider 2\.0Leiet al\.\([2025](https://arxiv.org/html/2606.17821#bib.bib39)\), which features enterprise\-scale databases where state\-of\-the\-art models achieve below 25% accuracy\.

Decomposition\-based Methods\.A natural response to this brittleness is to decompose complex questions into simpler sub\-problemsZhouet al\.\([2023](https://arxiv.org/html/2606.17821#bib.bib19)\); Pourreza and Rafiei \([2023](https://arxiv.org/html/2606.17821#bib.bib3)\); Eyalet al\.\([2023](https://arxiv.org/html/2606.17821#bib.bib29)\); Wanget al\.\([2025a](https://arxiv.org/html/2606.17821#bib.bib30)\)\. DIN\-SQLPourreza and Rafiei \([2023](https://arxiv.org/html/2606.17821#bib.bib3)\)pioneered decomposed in\-context learning with self\-correction for Text\-to\-SQL\. DEA\-SQLXieet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib40)\)introduces a workflow\-based paradigm that counters attention diffusion in monolithic prompting through sequential filtering, classification, and correction stages\. Our work extends these ideas by formalizing the decomposition as a dependency DAG and enabling plan\-level repair when sub\-problems fail\.

Schema Linking\.Passing the full database schema to every LLM call degrades generation quality and inflates cost\. CHESSTalaeiet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib5)\)integrates LLM\-driven schema pruning as a dedicated agent\. RSL\-SQLCaoet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib41)\)further improves schema linking with bidirectional pruning, achieving high recall while cutting input columns substantially\. DecoSearch’s schema selector follows this paradigm, applying LLM\-driven keyword extraction and two\-stage table and column selection before any generation call\.

Self\-Refinement and Execution Feedback\.Several methods improve robustness by iteratively revising SQL using execution feedbackMadaanet al\.\([2023](https://arxiv.org/html/2606.17821#bib.bib20)\); Gouet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib21)\); Chenet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib31)\); Askariet al\.\([2025](https://arxiv.org/html/2606.17821#bib.bib32)\)\. ExCoTZhaiet al\.\([2025](https://arxiv.org/html/2606.17821#bib.bib42)\)extends this with execution\-supervised fine\-tuning, iteratively improving open\-source models using only SQL execution accuracy as the reward signal\. These approaches address implementation\-level failures but cannot restructure an incorrect reasoning plan\. DecoSearch complements this by operating at the plan level: when execution feedback reveals a flawed decomposition, the system rewrites the DAG rather than patching individual queries\.

Multi\-Candidate, Routing, and Test\-Time Scaling\.CHASE\-SQLPourrezaet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib4)\)generates diverse candidates via multiple CoT strategies and selects the best via a fine\-tuned pairwise ranker\. Agentar\-Scale\-SQLWanget al\.\([2025b](https://arxiv.org/html/2606.17821#bib.bib12)\)combines RL, refinement, and parallel synthesis at the query level\. CHESSTalaeiet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib5)\)and MCS\-SQLLeeet al\.\([2025](https://arxiv.org/html/2606.17821#bib.bib34)\)use self\-consistency voting over multiple candidates; Query and ConquerBorchmann and Wydmuch \([2025](https://arxiv.org/html/2606.17821#bib.bib38)\)shows that execution\-guided selection alone enables smaller models to match much larger ones\. Complexity\-aware routing has also emerged as a practical tool: EllieSQLZhuet al\.\([2025](https://arxiv.org/html/2606.17821#bib.bib37)\)routes queries to different generation pipelines based on estimated difficulty, achieving substantial token savings, while Rethinking Agentic WorkflowsGuoet al\.\([2025](https://arxiv.org/html/2606.17821#bib.bib43)\)benchmarks test\-time scaling strategies for Text\-to\-SQL and finds that routing and decomposition consistently outperform naive candidate scaling\. DecoSearch uses a Judger\-led routing strategy to select between direct generation and hierarchical decomposition, reserving the structured DAG approach for queries requiring deeper reasoning\.

## 3Methodology

### 3\.1Problem Formulation

Given a natural language questionQQ, a database𝒟\\mathcal\{D\}with schema𝒮\\mathcal\{S\}, and optionally a set of domain hints \(“evidence”\), our goal is to produce an SQL queryQ^\\hat\{Q\}such thatExecute​\(Q^,𝒟\)=Execute​\(Q∗,𝒟\)\\text\{Execute\}\(\\hat\{Q\},\\mathcal\{D\}\)=\\text\{Execute\}\(Q^\{\*\},\\mathcal\{D\}\), whereQ∗Q^\{\*\}is the ground\-truth query\. We evaluate correctness via execution accuracy \(EX\): a query is correct if and only if its result set semantically matches the gold result set\.

### 3\.2Overview

DecoSearch treats Text\-to\-SQL generation as an adaptive, multi\-level reasoning process\. Rather than committing every question to the same generation procedure, the system first assesses query complexity and routes each question to the cheapest path that is likely to succeed\. For straightforward questions, a direct generation attempt is sufficient\. For complex questions, those requiring multi\-table joins, nested logic, or multi\-step inference; the system escalates to a structured decomposition that breaks the question into a DAG of simpler, independently solvable sub\-questions\. Failures are diagnosed and repaired at the appropriate level of abstraction: when a node’s SQL fails to execute, the system signals a flawed reasoning plan and triggers topology refinement of the DAG\. The entire framework is training\-free and operates at test\-time, relying solely on the reasoning capabilities of an off\-the\-shelf LLM\.

Our proposed framework consists of five primary components: \(1\) a Schema Selector that prunes the database schema to the most relevant tables before any LLM call, \(2\) a Judger\-Led Escalation strategy that determines the appropriate reasoning depth, \(3\) a Direct Path for manageable questions, \(4\) a Query\-Level SQL Generation step for sub\-problem solving, and \(5\) a Hierarchical Control Loop for dynamic topology refinement\. This tiered approach ensures that computational resources are allocated proportionally to the complexity of the question, with decomposition reserved for queries the Judger identifies as complex\. The full pipeline is given in Figure[1](https://arxiv.org/html/2606.17821#S1.F1)\. We describe each component below\.

### 3\.3Schema Selection

Real\-world databases often contain dozens of tables and hundreds of columns, the vast majority of which are irrelevant to any given question\. Passing the full schema to every LLM call wastes tokens, inflates cost and, more critically, degrades generation quality by filling the context with distracting schema noise\. DecoSearch therefore applies a lightweight schema pruning step before any LLM call in the pipeline\.

Our Schema Selector follows the schema\-pruning approach introduced in CHESSTalaeiet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib5)\)and DeepEye\-SQLLiet al\.\([2026](https://arxiv.org/html/2606.17821#bib.bib11)\), and is consistent with the bidirectional pruning principles of RSL\-SQLCaoet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib41)\), adapting their keyword\-based filtering strategy to our pipeline\. The Schema Selector operates in two stages\. First, it issues a single LLM call to extract a set of task\-relevant keywords and entities from the NLQ and the evidence string \(e\.g\., column names, value filters, domain terms\)\. Second, it uses those keywords to drive an LLM\-based table selection call, followed by a column selection call within the chosen tables\. Only the selected tables and their columns are serialized into the schema string passed to the Judger, Decomposer, SQL Generator, and Topology Refiner\.

This pruning reduces prompt length by up to an order of magnitude for large databases and focuses the LLM’s attention on relevant schema elements; the ablation study \(§[4\.3](https://arxiv.org/html/2606.17821#S4.SS3)\) confirms its impact on both accuracy and token cost\.

### 3\.4Judger\-Led Escalation and Direct Path

The pipeline begins with a specialized LLM Judger that evaluates the complexity of the natural language question \(NLQ\) relative to the database schema\. The Judger is a single zero\-shot LLM call that receives two inputs: \(1\) the NLQ and \(2\) the pruned database schema produced by the preceding schema\-selection step\. It outputs a structured JSON object of the form\{"needs\_decomposition": true/false, "reasoning": "\.\.\."\}, providing both a binary routing decision and a brief rationale\.

The Judger prefers the direct path by default, escalating to decomposition only for questions with conflicting aggregation grains, extreme join complexity, multi\-phase reasoning where step two depends on a materialized result from step one, or evidence\-driven formulas that would make a single query excessively nested\. This routing philosophy is consistent with recent work on complexity\-aware allocationZhuet al\.\([2025](https://arxiv.org/html/2606.17821#bib.bib37)\); Guoet al\.\([2025](https://arxiv.org/html/2606.17821#bib.bib43)\), which shows that matching computational effort to query difficulty yields significant accuracy and efficiency gains over uniform strategies\.

When decomposition is not needed, the pipeline proceeds directly to the Direct Path described below; when it is, the system skips the direct path and proceeds to DAG\-based decomposition\.

For questions judged as manageable, the system follows a Direct Path: a single SQL query is generated using a zero\-temperature LLM call and executed against the database\. If execution succeeds, the result is returned immediately, keeping both latency and cost low\. If execution fails, the framework falls through to the decomposition stage, which systematically breaks the original query into a sequence of simpler, more verifiable sub\-tasks\.

### 3\.5Plan\-Level Search: Task Decomposition

When the Judger mandates escalation or the direct path fails to execute, the system initiates an upper\-level plan by decomposing the complex NLQ into a DAG\. In this graph, nodes represent simpler, atomic sub\-questions, and directed edges represent data dependencies between them\. The topological order of the graph determines the execution sequence, ensuring that each node’s inputs are fully materialized before it executes\.

Example 1\.Consider the following question from the BIRD benchmark:

> “List all patients who were followed up at the outpatient clinic who underwent a laboratory test in October 1991 and had a total blood bilirubin level within the normal range\.”

The Decomposer breaks this into the three\-node DAG shown in Figure[2](https://arxiv.org/html/2606.17821#S3.F2)\. Nodes 0 and 1 are independent and can be solved in parallel; Node 2 consumes both their results\. The@\[n\]syntax is a dependency placeholder: at execution time, the result set of Nodennis resolved and injected into the downstream node’s prompt and SQL before generation\. For small result sets \(≤\\leq100 rows\), values are inlined as a SQL value list \(e\.g\., anIN \(…\)literal\); for larger result sets, the upstream result is materialized into a SQLite temporary table \(temp\_ds\_node\_n\), which the downstream node can query by name\. This design prevents the LLM from having to express the full multi\-table logic in a single query while remaining efficient regardless of result cardinality \(see Appendix[A\.3](https://arxiv.org/html/2606.17821#A1.SS3)for details\)\.

![Refer to caption](https://arxiv.org/html/2606.17821v1/figures/Picture1.png)Figure 2:DAG for thethrombosis\_predictionexample\. Node 2 executes last, injecting results of Nodes 0 and 1 via@\[n\]placeholders\.To improve the logical soundness of this initial decomposition, we employ a Retrieval\-Augmented Generation \(RAG\) strategy\. Before generating the graph, the system retrieves a set of successful question\-decomposition pairs from a pre\-populated knowledge base\. These examples are dynamically injected into the decomposer’s prompt as few\-shot demonstrations, grounding the LLM in relevant, structured examples and guiding it toward more coherent and viable task graphs\.

The knowledge base is constructed offline from prior successful runs on the benchmark’s training split: experiment logs are parsed to extract question–sub\-question pairs for which the pipeline produced a correct final answer, and these are stored as a JSONL file\. At inference time, we encode the incoming question using a sentence embedding modelReimers and Gurevych \([2019](https://arxiv.org/html/2606.17821#bib.bib24)\)and retrieve thek=3k=3most similar training examples by cosine similarity\.

### 3\.6Query\-Level SQL Generation

For each node in the decomposition graph, the system generates a single SQL query using a zero\-temperature LLM call \(full prompt in Appendix[C\.3](https://arxiv.org/html/2606.17821#A3.SS3)\)\. The prompt instructs the model to produce a valid SQL query grounded in the pruned schema and any available evidence hints, while applying standard robustness conventions such as case\-insensitive string comparisons\. The generated query is executed against the database; if it succeeds, its result is materialized and passed to downstream nodes via the@\[n\]placeholder mechanism\. If execution fails, the node signals failure to the Hierarchical Control loop, which then decides whether to trigger topology refinement\. The full pipeline is described in Algorithm[1](https://arxiv.org/html/2606.17821#alg1)\.

Algorithm 1DecoSearch Pipeline0:Natural Language Question

QQ, Database

𝒟\\mathcal\{D\}, Schema

𝒮\\mathcal\{S\}
0:Final SQL Result

ℛ\\mathcal\{R\}
1:\{Step 1: Schema Selection\}

2:

𝒮p​r​u​n​e​d←SchemaSelector​\(Q,𝒮\)\\mathcal\{S\}\_\{pruned\}\\leftarrow\\text\{SchemaSelector\}\(Q,\\mathcal\{S\}\)
3:\{Step 2: Judger — Direct Path or Decompose\}

4:ifJudger\(

Q,𝒮p​r​u​n​e​dQ,\\mathcal\{S\}\_\{pruned\}\) isDirect Paththen

5:

Q^←SQLGenerator​\(Q,𝒮p​r​u​n​e​d\)\\hat\{Q\}\\leftarrow\\text\{SQLGenerator\}\(Q,\\mathcal\{S\}\_\{pruned\}\)
6:

R,Error←Execute​\(𝒟,Q^\)R,\\text\{Error\}\\leftarrow\\text\{Execute\}\(\\mathcal\{D\},\\hat\{Q\}\)
7:if

Error=NONE\\text\{Error\}=\\text\{NONE\}then

8:return

RR\{Direct execution succeeded\}

9:endif

10:\{Execution failed: fall through to decomposition\}

11:endif

12:\{Step 3: Decomposition\}

13:

G←Decomposer​\(Q,𝒮p​r​u​n​e​d\)G\\leftarrow\\text\{Decomposer\}\(Q,\\mathcal\{S\}\_\{pruned\}\)\{DAG of sub\-questions\}

14:

Q​u​e​u​e←TopologicalSort​\(G\)Queue\\leftarrow\\text\{TopologicalSort\}\(G\)
15:

R​e​s​u​l​t​s←\{\}Results\\leftarrow\\\{\\\}
16:\{Step 4: Hierarchical Control & Materialization\}

17:while

Q​u​e​u​eQueueis not emptydo

18:

n←Q​u​e​u​e\.pop​\(0\)n\\leftarrow Queue\.\\text\{pop\}\(0\)
19:

Qs​u​b←Substitute\(n\.question,Results\)Q\_\{sub\}\\leftarrow\\text\{Substitute\}\(n\.question,Results\)
20:

Q^s​u​b←SQLGenerator​\(Qs​u​b,𝒮p​r​u​n​e​d\)\\hat\{Q\}\_\{sub\}\\leftarrow\\text\{SQLGenerator\}\(Q\_\{sub\},\\mathcal\{S\}\_\{pruned\}\)
21:

Rs​u​b,Error←Execute​\(𝒟,Q^s​u​b\)R\_\{sub\},\\text\{Error\}\\leftarrow\\text\{Execute\}\(\\mathcal\{D\},\\hat\{Q\}\_\{sub\}\)
22:if

Error≠NONE\\text\{Error\}\\neq\\text\{NONE\}then

23:

G←TopologyRefiner​\(G,n,Error\)G\\leftarrow\\text\{TopologyRefiner\}\(G,n,\\text\{Error\}\)
24:if

G​is revisedG\\text\{ is revised\}then

25:

Q​u​e​u​e←TopologicalSort​\(G\)Queue\\leftarrow\\text\{TopologicalSort\}\(G\)
26:continue

27:endif

28:endif

29:

R​e​s​u​l​t​s​\[n\]←Materialize​\(𝒟,Q^s​u​b,Rs​u​b\)Results\[n\]\\leftarrow\\text\{Materialize\}\(\\mathcal\{D\},\\hat\{Q\}\_\{sub\},R\_\{sub\}\)
30:endwhile

31:return

R​e​s​u​l​t​s​\[final\]Results\[\\text\{final\}\]

### 3\.7Hierarchical Control: Dynamic Topology Refinement

To improve resilience against flawed initial decompositions, DecoSearch maintains a hierarchical feedback loop that enables dynamic plan correction at the graph level\. This mechanism allows the system to recover from cases where the decomposition strategy itself is the root cause of failure, rather than individual SQL generation\.

#### Trigger Condition\.

Topology refinement is triggered when the generated SQL at a given node fails to execute successfully\. This signals that the sub\-question may be ill\-formed, overly broad, or structurally inconsistent with the available schema; problems that cannot be resolved by regenerating a query for the same sub\-question\.

#### Action and Resumption\.

Upon receiving the failure signal, the framework activates the Topology Refiner module that provides the LLM with the current DAG structure, the failing node’s sub\-question, and the execution error from the failed query\. The LLM’s task is to produce a revised DAG, which may involve re\-partitioning dependencies, inserting intermediate nodes to break down an overly complex sub\-question, or restructuring the data\-flow to better align with the schema\. The pipeline then adopts the revised graph and resumes execution from the first modified node, preserving the results of all unaffected upstream nodes\. Refinement is bounded by a budgetBB\(the maximum number of topology refinement attempts per query\)\. If the revised DAG also fails to execute and the budget is exhausted, the system accepts the best available result for the failing node and continues execution of all downstream nodes\. This graceful degradation ensures that a single irresolvable sub\-problem does not abort the entire pipeline\.

## 4Experiments

We conduct empirical evaluations to assess the performance of our proposed framework\. The experiments are designed to answer three primary research questions: \(1\) How does our hierarchical search framework compare against state\-of\-the\-art \(SOTA\) Text\-to\-SQL models and \(2\) how much does this approach reduce token usage and cost compared to standard methods? \(3\) Can the proposed method be combined with fine\-tune models to improve accuracy?

#### Datasets\.

We evaluate on two standard benchmarks\. SpiderYuet al\.\([2018](https://arxiv.org/html/2606.17821#bib.bib7)\)contains 2,147 testing queries across 200 databases\. It emphasizes structural SQL complexity \(multi\-table joins, nested queries\)\. BIRDLiet al\.\([2023](https://arxiv.org/html/2606.17821#bib.bib6)\)contains 1,534 development queries across 11 databases designed to test “data\-aware” reasoning, requiring the model to understand actual database content \(e\.g\., value distributions, cell\-level patterns\)\.

Table 1:Comprehensive comparison of Text\-to\-SQL frameworks on BIRD and Spider benchmarks, categorized by learning approach\. “Model Avail\.” indicates whether model weights are publicly available\.LearningMethodModelBIRD EX \(%\)Spider EX \(%\)ApproachAvail\.devdevTraining\-freeDeepEye\-SQL×\\times68\.5184\.44GenaSQL×\\times65\.3281\.93CHESS×\\times69\.6087\.33DAIL\-SQL×\\times59\.3983\.56DIN\-SQL×\\times39\.5764\.51Open\-sourceGPT\-OSS\-120b✓\\checkmark66\.1684\.16GPT\-OSS\-20b✓\\checkmark64\.2183\.09Llama\-4\-Maverick\-17B✓\\checkmark67\.2785\.42Mistral\-nemotron\-12B✓\\checkmark61\.7381\.93Qwen2\.5\-7B✓\\checkmark39\.9677\.27DeepSeek–66\.8185\.56DecoSearch \(ours\)–70\.5388\.31![Refer to caption](https://arxiv.org/html/2606.17821v1/x2.png)\(a\) BIRD
![Refer to caption](https://arxiv.org/html/2606.17821v1/x3.png)\(b\) Spider

Figure 3:Cumulative Execution Accuracy vs\. Cumulative Token Usage \(log scale\) on BIRD \(a\) and Spider \(b\)\. DecoSearch reaches its final accuracy with fewer tokens than all compared methods on both benchmarks, demonstrating superior token efficiency\.
### 4\.1Experimental Setup

Our experimental setup is defined as follows\.

Baselines\.Our method is tested with two categories of baselines: Training\-Free and Fine\-tuned methods\. Training\-free methods operate solely via prompting without any task\-specific fine\-tuning, including CHESSTalaeiet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib5)\), GenaSQLDönderet al\.\([2025](https://arxiv.org/html/2606.17821#bib.bib9)\), and DAIL\-SQLGaoet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib8)\)\. Fine\-tuned methods additionally train or adapt model weights on Text\-to\-SQL data, including XiYan\-SQLLiuet al\.\([2026](https://arxiv.org/html/2606.17821#bib.bib13)\), Agentar\-Scale\-SQLWanget al\.\([2025b](https://arxiv.org/html/2606.17821#bib.bib12)\), CHASE\-SQLPourrezaet al\.\([2024](https://arxiv.org/html/2606.17821#bib.bib4)\), and OmniSQLLiet al\.\([2025](https://arxiv.org/html/2606.17821#bib.bib10)\)\. Because our approach focuses on test\-time reasoning strategy, query routing, structured decomposition, and plan\-level repair, rather than on model parameters or training data, it is orthogonal to these fine\-tuned methods and can be readily combined with them to yield further improvements\.

Implementation Details\.Our framework is model\-agnostic\. For all experiments reported in this paper, all LLM\-driven components \(Judger, Decomposer, SQL Generator, Topology Refiner\) use DeepSeek as the backbone model with a single greedy generation per node\. All LLM calls are cached to ensure full reproducibility\. SQL Generator prompts are lightly adapted per dataset to reflect dataset\-specific conventions: the BIRD prompt enforces case\-insensitive string comparisons \(viaLOWER\(\)\) and treats the evidence string as ground truth, while the Spider prompt emphasizes column examples present in the schema\. The core reasoning structure is identical across both\. Full hyperparameter settings are reported in Appendix[B](https://arxiv.org/html/2606.17821#A2)\.

Evaluation Metric\.The primary metric is Execution Accuracy\. A generated SQL query is deemed correct if and only if its execution result set is identical to that of the ground\-truth query\. Result sets are canonicalized to be robust against arbitrary row and column ordering, as well as known surface\-level formatting artifacts \(e\.g\., concatenated vs\. separate string tokens that convey the same information\)\.

### 4\.2Results and Analysis

![Refer to caption](https://arxiv.org/html/2606.17821v1/x4.png)\(a\) Fine\-tuned backbones
![Refer to caption](https://arxiv.org/html/2606.17821v1/x5.png)\(b\) Open\-source backbones

Figure 4:Execution Accuracy on BIRD when pairing DecoSearch with fine\-tuned \(a\) and open\-source \(b\) backbone models, compared against their DirectSQL baseline\. DecoSearch consistently improves over the direct generation baseline regardless of the backbone, demonstrating its model\-agnostic nature\.#### Overall Performance\.

Evaluation results are summarized in Table[1](https://arxiv.org/html/2606.17821#S4.T1)\. On BIRD and Spider, DecoSearch achieves 70\.53% and 88\.31% EX, respectively, consistently outperforming all training\-free baselines\. These findings validate that our primary performance gains stem from the hierarchical decomposition and the Judger\-led routing strategy\.

#### Token Efficiency\.

Figure[3](https://arxiv.org/html/2606.17821#S4.F3)plots cumulative EX accuracy against cumulative token usage \(log scale\) for all methods\. DecoSearch is consistently the leftmost high\-accuracy curve on both benchmarks, demonstrating that it reaches its peak accuracy with fewer tokens than every compared method\. On BIRD, DecoSearch converges near2×1062\{\\times\}10^\{6\}tokens; CHESS requires approximately2×1072\{\\times\}10^\{7\}tokens to reach a comparable accuracy, a10×10\\timesoverhead\. On Spider, DecoSearch achieves 88\.31% at roughly2×1062\{\\times\}10^\{6\}tokens, a budget at which most baselines remain below 60% cumulative accuracy\. This efficiency advantage is a direct consequence of the Judger\-Led Escalation strategy: the majority of queries are resolved via the direct path, and the expensive decomposition machinery is invoked only for the fraction of queries that genuinely require it\.

#### DecoSearch as a General\-Purpose Wrapper for Fine\-Tuned Models\.

A key property of DecoSearch is that its hierarchical search framework is entirely model\-agnostic: the backbone LLM can be swapped without any modification to the pipeline\. To demonstrate this, we pair DecoSearch with several SOTA fine\-tuned SQL generation models and evaluate on BIRD\. Figure[4](https://arxiv.org/html/2606.17821#S4.F4)shows that DecoSearch consistently improves over the corresponding DirectSQL baseline for every backbone, with gains of\+10\.67\+10\.67pp \(XiYanSQL\-7B\),\+5\.61\+5\.61pp \(GPT\-5\-mini\), and\+3\.52\+3\.52pp \(OmniSQL\-7B\), where pp denotes percentage points\. These results confirm that DecoSearch’s decomposition and routing strategy is complementary to model\-level fine\-tuning: it provides an additional layer of structured reasoning on top of whatever SQL generation capability the backbone already possesses, and can therefore be applied as a drop\-in enhancement to any existing fine\-tuned system\.

### 4\.3Ablation Study

To quantify the contribution of each component, we conduct an ablation study on a 770\-query subset of BIRD, using DeepSeek as the backbone, shown in Table[2](https://arxiv.org/html/2606.17821#S4.T2)\. The Judger is the dominant component: forcing all queries through decomposition causes the largest drop \(−10\.65\-10\.65pp\), revealing that DAG decomposition actively hurts simple queries\. The Judger’s role is to prevent from over\-engineering\. The schema selector is the second most impactful component \(−1\.82\-1\.82pp\), while also inflating token cost6\.3×6\.3\\timeswhen removed\. Removing decomposition entirely costs only−1\.43\-1\.43pp, confirming it targets a small but consequential subset\. Topology refinement provides an additional incremental gain \(−0\.78\-0\.78pp\), with the primary benefit coming from routing and hierarchical decomposition\.

Table 2:Ablation study on BIRD \(dev\)\. Each row removes one component from the full DecoSearch pipeline\.Δ\\DeltaEX is the absolute change in Execution Accuracy relative to the full system\.ConfigurationEX \(%\)Δ\\DeltaEXTokens \(×106\\times 10^\{6\}\)Full Pipeline69\.48—2\.9w/o Judger \(always decompose\)58\.83−\-10\.652\.0w/o Decomposition \(direct path only\)68\.05−\-1\.431\.8w/o Topology Refinement68\.70−\-0\.782\.5w/o Schema Selector67\.66−\-1\.8218\.1

## 5Conclusion

We presented DecoSearch, a training\-free framework that adaptively matches computational effort to query difficulty by routing each question through a Judger\-Led Escalation strategy: simple queries are resolved via direct generation, while complex ones are escalated to a DAG decomposition process with automatic Topology Refinement\. DecoSearch achieves 70\.53% execution accuracy on BIRD and 88\.31% on Spider, surpassing all training\-free baselines and outperforming several fine\-tuned systems on Spider, while consuming an order of magnitude fewer tokens than methods such as CHESS\. The ablation study confirms that Judger\-led routing is the dominant contributor \(−10\.65\-10\.65pp when disabled\), underscoring that DecoSearch’s value lies in the principled orchestration of routing, decomposition, and plan\-level repair\.

## 6Limitations

DecoSearch relies on executable database feedback during inference\. The topology refiner is triggered by SQL execution errors at individual DAG nodes, which assumes that queries can be executed against the target database and that execution failures are informative signals of plan level flaws\. This assumption is common across most training free Text\-to\-SQL methods that incorporate self\-refinement or candidate selection, since execution feedback is the strongest unsupervised signal available at test time\. For settings where execution is unavailable, prohibitively expensive, or returns semantically wrong but syntactically valid results, DecoSearch, like other execution guided methods, cannot intervene\. Nevertheless, the framework remains applicable to any setting where SQL can be executed against the target database, which covers all standard Text to SQL benchmarks and the majority of deployed analytical workloads\.

## References

- A\. Askari, C\. Poelitz, and X\. Tang \(2025\)MAGIC: Generating Self\-Correction Guideline for In\-Context Text\-to\-SQL\.InAAAI Conference on Artificial Intelligence \(AAAI\),Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p2.1),[§2](https://arxiv.org/html/2606.17821#S2.p4.1)\.
- Ł\. Borchmann and M\. Wydmuch \(2025\)Query and Conquer: Execution\-Guided SQL Generation\.arXiv preprint arXiv:2503\.24364\.Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p2.1),[§2](https://arxiv.org/html/2606.17821#S2.p5.1)\.
- Y\. Cai and X\. Wan \(2020\)IGSQL: Database Schema Interaction Graph Based Neural Model for Context\-Dependent Text\-to\-SQL Generation\.In2020 Conference on Empirical Methods in Natural Language Processing \(EMNLP\),Cited by:[§2](https://arxiv.org/html/2606.17821#S2.p1.1)\.
- Z\. Cao, Y\. Zheng, Z\. Fan, X\. Zhang, W\. Chen, and X\. Bai \(2024\)RSL\-SQL: Robust Schema Linking in Text\-to\-SQL Generation\.arXiv preprint arXiv:2411\.00073\.Cited by:[§2](https://arxiv.org/html/2606.17821#S2.p3.1),[§3\.3](https://arxiv.org/html/2606.17821#S3.SS3.p2.1)\.
- X\. Chen, M\. Lin, N\. Schärli, and D\. Zhou \(2024\)Teaching Large Language Models to Self\-Debug\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p2.1),[§2](https://arxiv.org/html/2606.17821#S2.p4.1)\.
- Y\. D\. Dönder, D\. Hommel, A\. W\. Wen\-Yi, D\. Mimno, and E\. S\. Jo \(2025\)Cheaper, Better, Faster, Stronger: Robust Text\-to\-SQL without Chain\-of\-Thought or Fine\-Tuning\.arXiv preprint arXiv:2505\.14174\.Cited by:[§4\.1](https://arxiv.org/html/2606.17821#S4.SS1.p2.1)\.
- B\. Eyal, M\. Mahabi, O\. Haroche, A\. Bachar, and M\. Elhadad \(2023\)Semantic Decomposition of Question and SQL for Text\-to\-SQL Parsing\.InFindings of the Association for Computational Linguistics: EMNLP 2023,Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p2.1),[§2](https://arxiv.org/html/2606.17821#S2.p2.1)\.
- D\. Gao, H\. Wang, Y\. Li,et al\.\(2024\)Text\-to\-sql empowered by large language models: a benchmark evaluation\.InProceedings of the VLDB Endowment,Vol\.17\.Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p1.1),[§2](https://arxiv.org/html/2606.17821#S2.p1.1),[§4\.1](https://arxiv.org/html/2606.17821#S4.SS1.p2.1)\.
- Z\. Gou, Z\. Shao, Y\. Gong,et al\.\(2024\)CRITIC: large language models can self\-correct with tool\-interactive critiquing\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p2.1),[§2](https://arxiv.org/html/2606.17821#S2.p4.1)\.
- J\. Guo, K\. Patel, J\. P\. Ono, W\. He, and L\. Ren \(2025\)Rethinking Agentic Workflows: Evaluating Inference\-Based Test\-Time Scaling Strategies in Text\-to\-SQL Tasks\.arXiv preprint arXiv:2510\.10885\.Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p2.1),[§2](https://arxiv.org/html/2606.17821#S2.p5.1),[§3\.4](https://arxiv.org/html/2606.17821#S3.SS4.p2.1)\.
- A\. B\. Kahn \(1962\)Topological sorting of large networks\.Communications of the ACM5\(11\),pp\. 558–562\.Cited by:[§A\.2](https://arxiv.org/html/2606.17821#A1.SS2.p1.6)\.
- G\. Katsogiannis\-Meimarakis and G\. Koutrika \(2023\)A survey on deep learning approaches for text\-to\-SQL\.The VLDB Journal32,pp\. 905–936\.Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p1.1)\.
- D\. Lee, C\. Park, J\. Kim, and H\. Park \(2025\)MCS\-SQL: Leveraging Multiple Prompts and Multiple\-Choice Selection for Text\-to\-SQL Generation\.International Conference on Computational Linguistics \(COLING\)\.Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p2.1),[§2](https://arxiv.org/html/2606.17821#S2.p5.1)\.
- F\. Lei, J\. Chen, Y\. Ye, R\. Cao, D\. Shin, H\. Su,et al\.\(2025\)Spider 2\.0: Evaluating Language Models on Real\-World Enterprise Text\-to\-SQL Workflows\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§2](https://arxiv.org/html/2606.17821#S2.p1.1)\.
- B\. Li, C\. Chen, Z\. Xue, Y\. Mei, and Y\. Luo \(2026\)DeepEye\-SQL: A Software\-Engineering\-Inspired Text\-to\-SQL Framework\.InACM Special Interest Group on Management of Data \(SIGMOD\),Cited by:[§3\.3](https://arxiv.org/html/2606.17821#S3.SS3.p2.1)\.
- B\. Li, Y\. Luo, C\. Chai, G\. Li, and N\. Tang \(2024\)The dawn of natural language to SQL: are we fully ready?\.Proceedings of the VLDB Endowment17\(11\),pp\. 3318–3331\.Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p1.1),[§2](https://arxiv.org/html/2606.17821#S2.p1.1)\.
- H\. Li, S\. Wu, X\. Zhang, X\. Huang, J\. Zhang, F\. Jiang, S\. Wang, T\. Zhang, J\. Chen, R\. Shi, H\. Chen, and C\. Li \(2025\)OmniSQL: synthesizing high\-quality text\-to\-SQL data at scale\.Proceedings of the VLDB Endowment\.Note:arXiv:2503\.02240Cited by:[§4\.1](https://arxiv.org/html/2606.17821#S4.SS1.p2.1)\.
- J\. Li, B\. Hui, G\. Qu,et al\.\(2023\)Can llm already serve as a database interface? a big bench for large\-scale database grounded text\-to\-sqls\.InAdvances in Neural Information Processing Systems,Vol\.36\.Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p1.1),[§2](https://arxiv.org/html/2606.17821#S2.p1.1),[§4](https://arxiv.org/html/2606.17821#S4.SS0.SSS0.Px1.p1.1)\.
- Y\. Liu, Y\. Zhu, Y\. Gao, Z\. Luo, X\. Li, X\. Shi, Y\. Hong, J\. Gao, Y\. Li, B\. Ding, and J\. Zhou \(2026\)XiYan\-SQL: A Novel Multi\-Generator Framework For Text\-to\-SQL\.arXiv preprint arXiv:2507\.04701\.Cited by:[§4\.1](https://arxiv.org/html/2606.17821#S4.SS1.p2.1)\.
- Y\. Luo, G\. Li, J\. Fan, C\. Chai, and N\. Tang \(2025\)Natural Language to SQL: State of the Art and Open Problems\.Proceedings of the VLDB Endowment18\(12\),pp\. 5466–33547131\.Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p1.1)\.
- A\. Madaan, N\. Tandon, P\. Gupta,et al\.\(2023\)Self\-refine: iterative refinement with self\-feedback\.InAdvances in Neural Information Processing Systems,Vol\.36\.Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p2.1),[§2](https://arxiv.org/html/2606.17821#S2.p4.1)\.
- M\. Pourreza, H\. Chang, N\. Amin,et al\.\(2024\)CHASE\-SQL: Multi\-Path Reasoning and Preference Optimized Candidate Selection in Text\-to\-SQL\.InarXiv preprint arXiv:2410\.01943,Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p1.1),[§1](https://arxiv.org/html/2606.17821#S1.p2.1),[§2](https://arxiv.org/html/2606.17821#S2.p5.1),[§4\.1](https://arxiv.org/html/2606.17821#S4.SS1.p2.1)\.
- M\. Pourreza and D\. Rafiei \(2023\)DIN\-SQL: Decomposed In\-Context Learning of Text\-to\-SQL with Self\-Correction\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p1.1),[§1](https://arxiv.org/html/2606.17821#S1.p2.1),[§2](https://arxiv.org/html/2606.17821#S2.p2.1)\.
- N\. Rajkumar, R\. Li, and D\. Bahdanau \(2022\)Evaluating the Text\-to\-SQL Capabilities of Large Language Models\.arXiv preprint arXiv:2204\.00498\.Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p1.1),[§2](https://arxiv.org/html/2606.17821#S2.p1.1)\.
- N\. Reimers and I\. Gurevych \(2019\)Sentence\-BERT: Sentence Embeddings using Siamese BERT\-Networks\.In2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing \(EMNLP\-IJCNLP\),Cited by:[§3\.5](https://arxiv.org/html/2606.17821#S3.SS5.p5.1)\.
- T\. Scholak, N\. Schucher, and D\. Bahdanau \(2021\)PICARD: Parsing Incrementally for Constrained Auto\-Regressive Decoding from Language Models\.In2021 Conference on Empirical Methods in Natural Language Processing \(EMNLP\),Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p1.1)\.
- R\. Sun, S\. Arik, A\. Muzio, L\. Miculivicius, S\. Gundabathula, P\. Yin, H\. Dai, H\. Nakhost, R\. Sinha, Z\. Wang, and T\. Pfister \(2023\)SQL\-PaLM: Improved Large Language Model Adaptation for Text\-to\-SQL\.arXiv preprint arXiv:2306\.00739\.Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p2.1)\.
- S\. Talaei, M\. Pourreza, Y\. Chang,et al\.\(2024\)CHESS: Contextual Harnessing for Efficient SQL Synthesis\.InarXiv preprint arXiv:2405\.16755,Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p1.1),[§2](https://arxiv.org/html/2606.17821#S2.p3.1),[§2](https://arxiv.org/html/2606.17821#S2.p5.1),[§3\.3](https://arxiv.org/html/2606.17821#S3.SS3.p2.1),[§4\.1](https://arxiv.org/html/2606.17821#S4.SS1.p2.1)\.
- B\. Wang, R\. Shin, X\. Liu,et al\.\(2020\)RAT\-SQL: Relation\-Aware Schema Encoding and Linking for Text\-to\-SQL Parsers\.InAnnual Meeting of the Association for Computational Linguistics \(ACL\),Cited by:[§2](https://arxiv.org/html/2606.17821#S2.p1.1)\.
- B\. Wang, C\. Ren, J\. Yang, X\. Liang, J\. Bai, Q\. Zhang, Z\. Yan, and Z\. Li \(2025a\)MAC\-SQL: A Multi\-Agent Collaborative Framework for Text\-to\-SQL\.InInternational Conference on Computational Linguistics \(COLING 2025\),Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p2.1),[§2](https://arxiv.org/html/2606.17821#S2.p2.1)\.
- P\. Wang, B\. Sun, X\. Dong, Y\. Dai, H\. Yuan, M\. Chu, Y\. Gao, X\. Qi, P\. Zhang, and Y\. Yan \(2025b\)Agentar\-Scale\-SQL: Advancing Text\-to\-SQL through Orchestrated Test\-Time Scaling\.arXiv preprint arXiv:2509\.24403\.Cited by:[§2](https://arxiv.org/html/2606.17821#S2.p5.1),[§4\.1](https://arxiv.org/html/2606.17821#S4.SS1.p2.1)\.
- X\. Wang, J\. Wei, D\. Schuurmans,et al\.\(2023\)Self\-consistency improves chain of thought reasoning in language models\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p2.1)\.
- Y\. Xie, X\. Jin, T\. Xie, M\. Lin, L\. Chen,et al\.\(2024\)Decomposition for Enhancing Attention: Improving LLM\-based Text\-to\-SQL through Workflow Paradigm\.arXiv preprint arXiv:2402\.10671\.Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p2.1),[§2](https://arxiv.org/html/2606.17821#S2.p2.1)\.
- T\. Yu, R\. Zhang, K\. Yang,et al\.\(2018\)Spider: a large\-scale human\-labeled dataset for complex and cross\-domain semantic parsing and text\-to\-sql task\.InProceedings of the 2018 Conference on Empirical Methods in Natural Language Processing,Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p1.1),[§4](https://arxiv.org/html/2606.17821#S4.SS0.SSS0.Px1.p1.1)\.
- B\. Zhai, C\. Xu, Y\. He, and Z\. Yao \(2025\)ExCoT: Optimizing Reasoning for Text\-to\-SQL with Execution Feedback\.arXiv preprint arXiv:2503\.19988\.Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p2.1),[§2](https://arxiv.org/html/2606.17821#S2.p4.1)\.
- D\. Zhou, N\. Schärli, L\. Hou,et al\.\(2023\)Least\-to\-Most Prompting Enables Complex Reasoning in Large Language Models\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p2.1),[§2](https://arxiv.org/html/2606.17821#S2.p2.1)\.
- Y\. Zhu, R\. Jiang, B\. Li, N\. Tang, and Y\. Luo \(2025\)EllieSQL: Cost\-Efficient Text\-to\-SQL with Complexity\-Aware Routing\.arXiv preprint arXiv:2503\.22402\.Cited by:[§1](https://arxiv.org/html/2606.17821#S1.p2.1),[§2](https://arxiv.org/html/2606.17821#S2.p5.1),[§3\.4](https://arxiv.org/html/2606.17821#S3.SS4.p2.1)\.

## Appendix ADetailed Algorithms

### A\.1Schema Selector

Algorithm[2](https://arxiv.org/html/2606.17821#alg2)details theSchemaSelectorcomponent that prunes the full database schema before any downstream LLM call\. The selector makes three sequential LLM calls: first to extract task\-relevant keywords from the question and evidence, then to identify the necessary tables, and finally to pinpoint the required columns within those tables\. All LLM\-returned names are remapped to their true schema counterparts via exact match followed by fuzzy match \(FM\), guarding against surface\-level naming discrepancies in the LLM output\.FuzzyMatchfinds the closest LLM\-returned name to each true schema name by string similarity, returning∅\\varnothingif no sufficiently close match exists\. If the pruning procedure would produce an empty schema, the original schema is returned instead\.

Algorithm 2SchemaSelector: LLM\-Driven Schema Pruning0:Question

QQ, full schema

𝒮\\mathcal\{S\}, evidence

EE
0:Pruned schema

𝒮p​r​u​n​e​d\\mathcal\{S\}\_\{pruned\}, keyword list

KK
1:\{Step 1: Keyword Extraction\}

2:

K←LLMIR​\(Q,E\)K\\leftarrow\\text\{LLM\}\_\{\\text\{IR\}\}\(Q,E\)\{Extract keywords, entities, value mappings\}

3:\{Step 2: Table Selection\}

4:

𝒯s​e​l←LLMTS​\(Q,E,K,𝒮\)\\mathcal\{T\}\_\{sel\}\\leftarrow\\text\{LLM\}\_\{\\text\{TS\}\}\(Q,E,K,\\mathcal\{S\}\)\{Select relevant table names\}

5:\{Step 3: Column Selection\}

6:

𝒞s​e​l←LLMCS​\(Q,E,K,𝒯s​e​l\)\\mathcal\{C\}\_\{sel\}\\leftarrow\\text\{LLM\}\_\{\\text\{CS\}\}\(Q,E,K,\\mathcal\{T\}\_\{sel\}\)\{Select relevant columns per table\}

7:\{Step 4: Name Remapping & Schema Assembly\}

8:

𝒮p​r​u​n​e​d←\{\}\\mathcal\{S\}\_\{pruned\}\\leftarrow\\\{\\\}
9:for alltable

t∈𝒮t\\in\\mathcal\{S\}do

10:

t^←FM\(t\.𝑛𝑎𝑚𝑒,𝒯s​e​l\)\\hat\{t\}\\leftarrow\\text\{FM\}\(t\.\\mathit\{name\},\\;\\mathcal\{T\}\_\{sel\}\)
11:if

t^\\hat\{t\}foundthen

12:

Ct←\{c∈t\.𝑐𝑜𝑙𝑠:FM\(c\.𝑛𝑎𝑚𝑒,𝒞s​e​l\[t^\]\)\}C\_\{t\}\\leftarrow\\\{c\\in t\.\\mathit\{cols\}:\\text\{FM\}\(c\.\\mathit\{name\},\\;\\mathcal\{C\}\_\{sel\}\[\\hat\{t\}\]\)\\\}
13:if

Ct≠∅C\_\{t\}\\neq\\emptysetthen

14:

𝒮p​r​u​n​e​d\.add\(t\.𝑛𝑎𝑚𝑒,Ct\)\\mathcal\{S\}\_\{pruned\}\.\\text\{add\}\(t\.\\mathit\{name\},\\;C\_\{t\}\)
15:endif

16:endif

17:endfor

18:if

𝒮p​r​u​n​e​d=∅\\mathcal\{S\}\_\{pruned\}=\\emptysetthen

19:return

𝒮,K\\mathcal\{S\},\\;K\{Fallback: return original schema\}

20:endif

21:return

𝒮p​r​u​n​e​d,K\\mathcal\{S\}\_\{pruned\},\\;K

### A\.2Topological Execution Order

Algorithm[3](https://arxiv.org/html/2606.17821#alg3)computes the node execution order from the decomposition DAG using Kahn’s algorithmKahn \([1962](https://arxiv.org/html/2606.17821#bib.bib1)\)\. In the DAGG=\(V,E\)G=\(V,E\), a directed edge\(u,v\)\(u,v\)indicates that nodevvconsumes the result of nodeuu, souumust execute beforevv\. Leaf nodes \(in\-degree zero\) have no upstream dependencies and are scheduled first; a cycle detection check guards against malformed LLM outputs\.

Algorithm 3TopologicalSort: Dependency\-Aware Execution Ordering0:DAG

G=\(V,E\)G=\(V,E\); edge

\(u,v\)\(u,v\)means

vvdepends on

uu
0:Execution queue

𝑄𝑢𝑒𝑢𝑒\\mathit\{Queue\}with all dependencies before dependents

1:

𝑑𝑒𝑝𝐶𝑜𝑢𝑛𝑡​\[v\]←\|\{u:\(u,v\)∈E\}\|\\mathit\{depCount\}\[v\]\\leftarrow\|\\\{u:\(u,v\)\\in E\\\}\|for all

v∈Vv\\in V
2:

𝑅𝑒𝑎𝑑𝑦←\{v∈V:𝑑𝑒𝑝𝐶𝑜𝑢𝑛𝑡​\[v\]=0\}\\mathit\{Ready\}\\leftarrow\\\{v\\in V:\\mathit\{depCount\}\[v\]=0\\\}\{Leaf nodes\}

3:

𝑄𝑢𝑒𝑢𝑒←\[\]\\mathit\{Queue\}\\leftarrow\[\\;\]
4:while

𝑅𝑒𝑎𝑑𝑦\\mathit\{Ready\}is not emptydo

5:

n←𝑅𝑒𝑎𝑑𝑦\.pop​\(\)n\\leftarrow\\mathit\{Ready\}\.\\text\{pop\}\(\)
6:

𝑄𝑢𝑒𝑢𝑒\.append​\(n\)\\mathit\{Queue\}\.\\text\{append\}\(n\)
7:for alldependent

ddsuch that

\(n,d\)∈E\(n,d\)\\in Edo

8:

𝑑𝑒𝑝𝐶𝑜𝑢𝑛𝑡​\[d\]←𝑑𝑒𝑝𝐶𝑜𝑢𝑛𝑡​\[d\]−1\\mathit\{depCount\}\[d\]\\leftarrow\\mathit\{depCount\}\[d\]\-1
9:if

𝑑𝑒𝑝𝐶𝑜𝑢𝑛𝑡​\[d\]=0\\mathit\{depCount\}\[d\]=0then

10:

𝑅𝑒𝑎𝑑𝑦\.add​\(d\)\\mathit\{Ready\}\.\\text\{add\}\(d\)\{All of

dd’s dependencies resolved\}

11:endif

12:endfor

13:endwhile

14:if

\|𝑄𝑢𝑒𝑢𝑒\|<\|V\|\|\\mathit\{Queue\}\|<\|V\|then

15:raiseCycleDetectedError

16:endif

17:return

𝑄𝑢𝑒𝑢𝑒\\mathit\{Queue\}

### A\.3Dependency Placeholder Resolution

When a downstream node depends on the result of an upstream nodeuuvia the@\[uu\]placeholder, DecoSearch must inject that result into the downstream node’s sub\-question and SQL prompt before generation begins\. The injection strategy is chosen based on the cardinality of nodeuu’s result set\.

#### Small result sets \(\|ℛu\|≤θ\|\\mathcal\{R\}\_\{u\}\|\\leq\\theta\)\.

If the result contains at mostθ=100\\theta=100rows, the values are serialized directly as a SQL value list\. For example,@\[1\]in the sub\-question text is replaced with the literal tuple\(’v1’, ’v2’, …\), which can appear directly inside anIN \(…\)clause in the generated SQL\.

#### Large result sets \(\|ℛu\|\>θ\|\\mathcal\{R\}\_\{u\}\|\>\\theta\)\.

When the result exceedsθ\\thetarows, inlining the values would produce an unwieldy prompt and an oversized SQL literal\. Instead, DecoSearch materializes the result into a*SQLite temporary table*using:

CREATE TEMPORARY TABLE temp\_ds\_node\_uuAS⟨\\langleSQL⟩u\{\}\_\{u\}\\rangle

The temporary tabletemp\_ds\_node\_uuis then referenced by name wherever@\[uu\]appears in downstream SQL, and a schema description comment is prepended to the downstream node’s prompt so the LLM knows the table exists and can query it like any ordinary table\. The temporary table persists for the lifetime of the database connection and is therefore available to all subsequent nodes in the same execution run\.

#### Fallback\.

If temporary\-table creation is disabled or the result is empty, values are truncated to a adjustable limit \(200200rows by default\) with a comment appended to the SQL noting the truncation\.

### A\.4Topology Refiner

Algorithm[4](https://arxiv.org/html/2606.17821#alg4)detailsTopologyRefiner, invoked from the main pipeline \(Algorithm[1](https://arxiv.org/html/2606.17821#alg1)\) when execution fails at a DAG node and the refinement budgetBBhas not been exhausted\. The refiner serializes the current graph to JSON, constructs a prompt that includes the failing node’s sub\-question and the execution error, and asks the LLM to produce a structurally revised DAG\. The caller rejects the revision if it is isomorphic to the original \(no structural change\) or contains a cycle, and falls back to the original graph in either case\.

Algorithm 4TopologyRefiner: LLM\-Driven DAG Revision0:DAG

GG, failing node

n∗n^\{\*\}, failure reason

ρ\\rho, question

QQ, evidence

EE
0:Revised DAG

G′G^\{\\prime\}\(or

GGif revision is invalid\)

1:

J←Serialize​\(G\)J\\leftarrow\\text\{Serialize\}\(G\)\{Graph

→\\toJSON\}

2:

𝑝𝑟𝑜𝑚𝑝𝑡←BuildPrompt​\(Q,E,J,n∗,ρ\)\\mathit\{prompt\}\\leftarrow\\text\{BuildPrompt\}\(Q,\\,E,\\,J,\\,n^\{\*\},\\,\\rho\)
3:

𝑟𝑒𝑠𝑝𝑜𝑛𝑠𝑒←LLM​\(𝑝𝑟𝑜𝑚𝑝𝑡\)\\mathit\{response\}\\leftarrow\\text\{LLM\}\(\\mathit\{prompt\}\)
4:

J′←ExtractJSON​\(𝑟𝑒𝑠𝑝𝑜𝑛𝑠𝑒\)J^\{\\prime\}\\leftarrow\\text\{ExtractJSON\}\(\\mathit\{response\}\)
5:if

J′J^\{\\prime\}is valid JSONthen

6:

G′←Deserialize​\(J′\)G^\{\\prime\}\\leftarrow\\text\{Deserialize\}\(J^\{\\prime\}\)
7:if

G′G^\{\\prime\}is isomorphic to

GGthen

8:return

GG\{No structural change; skip\}

9:endif

10:if

G′G^\{\\prime\}contains a cyclethen

11:return

GG\{Reject invalid DAG\}

12:endif

13:return

G′G^\{\\prime\}
14:else

15:return

GG\{Parse failure; retain original\}

16:endif

## Appendix BDetailed Experiment Setup

All experiments on both BIRD and Spider use the same configuration unless otherwise stated\. DeepSeek\-V3 \(deepseek\-chat\) serves as the backbone for every LLM role in the pipeline, and a global random seed of4242is fixed across all API calls to ensure reproducibility\. The judger and the direct SQL generator both run at temperatureT=0T=0to produce deterministic outputs, while the decomposer runs atT=0\.1T=0\.1to allow for slightly varied but still constrained decomposition strategies\. The RAG\-based decomposer retrievesk=3k=3similar examples from the training knowledge base usingall\-MiniLM\-L6\-v2embeddings to construct few\-shot decomposition prompts\. If execution fails at any DAG node, the topology refiner is invoked for up toB=3B=3revision attempts before falling back to the best available result\. The schema selector runs a three\-stage LLM pipeline \(keyword extraction, table selection, column selection\) to prune the full database schema before any downstream call; pruning is adaptive with no hard cap on the number of retained tables, and fuzzy matching is applied to guard against naming discrepancies in the LLM output\.

## Appendix CPrompts

We report the core prompt templates used by each pipeline component\. Slots filled dynamically at runtime are shown in\[SLOT\]\.

### C\.1Judger Prompt

Judger PromptSystem:You are an expert SQL architect and query planner\. Your job is to analyze a natural language question and a database schema to decide if the question should be decomposed into multiple sub\-questions or if it can be solved reliably with a single direct SQL query\.STRATEGY: PREFER DIRECT SQL Empirical analysis shows that our Direct SQL path is highly accurate\. Decomposition should be used ONLY as a "Heavy Lifting" tool for logic that cannot be reliably expressed in a single pass\.1\. When to choose Direct SQL \(needs\_decomposition: false\):•Standard Relational Lookups: Even with 2\-\-4 joins, a single query is usually best\.•Simple Filters & Mappings: Using values from the Hint to filter columns\.•Standard Aggregations: SUM, AVG, COUNT, MAX/MIN per group\.•Basic Subqueries: WHERE id IN \(SELECT \.\.\.\) or simple CTEs\.2\. When to choose Decomposition \(needs\_decomposition: true\):•Conflicting Aggregation Grains:Asking for a detail and a scalar at once \(e\.g\., ‘‘List all students AND the average score’’\)\.•Extreme Join Complexity:Joining≥\\geq5 tables where the path is highly ambiguous\.•Complex Multi\-Phase Reasoning:When Step 2 depends on a mathematical result from Step 1 that must be calculated first \(e\.g\., ‘‘Find the top earner, then find all their transactions’’\)\.•Evidence\-Driven Fork:If the Hint specifies a formula or complex mapping that makes a single query extremely nested and error\-prone\.Input: Database Schema:\{schema\} Natural Language Question:\{question\} Task: Your task is to analyze the question and schema\. Decide if the question NEEDS to be decomposed\.Output:Respond with a JSON object\. Only output the JSON object\. Do not include any other text or markdown formatting\. \{"needs\_decomposition": true/false, "reasoning": "A brief explanation of your decision based on the criteria \(simplicity, JOINs, logical steps\)\."\}Now, take a deep breath, and think step by step to make your decision\.

### C\.2Decomposer Prompt

Decomposition Planner PromptSystem:You are a specialized SQL Architect and Query Planner\. Your task is to decompose a complex natural language question into a logically sound dependency graph \(DAG\) of simpler sub\-questions\.MISSION:Break the question into atomic, executable steps where each step produces a result required by the next\.STRICT DECOMPOSITION RULES:•1\. MANDATORY IDENTIFIER PASSING:If Step A depends on Step B, Step B MUST return a specific identifier \(like an ID, Code, or Name\) that Step A can use for filtering\. Example: ‘‘Find the IDs of\.\.\.’’ followed by ‘‘Find the details for IDs in @\[ID\]’’\.•2\. PLACEHOLDER SYNTAX:Use @\[node\_id\] to reference the result of a previous step\.•3\. EVIDENCE IS THE MAP:BIRD Evidence often contains formulas or value mappings\. If the evidence says ‘‘‘Active’ means status=1’’, create a sub\-question that handles that specific filter or calculation\.•4\. NO FRAGMENTATION:Do not create a new node for every single clause\. Only decompose if the result of one query is logically required to build the next \(e\.g\., Finding a Max/Min, or finding a set of IDs to filter a different table\)\.•5\. ROOT NODE PRECISION:The root node \(ID 0\) must be the final transformation\. It should return the exact column\(s\) requested in the original question using the results from its children\.Use the provided successful examples below to understand the correct decomposition format and style\.\{examples\_prompt\_str\}Input: Database Schema:\{schema\} Evidence \(Hint\):\{evidence\}\(Optional\) Question:\{question\}Output Format \(JSON Only\):•Output must be a single JSON object with nodes and edges\.•Nodes: id \(integer\) and question \(string\)\.•Edges: \[parent\_id, child\_id\], where parent depends on child\.•The graph must be a DAG, flowing from leaves to root\.Output only the valid JSON representation of the graph\.

### C\.3SQL Generator Prompt

SQL Generator Prompt \- BIRDSystem:You are an expert SQL generator\. Below, you are presented with a database schema and a question\. Your task is to read the schema, understand the question, and generate a valid\{self\.db\_type\}query to answer the question\.Input: Database Schema:\{schema\_str\} Question:\{sub\_question\} Hint \(Evidence\):\{evidence\}MANDATORY BIRD EXECUTION RULES:•1\. The Hint is GROUND TRUTH:The Hint \(Evidence\) is a strict requirement\. If the hint provides a mapping \(e\.g\., ‘‘’A’’’ for ‘‘’Active’’’\) or a specific filter value, you MUST use it exactly as specified\. Do not deviate from the hint\.•2\. Case\-Insensitivity:SQLite is case\-sensitive for string comparisons\. Use LOWER\(\) on columns and filter values \(e\.g\., LOWER\(city\) = LOWER\(’London’\)\) or LIKE for all string filters unless the hint specifies otherwise\.•3\. Joins:Use explicit JOIN \.\.\. ON syntax\.•4\. Name vs ID:Always prefer using the name column over the id column unless the hint specifies otherwise\.•5\. Null Handling:Be mindful of NULL values in your logic, especially in aggregations and comparisons\.•6\. Final Check:Ensure your query returns all requested information and nothing extra\.Output:Please respond with a JSON object structured as follows: \{"SQL": "Your SQL query in a single string\."\}Take a deep breath and think step by step to find the correct SQL query\.

SQL Generator Prompt \- SpiderSystem:You are a data science expert\. Below, you are presented with a database schema and a question\. Your task is to read the schema, understand the question, and generate a valid\{self\.db\_type\}query to answer the question\. Before generating the final SQL query think step by step on how to write the query\.Input: Database Schema:\{schema\_str\} Question:\{sub\_question\} Hint:\{evidence\}This schema offers an in\-depth description of the database’s architecture, detailing tables, columns, primary keys, foreign keys, and any pertinent information regarding relationships or constraints\. Special attention should be given to the examples listed beside each column, as they directly hint at which columns are relevant to our query\.Database instructions:•Make sure you only output the information that is asked in the question\. If the question asks for a specific column, make sure to only include that column in the SELECT clause, nothing more\.•Predicted query should return all of the information asked in the question without any missing or extra information\.Priority should be given to columns that have been explicitly matched with examples relevant to the question’s context\.Output:Please respond with a JSON object structured as follows: \{ "chain\_of\_thought\_reasoning": "Your thought process\.\.\.", "SQL": "Your SQL query in a single string\." \}Take a deep breath and think step by step to find the correct\{self\.db\_type\}SQL query\.

### C\.4SQL Refiner Prompt

SQL Refiner PromptSystem:You are an expert SQL debugger\. Fix a failing SQL query using the full history of prior attempts and their execution errors\.Input: Question:\[QUESTION\] Database Schema:\[SCHEMA\] Evidence:\[EVIDENCE\] Attempt history \(\[N\]failed attempts\):\[HISTORY\]Task:Review all prior failures and produce a corrected SQL query that addresses every identified issue\. Do not include a trailing semicolon\.Output:Corrected SQL query\.

### C\.5Topology Refiner Prompt

Topology Refiner PromptSystem:You are an expert workflow planner\. Your task is to revise a task decomposition graph that has failed during execution\.Input: Original User Question:\{question\} Current Decomposition Graph \(JSON\):\{graph\_json\_str\} Execution Failure:•The plan failed atNode\{failed\_node\_id\}\.•Sub\-question for this node:"\{sub\-question\}"•Reason for failure:"\{failure\_reason\}"Your Task:Analyze the failure and the overall graph, then propose a corrected version of the graph in JSON format\.Revision Rules:•1\. Localize Changes:Make the minimum necessary changes to fix the issue\. Focus on the area around the failed node\.•2\. Allowed Operations:–Rephrase a node:Modify the ’question’ of a node to be clearer or more specific\.–Decompose a node:Replace a single failed node with two or more simpler nodes\. Ensure you correctly wire the new dependencies\.–Add a node:Add a new intermediate step if a prerequisite was missing\.–Rewire edges:Change the dependencies \(edges\) if the data flow was incorrect\.•3\. Preserve Completed Nodes:Do NOT modify nodes that have already executed successfully \(i\.e\., nodes that are dependencies of the failed node\)\.•4\. Maintain Graph Integrity:The output must be a valid Directed Acyclic Graph \(DAG\)\. Do not introduce cycles\.•5\. Output Format:Your output MUST be only the complete, revised graph in the same JSON format as the input\. Do not include any other text, explanations, or markdown formatting\.Output:Revised Graph \(JSON only\): \{ "nodes": \[\.\.\.\], "edges": \[\.\.\.\] \}

## Appendix DCase Studies

We present two worked examples from the BIRD development set illustrating how DecoSearch decomposes complex questions into a dependency DAG and solves each sub\-question in topological order\. Both examples were solved correctly by DecoSearch while generating a direct SQL attempt failed to produce the right answer\.

### D\.1Example 1: Sequential Dependency Chain

Question & Context —formula\_1databaseNLQ:How many accidents did the driver who had the highest number of accidents in the Canadian Grand Prix have?Evidence:accidents≡\\equivrows where statusId = 3;Canadian Grand Prix≡\\equivraces\.name = ‘Canadian Grand Prix’Judger decision:Decompose\.The question requires a two\-phase aggregation: first materialise the set of Canadian GP race IDs, then identify the most\-accident driver in those races, and finally count their accidents\. Expressing this as a single MAX\(COUNT\(…\)\) subquery is error\-prone in one\-shot generation\.

DAG\(3 nodes; execution order1→2→01\\to 2\\to 0\):

Node 1raceId lookupNode 2top driver@\[1\]Node 0count accidents@\[1\],@\[2\]

leaf

intermediate

root

NodeDeps\.Sub\-question1—Find theraceId\(s\) for the race named*‘Canadian Grand Prix’*\.2@\[1\]Find thedriverIdwith the most accidents \(statusId=3\) among races@\[1\]\.0@\[1\],@\[2\]Count accidents for driver@\[2\]across races@\[1\]\.
Node 1 \(leaf\)—no dependenciesSELECT raceId FROM races WHERE name = ’Canadian Grand Prix’

Node 2—uses@\[1\]SELECT driverId FROM results WHERE statusId = 3 AND raceId IN @\[1\] GROUP BY driverId ORDER BY COUNT\(\*\) DESC LIMIT 1

Node 0 \(root\)—uses@\[1\],@\[2\]SELECT COUNT\(\*\) FROM results WHERE driverId = @\[2\] AND statusId = 3 AND raceId IN @\[1\]

Answer:2✓Matches gold\.

Why decomposition helps:Direct queries for this pattern demand a nestedMAX\(COUNT\(\.\.\.\)\)structure, a complexity that often causes LLMs to hallucinate or mistake it for a flat aggregation\. By materializing the driver ID as an intermediate result, the task is simplified into basicGROUP BYoperations or filters, which the model processes reliably\.

### D\.2Example 2: Parallel Branches with Aggregation

Question & Context —thrombosis\_predictiondatabaseNLQ:What is the ratio of male to female patients among all those with abnormal uric acid counts?Evidence:male≡\\equivSEX=‘M’;female≡\\equivSEX=‘F’;abnormal UA≡\\equivUA≤\\leq8\.0 for males, UA≤\\leq6\.5 for females;ratio=DIVIDE\(count\_M, count\_F\)\\text\{ratio\}=\\texttt\{DIVIDE\(count\\\_M, count\\\_F\)\}Judger decision:Decompose\.The ratio depends on two separate conditional counts with sex\-specific thresholds\. Decomposition computes each count independently, then combines them in the root node, avoiding the compound CASE\-within\-CASE logic that often produces off\-by\-one errors in direct generation\.

DAG\(4 nodes; execution order3→1,2→03\\to 1,2\\to 0; diamond topology\):

Node 3abnormal UApatient IDsNode 1count males@\[3\]Node 2count females@\[3\]Node 0M:F ratio@\[1\],@\[2\]

leaf

intermediate

root

NodeDeps\.Sub\-question3—Find all patient IDs where UA is abnormal: \(SEX=’M’&UA≤\\leq8\.0\)OR\(SEX=’F’&UA≤\\leq6\.5\)\.1@\[3\]Count distinct male patients \(SEX=’M’\) from@\[3\]\.2@\[3\]Count distinct female patients \(SEX=’F’\) from@\[3\]\.0@\[1\],@\[2\]ComputeCAST\(@\[1\] AS REAL\) / @\[2\]\.
Node 3 \(leaf\)—no dependenciesSELECT DISTINCT l\.ID FROM Laboratory l JOIN Patient p ON l\.ID = p\.ID WHERE \(p\.SEX = ’M’ AND l\.UA <= 8\.0\) OR \(p\.SEX = ’F’ AND l\.UA <= 6\.5\)

Node 1—uses@\[3\]SELECT COUNT\(DISTINCT p\.ID\) FROM Patient p WHERE p\.ID IN @\[3\] AND p\.SEX = ’M’

Node 2—uses@\[3\]SELECT COUNT\(DISTINCT p\.ID\) FROM Patient p WHERE p\.ID IN @\[3\] AND p\.SEX = ’F’

Node 0 \(root\)—uses@\[1\],@\[2\]SELECT CAST\(@\[1\] AS REAL\) / NULLIF\(@\[2\], 0\) AS ratio

Answer:0\.2057✓Matches gold\.

Why decomposition helps:The sex\-specific abnormality thresholds make it natural to separate the population filtering \(Node 3\) from the sex\-conditional counts \(Nodes 1 and 2\)\. A direct query must interleave both concerns in a singleCASEexpression, a pattern where LLMs frequently apply the wrong threshold to the wrong gender\. The diamond topology here shows that DecoSearch is not limited to linear chains: two sibling nodes can share a common dependency and produce independent partial results that are combined at the root\.

## Appendix ELLM Usage

In this paper, we leverage LLMs, including ChatGPT and Gemini, to refine sentence\-level writing\.