Featurized-Decomposition Join: Low-Cost Semantic Joins with Guarantees

Sepanta Zeighami, Shreya Shankar, Aditya G. ParameswaranarXiv 2025 · DOI · arXiv

Abstract

Performing semantic joins on large text datasets using Large Language Models (LLMs) is powerful but computationally expensive due to the $O(n^2)$ comparisons required. This paper introduces Featurized-Decomposition Join (FDJ), a method that automatically extracts key features from text and constructs inexpensive logical rules to filter out non-matching pairs. FDJ reduces LLM costs by up to 10x compared to state-of-the-art embedding cascades while providing strict statistical guarantees on output quality.

Introduction: The Cost of Semantic Joins

A "semantic join" involves linking two tables based on a natural language condition evaluated by an LLM—for instance, determining if two distinct police reports describe the same incident. A naive implementation requires comparing every row in Table A with every row in Table B, leading to a massive number of expensive LLM calls.

Example of a semantic join predicate and its featurized decomposition for police records.

Existing solutions often rely on model cascades, which use text embeddings to compute cosine similarity. If similarity is low, the pair is discarded; otherwise, it is sent to the LLM. However, embeddings are often "lossy" and fail to capture specific logical nuances in long or complex documents. This leads to unreliable proxy scores, forcing the system to fall back to expensive LLM calls for most pairs and negating potential cost savings.

Methods: Featurized-Decomposition Join (FDJ)

Instead of monolithic embeddings, FDJ breaks the join condition into a featurized decomposition—a logical expression in Conjunctive Normal Form (CNF) composed of smaller, cheaper checks (e.g., checking if incident dates differ by less than two days).

The FDJ pipeline: 1) Create featurized decomposition, 2) Estimate join conditions, and 3) Refine positives with an LLM.

The FDJ pipeline consists of three primary stages:

  1. Candidate Generation: FDJ uses an LLM to iteratively propose feature extraction functions (Python code or small prompts) and distance metrics. It employs a feedback loop based on "cost to cover," identifying positive pairs that current features fail to distinguish and generating new features to handle these edge cases.
  2. Logical Scaffold Formulation: These features are combined into a logical "scaffold" designed to minimize the false positive rate.
  3. Threshold Setting with Guarantees: To prevent filtering true matches, FDJ sets distance thresholds using a novel high-dimensional statistical bound. This ensures a user-defined recall target (e.g., 90%) with a mathematically bounded probability of failure.

Evaluation and Results

The authors evaluated FDJ across six diverse datasets, including legal citations, medical reactions (BioDEX), product listings, and police records.

Key results include:

  • Significant Cost Savings: FDJ achieved up to a 10x cost reduction over BARGAIN (the state-of-the-art guaranteed cascade method) and was up to 8x cheaper than an "optimal cascade" oracle baseline.
  • Performance on Complex Data: On the Movies dataset, FDJ reduced costs by 91% compared to BARGAIN. On legal Citations, it achieved a 76% reduction.
  • Reliable Quality: FDJ consistently maintained strict quality targets (e.g., 90% recall). In contrast, prior methods like LOTUS occasionally failed to meet recall targets due to a lack of finite-sample guarantees.

Discussion and Insights

The core insight of FDJ is that embeddings are insufficient for complex logic. Explicit feature extraction is more robust to text length and complexity. Furthermore, LLMs are highly effective at writing rules rather than just evaluating them. By generating extraction code upfront, FDJ amortizes the high LLM cost over the entire $O(n^2)$ cross-product.

While highly effective, FDJ has limitations. In classification tasks with complex mappings (e.g., BioDEX), cost savings were less dramatic. Additionally, the statistical guarantees require a sufficient sample of positive pairs (approximately 200 in experiments) to function reliably. Future work may explore combining FDJ with prompt batching to further enhance efficiency.

Summary updated

Abstract

Large Language Models (LLMs) are being increasingly used within data systems to process large datasets with text fields. A broad class of such tasks involves a semantic join-joining two tables based on a natural language predicate per pair of tuples, evaluated using an LLM. Semantic joins generalize tasks such as entity matching and record categorization, as well as more complex text understanding tasks. A naive implementation is expensive as it requires invoking an LLM for every pair of rows in the cross product. Existing approaches mitigate this cost by first applying embedding-based semantic similarity to filter candidate pairs, deferring to an LLM only when similarity scores are deemed inconclusive. However, these methods yield limited gains in practice, since semantic similarity may not reliably predict the join outcome. We propose Featurized-Decomposition Join (FDJ for short), a novel approach for performing semantic joins that significantly reduces cost while preserving quality. FDJ automatically extracts features and combines them into a logical expression in conjunctive normal form that we call a featurized decomposition to effectively prune out non-matching pairs. A featurized decomposition extracts key information from text records and performs inexpensive comparisons on the extracted features. We show how to use LLMs to automatically extract reliable features and compose them into logical expressions while providing statistical guarantees on the output result-an inherently challenging problem due to dependencies among features. Experiments on real-world datasets show up to 10 times reduction in cost compared with the state-of-the-art while providing the same quality guarantees.
BibTeX
@misc{zeighami2025featurized,
  author = {Sepanta Zeighami and Shreya Shankar and Aditya G. Parameswaran},
  title = {{Featurized-Decomposition Join: Low-Cost Semantic Joins with Guarantees}},
  year = {2025},
  eprint = {2512.05399},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.05399},
}
Figure