💬 NLP

CA-SQL: Complexity-Aware Inference Time Reasoning for Text-to-SQL via Exploration and Compute Budget Allocation

CA-SQL is a novel Text-to-SQL framework that enhances reasoning on challenging benchmarks by dynamically scaling exploration breadth based on task complexity, employing evolutionary prompt seeding, and utilizing a voting mechanism to achieve state-of-the-art performance on the BIRD dataset using only GPT-4o-mini.

Original authors: James Petullo, Nianwen Xue

Published 2026-05-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: James Petullo, Nianwen Xue

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a very complex puzzle, but instead of just one person working on it, you have a team of AI detectives. The goal is to translate a question written in plain English (like "Show me all customers who bought red shoes last year") into a specific computer language called SQL that a database understands.

This is the Text-to-SQL problem. While AI has gotten really good at this, it still struggles with the hardest puzzles. The paper argues that current AI methods are like a detective who only looks at one clue at a time, or tries to solve a simple riddle with the same amount of effort as a complex murder mystery.

Here is how the authors' new method, CA-SQL, changes the game, explained through everyday analogies:

1. The "Difficulty Meter" (Scaling Effort)

The Problem: Currently, most AI systems treat every question the same. They spend the same amount of time and computer power on a simple question ("What is the capital of France?") as they do on a complex one ("Find the average salary of employees who managed a project in 2022 and earned more than the median"). This is inefficient.

The CA-SQL Solution: The authors built a "Difficulty Meter." Before the AI starts working, it asks itself: "How hard is this specific puzzle?"

Analogy: Think of it like a home repair service. If you call to fix a leaky faucet, they send a handyman with a basic toolkit. If you call to fix a collapsed roof, they send a whole crew with heavy machinery. CA-SQL dynamically allocates more "brain power" and time to the hard questions and less to the easy ones.

2. The "Seed Garden" (Exploring More Options)

The Problem: To solve a SQL problem, the AI needs to know which parts of the database (tables and columns) are relevant. Most methods pick one list of relevant parts and stick with it. This limits the AI's creativity, like trying to paint a picture using only one specific set of colors.

The CA-SQL Solution: Instead of picking one list, CA-SQL generates a whole "garden" of different lists (schema subsets).

Analogy: Imagine you are baking a cake. Instead of using the same recipe and the same bowl of ingredients every time, CA-SQL creates ten different bowls with slightly different combinations of ingredients. It then uses these different bowls to start baking different versions of the cake. This ensures the AI explores a much wider variety of possibilities.

3. The "Evolutionary Chef" (Improving the Answers)

The Problem: Once the AI generates a few answers, it needs to pick the best one or fix the bad ones. Current methods often just ask the AI, "Which one is right?" or "Try again," which can be repetitive and uncreative.

The CA-SQL Solution: The authors use a technique inspired by evolution.

Analogy: Imagine a chef tasting a soup.
- The Critic: A critic tastes the soup and says, "It's too salty, but the herbs are good. I'd give it a 7/10."
- The Mutation: Instead of just throwing the soup away, the chef takes that recipe and mutates it. Maybe they swap the salt for pepper or add a new spice.
- Crossover: The chef might take the "good herbs" from Soup A and mix them with the "good broth" from Soup B to create a brand new Soup C.
- This process repeats, constantly mixing and tweaking the best ideas to create a "super-soup" that is closer to the perfect answer.

4. The "Scoreboard" (Picking the Winner)

The Problem: After generating many different soup recipes (SQL queries), how do you pick the winner? Most systems use "Majority Voting" (picking the answer that appears most often). But sometimes, the most common answer is just a popular mistake.

The CA-SQL Solution: They use a "Sum-of-Rewards" system.

Analogy: Instead of just counting how many people voted for a candidate, they look at a detailed scoreboard. They add up points for how accurate the answer was, how confident the AI felt, and how much improvement was needed. The answer with the highest total score wins, even if it wasn't the most common one.

The Results: Small Model, Big Wins

The most surprising part of the paper is the result. The authors tested this system using GPT-4o-mini, which is a smaller, cheaper, and less powerful AI model compared to the giants like GPT-4o or GPT-4 that others use.

The Claim: By using their "Difficulty Meter," "Seed Garden," and "Evolutionary Chef," their small AI model beat all other methods on the hardest category of the BIRD benchmark (a tough test for Text-to-SQL).
The Score: They achieved a 51.72% success rate on the "challenging" tasks, outperforming methods that used much larger, more expensive models.

Summary

In short, CA-SQL is a smarter way to use AI to translate English into database code. It doesn't just try harder; it tries smarter. It measures how hard a task is, explores many different starting points, evolves the answers like a biological organism, and picks the winner based on a detailed scorecard. The result is that even a "small" AI can solve the hardest puzzles better than "big" AI if it is given the right strategy.

Technical Summary: CA-SQL

Problem Statement

Recent advancements in inference-time learning have enhanced Large Language Model (LLM) reasoning for Text-to-SQL tasks, yet current solutions struggle significantly with the most complex tasks in the BIRD benchmark. The primary bottleneck is inadequate exploration of the solution space. Existing approaches often attempt to balance exploration (generating diverse candidate queries) and exploitation (refining promising candidates) but fail to generate a sufficient pool of unique, high-quality candidates.

Current limitations include:

Static Schema Linking: Most methods derive candidate queries from a single subset of database tables and columns, limiting the diversity of the search space.
Uniform Compute Allocation: Solutions typically allocate the same computational budget to all tasks, regardless of difficulty. This leads to under-exploration of complex tasks and over-optimization of simple ones.
Ineffective Selection: Standard selection methods, such as simple majority voting or LLM-as-a-judge, often fail to distinguish between subtle differences in query composition or select the correct solution from a pool of diverse candidates.

Methodology: CA-SQL

The authors propose CA-SQL (Complexity-Aware Inference Time Reasoning), a pipeline designed to dynamically scale the breadth and depth of the search process based on the estimated difficulty of a task. The methodology consists of four core components:

1. Task Difficulty Scoring

Before generating solutions, an LLM ( $LLM_{difficulty}$ ) analyzes the natural language question ( $Q$ ), the full database schema ( $S$ ), and a usage example ( $H$ ) to assign a difficulty score $C$ (ranging from 1 to 5). This score dictates the computational budget:

Higher $C$ : Triggers a wider search breadth (more parallel refinements) and greater search depth.
Lower $C$ : Allocates fewer resources, preventing over-optimization on simple tasks.

2. Schema Subset Generation for Prompt Seeding

To overcome the diversity limitations of single-schema subsets, CA-SQL generates a pool of distinct schema subsets ( $S'_1, ..., S'_N$ ) rather than relying on one static subset.

Initial Seeding: The schema generator samples $N$ times to create unique subsets of relevant tables and columns.
Evolutionary Expansion: Instead of resampling from the LLM for every iteration, the pipeline uses crossover (merging two subsets) and mutation (randomly removing table-column pairs) to generate new schema subsets. This evolutionary approach produces novel table-column combinations to seed subsequent candidate queries, increasing the uniqueness of the search space.

3. Candidate Generation and Refinement

For each schema subset, a candidate query ( $Q_C$ ) is generated and executed against the database.

Critic Evaluation: A critic LLM ( $LLM_{critic}$ $LL M_{cr i t i c}$ ) evaluates successful queries, assigning:
- Score ( $s$ ): Accuracy relative to the task intent.
- Confidence ( $k$ ): Certainty in the prediction.
- Mutation Temperature ( $t$ ): The degree of change needed to improve the query.
- Assessment ( $A$ ): Specific recommendations for modification.
Reward Calculation: A reward score $R$ is calculated as $R = s \times (1 - t) \times k$ . This formulation penalizes queries requiring significant changes (high $t$ ) and weights the score by the critic's confidence.
Mutation: Based on the assessment and temperature, a mutator LLM ( $LLM_{mutate}$ ) rewrites the query to produce an improved candidate ( $Q'_C$ ).

4. Scaling and Final Selection

The number of refinement steps and the size of the schema pool are scaled by the difficulty score $C$ .

Search Scaling: The pipeline performs $C$ iterations of subset creation, generation, and refinement. The maximum refinement depth for a single query is capped at $\lfloor C/2 \rfloor + 1$ to prevent degradation of feedback quality over excessive steps.
Sum-of-Rewards Voting: Instead of majority voting, the final solution is selected by identifying the output ( $O$ ) associated with the maximum sum of rewards across all candidate queries in the buffer. This method aggregates the quality of all attempts rather than relying on frequency.

Key Contributions

Dynamic Resource Allocation: The introduction of a task difficulty metric to dynamically scale the inference-time search breadth and depth, ensuring complex tasks receive adequate exploration.
Evolutionary Schema Seeding: A novel method using multiple schema subsets and evolutionary operators (crossover/mutation) to expand the candidate query pool, resulting in higher query uniqueness compared to single-subset approaches.
Novel Selection Mechanism: A sum-of-rewards voting strategy that outperforms standard self-consistency and majority voting techniques by prioritizing the cumulative quality of candidate evaluations.
Empirical Analysis: The first work to empirically analyze the limitations of existing Text-to-SQL exploration techniques and demonstrate the efficacy of difficulty-aware scaling.

Experimental Results

The authors evaluated CA-SQL on the BIRD development dataset using GPT-4o-mini as the base model.

Challenging Tier Performance: CA-SQL achieved a 51.72% Execution Accuracy (EX) on the "challenging" tier of BIRD. This outperforms existing in-context learning (ICL) methods, including those utilizing larger models like GPT-4 and GPT-4o (e.g., MCTS + GPT-4o scored 51.48%).
Overall Performance: The system achieved a 61.06% Execution Accuracy and a 68.77% Soft F1 score across the entire development set.
Comparison: While CA-SQL slightly underperforms on "simple" and "moderate" tiers compared to depth-focused SOTA methods, it significantly closes the performance gap on challenging tasks. The results suggest that proper exploration is more critical than depth for complex problems.

Significance and Claims

The paper claims that exploration is the limiting factor for LLM performance on complex Text-to-SQL tasks, rather than the raw capability of the model. By demonstrating that a smaller, cost-effective model (GPT-4o-mini) combined with a complexity-aware exploration strategy can outperform larger models using standard search methods, the authors argue for a paradigm shift in Text-to-SQL optimization.

The significance lies in:

Cost Efficiency: Achieving state-of-the-art results on difficult tasks without relying on expensive, larger proprietary models.
Scalability: Providing a framework that adapts compute resources to task complexity, avoiding waste on simple queries and ensuring sufficient coverage for hard ones.
Generalizability: The proposed evolutionary search and reward-based selection mechanisms offer a new direction for inference-time reasoning in structured query generation.

The authors remain modest, noting that their performance gains are specific to the "challenging" category and that the difficulty scoring mechanism itself may require further variance analysis in future work. They also acknowledge that their current evaluation is limited to GPT-4o-mini due to budget constraints.