Part II · Five Failures · Chapter 2

Completeness

When your result set is a sample pretending to be a census, every aggregate downstream is a guess wearing the costume of a fact.

The first lie in the $7.2M answer was “12 accounts.” There were not 12 accounts. There were 12 accounts in the top 50 chunks returned by a vector search configured by whoever wrote the tool description. The real number might be 40. It might be 12. The retrieval gives you no way to know.

This chapter builds the annotation that prevents this from happening silently: a completeness type that travels with every intermediate result, a composition rule that propagates it through joins and unions, and a gate that converts aggregation over incomplete data from a confident number into a labeled bound.

2.1 The problem: COUNT(*) over a ranking

Here is the pipeline that produced the lie:

chunks = vector_search(
    query="churn risk, non-renewal, evaluating competitors",
    filter={"created_at": {"gte": "2026-05-01"}},
    k=50,
)
accounts = {c.account_id for c in chunks}   # 12 accounts

Then the agent says “12 accounts.”

Relational algebra assumes sets are complete, unordered, and stable. Vector search returns a result that is incomplete by construction, ordered by a score, and unstable across index updates. Compose them without saying so and you get COUNT(*) over a truncated ranking, reported as a count.

Elastic’s own kNN documentation says the quiet part directly: aggregations are computed over the top k nearest documents, not the matching set. That is a correct and honest description of the behavior. It is also a loaded gun pointed at every agent that treats a vector store as a database.

Why raising k doesn’t fix it

The obvious fix — “raise k” — doesn’t work. There is no k at which the result becomes exact, because ANN recall is below 1 and the index lags the source. Raising k makes the lie smaller and no less a lie. Worse, it makes the lie harder to notice, because the number stops moving between runs and starts to look stable.

A 2026 paper on vector search inside relational engines (“To GPU or Not to GPU,” arXiv 2605.15957) builds a TPC-H variant mixing ANN with relational operators and reports relative revenue error for a SUM over an approximate retrieval — targeting ≤1% relative error at ≥95% per-query recall. That is the right instinct: treat approximation error as a quality knob. But note the framing — nobody downstream is told that the number they’re reading has a 1% error bar, and no LLM narrating it will invent one.

2.2 The completeness lattice

Every result set in our system carries a completeness annotation drawn from this ordered set:

\[ \texttt{exact} \sqsupset \texttt{sampled} \sqsupset \texttt{top\_k}(k) \sqsupset \texttt{truncated} \sqsupset \texttt{unknown} \]

The ordering means: exact is the strongest guarantee (every qualifying tuple is present), and unknown is the weakest (we have no idea what fraction of the true result set is here).

Level	Meaning	Example source
exact	The result is the complete answer to the predicate	Warehouse table with no filters beyond the query
sampled	A random subset with known sampling rate	Stratified sample table, approximate count-distinct
top_k(k)	The k highest-scored items under some ranking	Vector search, API with pagination limit
truncated	Incomplete for operational reasons (timeout, rate limit)	API that hit a rate limit mid-page
unknown	No completeness guarantee available	Third-party data dump with no freshness SLA

The meet rule for completeness

When two result sets are composed (joined, unioned, intersected), the output’s completeness is the meet — the weaker of the two inputs:

\[ \text{completeness}(A \bowtie B) = \text{completeness}(A) \sqcap \text{completeness}(B) \]

In concrete terms:

• exact ⋈ top_k(50) = top_k(50)
• top_k(50) ∪ top_k(100) = top_k(50) (the weaker bound governs)
• sampled(0.1) ⋈ exact = sampled(0.1)
• Anything ⋈ unknown = unknown

This is the single most valuable rule in the design because it prevents an exact warehouse fact from being laundered into exactness by association with an approximate retrieval result.

2.3 Aggregation gates

The critical design decision: what happens when you aggregate over an incomplete result?

There are three options:

1. Allow silently (current state of every agent framework). Produces the $7.2M lie.
2. Reject (compile error). Safe but annoying — many useful queries become unanswerable.
3. Allow with a labeled bound. The aggregation runs, but the result carries a qualifier.

Option 3 is the right default. Here is what it produces:

// Before: the agent reports a bare number
{ "value": 12, "type": "count" }

// After: the result carries its basis
{
  "value": 12,
  "type": "count",
  "completeness": "top_k(50)",
  "bound": "lower",
  "qualifier": "at least 12, from the top 50 matching conversations"
}

The aggregation function determines the bound direction:

Aggregate	Over incomplete data	Bound type
COUNT	Undercounts (missing tuples not counted)	Lower bound
SUM (positive values)	Undercounts	Lower bound
MIN	True minimum may be in the missing tuples	Upper bound on the minimum
MAX	True maximum may be in the missing tuples	Lower bound on the maximum
AVG	Direction unknown without distributional assumptions	No bound — reject or flag
COUNT DISTINCT	Undercounts	Lower bound

AVG is the dangerous case. A COUNT over incomplete data is at least honest about its direction — the true count can only be higher. But an average over a top-k set is biased in the direction of whatever the ranking correlates with, and you cannot bound the error without knowing the distribution of the missing values. The safe choice is to reject AVG over non-exact data entirely, or require the caller to explicitly opt in with an acknowledgment that the result is biased.

2.4 Implementation

The completeness type and its operations in Python:

from enum import IntEnum
from dataclasses import dataclass
from typing import Optional

class CompletenessLevel(IntEnum):
    EXACT = 4
    SAMPLED = 3
    TOP_K = 2
    TRUNCATED = 1
    UNKNOWN = 0

@dataclass(frozen=True)
class Completeness:
    level: CompletenessLevel
    k: Optional[int] = None          # only for TOP_K
    sample_rate: Optional[float] = None  # only for SAMPLED

    @staticmethod
    def exact():
        return Completeness(CompletenessLevel.EXACT)

    @staticmethod
    def top_k(k: int):
        return Completeness(CompletenessLevel.TOP_K, k=k)

    @staticmethod
    def sampled(rate: float):
        return Completeness(CompletenessLevel.SAMPLED, sample_rate=rate)

    def meet(self, other: "Completeness") -> "Completeness":
        """The weaker of two completeness guarantees."""
        if self.level <= other.level:
            return self
        return other

    def allows_aggregation(self, agg: str) -> bool:
        """Whether this completeness level permits the given aggregate."""
        if self.level == CompletenessLevel.EXACT:
            return True
        if self.level == CompletenessLevel.UNKNOWN:
            return False
        # AVG over incomplete data is rejected
        if agg in ("avg", "median", "percentile"):
            return False
        return True  # COUNT, SUM, MIN, MAX allowed with bounds

    def bound_direction(self, agg: str) -> Optional[str]:
        """For non-exact data, what bound does this aggregate give?"""
        if self.level == CompletenessLevel.EXACT:
            return None  # exact, no bound needed
        if agg in ("count", "count_distinct", "sum", "max"):
            return "lower"
        if agg == "min":
            return "upper"
        return None  # no bound determinable

The key design decisions:

• Completeness is a value object (frozen dataclass). It is immutable and travels with the result.
• The meet operation is the core composition rule. Every join, union, or intersection calls it.
• allows_aggregation is the gate. It returns false for operations that would produce unbounded errors.
• bound_direction tells the narrator which qualifier to use (“at least” vs. “at most”).

2.5 The stopping-condition problem

A deeper issue lurks behind the top-k truncation: agentic retrievers have no principled stopping condition. They cannot tell when they’re done, because “done” is not a signal the retrieval interface exposes.

A recent paper on structured RAG for aggregative questions (arXiv 2511.08505) puts it plainly: missing a single piece of evidence produces an incomplete answer, and there is no way to detect the miss from within the retrieval loop.

Three approaches, in increasing order of engineering cost:

Approach 1: Declare the bound and move on

Accept that the retrieval is incomplete. Report the bound. This is what our annotation system does. It is cheap, honest, and often sufficient — “at least 12 accounts” is a useful answer for many business questions.

Approach 2: Recall estimation

Run a second, independent retrieval path (different query formulation, keyword search, or a sample of the full corpus) and estimate what fraction of the true result set the primary retrieval captured. This gives a confidence interval on the bound rather than a bare lower bound. It doubles the retrieval cost but can be cached.

Approach 3: Exhaustive fallback

When the aggregation is critical (financial reporting, compliance), bypass the ANN index entirely and run an exact predicate over the full corpus. This is the equivalent of SELECT ... WHERE text ILIKE '%churn%' — exact but coarse. The completeness annotation lets you choose when to pay this cost: only when the aggregate matters, only when the bound is too loose, only when the caller hasn’t opted into approximation.

2.6 When completeness interacts with the other annotations

Completeness does not exist in isolation. Two interactions matter now and become formal in Chapter 6:

Completeness × Authorization: A result can be incomplete because of retrieval approximation (this chapter) or because of access control filtering (Chapter 5). Both produce the same symptom — missing tuples — but have different fix paths. The completeness annotation tracks the retrieval cause; the guarantee annotation tracks the authorization cause. When both apply, the result carries both, and the most restrictive one governs.

Completeness × Grain: A top-k retrieval at the chunk grain that is de-duplicated to the account grain changes the effective k. If 50 chunks map to 12 accounts, the effective coverage at the account grain is determined by whatever fraction of all accounts had at least one chunk in the top 50. This is unknowable without corpus statistics. The conservative choice: the completeness annotation does not improve through grain coarsening. top_k(50) at chunk grain remains top_k(50) after de-duplication to accounts.

---

Exercises

1. Extend the Completeness class to handle the sampled case properly: when two sampled results are joined (inner join on a shared key), the output sample rate is approximately the product of the two rates (under independence). Implement this in the meet method as a special case when both inputs are sampled.
2. Build a QueryPlan tree where each node is an operator (Scan, Filter, Join, Aggregate) and each leaf carries a Completeness. Implement a propagate() method that walks the tree bottom-up and annotates every node. At Aggregate nodes, emit a warning if the input completeness is not exact, and include the bound direction in the annotation.

1. Your organization uses a re-ranker after the initial ANN retrieval. The re-ranker takes the top-200 ANN results and returns a re-scored top-50. Does the re-ranker improve, worsen, or leave unchanged the completeness annotation? What if the re-ranker can add results from a secondary index that the primary ANN missed? Design the annotation semantics for a two-stage retrieval with augmentation.
2. Consider a streaming data source: new documents arrive continuously, and the vector index is updated asynchronously (lag of 5–30 minutes). How should the completeness annotation account for temporal incompleteness? Design a completeness_with_freshness type that combines the spatial (top-k) and temporal (lag) dimensions of incompleteness.

---