betaFeedback

WorksComputer Science

Adaptive-Elbow Graph Traversal for Schema Retrieval in Text-to-SQL

Abstract

LLM-based natural-language interfaces to relational databases are gated by a schema-retrieval step: the generator can only be as good as the slice of schema it is shown. On a database with hundreds of tables, that slice must be selected and the selection is two-sided—omit a needed table and the query becomes unrecoverable, include too many and the irrelevant ones act as noise that degrades the model's output. When an agentic retriever that lets the model inspect the schema can be too costly or too slow, the fallback is an embedder that ranks tables by cosine similarity and keeps a top-k. This fallback has two weaknesses: a fixed budget is suboptimal question by question, and embedding similarity overlooks foreign-key-linked tables that are necessary for joins. We present Adaptive-Elbow Graph Traversal (AEGT, ElbowHop for short), a property-graph table retriever that addresses both: an adaptive elbow cutoff replaces the fixed budget with a per-question one under a single aggressiveness parameter, and bidirectional foreign-key traversal deterministically recovers the bridge tables embedding similarity misses. We evaluate the retriever on 3 corpora of increasing candidate-pool size (BIRD Mini-Dev queried per database, 3–13 tables; its eleven schemas merged, 74; and a merged Spider-train graph, 546) and isolate the two mechanisms under a per-question budget-matched protocol. Across these settings the adaptive elbow emerges as the dominant mechanism—at matched recall it roughly doubles precision over a fixed budget on the larger pools, the margin widening as the pool grows—while the foreign-key traversal pays off on the join-critical bridge tables dense retrieval cannot reach, in the single-hop tight-budget case. We characterize the method as a low-cost, recall-robust first stage for schema retrieval on which a downstream selection or generation step can build.

Introduction

Using LLMs to translate natural-language questions into SQL queries is a promising way to make enterprise data accessible without SQL fluency. However, their accuracy is upper-bounded by a step that takes place before any query is generated: schema retrieval. A small schema can be shown to an LLM in full; a typical enterprise database with hundreds of tables breaks this down—and not only by exceeding the context window. Even when it fits, padding the prompt with irrelevant tables measurably degrades accuracy: models are easily distracted by irrelevant context [1], use long inputs increasingly poorly as they grow [2], and in RAG settings the noise from non-relevant passages can dominate output quality [3]. The system must therefore first select a small relevant subset, and the error is two-sided: miss the right tables and the correct query is unrecoverable (a recall failure); bury them under wrong ones and the generator reasons worse than it could (a precision failure). The upstream step thus caps the whole stack’s accuracy.

One can let an LLM inspect the schema (reading descriptions, sampling values, reasoning over joins) as the agentic stacks of MAC-SQL [4], CHESS [5], and CHASE-SQL [6] do; but running such a stage over the full table set of a large catalogue can be expensive, slow, and itself exposed to the noise above. The regime we study puts a low-cost stage first: a local embedding model ranks tables by cosine similarity and returns a small candidate set, so any downstream stage like column selection, an LLM filter, or a full agentic selector—operates over a smaller subset. Our goal is not to replace the agentic stage but to

© 2026 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). make this cheap prefilter as robust as possible: keep the gold tables (high recall) while shrinking the set to cut noise.

The naive dense baseline in this regime has two chronic weaknesses. First, it returns a fixed budget for all questions: a single kk is shipped to production, yet simple questions get padded with distractor tables while complex ones lose gold tables off the bottom of the list. Second, it ignores structure: tables that are essential to the join graph but whose names and descriptions are semantically dissimilar to the question—bridge tables such as order_items for “which products did customer XX buy?”—can be systematically missed. We attack the first weakness with an adaptive elbow that sets a per-question budget under a single aggressiveness knob α\alpha, and the second with bidirectional foreign-key traversal over a property graph of tables and columns.

Crucially, we do not assume these two mechanisms help equally, and we measure each in isolation along an axis of growing difficulty: the size of the candidate pool the retriever must search. We evaluate at the table level on three corpora—BIRD Mini-Dev queried per database (a pool of 3–13 tables), the same eleven schemas merged into one 74-table pool, and a merged Spider-train graph of 546 tables. Our contributions are:

  1. Adaptive elbow with aggressiveness scaling. We extend the Kneedle knee-detection algorithm [7] into a question-dependent retrieval budget controlled by a single α\alpha knob, replacing the fixed top-kk used by current text-to-SQL schema retrievers (§ 3.3).

  1. Bidirectional foreign-key traversal. We use a property graph of tables and columns to expand the seed set with bridge tables that embedding similarity cannot reach, in a deterministic step over a foreign-key graph loaded once from PostgreSQL and subsequently traversed in memory (§ 3.4).

  1. An empirical map of when each mechanism pays off. Under a strict per-question budget-matched protocol across three pool sizes—each reported gap attributable to one mechanism rather than to budget inflation—we show that the elbow’s precision advantage at matched recall grows with the candidate pool, while the foreign-key traversal’s recall contribution concentrates at tight seed budgets and a single hop (§ 4.4–§ 5.4).

We deliberately scope the present paper to the table stage—the object whose correctness gates the join graph—and treat column selection and downstream SQL generation as separate stages, the latter a direction we leave to future work.

Background and Related Work

Schema retrieval and linking. Deciding which schema elements to put in front of the model is an old problem. Long before LLMs, schema matching, surveyed by Rahm and Bernstein [8], already aligned a query with the right tables and columns by combining linguistic cues (their names) with structural ones (how they connect in the schema). On the text-retrieval side, the durable baseline for short, name-heavy strings such as table descriptions is Okapi BM25 [9]; when a dense embedding ranker is available too, the two ranked lists are typically merged into one by reciprocal rank fusion [10]. LLM-based text-to-SQL then made dense embedding similarity the default schema retriever [5]. CRUSH4SQL [11] adds a twist: instead of embedding the raw question, it has an LLM hallucinate the minimal schema the answer would need and retrieves real tables against that imagined target.

A separate group of methods uses schema structure, but not to retrieve. RAT-SQL [12] and LGESQL [13] fold the schema graph into the encoder so the generator can see how tables and columns relate, and RESDSQL [14] separates schema linking from generating the SQL skeleton; all three assume the whole schema already fits in the model, so they never confront the retrieval problem we do. The strongest agentic text-to-SQL systems make the same assumption from the other end: MAC-SQL [4], CHESS [5], CHASE-SQL [6], and XiYan-SQL [15] pour their engineering into the downstream generator and selector and just reuse an off-the-shelf embedding retriever upstream. That inherited retriever is exactly the first stage we set out to improve, with their precision-oriented generation stage assumed to sit on top of it.

Graph-structured and adaptive RAG. Two lines of general retrieval-augmented generation [16] sit close to ours, but each answers a different question than we do. The first asks where to retrieve from, and answers with a graph: instead of treating a corpus as a flat list of passages, it links the passages (or the entities in them) into a graph and searches over that. Microsoft GraphRAG [17] clusters related entities and retrieves one summary per cluster, LightRAG [18] builds a cheaper index and queries it at two resolutions—individual entities and broad topics—and HippoRAG [19] scores a passage by how a random walk over a knowledge graph reaches it. All of these graphs are built over free text and the entities it mentions, not over a database’s foreign keys; StructGPT [20], the one method here that does target structured data, gives the LLM an interface to query the tables rather than a graph to retrieve them. None uses the join structure a relational schema already carries—the structure our traversal follows.

The second line asks whether to retrieve at all, rather than what: Self-RAG [21] trains the model to emit special tokens that, mid-generation, call or skip a lookup; FLARE [22] triggers one whenever the sentence it is about to write looks uncertain; and Adaptive-RAG [23] sends easy questions down a light pipeline and hard ones down a heavy one. Neither line settles the question we face—how many tables to keep once retrieval has fired, the cutoff itself. That is a knee-detection problem, classically handled by the Kneedle algorithm [7], which we extend with an aggressiveness parameter so the budget–recall trade-off becomes a single tunable knob.

Positioning. Our retriever combines three ingredients in a configuration we have not seen elsewhere: (i) a property graph stores tables and columns as typed nodes with chunked embeddings, so cosine retrieval and graph traversal share the same store; (ii) the selection uses an adaptive elbow with an explicit aggressiveness parameter that sets how much to retrieve per question, a knob the adaptive-RAG line [21, 22, 23] does not offer, since it decides only whether to retrieve, not how large the retrieved set should be; (iii) bidirectional foreign-key traversal adds tables that are structurally necessary for joins but semantically dissimilar to the query, a deterministic complement to the LLM-hallucination bridge of CRUSH4SQL [11] and the entity-community summarisation of Microsoft GraphRAG [17].

Adaptive-Elbow Graph Traversal

Adaptive-Elbow Graph Traversal (AEGT; ElbowHop) maps each question to a table set T\mathcal{T} through adaptive semantic selection followed by bidirectional foreign-key traversal (Algorithm 1). The resulting set feeds a downstream column-selection stage that retains primary and foreign keys and produces an M-Schema-style representation [15]; this stage is outside the present evaluation.

Property Graph Store

The schema knowledge graph is stored in PostgreSQL under a dedicated schema per tenant through three relations: nodes(idid, labellabel, propsprops JSONB), edges(idid, srcsrc, dstdst, relrel), and embeddings(node_idnode\_id, vector_jsonvector\_json JSONB). Two node types are used by the retriever: Table (name, description) and Column (name, datatype, description, is_primary, is_foreign), linked by HAS_COLUMN (Table →\to Column) and REFERENCES (Table ↔\leftrightarrow Table, encoding foreign-key links and traversed bidirectionally). As a reference scenario, consider the table-level path

customers↔orders↔order_items↔products\mathit{customers} \leftrightarrow\mathit{orders} \leftrightarrow\mathit{order\_items} \leftrightarrow\mathit{products}

Each relation is a Table node, its attributes are Column nodes connected through HAS_COLUMN, and foreign keys induce the REFERENCES links shown above. For “Which products did customer X buy?”, semantic retrieval may favour customers and products, while traversal recovers the less salient intermediate tables.

Embeddings and Cosine Similarity

Each node’s text is embedded offline with all-MiniLM-L6-v2 (384 dimensions, served locally). We also conducted preliminary experiments with the larger gte-large backbone, which left the main qualitative retrieval trends unchanged. We therefore retained all-MiniLM-L6-v2 for the reported experiments because of its lower computational cost. This preliminary comparison should not be interpreted as a systematic embedding-model ablation: a larger or domain-tuned model may change the similarity-score distribution, absolute retrieval quality, and the position of the detected elbow, even if the proposed adaptive-selection and graph-traversal mechanisms remain applicable. Long text is chunked at a stride of 240 tokens, producing multiple (vector, chunk_text) pairs per node. Let chunks⁡(n)\operatorname{chunks}(n) denote the set of text chunks associated with node nn, eq∈R384e_q \in\mathbb{R}^{384} the embedding of query qq, and ec∈R384e_c \in\mathbb{R}^{384} the embedding of chunk cc. At retrieval time, the similarity of node nn to query qq is defined as the maximum cosine similarity across all chunks belonging to that node:

sim⁡(q,n)=max⁡c∈chunks⁡(n)eq⋅ec∥eq∥∥ec∥.(1)\operatorname{sim}(q,n) = \max_{c \in\operatorname{chunks}(n)} \frac{e_q \cdot e_c}{\lVert e_q\rVert\lVert e_c\rVert}. \tag*{(1)}

Here, ⋅\cdot and ∥⋅∥\lVert\cdot\rVert denote the Euclidean inner product and norm. The maximum assigns each node the score of its best-matching chunk; nodes are then ranked by this score.

Adaptive Elbow Detection

Equation (1) scores every candidate node; sorting those scores in descending order gives a similarity sequence s0≥s1≥⋯≥sn−1s_0 \ge s_1 \ge\cdots\ge s_{n-1}, where nn is the number of candidates in the pool and sis_i is the cosine similarity of the candidate at rank ii (so s0s_0 is the closest match and sn−1s_{n-1} the farthest). Such a curve typically has a steep head of clearly relevant nodes followed by a long, flat tail of near-ties that are mostly noise; the “elbow” is the rank where the head gives way to the tail. A fixed top-kk commits to that rank in advance, whereas we locate it per question from the shape of the curve, in four steps.

(1) Smoothing. Adjacent similarities are noisy—two candidates can swap places by chance—which would jitter the detected elbow. We first pass a moving average over the sequence. To avoid hand-tuning its width, we tie it to the pool size: a base window w1=max⁡(3,⌊log⁡2n⌋)w_1 = \max(3, \lfloor\log_2 n \rfloor) and a wider one w2=2w1−1w_2 = 2w_1 - 1, both edge-padded so the endpoints are not shortened. Smoothing at two widths, rather than one, keeps the outcome from hinging on a single arbitrary choice.

(2) Elbow as the point of maximum bend. For each smoothed sequence s~(k)\tilde{s}^{(k)}, with k∈{1,2}k \in\{1,2\} indexing the two windows, let mkm_k denote its length. We draw the straight chord between its first and last points, (0,s~0(k))(0,\tilde{s}^{(k)}_0) and (mk−1,s~mk−1(k))(m_k - 1,\tilde{s}^{(k)}_{m_k-1}). The distance of the point at rank ii from this chord is

di(k)=∣(s~mk−1(k)−s~0(k))i−(mk−1)s~i(k)+(mk−1)s~0(k)∣(s~mk−1(k)−s~0(k))2+(mk−1)2,i∈{0,…,mk−1}.(2)d_i^{(k)} = \frac{ \left| \left(\tilde{s}^{(k)}_{m_k-1}-\tilde{s}^{(k)}_0\right)i -(m_k-1)\tilde{s}^{(k)}_i +(m_k-1)\tilde{s}^{(k)}_0 \right| }{ \sqrt{ \left(\tilde{s}^{(k)}_{m_k-1}-\tilde{s}^{(k)}_0\right)^2 +(m_k-1)^2 } }, \qquad i \in\{0,\ldots,m_k-1\}. \tag*{(2)}

Here, ii is the rank and s~i(k)\tilde{s}^{(k)}_i its smoothed similarity. The candidate elbow is the earliest rank attaining the maximum distance:

i^(k)=min⁡{i:i∈arg max⁡j∈{0,…,mk−1} dj(k)}.(3)\hat{i}^{(k)} = \min\left\{i : i \in\underset{j \in\{0,\ldots,m_k-1\}}{\operatorname{arg\,max}}\, d_j^{(k)}\right\}. \tag*{(3)}

The detector uses chord distance rather than differential curvature. Its distance profile need not be unimodal and may contain multiple local maxima or tied global maxima. For a tie, we select the smallest index, avoiding an unnecessarily deep cutoff. Smoothing and aggregation across two windows reduce local instability but do not guarantee uniqueness; selection among distinct local maxima remains an open problem. (3) Robustness via median. The two windows can disagree on where the elbow sits; we reduce them to a single integer index

i^=⌊median⁡(i^(1),i^(2))⌋.\hat{i} = \left\lfloor\operatorname{median}\left(\hat{i}^{(1)},\hat{i}^{(2)}\right) \right\rfloor.

For two indices, the median is their midpoint, which is rounded down before applying the aggressiveness scaling. This aggregation prevents either smoothing width from determining the cutoff on its own.

(4) Aggressiveness scaling. Steps (1)–(3) give a neutral, data-driven cut; a single knob α>0\alpha> 0 then trades recall against precision without re-detecting anything, acting in two reinforcing ways. It first shifts the elbow location according to

i^α=clip⁡(⌊αi^⌋,1,n−1),(4)\hat{i}_{\alpha} = \operatorname{clip}\left(\left\lfloor\alpha\hat{i} \right\rfloor, 1, n-1\right), \tag*{(4)}

where α>0\alpha> 0 is the aggressiveness parameter and clip⁡(x,a,b)=min⁡(max⁡(x,a),b)\operatorname{clip}(x,a,b)=\min(\max(x,a),b). Values α>1\alpha> 1 move the cutoff deeper into the ranking and retain more candidates, whereas values α<1\alpha< 1 move it toward the head and retain fewer candidates. The lower bound of 1 ensures that the highest-ranked candidate is always retained. Rather than cutting directly at the integer rank i^α\hat{i}_{\alpha}, we convert it into the similarity threshold

τ=clip⁡(si^α−(s0−si^α)(α−1),sn−1,s0).(5)\tau= \operatorname{clip}\left(s_{\hat{i}_{\alpha}}-(s_0-s_{\hat{i}_{\alpha}})(\alpha-1),s_{n-1},s_0\right). \tag*{(5)}

The retriever retains candidates whose original similarity satisfies si≥τs_i \ge\tau. For α>1\alpha> 1, both transformations move the cutoff deeper and lower τ\tau; for α<1\alpha< 1, they have the opposite effect. At α=1\alpha= 1, the adjustment vanishes. When n≤1n \le1, the available candidate is returned unchanged.

The elbow reads the shape of the similarity curve for the question at hand, so the per-question budget it returns reflects how densely the corpus populates the knee, not the number of gold tables (a point we return to in § 6).

Bidirectional Foreign-Key Traversal

After the initial table selection T\mathcal{T} via embedding similarity, the set is expanded by traversing REFERENCES edges for thopt_{\mathrm{hop}} iterations. At each hop, the algorithm adds all tables connected to the current frontier via REFERENCES edges in either direction. The traversal is bidirectional because a question can be asked from the perspective of either side of a one-to-many relationship.

The mechanism targets bridge tables: tables required for a valid join despite weak semantic similarity to the question. In the scenario of § 3.1, orders and order_items connect the semantically salient endpoint tables. Bidirectional traversal can recover them from either endpoint selected by the embedding stage.

Algorithm 1 ElbowHop (Adaptive-Elbow Graph Traversal) Table Retrieval.

Require: Query qq, graph GG, parameters αtable\alpha_{\mathrm{table}}, thopt_{\mathrm{hop}}

Ensure: Table set T\mathcal{T}

  1. eq←Embed⁡(q)e_q \leftarrow\operatorname{Embed}(q)

  2. T←TableRAG⁡(G,eq,αtable)\mathcal{T} \leftarrow\operatorname{TableRAG}(G,e_q,\alpha_{\mathrm{table}}) {cosine sim + adaptive elbow}

  3. for t=1t=1 to thopt_{\mathrm{hop}} do

  4. T←T∪ReferenceNeighbours⁡(G,T)\mathcal{T} \leftarrow\mathcal{T} \cup\operatorname{ReferenceNeighbours}(G,\mathcal{T}) {bidirectional FK traversal}

  5. if no new tables added then

  6. &nbsp;&nbsp;&nbsp;&nbsp;break

  7. end if

  8. end for

  9. return T\mathcal{T}

Experimental Setup

Corpora and the Pool-Size Axis

The central experimental axis is the size of the candidate pool the retriever must search. We construct three corpora of growing pool size. BIRD per-DB queries the BIRD Mini-Dev set [24] one database at a time, so each question is answered against only its own 3–13 tables; this is the easy regime in which a fixed budget is already nearly correct. BIRD merged loads the same eleven schemas into a single 74-table property graph, so every question must now be disambiguated against ten other databases. Spider merged loads the Spider training databases [25] into one 546-table graph, the largest pool. The first transition (per-DB →\to merged) uses the same eleven BIRD schemas and the same query set, changing only whether each question is retrieved against its source database or against the combined 74-table pool. It therefore provides our controlled comparison of pool size. Spider merged serves a different purpose: it tests whether the qualitative behaviour observed on BIRD persists on a second corpus and at a substantially larger scale. The transition from BIRD merged to Spider merged does not isolate pool size, since dataset composition changes as well, and should therefore not be interpreted as a controlled causal comparison of the 74- and 546-table conditions. Each corpus is evaluated on 500 NL–SQL pairs (seed 1234). For each query the gold tables are extracted from the gold SQL with an abstract-syntax-tree parser (sqlglot), falling back to a regular-expression parser only when AST parsing fails. Every retriever consumes the same embeddings, graph store, and database connection.

Metrics

Let T^\hat{\mathcal{T}} denote the set of tables returned by a retriever and T⋆\mathcal{T}^{\star} the set of gold tables extracted from the reference SQL query. We compute table-level recall and precision as

Recall⁡=∣T^∩T⋆∣∣T⋆∣,(6)\operatorname{Recall} = \frac{\lvert\hat{\mathcal{T}} \cap\mathcal{T}^{\star} \rvert}{\lvert\mathcal{T}^{\star} \rvert}, \tag*{(6)}
Precision⁡=∣T^∩T⋆∣∣T^∣.(7)\operatorname{Precision} = \frac{\lvert\hat{\mathcal{T}} \cap\mathcal{T}^{\star} \rvert}{\lvert\hat{\mathcal{T}} \rvert}. \tag*{(7)}

Here, ∣⋅∣\lvert\cdot\rvert denotes set cardinality and T^∩T⋆\hat{\mathcal{T}} \cap\mathcal{T}^{\star} is the set of correctly retrieved gold tables. Recall is the quantity a first-stage retriever must protect—a gold table dropped here is generally unrecoverable downstream—while precision quantifies how much distractor budget the generator (or a precision stage) must absorb, distractors having a measurable cost [1, 2, 3].

Retrievers and Ablation Variants

All retrievers are backed by the same property-graph store and differ only in how they select tables. To decompose the two mechanisms, we compare the full retriever against an ablation of each. All baselines stay within the retriever’s own cost class—local-embedder methods that issue no LLM calls at retrieval time, the kind a production top-kk RAG pipeline deploys; agentic and LLM-in-the-loop selectors occupy a different cost/latency regime and are the downstream precision stage we assume, not a baseline here.

  • ElbowHop (ours). Adaptive elbow with aggressiveness αtable\alpha_{\mathrm{table}}, followed by thopt_{\mathrm{hop}} iterations of bidirectional REFERENCES traversal (Algorithm 1). The seed budget is set per question by the elbow.

  • ElbowHop-fixedkk (elbow ablation). Identical to ElbowHop but the per-question elbow seed is replaced by a fixed seed size equal to the mean elbow seed at that sweep cell, followed by the same FK traversal. Comparing ElbowHop against ElbowHop-fixedkk isolates the value of per-question adaptivity.

  • Dense (same-kk) (traversal ablation / baseline). Pure top-kk cosine ranking over the Table nodes, matched to the per-question total output of ElbowHop-fixedkk: k=∣Tfixed−k∣k = \lvert\mathcal{T}_{\mathrm{fixed-}k} \rvert, the number of tables returned by ElbowHop-fixedkk after FK expansion (seed tables plus FK-expanded neighbours). Dense and ElbowHop-fixedkk therefore retrieve the same total number of tables per question; any recall difference is attributable solely to the FK structure, not to budget inflation.

  • Hybrid RRF. Reciprocal rank fusion [10] of the dense and a sparse Okapi BM25 [9] ranking (k1=1.5k_1=1.5, b=0.75b=0.75) at the canonical krrf=60k_{\mathrm{rrf}}=60, budget-matched per question. BM25 tokenisation is lowercase [A-Za-z0-9_]+, which splits snake_case implicitly.

Comparison Protocol and Parameter Sweep

Dense is matched per question to the total output of ElbowHop-fixed-kk, including FK expansion. Thus, the two methods return the same number of tables and their recall difference isolates the effect of graph traversal. In the full frontier comparison, ElbowHop retains its smaller adaptive budget by design. Reported ⟨k⟩\langle k\rangle values are averages over questions. We sweep αtable∈{0.2,0.4,0.6,0.8,1.0,1.2,1.4}\alpha_{\mathrm{table}} \in\{0.2, 0.4, 0.6, 0.8, 1.0, 1.2, 1.4\} and thop∈{0,1,2,3}t_{\mathrm{hop}} \in\{0, 1, 2, 3\}, yielding 14,000 per-query records per corpus. Metrics are means over 500 questions with ±1\pm1 SEM bands. Unless stated otherwise, reported ablation values use αtable=0.6\alpha_{\mathrm{table}} = 0.6. BM25 uses k1=1.5k_1 = 1.5 and b=0.75b = 0.75, while RRF uses krrf=60k_{\mathrm{rrf}} = 60.

Results

We first read the ElbowHop operating surface across the three pools (§ 5.1), then isolate each mechanism in turn: the adaptive elbow versus a fixed budget (§ 5.2), the foreign-key traversal versus none at a matched budget (§ 5.3), and the full retriever against the budget-matched baselines (§ 5.4).

The Operating Surface Across Pool Sizes

Sweeping ElbowHop over the thop×αtablet_{\mathrm{hop}} \times\alpha_{\mathrm{table}} grid, the qualitative structure is identical across the three pools: table recall rises with both αtable\alpha_{\mathrm{table}} and thopt_{\mathrm{hop}} while precision falls. What changes dramatically with pool size is the price of high recall. On BIRD per-DB, one hop already reaches 81–99% recall while precision stays at 34–60%; on BIRD merged the same one-hop row spans 82–100% recall but precision collapses from 57% to 3% as α\alpha grows; on Spider merged it reaches 100% recall only at precision near zero, with the maximal budget approaching the entire 546-table pool. The region of high recall at usable precision is broad on the small pool and almost disappears on Spider.

We adopt αtable=0.6\alpha_{\mathrm{table}}=0.6 as the single default operating point for the analyses that follow: at this setting table recall is already high on the realistic merged pools while the set stays bounded (of order ten tables on BIRD merged, twenty on Spider merged). The meaningful range αtable∈[0.2,1.2]\alpha_{\mathrm{table}}\in[0.2, 1.2] holds across all three corpora despite pool sizes differing by two orders of magnitude; what changes across pools is the absolute budget the elbow allocates at a given α\alpha, while the useful range of α\alpha itself does not.

The Adaptive Elbow Beats a Fixed Budget

Figure 1 fixes αtable=0.6\alpha_{\mathrm{table}}=0.6 and plots the distribution of the per-question elbow seed kseedk_{\mathrm{seed}} over the 500 questions. The elbow does not settle on one value, and the right way to measure its spread is in absolute tables, since precision is governed by ∣T∗∣/k|T^*|/k: a fixed kk that misbudgets a query by Δk\Delta k tables wastes or forgoes Δk\Delta k tables. By that measure the spread grows sharply with the pool—mean absolute deviation 0.4→1.7→4.7 tables (coefficient of variation 0.48→0.52→0.79; seed range 1–4→1–18→1–82)—so a fixed kk set to the mean disagrees with the per-question seed by ever more tables, falling below it for some queries (at risk to recall) and above it for the rest (at cost to precision). This establishes only that the room for a per-question policy grows with pool size; it does not, on its own, show the elbow’s choices are the right ones, since deviations are measured against the elbow’s own mean—reading them as “errors” would assume exactly what is in question. Whether the variation is useful—whether it buys recall and precision against the gold tables—is settled by the head-to-head below.

Per-query variation of the elbow seed at fixed alpha

Figure 1. Per-question variation of the elbow seed at a single aggressiveness αtable=0.6\alpha_{\mathrm{table}}=0.6. Top: distribution of the elbow seed kseedk_{\mathrm{seed}} over 500 questions per corpus; the dashed line is the mean (the “fixed kk”). The absolute spread (MAD, in tables) grows with the pool—0.4→1.7→4.70.4 \to1.7 \to4.7 tables—as does the relative spread (CV, 0.48→0.52→0.790.48 \to0.52 \to0.79). Bottom: questions sorted by kseedk_{\mathrm{seed}}; a single fixed kk (its mean) falls below the per-question seed for some queries (fewer tables, at risk to recall) and above it for the rest (more tables, at cost to precision), splitting them 20%/80% (BIRD per-DB), 40%/60% (BIRD merged), and 39%/61% (Spider merged).

Figure 2 isolates the elbow by comparing ElbowHop (per-question elbow + FK) against ElbowHop-fixed-kk (fixed seed + FK), each at its own budget, one panel per hop depth thop∈{0,1,2,3}t_{\mathrm{hop}} \in\{0, 1, 2, 3\}. On the two merged pools, at essentially identical recall the elbow delivers markedly higher precision at every hop depth: on BIRD merged at thop=1t_{\mathrm{hop}}=1 it reaches 97% recall at 36.9% precision versus 25.6% for the fixed-kk seed, and the advantage widens with the pool—on Spider merged the elbow lifts precision from 7.0% to 14.3% at one hop. On the small BIRD per-DB pool the win does not reproduce: at thop≤1t_{\mathrm{hop}}\le1 the elbow’s smaller budget trades a little recall for precision rather than winning outright, and at $t_{\mathrm{hop}}\ge 2 the two budgets all but coincide and the curves converge. With only a handful of candidate tables there is little room for a per-question budget to differ from a fixed one (the 0.4-table divergence of Figure 1), so the benefit is confined to the larger pools and grows with their size.

Elbow contribution: ElbowHop vs ElbowHop-fixed-$k$

Figure 2. ElbowHop (per-question elbow, solid) versus ElbowHop-fixedkk (fixed seed, dashed), each at its own budget, with blue = recall (left axis) and red = precision (right axis), one panel per thopt_{\mathrm{hop}} and ±1\pm1 SEM bands. At matched recall the elbow holds substantially higher precision, and the gap grows with pool size. Markers along each curve are the swept αtable\alpha_{\mathrm{table}} values, labelled in every panel and increasing with kk from left to right (αtable=0.6\alpha_{\mathrm{table}}=0.6, our default, is the third).

Foreign-Key Traversal Analysis

We isolate the traversal by comparing ElbowHop-fixedkk (fixed seed + FK) against Dense at the same per-question total budget: Dense retrieves ∣Tfixed−k∣|\mathcal{T}_{\mathrm{fixed-}k}| tables per question by pure cosine ranking—the same count as ElbowHop-fixedkk after FK expansion. With the total table count identical, every recall difference is attributable to the FK structure alone. Figure 3 plots the recall (top) and precision (bottom) frontiers for all three pools. The recall gain from the FK structure is budget-dependent: it is largest at the tight-budget end of each curve (low αtable\alpha_{\mathrm{table}}) and on the smaller pools—where the seed is still impoverished, the FK-expanded set recovers more gold tables than pure dense at the same total budget—and it narrows as the budget grows and the seed already spans the join neighbourhood.

Hop contribution: ElbowHop-fixed-k vs Dense (same-k), with recall and precision curves for BIRD per-DB, BIRD merged, and Spider merged

Figure 3. Foreign-key hop contribution at iso-budget. ElbowHop-fixedkk (seed + FK, one curve per thopt_{\rm hop}) versus Dense at the same per-question total budget (k=∣Tfixed−k∣k = |\mathcal{T}_{\mathrm{fixed-}k}|); recall (top) and precision (bottom) with ±1\pm1 SEM bands. The FK traversal adds only +3 to +8 recall points, at thop=1t_{\rm hop}=1; precision is identical between the two.

At our αtable=0.6\alpha_{\mathrm{table}}=0.6 default the gap is already modest (+8 points on BIRD per-DB, +2 on BIRD merged, +3 on Spider merged), and a single hop captures essentially all of it: the second hop adds +1 or less on every corpus (≈ 0 on Spider). On precision the two methods are indistinguishable, both lying on the same ≈ ∣T⋆∣/k|\mathcal{T}^\star|/k line (bottom panels). Aggregate recall averages the join-critical bridge tables into the much larger set of content tables the dense seed already finds, which we isolate next.

Where the traversal pays off: bridge tables. We re-analyse the saved iso-budget runs, restricting recall to bridge tables: gold tables that appear in the query yet contribute no content column—none in SELECT, WHERE, GROUP BY, HAVING, or ORDER BY—their only occurrences being join keys. These junction/linking tables carry little or no direct lexical signal from the question for the dense encoder and are recovered by FK traversal by construction; we identify them structurally and deterministically from each gold query. Fixing thop=1t_{\mathrm{hop}}=1 and sweeping αtable\alpha_{\mathrm{table}}, Figure 4 plots Δ=recall⁡(seed+FK)−recall⁡(dense same-k)\Delta= \operatorname{recall}(\mathrm{seed}+\mathrm{FK}) - \operatorname{recall}(\mathrm{dense\ same\text{-}}k) in points against the mean budget. On every corpus the bridge-table gain is large and concentrated at tight budget: +15+15 points on BIRD (per-DB and merged) and +6+6–77 on Spider at the smallest αtable\alpha_{\mathrm{table}}, decaying toward zero as the budget grows—once kk is wide enough, dense recovers the bridges by pure spread.

Bridge-table recall gain of the FK traversal at iso-budget for BIRD per-DB, BIRD merged, and Spider merged

Figure 4. Bridge-table recall gain of the FK traversal at iso-budget: Δ=recall(seed+FK)−recall(dense same−k)\Delta= \mathrm{recall}(\mathrm{seed+FK})-\mathrm{recall}(\mathrm{dense\ same-}k), in points, restricted to content-column-free junction/linking gold tables, at thop=1t_{\rm hop}=1. Each marker is one swept αtable\alpha_{\mathrm{table}}, placed at its mean budget kk. The gain peaks at tight budget (+15 points on BIRD, +6–7 on Spider) and decays as kk grows. Counts: 72 bridge queries / 78 bridge tables on BIRD, 142 / 161 on Spider.

The Full Retriever vs. Budget-Matched Baselines

Figure 5 plots the recall and precision frontiers against the average budget kk (log scale) for ElbowHop (one solid curve per thopt_{\rm hop}) and the Dense and Hybrid-RRF baselines.

Recall and precision frontiers for BIRD per-DB, BIRD merged, and Spider merged

Figure 5. Recall (top) and precision (bottom) frontiers versus average budget kk (log scale) for ElbowHop (solid, one per thopt_{\mathrm{hop}}), Dense (dashed, at the ElbowHop-fixed-kk total budget), and Hybrid-RRF (dashed), ±1\pm1 SEM bands.

As described in § 4.4, Dense sits at the higher fixed-kk budget and ElbowHop at the lower elbow budget. Two facts hold across all three pools. First, at a given budget ElbowHop achieves higher recall than the baselines, thus reaching a target recall with fewer tables. This advantage widens with pool size, although the budget required for 99% recall rises from ⟨k⟩≈10.4\langle k\rangle\approx10.4 on BIRD merged to ≈133.6\approx133.6 on Spider merged. Second, at a fixed budget kk the methods trace a common precision envelope, so none is systematically more precise. ElbowHop’s precision advantage appears at matched recall, because it reaches that recall with fewer tables. The collapse is tightest on the two BIRD pools; on Spider, ElbowHop curves fan out mildly by hop depth at matched kk, while Dense and Hybrid stay on the same envelope.

Taking a target recall of ≥99%\ge99\% as reference, Dense and Hybrid retrievers at their highest fixed-kk budget fall short of ElbowHop by roughly 1 to 6 recall points; the deficit is most pronounced on BIRD merged, where Hybrid lags by 6.2 points. The precision there is whatever the budget allows—about 35% on the small per-DB pool (⟨k⟩≈6.9\langle k\rangle\approx6.9), 26% on BIRD merged (⟨k⟩≈10.4\langle k\rangle\approx10.4), and only 2% on Spider merged, where reaching 99% recall costs ≈134\approx134 tables.

Discussion

At the default operating point, the elbow provides most of the gain: it adapts the budget to the question-specific score profile, whose variability increases with pool size (Figure 1). Its useful αtable\alpha_{\mathrm{table}} range remains stable across the evaluated pools, while the allocated budget changes with their scale. This conclusion is controlled for BIRD per-DB versus BIRD merged, which use the same schemas and questions; Spider merged instead provides a larger cross-corpus robustness check and does not isolate pool size from dataset composition. Additional matched-size subsets remain future work. The elbow does not estimate answer complexity: the correlation between kseedk_{\mathrm{seed}} and the number of gold tables is negligible (ρ≈0.05\rho\approx0.05–0.160.16). FK traversal provides a smaller aggregate contribution but improves recall for semantically weak bridge tables, especially with one hop and a tight budget (Figure 4). At larger budgets, dense retrieval increasingly recovers the same tables. We therefore recommend a selective elbow with thop=1t_{\mathrm{hop}} = 1. At a fixed output size, precision is largely budget-bound. ElbowHop’s advantage is therefore not higher precision at equal budget, but higher recall at equal budget, or equivalently, a smaller budget and higher precision at matched recall.

The present evaluation does not establish that this table-level advantage translates directly into higher SQL execution accuracy, since column selection and SQL generation are outside its scope. Nevertheless, at matched table recall, higher precision exposes the downstream generator to the same gold-table coverage with fewer irrelevant tables. Prior work shows that irrelevant or poorly positioned context can degrade model performance [1, 2, 3], which provides a plausible mechanism through which the smaller candidate sets produced by the elbow could reduce downstream generation errors. Smaller table sets also reduce the number of schema tokens passed to an LLM-based selector or generator. These remain expected downstream benefits rather than results demonstrated by the present experiments; an end-to-end evaluation of SQL validity and execution accuracy is left to future work.

Our current implementation completes the full retrieval pipeline in approximately 300–450 ms per query. This measurement includes query embedding, table and column retrieval, elbow detection, in-memory FK traversal, and retrieval of stored SQL examples. By contrast, the 0.3–6 ms measured for dense ranking covers only ranking over preloaded embeddings and metadata, with the query embedding already available. The two measurements therefore have different scopes and should not be interpreted as a controlled latency comparison or used to attribute the overhead to any individual component. The FK graph is loaded once from PostgreSQL and subsequently traversed in memory. A component-level latency breakdown is outside the scope of the present evaluation.

Another limitation is intrinsic to the elbow, which needs a sufficiently distinct knee to find. On short lists, or when similarities are uniformly high or low, the method may degrade toward returning most or all candidates, so extremely small or pathologically flat pools fall outside the regime where it helps. We did not separately label such flat-profile cases in the reported evaluation and therefore cannot provide a reliable estimate of their frequency. Potential diagnostic signals include a small similarity range s0−sn−1s_0 - s_{n-1}, a small maximum chord distance, or an elbow output approaching the full candidate pool. These quantities could support a fallback to a conservative fixed budget when the profile contains insufficient evidence for a distinct knee. However, defining and validating such a diagnostic threshold requires a dedicated analysis and is left to future work. Moreover, the chord-distance profile used by the detector is not guaranteed to have a unique maximum. Multiple local maxima may represent alternative transitions between the head and the tail of the ranking, and the global maximum is not necessarily the most operationally useful candidate if it occurs deep in the tail. The current method resolves tied global maxima conservatively by selecting the earliest one, but it does not explicitly compare distinct local maxima. Establishing regularity conditions under which the selected elbow is unique, and developing a principled criterion for choosing among multiple local maxima, remain directions for future work.

Conclusion

We presented ElbowHop, a table retriever combining an adaptive elbow cutoff with bidirectional FK traversal. Across pools of 3–13, 74, and 546 tables, the elbow reaches matched recall with substantially higher precision than a fixed budget on the larger pools, while a single FK hop improves recovery of bridge tables at tight budgets. The method is best used as a recall-oriented first stage before downstream pruning or generation. Future work includes end-to-end SQL evaluation, flat-profile fallback diagnostics, and selection among multiple elbow candidates.

Acknowledgments

This work is framed within the Project “AVANT” – Project no. IPCEI-CL_0000005 – Application protocol no. 108421 of 14/05/2024 – CUP B89J24002920005 – Grant decree no. 1322 of August 8, 2024 – financed by the European Union – NextGenerationEU (IPCEI Funding).

Declaration on Generative AI

During the preparation of this work, the authors used a large language model assistant for grammar, spelling, and rephrasing, then reviewed and edited the content and take full responsibility for it.

References

  1. [1]F. Shi, X. Chen, K. Misra, N. Scales, D. Dohan, E. H. Chi, N. Schärli, and D. Zhou, Large Language Models Can Be Easily Distracted by Irrelevant Context, in Proceedings of the 40th International Conference on Machine Learning (ICML), 2023, arXiv:2302.00093.arxiv.org/abs/2302.00093
  2. [2]N. F. Liu, K. Lin, J. Hewitt, A. Paranjape, M. Bevilacqua, F. Petroni, and P. Liang, Lost in the Middle: How Language Models Use Long Contexts, Transactions of the Association for Computational Linguistics (TACL), 12:157–173, 2024, arXiv:2307.03172.arxiv.org/abs/2307.03172
  3. [3]F. Cuconasu, G. Trappolini, F. Siciliano, S. Felice, C. Campagnano, Y. Maarek, N. Tonellotto, and F. Silvestri, The Power of Noise: Redefining Retrieval for RAG Systems, in Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2024, arXiv:2401.14887.DOI
  4. [4]B. Wang, C. Ren, J. Yang, X. Liang, J. Bai, L. Chai, Z. Yan, Q.-W. Zhang, D. Yin, X. Sun, and Z. Li, MAC-SQL: A Multi-Agent Collaborative Framework for Text-to-SQL, in Proceedings of COLING, 2025, arXiv:2312.11242.arxiv.org/abs/2312.11242
  5. [5]S. Talaei, M. Pourreza, Y.-C. Chang, A. Mirhoseini, and A. Saberi, CHESS: Contextual Harnessing for Efficient SQL Synthesis, arXiv preprint arXiv:2405.16755, 2024.arxiv.org/abs/2405.16755
  6. [6]M. Pourreza, H. Li, R. Sun, Y. Chung, S. Talaei, G. T. Kakkar, Y. Gan, A. Saberi, F. Ozcan, and S. O. Arik, CHASE-SQL: Multi-Path Reasoning and Preference Optimized Candidate Selection in Text-to-SQL, arXiv preprint arXiv:2410.01943, 2024.arxiv.org/abs/2410.01943
  7. [7]V. Satopaa, J. Albrecht, D. Irwin, and B. Raghavan, Finding a “Kneedle” in a Haystack: Detecting Knee Points in System Behavior, in Proceedings of the 31st International Conference on Distributed Computing Systems Workshops (ICDCSW), 2011.DOI
  8. [8]E. Rahm and P. A. Bernstein, A Survey of Approaches to Automatic Schema Matching, The VLDB Journal, 10(4):334–350, 2001.DOI
  9. [9]S. E. Robertson, S. Walker, S. Jones, M. Hancock-Beaulieu, and M. Gatford, Okapi at TREC-3, in NIST Special Publication SP 500-225: The Third Text REtrieval Conference (TREC-3), pp. 109–126, 1995.
  10. [10]G. V. Cormack, C. L. A. Clarke, and S. Buettcher, Reciprocal Rank Fusion Outperforms Condorcet and Individual Rank Learning Methods, in Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 758–759, 2009.DOI
  11. [11]M. Kothyari, D. Dhingra, S. Sarawagi, and S. Chakrabarti, CRUSH4SQL: Collective Retrieval Using Schema Hallucination For Text2SQL, in Proceedings of EMNLP, 2023, arXiv:2311.01173.arxiv.org/abs/2311.01173
  12. [12]B. Wang, R. Shin, X. Liu, O. Polozov, and M. Richardson, RAT-SQL: 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), 2020, arXiv:1911.04942.arxiv.org/abs/1911.04942
  13. [13]R. Cao, L. Chen, Z. Chen, Y. Zhao, S. Zhu, and K. Yu, LGESQL: Line Graph Enhanced Text-to-SQL Model with Mixed Local and Non-Local Relations, in Proceedings of ACL, 2021, arXiv:2106.01093.arxiv.org/abs/2106.01093
  14. [14]H. Li, J. Zhang, C. Li, and H. Chen, REDSQL: Decoupling Schema Linking and Skeleton Parsing for Text-to-SQL, in Proceedings of AAAI, 2023, arXiv:2302.05965.arxiv.org/abs/2302.05965
  15. [15]Y. Gao, Y. Liu, X. Li, X. Shi, Y. Zhu, Y. Wang, S. Li, W. Li, Y. Hong, Z. Luo, J. Gao, L. Mou, and Y. Li, XiYan-SQL: A Multi-Generator Ensemble Framework for Text-to-SQL, arXiv preprint arXiv:2411.08599, 2024.arxiv.org/abs/2411.08599
  16. [16]P. Lewis, E. Perez, A. Piktus, F. Petroni, V. Karpukhin, N. Goyal, H. Küttler, M. Lewis, W. Yih, T. Rocktäschel, S. Riedel, and D. Kiela, Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks, in NeurIPS, 2020, arXiv:2005.11401.arxiv.org/abs/2005.11401
  17. [17]D. Edge, H. Trinh, N. Cheng, J. Bradley, A. Chao, A. Mody, S. Truitt, and J. Larson, From Local to Global: A Graph RAG Approach to Query-Focused Summarization, arXiv preprint arXiv:2404.16130, 2024.arxiv.org/abs/2404.16130
  18. [18]Z. Guo, L. Xia, Y. Yu, T. Ao, and C. Huang, LightRAG: Simple and Fast Retrieval-Augmented Generation, arXiv preprint arXiv:2410.05779, 2024.arxiv.org/abs/2410.05779
  19. [19]B. J. Gutiérrez, Y. Shu, Y. Gu, M. Yasunaga, and Y. Su, HippoRAG: Neurobiologically Inspired Long-Term Memory for Large Language Models, in NeurIPS, 2024, arXiv:2405.14831.
  20. [20]J. Jiang, K. Zhou, Z. Dong, K. Ye, W. X. Zhao, and J.-R. Wen, StructGPT: A General Framework for Large Language Model to Reason over Structured Data, in Proceedings of EMNLP, 2023, arXiv:2305.09645.arxiv.org/abs/2305.09645
  21. [21]A. Asai, Z. Wu, Y. Wang, A. Sil, and H. Hajishirzi, Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflection, in Proceedings of ICLR, 2024, arXiv:2310.11511.arxiv.org/abs/2310.11511
  22. [22]Z. Jiang, F. F. Xu, L. Gao, Z. Sun, Q. Liu, J. Dwivedi-Yu, Y. Yang, J. Callan, and G. Neubig, Active Retrieval Augmented Generation, in Proceedings of EMNLP, 2023, arXiv:2305.06983.arxiv.org/abs/2305.06983
  23. [23]S. Jeong, J. Baek, S. Cho, S. J. Hwang, and J. C. Park, Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity, in Proceedings of NAACL, 2024, arXiv:2403.14403.arxiv.org/abs/2403.14403
  24. [24]J. Li, B. Hui, G. Qu, J. Yang, B. Li, B. Li, B. Wang, B. Qin, R. Cao, R. Geng, N. Huo, X. Zhou, C. Ma, G. Li, K. C. C. Chang, F. Huang, R. Cheng, and Y. Li, Can LLM Already Serve as a Database Interface? A Big Bench for Large-Scale Database Grounded Text-to-SQLs, in Advances in Neural Information Processing Systems (NeurIPS), 2023, arXiv:2305.03111.arxiv.org/abs/2305.03111
  25. [25]T. Yu, R. Zhang, K. Yang, M. Yasunaga, D. Wang, Z. Li, J. Ma, I. Li, Q. Yao, S. Roman, Z. Zhang, and D. Radev, Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task, in Proceedings of EMNLP, 2018, arXiv:1809.08887.arxiv.org/abs/1809.08887

Paper details

vlnc:W_v6nmh4xc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

a large language model assistant

View statement
Looking for related papers…
Contents