Privacy–Utility Trade-off Measurement

Every privacy control on a spatial pipeline is a trade, and almost every team makes that trade without measuring either side of it. The privacy side at least has a number — an $\varepsilon$, a $k$, a cell edge in metres — but the utility side is usually defended with a screenshot of a map that “still looks right”. That asymmetry is why parameter arguments never resolve: one party quotes a guarantee and the other quotes an impression. This guide replaces the impression with a measured quantity. It sits under Core Fundamentals & Architecture for Spatial Privacy and feeds the routing thresholds set by the spatial sensitivity scoring models, the caps enforced by privacy budget management, and the architecture choice worked through in the privacy model comparison.

The concrete engineering scenario throughout is a metro mobility team publishing an hourly origin–destination matrix and a hotspot map from device pings. They need to answer one question with evidence: what does this release lose, and at which parameter setting does it stop being worth publishing?

Prerequisites

• A held-out extract you are willing to treat as truth. Measurement compares a protected release against an unprotected one, so the ground-truth extract is itself sensitive and must live inside the trust boundary, be access-controlled, and never be published. Teams that skip this because “we can’t hold raw data” end up with no measurement at all.
• numpy, geopandas, shapely, and h3 for binning and geometry; scipy.stats for rank correlation. No modelling framework is required — every metric here is arithmetic over two arrays.
• A named downstream task. “Utility” is not a property of a dataset; it is a property of a dataset with respect to a question. Write the question down first: “which 20 cells should get extra buses on a Tuesday evening” is measurable; “the map should look right” is not.
• A fixed privacy unit and accounting method. Utility numbers computed under a device-day unit are not comparable with numbers computed under an event-level unit, so record the unit alongside every measurement.

Step 1: Define the utility vector, not a utility number

There is no single utility scalar, and forcing one hides the failure that matters. Use a small vector of task-aligned metrics, each with an independent threshold, and require all of them to pass.

Relative error is the metric everyone reaches for first and the one that most often misleads. It is dominated by small cells, where the noise is comparable to the count, and those cells are usually the ones nobody acts on. Reporting a single MRE across all cells therefore fails releases that are perfectly fit for purpose. Compute it conditioned on the reporting floor: over cells whose true count clears the threshold at which anyone would act on the number.

Decision agreement is the metric almost nobody computes and the only one that speaks the language of the people who approve the release. Encode the downstream decision as a function of the data — “deploy extra capacity where the noisy count exceeds 400” — apply it to both the truth and the release, and report the fraction of cells where the two decisions agree. A release whose counts are 20% off but whose decisions match 99% of the time is a good release; one whose counts are 3% off but whose decisions flip on a third of the borderline cells is not.

Step 2: Sweep the parameter grid, do not guess a point

Utility is not monotone in a single parameter, because resolution, $\varepsilon$ and the anonymity floor interact: a finer grid raises relative error but lowers suppression bias, and a higher floor does the reverse. The only reliable approach is a sweep over the cross-product, evaluated on the held-out extract, with several noise draws per point so the numbers are not one lucky sample.

from __future__ import annotations

import itertools
from dataclasses import dataclass
from typing import Callable, Iterable, Sequence

import numpy as np


@dataclass(frozen=True)
class ParamSet:
    """One point on the sweep grid."""

    resolution: int          # H3 resolution used for binning
    epsilon: float           # per-release budget for the whole grid
    k_min: int               # anonymity floor; cells below it are suppressed


@dataclass(frozen=True)
class Utility:
    """The utility vector for one parameter set (means over the draws)."""

    mean_rel_error: float
    topk_agreement: float
    suppression_rate: float
    decision_agreement: float

    def passes(self, slo: "Utility") -> bool:
        return (
            self.mean_rel_error <= slo.mean_rel_error
            and self.topk_agreement >= slo.topk_agreement
            and self.suppression_rate <= slo.suppression_rate
            and self.decision_agreement >= slo.decision_agreement
        )


def evaluate(
    truth: np.ndarray,
    params: ParamSet,
    *,
    decision: Callable[[np.ndarray], np.ndarray],
    draws: int = 25,
    report_floor: float = 25.0,
    k: int = 20,
    seed: int = 0,
) -> Utility:
    """Measure one parameter set over `draws` independent noise realisations.

    `truth` is the unprotected per-cell count vector at this resolution. The noise
    is calibrated to sensitivity 1 under a device-day privacy unit, which is only
    valid because contributions were clipped upstream — without that clipping the
    scale below understates the real sensitivity.
    """
    rng = np.random.default_rng(seed)
    scale = 1.0 / params.epsilon
    actionable = truth >= report_floor
    true_top = set(np.argsort(-truth)[:k].tolist())
    true_decision = decision(truth)

    rel_errors, agreements, suppressions, decisions = [], [], [], []
    for _ in range(draws):
        noisy = truth + rng.laplace(0.0, scale, size=truth.shape)
        released = np.where(noisy >= params.k_min, np.maximum(noisy, 0.0), np.nan)

        observed = np.nan_to_num(released, nan=0.0)
        rel_errors.append(
            float(np.mean(np.abs(observed[actionable] - truth[actionable]) / truth[actionable]))
        )
        noisy_top = set(np.argsort(-observed)[:k].tolist())
        agreements.append(len(true_top & noisy_top) / k)
        suppressions.append(float(np.mean(np.isnan(released)[truth > 0])))
        decisions.append(float(np.mean(decision(observed) == true_decision)))

    return Utility(
        mean_rel_error=float(np.mean(rel_errors)),
        topk_agreement=float(np.mean(agreements)),
        suppression_rate=float(np.mean(suppressions)),
        decision_agreement=float(np.mean(decisions)),
    )


def sweep(
    truth_by_resolution: dict[int, np.ndarray],
    resolutions: Sequence[int],
    epsilons: Sequence[float],
    k_mins: Sequence[int],
    *,
    decision: Callable[[np.ndarray], np.ndarray],
    slo: Utility,
) -> list[tuple[ParamSet, Utility, bool]]:
    """Evaluate the full cross-product and mark which points clear the SLO."""
    out: list[tuple[ParamSet, Utility, bool]] = []
    for res, eps, kmin in itertools.product(resolutions, epsilons, k_mins):
        params = ParamSet(resolution=res, epsilon=eps, k_min=kmin)
        util = evaluate(truth_by_resolution[res], params, decision=decision)
        out.append((params, util, util.passes(slo)))
    return out


def _self_test() -> None:
    rng = np.random.default_rng(7)
    truth = np.clip(rng.lognormal(mean=4.4, sigma=1.1, size=800), 0, None)
    by_res = {8: truth, 9: truth / 7.0}
    decide = lambda counts: counts >= 400.0

    slo = Utility(mean_rel_error=0.05, topk_agreement=0.90,
                  suppression_rate=0.10, decision_agreement=0.95)
    results = sweep(by_res, [8, 9], [0.5, 1.0, 2.0], [5, 10], decision=decide, slo=slo)

    assert len(results) == 12, "the sweep must evaluate the full cross-product"
    # Utility is monotone in epsilon at a fixed grid: more budget, less error.
    at_res8 = {(p.epsilon, p.k_min): u for p, u, _ in results if p.resolution == 8}
    assert at_res8[(2.0, 5)].mean_rel_error < at_res8[(0.5, 5)].mean_rel_error
    # A finer grid at the same epsilon is strictly worse for relative error.
    coarse = [u for p, u, _ in results if p.resolution == 8 and p.epsilon == 1.0][0]
    fine = [u for p, u, _ in results if p.resolution == 9 and p.epsilon == 1.0][0]
    assert fine.mean_rel_error > coarse.mean_rel_error
    print("privacy-utility sweep: assertions passed")


_self_test()

The sweep returns a frontier, not a winner. Read it by discarding every point that fails the SLO, then choosing the cheapest surviving point in privacy terms — the smallest $\varepsilon$ and the coarsest grid that still passes. Teams routinely do the opposite, picking the point with the best utility that is “still private enough”, which spends budget for accuracy nobody asked for.

Step 3: Separate the three sources of error

When a release fails its SLO, the fix depends entirely on which of three mechanisms caused the loss, and they are distinguishable by measurement rather than by inspection.

• Noise error is symmetric, zero-mean, and scales as $1/\varepsilon$ independently of the count. Diagnose it by re-running the sweep at a much larger $\varepsilon$: if the metric recovers, noise was the cause, and more budget or a coarser grid will fix it.
• Truncation and clipping bias is one-sided. Clamping negative noisy counts to zero inflates empty areas; clipping per-device contributions deflates dense ones. Diagnose it by comparing the sum of the release with the sum of the truth: noise alone leaves the total roughly unchanged, so a systematic gap is bias, and it does not shrink with more draws.
• Suppression bias deletes cells non-randomly — always the sparse ones. Diagnose it by computing each metric twice, once over all cells and once over the surviving cells only. A metric that looks excellent on survivors and poor overall is telling you the release is fine and that a third of the map is gone, which is a different conversation with the analyst.

The three failures have opposite remedies, which is why lumping them into “the release is too noisy” leads to spending budget on a problem budget cannot solve. Suppression bias in particular gets worse with more budget at a fixed floor, because a higher $\varepsilon$ does nothing about a cell that holds three people.

Threat model considerations

Measurement itself touches raw data and produces numbers that are published in release notes, so it carries its own disclosure risk.

• The utility report is a side channel. “Suppression rate rose from 6% to 24% this week” is a statement about the underlying distribution, and an adversary tracking those reports learns about changes in sparse areas. Round reported utility metrics, publish them on a delay, or account for them under the same ledger as any other release.
• Tuning on the production extract is adaptive data analysis. Every sweep evaluated against the same held-out data leaks a little of it into the chosen parameters, and after enough iterations the parameters themselves encode the data. Rotate the held-out extract, or budget the tuning as a release in its own right.
• A published parameter set is an attack input. Once $\varepsilon$, the grid resolution and the floor are public — and they should be, for accountability — an adversary can model the noise distribution exactly and de-noise across repeated releases. Publishing parameters is correct; it just means the composition accounting has to be correct too.
• Ground-truth extracts outlive their purpose. The measurement corpus is the most sensitive artefact the pipeline holds and the one least likely to appear in a retention policy. Give it the shortest lifetime that still allows a regression comparison, and delete on schedule.

Validation and compliance checklist

1. Every metric names a task. Reject any utility metric that cannot be traced to a decision someone makes. Pass criterion: each metric in the vector has a named downstream consumer.
2. Draws, not a draw. Every reported utility number is a mean over at least 20 independent noise realisations, with the standard deviation reported alongside. Pass criterion: no single-draw numbers appear in the release record.
3. Conditioned error. Relative error is reported conditioned on the reporting floor, and the floor is stated. Pass criterion: the floor appears in the same table as the metric.
4. Bias is separated from noise. The release record includes the total-sum gap and the suppression rate, not only a symmetric error metric. Pass criterion: both fields are non-null.
5. The frontier is recorded. The chosen parameter set is justified against the sweep as the cheapest passing point, and the full sweep is archived. Pass criterion: the archived sweep contains at least one failing point on each side of the chosen one.
6. Utility SLOs are versioned with the pipeline. A change to a threshold is a reviewed change, not a config edit. Pass criterion: the SLO file is under the same review policy as the mechanism.

Failure modes and remediation

• The metric improves while the map gets worse. Almost always suppression: cells that would have dragged the average are gone, so the average over survivors improves. Remediate by always reporting the paired all-cells and survivors-only numbers.
• Utility collapses at a resolution step and nothing else changed. The knee in the suppression curve was crossed. Remediate by moving one resolution coarser rather than raising $\varepsilon$ — it is free in privacy terms and usually recovers the whole loss.
• Measurements are not reproducible between runs. The noise seed is not pinned, or the held-out extract changed underneath the comparison. Remediate by pinning both and recording their hashes in the release record.
• The SLO passes but analysts complain. The measured task is not the task they perform. This is a specification failure, not a mechanism failure: sit with the consumer, watch what they actually do with the release, and add that as a metric.
• Tuning drifts toward ever-larger budgets. Nobody is enforcing the “cheapest passing point” rule. Remediate by making the sweep artefact a required input to release approval, so a chosen point that is not on the frontier has to be defended explicitly.

One further discipline is worth naming because it is where measurement programmes usually decay: keep the sweep artefact and the release record in the same place, versioned together. A utility number that cannot be traced back to the extract it was measured on, the seed it used and the parameter set it justified is an assertion rather than evidence, and six months later nobody will be able to reconstruct which of the three changed. The archive is small — a few kilobytes of JSON per release — and it is the difference between a parameter choice you can defend and one you have to re-derive under pressure.

Frequently Asked Questions

Related

• Privacy Budget Management — the ledger that the chosen $\varepsilon$ is debited against.
• Spatial Sensitivity Scoring Models — where the resolution floor for each risk tier comes from.
• Privacy Model Comparison for Spatial Analytics — choosing the architecture whose trade-off you are measuring.
• Differentially Private Spatial Aggregation — the mechanism most often under measurement here.

Up one level: Core Fundamentals & Architecture for Spatial Privacy.