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.
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
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