Beyond Linear LLM Invocation: An Efficient and Effective Semantic Filter Paradigm

This paper proposes Clustering-Sampling-Voting (CSV), a novel framework that significantly reduces the linear latency and token costs of semantic filtering in large language models by embedding tuples into semantic clusters, sampling subsets for evaluation, and inferring cluster-level labels through voting strategies, thereby achieving sublinear complexity with strong error guarantees.

The Gist

Imagine you are the manager of a massive library with 50,000 books (or reviews, or chat logs). You have a very specific, tricky question you need to ask every single book: "Is this story about a happy ending?"

In the past, to answer this, you had to hire a super-intelligent, but very expensive and slow, librarian (the Large Language Model, or LLM). You would hand them one book at a time, wait for them to read it, think about it, and give you a "Yes" or "No."

If you have 50,000 books, that means 50,000 expensive phone calls. It would take forever and cost a fortune. This is what the old systems did: a "linear scan," checking every single item one by one.

The Problem with the "Middleman"

Some recent attempts tried to be smarter. They hired a junior librarian (a smaller, cheaper AI) to do a quick skim of every book first.

• If the junior librarian was 100% sure, they'd say "Yes" or "No."
• If the junior librarian was unsure (maybe the score was "kind of yes"), they'd pass the book to the super-intelligent librarian for a final verdict.

The Catch: The junior librarian often wasn't very good at spotting the "unsure" books. They'd either pass everything to the expensive librarian (saving no money) or miss the tricky ones. It was like having a security guard who lets everyone through because they can't tell the difference between a tourist and a thief.

The New Solution: The "Book Club" Strategy (CSV)

The authors of this paper propose a brilliant new way called Clustering-Sampling-Voting (CSV). Instead of checking every book, they treat the library like a series of Book Clubs.

Here is how it works, step-by-step:

1. Clustering (Sorting the Books)

First, you don't read the books yet. You just look at their covers and summaries. You use a smart algorithm to group books that look and feel similar into piles (clusters).

• Analogy: You put all the "Romance Novels" in one pile, all the "Sci-Fi" in another, and all the "True Crime" in a third. You do this offline, so it's fast and cheap.

2. Sampling (The Taste Test)

Now, you don't ask the expensive librarian to read every book in the "Romance" pile. You just pick 5 random books from that pile and ask the expensive librarian to read those.

• Analogy: You ask the expert, "Read these 5 romance novels. Are they happy endings?"

3. Voting (The Group Decision)

This is the magic part.

• If the expert says 4 out of 5 of those romance books are happy endings, you assume ALL the other books in that "Romance" pile are happy endings too. You don't need to ask the expert again! You just stamp them all "Yes."
• If the expert is split (2 say Yes, 3 say No), the pile is too messy. You don't guess. You take that messy pile, break it down into smaller sub-groups, and try again.

Why is this a Game-Changer?

This method is like amortizing the cost. Instead of paying the expensive librarian 50,000 times, you might only pay them 200 times.

• Speed: It's 100 to 300 times faster.
• Cost: You save a massive amount of money (tokens).
• Accuracy: It's just as accurate as checking every single book because the "Book Clubs" are usually very pure (all the books in a pile really do belong together).

The "Safety Net"

What if a pile is weird? What if you have a pile of "Mystery Novels" that are actually a mix of happy and sad endings?
The system has a safety net. If the voting isn't clear (the "experts" in the sample disagree too much), the system automatically re-sorts that specific messy pile into smaller groups and tries again. If it's still too messy, it finally gives up and asks the expensive librarian to read those specific tricky books one by one.

The Bottom Line

The paper shows that you don't need to ask the "Genius AI" to read every single sentence in a massive database. By grouping similar items together and just asking the AI to check a few representatives, you can make a highly accurate guess for the whole group.

In short: Instead of interviewing every single candidate for a job, you interview a small, representative sample from each neighborhood. If the sample from "Downtown" is all hired, you hire everyone from Downtown without interviewing them individually. It's faster, cheaper, and surprisingly accurate.

Technical Summary

Here is a detailed technical summary of the paper "Beyond Linear LLM Invocation: An Efficient and Effective Semantic Filter Paradigm".

1. Problem Statement

Large Language Models (LLMs) are increasingly used for semantic query processing, particularly for semantic filters (analogous to relational selection operators). Given a table $T$ and a natural language predicate $e$, the goal is to identify all tuples $t \in T$ that satisfy $e$ based on LLM judgment.

The Core Challenge:

• Linear Complexity: Current state-of-the-art approaches (e.g., Lotus, BARGAIN) and baseline methods require a linear scan of the entire table, invoking the LLM for every single tuple. This results in prohibitive latency and token costs for large datasets.
• Limitations of Existing Optimizations:
  • Lotus uses a two-stage cascading approach (proxy model $\to$ oracle model). However, it still requires a linear pass through the proxy model for every tuple. Furthermore, if the proxy model's confidence scores are poorly calibrated or the thresholds are unstable, nearly all data may be forwarded to the expensive oracle model, negating efficiency gains.
  • BARGAIN similarly relies on proxy scores and linear scanning, suffering from the same overhead and the inherent overconfidence issues of neural network proxy scores.

The authors ask: Can we reduce the complexity of LLM invocations to sublinear while providing rigorous error guarantees?

2. Methodology: Clustering-Sampling-Voting (CSV)

The paper proposes CSV, a new paradigm that leverages the observation that semantically similar inputs tend to elicit consistent outputs from LLMs. Instead of processing tuples individually, CSV processes them in groups.

The Three-Phase Framework

1. Clustering (Offline):

   • Tuples are embedded into a vector space using a pre-trained encoder (e.g., E5-Large).
   • The embeddings are partitioned into $k$ clusters using K-means (or similar algorithms).
   • This step is query-agnostic and can be reused across different semantic predicates.

2. Sampling (Online):

   • For each cluster, a small subset of tuples is randomly sampled with a ratio $\xi$ (e.g., 0.5% to 5%).
   • The LLM is invoked only on these sampled tuples to determine their labels (True/False) regarding the predicate $e$.

3. Voting (Inference):

   • Based on the sampled results, the labels for the remaining tuples in the cluster are inferred without further LLM calls.
   • Two voting strategies are proposed:
     • UniVote (Uniform Voting): Aggregates labels uniformly. If the proportion of "True" in the sample exceeds an upper bound ($ub$), all remaining tuples are labeled True. If below a lower bound ($lb$), all are labeled False.
     • SimVote (Similarity-based Voting): Weights the vote of each sample based on its semantic similarity (embedding distance) to the target tuple. This provides robustness when clusters are not perfectly pure.

Handling Ambiguity (Re-clustering)

• If the voting confidence falls within the ambiguous interval $(lb, ub)$, the cluster is deemed "impure."
• CSV triggers a recursive re-clustering mechanism on these ambiguous subsets.
• This process repeats until the clusters are sufficiently pure or a maximum recursion depth is reached. If ambiguity persists, the framework falls back to direct linear LLM invocation for those specific tuples, ensuring an error bound.

Theoretical Guarantees

The authors provide a rigorous theoretical analysis using Bernstein Inequality to bound the error.

• They derive a relationship between the sample ratio ($\xi$) and the error tolerance ($\epsilon$).
• The analysis proves that with a sufficiently large $\xi$, the probability of the voting decision disagreeing with the true LLM output is bounded by $\max(lb + \epsilon, 1 - (ub - \epsilon))$ with high probability ($1 - 2l^n$).
• This allows users to tune $\xi$ to achieve a desired accuracy guarantee.

3. Key Contributions

1. Algorithm Development: Introduction of the CSV framework, which reduces LLM invocations from linear $O(|T|)$ to sublinear $O(\xi|T|)$ in the average case, while maintaining high accuracy.
2. Theoretical Analysis: A formal proof establishing error bounds for the voting strategies (UniVote and SimVote) based on sampling theory, explicitly connecting the sample ratio to the error guarantee.
3. Adaptive Mechanism: A recursive re-clustering strategy that ensures robustness across diverse datasets and predicates, preventing accuracy degradation in "hard" cases where initial clustering fails.
4. Experimental Validation: Comprehensive evaluation demonstrating significant efficiency gains without sacrificing effectiveness.

4. Experimental Results

The authors evaluated CSV on five real-world datasets (IMDB-Review, Codebase, Airdialogue, Twitter Hate Speech, FEVER) and 14 diverse queries.

• Efficiency:
  • LLM Calls: CSV reduced LLM calls by 1.28–355× compared to the linear baseline (Reference) and 1.81–355× compared to the state-of-the-art Lotus.
  • Latency & Tokens: Execution time and token consumption were reduced by 1 to 3 orders of magnitude. For example, on the RV-Q1 query, CSV completed in <13 seconds with ~170k tokens, whereas baselines took >1000 seconds with >20M tokens.
• Effectiveness:
  • Accuracy & F1: CSV achieved Accuracy and F1 scores comparable to the linear baseline (Reference) and significantly outperformed Lotus and BARGAIN in most scenarios.
  • Robustness: SimVote showed slight advantages over UniVote in noisy or ambiguous clusters (e.g., CB-Q2, AD-Q1).
  • Re-clustering Impact: Ablation studies showed that disabling re-clustering caused significant drops in F1 scores (up to 12%) for complex queries, validating the necessity of the recursive mechanism.
• Hyperparameters: The system is robust to variations in the number of clusters and sample ratio, provided the theoretical error bounds are respected.

5. Significance

This paper represents a paradigm shift in how LLMs are integrated into data processing systems:

• Breaking the Linear Barrier: It demonstrates that semantic filtering does not require a full linear scan of the data, challenging the assumption that LLMs must be invoked per-tuple.
• Cost-Effective AI Analytics: By drastically reducing token usage and latency, CSV makes large-scale semantic query processing economically viable for production systems.
• Theoretical Rigor: Unlike many heuristic optimizations, CSV provides mathematical guarantees on error rates, making it suitable for applications requiring reliability.
• Generalizability: The approach is compatible with various embedding models and LLM backbones, making it a versatile solution for the emerging field of LLM-powered database systems.

In summary, CSV transforms semantic filtering from a computationally expensive, linear operation into an efficient, sublinear process by leveraging semantic clustering and statistical sampling, offering a scalable solution for the next generation of AI-driven data analytics.