Skip to content

Glossary

This page defines every word the documentation uses that you might not already know, in plain language first. Each entry then gives the name the same thing has in the code (a field, class or function), and a link to the page that explains it properly. Entries are in alphabetical order; words the old pages used for the same thing ("cursor", "channel", "run-book") point to the current term.

A

Abstain

The decision is held: the proposed action is not carried out. A person or a later event decides instead. It happens when any check fails, or when the policy is in a state that proposes nothing.

  • In the code: Verdict.ABSTAIN; record.action is None and record.proposed_action still names what was blocked.
  • More: Act, abstain, degrade.

Act

The proposed action passed all six checks and may be carried out.

Alpha (α)

The share of ordinary cases you are willing to hold back as "unusual". With α = 0.10, a case is held when fewer than about 10% of the calibration cases are at least as unusual as it. The default is a starting point; in production it is learned from your history (Learn-then-Test).

Await next event

A routing label used by the examples and the reference service for an abstain where nothing was proposed and no check failed: the policy is simply waiting for the next thing to happen. Nothing needs a person.

  • In the code: the string "await_next_event" in examples/livefeed.py and examples/reference_service.py; it is not a field of DecisionRecord.
  • Contrast: hold for human.
  • More: Act, abstain, degrade.

B

Blocked overconfident acts

In the examples, the number of decisions a naive rule would have carried out but the library did not. It is the headline number of each example.

  • In the code: blocked_overconfident_acts in the summary returned by compare_with_naive_policy (examples/common.py); it equals naive_acts − grounded_acts.
  • More: Naive vs grounded.

Broadcast tree

Old name for the corroboration graph as the reconstruction theory models it. See related cases.

C

Calibration set

A list of unusualness scores from recent cases where the answer turned out right. The unusual-case check compares this case's score with them. An empty list means the check cannot say anything, and by default it passes.

Calibration split, risk split, hold-out

The three parts the learner divides your labelled history into, at random (30%, 50% and 20% by default). The calibration split builds the calibration set for each proposed action. The risk split is where every candidate setting is tested against the risk target. The hold-out is never used for choosing; it reports how the chosen settings do on unseen cases.

  • In the code: learn_parameters(calibration_fraction=0.3, holdout_fraction=0.2, seed=0); LearnedParameters.split_sizes, .risk_split, .holdout.
  • More: Learn parameters from your history.

Catalog, math catalog

The companion collection of mathematical results this library relies on, kept outside this repository. Each result has a number (old pages say "family"); for example, Kesten–Stigum reconstruction is catalog result 229. Some results have machine-checked proofs in Lean.

  • In the code: CatalogRef(family=..., title=..., lean=..., note=...) constants in grounded_decision.certificates; each check's report lists them in channels[].catalog. A "pin" is one of these references.
  • More: Where each result stands.

Certificate check

See policy-shape check.

Certified

A learned setting is certified when an exact statistical test shows, with the confidence you asked for, that its error rate is below your risk target. If no candidate is certified, the learner returns settings that hold every decision.

  • In the code: LearnedParameters.status is "certified" or "no_safe_configuration"; .certified; the command exits with 2 when nothing is certified.
  • More: Learning settings with a guarantee.

Channel

The name used in records for a check. Use "check" in prose.

Check

One of six independent yes/no tests every decision goes through. If any one says no, the decision is held. The six are: policy shape, progress, neighbour agreement, knife-edge, unusual case and support.

  • In the code: record.channels, a tuple of six ChannelReport, each with name (certificate, game, reconstruction, threshold, conformal, support), passed, trust, summary, metrics and catalog.
  • More: The six checks.

Comparator

The tool the companion math catalog uses to confirm that a Lean proof proves exactly the stated theorem. Nothing in this package runs it.

Compile time and decide time

Compile time is the work done once, when a Module is built: reading the policy, building its state machine, and solving the progress check. Decide time is the work done for every event: one step through the policy and four arithmetic checks on the evidence.

Conformal p-value

The share of calibration cases at least as unusual as this one, with a +1 correction so it is never zero. Small means "unlike anything we have seen". The unusual-case check passes when it is above α.

  • In the code: \( p = (1 + \#\{s \ge \texttt{label\_score}\}) / (1 + \text{number of scores}) \); conformal_p_value in evidence.conformal; record.health.conformal_p.
  • More: Coverage for unfamiliar cases.

Corroboration graph

See related cases.

Cursor

Old name for state.

D

Decision record

Everything about one decision, kept for audit: the verdict, the action carried out, the proposed action, the reason, all six check reports, a numeric summary, and the state to save.

  • In the code: DecisionRecord; store record.to_dict(), read back with DecisionRecord.from_dict.
  • More: The decision record.

Degrade

A third verdict: the policy itself asked for a weaker, pre-agreed fallback (for example, read-only mode). It only happens when all six checks pass and the current state is marked as a degrade state.

  • In the code: Verdict.DEGRADE, set with Statechart().state(name, verdict=Verdict.DEGRADE, action=...).
  • More: Act, abstain, degrade.

Degree (d)

The average number of links each related case has to other related cases.

Density (p̂)

How densely the related cases are linked: the share of all possible pairs that are actually linked, from 0 to 1.

E

Envelope

A label saying how hard a computation is. Two labels mean "refuse rather than try": undec (no algorithm can exist) and exptime_trap (too expensive under our budget). The router also refuses fpras, because no handler for it exists yet. The label on a Module is recorded but does not change decide.

  • In the code: Envelope with values p_exact, fpras, ugc_opt, undec, exptime_trap; record.envelope; Subgoal.envelope.
  • More: Questions the library refuses.

Environment-owned state

A state of a hand-built chart where someone other than your service (a customer, a payment network, a pager) chooses the next event. The progress check assumes the worst choice there.

Event

Something that happened, named the way the policy names it (suspicious, low_risk). Only the name moves the policy; any data you attach is recorded but not read. Old pages call it a "letter".

Evidence

The numbers describing the related cases around this decision: how many there are, how densely and strongly linked, how much they agree, and how unusual this case is compared with recent ones.

Evidence strength (dλ²)

Average links per case times neighbour agreement squared. Above about 1, the related cases genuinely tell you something about this one; below it, what they say is mostly noise. The check needs it above 1 + margin = 1.05 by default. It measures how informative the related cases are, not which outcome they point to.

Exchangeable

Cases are exchangeable when they come from the same process, so that any ordering of them is equally likely. In practice: tomorrow's cases look like a random draw from the same pool as the history. The unusual-case check's guarantee and the learner's certificate both assume it (the learner's exact test needs the slightly stronger "independent draws from one distribution"). Drift breaks it.

EXPTIME trap

The router's label for a question whose cost grows exponentially with a setting and is over our budget, such as Weisfeiler–Leman refinement with k above 2. It means "too expensive under our budget", not a proof of hardness.

F

Family

Old name for a math catalog result number.

Fiber

All tables with the same row and column totals. Used to ask whether an observed A/B split could have happened by chance.

Final state

A state with no way out: no event leads anywhere from it. The progress check treats the workflow as finished there and lets it stay; in a text policy, final states count as progress (priority 2).

Fixed-sequence testing

The default way the learner tests its grid of candidate settings: in an order fixed in advance from the calibration split (most clearly safe first), each at the full significance, stopping at the first failure. It gives the same guarantee as Bonferroni without dividing the significance by the number of candidates, so it usually certifies settings that act more often.

  • In the code: learn_parameters(..., procedure="fixed_sequence") (the default) or "bonferroni"; --procedure on the command line.
  • More: Learning settings with a guarantee.

Flicker window

Old name for the knife-edge window.

FPRAS

"Fully polynomial randomised approximation scheme": an algorithm that estimates a count to any requested accuracy in polynomial time, with high probability. Used as an envelope label; the router refuses subgoals sent with it, because no handler implements one, and this package's table sampler is not one.

G

Game check

See progress check.

H

Health

A flat summary of the numbers inside the six check reports (evidence strength, density, window widths, conformal p-value, star height, support share), so a dashboard does not have to unpack them.

Hold-out

See calibration split, risk split, hold-out.

Hold for human

A routing label used by the examples and the reference service for an abstain where an action was proposed and blocked by a failed check: send the case to a person. "Hold" in prose means the same.

  • In the code: the string "hold_for_human" in the examples; detect it as record.verdict == "abstain" and record.proposed_action is not None.
  • Contrast: await next event.

K

Kesten–Stigum line

The point, evidence strength = 1, above which related cases carry recoverable information about each other in the theory's model. "KS" in printouts.

Knife-edge window

The range of link densities around your cut-off where a little noise can flip the answer. If this case's density is inside it, the decision is held. The window is wide when there are few related cases: with 6 or fewer it covers every density, at 40 it is ±0.118, at 200 it is ±0.057.

L

Label, seed

The outcome you want to confirm for a case (fraud or not), and the value each related case carries. "Seed" is the theory's word for the label at the root of the related cases.

  • In the code: the labels argument of snapshot_from_graph.

Label mix

The proportions of each label among the related cases (for example 90% cleared, 10% fraud). When one label dominates everywhere and links may be unrelated to labels, random links agree most of the time, and the default agreement measure (uniform, the one the Kesten–Stigum result assumes) mistakes that for signal. Measuring agreement against the label mix corrects that, but scores a homogeneous ring (nearly all fraud) near zero although it is strong evidence, so it is not the default. Which way the related cases point is the support check's job.

  • In the code: snapshot_from_graph(..., agreement_baseline="label_mix"), lambda_against_label_mix in evidence.reconstruction.
  • More: Do the related cases agree?.

Lean

A proof assistant: software that checks mathematical proofs line by line. Some results in the math catalog have Lean proofs. Nothing in this package runs Lean, and you do not need it installed.

Learn-then-Test

The method the library uses to learn check settings from labelled history (Angelopoulos, Bates, Candès, Jordan and Lei, 2021). It tests candidate settings' error rates against your risk target with exact binomial tests, controlled for testing many candidates (fixed-sequence testing by default, or Bonferroni), and picks the most useful certified one. If future cases come from the same process as the history, the chosen setting's error rate is at most the target with the confidence you asked for.

Limits

One frozen object holding every size cap and tunable threshold. Pass a new one to change them.

M

Margin

How far above the Kesten–Stigum line evidence strength must be before the neighbour-agreement check passes. Default 0.05, so the bar is 1.05; in production, learn it from your history (Learn-then-Test).

Marking

A note on a policy state saying "propose this action when we get here".

  • In the code: Statechart().state(name, action=...); act(...) in a policy produces one.

Mean payoff

The long-run average reward per step along a loop of the policy, using payoffs you assign to states. The progress check needs the best achievable average from the start to be at least 0.

Module

One compiled policy plus the current state of one entity. Build it once, call decide for each event. Not safe to share between threads without a lock.

Monotone property

A yes/no property of a graph that stays yes when you add links (for example, "has a cycle"). The knife-edge theory is about such properties.

N

Not handled

An event that has no arrow out of the current state: a name the policy never uses, or one it uses only elsewhere (an approval before any request). The entity stays where it is and nothing is proposed. Old pages call this a "stutter".

  • In the code: Statechart.step returns None; the record's reason is event '…' is not handled in state '…'; nothing proposed.
  • More: One decision, step by step.

Naive policy

The comparison rule in the examples: carry out every proposed action without checking anything.

Neighbour agreement (λ)

How much more often linked cases share a label than chance would give. 0 means no better than chance; 1 means linked cases always agree; negative means they tend to disagree (which also counts as information, because the check squares it). It is not a model probability.

  • In the code: EvidenceSnapshot.lambda_hat; computed from the share of linked pairs that agree, \( p_{\mathrm{same}} \), as \( \lambda = (q\,p_{\mathrm{same}} - 1)/(q - 1) \) where \(q\) is n_states.
  • More: Do the related cases agree?.

Nonconformity score

Old name for unusualness score.

Number of label values (n_states, q)

How many different labels a case can have. Default 2 (for example, fraud / not fraud). It only affects how neighbour agreement is computed from raw agreements.

  • In the code: n_states on EvidenceSnapshot and snapshot_from_graph.

O

Operational width, theorem width

Two widths for the knife-edge window. The theorem width comes from the published Friedgut–Kalai result and is larger than 1 (so useless) at any realistic number of cases; it is reported, never used. The operational width uses a practical constant (2 instead of \(2^{19}\)) and is the one the check uses.

  • In the code: health.threshold_width_theorem, health.threshold_width_operational; Limits.operational_fk_prefactor.
  • More: Knife-edge densities.

P

Payload

Data attached to an event (amount, vital signs). Recorded, never read by the policy.

  • In the code: Event.payload.

Pin

Old name for a CatalogRef; see math catalog.

Policy

The short text or chart that lists which events lead to which proposed actions, for example test(suspicious) ; act(block). Old pages call it a "grammar" or "run-book".

  • In the code: parse(text) or the builders evt, act, seq, union, star; or a hand-built Statechart.
  • More: Write a policy.

Policy fingerprint

A short hash of what gives a saved state its meaning (the module name, envelope, compiled chart and policy text), saved alongside an entity's state, so a service can refuse to restore a state saved under a different policy version. Needed because editing a policy renumbers its states. Settings (Limits, evidence settings, learned parameters) have their own fingerprint, parameters_fingerprint.

  • In the code: policy_fingerprint(module) in examples/reference_service.py returns e.g. "fraud_review@3f9a1c0d2b7e"; the service answers HTTP 409 policy_version_mismatch when a saved state's fingerprint differs.
  • More: State and policy versions.

Policy-shape check

The check that the policy is simple enough to analyse: its nesting of repeats (star height) is at most 3 and it has at most 256 states. It is decided when the module is built; a policy that breaks either limit is refused then, so in a record this check always passes.

Priority

A whole number on each state used by the progress check. Even means "fine to keep coming back here forever"; odd means "must not end up circling here forever"; the largest priority seen forever decides. Text policies get 2 on states that propose an action and on final states, 1 elsewhere.

Progress check

The check, solved once when the module is built, that from the start the service can keep the workflow making progress (coming back to even-priority states, whatever the environment does in environment-owned states) and that some reachable cycle has a non-negative average payoff. A text policy that can loop forever without proposing anything fails it. It assumes the service sends the right events in the states it controls.

Proposed action

What the policy would do next if nothing else were checked. Always recorded, including when the decision is held.

Provenance

The record of where a learned setting came from: the risk target, the grid of candidates, how many were certified, the split sizes and seed, a fingerprint of the history, and the hold-out result. Its short hash, the parameters fingerprint, belongs on every decision record.

  • In the code: the provenance section of LearnedParameters.to_dict() (params.json); LearnedParameters.fingerprint (params@…).
  • More: Where every number comes from.

R

Reason

A one-line explanation on every record: the summaries of the failed checks joined by ;, or all channels passed, or event '…' is not handled in state '…'; nothing proposed, or no action marked on current state.

Reconstruction check

See neighbour agreement and evidence strength. Channel name reconstruction.

Refusal

The router declining to attempt a question because no algorithm can answer it in general, or it is too expensive under the current limits.

  • In the code: a RouterResult with ok=False for envelopes undec, exptime_trap and fpras; RouterRefuse is raised only for an unknown subgoal.
  • More: Questions the library refuses.

The past cases connected to this one (by a shared device, symptom, reporter, ...), drawn as dots with lines between cases that share something. Also called the corroboration graph. The evidence describes this graph.

  • In the code: the labels and edges you pass to snapshot_from_graph; EvidenceSnapshot.n is how many there are.
  • More: From your data to evidence.

Risk split

See calibration split, risk split, hold-out.

Risk target

The error rate you accept, how sure you must be of it, and which error rate it is (among the decisions acted on, or among all decisions). It is the one setting data cannot choose: it is your risk appetite.

  • In the code: RiskTarget(max_risk=0.05, confidence=0.95, measure=RiskMeasure.ERROR_RATE_AMONG_ACTS); --max-risk on the command line.
  • More: Learn parameters from your history.

Router

An optional helper, never called by decide, for hard side questions (split a graph into two groups, cover all links, place facilities, fingerprint a graph, find rational roots). It runs a bounded approximation or refuses.

Run-book

Old name for policy.

S

Selective labels

Outcomes known for only some decisions: chargebacks only for cards that were not blocked, reviewer verdicts only for held cases. History with selective labels describes a different population from the one the service decides on, so settings learned from it are certified for that other population. The learner warns when every case with a known outcome has was_acted_on: true.

Star height

How deeply repeats (*) are nested inside each other in a policy. test(a)* has star height 1; a repeat inside a repeat has 2. The library refuses policies above 3.

State

Where an entity currently is in its policy, such as "in review". Save it after each decision and restore it before the next event for the same entity. Old pages call it the "cursor".

  • In the code: record.extras["state"], Module.state, Module.restore(state), Module.reset(). Policies written as text get states named s0, s1, ...
  • More: State and policy versions.

Statechart

The policy drawn as a flowchart: named states, arrows labelled with events, and optional proposed actions, payoffs and priorities on states. Text policies are compiled into one.

Stutter

Old name for an event that is not handled.

Subgoal

A hard side question handed to the router, tagged with how hard it is.

  • In the code: Subgoal(name, envelope, payload).

Supercritical, subcritical

Above (supercritical) or at or below (subcritical) the Kesten–Stigum line. Printouts say "supercritical" when the neighbour-agreement check passes.

Support

The share of related cases that carry the outcome the proposed action implies (for block: confirmed fraud). The support check holds the decision when it is below the minimum (0.5 by default). It is the only check that looks at which way the evidence points, and only when the evidence carries the share.

  • In the code: EvidenceSnapshot.support (None = not measured), snapshot_from_graph(..., supporting_label=...), support_report, Limits.min_support, Limits.require_support; channel support; record.health.support.
  • More: Do the related cases support this action?.

T

Threshold, cut-off (p_threshold)

The link density at which your own policy considers the related cases "meaningfully connected". The knife-edge window is centred on it. You choose it.

Threshold check

See knife-edge window. Channel name threshold.

Trust level

How much of a mathematical result a check's yes/no relies on: proven (a machine-checked theorem covers it), published (a published argument, not machine-checked, or a policy choice), practical (an engineering stand-in with a tunable constant).

  • In the code: Trust with values lean, paper, operational; channels[].trust. These are coarse: the policy-shape check always says lean, the knife-edge check is operational at every realistic size, and the unusual-case and support checks are always operational.
  • More: Trust levels and honest limits.

U

UNDEC

Envelope label for a question no algorithm can answer in general. The router refuses it.

Unique Games Conjecture

An unproven conjecture in complexity theory. If it is true, several approximation ratios (such as 0.8786 for Max-Cut) are the best any fast algorithm can promise. Results that rely on it always say "assuming the Unique Games Conjecture".

Unusualness score

A number you compute, the same way for every case, saying how unusual a case is (for example, 1 − model confidence). The unusual-case check compares this case's score with the calibration set. Old pages call it a "nonconformity score".

V

Vacuous

A proven bound that is too loose to constrain anything at real data sizes, for example a knife-edge window wider than the whole 0-to-1 range. It is reported for the record and never used. "Galactic" means the same for constants.

Verdict

The outcome of a decision: act, abstain or degrade.

W

Was acted on

Whether a past decision in the history was carried out (true) or held (false). The learner uses it to warn about selective labels.

W

Weisfeiler–Leman (WL)

A family of methods for fingerprinting graphs by repeatedly refining node colours. Level k costs roughly \(n^{k+1}\) work; the router allows k up to 2.

Z

Zielonka's algorithm

The standard recursive algorithm for solving parity games, used once at build time by the progress check.