JoinGR: Learning to Traverse Join Graphs for Table Retrieval

J OIN GR: Learning to Traverse Join Graphs for Table Retrieval Sandipan De1

Abhijit Chakraborty1 Sambaran Bandyopadhyay2 Arizona State University1 Adobe Research, India2

Vivek Gupta1

sandipan@asu.edu, achakr40@asu.edu, samb.bandyo@gmail.com, vgupt140@asu.edu

Abstract

query may be impossible to generate. Table retrieval therefore narrows the schema before downstream schema linking and generation. The dominant approach is dense retrieval. A question and schema elements are embedded into a shared vector space, and tables are ranked by semantic similarity to the question. This works well when schemas are compact, table and column names are descriptive, and when questions refer directly to the required tables. However, independent retrieval struggles when queries require multi-hop joins, or when table names are abbreviated, overlapping, or meaningful only in relation to other tables. A bag-of-columns retriever has no mechanism for expressing that a table becomes relevant only after another table has been selected. We argue that this structural blindness, rather than embedding quality, is a key constraint. To make schema relationships first-class, we posit Join Graph: a graph representation in which columns are nodes and intra-table and foreign-key relationships are typed edges. Structure alone is insufficient as it specifies table connections but not their relevance to specific questions. Different questions from the same anchor table may need different join edges. J OIN GR combines semantic matching to select anchor tables and a query-conditioned scorer to determine relevance in the join graph. The scorer assigns weights to join edges, directing relevance flow along promising paths. Final table scores aggregate deposits from these query-specific walks. Figure 1 details the three-stage flow. We evaluate J OIN GR on Spider (Yu et al., 2018), BIRD (Li et al., 2023), and BEAVER (Chen et al., 2024a), spanning various retrieval difficulties. Spider offers a standard cross-domain setting where schemas are compact, and dense retrieval is strong. BIRD features larger databases, but many queries need only a few tables. BEAVER is a challenging enterprise benchmark with cryptic table names and

arXiv:2610.01064v1 [cs.CL] 1 Oct 2026

Retrieving the right tables is a prerequisite for Text-to-SQL over realistic databases. Dense table retrievers rank schema elements independently, but this ignores a key source of evidence: some required tables are not mentioned in the question and become identifiable only through their join relationships to already relevant tables. We introduce J OIN GR, a join-aware table retrieval method that treats the database join graph as the retrieval space. Columns are represented as graph nodes, while intra-table and foreign-key relationships are represented as typed edges. Given a question, J OIN GR selects semantically similar anchor tables, traverses join edges with a query-conditioned scorer, and aggregates the resulting edge deposits into table scores. The scorer is a lightweight MLP on top of frozen query, node, and edge embeddings, trained with a pairwise margin loss over gold tables. On BIRD and Spider datasets, J OIN GR is competitive with the strongest retrieval baselines. On BEAVER, a challenging enterprise benchmark with multi-hop table requirements, J OIN GR substantially improves recall over dense retrieval and re-ranking baselines. Cross-domain experiments show that the learned scorer transfers across benchmarks, indicating that the method captures reusable joingraph traversal behavior.

1

Introduction

Modern text-to-SQL systems increasingly rely on large language models to perform semantic parsing (Li et al., 2023; Pourreza and Rafiei, 2023). However, their success still depends on an upstream retrieval step: the model must have access to the schemas of the relevant table(s). In realistic databases, the full schema is often too large to place in context, and irrelevant schema elements can induce spurious joins or hallucinated SQL (Maamari et al., 2024). Conversely, if even one required table is missing from the retrieved context, the correct 1

Q: What is the current building key, building street address, cit y, state, and postal code of the history department? Gold: [' FCLT_BUILDING_ADDRESS', ' FCLT_ROOMS', ' FCLT_ORG_DLC_KEY', ' MASTER_DEPT_HIERARCHY', ' BUILDINGS' ]

(1) Semantic Anchor Retrieval

(2) Join Graph Traversal (Multi- hop Walk f rom Each Anchor)

Top Semantic Matches

(3) Aggregated Deposit to Tables FCL_ROOMS

Reranked Tables (Based on Deposit Scores)

FCLT_BUILDING_ADDRESS 1 FCLT_BUILDING_ADDRESS_HIST

FCLT_BUILDING_ADDRESS_HIST

FCLT_ROOMS

1 FCLT_BUILDING_ADDRESS*

2 FCLT_BUILDING_ADDRESS*

2 BUILDINGS*

3 FAC_BUILDING_ADDRESS

3 FCLT_ROOMS

4 FCLT_BUILDING_HIST

4 FCLT_ORG_DLC_KEY SPACE_USAGE

5 BUILDINGS*

5 MASTER_DEPT_HIERARCHY

FAC_BUILDING_ADDRESS FCLT_ORG_DLC_KEY -

Gold + Anchor

6 .. 7 ..

Gold Table Anchor Table Other Table

FCLT_BUILDING_HIST

MASTER_DEPT_HIERARCHY

BUILDINGS

Figure 1: Overview of J OIN GR table retrieval for the example question. (1) Semantic retrieval selects the top-5 anchor tables based on dense similarity between the query and table/column representations. (2) Starting from these anchors, J OIN GR performs query-conditioned multi-hop traversal over the join graph; edge thickness indicates traversal probability and node size reflects aggregated deposit received during propagation. Gold tables are highlighted in orange. (3) Deposits accumulated from all traversal paths are aggregated to produce final table scores.

multi-hop table needs. This range lets us determine when structure-aware retrieval is needed: J OIN GR should be competitive when semantic retrieval suffices and improve recall when relational structure is crucial. Our results support this view. On Spider and BIRD, J OIN GR is competitive with strong retrieval baselines in regimes where dense embedding similarity already performs well. On BEAVER, where independent retrieval and re-ranking methods struggle, J OIN GR substantially improves recall and perfect recall. Moreover, scorers trained on one benchmark transfer to another without retraining, suggesting that the model learns to traverses join graphs rather than memorizing dataset-specific table names. Our contributions are:

(DW), showing that J OIN GR is competitive when dense retrieval is strong and substantially improves recall and perfect recall on multi-hop enterprise schemas. • We show that the learned scorer transfers across benchmarks, supporting its use as a reusable traversal policy for new schemas with limited supervision.

2

Problem Formulation

Let D = {D1 , . . . , Dn } denote a dataset of relational databases. For a database D ∈ D, let T (D) = {t S1 , . . . , tm } denote its set of tables and C(D) = i C(ti ) denote the set of all columns across those tables. A natural-language question q associated with database D has a gold set T g (q) ⊆ T (D) of tables required to construct the correct SQL query, and (when annotated) a gold set Kg (q) of join-key pairs (c, c′ ), where c ∈ C(ti ) and c′ ∈ C(tj ) for i ̸= j. The table retrieval task requires: given q, produce a ranked list of tables that contains all of T g (q) at as small a rank as possible. The above formulation treats table retrieval as a ranking problem. However, ranking tables independently ignores the fact that some tables necessary to answer a query may not be immediately obvious

• We formulate table retrieval as query conditioned traversal over a database join graph, enabling retrieval of tables that are structurally implied rather than directly mentioned. • We propose J OIN GR, an anchor-walkaggregate method that combines semantic retrieval with learned propagation over join relationships. • We evaluate on Spider, BIRD, and BEAVER 2

from the query utterance; instead, they may become relevant only through their structural relationship to already identified tables. We therefore utilize the database relational structure as the retrieval space for J OIN GR.

Table 2

node21 (k)

Table 1

node11 (k)

node12 (k) node22

3

J OIN GR node13

J OIN GR retrieves tables by first constructing a structured search space from the schema and then performing learned traversal over that space. We describe the join-graph representation, followed by the anchor–walk–aggregate retrieval procedure and training objective. 3.1

node14

node15

Intra- Edge Join- Edge

Figure 2: Example of the join graph constructed from a relational schema. Circular nodes denote key columns, rectangular nodes denote non-key columns, solid edges represent intra-table connectivity, and dashed edges represent inter-table join relationships.

Join Graph Construction

We construct a single undirected graph GD = (V, E) over all databases in the dataset. Each column c ∈ C(D) for some D ∈ D is represented as a node vc ∈ V with a node descriptor dv containing (i) the canonical name (db.table.column), (ii) a short LLM-generated semantic name and purpose, (iii) the data type, and (iv) a key flag is_key indicating whether c is either a primary or foreign key of the table. The relationship between two columns is represented as an edge e = (vc , vc′ ) ∈ E with an edge descriptor de containing (i) the endpoint node identifiers and names, (ii) the edge type, and (iii) a short LLM-generated edge purpose describing why the two columns are related. Edges are typed as either intra or join. An intra edge connects columns belonging to the same table, specifically between a key column and a non-key column or between two key columns. A join edge connects key columns from different tables that participate in a foreign-key relationship. Figure 2 illustrates the resulting connectivity patterns induced by intra and join edges. 3.2

node23

3.2.1 Encoding J OIN GR operates in a shared embedding space for queries, nodes, and edges. Let φ(·) be a frozen encoder. For query q, we compute q = φ(q) ∈ Rd . Offline, for each node v with descriptor dv , we compute v = φ(dv ) ∈ Rd . Similarly, for each edge e with descriptor de , we compute e = φ(de ) ∈ Rd . All vectors are ℓ2 -normalized so that dot products correspond to cosine similarities. 3.2.2 Anchor Selection The walk begins from tables that are semantically close to the query. We first retrieve the nearest nodes from the query embedding and map each retrieved node to its parent table. Each candidate table is assigned a semantic table score s(t | q) = max ⟨q, v⟩. v∈V (t)

We use s(t | q) to rank candidate tables and initialize anchor deposits.1 For later use in the graph walk, we also define the query-dependent table representation

Anchor → Walk → Aggregate

rt = vt∗ ,

While the join graph defines the space for possible connections, a query usually requires only a small part of the structure. J OIN GR retrieves this query-specific subgraph through a three stage process. First, it selects a small set of semantically relevant anchor tables using similarity between query and node embeddings. Second, it walks from these anchors along the join edges using a queryconditioned scorer to decide which paths are most relevant, and third, it aggregates the evidence accumulated on the traversed edges into final table scores.

vt∗ = arg max ⟨q, v⟩, v∈V (t)

where vt∗ is the embedding of the best-matching node vt∗ in table t. The top-scoring tables are selected as anchors for graph traversal. 3.2.3 Learned Graph Walk From each anchor table, J OIN GR performs a bounded breadth-first walk of depth H over join edges. The walk maintains a non-negative deposit 1

Max similarity avoids diluting a highly indicative column among many unrelated columns in wide tables.

3

been expanded in the current anchor walk, ∆e is added to its deposit for the next hop. We maintain a visited set for each anchor walk to prevent cycles.

t1 zf f

e : ue → πe ∆e = zf αh πe

3.2.4 Aggregation The graph walk produces edge-level evidence, but the retrieval output is a ranked list of tables. We therefore project accumulated edge deposits back onto their endpoint tables. Let ∆e (q) denote the total deposit accumulated on edge e across all anchors and hops. The final table score is X ŝ(t | q) = ∆e (q).

t2

t3 Figure 3: Expansion in Join Graph. From frontier table f , J OIN GR scores outgoing join edges to neighbor t1 , t2 and t3 , locally normalizes the scores, and propagates deposit.

e: t∈endpoints(e)

Tables are ranked in descending order of ŝ(t | q). 3.2.5 Training We train the edge scorer using supervised table sets. Let P = T g (q) be the gold table set and N = T (D) \ P the negatives. The table-level loss is X
1 Ltab = max 0, m − ŝ(p) + ŝ(n) , |P ||N |

at each frontier table, representing the amount of relevance that has reached that table. At each hop, the model distributes this deposit across the outgoing join edges according to query-conditioned transition scores. Let f denote the frontier table at hop h, with incoming deposit zf . For each outgoing join edge e = (f, t′ ), where t′ is the neighboring table, we form the feature vector

p∈P n∈N

with margin m. When gold join keys Kg (q) are available, we also consider an edge-level variant that applies the same pairwise margin objective to deposits on gold and non-gold join edges. The main experiments use the table-level loss, since gold table sets are available in standard text-to-SQL benchmarks.

xe = [ q ; e ; rf ; rt′ ; zf ; h ], where q is the query embedding, e is the edge embedding, rf and rt′ are the query-dependent table representations of the frontier and neighbor tables, respectively, zf is the incoming deposit, and h is the hop index. A query-conditioned scorer sθ assigns a relevance score to each outgoing edge:

4

Experimental Setup

Datasets. We evaluate J OIN GR on three text-toSQL benchmarks that offers varying degrees of table-retrieval complexity: Spider (Yu et al., 2018), BIRD (Li et al., 2023) and BEAVER (Chen et al., 2024a). Table 1 summarizes dataset and join-graph statistics for each split. Figure 4 shows the distribution of the number of gold tables required per query.

ue = sθ (xe ) ∈ R. For each frontier table f , the raw scores of its outgoing join edges Njoin (f ) are locally normalized with a softmax: exp(ue ) . e′ ∈Njoin (f ) exp(ue′ )

πe = P

Encoders and baselines. We use two frozen sentence embedders (Reimers and Gurevych, 2019), all-MiniLM-L6-v2 (Wang et al., 2020b) and BGElarge-en-v1.5 (Xiao et al., 2024) to embed queries, nodes, and edges. Our first baseline is the corresponding Vanilla Retriever, which ranks each table by the maximum similarity between the query and any column in the table. This baseline isolates semantic retrieval without graph expansion.

The deposit propagated onto edge e is ∆e = zf · αh · πe , where αh = σ(α̃h ) is a learned hop-specific decay coefficient. Figure 3 summarizes this local expansion step. Edge deposits accumulate across all anchors and hops. If the neighboring table t′ has not already 4

Dataset

Split #DB #Tab.

Spider Dev 20 Spider Train 166 BIRD Dev 11 BIRD Train 69 BEAVER DW 1

#Q

feature vector described in Section 3.2.3 to an unnormalized edge score. We use hidden dimension 64, dropout 0.3, Adam with learning rate 10−3 and weight decay 10−4 , gradient clipping at 1.0, and ReduceLROnPlateau scheduling. We set maximum walk depth H = 5. The sentence encoder and all graph embeddings are frozen; only the edge scorer and hop-specific decay parameters are trained. Spider and BIRD use the standard train/dev split. Because BEAVER (DW) has only 121 queries, we report 5-fold cross-validation. Cross-domain experiments train on one benchmark and evaluate on another without target-domain supervision.

#N #Intra #Join

81 1034 441 876 7000 4503 75 1534 798 522 9428 3539 97 121 1530

492 4704 3345 4559 3536

63 793 102 418 197

Table 1: Dataset and join-graph statistics. #N denotes column nodes; intra edges connect columns within a table, and join edges connect foreign-key-related columns across tables. 1 table 4 tables

2 tables 5+ tables

3 tables

Fraction of queries

1

Metrics. We report precision (P@K), recall (R@K), and perfect recall (PR@K) at K ∈ {5, 15}. PR@K is the strictest metric: it equals 1 iff every gold table is present within the first K elements, and is the metric most directly tied to downstream SQL accuracy.

0.8 0.6 0.4 0.2 0 Spider Dev

Spider Train

BIRD Dev

BIRD BEAVER Train DW

Figure 4: Distribution of queries by number of required gold tables.

5

Results

5.1

Results on BEAVER (DW)

Table 2 reports results on BEAVER (DW), the most structurally challenging benchmark in our evaluation. Across both encoders, J OIN GR achieves the strongest overall retrieval performance. With BGElarge-en-v1.5, J OIN GR improves R@15 from 0.697 for the vanilla retriever to 0.875, and PR@15 from 0.339 to 0.645. With MiniLM, the gains are similarly large, improving R@15 from 0.667 to 0.873 and PR@15 from 0.273 to 0.653. The gains are especially visible with the lightweight MiniLM encoder, where semantic retrieval is weaker. For example, J OIN GR improves R@5 from 0.385 to 0.528 and PR@5 from 0.066 to 0.182 over the vanilla retriever. This suggests that structural traversal can compensate when embedding quality alone is insufficient, reducing the dependence on stronger semantic encoders. Because BEAVER (DW) contains only 121 annotated queries, we report the in-domain trained model using 5-fold cross-validation. This limited evaluation size leads to noticeable fold-to-fold variance, so we interpret the in-domain numbers as evidence of the method’s potential under supervision. The cross-domain setting provides an important complementary evaluation. A scorer trained on BIRD and evaluated on BEAVER (DW) still achieves R@15 of 0.806 with BGE and 0.740 with MiniLM, matching other retrieval and re-ranking

We compare against recent multi-table retrieval baselines. REaR (Agarwal et al., 2025) is a retrieveand-rerank pipeline that refines initially retrieved candidates using relation-aware signals. JAR (Chen et al., 2024b) is a join-aware re-ranking method that combines query-table relevance with tabletable joinability and solves table selection as a mixed-integer optimization problem. IterativeJAR (Boutaleb et al., 2025) replaces JAR’s global optimization step with a greedy iterative search procedure for better scalability. We report the available DTR- and Contriever-based variants of these methods where applicable. Finally, we include a heuristic J OIN GR variant that uses the same query-conditioned anchor–walk– aggregate pipeline but replaces the learned edge scorer with fixed propagation weights. Comparing dense retrieval, heuristic J OIN GR, and trained J OIN GR isolates the contributions of semantic matching, graph expansion with fixed weights, and learned edge weighting. Scorer implementation and training. The J O IN GR scorer is a one-hidden-layer MLP with LayerNorm, ReLU, and dropout, mapping the edge 5

baselines. This suggests that the scorer learns a reusable scoring mechanism over join graphs. The comparison between the vanilla retriever, heuristic J OIN GR, and trained J OIN GR further isolates the contributions of semantic similarity, graph expansion, and learned edge scoring. The heuristic variant improves R@15 over the vanilla retriever for both encoders, indicating that join-graph expansion alone recovers additional relevant tables. However, trained J OIN GR substantially improves perfect recall over the heuristic variant, increasing PR@15 from 0.405 to 0.645 with BGE and from 0.430 to 0.653 with MiniLM. This indicates that learning how to distribute deposit is important for recovering complete multi-hop table sets.

the lightweight MiniLM encoder. Compared with the MiniLM vanilla retriever, J OIN GR improves R@5 from 0.886 to 0.909 and PR@15 from 0.936 to 0.951. This mirrors the trend observed on BEAVER: when the semantic retriever is weaker, query-conditioned join traversal provides a useful corrective signal. Alignment-based re-rankers are also strong on BIRD: REaR performs query-aware cross-encoder reranking in its refine stage, while JAR and IterativeJAR incorporate fine-grained query–schema alignment and coverage-based selection. These signals are well suited to BIRD, where many required tables are directly reflected in the utterance. Method

Method

P @5

R @15

@5

PR @15

@5

@15

0.352 0.347 0.319 0.423 0.384

Vanilla Retriever REaR J OIN GRH J OIN GR J OIN GRX→Y

0.279 0.247 0.311 0.395 0.314

0.175 0.179 0.195 0.226 0.206

0.476 0.474 0.423 0.553 0.514

0.697 0.684 0.759 0.875 0.806

0.124 0.174 0.058 0.157 0.149

0.339 0.364 0.405 0.645 0.529

0.667 0.445 0.779 0.873 0.740

0.066 0.116 0.074 0.182 0.107

0.273 0.215 0.430 0.653 0.397

Vanilla Retriever REaR J OIN GRH J OIN GR J OIN GRX→Y

0.385 0.340 0.414 0.528 0.429

0.323 0.353 0.113 0.303 0.379

0.176 0.176 – – 0.180

0.431 0.468 0.155 0.392 0.515

0.693 0.695 – – 0.719

0.150 0.142 0.067 0.125 0.198

0.375 0.392 – – 0.397

@5

@15

0.349 0.359 0.300 0.360 0.346

0.127 0.198 0.123 0.188 0.126

0.918 0.937 0.789 0.934 0.901

0.983 0.985 0.951 0.973 0.973

0.830 0.871 0.650 0.877 0.818

0.964 0.970 0.921 0.961 0.962

Vanilla Retriever REaR J OIN GRH J OIN GR J OIN GRX→Y

0.335 0.354 0.325 0.347 0.338

DTR Contriever JARF (DTR) JARF (Contriever) JARIterative

0.376 0.366 0.402 0.403 0.355

0.125 0.189 0.122 0.125 0.125

0.886 0.923 0.858 0.909 0.883

0.970 0.969 0.945 0.966 0.966

0.775 0.846 0.762 0.839 0.787

0.936 0.942 0.917 0.951 0.951

0.144 0.145 – – 0.127

0.851 0.825 0.897 0.898 0.930

0.970 0.974 – – 0.980

0.701 0.654 – – 0.864

0.934 0.949 – – 0.961

Table 3: Table retrieval results on BIRD. J OIN GRH is the heuristic version of our algorithm. For J OIN GRX→Y we utilized the scorer trained on BEAVER dataset and evaluated on BIRD.

Table 2: Table retrieval results on BEAVER (DW). J O IN GR H is the heuristic version of our algorithm. For J OIN GRX→Y we utilized the scorer trained on BIRD dataset and evaluated on BEAVER.

5.3 5.2

PR @15

Additional Baselines

Additional Baselines DTR Contriever JARF (DTR) JARF (Contriever) JARIterative

@5

all-MiniLM-L6-v2

all-MiniLM-L6-v2 0.169 0.134 0.200 0.226 0.187

R @15

BGE-large-en-v1.5

BGE-large-en-v1.5 Vanila Retriever REaR J OIN GRH J OIN GR J OIN GRX→Y

P @5

Results on BIRD

Results on SPIDER

Spider is the least structurally demanding benchmark in our evaluation: 94% of queries require only one or two tables, and the schemas are well structured. For this dataset, retrieval is largely solved by direct query-schema similarity. Consequently, J O IN GR remains close to the corresponding vanilla retriever. With MiniLM, J OIN GR achieves R@15 of 0.748 compared with 0.752 for the vanilla retriever, indicating that query-conditioned traversal does not disrupt simple retrieval. Existing alignment-based baselines such as DTR, Contriever, JAR, and IterativeJAR perform strongly on Spider, reflecting that many required tables are directly recoverable from the query utterance. Full Spider results are reported in Appendix C

Table 3 reports results on BIRD. In comparison with BEAVER, BIRD is a high-recall setting for dense retrieval: 84% queries require only one or two tables. As a result, the vanilla retriever is already strong, reaching R@15 of 0.983 and PR@15 of 0.964 with BGE. In this setting, J OIN GR remains competitive. With BGE, REaR achieves the strongest R@15 and PR@15, while J OIN GR obtains the best P@5 and PR@5. The heuristic variant underperforms, suggesting that fixed-weight graph expansion can over-explore when semantic retrieval already identifies most relevant tables. The benefit of learned traversal is clearer with 6

6

Analysis

6.1

Precision and Recall by Query Complexity

0.26

0.19

4

0.64

0.66

0.86 3

0.23

0.12 2

0.18

ALL 1

0.17

5+

0.24

0.69

0.96

0.97

0.94

0.97

0.13

1

0.9

0.74 4

0.19

3

@5

0.07

0.3 0.37 0.34 0.31

0.52

0.7 2

0.31

0.28

0.31 0.43

ALL 1

0.97 0.13

(b)

0.07

0.53 0.67 0.53 0.5

0.93

0.95

0.81 0.49

0.37

0.91

(a)

1

0.35

The cross-domain rows, J OIN GRX→Y , in Tables 2, 3, and 5 evaluate transfer without target-domain supervision: the scorer is trained on dataset X and evaluated on dataset Y. This is crucial when annotated examples are scarce, as a scorer from another domain can serve as an initial tool until local supervision is collected. Section 5.1 shows BEAVER (DW) results as strong evidence: despite limited supervision, the BIRD-trained scorer is competitive with in-domain J OIN GR and other retrieval baselines, indicating that the scorer learns reusable behavior rather than fitting only the source benchmark. Transfer is less critical on BIRD and Spider, where vanilla retrieval is strong. However, BEAVER-trained scorers remain close to indomain J OIN GR on these datasets. Overall, crossdomain results support using J OIN GR as a reusable scoring mechanism that can be deployed before domain-specific supervision and then fine-tuned when local data justifies a domain-specific scorer.

0.19

Cross-Domain Transfer

0.2

5.4

5+

@15 Precision

Recall

Figure 5: Precision and Recall @5, 15 by number of gold tables: (a) BIRD, (b) BEAVER (DW).

6.2

Semantic Anchors vs. Graph Expansion

We isolate the value of structured traversal by varying the number of anchor tables on BEAVER (DW). All methods use MiniLM and are evaluated at K = 10. We use R@10 because BEAVER (DW) queries can require up to seven tables. The Vanilla Retriever returns tables directly from the semantic ranking. In contrast, J OIN GR starts from the same anchors but expands through the join graph, allowing it to retrieve additional tables. Figure 6 compares the Vanilla Retriever, heuristic J OIN GR, and trained J OIN GR as the number of anchors increases from 1 to 7. The gap between Vanilla and the graph-based variants is largest when the anchor budget is small. This indicates that many relevant BEAVER (DW) tables are not among the top semantic matches to the query, but can be recovered once retrieval expands from a related anchor through schema structure. As the number of anchors grows, Vanilla recall improves because more semantically similar tables are included directly, but it remains below the graph-based methods. The heuristic variant captures much of the gain from adding structure, while the trained scorer provides the best overall recall, especially at larger anchor budgets. This supports the central design of J OIN GR: the join graph supplies the expansion space, and learned edge weighting improves how relevance is distributed through

We analyze precision and recall by query complexity, using the number of required gold tables as a proxy for the join structure needed. Queries are bucketed into A LL, 1, 2, 3, 4, and 5+ required tables, reporting P/R at @5 and @15 for MiniLMJ OIN GR. We focus on the BIRD-trained scorer in two settings: BIRD (Dev), with many queries answerable from one or two tables, and BEAVER (DW), where queries often need multi-hop relational context. The BIRD scorer on BEAVER avoids evaluating queries possibly seen during BEAVER cross-validation. Figure 5 shows traversal preserves performance on simpler BIRD queries: for one- and two-table buckets, recall remains high, indicating the learned walk doesn’t disrupt cases where semantic retrieval identifies needed tables. BEAVER (DW) buckets show why traversal is necessary for harder queries. As required table count grows, recall remains higher, showing the walk recovers relevant tables even when retrieval becomes harder. The drop for 4- and 5+-table BEAVER queries reflects the difficulty of following longer join paths without target-domain supervision. 7

that space. Vanilla

Heuristic

Trained

or their serialized forms. Join-aware methods (Chen et al., 2024b; Boutaleb et al., 2025; Agarwal et al., 2025) add structural signals during retrieval or re-ranking. J OIN GR differs by using the database join graph itself as the retrieval space.

6

Graph-based retrieval. Graph retrieval has been widely used in multi-hop QA and document retrieval (Zhang et al., 2022; Gutierrez et al., 2024; Gutiérrez et al., 2025), where systems select anchors and expand through edges to recover evidence spread across multiple units. J OIN GR adapts this idea to relational schemas, where columns and tables form a natural hierarchy and foreign-key edges define possible retrieval paths.

R@10

0.6

0.4

0.2

0

1

2

3

4

5

7

Number of anchors

Figure 6: R@10 on BEAVER (DW) for different anchor budgets.

6.3

Schema graphs for tabular reasoning. Graphbased methods also appear for multi-table reasoning. (Wang et al., 2025) uses schema graphs for end-to-end QA/SQL generation, while (Safdarian et al., 2026) performs training-free schema linking by predicting tables and returning shortest paths in a table-level graph. J OIN GR focuses on upstream table retrieval, learning a traversal scorer over a column-level join graph, allowing retrieval through query-supported join paths. Concurrent anonymous work, CORE-T (Anonymous, 2026) tackles open-book multi-table retrieval for text-to-SQL on pooled heterogeneous tables without database IDs or gold foreign keys. It integrates offline LLM-generated metadata, a compatibility cache, and online dense retrieval with LLM selection to produce compact, join-coherent table sets. Whereas, J OIN GR uses a learned scorer for join-graph traversal.

Failure Cases

We inspect the BEAVER queries on which TrainedJ OIN GR misses at least one gold table at K=15. The dominant failure mode is the long tail of “narrative” joins: questions like “Which department occupies the most square footage?” require traversing four FK chains, and the third hop’s softmax frequently splits mass across two plausible neighbours. A second failure mode is anchor mis-selection: when the question vocabulary overlaps several tables (e.g., building, address, room), the top-5 anchors fail to include the eventual main table. Both failure modes are mitigated through additional anchors or hops, at the cost of latency.

7

Related Work

Table retrieval and schema linking for textto-SQL. Text-to-SQL systems identify relevant schema elements before generation, either within the parser or as an explicit upstream step (Wang et al., 2020a; Guo et al., 2019; Pourreza and Rafiei, 2023). Parser- and prompting-based systems assume the database schema for a question is provided, then perform schema linking. Recent LLMbased pipelines make this step crucial as irrelevant schema elements can distract generation or cause spurious joins (Maamari et al., 2024). While dense retrievers and prompt-based linkers rely on query to schema similarity, J OIN GR adds join-graph traversal, considering structurally related tables during retrieval.

8

Conclusion

We present J OIN GR, a table retriever using the database join graph as a search space. Retrieval starts from semantic anchors, follows join edges with a query-conditioned scorer, and aggregates evidence into table scores. This design separates semantic matching from structural expansion, allowing use of both direct question matches and schema connections. The main takeaway is that join structure guides retrieval, not just SQL generation. In settings where independent table similarity suffices, J OIN GR competes with standard retrievers. When tables connect through relational context, learned traversal aids recovery. J OIN GR exemplifies the principle: when information connects by structure, retrieval should use it.

Table representations and join-aware retrieval. Table encoders (Herzig et al., 2021; Deng et al., 2022), and dense retrievers (Izacard et al., 2022), learn semantic representations of tables, columns, 8

9

Limitations

Çağatay Demiralp, and Michael Stonebraker. 2024a. Beaver: an enterprise benchmark for text-to-sql. arXiv preprint arXiv:2409.02038.

J OIN GR depends on a join graph being constructable from the schema. For databases that lack declared foreign-key constraints, foreign keys must be inferred, typically via heuristic name-matching or an LLM pass, and the noise of that inference propagates into our edges. Second, our experiments use frozen encoders; we have not measured the effect of fine-tuning the encoder jointly with the scorer, and we expect that to be a useful but tangential extension. Third, the LLM-generated descriptors used in node and edge text are a one-time cost that scales linearly in the number of columns plus edges; on a 10,000-column schema this is tractable but not free. Finally, our evaluation is restricted to English-language questions and to three benchmarks; multilingual and lower-resource settings remain unexplored.

10

Peter Baile Chen, Yi Zhang, and Dan Roth. 2024b. Is table retrieval a solved problem? exploring join-aware multi-table retrieval. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2687– 2699, Bangkok, Thailand. Association for Computational Linguistics. Xiang Deng, Huan Sun, Alyssa Lees, You Wu, and Cong Yu. 2022. Turl: Table understanding through representation learning. SIGMOD Rec., 51(1):33–40. Jiaqi Guo, Zecheng Zhan, Yan Gao, Yan Xiao, JianGuang Lou, Ting Liu, and Dongmei Zhang. 2019. Towards complex text-to-SQL in cross-domain database with intermediate representation. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (ACL). Bernal Jimenez Gutierrez, Yiheng Shu, Yu Gu, Michihiro Yasunaga, and Yu Su. 2024. HippoRAG: Neurobiologically inspired long-term memory for large language models. In The Thirty-eighth Annual Conference on Neural Information Processing Systems.

Ethical Considerations

Table Retrieval is an enabling step for naturallanguage access to enterprise databases, with corresponding privacy implications: incorrect retrieval can disclose tables the user is not authorized to see, while correct retrieval enables them to query data that may be sensitive. Our method is no more or less prone to either failure than the baselines it compares against; we recommend that any deployment compose J OIN GR with a downstream authorization layer that is independent of the retrieval policy. We use LLMs only to generate schema descriptions, on data that the schema owner controls; no personal data leaves the database. AI writing assistants were used to polish the manuscript; all scientific claims, experimental design, and analysis were conducted and verified by the authors.

Bernal Jiménez Gutiérrez, Yiheng Shu, Weijian Qi, Sizhe Zhou, and Yu Su. 2025. From RAG to memory: Non-parametric continual learning for large language models. In Forty-second International Conference on Machine Learning. Jonathan Herzig, Thomas Müller, Syrine Krichene, and Julian Martin Eisenschlos. 2021. Open domain question answering over tables via dense retrieval. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics (NAACL). Gautier Izacard, Mathilde Caron, Lucas Hosseini, Sebastian Riedel, Piotr Bojanowski, Armand Joulin, and Edouard Grave. 2022. Unsupervised dense information retrieval with contrastive learning. Transactions on Machine Learning Research (TMLR).

References

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 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 Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track.

Rishita Agarwal, Himanshu Singhal, Peter Baile Chen, Manan Roy Choudhury, Dan Roth, and Vivek Gupta. 2025. Rear: Retrieve, expand and refine for effective multitable retrieval. arXiv preprint arXiv:2511.00805. Anonymous. 2026. CORE-T: Coherent retrieval of tables for text-to-sql. Allaa Boutaleb, Bernd Amann, Rafael Angarita, and Hubert Naacke. 2025. Exploring multi-table retrieval through iterative search. In EurIPS 2025 Workshop: AI for Tabular Data.

Karime Maamari, Fadhil Abubaker, Daniel Jaroslawicz, and Amine Mhedhbi. 2024. The death of schema linking? text-to-SQL in the age of well-reasoned language models. In NeurIPS 2024 Third Table Representation Learning Workshop.

Peter Baile Chen, Devin Yang, Weiyue Li, Fabian Wenz, Yi Zhang, Nesime Tatbul, Michael Cafarella,

9

Mohammadreza Pourreza and Davood Rafiei. 2023. DIN-SQL: Decomposed in-context learning of textto-SQL with self-correction. In Thirty-seventh Conference on Neural Information Processing Systems. Nils Reimers and Iryna Gurevych. 2019. SentenceBERT: Sentence embeddings using Siamese BERTnetworks. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP). AmirHossein Safdarian, Milad Mohammadi, Ehsan Jahanbakhsh Bashirloo, Mona Shahamat Naderi, and Heshaam Faili. 2026. SchemaGraphSQL: Efficient schema linking with pathfinding graph algorithms for text-to-SQL on large-scale databases. In Findings of the Association for Computational Linguistics: EACL 2026, pages 2585–2599, Rabat, Morocco. Association for Computational Linguistics. Bailin Wang, Richard Shin, Xiaodong Liu, Oleksandr Polozov, and Matthew Richardson. 2020a. RATSQL: Relation-aware schema encoding and linking for text-to-SQL parsers. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics (ACL). Wenhui Wang, Furu Wei, Li Dong, Hangbo Bao, Nan Yang, and Ming Zhou. 2020b. Minilm: Deep selfattention distillation for task-agnostic compression of pre-trained transformers. Advances in neural information processing systems, 33:5776–5788. Xixi Wang, Miguel Costa, Jordanka Kovaceva, Shuai Wang, and Francisco C. Pereira. 2025. Plugging schema graph into multi-table QA: A human-guided framework for reducing LLM reliance. In Findings of the Association for Computational Linguistics: EMNLP 2025, pages 5829–5842, Suzhou, China. Association for Computational Linguistics. Shitao Xiao, Zheng Liu, Peitian Zhang, Niklas Muennighoff, Defu Lian, and Jian-Yun Nie. 2024. C-pack: Packed resources for general chinese embeddings. In Proceedings of the 47th international ACM SIGIR conference on research and development in information retrieval, pages 641–649. Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev. 2018. Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-SQL task. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP). Jing Zhang, Xiaokang Zhang, Jifan Yu, Jian Tang, Jie Tang, Cuiping Li, and Hong Chen. 2022. Subgraph retrieval enhanced model for multi-hop knowledge base question answering. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 5773– 5784, Dublin, Ireland. Association for Computational Linguistics.

10

A

Algorithms

Algorithm 2 Query-Conditioned Table Search Require: Query q, embedder, offline index, node embeddings, edge embeddings, join graph, learned scorer S Require: Parameters: top-K, number of anchors A, max hops H Ensure: Ranked list of tables 1: x ← Embed(q) 2: C ← FAISS_Search(x, K) ▷ candidate nodes 3: A0 ← DeduplicateByTable(C) ▷ keep best node per table 4: DE ← ∅ ▷ edge deposits 5: for all anchor table Ta ∈ A0 do 6: L ← {(Ta , sa )} ▷ current frontier: table → score 7: V ←∅ ▷ visited tables 8: for h = 1 to H do ′ 9: L ←∅ 10: for all (Tf , sf ) ∈ L do 11: V ← V ∪ {Tf } 12: Ef ← OutgoingJoinEdges(Tf ) 13: if Ef = ∅ then 14: continue 15: end if 16: for all e = (kf , kn ) ∈ Ef do 17: Construct feature vector:

Algorithm 1 constructs a navigation graph over all databases in the dataset. Algorithm 2 performs query-conditioned graph traversal using offline semantic indexes and a learned edge scorer. Starting from retrieved anchor tables, the algorithm propagates relevance scores through join paths and ranks tables based on accumulated traversal deposits. Algorithm 1 Abstract Join Graph Construction Require: Tables T = {T1 , T2 , . . . , Tm } 1: for all table T ∈ T do 2: C(T ): set of columns in T 3: K(T ) ⊆ C(T ): set of key columns 4: end for Require: J : set of join relationships between key columns Ensure: Graph G = (V, E) 5: V ← ∅, E ← ∅ ▷ Add column nodes 6: for all table T ∈ T do 7: for all column c ∈ C(T ) do 8: Add node v(c) to V 9: Mark whether c ∈ K(T ) 10: end for 11: end for ▷ Add intra-table navigation edges 12: for all table T ∈ T do 13: N (T ) ← C(T ) \ K(T ) ▷ Connect non-key columns to key columns 14: for all n ∈ N (T ) do 15: for all k ∈ K(T ) do 16: Add edge (v(n), v(k)) to E with type intra 17: end for 18: end for ▷ Connect key columns pairwise 19: for all unordered pair (ki , kj ) ∈ K(T ) do 20: Add edge (v(ki ), v(kj )) to E with type intra 21: end for 22: end for ▷ Add inter-table join edges 23: for all join relationship between ka ∈ K(Ta ) and kb ∈ K(Tb ) do 24: Add edge (v(ka ), v(kb )) to E with type join 25: end for 26: return G = (V, E)

B

ϕ(e) =

Hyperparameters

Hyperparameter

Value

Max BFS hops H Scorer hidden dim Dropout Optimizer Learning rate Weight decay Gradient clipping LR scheduler factor / patience Margin m Training epochs (BIRD) CV folds (BEAVER)

5 64 0.3 Adam 10−3 10−4 1.0 ReduceLROnPlateau 0.5 / 3 0.1 20 5

Table 4: Hyperparameters used in all main experiments.

Full Results on Spider

Table 5 reports the complete Spider retrieval results omitted from the main paper for space considerations.

D

x ; emb(e) ; MaxSim(Tn ),  MaxSim(Tf ) ; sf ; h

18: end for 19: r ← S(ϕ) 20: p ← softmax(r) 21: for all (e, Tn , pe ) ∈ (Ef , nbrTables(Ef ), p) do 22: d ← s f · αh · p e 23: DE [e] ← DE [e] + d 24: if Tn ∈ / V then 25: L′ [Tn ] ← L′ [Tn ] + d 26: end if 27: end for 28: end for 29: L ← {(T, s) ∈ L′ | T ∈ / V} 30: if L = ∅ then 31: break 32: end if 33: end for 34: end for 35: DT ← AggregateTableDeposits(DE ) 36: return RankTables(DT )

Table 4 lists the hyperparameters used across all main experiments, including values for anchor candidates, number of anchors, BFS hops, MMR weight, model dimensions, optimization settings, learning rate, weight decay, gradient clipping, learning rate scheduler, margin, training epochs, and cross-validation folds.

C



BEAVER. Frozen encoders are from Hugging Face Hub checkpoints BAAI/bge-large-en-v1.5 and sentence-transformers/all-MiniLM-L6-v2. Full BFS-with-scorer evaluation runs at about 40 queries/second on CPU once embeddings are cached, making J OIN GR suitable for online LLM-front-end use.

Reproducibility

All training and evaluation use a single NVIDIA H200 GPU (40 GB), completing in under one hour for BIRD and under five minutes per fold for 11

Method

P @5

R @15

@5

PR @15

@5

@15

0.752 0.746 0.747 0.747 0.747

0.729 0.733 0.699 0.722 0.705

0.741 0.735 0.736 0.736 0.736

0.752 0.750 0.748 0.748 0.748

0.735 0.734 0.726 0.735 0.725

0.740 0.737 0.737 0.737 0.737

0.998 0.994 – – 0.985

0.930 0.928 – – 0.959

0.994 0.987 – – 0.975

BGE-large-en-v1.5 Vanilla Retriever REaR J OIN GRHeuristic J OIN GR J OIN GRBEAVER→SPIDER

0.215 0.216 0.209 0.213 0.210

Vanilla Retriever REaR J OIN GRHeuristic J OIN GR J OIN GRBEAVER→SPIDER

0.216 0.216 0.214 0.216 0.214

0.072 0.099 0.072 0.072 0.072

0.745 0.745 0.715 0.737 0.721

all-MiniLM-L6-v2 0.072 0.121 0.072 0.072 0.072

0.749 0.748 0.739 0.747 0.739

Additional Baselines DTR Contriever JARF (DTR) JARF (Contriever) IterativeJARContriever

0.284 0.417 0.419 0.399 0.293

0.101 0.143 – – 0.099

0.958 0.970 0.978 0.937 0.975

Table 5: Table retrieval results on Spider.

12

Related documents

• JoinGR: Learning to Traverse Join Graphs for Table Retrieval#1155999
• EviLink: Multi-Path Schema Linking with Uncertainty-Guided Evidence Acquisition for Large-Scale Text-to-SQL#1128603
• Associativity-Peakiness Metric for Contingency Tables#134538
• When LLMs Read Tables Carelessly: Measuring and Reducing Data Referencing Errors#324920
• Algebraic Subgraph Counting#1155244