Estimating Semantic Operators

Core idea: lightweight language models.

Evaluating individual data points with a large language model is expensive. Instead, build semantic statistics and use smaller models for semantic inference.

Cardinality estimation means estimating the number of data points that satisfy a semantic query without executing the query itself.

1. Offline Phase: Constructing the Semantic Catalog

Background Concepts

For example, sports events and sports teams are subdimensions of sports.

Workflow Overview

Phrase extraction → coarse-grained semantic dimension identification by an LLM → semantic catalog.

A. Keyword Extraction

The LLM identifies semantic dimensions, analyzes key phrases, and prioritizes them by frequency.

Implementation: Use Top2Vec and construct a priority queue initialized with the root node and frequencies. Iteratively remove the highest-frequency element from the queue.

B. Distribution Estimation

Use an LLM to label a small dataset, then train a lightweight classifier.

Rather than directly analyzing labels for individual data points, determine whether pairs of data points share a value along a particular semantic dimension.

The workflow is:

1. Construct a k-nearest-neighbor (KNN) graph.
2. Apply a small model, such as a graph neural network (GNN).
3. Form clusters of data points that may share the same dimension value.

2. Offline Phase: Building the Semantic Data Index

For each leaf node, identify dimension values and record which data points contain the relevant information.

Background Concepts

A. Dimension Nodes

Dimension classification: Train a binary classifier on document embeddings using an LLM-labeled subset. Use it to partition the data-point collection into smaller subsets.

B. Dimension-Value Nodes

Core idea: Identify internal clustering relationships, cluster data points using pairwise relationships, and use an LLM to check labels.

1. Compute semantic embeddings and construct a KNN graph, retaining semantically related pairs.

   The stated time-complexity reduction is:

   $$O(n^2) \rightarrow O(nk)$$

2. Use LLM-labeled samples to train a classifier, treating pairs with the same tag as positive examples. Predict the relationships between connected data points in the KNN graph and remove edges that do not match.

3. Assign a cluster's most frequent label as its approximate label. If no labels are available, ask the LLM to determine one.

C. Decision Model

Large models are expensive to run. Instead, use a model that takes a data point and a query as input and returns a binary decision.

How can enough training data be obtained?

Select two nodes and combine them through a compositional operation to create a new query. Generate positive and negative examples from the resulting query, then train the model.

3. Online Phase: Semantic Cardinality Queries

A. Locating Relevant Data

Key idea: Convert a natural-language query into structured constraints.

For example, a query for documents about the results of competitions held in the United States yields the constraint Country = USA.

Classify nodes into three categories:

1. Fully matching nodes: Their contents satisfy the query.
2. Candidate nodes: Their semantics are related to the query, but constraint satisfaction still requires verification.
3. Nonmatching nodes: Their contents do not satisfy the query.

B. Stratified Importance Sampling

Step 1: Construct Strata

Partition the collection into strata that together cover the complete dataset. A stratum is a nonoverlapping subset whose members share common characteristics.

The semantic index expands each candidate node down to its leaf nodes to construct these strata.

For example, the candidate node sports event expands to the leaf nodes NBA and Olympics. To avoid excessively small strata, any stratum below a predefined size threshold is merged upward with its siblings until it reaches a sufficient sample size.

Step 2: Deduplicate

Remove data points that have already been classified as satisfying or not satisfying the query. Where a data point belongs to multiple nodes, retain its membership in the node with the highest similarity.

Step 3: Sample

For each stratum $i$, calculate the importance weight of data point $j$ as:

Here, $s_{ij}$ is the similarity between the query embedding and the data-point embedding, and $N_i$ is the size of stratum $i$. Sample according to $w_{ij}$.

Why stratify? Collapsing hundreds of dimensions into a single score ignores the diversity of semantic dimensions and can introduce query-estimation errors.