Paper deep dive
SPENCE: A Syntactic Probe for Detecting Contamination in NL2SQL Benchmarks
Mohammadtaher Safarzadeh, Hitesh Laxmichand Patel, Afshin Orojlooyjadid, Graham Horwood, Dan Roth
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 97%
Last extracted: 4/27/2026, 9:18:49 AM
Summary
The paper introduces SPENCE (Syntactic Probing and Evaluation of NL2SQL Contamination Effects), a framework designed to detect and quantify data contamination in NL2SQL benchmarks. By generating syntactic variants of natural language queries using LLMs and measuring the degradation in execution accuracy across increasing levels of syntactic divergence (measured by Tree Edit Distance), the authors demonstrate a temporal gradient of contamination. Older benchmarks like Spider, SParC, and CoSQL show significant performance drops and high negative Kendall's tau correlation, suggesting training-time leakage. In contrast, the more recent BIRD benchmark shows minimal sensitivity, indicating it is largely uncontaminated. The study highlights the necessity of syntactic-probing for trustworthy NL2SQL evaluation.
Entities (17)
Relation Signals (8)
SPENCE â evaluates â Spider
confidence 100% · SPENCE systematically generates syntactic variants of test queries for four widely used NL2SQL datasets-Spider, SParC, CoSQL, and the newer BIRD benchmark.
SPENCE â evaluates â BIRD
confidence 100% · We use SPENCE to evaluate multiple high-capacity LLMs... for four widely used NL2SQL datasets... BIRD benchmark.
SPENCE â evaluates â BIRD
confidence 100% · SPENCE systematically generates syntactic variants of test queries for four widely used NL2SQL datasets-Spider, SParC, CoSQL, and the newer BIRD benchmark.
Tree Edit Distance â measures â Syntactic Divergence
confidence 100% · TED thus measures the minimal number of such operations needed to transform one parse tree into another and serves as our syntactic similarity metric.
Spider â exhibitshigh â Contamination
confidence 90% · older benchmarks such as Spider exhibit the strongest negative values and thus the highest likelihood of training leakage.
BIRD â exhibitslow â Contamination
confidence 90% · the more recent BIRD dataset shows minimal sensitivity and appears largely uncontaminated.
Spider â hashighcontamination â LLMs
confidence 90% · older benchmarks such as Spider exhibit the strongest negative values and thus the highest likelihood of training leakage.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Large language models (LLMs) have achieved strong performance on natural language to SQL (NL2SQL) benchmarks, yet their reported accuracy may be inflated by contamination from benchmark queries or structurally similar patterns seen during training. We introduce SPENCE (Syntactic Probing and Evaluation of NL2SQL Contamination Effects), a controlled syntactic probing framework for detecting and quantifying such contamination. SPENCE systematically generates syntactic variants of test queries for four widely used NL2SQL datasets-Spider, SParC, CoSQL, and the newer BIRD benchmark. We use SPENCE to evaluate multiple high-capacity LLMs under execution-based scoring. For each model, we measure changes in execution accuracy across increasing levels of syntactic divergence and quantify rank sensitivity using Kendall's tau with bootstrap confidence intervals. By aligning these robustness trends with benchmark release dates, we observe a clear temporal gradient: older benchmarks such as Spider exhibit the strongest negative values and thus the highest likelihood of training leakage, whereas the more recent BIRD dataset shows minimal sensitivity and appears largely uncontaminated. Together, these findings highlight the importance of temporally contextualized, syntactic-probing evaluation for trustworthy NL2SQL benchmarking.
Tags
Links
- Source: https://arxiv.org/abs/2604.17771v1
- Canonical: https://arxiv.org/abs/2604.17771v1
Trouble viewing inline? Open PDF directly â
Full Text
69,742 characters extracted from source content.
Expand or collapse full text
SPENCE: A Syntactic Probe for Detecting Contamination in NL2SQL Benchmarks Mohammadtaher Safarzadeh * Hitesh Laxmichand Patel Afshin Orojlooyjadid Graham Horwood Dan Roth Oracle AI Abstract Large language models (LLMs) have achieved strong performance on natural language to SQL (NL2SQL) benchmarks, yet their reported accuracy may be inflated by contamination from benchmark queries or structurally sim- ilar patterns seen during training. We intro- duce SPENCE (Syntactic Probing and Eval- uation of NL2SQL Contamination Effects), a controlled syntactic probing framework for de- tecting and quantifying such contamination. SPENCE systematically generates syntactic variants of test queries for four widely used NL2SQL datasetsâSpider, SParC, CoSQL, and the newer BIRD benchmark. We use SPENCE to evaluate multiple high-capacity LLMs under execution-based scoring. For each model, we measure changes in execution accu- racy (âAccuracy) across increasing levels of syntactic divergence and quantify rank sensitiv- ity using KendallâsÏwith bootstrap confidence intervals. By aligning these robustness trends with benchmark release dates, we observe a clear temporal gradient: older benchmarks such as Spider exhibit the strongest negativeÏvalues, while the more recent BIRD dataset shows sub- stantially weaker rank sensitivity. Together, these findings suggest that syntactic-probing evaluations can help identify contamination- like behavior and provide a more trustworthy view of NL2SQL generalization. 1 Introduction As NLP systems are increasingly deployed in real- world settings (Singh, 2023), reliable text-to-SQL systems are becoming an increasingly important practical application area (Singh et al., 2025). A growing body of work has examined data con- tamination and benchmark leakage in large lan- guage models. Dekoninck et al. (2024) highlight how benchmark scores can be artificially inflated and propose retrieval-based overlap checks and * mohammadtaher.safarzadeh@oracle.com Figure 1: Overview of the SPENCE pipeline for evaluating contamination in NL2SQL benchmarks. Given a test dataset, we extract the schema and gold SQL for each example and provide them, together with the natural-language (NL) query, to GPT-5 to generate ten syntactic paraphrases. The generated paraphrases are ranked by syntactic similarity using tree edit distance and filtered via embedding-based similarity and man- ual inspection to ensure semantic fidelity. Both the original and filtered paraphrased queries are then executed with the NL2SQL model, and execution accuracy is computed across paraphrase ranks. The resulting performance curves reveal how model robustness varies with syntactic divergence, en- abling detection of contamination or memorization effects. a âtestset slot guessingâ protocol to uncover hid- den contamination in both open- and closed-source LLMs. Golchin and Surdeanu (2023) and Golchin and Surdeanu (2024) introduce two complemen- tary toolsâthe Data Contamination Quiz and Time Travel in LLMsâwhich convert benchmark items into multiple-choice or guided-completion tasks to reveal memorization signals at the instance and partition levels. Li (2023) compiles an open-source contamination report comparing overlap metrics, perplexity behavior, and n-gram matching across models and benchmarks. Oren et al. (2023) move beyond string-overlap and propose statistical tests based on canonical vs. shuffled benchmark order- ings, providing provable guarantees of test-set con- tamination even in black-box settings. Shi (2023) and Shi et al. (2023) study the pretraining-data detection problem at the instance level, introduc- arXiv:2604.17771v1 [cs.CL] 20 Apr 2026 ing open-source toolkits, the WikiMIA benchmark, and a simple Min-K% Prob method that can flag member vs. non-member examples without know- ing the training corpus. On the same trend, Mattern et al. (2023) and Xu et al. (2024) provide broader benchmark-level studies, showing pervasive leak- age across dozens of LLMs and recommending transparency practices such as âBenchmark Trans- parency Cards.â Together, these efforts demon- strate that contamination can occur in diverse ways and that performance drops on rephrased or reordered samples are a strong signal of non- generalizing, inflated benchmark scoresâan in- sight our work builds upon with controlled para- phrase evaluation in the NL2SQL setting. For a comprehensive survey on data contamination see Cheng et al. (2025); Ravaut et al. (2025). WeinvestigatewhetherLLMsexhibit contamination-like behavior on four widely used NL2SQL benchmarksâSpider (Yu et al., 2018), SParC (Yu et al., 2019b), CoSQL (Yu et al., 2019a), and BIRD (Li et al., 2023)âby probing the effect of syntactic paraphrasing of the natural-language queries on model performance. These benchmarks were released at different times: Spider in September 2018, SParC in June 2019, CoSQL in October 2019, and BIRD in May 2023. Given its earlier release and widespread adoption, we hypothesize that Spider is the most vulnerable to contamination effects, whereas the more recent BIRD benchmark is least likely to be affected. Throughout this paper we use âcontaminationâ in an operational sense: behavior consistent with memorization or near-memorization of benchmark instances due to prior exposureâcharacterized by unusually high stability at small syntactic distances coupled with sharp degradation as structural divergence increasesârather than general compo- sitionality failure, which would affect all queries more uniformly. Our experimental protocol applies controlled paraphrase transformations to each benchmarkâs development set and quantifies the corresponding degradation in execution accuracy, providing an empirical measure of contamination risk across datasets. Our paraphraseâbased probing shares concep- tual similarities with the recent ConStat framework Dekoninck et al. (2024), which redefines contam- ination in large language models as performance inflation that fails to generalize rather than simple string overlap. ConStat introduces three contamina- tion regimes depending on the choice of reference benchmark: syntax-specific (paraphrased versions of the same examples), sample-specific (new exam- ples from the same underlying distribution), and benchmark-specific (different but related bench- marks). Dekoninck et al. (2024) report that sample- specific contamination is often more pronounced and easier to detect than syntax-specific contamina- tion, indicating that models may memorize dataset artifacts beyond the surface form of questions. Our study focuses on the syntax axisâparaphrasing original NL queries to create increasingly distant rephrasingsâbut our methodology could naturally be extended with ConStat-style sample-specific probes (e.g., generating new but semantically equiv- alent NLâSQL pairs) to capture deeper forms of contamination. Thus our results complement Con- Statâs findings: whereas ConStat emphasizes de- tecting non-generalizing performance across bench- marks, our approach offers a fine-grained view of generalization across controlled syntactic transfor- mations. Our work also complements recent investiga- tions into contamination in text-to-SQL models. Ranaldi et al. (2024) study GPT-3.5âs performance on the Spider benchmark versus a newly intro- duced, presumably unseen dataset called Termite. They propose several probesâmost notably an ad- versarial table disconnection (ATD) manipulation and a DC-accuracy testâto measure how much a model has memorized schema and content. Their results show large performance drops on Termite and under ATD, suggesting that high scores on Spider may in part reflect sample-level contamina- tion rather than true generalization. Whereas their analysis operates at the dataset level by contrasting seen versus unseen databases, our approach focuses on the syntactic axis: creating increasingly distant paraphrases of original NL queries while holding schemas fixed. Together, these perspectives give a more complete view of contamination, spanning both sample-level and syntax-level generalization. 2 Methods We introduce SPENCE (Syntactic Probing and Evaluation of NL2SQL Contamination Effects), a controlled framework for detecting and quanti- fying contamination in natural language to SQL (NL2SQL) benchmarks. SPENCE applies system- atic syntactic perturbations to benchmark queries to evaluate whether large language models (LLMs) rely on surface-form memorization or exhibit gen- â15 â10 â5 0 5 Î Accuracy (%) Spider Dataset (Release: September 2018) â15 â10 â5 0 5 Î Accuracy (%) SParC Dataset (Release: June 2019) â15 â10 â5 0 5 Î Accuracy (%) CoSQL Dataset (Release: October 2019) 12345678910 Syntactic Rank â15 â10 â5 0 5 Î Accuracy (%) BIRD Dataset (Release: May 2023) Paraphrase Accuracy Difference vs Original (per rank) Four NL2SQL Benchmarks by Release Date GPT-4o-miniGPT-OSS-120BGPT-OSS-20BLLaMA-3.3-70BLLaMA-3.1-405BO3-mini Figure 2: Difference in execution accuracy (Paraphrase â Original queries) for each model across paraphrase ranks on four NL2SQL benchmarks â Spider (Sep 2018), SParC (Jun 2019), CoSQL (Oct 2019), and BIRD (May 2023) â shown in release order. Bars above the zero line indicate paraphrased queries performed better than the original queries on the same subset; bars below zero indicate performance degradation. All panels share the samex-axis (paraphrase rank) andy-axis scale (accuracy difference). uine compositional generalization. Figure 1 illus- trates the end-to-end evaluation pipeline, which proceeds from the generation of syntactic variants to execution-based assessment and rank-sensitivity analysis across models and datasets. We describe each component of the framework in detail below. 2.1 Data Selection and Preprocessing Our objective is to test whether NL2SQL mod- els exhibit contamination-like behavior on public benchmarks under a realistic âblack boxâ setting where we only observe outputs, not parameters or training data (Brown et al., 2020; Touvron et al., 2023). We conduct all experiments on the devel- opment splits of four widely used NL2SQL bench- marks: Spider, BIRD, CoSQL, and SParC. For each benchmark, we extract the gold SQL queries and associated database schemas, providing a clean ground-truth mapping between natural-language (NL) questions and their executable SQL. For the conversational benchmarks SParC and CoSQL, we paraphrase only the final user question in each dialogue, while keeping all preceding turns un- changed so that the dialogue state and grounding context are preserved. Execution-accuracy changes across paraphrase ranks can therefore be attributed more directly to syntactic perturbations of the tar- get query, rather than to changes in conversational context. 2.2 Paraphrase Generation and Filtering For our NL2SQL experiments we began with the test set from the Spider dataset and created 10 para- phrased versions of each NL query using large language models (LLMs). To ensure the generated queries were valid and semantically meaningful, we included the gold SQL query and its associated database schema in the prompt. This step mini- mizes invalid or ill-formed paraphrases. Each generated paraphrase was parsed into a syntactic dependency tree using thespaCypackage (v3.7) 1 . We then computed the tree edit distance (TED) between each paraphrase and the original NL query, where the allowed operations are inser- tions, deletions, and substitutions of dependency- tree nodes (not just individual tokens). TED thus measures the minimal number of such operations needed to transform one parse tree into another and serves as our syntactic similarity metric. An example of this is provided in Appendix A. 1 https://spacy.io Algorithm 1 Paraphrase Generation and Filtering 1: for each NL query q in Spider test set do 2:Generate 10 paraphrasesp i 10 i=1 using LLM with (q goldSQL , schema) as context 3: for each paraphrase p i do 4: Parsep i andqinto dependency trees T p i ,T q using spaCy 5:ComputeTED i = TreeEditDistance(T p i ,T q ) 6:Compute cosine similarityc i = CosSim(Embed(p i ), Embed(q)) 7: end for 8:Rankp i by TED i (ascending) 9: Retain paraphrases withc i â„ Ï(manually chosen threshold) 10: end for Paraphrases were ranked by TED score from 1 (closest to the original query) to 10 (most distant). Because absolute TED ranges can differ across base queries, the rank index indicates relative dis- tance within a single query but not across queries. To further filter noise, we computed an embedding- based cosine similarity (E5-base-v2; Wang et al., 2024) and retained only paraphrases above a manu- ally selected threshold (chosen via pilot inspection for clear separation between meaningful and irrele- vant paraphrases). This yields nested âgradesâ of increasingly distant paraphrases for probing model generalization (see Appendix C Table 2 for statis- tics on retained paraphrases). To quantitatively verify that this filtering yields semantically faithful paraphrases across rank tiers, we additionally con- duct a small human validation study on 100 Spider examples spanning ranks 1, 5, and 10. Over 85% of paraphrases are judged semantically equivalent to their originals, with no systematic variation across rank (Appendix I). Low TED scores typically correspond to su- perficial lexical changes (synonym swaps, minor word reordering), whereas high TED scores cap- ture more substantial structural changes (clause reordering, subquery restructuring). 2.3 Evaluation on Original and Paraphrased Queries Once the final paraphrase sets were obtained, we evaluated model performance on the original and paraphrased queries in a paired manner. For each base question, we took itsk-th paraphrase (i.e., the paraphrase with rankkaccording to TED) and compared the modelâs output on that paraphrase to its output on the same underlying original question. This ensures that at ârankkâ we are always com- paring paraphrases of the same original questions rather than shifting to a different question subset. Reporting results in this paired fashion isolates the effect of paraphrasing from any changes in the un- derlying question set. We treat contamination detection as a paired hy- pothesis test: âą H 0 : the modelâs accuracy is invariant to para- phrasing (no contamination / robust general- ization); âą H 1 : the modelâs accuracy degrades with syn- tactic distance from original NL query be- cause of memorization or leakage. We evaluated the results using both reasoning and non-reasoning models and compared perfor- mance metrics across ranks. Interestingly, as syn- tactic distance increased (i.e., moving toward para- phrase rank 10), we observed a considerable drop in accuracy. This pattern suggests that models may be overly dependent on syntactic similarity in the NL query and can struggle with paraphrases more distant from the originalâa possible sign of con- tamination or memorization effects. 2.4 LLMs In order to get the paraphrased queries, we used GPT-5.0 (OpenAI, 2025b). We verify in Sec- tion 5 that our findings do not depend on this specific choice of paraphrase generator. Then, for SQL query generation, we choose six LLMs, ranging from small to big open-source LLMs: GPT-OSS-20B, GPT-OSS-120B (OpenAI, 2025a), LLaMA3.3-70B, LLaMA3.1 405B (Dubey et al., 2024), and two commercial models: GPT-4o- mini (OpenAI, 2024), and GPT-O3-mini (OpenAI, 2025c). 2.5 Summary of Experimental Design Across all four benchmarks, our pipeline (i) gener- ates controlled paraphrase sets at varying distances, (i) filters them using cosine similarity thresholds, (i) evaluates original vs. paraphrased accuracy for each subset, and (iv) compares models under the H 0 /H 1 framing above. This design allows us to quantify not only how paraphrasing affects execu- tion accuracy but also how potential data leakage influences a modelâs robustness to linguistic varia- tion. In all our experiments, the results are provided by setting the sampling temperature toT = 1. In Appendix D we show that our results are immune to this by showing the results for T = 0. Finally, we note that the SPENCE pipeline is inexpensive to run. For a given benchmark, de- pendency parsing scales linearly in query length, and tree edit distance between two dependency trees is computed in low-degree polynomial time using the standard ZhangâShasha algorithm (Zhang and Shasha, 1989); both are applied once per para- phrase and contribute negligibly to the total run- time. The dominant costs in the pipeline are the LLM calls for paraphrase generation and for down- stream NL2SQL evaluation, which together ac- count for essentially all of the wall-clock time. Parsing, ranking, and filtering are performed once per dataset and can be cached, so repeating the eval- uation with additional downstream models does not incur additional parsing or TED overhead. 3 Results 3.1 Spider Top panel of Figure 2 shows the results of our syn- tactic paraphrasing probe on the Spider benchmark. Performance on Spider drops sharply even for the earliest paraphrase ranks: all models incur notice- able accuracy losses from rank 1 onward, and the decline accelerates steadily as paraphrases become more syntactically distant. By ranks 8â10, the dif- ference in execution accuracy exceeds 10â15 per- centage points for every model tested. This pattern supports our hypothesis that Spiderâas the ear- liest and most widely used NL2SQL benchmark (released in September 2018)âis the most vulnera- ble to contamination or overfitting to near-verbatim queries. 3.2 SparC Second panel in Figure 2 shows the results of our syntactic paraphrasing probe on the SParC-SQL benchmark. Across all six LLMs evaluated on the SParC-SQL benchmark, accuracy remains roughly stable or slightly improves for the first one to three paraphrase variants, which are closest in syntax to the original queries. Beginning at rank 4, how- ever, the differences in accuracy turn negative and decline steadily as paraphrases become more syn- tactically distant. By ranks 8â10, all models ex- hibit substantial performance drops, in some cases exceeding 10â15 percentage points. Larger mod- els such as LLaMA-3.1-405B degrade less sharply than smaller ones like o3-mini, but no model is immune. These results indicate that syntactic para- phrasing, especially at high divergence, exposes a hidden fragility in NL2SQL performance and provides an empirical signal of potential contami- nation or overfitting to near-verbatim queries. 3.3 CoSQL Third panel in Figure 2 shows the results of our syntactic paraphrasing probe on the CoSQL bench- mark. Model performance is initially robust, with most systems exhibiting small positive gains for the first few paraphrase ranks, similar to what we observe on SParC. However, starting around rank 6, the differences in accuracy begin to turn negative and the drop accelerates toward higher paraphrase distances. By ranks 9â10, all models show clear degradation, though the magnitude of the drop is less severe than on Spider and somewhat more pronounced than on BIRD. This intermediate pat- tern is consistent with CoSQLâs release date (Oc- tober 2019) and its position between the earliest and most widely used benchmark (Spider) and the much newer BIRD dataset: contamination effects appear weaker than on Spider but stronger than on BIRD, underscoring the value of CoSQL as a mid-point stress test for paraphrase robustness. 3.4 BIRD Bottom panel of Figure 2 shows the results of our syntactic paraphrasing probe on the BIRD bench- mark. In contrast to Spider and SParC, model per- formance on BIRD remains remarkably stable un- der paraphrasing. For the first several paraphrase ranks, most models even show slight gains rela- tive to the original queries, and the differences hover near zero across ranks 1â10. Only small, spo- radic drops are observed for some models at higher ranks, and these never approach the steep degrada- tions seen on the older benchmarks. This pattern is consistent with our expectation that BIRDâas the most recent NL2SQL benchmark (released in May 2023)âis least vulnerable to contamination or overfitting to near-verbatim queries, thereby pro- viding a stronger measure of generalization under syntactic variation. 4 Results: Sensitivity of Models to Paraphrase Rank To quantify how sensitive each model is to the ordering of paraphrased queries, we compute KendallâsÏcorrelation between paraphrase rank and the change in execution accuracy relative to the original queries (âAccuracy). KendallâsÏ measures the ordinal association between two vari- ables by comparing the number of concordant and discordant pairs in their rankings; formally, Ï = n c â n d 1 2 n(nâ 1) , wheren c andn d denote the numbers of concordant and discordant pairs, respectively, andnis the to- tal number of observations. The coefficient ranges fromâ1(perfect inverse correlation) to+1(per- fect agreement), with0indicating no monotonic relationship. To estimate uncertainty,we apply non- parametric bootstrapping: for each modelâdataset pair,we randomly resample thenpara- phraseâaccuracy pairs with replacementB = 100 times, recompute KendallâsÏ â(b) for each resample, and derive the empirical 95% confidence interval from the 2.5th and 97.5th percentiles of the bootstrap distributionÏ â(b) B b=1 . This approach provides a robust, distribution-free estimate of variability in the rank correlation.PositiveÏ values indicate that accuracy tends to increase with paraphrase rank, whereas negative values indicate a decline in accuracy as rank increases. Trends across benchmarks. Figure 3 summa- rizes these correlations. Across the three older benchmarksâSpider, SParC, and CoSQLâall models show strongly negative KendallâsÏvalues (typically betweenâ0.6andâ0.95), indicating a consistent degradation in accuracy as paraphrases become more syntactically distant. The bootstrap confidence intervals for these datasets do not over- lap zero, confirming that this trend is statistically robust. In contrast, on the newer BIRD benchmark, KendallâsÏvalues cluster near zero (roughlyâ0.46 toâ0.11, with most confidence intervals spanning zero), suggesting that model performance is largely insensitive to paraphrase rank. This divergence between older and newer datasets supports the hypothesis that models may have memorized or been exposed to earlier bench- marks, yielding higher accuracy on paraphrases closest to the originals, whereas the newer BIRD SpiderSParCCoSQLBIRD â1.0 â0.8 â0.6 â0.4 â0.2 0.0 0.2 0.4 Kendall Ï vs Î Accuracy Paraphrase Rank Sensitivity (Kendall Ï with 95% CI, n_boot=100) GPT-4o-mini LLaMA3-70B LLaMA3.1-405B O3-mini gpt-oss-120b gpt-oss-20b (a) All paraphrase ranks. SpiderSParCCoSQLBIRD â1.00 â0.75 â0.50 â0.25 0.00 0.25 0.50 0.75 Kendall Ï (Rank â„3 vs Î Accuracy) Paraphrase Rank Sensitivity (Kendall Ï ranks â„3 with 95% CI, n_boot=100) GPT-4o-mini LLaMA3-70B LLaMA3.1-405B O3-mini gpt-oss-120b gpt-oss-20b (b) Paraphrase ranksâ„ 3. Figure 3: KendallâsÏbetween paraphrase rank andâAccuracy (paraphrase accuracy minus original accuracy) across the four NL2SQL benchmarks (Spider, SParC, CoSQL, BIRD). Each dashed line corresponds to a model, and the shaded region shows the 95% bootstrap confidence interval based on 100 resamples. (a) All paraphrase ranks. (b) Only ranksâ„ 3. Strongly negative Ïvalues on Spider, SParC and CoSQL indicate sensitivity to paraphrase rank (accuracy drops for more distant paraphrases), whereas the near-zero values and wide confidence intervals on BIRD suggest little or no such sensitivity on the newer benchmark. See section 4 for details of the method implemented. dataset shows little evidence of such contamina- tion. In other words, sensitivity to paraphrase rank appears to âwash outâ for more recent benchmarks. Comparison of all vs. higher-ranked para- phrases. To assess whether performance degra- dation is driven primarily by distant paraphrases, we recompute KendallâsÏusing (i) all paraphrase ranks and (i) only ranksâ„ 3. Table 1 reports the mean correlation across models for each dataset, while Table 3 in Appendix E provides full per- model results with 95% bootstrap confidence inter- vals. Across Spider, SParC, and CoSQL, the correla- tions remain strongly negative (Ï ââ0.7toâ0.9), confirming that execution accuracy consistently declines as syntactic divergence increasesâeven when excluding near-identical paraphrases. For these three datasets, the negative and statistically significant correlations persist when restricted to ranksâ„ 3(Ïbetweenâ0.57andâ1.00), indi- cating that the degradation is not confined to mi- nor surface variations but extends to more substan- tive syntactic rewrites. In contrast, BIRD exhibits weak, statistically indistinguishable correlations un- der both settings (Ï ââ0.35), suggesting limited rank sensitivity and reinforcing that contamination effects are more pronounced in older benchmarks but largely absent in newer data. 5 Controlling for Alternative Explanations We consider four alternative hypotheses that could potentially explain our findings. In evaluating each, Table 1: Average KendallâsÏbetween paraphrase rank and âAccuracy across models for each dataset. Results are shown for all paraphrase ranks and for higher-ranked paraphrases (â„3), isolating the effect of more distant paraphrases. See Appendix E for per-model results with confidence intervals. Dataset All ranks Ranksâ„3 Spider-0.89-0.88 SParC-0.76-0.63 CoSQL -0.71-0.64 BIRD-0.35-0.37 we note that any explanation must account not only for the accuracy decline itself, but for its differ- ential magnitude across benchmarks: the steep- est drops occur on the oldest benchmark (Spider), while BIRDâdespite being the most structurally complex of the fourâshows minimal degradation. Generic paraphrase-invariance or compositionality limitations would predict similar decay patterns across datasets, which is not what we observe. First, we test whether the observed degradation in execution accuracy with increasing syntactic distance is driven by the length of the generated queries rather than by their syntactic structure. In particular, one might suspect that higher-ranked paraphrases (i.e., those with greater syntactic di- vergence) lead to lower accuracy simply because they tend to be longer. To examine this, we plot the distribution of query lengths for syntactic ranks 1, 5, and 10 across the four benchmarks. As shown in Figure 4, the distributions are broadly similar across ranks, indicating that the performance de- cline in older benchmarks such as Spider is not an 05101520253035 0.00 0.02 0.04 0.06 0.08 0.10 0.12 0.14 Density Spider Dataset 05101520253035 SParC Dataset 05101520253035 Length of Paraphrase NL Queries 0.00 0.02 0.04 0.06 0.08 0.10 0.12 0.14 Density CoSQL Dataset 05101520253035 Length of Paraphrase NL Queries BIRD Dataset PDFs of Length Distribution of Paraphrase NL Queries Rank 1Rank 5Rank 10 Figure 4: Probability Density Functions (PDFs) of Paraphrase Length Distributions for Different Ranks in Multiple Datasets. The plot compares the length distributions of paraphrased nat- ural language queries (NLQs) across four datasets: Spider, SPARQL, CoSQL, and BIRD. The colors represent different ranks, with Rank 1 (red) corresponding to paraphrased queries with the closest syntactic similarity to the original query, Rank 10 (blue) representing paraphrased queries with the most dis- tinct syntactic differences, and Rank 5 (purple) representing queries with moderate syntactic similarity. artifact of query length. We further examine whether the observed rank sensitivity might be confounded by lexical overlap between the original and paraphrased queries. To test this, we perform a stratified apples-to-apples analysis based on the Jaccard lexical-overlap score between each paraphrase and its corresponding original query, defined asJ (A,B) = |Aâ©B| |AâȘB| , where AandBdenote the sets of tokens in the original and paraphrased queries, respectively. Paraphrases are grouped into two overlap bins (0.0â0.2, 0.2â 0.4), and within each bin we compute KendallâsÏ between execution accuracy and syntactic rank. If the degradation were purely lexical, accuracy should remain stable once overlap is controlled. However, we find that the negative correlation with syntactic rank persists within all overlap strata, in- dicating that the trend is genuinely driven by struc- tural, rather than lexical, divergence. Figure 5 illustrates this effect for GPT-4o-mini: the unfil- tered accuracyârank curve (black) is shown along- side curves conditioned on the two Jaccard-overlap bins (colored lines). The consistent downward slope across bins confirms that SPENCE primar- ily probes syntactic robustness rather than surface- form similarity. The distribution of Jaccard for all the bench- marks for a few of the ranks is provided in Ap- 12345678910 Syntactic Rank â16 â14 â12 â10 â8 â6 â4 Î Accuracy (%) Accuracy Difference by TED Score Jaccard Bin 0-0.2 Jaccard Bin 0.2-0.4 Figure 5: Accuracy as a function of paraphrase rank for GPT- 4o-mini, conditioned on Jaccard similarity. The black curve shows the unfiltered accuracyârank trend, while the colored curves correspond to two bins of Jaccard-overlap between the original and paraphrased queries. The consistent downward slope across both bins indicates that SPENCE primarily mea- sures syntactic robustness rather than surface-form similarity. pendix G Figure 10. Lastly, we ask whether the stronger rank sensitiv- ity observed in Spider may instead reflect schema- linking dependence. If Spider queries rely more heavily on lexical and structural alignment between the natural-language question and the database schema, syntactic paraphrasing could disrupt these links 2 , leading to larger performance drops. In con- trast, benchmarks like BIRD may exhibit weaker schema-linking bias, and thus show less degrada- tion under syntactic perturbation. For a given LLM, we examined several cases where the original natural language (NL) query resulted in a successful execution, whereas its paraphrased counterpart failed. Among the in- spected samples, we did not observe any instances of broken schema linking.Figure 6 provides one example each from the BIRD and Spider datasets, illustrating the original and paraphrased NL queries alongside their corresponding SQL queries. A closer inspection reveals that all key lex- ical anchors used for schema linking are preserved. For instance, in the BIRD example, the para- phrased NL query retains the keywords"schools", "County", and"open date", which align re- spectively withtable=schools,column=County, andcolumn=OpenDatein the schema. Addition- ally, the identifierDOC=52is drawn from the Evidencesection of the schema and correctly in- corporates the filter values"Alameda County" and"1980". Hence, no information loss or link- 2 For example, consider the case that the schema uses Table with name "Student" and the original query also refers to the number of students. Then, if in the new query we replace "student" with "learner", it might break the schema-link. Original: What is the monthly average number of schools that opened in Alameda County under the jurisdiction of the Elementary School District in 1980? Paraphrased: Over the course of 1980, how many schools were opened in Alameda County under DOC 52, calculated as a monthly average? SELECT COUNT(*) / 12.0 AS monthly_average FROM schools WHERE County = 'Alamedaâ AND DOC = '52â AND STRFTIME('\%Y',OpenDate)= '1980' SELECT COUNT(CDSCode) / 12 FROM schools WHERE DOC = '52â AND County = 'Alameda' AND OpenDate LIKE '1980\%' Original: What are all distinct countries where singers above age 20 are from? SELECT DISTINCT Country FROM singer WHERE Age > 20 Paraphrased: What are the unique countries of singers who are older than 20? SELECT Country FROM singer WHERE Age > 20 Figure 6: Samples of original and paraphrased queries for BIRD (top example) and Spider (bottom example), and the corresponding SQL queries. The paraphrased queries show no sign of schema linkage issue (like deviation from the table- names on the schema nor the column-names). Still, due to the semantical variations, the LLM is unable to generate a correct SQL query for the paraphrased queries. In the example from BIRD, it uses LIKE instead of filtering via STRFTIME. Note that, LIKE might not work as expected if the date is stored in a different format, or if the year is not always at the beginning of the string. In the example from Spider, apparently it missed to add DISTINCT to avoid repetition of countries. ing error occurs. Similarly, in the Spider exam- ple, the words"singer"and"country"correctly map totable=singerandcolumn=Countryin the schema (see Appendix H for the schema details). Finally, we examine whether the observed rank sensitivity could be an artifact of the paraphrase generator itself, rather than a property of the un- derlying benchmarks. Because all paraphrases in our main experiments are produced by GPT-5, one might suspect that the accuracy decline reflects GPT-5âs stylistic idiosyncrasies, or potential ex- posure of GPT-5 to these benchmarks during its own pretraining. If either were the case, substitut- ing a different paraphrase generator should mate- rially change the accuracyârank curves. To test this, we repeat the paraphrase generation stage on Spider using LLaMA-4 Maverick in place of GPT-5, holding the remainder of the SPENCE pipeline fixed: schema conditioning, TED-based ranking, embedding-based filtering, and down- stream NL2SQL evaluation. Figure 7 reports the resultingâAccuracy per paraphrase rank for three downstream models spanning open-source and rea- soning families. The monotonic decline with syn- tactic rank and the slope magnitudes are compa- rable to those obtained under GPT-5 paraphras- ing: gpt-oss-20B drops from 77.05 on the original queries to 69.11 at rank 10, LLaMA-3.3-70B from 76.41 to 68.42, and o3-mini from 76.37 to 70.20. The negative correlation with syntactic rank there- 12345678910 Syntactic Rank 10 8 6 4 2 0 2 Accuracy (%) Spider Paraphrases generated by LLaMA-4 Maverick gpt-oss-20Bo3-miniLLaMA-3.3-70B Figure 7: Difference in execution accuracy (Paraphrase â Original) on Spider when paraphrases are generated by LLaMA-4 Maverick instead of GPT-5, for three downstream NL2SQL models. Bars below the zero line indicate perfor- mance degradation. The monotonic decline with syntactic rank and the slope magnitudes mirror those observed under GPT-5 paraphrasing, indicating that the SPENCE signal is not an artifact of the paraphrase generator. fore persists across paraphrase generators, indicat- ing that the SPENCE signal is robust to paraphrase- generator choice and is unlikely to be explained solely by GPT-5-specific stylistic or exposure ef- fects. 6 Conclusions We introduced SPENCE (Syntactic Probing and Evaluation of NL2SQL Contamination Effects), a controlled syntactic probing framework for detect- ing and quantifying contamination in natural lan- guage to SQL (NL2SQL) benchmarks. By gen- erating ranked sets of syntactically diverse para- phrases and measuring execution accuracy as a function of structural distance, SPENCE offers a reproducible and model-agnostic method for dis- tinguishing genuine generalization from memo- rization of benchmark artifacts. Our experiments across four NL2SQL benchmarks reveal consis- tent rank-sensitivity on older datasetsâSpider, SParC, and CoSQLâbut not on the more recent BIRD benchmark, suggesting that contamination- like rank sensitivity is more pronounced in older benchmarks than in more recent ones. These results underscore the need for syntactic-probing evalua- tions as a critical complement to standard leader- board reporting. In future work, we plan to extend SPENCE beyond the NL2SQL domain to text-to- code and question answering tasks, and to incor- porate automated paraphrase quality controls to support large-scale, systematic robustness auditing of language models. 7 Limitations Our analysis is limited to four public NL2SQL benchmarks (Spider, SParC, CoSQL, and BIRD), which may not fully represent the linguistic or schema diversity of real-world databases. The para- phrases are generated automatically by large lan- guage models and filtered using syntactic metrics (TED, cosine similarity), which could introduce generation biases. Moreover, we focus on execu- tion accuracy as the primary metric; while infor- mative, it conflates multiple error sources such as schema linking and logical form generation. In the multi-turn settings (SParC, CoSQL), we re- strict paraphrasing to the final user turn; extending SPENCE to perturb earlier turns is possible, but would require additional consistency constraints over the dialogue context, and we leave this to future work. Our framework focuses on the syn- tactic axis of contamination; extending SPENCE to sample-level probes (e.g., generating new but semantically equivalent NLâSQL pairs in the style of ConStat) and to semantic contamination is a nat- ural direction for future work. Our evaluation also focuses on general-purpose LLMs rather than SQL- specialized systems such as OmniSQL or Arctic- Text2SQL-R1; extending SPENCE to such models is an important direction for future work. More broadly, the temporal gradient we observe is corre- lational: older benchmarks may differ from newer ones not only in prior exposure risk, but also in dif- ficulty, annotation style, or distributional properties. Finally, our use of KendallâsÏcaptures monotonic sensitivity trends but does not establish causal ex- planations for accuracy degradation under syntactic variation. References Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, and et al. 2020. Language models are few- shot learners. In Advances in Neural Information Processing Systems (NeurIPS). Yuxing Cheng, Yi Chang, and Yuan Wu. 2025. A survey on data contamination for large language models. Preprint, arXiv:2502.14425. Jasper Dekoninck, Mark Niklas MĂŒller, and Martin Vechev. 2024. Constat: Performance-based contami- nation detection in large language models. Preprint, arXiv:2405.16281. Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. 2024. The llama 3 herd of models. arXiv preprint arXiv:2407.21783. Shahriar Golchin and Mihai Surdeanu. 2023. Data con- tamination quiz: A tool to detect and estimate con- tamination in large language models. arXiv preprint arXiv:2311.06233. Shahriar Golchin and Mihai Surdeanu. 2024. Time travel in llms: Tracing data contamination in large language models. Preprint, arXiv:2308.08493. Jinyang Li, Binyuan Hui, Ge Qu, Jiaxi Yang, Binhua Li, Bowen Li, Bailin Wang, Bowen Qin, Ruiying Geng, Nan Huo, Xuanhe Zhou, Chenhao Ma, Guoliang Li, Kevin C.C. Chang, Fei Huang, Reynold Cheng, and Yongbin Li. 2023. Can llm already serve as a database interface? a big bench for large-scale database grounded text-to-sqls. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS â23, Red Hook, NY, USA. Curran Associates Inc. Yucheng Li. 2023. An open source data contamination report for large language models. arXiv preprint arXiv:2310.17589. Justus Mattern, Fatemehsadat Mireshghallah, Zhijing Jin, Bernhard Schölkopf, Mrinmaya Sachan, and Tay- lor Berg-Kirkpatrick. 2023. Membership inference attacks against language models via neighbourhood comparison. In Findings of the Association for Com- putational Linguistics: ACL 2023. OpenAI. 2024. Gpt-4o mini: advancing cost-efficient intelligence. Available athttps://openai.com/ index/gpt-4o-mini/. OpenAI. 2025a. gpt-oss-120b & gpt-oss-20b model card. Preprint, arXiv:2508.10925. OpenAI. 2025b.Openai gpt-5: Smartest, fastest, most useful model yet, with built-in thinking that puts expert-level intelligence in everyoneâs hands. Available athttps://openai.com/index/ introducing-gpt-5/. OpenAI. 2025c. Openai o3-mini: Pushing the frontier of cost-effective reasoning. Available athttps:// openai.com/index/openai-o3-mini/. Yonatan Oren, Nicole Meister, Niladri S. Chatterji, Faisal Ladhak, and Tatsunori B. Hashimoto. 2023. Proving test set contamination in black box language models. arXiv preprint arXiv:2310.17623. Federico Ranaldi, Elena Sofia Ruzzetti, Dario Ono- rati, Leonardo Ranaldi, Cristina Giannone, Andrea Favalli, Raniero Romagnoli, and Fabio Massimo Zan- zotto. 2024. Investigating the impact of data contam- ination of large language models in text-to-sql trans- lation. In Findings of the Association for Computa- tional Linguistics ACL 2024, pages 13909â13920. Mathieu Ravaut, Bosheng Ding, Fangkai Jiao, Hailin Chen, Xingxuan Li, Ruochen Zhao, Chengwei Qin, Caiming Xiong, and Shafiq Joty. 2025. A comprehen- sive survey of contamination detection methods in large language models. Preprint, arXiv:2404.00699. WeijiaShi.2023.Detect-pretrain-code- contamination.https://github.com/swj0419/ detect-pretrain-code-contamination. Weijia Shi, Anirudh Ajith, Mengzhou Xia, Yangsibo Huang, Daogao Liu, Terra Blevins, Danqi Chen, and Luke Zettlemoyer. 2023. Detecting pretraining data from large language models. arXiv preprint arXiv:2310.16789. Jyotika Singh. 2023. Natural Language Processing in the Real World: Text Processing, Analytics, and Classification. Chapman and Hall/CRC. Jyotika Singh, Weiyi Sun, Amit Agarwal, Viji Krishna- murthy, Yassine Benajiba, Sujith Ravi, and Dan Roth. 2025. Can LLMs narrate tabular data? an evaluation framework for natural language representations of text-to-SQL system outputs. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing: Industry Track, pages 883â 902, Suzhou (China). Association for Computational Linguistics. Hugo Touvron, Louis Martin, Kevin Stone, Peter Al- bert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, and et al. 2023. Llama 2: Open foun- dation and fine-tuned chat models. arXiv preprint arXiv:2307.09288. Liang Wang, Nan Yang, Xiaolong Huang, Binx- ing Jiao, Linjun Yang, Daxin Jiang, Rangan Ma- jumder, and Furu Wei. 2024. Text embeddings by weakly-supervised contrastive pre-training. Preprint, arXiv:2212.03533. Ruijie Xu, Zengzhi Wang, Run-Ze Fan, and Pengfei Liu. 2024. Benchmarking benchmark leakage in large language models. arXiv preprint arXiv:2404.18824. Tao Yu, Rui Zhang, Heyang Er, Suyi Li, Eric Xue, Bo Pang, Xi Victoria Lin, Yi Chern Tan, Tianze Shi, Zihan Li, Youxuan Jiang, Michihiro Yasunaga, Sun- grok Shim, Tao Chen, Alexander Fabbri, Zifan Li, Luyao Chen, Yuwen Zhang, Shreya Dixit, Vincent Zhang, Caiming Xiong, Richard Socher, Walter S. Lasecki, and Dragomir Radev. 2019a. CoSQL: A conversational text-to-SQL challenge towards cross- domain natural language interfaces to databases. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Lan- guage Processing (EMNLP-IJCNLP), pages 1962â 1979, Hong Kong, China. Association for Computa- tional Linguistics. Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingn- ing Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev. 2018. Spider: A large-scale human-labeled dataset for complex and cross-domain semantic pars- ing and text-to-SQL task. In Proceedings of the 2018 Conference on Empirical Methods in Natural Lan- guage Processing, pages 3911â3921, Brussels, Bel- gium. Association for Computational Linguistics. Tao Yu, Rui Zhang, Michihiro Yasunaga, Yi Chern Tan, Xi Victoria Lin, Suyi Li, Heyang Er, Irene Li, Bo Pang, Tao Chen, Emily Ji, Shreya Dixit, David Proctor, Sungrok Shim, Jonathan Kraft, Vin- cent Zhang, Caiming Xiong, Richard Socher, and Dragomir Radev. 2019b. SParC: Cross-domain se- mantic parsing in context. In Proceedings of the 57th Annual Meeting of the Association for Computa- tional Linguistics, pages 4511â4523, Florence, Italy. Association for Computational Linguistics. Kaizhong Zhang and Dennis Shasha. 1989. Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal on Computing, 18(6):1245â1262. A TED Computation To quantify syntactic divergence between original and paraphrased queries, we compute the Tree Edit Distance (TED) between their dependency parses. Figure 8 illustrates the alignment between two se- mantically equivalent questions drawn from our paraphrase set. TED measures the minimal num- ber of structural operationsâinsertions, deletions, and substitutionsârequired to transform one de- pendency tree into another. In this example, the in- terrogative span (how many singers) remains struc- turally identical across both trees, whereas the pred- icate transitions from an active possessive form (have) to a passive recorded-state construction (are recorded in the database). Such substitutions cor- respond to update operations, while the addition of prepositional modifiers (e.g., in the database) contributes insert operations. The cumulative cost of these edits defines the syntactic distance rank used throughout SPENCE to order paraphrases and correlate model performance with structural diver- gence. B Prompt Template Given the following database schema and an SQL query, generate num_queries distinct natural language questions that describe the purpose and output of the SQL query. schema_definitions SQL Query: sql_query Instructions: 1. Generate num_queries natural language questions that reflect the intent of the SQL query. 2. Each question should vary in phrasing, structure, and wording, but all questions must remain logically equivalent. (a) How many singers do we have? ROOTâhave(VERB) singer(NOUN) many(ADJ) how(SCONJ) do(AUX)we(PRON)?(PUNCT) (b) How many singers are recorded in the database? ROOTârecorded(VERB) singer(NOUN) many(ADJ) how(SCONJ) are(AUX)in(ADP) database(NOUN) the(DET) ?(PUNCT) Figure 8: Dependency-tree alignment for two semantically equivalent questions: (a) âHow many singers do we have?â and (b) âHow many singers are recorded in the database?â. Each node denotes a token annotated with its Universal Part- of-Speech (POS) tag, and edges indicate headâdependent re- lations. Colors correspond to minimal tree-edit operations: gray = match (preserved structure), orange = update (mor- phological substitution, e.g., doâare, haveârecorded), and teal = insert (new constituents such as in the database). POS tags follow the Universal Dependencies standard:VERB(verb), NOUN(noun),ADJ(adjective),SCONJ(subordinating conjunc- tion),AUX(auxiliary verb),ADP(adposition/preposition),DET (determiner),PRON(pronoun), andPUNCT(punctuation). The shared interrogative phrase âhow many singersâ remains iden- tical across both trees, while the predicate transitions from an active possessive to a passive recorded-state form. 3. Do not include explanations, task descriptions, or any additional comments in the output. Output Format: 1. <First question> 2. <Second question> ... num_queries. <Nth question>. C Paraphrase Examples Table 2 presents examples of the paraphrased queries sorted by their TED distance from BIRD dev-set benchmark. D Effect of LLM Temperature We wanted to see how robust the results are when the temperature of the LLM changes. So, we ran the experiments with temperature=0, for the LLM for both the query generation and SQL generation. We tried GPT-OSS-20B and GPT4o-mini(OpenAI, 2024) for all datasets, and got the performance drop across all ranks. Figure 9 shows the corresponding results, where we present the performance drop for both temperatures 0.0 and 1.0, represented via âT0â and âT1â on the LLM names. As shown, the LLM temperature does not change the trend of the results, 12345678910 Syntactic Rank â16 â14 â12 â10 â8 â6 â4 â2 0 Î Accuracy (%) Spider Dataset(Release: September 2018) 12345678910 Syntactic Rank â8 â6 â4 â2 0 2 Î Accuracy (%) SParC Dataset(Release: June 2019) 12345678910 Syntactic Rank â4 â2 0 2 4 6 8 Î Accuracy (%) CoSQL Dataset(Release: October 2019) 12345678910 Syntactic Rank â4 â3 â2 â1 0 1 2 3 4 Î Accuracy (%) BIRD Dataset(Release: May 2023) gpt-4o-mini-T0gpt-4o-mini-T1gpt-oss-20b-T0gpt-oss-20b-T1 Figure 9:Difference in execution accuracy (Para- phrase â Original queries) for GPT-OSS-20B and GPT4o-mini across paraphrase ranks on four NL2SQL benchmarks â Spi- der (Sep 2018), SParC (Jun 2019), CoSQL (Oct 2019), and BIRD (May 2023) â shown in release order. Similar to Figure 2, anything above the zero line indicate paraphrased queries outperformed the original queries and vice versa. We show the temperature=0 and temperature=1 with âT0â and âT1â, respectively, added at the end of LLM names. still the same trend on the performance-drop with increasing the rank exist. So, the temperature does not affect the leakage and with a wide range of temperatures we still observe the same issue. E Full Table for Kendall values Detailed version of our results is presented in Table 3. F Length Distribution of Paraphrase NL Queries As shown in Figure 4, the probability density func- tions (PDFs) of paraphrased query lengths are largely similar across ranks and datasets. Although higher-rank paraphrases (e.g., Rank 10 in blue) tend to exhibit slightly broader or right-shifted distributions compared to lower-rank paraphrases (e.g., Rank 1 in red), the overall differences are minute. This indicates that the observed decline in Table 2: Examples of paraphrased queries for one original question from the BIRD dataset, sorted by normalized Tree Edit Distance (TED) from the original. Lower TED indicates closer syntactic similarity. Original query: How many active and closed District Community Day Schools are there in the county of Alpine? Paraphrase queryTED (norm) How many schools in Alpine County are either closed or currently active?0.4375 How many schools in Alpine County are classified as either active or closed?0.4545 How many schools in the county of Alpine have a status of closed or active?0.4571 Can you determine how many schools in Alpine County are listed as either active or closed?0.5000 Can you count the schools in Alpine County that are marked as either active or closed?0.5556 What is the total number of schools in Alpine County with a status of "Closed" or "Active"?0.5610 What is the total count of schools in Alpine County with their status listed as "Closed" or "Active"? 0.5714 What is the number of schools in Alpine County that are either operational or were previously closed? 0.5946 What is the number of schools in Alpine County that have an "Active" or "Closed" status?0.6000 Provide the count of schools within Alpine County that are currently active or have been closed.0.6389 Table 3: KendallâsÏbetween paraphrase rank andâAccu- racy (paraphrase accuracy minus original accuracy) for each model and benchmark. Two columns per model: âAll ranksâ and âRanksâ„ 3â. Values in bold have 95% bootstrap con- fidence intervals entirely below zero, indicating statistically significant rank sensitivity at α = 0.05. DatasetModelÏ All ranks95% CI Ï Ranksâ„ 395% CI SpiderGPT-OSS-120-0.78[-1.00, -0.46] -0.79[-1.00, -0.36] SpiderGPT-OSS-20-0.91[-1.00, -0.76] -0.86[-1.00, -0.34] SpiderGPT-4o-mini-0.91[-1.00, -0.35] -0.86[-1.00, -0.36] SpiderLLaMA3.3-70B -0.87[-1.00, -0.62] -0.86[-1.00, -0.51] SpiderLLaMA3.1-405B -0.96[-1.00, -0.74] -1.00[-1.00, -1.00] SpiderO3-mini-0.91[-1.00, -0.65] -0.93[-1.00, -0.74] SParCGPT-OSS-120-0.82[-0.95, -0.67] -0.79[-1.00, -0.45] SParCGPT-OSS-20-0.73[-1.00, -0.32]-0.64[-1.00, -0.08] SParCGPT-4o-mini-0.73[-1.00, -0.38]-0.57[-1.00, -0.13] SParCLLaMA3.3-70B -0.87[-1.00, -0.53] -0.79[-1.00, -0.23] SParCLLaMA3.1-405B-0.64[-0.92, -0.30]-0.43[-0.83, 0.09] SParCO3-mini-0.69[-0.95, -0.30]-0.57[-1.00, -0.16] CoSQL GPT-OSS-120-0.73[-1.00, -0.25]-0.64[-1.00, -0.01] CoSQL GPT-OSS-20-0.78[-1.00, -0.40]-0.71[-1.00, 0.04] CoSQL GPT-4o-mini-0.78[-1.00, -0.36]-0.64[-1.00, -0.06] CoSQL LLaMA3.3-70B -0.78[-1.00, -0.52] -0.79[-1.00, -0.29] CoSQL LLaMA3.1-405B-0.64[-0.83, -0.40] -0.57[-0.91, -0.21] CoSQL O3-mini-0.69[-1.00, -0.16]-0.50[-1.00, 0.32] BIRDGPT-OSS-120-0.47[-0.85, -0.02]-0.50[-1.00, 0.16] BIRDGPT-OSS-20-0.42[-0.87, 0.12]-0.43[-0.84, 0.14] BIRDGPT-4o-mini-0.33[-0.82, 0.53]-0.64[-1.00, 0.09] BIRDLLaMA3.3-70B-0.11[-0.73, 0.32]-0.14[-0.77, 1.00] BIRDLLaMA3.1-405B-0.39[-0.88, 0.21]-0.24[-1.00, 0.62] BIRDO3-mini-0.38[-0.88, 0.05]-0.36[-1.00, 0.25] execution accuracy with increasing syntactic rank (Section 5) cannot be attributed simply to differ- ences in query length. G Jaccard similarity Distribution of Paraphrase NL Queries Figure 10 shows the probability density functions (PDFs) of Jaccard similarity between paraphrased and original natural language queries across dif- ferent ranks and datasets. As expected, Rank 1 paraphrases (light red) exhibit the highest Jaccard similarity, closely matching the lexical content of the original query, while higher ranks (e.g., Rank 10 in cyan) show progressively lower overlap. However, the overall separation between ranks re- mains moderate, suggesting that even paraphrases with substantial syntactic divergence retain partial lexical overlap with the source query. This pat- tern indicates that the SPENCE ranking procedure successfully produces a graded spectrum of para- phrasesâranging from near-identical reformula- tions to substantially reworded variantsâwithout collapsing into either trivial copies or semantically unaligned outputs. H Schema Linking Preservation Tables 4 and 5 show some examples of for Bird and Spider datasets where the paraphrased queries keep the schema linking, while LLMs fail to get the correct SQL query based on them. On each 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 Density Spider DatasetSParC Dataset 0.00.10.20.30.40.50.60.70.80.91.0 Jaccard Similarity Between Paraphrases and Original Query 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 Density CoSQL Dataset 0.00.10.20.30.40.50.60.70.80.91.0 Jaccard Similarity Between Paraphrases and Original Query BIRD Dataset PDFs of Jaccard Similarity Between Paraphrases and Original Query by Rank Rank 1Rank 5Rank 10 Figure 10: Probability Density Functions (PDFs) of Jaccard Similarity Between Paraphrases and Original Query for Dif- ferent Ranks in Multiple Datasets. The plot compares the Jaccard similarity distributions of paraphrased natural lan- guage queries (NLQs) across four datasets: Spider, SPARQL, CoSQL, and BIRD. The colors represent different ranks, with Rank 1 (light red) corresponding to paraphrased queries with the closest similarity to the original query, Rank 10 (cyan) representing paraphrased queries with the most distinct differ- ences in similarity, and Rank 5 (dark red) representing queries with moderate similarity to the original. dataset, there are several rows where Original and Paraphrased-Rx show the original or paraphrased samples, in which "Rx" refers to the sample with Rank= x â 1,..., 10. Also, Listings 1 and 2 shows the corresponding schema. The example for some ranks are missing, since the generated query did not satisfy the bare minimum quality bars on the query generation. This happens more for smaller queries, like the one in Table 5, and less often for longer more complex queries, like the one in Table 4. As shown in both tables, the generated queries hold all the required information to create a SQL query, while keeping all the keywords aligned with the schema. This is the result of our design choice to pass both the gold-query and the schema for generating new queries, so that there is no mis- alignment and schema-linking issue between the schema and the new queries. I Human Validation of Semantic Equivalence To verify that TED-based ranking reflects struc- tural rather than semantic divergence, we conduct a small human study on paraphrase fidelity. We sample 100 base questions from the Spider devel- opment set and, for each, extract the paraphrases at ranks 1, 5, and 10 produced by our pipeline (Sec- tion 2)âyielding 300 paraphraseâoriginal pairs in total. Annotators were shown each pair with- out rank information and asked to assign one of three labels: equivalent (the paraphrase preserves the meaning of the original question), partially equivalent (the paraphrase shifts or omits a non- trivial part of the original meaning), or not equiva- lent (the paraphrase asks a meaningfully different question). The rank at which each paraphrase was drawn was hidden from annotators to avoid anchor- ing effects. Across the 300 pairs, more than 85% are judged semantically equivalent to their origi- nals, and the proportion of equivalent judgments does not vary systematically with rank: rank-10 paraphrases are judged faithful at a rate compara- ble to rank-1 paraphrases. The absence of a rank trend in semantic judgments is consistent with our interpretation that TED ranks capture structural reorganization (clause reordering, predicate substi- tution, passive/active shifts) rather than changes in underlying meaning. This supports the use of TED-based ranking as a probe for syntacticârather than semanticârobustness, and ensures that the ac- curacy decline observed at higher ranks is not an artifact of paraphrase quality. We note that this is a small-scale validation in- tended to confirm that the filtering pipeline (Sec- tion 2) produces meaning-preserving paraphrases across rank tiers; a larger annotation effort with inter-annotator agreement statistics would be a nat- ural extension, and we leave this to future work. Table 4: Samples of original and paraphrased queries and the corresponding SQL queries, for a sample from Bird dataset. The paraphrased queries show no sign of schema linkage issue, and as a result of semantic edits, the LLM is unable to generate a correct SQL query. On each row, Original/Paraphrased-Rx shows if it is the original or paraphrased samples, and "Rx" refers to the sample with Rank= xâ1,..., 10. QuerySQL Original: What is the monthly average number of schools that opened in Alameda County under the jurisdiction of the Elementary School District in 1980? SELECT COUNT(*) / 12.0 AS monthly_average FROM schools WHERE County = âAlamedaâ AND DOC = â52â AND STRFTIME(â%Yâ, OpenDate) = â1980â Paraphrased-R1: What is the monthly average of schools that opened in Alameda County in 1980 with a DOC value of 52? SELECT COUNT(DISTINCT School) FROM schools WHERE SUBSTR(OpenDate, 1, 4) = â1980â AND County = âAlamedaâ AND DOC = â52â Paraphrased-R3: For Alameda County in 1980, what is the monthly average of schools that opened and had a DOC value equal to 52? SELECT COUNT(CDSCode) FROM schools WHERE County = âAlamedaâ AND DOC = â52â AND STRFTIME(â%Yâ, OpenDate) = â1980â Paraphrased-R4: What is the calculated monthly average of new schools in Alameda County during 1980 with a DOC value of 52? SELECT AVG(CASE WHEN STRFTIME(â%Yâ, OpenDate) = â1980â THEN 1 ELSE 0 END) / 12 AS monthly_average_new_schools FROM schools WHERE County = âAlamedaâ AND DOC = â52â Paraphrased-R5: What is the average number of schools opened each month in Alameda County in 1980 under Department of Education code 52 SELECT AVG(OpenDate) FROM schools WHERE County = âAlamedaâ AND DOC = â52â AND CAST(STRFTIME(â%Yâ, OpenDate) AS INTEGER) = 1980; Paraphrased-R6: What is the average number of schools opened per month in Alameda County in 1980 with a DOC value of 52? SELECT COUNT(DISTINCT School) FROM schools WHERE County = âAlamedaâ AND SUBSTR(OpenDate, 1, 4) = â1980â AND DOC = â52â Paraphrased-R7: How many schools, on average, opened each month in Alameda County in 1980 with the Department of Education code set to 52? SELECT AVG(TotalSchools) FROM ( SELECT STRFTIME(â%Y-%mâ, OpenDate) AS Month, COUNT(CDSCode) AS TotalSchools FROM schools WHERE County = âAlamedaâ AND DOC = â52â AND OpenDate BETWEEN â1980-01-01â AND â1980-12-31â GROUP BY STRFTIME(â%Y-%mâ, OpenDate) ); Paraphrased-R8: How many schools were opened in Alameda County under the Department of Educa- tion code 52 during the year 1980, on average per month? SELECT COUNT(CDSCode) / 12.0 AS AverageSchoolsPerMonth FROM schools WHERE DOC = â52â AND STRFTIME(â%Yâ, OpenDate) = â1980â Paraphrased-R9: Over the course of 1980, how many schools were opened in Alameda County un- der DOC 52, calculated as a monthly average? SELECT COUNT(CDSCode) / 12 FROM schools WHERE DOC = â52â AND County = âAlamedaâ AND OpenDate LIKE â1980%â Paraphrased-R10: On a monthly basis, how many schools were opened in the year 1980 in Alameda County under Department code 52? SELECT COUNT(DISTINCT School) FROM schools WHERE StatusType = âActiveâ AND County = âAlamedaâ AND OpenDate LIKE â1980-%â AND DOCType = â52â Table 5: Samples of original and paraphrased queries and the corresponding SQL queries, for a sample from Spider dataset. Similar to Bird dataset, there is sign of schema linkage issue in the paraphrased queries, and due to semantic edits the LLM cannot generate a correct SQL query. querySQL Original: What are all distinct countries where singers above age 20 are from? SELECT DISTINCT Country FROM singer WHERE Age >20 Paraphrased-R3: What are the unique countries of singers who are older than 20? SELECT Country FROM singer WHERE Age > 20 Paraphrased-R4: Can you list the different coun- tries represented by singers with an age greater than 20? SELECT Country FROM singer WHERE Age > 20 Paraphrased-R8: From how many unique countries do singers with an age greater than 20 hail? SELECT COUNT(DISTINCT Country) FROM singer WHERE Age > 20 Paraphrased-R9: Which unique countries are asso- ciated with singers aged over 20? SELECT Country FROM singer WHERE Age > 20 Listing 1: SQL schema for the example of Bird dataset. CREATE TABLE schools ( "CDSCode" TEXT NOT NULL, "NCESDist" TEXT, "NCESSchool" TEXT, "StatusType" TEXT NOT NULL, "County" TEXT NOT NULL, "District" TEXT NOT NULL, "School" TEXT, "Street" TEXT, "StreetAbr" TEXT, "City" TEXT, "Zip" TEXT, "State" TEXT, "MailStreet" TEXT, "MailStrAbr" TEXT, "MailCity" TEXT, "MailZip" TEXT, "MailState" TEXT, "Phone" TEXT, "Ext" TEXT, "Website" TEXT, "OpenDate" DATE, "ClosedDate" DATE, "Charter" INTEGER, "CharterNum" TEXT, "FundingType" TEXT, "DOC" TEXT NOT NULL, "DOCType" TEXT NOT NULL, "SOC" TEXT, "SOCType" TEXT, "EdOpsCode" TEXT, "EdOpsName" TEXT, "EILCode" TEXT, "EILName" TEXT, "GSoffered" TEXT, "GSserved" TEXT, "Virtual" TEXT, "Magnet" INTEGER, "Latitude" REAL, "Longitude" REAL, "AdmFName1" TEXT, "AdmLName1" TEXT, "AdmEmail1" TEXT, "AdmFName2" TEXT, "AdmLName2" TEXT, "AdmEmail2" TEXT, "AdmFName3" TEXT, "AdmLName3" TEXT, "AdmEmail3" TEXT, "LastUpdate" DATE NOT NULL, PRIMARY KEY ("CDSCode") ) /* 3 rows from schools table: CDSCode NCESDist NCESSchool StatusType County District School Street StreetAbr City Zip State MailStreet MailStrAbr MailCity MailZip MailState Phone Ext Website OpenDate ClosedDate Charter CharterNum FundingType DOC DOCType SOC SOCType EdOpsCode EdOpsName EILCode EILName GSoffered GSserved Virtual Magnet Latitude Longitude AdmFName1 AdmLName1 AdmEmail1 AdmFName2 AdmLName2 AdmEmail2 AdmFName3 AdmLName3 AdmEmail3 LastUpdate 01100170000000 0691051 None Active Alameda Alameda County Office of Education None 313 West Winton Avenue 313 West Winton Ave. Hayward 94544-1136 CA 313 West Winton Avenue 313 West Winton Ave. Hayward 94544-1136 CA (510) 887-0152 None w.acoe.org None None None None None 00 County Office of Education (COE) None None None None None None None None None None 37.658212 -122.09713 L Karen Monroe lkmonroe@acoe.org None None None None None None 2015-06-23 01100170109835 0691051 10546 Closed Alameda Alameda County Office of Education FAME Public Charter 39899 Balentine Drive, Suite 335 39899 Balentine Dr., Ste. 335 Newark 94560-5359 CA 39899 Balentine Drive, Suite 335 39899 Balentine Dr., Ste. 335 Newark 94560-5359 CA None None None 2005-08-29 2015-07-31 1 0728 Directly funded 00 County Office of Education (COE) 65 K-12 Schools (Public) TRAD Traditional ELEMHIGH Elementary-High Combination K-12 K-12 P 0 37.521436 -121.99391 None None None None None None None None None 2015-09-01 01100170112607 0691051 10947 Active Alameda Alameda County Office of Education Envision Academy for Arts \& Technology 1515 Webster Street 1515 Webster St. Oakland 94612-3355 CA 1515 Webster Street 1515 Webster St. Oakland 94612 CA (510) 596-8901 None w.envisionacademy.org/ 2006-08-28 None 1 0811 Directly funded 00 County Office of Education (COE) 66 High Schools (Public) TRAD Traditional HS High School 9-12 9-12 N 0 37.80452 -122.26815 Laura Robell laura@envisionacademy.org None None None None None None 2015-06-18 */ CREATE TABLE frpm ( "CDSCode" TEXT NOT NULL, "Academic Year" TEXT, "County Code" TEXT, "District Code" INTEGER, "School Code" TEXT, "County Name" TEXT, "District Name" TEXT, "School Name" TEXT, "District Type" TEXT, "School Type" TEXT, "Educational Option Type" TEXT, "NSLP Provision Status" TEXT, "Charter School (Y/N)" INTEGER, "Charter School Number" TEXT, "Charter Funding Type" TEXT, "IRC" INTEGER, "Low Grade" TEXT, "High Grade" TEXT, "Enrollment (K-12)" REAL, "Free Meal Count (K-12)" REAL, "Percent (%) Eligible Free (K-12)" REAL, "FRPM Count (K-12)" REAL, "Percent (%) Eligible FRPM (K-12)" REAL, "Enrollment (Ages 5-17)" REAL, "Free Meal Count (Ages 5-17)" REAL, "Percent (%) Eligible Free (Ages 5-17)" REAL, "FRPM Count (Ages 5-17)" REAL, "Percent (%) Eligible FRPM (Ages 5-17)" REAL, "2013-14 CALPADS Fall 1 Certification Status" INTEGER, PRIMARY KEY ("CDSCode"), FOREIGN KEY("CDSCode") REFERENCES schools ("CDSCode") ) /* 3 rows from frpm table: CDSCode Academic Year County Code District Code School Code County Name District Name School Name District Type School Type Educational Option Type NSLP Provision Status Charter School (Y/N) Charter School Number Charter Funding Type IRC Low Grade High Grade Enrollment (K-12) Free Meal Count (K-12) Percent (\%) Eligible Free (K-12) FRPM Count (K-12) Percent (\%) Eligible FRPM (K-12) Enrollment (Ages 5-17) Free Meal Count (Ages 5-17) Percent (\%) Eligible Free (Ages 5-17) FRPM Count (Ages 5-17) Percent (\%) Eligible FRPM (Ages 5-17) 2013-14 CALPADS Fall 1 Certification Status 01100170109835 2014-2015 01 10017 0109835 Alameda Alameda County Office of Education FAME Public Charter County Office of Education (COE) K-12 Schools (Public) Traditional None 1 0728 Directly funded 1 K 12 1087.0 565.0 0.519779208831647 715.0 0.657773689052438 1070.0 553.0 0.516822429906542 702.0 0.65607476635514 1 01100170112607 2014-2015 01 10017 0112607 Alameda Alameda County Office of Education Envision Academy for Arts \& Technology County Office of Education (COE) High Schools (Public) Traditional None 1 0811 Directly funded 1 9 12 395.0 186.0 0.470886075949367 186.0 0.470886075949367 376.0 182.0 0.484042553191489 182.0 0.484042553191489 1 01100170118489 2014-2015 01 10017 0118489 Alameda Alameda County Office of Education Aspire California College Preparatory Academy County Office of Education (COE) High Schools (Public) Traditional None 1 1049 Directly funded 1 9 12 244.0 134.0 0.549180327868853 175.0 0.717213114754098 230.0 128.0 0.556521739130435 168.0 0.730434782608696 1 */ CREATE TABLE satscores ( cds TEXT NOT NULL, \# California Department Schools rtype TEXT NOT NULL, sname TEXT, \# school name dname TEXT, \# district segment cname TEXT, \# county name enroll12 INTEGER NOT NULL, \# enrollment (1st-12nd grade) "NumTstTakr" INTEGER NOT NULL, "AvgScrRead" INTEGER, "AvgScrMath" INTEGER, "AvgScrWrite" INTEGER, "NumGE1500" INTEGER, PRIMARY KEY (cds), FOREIGN KEY(cds) REFERENCES schools ("CDSCode") ) /* 3 rows from satscores table: cds rtype sname dname cname enroll12 NumTstTakr AvgScrRead AvgScrMath AvgScrWrite NumGE1500 1100170000000 D None Alameda County Office of Education Alameda 398 88 418 418 417 14 1100170109835 S FAME Public Charter Alameda County Office of Education Alameda 62 17 503 546 505 9 1100170112607 S Envision Academy for Arts \& Technology Alameda County Office of Education Alameda 75 71 397 387 395 5 */ Listing 2: SQL schema for the example of Spider dataset. CREATE TABLE singer ( "Singer_ID" INTEGER, "Name" TEXT, "Country" TEXT, "Song_Name" TEXT, "Song_release_year" TEXT, "Age" INTEGER, "Is_male" BOOLEAN, PRIMARY KEY ("Singer_ID") ) /* 3 rows from singer table: Singer_ID Name Country Song_Name Song_release_year Age Is_male 1 Joe Sharp Netherlands You 1992 52 True 2 Timbaland United States Dangerous 2008 32 True 3 Justin Brown France Hey Oh 2013 29 True */ CREATE TABLE stadium ( "Stadium_ID" INTEGER, "Location" TEXT, "Name" TEXT, "Capacity" INTEGER, "Highest" INTEGER, "Lowest" INTEGER, "Average" INTEGER, PRIMARY KEY ("Stadium_ID") ) /* 3 rows from stadium table: Stadium_ID Location Name Capacity Highest Lowest Average 1 Raith Rovers Starkâs Park 10104 4812 1294 2106 2 Ayr United Somerset Park 11998 2363 1057 1477 3 East Fife Bayview Stadium 2000 1980 533 864 */ CREATE TABLE concert ( "concert_ID" INTEGER, "concert_Name" TEXT, "Theme" TEXT, "Stadium_ID" TEXT, "Year" TEXT, PRIMARY KEY ("concert_ID"), FOREIGN KEY("Stadium_ID") REFERENCES stadium ("Stadium_ID") ) /* 3 rows from concert table: concert_ID concert_Name Theme Stadium_ID Year 1 Auditions Free choice 1 2014 2 Super bootcamp Free choice 2 2 2014 3 Home Visits Bleeding Love 2 2015 */ CREATE TABLE singer_in_concert ( "concert_ID" INTEGER, "Singer_ID" TEXT, PRIMARY KEY ("concert_ID", "Singer_ID"), FOREIGN KEY("concert_ID") REFERENCES concert ("concert_ID"), FOREIGN KEY("Singer_ID") REFERENCES singer ("Singer_ID") ) /* 3 rows from singer_in_concert table: concert_ID Singer_ID 1 2 1 3 1 5 */