# Oracle

The oracle is how a method decides an output is *correct*. There are three
branches — **property** (a machine check on one output) and **judgment** (a human
or AI decides one output), both single-run; and **probabilistic** (a claim about
the *distribution* of many runs), which sits over either of the first two or
stands alone.

<figure class="axis-tree" markdown>

- property
    - **equality**
    - **predicate**
    - **relation**
    - **errors**
- judgment
    - **human**
    - **AI**
- probabilistic
    - **aggregate**
    - **statistical**
    - **exact**

</figure>

## Property — a checkable claim

A property is a claim the output must satisfy, computed by a fixed procedure.
Written as a formula over the program $f$, the kinds line up by the **form of
the check**:

| kind          | the check                              | examples                                                                            |
| ------------- | -------------------------------------- | ----------------------------------------------------------------------------------- |
| **equality**  | $f(x) = y$ ($y$ given)                   | snapshot                                                                            |
|               | $f(x) = f'(x)$ ($y$ from a reference $f'$) | differential                                                                        |
| **predicate** | $P(f(x))$                              | invariant $f(x) \geq 0$; type/schema $f(x) : T$; formal $f(x) \models \varphi$; threshold $m(f(x)) < c$; membership (supply-chain: dep $\notin$ advisory DB) |
| **relation**  | $R(f(x), f(x'))$, $x' = t(x)$          | metamorphic $f(\text{shuffle } x) = f(x)$, $f(2x) = 2 \cdot f(x)$                 |
| **errors**    | $f(x)\downarrow$ (it just runs)                 | crash, hang, resource exhaustion, sanitizer trip                                |

The kinds **partition by the form written** (a value, a unary predicate, a
relation, or nothing), even though they nest logically by strength ($= y$ is a
special predicate; a relation is a predicate over two outputs; $\downarrow$ is the
weakest). All four judge a *single* output; an oracle that judges the
*distribution* of many outputs is a separate branch: **probabilistic**.

**equality** splits by the **provenance** of $y$: recorded → **[snapshot /
approval](https://quality.stereobooster.com/snapshot-testing.md)** (catches *change*, not
*correctness*); a reference computes it →
**differential** (relative correctness, only as good as the reference $f'$).
A hand-authored expected value (`assert f(2) == 4`) is not an oracle in this
sense: no procedure computes $y$, so it is an oracle-agnostic
[example test](https://quality.stereobooster.com/example-tests.md), not an equality oracle.

**predicate** spans a partial constraint many outputs pass — an ad-hoc
**invariant** (one holding across all *inputs*, $\forall x.\, P(f(x))$), a **type / schema**, a
machine-checked **formal** spec, a
deterministic **threshold** ($m(f(x)) < c$ on a single output, e.g. a clone-similarity
score), or a **membership** test (supply-chain hygiene: "this
dependency is not in the advisory database"). A threshold over a *distribution*
of runs is a different kind — **probabilistic**.

**errors** is the one kind with **no authored claim** — the runtime or a
sanitizer ([ASan](https://clang.llvm.org/docs/AddressSanitizer.html) / [UBSan](https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html) / [MSan](https://clang.llvm.org/docs/MemorySanitizer.html) /
[TSan](https://clang.llvm.org/docs/ThreadSanitizer.html)) supplies the check: an *unexpected* abnormal termination (a
crash, hang, or uncaught exception), where memory-unsafety / UB is a bug by
definition. An exception the contract documents (a named `ValueError`, not a
bare crash) is the program working as specified; fuzzing harnesses catch those
and treat only the rest as findings. It's still "computed by a fixed
procedure": the procedure is just the runtime.

## Judgment — a human or AI decides

When no checkable claim is writable — *is this answer helpful? is this
translation good? is this UI right?* — a **judge** forms the verdict, with no
fixed procedure.

- **human** — a person judges the run's *output* (raters, manual QA,
  exploratory testing). Judging the *code* rather than its output is code
  review — a [process method](https://quality.stereobooster.com/code-review.md), off this
  axis.
- **AI** — a model judges: LLM as judge, reward models. Historically the human
  oracle was the *manual, last-resort* option; AI makes the judgment branch
  **automatable at scale** (the case where [AI is the oracle](https://quality.stereobooster.com/ai.md)).
  Caveat: the judge is itself fallible,
  biased, and non-deterministic, so the judge itself must be validated, and its
  verdict is a distribution, not a single answer.

## Probabilistic — a claim about the distribution

When the SUT *or* the judge is non-deterministic — LLMs, flaky concurrency,
statistical code, the strength of a chess engine — no single run is a verdict.
The oracle is a claim about a *parameter of the output distribution* — $\theta(D_f(x)) \bowtie c$,
a parameter $\theta$ of the distribution $D_f(x)$ against a bound $c$: a win-rate, a
pass-rate, a tail latency, an error budget, an A/B lift. The oracle obtains that
parameter — by sampling, or by computing it exactly over the state space — and
compares it to the bound. Dobslaw et al. call this treating correctness as "a
distribution of outcomes rather than a binary property" (Dobslaw et al. 2025)[^dobslaw2025].
This is the oracle of [statistical / sampling
testing](https://quality.stereobooster.com/statistical-testing.md); the sub-kinds differ in how
the parameter is obtained, and how much the decision promises:

- **Aggregate.** Pick a sample size, summarize — majority vote, mean, pass-rate $\geq$ a
  bound — and compare to a threshold chosen by judgment. There's no controlled
  error rate: a "95% over 100 runs" gate bounds neither the odds of waving
  through a bad build nor the odds of rejecting a good one. This is the
  *hope-for-the-best* end, common in LLM evals and SLO checks; it earns a
  [heuristic](https://quality.stereobooster.com/guarantee.md) guarantee.
- **Statistical.** State a hypothesis and control the false-accept / false-reject
  rates. In testing this is mostly comparing two builds' metric *distributions*: a
  Welch's t-test (Welch 1947)[^welch1947] or Mann–Whitney (Mann and Whitney 1947)[^mann1947] on latency, a
  two-proportion test on a model's pass-rate, bootstrap (Efron 1979)[^efron1979] or permutation
  intervals when the statistic is a percentile like p99. *Sequential* tests stop as soon as the evidence is decisive — SPRT
  (Wald 1945)[^wald1945] and GSPRT (Li et al. 2014)[^li2014] are the sequential case, how **Stockfish** gates
  every patch on Fishtest at far fewer games than a fixed-sample test
  (The Stockfish Project 2026)[^stockfish2026]. (At the deployment edge — always-on A/B and canary analysis —
  Bayesian and *anytime-valid* variants like mixture SPRT carry the same idea so a
  result survives continuous peeking.) This is the *statistical-confidence* end;
  fixed vs sequential is just a sample-size choice — both control error,
  aggregate does not.
- **Exact.** No sampling at all: the parameter is computed over the whole state
  space, and the property checked against its true value. [Exact probabilistic
  model checking](https://quality.stereobooster.com/probabilistic-model-checking.md) ([PRISM](https://www.prismmodelchecker.org/), [Storm](https://www.stormchecker.org/))
  solves a PCTL / CSL probability over every reachable state, so the verdict is
  sound within the model's bounds rather than a confidence interval. It is the
  only probabilistic sub-kind that reaches an [exhaustive](https://quality.stereobooster.com/guarantee.md)
  guarantee, and only because its input enumerates the space instead of sampling
  it.

A probabilistic oracle judges no individual run — a single lost game isn't a
bug. Usually it sits *on top of* a per-run signal, a predicate's pass/fail or a
human or AI judge's rating, and turns the sample into a verdict (a pass-rate is
a predicate sampled; inter-rater agreement is judges sampled). But it needn't: a
win-rate or a latency distribution has no per-run verdict underneath at all.
Caveat: the test assumes roughly i.i.d. trials and a well-defined per-trial
signal, so for truly open-ended output the aggregate is only as meaningful as
that signal.

It's the only oracle available at the **unbounded** tier of the [nondeterminism
ladder](https://quality.stereobooster.com/effect.md) — variation that can be neither removed nor modeled, only
sampled — and it also judges noisy-but-bounded measurements like latency.

## Correspondence to the literature

The standard oracle survey (Barr et al. 2015)[^barr2015] classifies oracles by their *source*;
these kinds map onto it:

- **provenance** (authored / recorded / reference) ≈ Barr's *specified* vs
  *derived* — for us a sub-split of *equality*, not the spine.
- **errors** ≈ Barr's *implicit*.
- **judgment / human** ≈ Barr's *human*; we split out **AI** (a judge type that
  didn't exist in 2015).
- **metamorphic** is defined as a relation over *two or more* runs ($n \geq 2$)
  (Chen et al. 2018)[^chen2018] — our *relation* kind.
- **probabilistic** ≈ Barr's *probabilistic* oracle (Barr et al. 2015)[^barr2015], with
  Dobslaw et al.'s atomic-vs-*aggregated* cut as a separate framing (Dobslaw et al. 2025)[^dobslaw2025]; its sequential
  decision procedure is the SPRT / GSPRT (Wald 1945; Li et al. 2014)[^wald1945] [^li2014].

Sorting by *form of the check* separates the three things Barr's single
*derived* bucket conflates: **differential** (an equality — value from a
reference), **recorded** (an equality — value from a prior run), and
**metamorphic** (a relation) sit at three different kinds.

## Related

**Same name, different thing — Invariant: contract-lifetime vs across-inputs**

The word *invariant* names different things. In [Design by
Contract](https://quality.stereobooster.com/contracts-and-runtime-assertions.md) it's a predicate
on an object's state that holds across its whole *lifetime* — before and after
every public method. In [property-based
testing](https://quality.stereobooster.com/property-based-testing.md) and on the oracle
axis it's a predicate that holds across *inputs*
($\forall x.\ P(f(x))$ — `sort(xs)` comes out ordered), which in contract terms
is a *postcondition*, not the lifetime invariant. (Hoare logic adds a third: the
*loop* invariant, across iterations.) The [glossary](https://quality.stereobooster.com/glossary.md) lays out all
three.

**Same name, different thing — Property: the PBT claim vs the whole oracle branch**

[Property-based testing](https://quality.stereobooster.com/property-based-testing.md) historically
calls the claim it checks a "property" — usually a single predicate or a
relation. On this axis, **property** is broader: it names the *whole computed
branch* (equality / predicate / relation / errors), as opposed to human or AI
*judgment*. So the property-based-testing sense is just the predicate and
relation kinds within the property branch.

## Referenced by

- [Effect scope](https://quality.stereobooster.com/effect.md) · The axes
- [Guarantee](https://quality.stereobooster.com/guarantee.md) · The axes
- [The axes](https://quality.stereobooster.com/axes.md) · The axes
- [Contracts as specifications](https://quality.stereobooster.com/contracts-as-specifications.md) · Methods
- [Metamorphic testing](https://quality.stereobooster.com/metamorphic-testing.md) · Methods
- [Methods](https://quality.stereobooster.com/methods.md) · Methods
- [Snapshot and approval testing](https://quality.stereobooster.com/snapshot-testing.md) · Methods
- [How AI fits into software quality](https://quality.stereobooster.com/ai.md) · AI
- [Glossary](https://quality.stereobooster.com/glossary.md) · Overview

## References

[^dobslaw2025]: Dobslaw, Felix, Robert Feldt, Juyeon Yoon, and Shin Yoo. 2025. *[Challenges in Testing Large Language Model Based Software: A Faceted Taxonomy](https://arxiv.org/pdf/2503.00481)*. arXiv:2503.00481. <https://doi.org/10.48550/arXiv.2503.00481>.
[^welch1947]: Welch, B. L. 1947. "[The Generalization of 'Student's' Problem when Several Different Population Variances are Involved](https://www.jstor.org/stable/2332510)." *Biometrika* 34 (1–2): 28–35. <https://doi.org/10.2307/2332510>.
[^mann1947]: Mann, H. B., and D. R. Whitney. 1947. "[On a Test of Whether one of Two Random Variables is Stochastically Larger than the Other](https://projecteuclid.org/journalArticle/Download?urlId=10.1214%2Faoms%2F1177730491)." *Annals of Mathematical Statistics* 18 (1): 50–60. <https://doi.org/10.1214/aoms/1177730491>.
[^efron1979]: Efron, B. 1979. "[Bootstrap Methods: Another Look at the Jackknife](https://sites.stat.washington.edu/courses/stat527/s14/readings/ann_stat1979.pdf)." *Annals of Statistics* 7 (1): 1–26. <https://doi.org/10.1214/aos/1176344552>.
[^wald1945]: Wald, Abraham. 1945. "[Sequential Tests of Statistical Hypotheses](https://projecteuclid.org/journals/annals-of-mathematical-statistics/volume-16/issue-2/Sequential-Tests-of-Statistical-Hypotheses/10.1214/aoms/1177731118.pdf)." *Annals of Mathematical Statistics* 16 (2): 117–86. <https://doi.org/10.1214/aoms/1177731118>.
[^li2014]: Li, Xiaoou, Jingchen Liu, and Zhiliang Ying. 2014. "[Generalized Sequential Probability Ratio Test for Separate Families of Hypotheses](https://pmc.ncbi.nlm.nih.gov/articles/PMC4941833/)." *Sequential Analysis* 33 (4): 539–63. <https://doi.org/10.1080/07474946.2014.961861>.
[^stockfish2026]: The Stockfish Project. 2026. *[Statistical Methods and Algorithms in Fishtest](https://official-stockfish.github.io/docs/fishtest-wiki/Fishtest-Mathematics.html)*. <https://official-stockfish.github.io/docs/fishtest-wiki/Fishtest-Mathematics.html>.
[^barr2015]: Barr, Earl T., Mark Harman, Phil McMinn, Muzammil Shahbaz, and Shin Yoo. 2015. "[The Oracle Problem in Software Testing: A Survey](https://ieeexplore.ieee.org/ielx7/32/7106034/06963470.pdf)." *IEEE Transactions on Software Engineering* 41 (5): 507–25. <https://doi.org/10.1109/TSE.2014.2372785>.
[^chen2018]: Chen, Tsong Yueh, Fei-Ching Kuo, Huai Liu, et al. 2018. "[Metamorphic Testing: A Review of Challenges and Opportunities](https://www.cs.hku.hk/data/techreps/document/TR-2017-04.pdf)." *ACM Computing Surveys* 51 (1): 1–27. <https://doi.org/10.1145/3143561>.

## Acronyms

- CSL — continuous stochastic logic
- GSPRT — generalized sequential probability ratio test
- PBT — property-based testing
- PCTL — probabilistic computation tree logic
- SLO — service level objective
- SPRT — sequential probability ratio test
- SUT — system under test
- UB — undefined behavior