Skip to content

Knife-edge densities (Friedgut–Kalai)

Many policies draw a line through a number: take a post down when it sits in a cluster of matching posts at least this dense, treat a team as cohesive when its members are linked at least this often. When the measured number lands right on that line, a little noise decides the outcome, and an automated system flips between two actions from one request to the next. This page explains the mathematics behind the library's knife-edge check — Friedgut–Kalai sharp thresholds, catalog result 186 — what the theorem says, and why the check the code runs is a practical rule shaped like the theorem rather than the theorem applied.

It assumes you know what a random graph and a logarithm are. Symbols are collected on How to read these pages; the plain-language version of this check is The knife-edge check.

The situation

Each decision carries evidence: the related cases around it, drawn as a graph (the corroboration graph) with \(n\) cases and the links between them. One number the evidence carries is the observed link density \(\hat p\): the links present divided by the links possible, \(\lvert E\rvert / \binom{n}{2}\). Your policy picks a cut-off \(p^\star\) (the field p_threshold): the density at which it starts reading the cluster differently, for example "one piece of content copied many times" rather than "many posts that share a template".

The question this check answers is: is the observed density so close to the cut-off that a few more or fewer links would change how the cluster is read? If yes, the library holds the decision for a person and records the action it would have taken (proposed_action). If no, the density is allowed to support an automated action. The check says nothing about which action; that comes from the event and the policy.

Intuition: properties switch on over a window, not at a point

Take \(n\) points and join each pair independently with probability \(p\). Ask a yes/no question about the result that can only go from "no" to "yes" as links are added, such as "is the graph connected?" or "is there a triangle?" (a monotone property). At \(p = 0\) the answer is surely no; at \(p = 1\) surely yes. In between, the probability of "yes" climbs along an S-shaped curve.

Edge probability \(p\) well below the window inside the window well above the window
Probability the property holds close to 0 anywhere from \(\varepsilon\) to \(1 - \varepsilon\) close to 1
What a small change in \(p\) does nothing visible can flip the answer nothing visible

The window is the range of \(p\) over which the probability climbs from a small \(\varepsilon\) (say 10%) to \(1 - \varepsilon\). Inside it, the answer is close to a coin toss and sensitive to every link. Friedgut and Kalai showed that for every such property the window shrinks as \(n\) grows: large graphs switch sharply.

The library borrows the shape of that idea for a different line. It draws a band around your cut-off \(p^\star\), with a width that shrinks with \(n\) in the same way, and holds any decision whose observed density lands inside the band.

Worked example: a meme template versus a re-upload

Run:

uv run grounded-decision examples content_moderation

The example decides whether to take down flagged posts using a graph of near-duplicate posts (cases are posts, links join perceptual-hash matches), with cut-off \(p^\star = 0.30\).

Flagged post \(n\) Links \(\hat p\) Half-width of the band Distance from \(p^\star\) Knife-edge check Verdict
re-upload of a removed video 20 190 1.0 0.179 0.70 pass act take_down
resembles a loose cluster of template posts 30 161 161/435 = 0.370 0.139 0.070 fail hold, proposed_action=take_down

The example prints the second case as

density p̂=0.3701  flicker band p*=0.3  FLICKERING (inside window — do not trust)
...
threshold        FAIL  is density outside the operational flicker window?
                   evidence density inside operational window (theorem width=7.29e+04, vacuous=True)

The neighbour-agreement check passed on that post (evidence strength \(d\lambda^2 = 10.73\), well above its line): the related cases agree perfectly. The density alone is the reason it is held. A team that implemented only the neighbour-agreement check would have taken it down.

A second run shows the same check on access requests from a 50-person team, cut-off 0.20:

uv run grounded-decision examples step_threshold_window

Dan's team has density 0.45 (outside the band of half-width 0.1052, granted); Erin's has 0.21 (inside, held). The example ends with window_half_width=0.1052.

You can reproduce the held post directly:

from grounded_decision.evidence.thresholds import threshold_report

r = threshold_report(30, 161 / 435, 0.3)
print(r.passed, r.trust)  # False operational
print(round(r.metrics["operational_width"], 4))  # 0.2783
print(r.metrics["theorem_width"] > 1)  # True: the theorem's width is vacuous

The precise statement

Setting. \(G(n, p)\) is the random graph on \(n\) labelled vertices where each of the \(\binom{n}{2}\) pairs is linked independently with probability \(p\). A graph property is a set of graphs closed under relabelling the vertices; it is increasing (monotone) if adding edges never destroys it, and nontrivial if the empty graph lacks it and the complete graph has it. Write \(\mu_p(A)\) for the probability that \(G(n,p)\) has property \(A\), and \(p_\varepsilon\) for the \(p\) at which \(\mu_p(A) = \varepsilon\). The critical probability is \(p_{1/2}\).

Friedgut–Kalai (1996). For every nontrivial increasing graph property \(A\) and \(0 < \varepsilon < 1/2\),

\[ p_{1-\varepsilon} - p_\varepsilon \;\le\; C\,\frac{\log(1/\varepsilon)}{\log n} \]

for an absolute constant \(C\). The window \([p_\varepsilon, p_{1-\varepsilon}]\) contains the property's own critical probability \(p_{1/2}\); it is a statement about where the property switches on, for a graph drawn from \(G(n,p)\).

Sharper widths. Bourgain and Kalai (1997) improved the exponent for graph properties to \((\log n)^{-2+\delta}\) for every \(\delta > 0\). A width of order \((\log n)^{-2}\) is conjectured.

Where this result stands

In the wider literature: the \(O(\log(1/\varepsilon)/\log n)\) window is a theorem (Friedgut and Kalai, 1996), and \((\log n)^{-2+\delta}\) for every \(\delta > 0\) is a theorem for graph properties (Bourgain and Kalai, 1997). A width of order \((\log n)^{-2}\) with an explicit constant is, to our knowledge, open.

In this project's math catalog (result 186): for every \(n \ge 2\), every nontrivial increasing relabelling-invariant graph property and \(0 < \varepsilon < 1/2\), the window has width at most [ \frac{2^{19}\,\log\bigl(1/(2\varepsilon)\bigr)}{(\log n)^2}, ] with a Lean statement. The catalog reference's title in the code calls this "Friedgut–Kalai"; it is the catalog's sharpened form, not the 1996 statement.

What this library relies on: nothing from either. The catalog width is reported but never decides anything, because it is larger than 1 for every \(n\) below about \(10^{399}\) (below). The check that decides is a practical rule with a hand-chosen constant. See Where each result stands.

How vacuous the catalog width is. With \(\varepsilon = 0.1\), \(\log(1/(2\varepsilon)) = \ln 5 \approx 1.609\), so the catalog width is \(843{,}809/(\ln n)^2\). It drops below 1 only when \(\ln n > 918.6\), that is \(n > 10^{399}\). At \(n = 80\) it is 43,943; at \(n = 10^6\) it is 4,420 (from theorem_width(n, 0.1) in the table below). A width larger than the whole interval \([0, 1]\) says nothing; the code calls it vacuous.

What the code does

threshold_report(n, p_hat, p_threshold) in grounded_decision/evidence/thresholds.py computes two widths with \(\varepsilon = 0.1\) (fixed; Module.decide does not let you change it) and natural logarithms:

\[ w_{\mathrm{catalog}} = \frac{2^{19}\ln 5}{(\ln n)^2}, \qquad w = \frac{2\ln 5}{(\ln n)^2}, \]

the second using Limits.operational_fk_prefactor (default 2.0). For \(n < 3\) both widths are set to 1. Then

\[ \text{fail (hold)} \iff \lvert \hat p - p^\star \rvert \le \tfrac12 \min(w, 1). \]

Half the width, \(\tfrac12\min(w,1)\), is the distance from the cut-off inside which the check holds. It depends only on \(n\). From uv run python -c "from grounded_decision.evidence.thresholds import operational_width as w; [print(n, round(w(n, 0.1), 4), round(min(w(n, 0.1), 1)/2, 4)) for n in (6, 7, 10, 16, 20, 30, 40, 50, 80, 200, 1000)]":

Related cases \(n\) Width \(w\) Half-width (hold if within this of \(p^\star\))
3 to 6 ≥ 1 0.5 (cap)
7 0.850 0.425
10 0.607 0.304
16 0.419 0.209
20 0.359 0.179
30 0.278 0.139
40 0.237 0.118
50 0.210 0.105
80 0.168 0.084
200 0.115 0.057
1000 0.068 0.034

Every difference from the theorem:

  1. The band is centred on your cut-off, not on a critical probability. The theorem locates where a property of a random graph switches on. The code puts a band around \(p^\star\), a number your policy chose, and asks whether one observed density is near it. The theorem does not say that densities near a policy cut-off are unreliable; that is a product judgement which borrows the theorem's shape (a band that narrows like \(1/(\log n)^2\)).
  2. The constant is hand-chosen. The prefactor 2 is not derived from any theorem or fitted to data in this repository. It was picked so the band fits inside \([0, 1]\) at the graph sizes the examples use. The tag on the check says so: trust="operational".
  3. One observed graph, not a probability. The theorem is about the edge probability \(p\) of a random graph. The code uses the density of one graph you observed, and does not check that your graph resembles \(G(n,p)\) or that anything about it is monotone.
  4. The band is not a sampling-error interval. If your graph really were \(G(n, p)\), the standard error of \(\hat p\) would be \(\sqrt{p(1-p)/\binom n2}\): 0.0114 for \(n = 50\), \(p = 0.2\), and 0.022 for \(n = 30\), \(p = 0.3\) (computed with uv run python -c "import math; print(math.sqrt(.2*.8/1225), math.sqrt(.3*.7/435))"). The bands at those sizes (0.105 and 0.139) are five to nine times wider. The check is a conservative dead band, not a confidence interval.
  5. Trust tag. The code tags the result lean only if the catalog width is below 1, which never happens at a size you can store; in practice every result is operational.
  6. Exactly on the cut-off always holds, because the test is \(\le\): \(\hat p = p^\star\) is inside any band.

The record's metrics carry n, p_hat, p_threshold, epsilon, theorem_width, operational_width, in_theorem_window (always false while the width is vacuous), in_operational_window and theorem_vacuous. The decision's Health copies the same widths and flags so a dashboard can plot them without unpacking the checks.

Limits, and what to do about them

Small graphs almost always hold

With 6 or fewer related cases the half-width is 0.5, so the check passes only when \(\hat p\) and \(p^\star\) are more than 0.5 apart. Below about 10 cases it passes only when the density is at least 0.3 from the cut-off. If your traffic usually has small evidence graphs, expect this check to hold most decisions, and decide whether that is what you want before going live.

  • It is direction-blind. A pass means "not near the cut-off", not "the density supports this action". In content_moderation, a benign event on a dense cluster acts leave_up exactly as a flagged event acts take_down, because that example does not measure support. The event you send carries the direction; the support check can hold an action the related cases contradict, when you measure it.
  • Choosing \(p^\star\). Put the cut-off where the meaning of the density really changes for your policy, using labelled history (for example, the density above which past clusters were almost always ruled to be one piece of content). Then look up the half-width for your typical \(n\) in the table above and check how much of last month's traffic falls inside \(p^\star \pm\) half-width: that is roughly the share this check will hold. Set the cut-off once and leave it; retuning it to push borderline cases outside the band defeats the check. Choose parameters walks through this.
  • Leaving p_threshold at 0. The band then sits at 0, so sparse graphs hold and dense ones pass regardless of meaning. Always set a cut-off.
  • Densities that are not graph densities. You may put any number in \([0, 1]\) in p_hat (a report rate, a share of positive reviews). The check then is purely the dead band above; none of the theorem's setting applies.
  • Widening or narrowing the band. Change Limits(operational_fk_prefactor=...). Doubling it doubles the width at every \(n\). Never shrink friedgut_kalai_prefactor to make the catalog width non-vacuous: the catalog statement uses \(2^{19}\).
  • It ignores agreement and the score. A dense graph can be uninformative (neighbour agreement), and a case can be unusual on an otherwise clear graph (unusualness). The decision acts only when all six checks pass.