SchemaGraphSQL: Efficient Schema Linking with Pathfinding Graph Algorithms for Text-to-SQL on Large-Scale Databases

AmirHossein Safdarian; Ehsan Jahanbakhsh; Heshaam Faili; Milad Mohammadi; Mona Shahamat Naderi

REVIEW 4 major objections 5 minor 12 references

SchemaGraphSQL: Efficient Schema Linking with Pathfinding Graph Algorithms for Text-to-SQL on Large-Scale Databases

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper claims that a zero-shot, training-free linker—a single LLM call to name source and destination tables, then the union of all shortest foreign-key paths—outperforms specialized fine-tuned linkers on the BIRD benchmark.

desk verdict A simple, cheap schema linker that performs well on BIRD dev; the SOTA claim needs a held-out config selection and a test of the shortest-path coverage assumption. read the letter →

arxiv 2505.18363 v1 pith:WCKLDAN3 submitted 2025-05-23 cs.CL cs.AIcs.DB

AmirHossein Safdarian , Milad Mohammadi , Ehsan Jahanbakhsh , Mona Shahamat Naderi , Heshaam Faili This is my paper

classification cs.CLcs.AIcs.DB

keywords schemalinkingtext-to-SQLshortestpathsgraphzero-shotBIRDbenchmarkforeignkeyslargelanguagemodels

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper sets out to show that schema linking for text-to-SQL can be done well without any training or complex prompting. The proposed method, SchemaGraphSQL, turns the database schema into a graph whose edges are foreign keys, asks one lightweight LLM call to name source tables (from filtering conditions) and destination tables (from output columns), then unions all shortest paths between every source and destination pair. On the BIRD development split this union of shortest paths reaches 95.71% recall and 95.43% F6, ahead of specialized fine-tuned linkers, and it lifts end-to-end SQL execution accuracy by 6–12 points across four generators. With Gemini-2.5-Flash the best configuration lands at 62.91% total accuracy, within 1.5 points of an oracle that already knows the ideal linked schema. The point of caring: if this holds, a cheap, transparent, and interpretable linking module can replace heavier learned components.

What carries the argument

The load-bearing object is the schema graph $G = (T, K)$, an undirected graph whose nodes are database tables and whose edges are foreign-key relations, augmented for sparse schemas by edges joining tables that share a column with 'id' in its name. On this graph the pipeline is fixed: one LLM call produces source tables $T_s$ (tables whose columns appear in filters) and destination tables $T_d$ (tables supplying output columns); for every pair in $T_s \times T_d$ the algorithm enumerates all shortest simple paths, forming candidate set $C$; the union $U$ of all tables on any candidate path is the returned subschema in the force-union configuration. This single deterministic graph operation carries the argument, converting a fuzzy semantic selection problem into a combinatorial path-enumeration problem with search cost $\mathcal{O}(|E|)$ and guaranteeing that the filtered schema is connected and grounded in the query. The other configurations (longest path, no union, per-pair selection) exist mainly to ablate the recall-precision trade-off.

What would settle it

Run the published pipeline on the BIRD development split and compare each gold query's table set against the union of all shortest paths between the LLM-extracted source and destination tables: every gold query whose join path is not a shortest path between its named endpoints is a guaranteed recall miss, and the fraction of such queries settles whether the 95.71% recall claim can hold.

Watch

Extended reading notes

Core claim

The paper's central claim is that classical graph path-finding, not learned linking, is the right engine for schema selection in LLM text-to-SQL. Given a question, a single Gemini 2.5 Flash call outputs two coarse sets, sources and destinations; SchemaGraphSQL then enumerates all shortest simple paths in the foreign-key schema graph between each source and each destination, and the force-union configuration returns the union of those paths as the filtered subschema. This candidate set is connected by construction and grounded in the query. The authors report that this configuration achieves Recall = 95.71%, F6 = 95.43%, and Exact-Match Rate = 76.60% on BIRD dev, surpassing all published systems on recall-weighted metrics, and that with Gemini-2.5-Flash it reaches 62.91% execution accuracy, only 1.5% below the oracle ideal-schema-linking setting. The corollary they draw is that most remaining errors come from SQL generation rather than from missing tables: including extra tables through the union costs little while omitting one costs a lot.

Load-bearing premise

Every table in the gold SQL query must lie on at least one shortest path between a source table the LLM correctly names from the question's filter conditions and a destination table it correctly names from the requested output columns; if the gold query needs a non-shortest join or the LLM misses an endpoint, recall collapses.

Editorial extensions

If this is right

Unioning all shortest paths is the right operating point: removing the union (no-union) or forcing the longest path both hurt F1 and exact-match rate on BIRD dev.
Recall-weighted F6 predicts downstream execution accuracy better than precision or F1, since the highest-F6 configuration is always the highest-accuracy configuration across all four tested generators.
High-recall force-union beats high-precision 1–1 linking by 2–7% on dev and 4–12% on MiniDev, implying that LLM SQL generators tolerate extra tables better than missing joins.
The linking stage costs almost nothing: one Gemini Flash call averaging 4.6K input and 14 output tokens plus a shortest-path search under 15 ms, compatible with real-time and low-resource deployment.
Gains concentrate on challenging questions, with Gemini-2.5-Flash gaining 15 points on the Challenging subset, where multi-join queries need exactly the join chain the graph enumeration supplies.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The shortest-path-union idea generalizes beyond BIRD: any relational database with foreign-key metadata can be linked this way, and swapping the endpoint-extraction LLM for a cheaper classifier would preserve the deterministic core.
If the shortest-path assumption is the bottleneck, a natural extension is to weight edges by join cardinality or column-name similarity and take only the top-ranked paths, which could restore precision on dense, noisy foreign-key graphs without sacrificing recall.
The method could also compose with column-level linking: once the table path is fixed, selecting columns inside those tables is a much smaller problem, so prompts could shrink further for very wide tables.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know this paper: SchemaGraphSQL is a genuinely simple schema linker that gets high recall on BIRD dev by doing one LLM call to identify source/destination tables, then taking the union of all shortest paths between them in the foreign-key graph. It is cheap, training-free, and the within-paper ablations are coherent. The gains over their own single-step LLM baseline (6–12% execution accuracy across four generators) look credible, and the token cost is low (about 4.6K input tokens per query), which is a real practical advantage.

What is new is the specific recipe: prior graph-based systems like DBCopilot and Interactive-T2S use traversal only as an auxiliary tool, while here pathfinding is the whole linking engine. The paper is upfront about that distinction. The ablation showing that union beats no-union, and that longest-path hurts, supports their design choices.

The soft spots are real but manageable. The headline SOTA claim is weakened by configuration selection on the same BIRD dev split: the authors swept seven modes, picked the recall-optimal force-union, and reported that as primary. MiniDev is a subset of the same split, so it does not fix the selection issue. A held-out split or pre-registered config would be needed to make the SOTA claim stick. Related, they compare to published numbers from other systems without re-running them; that is common but worth flagging.

The deeper concern, raised by the stress test, is that the method's recall ceiling is set by the union-of-shortest-paths assumption: if a gold query needs a bridge table not on any shortest path between the LLM-identified endpoints, that table is invisible even with perfect endpoint extraction. The paper's own limitation section concedes dense/noisy FK graphs yield overly broad candidate sets but never quantifies how often BIRD queries violate this coverage condition. An oracle-endpoint recall test would separate LLM errors from path-coverage errors. That said, the end-to-end oracle gap is only 1.5% for Gemini, suggesting the practical impact of this ceiling is small—but it should be measured and reported.

There is also no code release yet, and no error bars. For a method whose main selling point is simplicity, releasing prompts and outputs would help trust.

Overall, this is a useful component paper for anyone building cheap text-to-SQL pipelines on large schemas. It deserves serious review, but with the understanding that the SOTA claim needs a held-out config and a coverage analysis. If the authors address those, I would be happy to see it in print.

My recommendation: send to peer review, with major revisions requested.

Referee Report

4 major / 5 minor

Summary. The paper proposes SchemaGraphSQL, a zero-shot, training-free schema-linking method for Text-to-SQL. A schema graph is built from foreign-key relations; a single Gemini 2.5 Flash call identifies source tables (filters) and destination tables (output columns); and classical shortest-path enumeration over all source-destination pairs produces a candidate table set, with several configurations (union, longest, no-union) ablated. The primary configuration, force-union, returns the union of all shortest paths. On the BIRD development split, the method achieves 95.71% recall and 95.43% F6 for schema linking, and improves execution accuracy over the paper's own baselines across four SQL generators, reaching 62.91% total accuracy with Gemini-2.5-Flash, claimed to be only 1.5% short of an 'ideal schema linking' oracle.

Significance. If validated, the paper would make a useful practical contribution: a simple, interpretable, low-cost schema linker that uses LLMs only for coarse endpoint extraction and otherwise relies on deterministic graph algorithms. The promised release of code, prompts, and outputs supports reproducibility, and the ablation across seven configurations and four generators is a genuine strength. The significance of the headline claims, however, depends on two points that are not currently established: that the primary configuration was not selected by peeking at the same dev split used for the final result, and that the union-of-shortest-paths assumption actually covers the gold tables for BIRD queries. Because these points are load-bearing for the state-of-the-art and oracle-gap claims, the contribution is not yet fully demonstrated.

major comments (4)

[§4.2, Table 2, §5.1] The primary configuration, SchemaGraphSQLforce-union, is chosen after sweeping seven configurations on the same BIRD development split that is then used to report the headline Recall=95.71% and F6=95.43% results. Selecting the best configuration on the evaluation split and then reporting that configuration's score on the same split makes the headline numbers optimistic and the 'surpassing all published systems' claim difficult to interpret. The authors should either evaluate on a held-out split (e.g., BIRD test set, if accessible without further configuration selection) or explicitly frame force-union as the result of a model-selection procedure and provide an unbiased estimate, for example by cross-validation on the dev split or by reporting all configurations with a clear statement that the best one was chosen on dev.
[§3.2, Step 2; Limitation section] The recall ceiling of the method is the union U of all shortest paths between the LLM-identified source and destination tables. If a gold query uses a bridge table that is neither a source nor a destination, or uses a semantically valid join path that is not a shortest path (because a shorter foreign-key edge exists but represents a different relationship), that table is excluded from U no matter how accurate the LLM endpoint extraction is. The paper never quantifies how often BIRD dev queries violate this coverage condition, and no oracle-endpoint experiment is reported. Consequently, the observed 4.29% recall gap cannot be attributed between LLM endpoint errors and structural limitations of the graph search. To support the claim that the linker is only 1.5% short of oracle-level schema coverage, the authors should run an oracle source/destination extraction experiment on BIRD dev and report the recall of the union-of-shortest-paths procedure under perfect endpoints, or provide a per-query analysis of the missing tables.
[Table 3] The term 'Ideal Schema Linking' is used to support the central claim that SchemaGraphSQLforce-union attains 62.91% total accuracy, only 1.5% short of the oracle setting. The manuscript does not define what this oracle setting is: whether it is the gold table set, the full schema, or some other construction. The gap claimed in the abstract and Section 5.3 is only meaningful if the oracle is a well-defined and fair upper bound, so the authors should define it precisely and state whether the same downstream generator, prompting template, and temperature are used in both settings.
[Table 1] The state-of-the-art claim in Section 5.1 compares SchemaGraphSQLforce-union against numbers from published systems (DIN-SQL, PET-SQL, MAC-SQL, MCS-SQL, RSL-SQL, LinkAlign, DTS-SQL, Gen, ExSL). The manuscript does not specify how these numbers were obtained, what underlying LLM or schema-linking prompt each system used, or whether the evaluation protocols are identical (e.g., same dev split, same gold-table extraction procedure). Because the headline contribution is a new SOTA on BIRD dev schema linking, this comparison needs to be controlled or at least carefully documented. At minimum, the authors should report the controlled baselines introduced in Section 4.2 alongside the published numbers and explicitly state any differences in evaluation conditions.

minor comments (5)

[§3.3] The configuration table is referred to as 'Table 3.3' but appears without a caption or number in the text; this should be fixed so that references match.
[Appendix B, Table 4] The row labeled 'SchemaGraphSQL (Ours)' in Table 4 appears to correspond to one specific configuration from Table 5 (the n-n configuration), but this is not stated. The authors should identify the configuration used in Table 4.
[§4.2] The formatting of 'DENSE RETRIEVER' and 'LINK ALIGN .' is inconsistent, and the latter appears to be a typo for 'LinkAlign'; these should be cleaned up.
[§5.4] The paper states that the shortest-path search is O(|E|), but the method enumerates all shortest simple paths between multiple source-destination pairs; the number of such paths can be exponential in the input size, so the complexity claim is inaccurate as stated.
[Notation, first paragraph] The heuristic that adds edges between tables sharing a column containing 'id' for sparse schemas is an unablated design choice that changes the graph structure and can affect path enumeration. A sentence reporting how often this heuristic is triggered on BIRD and whether results change without it would improve transparency.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the method is a deterministic graph computation over LLM-extracted endpoints, with no fitted parameters, no load-bearing self-citations, and no imported uniqueness results; the dev-mode configuration sweep is a selection concern, not a circular derivation.

full rationale

SchemaGraphSQL's reported claims do not reduce to their inputs by construction. The pipeline (Section 3.2) is: one Gemini call extracts source and destination tables; a deterministic shortest-path enumeration over the foreign-key schema graph produces candidate set C and union U; a configuration (Mode 7) returns U as the filtered schema. Recall, F6, and execution accuracy are then measured against BIRD gold queries using the official evaluation script. There is no fitted continuous parameter, no learned weight, and no equation in which a reported metric is definitionally equal to a prompt output or to a design choice. The '1.5% short of oracle' statement compares against an independently defined ideal-schema-linking upper bound; it is a benchmark, not a self-referential construction. The seven configurations in Table 3.3 are discrete ablations; choosing the recall-optimal force-union mode after seeing BIRD-dev results is a model-selection and multiple-comparisons concern, but it does not make the reported accuracy a forced consequence of the selection criterion. The paper contains no load-bearing self-citations, no imported uniqueness theorem, and no ansatz smuggled via citation. The acknowledged limitation that non-shortest join paths or noisy foreign-key graphs can break coverage (Limitation section) is an untested correctness assumption, not circularity; per the review rules, untested assumptions belong to correctness risk, not to the circularity score.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central claim rests on the schema graph being a faithful representation of joinability, the LLM being able to name all endpoint tables, and the assumption that all gold tables fall on some shortest path between an endpoint pair. None of these are demonstrated with held-out evidence, and the configuration choice, force-union mode, is made on the same split used for evaluation.

free parameters (1)

Selection configuration (Mode 7, force-union) = UNION=true, LONGEST=false, no path selection
The headline results use the force-union mode, chosen after ablating seven configurations on the same BIRD dev split (Tables 2 and 5). This is a post-hoc selection on the evaluation set rather than a held-out validation, so the headline numbers partly reflect tuning to the benchmark.

assumptions (5)

domain assumption Schema graph edges are determined by declared foreign keys, and these FK constraints are complete and accurate for the BIRD schemas.
Section 3 defines the schema graph as G=(T,K) with K the set of foreign-key relations; if BIRD schemas have missing or noisy FK metadata, path enumeration may miss valid joins or create invalid ones.
domain assumption The gold SQL query's referenced tables can be unambiguously extracted for evaluation.
Section 4.1 states that gold queries are used 'by extracting the referenced tables'; the extraction rule is not fully specified, and different extraction protocols may change the reported recall and precision.
domain assumption The single LLM call to Gemini 2.5 Flash reliably identifies all source and destination tables from the question and full schema.
Prompt 1 in Section 3.2 asks for source and destination tables; the method's recall depends directly on this extraction being complete and correct.
ad hoc to paper Every table needed for the answer lies on at least one shortest path between an identified source and destination table in the schema graph.
Step 3 in Section 3.2 returns the union of all shortest paths; the paper does not provide evidence that BIRD gold schemas always form shortest paths, and its own limitations note that dense graphs yield overly broad sets.
ad hoc to paper Tables sharing a column whose name contains 'id' are joinable and can be added as edges for sparse schemas.
Section 3 states that for schemas with fewer than two edges, edges are added between tables sharing an 'id'-containing column; this heuristic can create spurious shortest paths and is not validated against join semantics.

how reviews work

0 comments

Cite this review

Pith. "Pith review of SchemaGraphSQL: Efficient Schema Linking with Pathfinding Graph Algorithms for Text-to-SQL on Large-Scale Databases." pith.science (2026). https://pith.science/paper/WCKLDAN3

@misc{pith2026250518363,
  author       = {Pith},
  title        = {Pith review of: SchemaGraphSQL: Efficient Schema Linking with Pathfinding Graph Algorithms for Text-to-SQL on Large-Scale Databases},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WCKLDAN3}},
  note         = {Machine review of arXiv:2505.18363}
}

read the original abstract

Text-to-SQL systems translate natural language questions into executable SQL queries, and recent progress with large language models (LLMs) has driven substantial improvements in this task. Schema linking remains a critical component in Text-to-SQL systems, reducing prompt size for models with narrow context windows and sharpening model focus even when the entire schema fits. We present a zero-shot, training-free schema linking approach that first constructs a schema graph based on foreign key relations, then uses a single prompt to Gemini 2.5 Flash to extract source and destination tables from the user query, followed by applying classical path-finding algorithms and post-processing to identify the optimal sequence of tables and columns that should be joined, enabling the LLM to generate more accurate SQL queries. Despite being simple, cost-effective, and highly scalable, our method achieves state-of-the-art results on the BIRD benchmark, outperforming previous specialized, fine-tuned, and complex multi-step LLM-based approaches. We conduct detailed ablation studies to examine the precision-recall trade-off in our framework. Additionally, we evaluate the execution accuracy of our schema filtering method compared to other approaches across various model sizes.

Figures

Figures reproduced from arXiv: 2505.18363 by the authors.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

12 extracted references · 9 canonical work pages

[1]

Briefly justify your decision internally but do not in- clude any reasoning in the final output

Internally inspect each path to determine: • whether it connects all necessary tables, • whether joins are complete and valid, • and whether it satisfies the intent of the question. Briefly justify your decision internally but do not in- clude any reasoning in the final output

work page
[2]

Your task is to generate a valid query to answer a user question based on the given schema and join path

Output one line in the following format:Final Answer: path_id: <ID> Prompt 3: System prompt for SQLite query generation after schema linking ROLE & OBJECTIVE You are an expert in SQLite query generation. Your task is to generate a valid query to answer a user question based on the given schema and join path. INPUTS • Schema: {schema} • Join Path: {join_pa...

work page
[3]

Preprint, arXiv:2312.03463

Dbcopilot: Natural language querying over massive databases via schema routing. Preprint, arXiv:2312.03463. Yihan Wang and Peiyu Liu. 2025. Linkalign: Scal- able schema linking for real-world large-scale multi- database text-to-sql. Preprint, arXiv:2503.18596. Guanming Xiong, Junwei Bao, Hongfei Jiang, Yang Song, and Wen Zhao. 2024. Interactive-t2s: Multi...

arXiv 2025
[4]

Preprint, arXiv:2410.06011

Large language model enhanced text-to-sql generation: A survey. Preprint, arXiv:2410.06011. A Prompts This section includes all system prompts used throughout the SchemaGraphSQL pipeline. These prompts are designed to be modular and reusable across different configurations and model sizes. • Prompt 2: Selection of the most appropriate join path among cand...

arXiv
[7]

Use the provided schema and join path to construct a valid SQLite query

work page
[8]

Ensure the query correctly answers the user’s question

work page
[9]

Prompt 4: Baseline prompt for SQLite query generation ROLE & OBJECTIVE You are an expert in SQLite query generation

Format the query clearly and confirm it adheres to SQLite syntax. Prompt 4: Baseline prompt for SQLite query generation ROLE & OBJECTIVE You are an expert in SQLite query generation. Your task is to produce a valid query that answers a user’s question using the provided schema. INPUTS • Schema: {schema} • Question Context: {evidence_string} INSTRUCTIONS

work page
[10]

Generate a correct SQLite query that answers the user question

work page

Show all 12 references

[11]

Ensure the query is syntactically valid and aligns with the schema
[12]

B Additional Results This section presents extended evaluation results that complement those in the main text

Format the query clearly and cleanly. B Additional Results This section presents extended evaluation results that complement those in the main text. We report schema linking scores and execution accuracy on the MINI DEV split of the BIRD dataset to validate robustness and gene...
[2024]

Preprint, arXiv:2412.12522

Solid-sql: Enhanced schema-linking based in-context learning for robust text-to-sql. Preprint, arXiv:2412.12522. Geling Liu, Yunzhi Tan, Ruichao Zhong, Yuanzhen Xie, Lingchen Zhao, Qian Wang, Bo Hu, and Zang Li

arXiv
[2025]

In Pro- ceedings of the 31st International Conference on Computational Linguistics, pages 9793–9803, Abu Dhabi, UAE

Solid-SQL: Enhanced schema-linking based in-context learning for robust text-to-SQL. In Pro- ceedings of the 31st International Conference on Computational Linguistics, pages 9793–9803, Abu Dhabi, UAE. Association for Computational Linguis- tics. Mohammadreza Pourreza and Davo...

2024 arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Briefly justify your decision internally but do not in- clude any reasoning in the final output

Internally inspect each path to determine: • whether it connects all necessary tables, • whether joins are complete and valid, • and whether it satisfies the intent of the question. Briefly justify your decision internally but do not in- clude any reasoning in the final output

work page

[2] [2]

Your task is to generate a valid query to answer a user question based on the given schema and join path

Output one line in the following format:Final Answer: path_id: <ID> Prompt 3: System prompt for SQLite query generation after schema linking ROLE & OBJECTIVE You are an expert in SQLite query generation. Your task is to generate a valid query to answer a user question based on the given schema and join path. INPUTS • Schema: {schema} • Join Path: {join_pa...

work page

[3] [3]

Preprint, arXiv:2312.03463

Dbcopilot: Natural language querying over massive databases via schema routing. Preprint, arXiv:2312.03463. Yihan Wang and Peiyu Liu. 2025. Linkalign: Scal- able schema linking for real-world large-scale multi- database text-to-sql. Preprint, arXiv:2503.18596. Guanming Xiong, Junwei Bao, Hongfei Jiang, Yang Song, and Wen Zhao. 2024. Interactive-t2s: Multi...

arXiv 2025

[4] [4]

Preprint, arXiv:2410.06011

Large language model enhanced text-to-sql generation: A survey. Preprint, arXiv:2410.06011. A Prompts This section includes all system prompts used throughout the SchemaGraphSQL pipeline. These prompts are designed to be modular and reusable across different configurations and model sizes. • Prompt 2: Selection of the most appropriate join path among cand...

arXiv

[5] [7]

Use the provided schema and join path to construct a valid SQLite query

work page

[6] [8]

Ensure the query correctly answers the user’s question

work page

[7] [9]

Prompt 4: Baseline prompt for SQLite query generation ROLE & OBJECTIVE You are an expert in SQLite query generation

Format the query clearly and confirm it adheres to SQLite syntax. Prompt 4: Baseline prompt for SQLite query generation ROLE & OBJECTIVE You are an expert in SQLite query generation. Your task is to produce a valid query that answers a user’s question using the provided schema. INPUTS • Schema: {schema} • Question Context: {evidence_string} INSTRUCTIONS

work page

[8] [10]

Generate a correct SQLite query that answers the user question

work page