Router and compare¶

Some products need to answer a hard side question before or after a decision: split a fraud ring into two groups, choose a few warehouse sites, check whether an A/B split could be chance, or notice that the distribution of outcomes moved. The router (router/) and the compare helpers (compare/) answer those questions with bounded, labelled procedures, or refuse. Module.decide never calls them; your code does. This page is for contributors changing them: what each function actually computes, what it guarantees, and what it must not claim.

How to call them from a product: Use the hardness router and Compare outcomes and features. The mathematics and its status: the theory pages linked in each section. Words such as envelope, UNDEC and Unique Games Conjecture are in the glossary.

How `dispatch` works¶

dispatch(Subgoal(name, envelope, payload), limits=...) in router/dispatch.py:

if envelope is UNDEC:          return RouterResult(ok=False, detail="envelope UNDEC: refuse")
if envelope is EXPTIME_TRAP:   return RouterResult(ok=False, detail="envelope EXPTIME_TRAP: refuse")
if envelope is FPRAS:          return RouterResult(ok=False, detail="no FPRAS handler is implemented; ...")
fn = _HANDLERS.get(name)       or raise RouterRefuse("unknown subgoal ...")
return fn(subgoal, limits)

The three refusing envelopes short-circuit before any handler, even if one is registered. The dispatcher never tries "just this once". fpras is refused because no handler implements it yet (detail no FPRAS handler is implemented; send the subgoal with its own envelope), so no handler can answer under one label and report another.
The other envelopes (p_exact, ugc_opt) reach the handler, which receives the caller's Limits (tests/test_router_compare.py::test_dispatch_honours_caller_limits).
A handler may refuse a combination (max_cut raises RouterRefuse("max_cut requires UGC_OPT or P_EXACT") for any other envelope; none reaches it today) or report a weaker result envelope than requested (Max-Cut always returns ugc_opt, because it is an approximation). It never reports a stronger one.
An unknown name raises RouterRefuse: a programming error, not a hard instance.

available_subgoals() returns ("k_median", "max_cut", "rational_zeros", "vertex_cover", "wl"). RouterResult is frozen: subgoal, envelope, ok, detail, value, with to_dict(). Refusals are results with ok=False, not exceptions.

Handlers at a glance¶

`name`	A product would call it to…	What runs	Result envelope
`max_cut`	split a graph into two groups with many links between them	top Laplacian eigenvector, then local search	`ugc_opt`
`vertex_cover`	choose nodes that touch every link (monitors, reviewers)	both ends of a maximal matching	`ugc_opt`
`k_median`	get the approximation factor not to promise for facility placement	no search; returns 1 + 2/e as a note	`ugc_opt`
`wl`	fingerprint a graph to spot structurally identical ones	colour refinement (k = 1) or pairwise refinement (k = 2)	`p_exact`, or `exptime_trap` above the cap
`rational_zeros`	(refused) find every rational root of a polynomial	nothing	`undec`

Max-Cut: eigenvector plus local search¶

max_cut_spectral(adj) in router/ugc.py, with adj: dict[int, set[int]]:

Build the Laplacian \(L = D - A\), counting each undirected edge once. No vertices or no edges → value 0.
Take the eigenvector of the largest eigenvalue of \(L\) (it maximises \(\sum_{(u,v)} (x_u - x_v)^2\), which points toward a large cut) and split vertices by sign.
Local search: while some vertex has more neighbours on its own side than across, move it. Each move increases the cut, so this stops, and at the end every vertex has at least half its edges cut, so the cut has at least \(m/2\) edges.

factor_claimed is gw_alpha() ≈ 0.8786 with catalog_optimal=True. That number is the best ratio any polynomial algorithm can promise if the Unique Games Conjecture holds (catalog result 102); it is not a guarantee of this procedure, whose only guarantee is \(m/2\). The detail string says so. Real outputs:

Graph	`detail` (start)
triangle	`spectral cut with local search 2/3 edges ...`
6-cycle	`spectral cut with local search 6/6 edges ...`

Replacing this with a semidefinite-programming (Goemans–Williamson) solver would be a new handler; until then the word "spectral" stays in the detail. Theory: Approximation limits.

Vertex Cover: both ends of a maximal matching¶

vertex_cover_matching(adj) walks vertices and, for each uncovered vertex with an uncovered neighbour, adds both. That is a maximal matching's endpoints: at most twice the smallest cover, on any graph. factor_claimed=2.0. On the 6-cycle it returns 6 (the minimum is 3).

Factor 2 is the best a polynomial algorithm can promise on general graphs assuming the Unique Games Conjecture. On bipartite graphs a minimum cover can be found exactly in polynomial time (König's theorem, via maximum matching); this handler does not special-case them. Adding that would be a sound improvement.

k-median: a number, not a search¶

k_median_note() ignores the payload and returns 1 + 2/e ≈ 1.7358 as both value and factor_claimed, with detail do not claim worst-case factor below 1.7358 (catalog 125). 1 + 2/e is a hardness lower bound for metric k-median: no polynomial algorithm does better unless P = NP. No known algorithm achieves it; the best known ratios are higher. So the note means "never promise a ratio below this", not "this ratio is achievable".

Weisfeiler–Leman¶

refine(graph, k=1, limits=...) in router/wl.py:

k < 1 or k > limits.max_wl_k (default 2) raises WLRejected; the wl handler turns that into ok=False, envelope exptime_trap, for example k=5 exceeds cap 2: k-WL takes about n^(k+1) steps, so cost grows exponentially with k (catalog 133).
k = 1: colour refinement. Every vertex starts with colour 0; each round, a vertex's new colour is determined by its colour and the sorted colours of its neighbours; stop when nothing changes.
k = 2: wl2_hash, a refinement over ordered pairs of vertices (initial colour: same vertex, linked, not linked). It is a practical pairwise refinement, not guaranteed to match a textbook 2-WL index convention.
k > 2 with a raised cap (for example Limits(max_wl_k=5)) is still refused: only k = 1 and k = 2 are implemented, and running 2-WL while reporting it as k-WL would overstate what was computed. The detail is k=3 is allowed by the cap but only k <= 2 is implemented.

For fixed k, k-WL runs in polynomial time (roughly \(n^{k+1}\)). The cap is a cost budget, and the exptime_trap label means "too expensive under our budget", not that the problem is EXPTIME-hard for fixed k. Theory: Graph fingerprints.

Rational roots: always refused¶

The rational_zeros handler ignores the payload and returns ok=False, envelope undec, detail no complete algorithm for integer polynomials over Q (catalog 004), and REF_HILBERT10.to_dict() as value. Tagging the subgoal undec refuses earlier, at the dispatcher, with envelope UNDEC: refuse.

In the wider literature, Hilbert's tenth problem is undecidable over the integers (Matiyasevich, a theorem) and open over the rationals. The math catalog states the rational case as a claim (result 004, not machine-checked). Refusing is the safe choice either way: no known procedure answers every instance. Theory: Questions with no algorithm.

Compare helpers¶

Plain functions in compare/, importable from grounded_decision. Each returns a dictionary or TableSample that carries its catalog reference.

Courtade–Kumar: keep one coordinate¶

best_coordinate(bits, target) with bits of shape \((n, d)\) in \(\{0,1\}\): for each column, agreement is \(\max(\Pr[X_j = Y], \Pr[X_j \ne Y])\); the best column wins, with use_complement=True if it mostly disagrees. apply_coordinate returns that column, flipped if needed.

A product would call it to pick one yes/no feature that best predicts a target. In the wider literature, the Courtade–Kumar conjecture (that a single coordinate maximises mutual information under bit-flip noise on uniform bits) is open; the math catalog (result 119) claims it with a Lean-checked statement. The function itself is just "pick the best-agreeing column" and is correct whatever the status. The feature_selection example is circular (its target is a noisy copy of one column), so it illustrates the API, not that the method finds signal. Theory: Keeping one bit.

Optimal transport: did the distribution move?¶

w2_1d(a, b) is the exact Wasserstein-2 distance between two 1-D samples of any sizes: in one dimension the optimal plan matches quantiles, so it integrates the squared difference of the two empirical quantile functions over the merged breakpoints \(k/n\) and \(j/m\). No sample is dropped. For example, w2_1d([0, 1], [0, 1, 2]) is 0.7071 (test_w2_uses_every_sample_when_sizes_differ).

compare_outcome_laws(a, b, tau=, scale=1.0) returns w2, allowed_w2_for_map_error = scale * tau**3, maps_comparable (w2 <= allowed), exponent = 1/3 and the catalog reference (result 374: transport-map error scales like \(W_2^{1/3}\); a larger exponent fails). In 1-D the map error equals \(W_2\) itself, so the gate reduces to \(W_2 \le \text{scale}\cdot\tau^3\); it can block a pure shift such as a uniform speed-up. Theory: Did the distribution move?.

Contingency tables¶

Two rows: exact. sample_two_row(col_sums, row0, rng=) fills the top row column by column with hypergeometric draws, then sets the bottom row to the column sums minus the top:

for each column j:
    X ~ Hypergeometric(good=col_j, bad=remaining total − col_j, draws=remaining row0)
    top[j] = X; update remainders
bottom = col_sums − top

method="two_row_hypergeometric", mixer_status="exact_hypergeometric". This samples exactly from the hypergeometric distribution on tables with those margins: the distribution a Fisher exact test or permutation test needs. It is not the uniform distribution over such tables. Example, sample_two_row((10, 8, 6), 12, rng=default_rng(0)) gives [[4, 6, 2], [6, 2, 4]].

More rows: switch chain. sample_switch(row_sums, col_sums, steps=2000, rng=) starts from a greedy feasible table and applies steps random ±1 swaps on 2×2 sub-tables, keeping margins fixed. The chain is symmetric, so its long-run distribution is uniform over the tables, but nothing bounds how many steps that takes. method="switch_chain", mixer_status="switch_steps=2000_not_paper_fpras": it is not the FPRAS (fast approximate counting scheme) that catalog result 115 is about; whether such a scheme exists is open in the wider literature. Both functions take limits=: sample_two_row raises ValueError: 80 cells exceed the exact-sampling limit 64; use sample_switch for a two-row table with more than max_table_cells_exact (64) cells, and sample_switch raises ValueError: 20000 switch steps exceed the limit 10000 when asked for more than max_switch_steps. Theory: Is the A/B lift real?.

Prophet: one slot, no take-backs¶

compare/prophet.py has two rules. Both take the first value that reaches a bar, or the last value if none does, and return a ProphetChoice with factor_claimed, a guarantee sentence and lean_factor=2**-310.

single_item_max_of_samples(values, samples): the bar is the largest of one past sample per arrival (samples must be non-empty and as long as values, otherwise ValueError). With values=[1, 6, 9] and samples=[5, 2, 3] the bar is 5 and it takes index 1 (value 6). factor_claimed=0.5 is a proven guarantee for this rule (Rubinstein, Wang and Weinberg 2020): in expectation it earns at least half of the best value in hindsight, when values are independent and non-negative and each sample is drawn like its arrival. The proof is in the module docstring.
single_item_one_sample(sample, values): the bar is one scalar you choose. With sample=5 and values=[1, 6, 9] it also takes index 1. No worst-case ratio holds for an arbitrary scalar bar, so factor_claimed=None and guarantee says so.

The \(2^{-310}\) is the catalog's machine-checked constant for the matroid version (result 111): true, and too small to be useful, so it is reported and never used. Theory: One slot, no take-backs.

What `dispatch` does not do¶

It does not call Module.decide, run Lean, or start an SDP solver, a table FPRAS or a matroid prophet construction.
It does not search when the envelope is undec, whatever the payload looks like.
It does not raise on refusals (undec, exptime_trap, WL above the cap, fpras); those are ok=False results. RouterRefuse is only for an unknown name or Max-Cut with a forbidden envelope.

Adding a handler¶

Write def _my_handler(sg: Subgoal, limits: Limits) -> RouterResult in router/ and decorate it with @_register("my_name") in dispatch.py. Read caps from limits, never DEFAULT_LIMITS.
Return the weakest envelope that honestly describes the result, and put the guarantee (or its absence) in detail.
If it relies on a catalog result, add a CatalogRef in certificates.py and a theory page.
Add tests in tests/test_router_compare.py, including a refusal case.
Update interface_map() in examples/catalog.py (the router_subgoals list) and Use the hardness router.

Never call a handler from Module.decide.

Rules for changes¶

The envelope short-circuit stays at the top of dispatch.
Every reported factor must say whether it is a guarantee of this code, a conditional bound (Unique Games Conjecture), or a lower bound. Change the detail string, the theory page and the test together.
Keep mixer_status truthful: exact_hypergeometric for two rows, ..._not_paper_fpras for the chain.
Report factor_claimed=0.5 only from single_item_max_of_samples, whose guarantee is proven; keep None for the scalar-bar rule, and keep lean_factor reported.
tests/test_router_compare.py is the behavioural spec for this page.