Same Query, Different Answer: Run-to-Run Variance in Semantic Query Processing

Oktie Hassanzadeh, Dharmashankar SubramanianarXiv 2026 · arXiv

TL;DR

Even at "temperature 0," Large Language Models (LLMs) are not deterministic oracles, leading to significant run-to-run variance in semantic query processing. This paper demonstrates that query plans exponentially amplify small row-level fluctuations, often rendering benchmark conclusions and system optimizations unstable unless specific operator outputs are recorded.

What Problem Does This Paper Address?

Semantic query engines integrate LLMs directly into database operations, using them as "operators" to filter, join, or aggregate data based on natural language instructions. A common assumption among researchers and developers is that running these models at temperature 0—using greedy decoding—makes them deterministic.

However, hidden sources of non-determinism, such as hardware-level batching effects in inference servers, cause LLMs to return different answers for identical prompts. This paper quantifies how pervasive this variance is and, crucially, how it propagates through relational query plans. If a single row's classification "flips" between runs, how does that affect a complex join or a count? The authors argue that current benchmarking practices are often insufficient to settle system comparisons because they ignore this inherent instability.

Methods

The authors performed an extensive empirical study by re-executing three major semantic query benchmarks across eight different model deployments (including Llama-3, Granite, Qwen, GPT-4o, and Claude). They logged every one of the 1.2 million model calls to track variance at the individual item level.

Key methodological contributions include:

  • Possible-Worlds Model: A theoretical framework based on probabilistic databases to predict how row-level disagreement propagates to final query answers.
  • Item Flip Rate & Answer Reproduction: New metrics to measure how often individual operator outputs change and how often entire query answers remain identical across runs.
  • Remedy Replay: Testing the effectiveness of common strategies like voting (running the same query multiple times and taking the majority) and calibrated cascades.

Datasets

The study re-analyzes and re-executes three prominent benchmarks:

  • SemBench: A benchmark for semantic query engines (like LOTUS and Palimpzest) focusing on text and tabular data.
  • LRO-Bench: A suite that classifies and evaluates LLM-enhanced relational operators across 27 different databases.
  • UDA-Bench: A benchmark for unstructured data analysis where SQL queries are executed over attributes extracted from documents by an LLM.

Key Insights and Ideas

  • Exponential Amplification: Query plans act as amplifiers for non-determinism. For operations that expose many rows (like a full join or a map returning all rows), the probability of getting the exact same answer twice decays exponentially as the number of items increases.
  • Variance is Ambiguity: Non-determinism isn't just random noise; it concentrates on "contested" items. These are rows where the model is "unsure" (low decision margin) or where different models also tend to disagree. A single execution's reasoning length or log-probability gap can actually predict which items are likely to change in a future run.
  • The Deployment is Part of the Result: Running the same model weights on different inference stacks (e.g., a managed API vs. a local vLLM instance) can lead to different answers and different levels of variance. Figure 1 shows how different deployments return different counts for the same query. Figure 1: Variance in counts returned by Movie Q3
  • Quality Metrics are Deceptive: Standard metrics like F1 or accuracy can remain stable even when the underlying data returned by a query changes significantly. This creates a false sense of reproducibility.
Figure 1: The count that Movie Q3 returns in each execution at temperature 0, per deployment. Marker labels give the number of executions that returned the count; grey deploy- ments returned one count in every execution.

Key Results

  • Row-Level Volatility: At temperature 0, between 0.07% and 10.2% of rows changed their output over five executions. For certain tasks, this "flip rate" reached as high as 24%.
  • Operator Sensitivity: Graded judgments (like 1–5 star ratings) and free-text extractions are significantly more volatile than simple Boolean filters. Figure 3: Item flip rate by operator type
  • Benchmark Instability: In published SemBench results, 21% of text-based queries changed their quality score between executions. The authors found that many system comparisons required more than the standard five executions to be statistically significant.
  • Predictable Decay: The "possible-worlds" model accurately predicts answer reproduction. As the expected number of disagreements ($x$) grows, the chance of the full answer reproducing follows a sharp $e^{-x}$ curve. Figure 4: Answer reproduction vs expected disagreements
Figure 3: Item flip rate over five executions by the output type of the operator, pooled over SemBench queries (log scale; zero shown at 0.01%).
Figure 4: Left: item flip rate of gpt-oss-120B against the number of executions observed, by output type (exact expectation over subsets of the ten executions). Right: answer reproduction against the expected number of items on which two executions disagree, one point per SemBench query (joins included) and deployment. Filled points are answers that expose every item, for which the possible-worlds model predicts 𝑅≈𝑒−𝑥; hollow points are answers under LIMIT, an aggregate, or a ranking.

Limitations and Future Work

  • Scope: The study focused on text and tabular data. The impact of variance in multi-modal semantic queries (involving images or audio) remains an open question.
  • Reasoning Models: Due to API limitations, the authors could not fully disentangle the effects of internal "reasoning" steps from the base model's non-determinism.
  • Remedies: While voting reduces variance, it is costly and doesn't eliminate it. The authors suggest that the only true way to ensure stable, reproducible answers in production systems is to record and store the specific operator outputs that generated a query result, effectively treating them as materialized views. Future work could explore more cost-effective ways to flag and re-run only the most "ambiguous" items.

Summary updated

Abstract

Semantic query engines ask a large language model (LLM) to judge individual rows, and benchmarks compare these engines on the quality of a few executions at temperature 0. We measure how much another execution changes. We re-execute the text and tabular workloads of SemBench, LRO-Bench, and UDA-Bench through their own harnesses, log every one of 1.2 million model calls, and reanalyze SemBench's published executions. At temperature 0, between 0.07% and 10.2% of rows change their operator output over five executions, depending on the model, and up to 24.0% on one task. Plans amplify these changes exponentially in the number of rows an answer exposes, as a possible-worlds model predicts: on UDA-Bench, a few percent of extracted values change, but about two thirds of the answers do. In SemBench's published results, 21% of text results change quality between executions, including on engines whose plans are deterministic. Several per-query system comparisons, and 16 of 28 tests of LRO-Bench's implementation recommendations, are not settled by the executions the benchmarks run. Changing rows are rows on which models disagree with each other; identical requests within one execution disagree as often as across executions; and one execution's decision margin or reasoning length predicts which rows change. Voting reduces the variance but does not remove it, and a calibrated cascade keeps its guarantee while the rows it returns change. We derive reporting rules for benchmarks and design rules for engines.
BibTeX
@misc{hassanzadeh2026same,
  author = {Oktie Hassanzadeh and Dharmashankar Subramanian},
  title = {{Same Query, Different Answer: Run-to-Run Variance in Semantic Query Processing}},
  year = {2026},
  eprint = {2610.13823},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.13823},
}
Figure