Calibrated Completeness for Verifiable Search Across Misaligned Schemas

When a company or hospital stores its data with an untrusted cloud provider, it can already demand proof that a query's answer is complete. Cryptographic structures such as Merkle hash trees (trees of hashes whose signed root lets a client detect any omitted or altered record) catch a "lazy" server that skips records to save work. Every such scheme, however, assumes that everyone agrees on what the query means: one fixed schema with fixed column names. Real data rarely looks like that. One source calls a field salary, another income, a third pay_empr, and the column mapping that connects them comes from a statistical matcher that is sometimes wrong. A query over such data is complete only relative to some mapping. A server that quietly ignores low-confidence correspondences can drop matching records, and no current proof would show it.

This note proposes to split the guarantee into two parts, each with its own kind of evidence. The first part is cryptographic: the server proves that it searched every source column the committed alignment selects for the query. The second part is statistical: a calibration procedure called conformal prediction, which turns matcher scores into a threshold with a stated error rate, guarantees that the selected set contains the true corresponding column with probability at least $1-\alpha$. The practical result is a single number a client can act on, such as "complete with 95% coverage of the true schema correspondences." The price of that number is the count of extra columns the server must scan and prove. This price shrinks as the matcher improves, so matcher quality and verification cost become one measurable trade-off.

Core Claim

Verifiable search over heterogeneous sources does not require verifying the schema matcher, which is impossible for a neural model at reasonable cost. It requires verifying that the matcher's committed output was used faithfully, plus a calibrated statement about how often that output misses the truth. The specific claim is that alignment-relative cryptographic completeness, combined with a conformally chosen threshold, can reach a target end-to-end record recall on real biomedical schema-matching benchmarks. It does so at a scan cost of a small number of columns per target attribute, while neither top-1 alignment nor unverified LLM mediation can provide a guarantee at all.

The closest prior work is Verifiable Keyword-Based Semantic Similarity Search on Social Data Outsourcing. It builds two Merkle trees, one over social posts and one over a fixed "is-a" keyword taxonomy (NameNet), so that a data provider must prove it visited every related keyword. That paper motivates the design: it shows completeness of semantic search is achievable once the semantic relation is committed. It also constrains the design, because it gets there only with a static, centrally signed, binary taxonomy from a single authority. We replace the taxonomy with a learned, scored, many-to-many alignment across independently authored sources, and we replace "related or not" with a calibrated threshold. Calibration is the missing piece. Without it, completeness relative to a mapping says nothing about completeness relative to the truth.

Research Program

The system has three layers.

Data owners. Each owner signs its own schema metadata, consisting of headers, descriptions, and types. Optionally it also signs a coarse per-column value sketch, such as a histogram or a value-type profile. The owner then builds a standard per-column Merkle tree over its records and publishes the signed root. Owners need not coordinate, which keeps the multi-authority autonomy stressed in Efficient Multi-Authority Attribute-Based Searchable Encryption Scheme with Blockchain Assistance for Cloud-Edge Coordination.

Alignment. A scorer assigns a score $s(a,c)$ to every pair of target attribute $a$ and source column $c$. This is a full score matrix, not a top-$k$ shortlist. Producing the full matrix removes the recall ceiling that Magneto: Combining Small and Large Language Models for Schema Matching identifies in retrieve-then-rerank pipelines, where a candidate dropped at retrieval can never be recovered. The scorer reuses the method of existing matchers. It can be Magneto's fine-tuned small model with large-model reranking, or the metadata-only language-model program from Bootstrapping Self-Improvement of Language Model Programs for Zero-Shot Schema Matching. For each attribute, the scores are sorted and committed in a Merkle tree, either by the client or by the party running the matcher.

The threshold comes from labeled correspondences held out by source. Let $\hat q_\alpha$ be the $\lfloor (n+1)\alpha \rfloor$-th smallest score among the $n$ true calibration pairs. The selected set is

$$S_\alpha(a) = \{\, c : s(a,c) \ge \hat q_\alpha \,\},$$

and split conformal prediction gives $\Pr[c^*(a) \in S_\alpha(a)] \ge 1-\alpha$ for the true column $c^*(a)$, provided calibration and test pairs are exchangeable.

Query time. For a query on attribute $a$, the server returns three things: the records from every column in $S_\alpha(a)$, each with its per-column Merkle completeness proof; and a boundary proof on the sorted score tree. The boundary proof consists of the entry just below the threshold and its authentication path. It shows that no column scoring above $\hat q_\alpha$ was left out. This is the same "adjacent boundary node" technique used in A Verifiable Fuzzy Keyword Search Scheme Over Encrypted Data, applied here to a ranked list of alignment scores instead of keywords. Pruning a low-but-above-threshold correspondence therefore breaks the proof.

Main risk: exchangeability. Conformal coverage holds only when calibration and test pairs are exchangeable. New sources may differ systematically from the calibration sources. We therefore always calibrate on whole sources held out from testing and report the coverage actually achieved under this source shift, not only the nominal $1-\alpha$. We will also test calibration conditioned on attribute type, such as categorical versus numeric, because Segment-driven Structural Induction and Semantic Alignment for Heterogeneous Tabular Representation shows that numeric columns behave differently.

Secondary question: value sketches and privacy. Signed coarse value sketches may shrink $S_\alpha$ without exposing row values. Matchmaker deliberately ignores rows for privacy reasons. NAVI shows value evidence disambiguates columns but needs plaintext. A sketch sits between the two.

Baselines

Naive reference. Top-1 alignment followed by a verifiable per-column query. This is cryptographically complete with respect to one column but carries no coverage guarantee. Its end-to-end recall is bounded by matcher accuracy@1. The strongest reported figure is Matchmaker's 62.2% accuracy@1 on MIMIC-OMOP and 70.2% on Synthea-OMOP, against ReMatch at 42.5% (Bootstrapping Self-Improvement of Language Model Programs for Zero-Shot Schema Matching). Our method beats this reference if it reaches coverage at or above $1-\alpha$ (for example 90–95%) on held-out sources.

Fixed top-$k$. The same matcher, with the server proving it searched the top $k$ candidates. This is the natural heuristic fix, and it isolates whether calibration matters or whether any widening of the candidate set suffices. For fairness, $k$ is tuned on the same calibration split that sets the conformal threshold. Both methods are compared at equal average scanned columns. We beat it if we achieve higher worst-case coverage, or a smaller scan at equal coverage, because adaptive set sizes give confident attributes one column and ambiguous attributes several.

Strongest unverified competitor. An LLM data agent mediating the heterogeneity at query time with no proofs. On DataSpace: Benchmarking Data Agents for Verifiable Analytics over Heterogeneous Workspaces, the best configuration reports 66.34% task accuracy, joins cost 10–20 points, and 18.5% of tasks are solved by no model. We run the same agent harness on the same tasks against a server that drops a controlled fraction of records. We beat it if we detect every drop while the agent's answers silently degrade.

Probabilistic sampling. The basic scheme of Verifiable Keyword-Based Semantic Similarity Search on Social Data Outsourcing, which samples through a public API. The paper reports 100% detection only once results exceed $10^4$–$10^5$ items. It gets the same sampling budget as our proof bytes.

Ablations. Two ablations isolate the key ingredients. The first uses uncalibrated raw thresholds, such as a score of at least 0.5. The second varies the scorer, comparing Magneto with Matchmaker and header-only input with header plus signed sketch, to show how matcher quality translates into scan cost.

Why not just…?

Why not just harmonize everything to a global schema before outsourcing? When this is affordable, it is the right answer, and our system reduces to it in the limit $\alpha \to 0$ with perfect labels. The evidence against it as a default is cost and autonomy. Matchmaker reports that mapping one medical database took experts 500 hours. Independently authored sources keep evolving, and each change would trigger re-harmonization and re-signing. Our experiments report the label budget at which conformal calibration reaches target coverage. That budget is directly comparable to full manual mapping.

Why not just let the client run the matcher locally on signed schemas and issue ordinary verifiable queries? This is the most serious alternative, and it is largely our system minus the score-tree proof. When the client can see all schemas and afford matching, the client-side variant is adopted directly, and the boundary proof becomes unnecessary. Even then, the calibration layer is what turns the result into a guarantee. Top-1 or top-$k$ local matching gives verified records for a mapping of unknown quality. We report both deployment modes and treat the server-side proof as needed only when the client is thin or the schemas are confidential.

Why not just use an LLM agent with self-checking? An agent cannot observe records a server never returned. The DataSpace numbers show that even honest-server accuracy is far from reliable. The record-drop experiment below measures directly whether agent answers reveal tampering.

Why not compile matching into a zero-knowledge circuit? Both ZKSQL: Verifiable and Efficient Query Evaluation with Zero-Knowledge Proofs and Zero-Knowledge Verifiable Graph Query Evaluation via Expansion-Centric Operator Decomposition gain their efficiency by avoiding monolithic circuits. ZKSQL, for example, reports up to 410× speedup from operator-level decomposition. Proving neural matcher inference inside such a circuit runs against that lesson, which is why we commit to the matcher's output rather than proving its computation.

Proposed Experiments

Alignment-level coverage. On MIMIC-OMOP, Synthea-OMOP, and GDC-SM (more than 700 target attributes), and on Valentine for breadth, we calibrate on held-out sources. We report achieved coverage against nominal $1-\alpha$ and mean $|S_\alpha|$ per attribute, separately for each scorer. No reported MRR for Magneto on GDC-SM was found on Lacuna, so we will measure it ourselves. GDC-SM also tests runtime: Magneto's zero-shot variant reports under 33 seconds, while ISResMat failed beyond 100 columns.

End-to-end verified retrieval. We attach per-column record Merkle trees to the benchmark sources, populated with synthetic rows that match the schemas. We simulate lazy servers of three kinds: those that drop record fractions, those that prune above-threshold columns, and those that return empty results. We report detection rate, verified record recall, proof size, and client verification time. Verification time is compared with the under-one-second figure in the social-data paper.

Analytics stress test. We run selected DataSpace tasks requiring cross-source joins against an honest and a lazy server, comparing the unverified agent with an agent constrained to our verified retrieval layer.

Decisive checks. The proposal is supported if three things hold together on held-out sources: achieved coverage stays within a few points of $1-\alpha$, conformal sets are strictly smaller than tuned top-$k$ at equal coverage, and every injected omission is detected. It fails if source shift breaks coverage badly enough that no feasible label budget fixes it. In that case the honest conclusion is that per-source calibration, essentially partial harmonization, is unavoidable.