Same Query, Different Answer: The Run-to-Run Variance Problem in Semantic Query Engines

Semantic Query Engines are emerging as the bridge between large language models and structured data. These systems use LLMs to evaluate data row by row — determining whether a piece of text meets a condition, or extracting specific fields from a table. But a long-overlooked problem has come to the surface: running the same query twice can produce different answers. A study based on 1.2 million model calls systematically quantifies this run-to-run variance, raising serious questions about the reliability of existing benchmarks.

Temperature Zero Doesn't Guarantee Determinism

Intuitively, when an LLM's sampling temperature is set to 0, its output should be deterministic. But after re-running text and table workloads from three benchmarks — SemBench, LRO-Bench, and UDA-Bench — and logging all 1.2 million model calls, the research team found that even at temperature 0, between 0.07% and 10.2% of rows change their operator output across five executions, depending on the model. On one particular task, that figure reached 24.0%.

This means the notion of "deterministic inference" simply doesn't hold up in engineering practice. Non-determinism in hardware floating-point arithmetic, concurrent scheduling, and implementation details on the model serving side can all cause the same input to produce different token distributions. For semantic queries that judge data row by row, even a low per-row flip probability can have a non-trivial cumulative effect.

The sampling temperature is the core parameter controlling the randomness of a language model's output. At temperature = 0, the model selects the highest-probability token at each decoding step (i.e., greedy decoding), which should theoretically produce identical outputs for the same input. In practice, however, this theoretical guarantee has several cracks: modern GPU floating-point operations are not associative under parallelization, meaning different batch sizes or concurrency levels can cause subtle differences in intermediate results; continuous batching and PagedAttention mechanisms introduced by model serving frameworks (such as vLLM and TensorRT-LLM) to improve throughput further cause a single request's computation path to vary with system load; and some cloud APIs reinterpret or modify the semantics of temperature on the server side. When these factors combine, "determinism" becomes only a statistical "probably the same" rather than a mathematical "necessarily the same."

How Query Plans Amplify Errors Exponentially

The truly thorny problem lies in how errors propagate. The research uses a possible-worlds model to characterize this phenomenon: query plans amplify these variations exponentially with respect to the number of rows involved in an answer.

On UDA-Bench, only a few percentage points of extracted values changed — yet approximately two-thirds of final answers changed. The reason is straightforward: a final answer typically aggregates judgments across many rows, and if any single row flips, the entire answer may differ. Small instabilities at the row level are dramatically amplified into large swings at the answer level by aggregation operators. This is a critical vulnerability for any analytical query that relies on multi-row aggregation.

The possible worlds model is a classic framework from database uncertainty theory, originally used to describe probabilistic databases containing uncertain data. Its core idea: when each fact in a database exists with some probability, the entire database corresponds to an exponential number of "possible deterministic worlds," and query results must be computed as expectations or distributions over all possible worlds. Applying this framework to semantic query processing, each row's model judgment becomes a probabilistic event — the model outputs "satisfies condition" with probability p and "does not satisfy" with probability 1-p. For queries that aggregate n rows (such as COUNT, SUM, or questions requiring results from multiple rows), the stability of the final answer is determined by the joint distribution of all participating rows. Even if each row has only a 1% flip probability, the probability that at least one row in 100 flips is already close to 63% — this is the mathematical root of why small per-row changes on UDA-Bench lead to the majority of final answers changing.

Benchmark Conclusions May Not Hold Up

The most impactful finding of this research is its direct challenge to the credibility of existing benchmarks.

Among SemBench's published results, 21% of text results vary in quality across different executions — including engines whose query plans are themselves deterministic. In other words, the conclusion that "engine A outperforms engine B" reported in a paper may simply be an artifact of a single execution.

The study further points out that several system comparison conclusions for individual queries, and 16 out of 28 tests in LRO-Bench's implementation recommendations, cannot be definitively "decided" by the actual number of executions the benchmark was run. These conclusions fall within statistical noise and could be reversed by a single re-run. For the field as a whole, this means a large body of published performance rankings deserves fresh scrutiny.

Which Rows Will Change Is Predictable

The changes are not entirely random. The research reveals several clear patterns:

• Rows that change are exactly those where different models disagree with each other. Disagreement between models on the same row corresponds precisely to the rows where a single model's own output is unstable.
• The disagreement frequency of repeated requests within a single execution is comparable to disagreement frequency across executions. This shows that uncertainty is an intrinsic property of model behavior, not a coincidental artifact of cross-session variation.
• Decision margin or reasoning length can predict which rows will change. The more a model "hesitates" (low confidence, long reasoning chain), the higher the likelihood that row will flip.

This finding has significant practical value — it means systems can proactively identify high-risk rows and apply targeted stabilization measures to them.

The concept of decision margin comes from interpretability research on classification models: in binary classification, samples closer to the decision boundary are harder for the model to classify, have lower prediction confidence, and are more likely to flip due to small perturbations in the input. In LLM judgments that use Chain-of-Thought or reasoning steps, reasoning chain length serves as a proxy for distance from the decision boundary — when a model requires many reasoning steps to reach a conclusion, it often means the row's semantic features fall in the ambiguous zone of the evaluation criteria. The predictability of both signals provides an important engineering interface: systems can automatically trigger multiple re-runs or escalate to a stronger model for low-confidence rows after the first execution, while reusing single-run results for high-confidence rows — achieving a dynamic trade-off between accuracy and computational cost.

Voting and Cascading: Mitigation, Not a Cure

A common engineering approach to variance is voting — running multiple executions and taking the majority result. The research confirms that voting does reduce variance, but cannot eliminate it. Another approach is calibrated cascading, which, while maintaining its own guarantees, still returns row sets that can vary.

In other words, no single technique can completely eliminate run-to-run variance. The viable path is a combination strategy: use decision margins to identify high-risk rows, vote on critical rows, and honestly disclose uncertainty when reporting results.

Implications for Benchmark and Engine Design

Based on these findings, the research offers clear recommendations for two groups:

For benchmark reporting norms: Rather than reporting results from a single or handful of temperature-0 executions, benchmarks should run multiple times and report variance intervals, explicitly marking which comparison conclusions remain statistically undecided. Otherwise, leaderboard "wins" may be meaningless.

For engine design: Engines should treat uncertainty as a first-class citizen, using signals like decision margin and reasoning length to identify unstable rows, and balancing cost against stability through mechanisms like voting and cascading.

The significance of this work extends beyond specific numbers. It reminds the entire semantic data processing community: when we use LLMs as database operators, we must confront their probabilistic nature head-on. Determinism is not free — and the rigor of evaluation depends on honest quantification of that uncertainty.