When a question like "list the customers who did not buy every product in a category" reaches a text-to-SQL system, the words can legitimately mean several different queries. The meaning depends on whether the negation covers the "every", and on which column "category" refers to. Current agentic systems cope by guessing, running the query, reading the error or the empty result, and asking the model again. The strongest of them, ACTS-SQL, branches into one child per interpretation and backtracks when a branch fails. That tree search is what makes it accurate. It also costs 3 to 5 minutes and about five sequential model calls per question. Forcing it onto a single linear path drops PostgreSQL accuracy on BIRD-Critic from 58.70% to 45.81%, so the branching is doing real work.
Computational semantics solved a structurally identical problem decades ago. A sentence with several scope-taking words ("every", "some", "not") has a number of readings that grows factorially. Rather than listing them, the field wrote one compact description that stands for all of them at once. A regular tree grammar is such a description: a small set of rewrite rules whose derivations are exactly the valid readings. Regular Tree Grammars as a Formalism for Scope Underspecification used it to remove duplicate readings by intersecting with a filter grammar and to pull out the best reading in about a second, even for sentences with more than $4.5 \times 10^{12}$ readings. This note proposes to move the refinement loop onto that kind of object. The language model is called once and emits an underspecified SQL sketch, meaning a set of query fragments plus constraints on how they may nest and which schema items fill each slot. The sketch compiles into a weighted tree grammar over candidate queries. Every later "refinement" step is a cheap grammar operation driven by database execution, with no further model generation. The key property is that running one shared fragment and seeing it fail removes every reading that contains it, all at once.
Core Claim
Much of what tree-structured refinement buys on ambiguous questions can be kept at a small fraction of the latency. The system needs two things: it must represent interpretations as a packed grammar rather than as separate model-generated branches, and it must spend execution feedback on shared fragments rather than on whole queries. Concretely, we expect a single-call system with parallel, fragment-level execution to come within a few points of ACTS-SQL's accuracy on the ambiguous portion of BIRD-Critic while using roughly one model call instead of about five and seconds rather than minutes of wall-clock time. We expect a clear gain over flat sampling on questions whose correct reading is low-probability under the model, such as inverse-scope and negated-universal questions. Scope Ambiguities in Large Language Models found that inverse-scope readings are systematically harder for models, and sampling from the model's prior under-covers exactly those readings.
This differs from ACTS-SQL in that the branches are never generated by the model and never executed one at a time. It differs from the older underspecification literature in that the grammar's weights and pruning come from a language model and a live database rather than from a hand-built grammar of English. And it differs from Automata-based constraints for language model decoding, which constrains surface syntax such as JSON. We reuse their machinery only to force the model's output to be a well-formed sketch; the semantic packing happens downstream.
Research Program
The first component is the sketch language. It is a small extension of SQL in which a question is written as a bag of fragments. Fragments include predicates, aggregates, EXISTS and NOT EXISTS blocks, and grouping levels. They are connected by dominance constraints, which state "A must end up somewhere above B" without fixing the exact parent. Schema slots can also list several candidate columns or join paths. Hole semantics and dominance constraints are equivalent on well-behaved fragments (Underspecification formalisms: Hole semantics as dominance constraints), and minimal recursion semantics maps into dominance constraints with quadratic-time enumeration on the linguistically common case (Bridging the Gap Between Underspecification Formalisms). These results supply the method. They also constrain the design: outside those restricted fragments, finding a valid configuration becomes NP-complete. We will therefore restrict the sketch grammar so that every sketch falls in the chain-connected fragment, and we will measure how often real questions need something the restriction cannot express.
The second component is the compiler and the weights. The model is fine-tuned, or prompted for API models, to emit sketches under automaton-constrained decoding. Its token probabilities on each slot choice and nesting choice become weights on the grammar rules. That gives an answer to the open question the RTG paper leaves, namely where scalable weights come from. A filter grammar in the style of Koller et al. then removes SQL-equivalent readings before anything is executed. Examples are reorderings of commutative joins, adjacent existential nestings, and alias permutations. This targets the redundancy ACTS-SQL has no mechanism to detect.
The third component replaces refinement with execution over fragments. Each fragment in the grammar, such as a join path, a subquery, or a grouped aggregate, is executed once and in parallel. The results update the grammar. A fragment that errors or returns zero rows where rows are required removes its whole subgrammar. A fragment whose output matches another's merges their readings. Only the few surviving top-weighted full readings are executed. MAG-SQL's sub-query refinement (MAG-SQL) motivates this step: it showed that fixing broken sub-queries beats regenerating whole programs, and that removing execution feedback costs about 10%. Our difference is that the sub-query check applies across all interpretations at once instead of along one sequential path.
A model call is spent a second time only when the grammar is emptied, because every reading died. This is also a natural stopping rule, which RepoCoder (RepoCoder) and iterative-refinement work (Extrapolative Controlled Sequence Generation via Iterative Refinement) identify as an open problem. We stop when a single reading class survives or when the surviving classes agree on execution.
Baselines
The naive reference is one-shot generation with the same backbone: a single model call, a single query, no execution. The file reports vanilla GPT-4 at 46.35% execution accuracy on BIRD (MAG-SQL). We will rerun it with our backbone rather than rely on that figure.
The strongest existing method on the question we care about is ACTS-SQL, which reports 58.70% accuracy on BIRD-Critic PostgreSQL at 3 to 5 minutes and about 5 model calls per instance (ACTS-SQL). It is the right target because it is the only method in the file that explicitly branches over interpretations and backtracks, which is exactly the behaviour we compress. We will run it with the same backbone, databases, and prompt-tuning budget as our system. We will report accuracy and wall-clock time together, including a latency-matched variant cut off after one or two calls. Beating it means being within 2 points of its accuracy at under a tenth of its wall-clock time, or exceeding it at matched latency. On the whole of BIRD, the strongest numbers in the file are SQL-PaLM at 61.7% and MAG-SQL with GPT-4 at 61.08%. We will run MAG-SQL with our backbone as the sequential sub-query refinement competitor.
The most dangerous baseline is execution-based consistency decoding. It samples $N$ queries in parallel, executes all of them, and returns the majority result, which is the approach SQL-PaLM uses. It is also parallel and needs one round, so it attacks our latency argument directly. We give it the same number of database executions and the same model-token budget as our system. No reported result was found on Lacuna for best-of-N or consistency decoding on BIRD-Critic, so we will produce it ourselves.
Two ablations isolate the key ingredient. The first is one-call enumeration: the model lists every interpretation it can think of as complete, separate queries in a single call, and all of them are executed in parallel. This removes the packed grammar, fragment sharing, and equivalence filtering. The second keeps the grammar but executes only full readings, with no fragment-level pruning. If one-call enumeration matches the full system, the formal machinery is unnecessary.
Why not just…?
Why not just prompt a frontier model to pick the most likely reading in one shot? Kamath et al. show that GPT-4 chooses human-preferred scope readings about 98% of the time in forced-choice tests, so for the easy, preferred reading this may suffice. It does not help when the intended reading is the dispreferred one, and on realistic databases one-shot GPT-4 sits far below human performance on BIRD (46.35% versus 92.96%, Can LLM Already Serve as A Database Interface?). Our stratified evaluation reports accuracy separately on questions where the gold reading is the model's top choice and on those where it is not. The proposal only matters on the second stratum, and we will report it honestly even if that stratum turns out to be small.
Why not just sample N queries and take the execution majority? This is the real threat. Clustering by execution result already merges equivalent queries after the fact, so our equivalence filter only saves executions; it does not add correctness. Our claimed advantage is coverage. Sampling from the model's prior rarely produces low-prior scope readings, whereas the grammar holds them by construction. Majority voting also rewards the popular reading even when execution cannot tell the readings apart. The decisive check is the gold-reading coverage rate, meaning how often the correct reading is among the candidates, at equal executions. If sampling reaches the same coverage at the same cost, we will conclude that packing does not pay for SQL-scale ambiguity. We will also narrow the claim to the regime where the number of interacting ambiguity points is large.
Why not just ask the model to list all interpretations in one call? For questions with two ambiguity points this may work as well as a grammar, and our ablation tests exactly that. The grammar should win when independent choices multiply, for example three schema slots with three candidates each crossed with two scope orders. At that size listing everything costs many tokens and misses combinations, while one failing fragment in the grammar prunes a third of the space at once. We will plot the accuracy and token gap against the number of ambiguity points per question.
Why not just distill the reflection into the model, as Meta-Reflection does? Meta-Reflection cuts first-token latency from 951ms to 246ms by internalizing reflection, but it runs without feedback at test time and needs white-box access. Whether a question means "not every" or "every not" depends on the database contents, which no internal codebook can know. MAG-SQL's roughly 10% drop without execution feedback is the relevant evidence. Our system keeps execution but makes it parallel and shared across readings.
Proposed Experiments
Evaluation uses BIRD dev, BIRD-Critic PostgreSQL, and Spider as the unmodified benchmarks. We also build a controlled stress set: templated scope, negation, and aggregation-level questions over Spider databases. Each question has every reading annotated, and the target reading is set to the inverse or dispreferred one in half the cases. This mirrors the balanced surface and inverse design of Kamath et al.'s LSAT sets. For all methods we report execution accuracy, wall-clock time per question, the number of sequential model calls, model tokens, database executions, and gold-reading coverage.
Three checks decide the project. The first is whether, on the ambiguity-annotated portion of BIRD-Critic, the full system reaches within 2 points of ACTS-SQL's 58.70% at under a tenth of its latency. The second is whether, on the stress set, the system beats consistency decoding at equal executions on the inverse-reading half. The third is whether fragment-level pruning beats the one-call enumeration ablation, and whether that gap widens as the number of ambiguity points grows. If the second check fails, the coverage argument is wrong. If the third fails, the formal representation is decorative and the practical takeaway reduces to "enumerate once, execute in parallel", which is still a useful and much cheaper negative result than ACTS-SQL's tree search. We will also report the fraction of real BIRD questions whose ambiguity can be expressed within the restricted, tractable sketch fragment, because that number bounds how far the whole approach can reach.
References
- ACTS-SQL: Agentic and Critic-Oriented Tree-Structured SQL Correctness with Large Language Models
- Regular Tree Grammars as a Formalism for Scope Underspecification
- Scope Ambiguities in Large Language Models
- Automata-based constraints for language model decoding
- Underspecification formalisms: Hole semantics as dominance constraints
- Bridging the Gap Between Underspecification Formalisms: Minimal Recursion Semantics as Dominance Constraints
- MAG-SQL: Multi-Agent Generative Approach with Soft Schema Linking and Iterative Sub-SQL Refinement for Text-to-SQL
- RepoCoder: Repository-Level Code Completion Through Iterative Retrieval and Generation
- Extrapolative Controlled Sequence Generation via Iterative Refinement
- Can LLM Already Serve as A Database Interface? A BIg Bench for Large-Scale Database Grounded Text-to-SQLs
- Meta-Reflection: A Feedback-Free Reflection Learning Framework