Diagnosing Epsilon Budget Exhaustion Across Releases

Each differentially private release over the same source spends part of a finite privacy budget, and a pipeline that accounts for epsilon per release instead of cumulatively will quietly exceed the total it promised — voiding the guarantee for every release, not just the last.

Part of Privacy-Preserving Generation Frameworks: the parent page defines how a single generation run allocates a differential privacy budget across its mechanisms; this page addresses what happens across many runs over time, where composition adds those per-run costs together and an unaccounted-for total silently exhausts the budget the whole program was designed around.

Root Cause: Composition Accumulates Epsilon Across Releases

Differential privacy is a property of a mechanism, but privacy loss is a property of everything an adversary sees. A mechanism $\mathcal{M}$ is $(\varepsilon, \delta)$-differentially private when, for adjacent datasets $D, D'$ differing in one record and any output set $S$,

$$\Pr[\mathcal{M}(D) \in S] \le e^{\varepsilon}\,\Pr[\mathcal{M}(D') \in S] + \delta.$$

The trap is that when you release $k$ times over the same source, an adversary sees all $k$ outputs, and the guarantee that governs them is the composition of the mechanisms, not any single one. Under basic sequential composition, epsilons and deltas simply add:

$$\varepsilon_{\text{total}} = \sum_{i=1}^{k} \varepsilon_i, \qquad \delta_{\text{total}} = \sum_{i=1}^{k} \delta_i.$$

Ten monthly releases at $\varepsilon = 0.5$ each do not cost $\varepsilon = 0.5$; they cost $\varepsilon = 5.0$. A program that set a lifetime ceiling of $\varepsilon_{\max} = 2.0$ blew through it after the fourth release, and every release from the fifth onward carries a guarantee weaker than the one promised to data subjects. Two refinements change the arithmetic but not the principle. Advanced composition tightens the growth to roughly $\varepsilon_{\text{total}} \approx \sqrt{2k \ln(1/\delta')}\,\varepsilon + k\varepsilon(e^{\varepsilon}-1)$, sublinear in $k$ at the cost of a slack term $\delta'$. Parallel composition is the escape hatch: mechanisms applied to disjoint partitions of the source cost only the maximum of their epsilons, not the sum, because no record appears in more than one partition. The failure is not the math — it is not tracking the running total at all. A per-release check that each individual $\varepsilon_i \le \varepsilon_{\max}$ passes forever while the composed total climbs without limit.

The diagnosis, therefore, is an accounting problem. You need a persistent ledger that records the epsilon and delta of every release against a source, knows whether each new release is sequential (same or overlapping data) or parallel (disjoint partition), and computes the composed total the way an adversary would. The per-coordinate mechanics of spending that budget live in implementing differential privacy for coordinate generation, and the choice between Laplace, Gaussian, and their composition behaviour is compared in differential privacy mechanisms compared for spatial data; this page assumes those choices are made and focuses on adding them up correctly over time.

Prerequisite Check: See the Total the Per-Release Check Misses

Reproduce the blind spot. A guard that only checks each release’s individual epsilon against the ceiling passes indefinitely while the composed total marches past it.

pythonCopy
# requirements.txt — pin majors; let patch releases float
numpy==1.26.*

pythonCopy
releases = [0.5, 0.5, 0.5, 0.7, 0.6]   # epsilon spent by five sequential releases
EPS_MAX = 2.0

# The naive per-release guard — passes every time:
for i, eps in enumerate(releases, 1):
    assert eps <= EPS_MAX, f"release {i} over budget"   # 0.7 <= 2.0, always fine
print("per-release guard: all releases OK")

# What the adversary actually sees (basic sequential composition):
cumulative = 0.0
for i, eps in enumerate(releases, 1):
    cumulative += eps
    flag = "  <-- BUDGET EXHAUSTED" if cumulative > EPS_MAX else ""
    print(f"after release {i}: composed eps = {cumulative:.1f}{flag}")
# after release 4: composed eps = 2.2   <-- BUDGET EXHAUSTED

The per-release guard is the exhaustion bug in miniature: it never sees the sum, so it never fails, while the real guarantee was voided at release four.

Fix: A Persistent Epsilon Ledger with Composition-Aware Accounting

The fix is a ledger that persists across releases, records each spend with the partition it touched, and composes the total using the correct rule. Sequential spends over overlapping data add; parallel spends over disjoint partitions take the maximum within each partition group.

Step 1 — Record every spend. Each entry carries the epsilon, delta, a timestamp, and a partition key identifying which slice of the source it touched. Persist the ledger (a JSON file, a table) so it survives across CI runs and releases.

pythonCopy
import json
from dataclasses import dataclass, asdict
from pathlib import Path

@dataclass(frozen=True)
class Spend:
    release_id: str
    epsilon: float
    delta: float
    partition: str        # disjoint partition key; "GLOBAL" means whole source
    ts: str

class BudgetLedger:
    def __init__(self, path: Path):
        self.path = Path(path)
        self.entries: list[Spend] = [
            Spend(**e) for e in json.loads(self.path.read_text())
        ] if self.path.exists() else []

    def record(self, spend: Spend) -> None:
        self.entries.append(spend)
        self.path.write_text(json.dumps([asdict(e) for e in self.entries], indent=2))

Step 2 — Compose within and across partitions. Group spends by partition; within a group they are sequential and add; across disjoint groups they are parallel and the total is the maximum group cost. This is the accounting the privacy-preserving generation frameworks contract requires every release to honour.

pythonCopy
from collections import defaultdict

def composed_epsilon(entries: list[Spend]) -> float:
    """Sequential within a partition (sum); parallel across partitions (max)."""
    per_partition: dict[str, float] = defaultdict(float)
    for e in entries:
        per_partition[e.partition] += e.epsilon      # same records -> add
    return max(per_partition.values(), default=0.0)  # disjoint slices -> take the max

def composed_delta(entries: list[Spend]) -> float:
    per_partition: dict[str, float] = defaultdict(float)
    for e in entries:
        per_partition[e.partition] += e.delta
    return max(per_partition.values(), default=0.0)

Step 3 — Admit a release only if it fits. Before publishing, simulate the spend against the ledger and refuse it if the projected composed total would breach either ceiling. Refusing before the write is what keeps the guarantee intact rather than discovering the breach afterward.

pythonCopy
def can_release(ledger: BudgetLedger, spend: Spend, *,
                eps_max: float, delta_max: float) -> tuple[bool, float]:
    projected = ledger.entries + [spend]              # what the total WOULD be
    eps = composed_epsilon(projected)
    ok = eps <= eps_max and composed_delta(projected) <= delta_max
    return ok, eps

Verification Step: Block Over-Spending Releases in CI

Turn admission into a build gate. The CI job loads the persisted ledger, projects the pending release, and fails the build if it would exhaust the budget — so an over-spending release cannot merge, let alone publish. This is the privacy counterpart to the black-box check in running membership inference attacks on synthetic geodata: the ledger proves the budget was respected, the attack confirms the data behaves as if it was.

pythonCopy
import pytest
from datetime import datetime, timezone

EPS_MAX, DELTA_MAX = 2.0, 1e-5

def test_release_blocked_when_budget_exhausted(tmp_path):
    ledger = BudgetLedger(tmp_path / "budget.json")
    now = lambda: datetime.now(timezone.utc).isoformat()

    # Three sequential releases over the GLOBAL source: composed eps = 1.5, still fine.
    for i, eps in enumerate([0.5, 0.5, 0.5], 1):
        spend = Spend(f"r{i}", eps, 2e-6, "GLOBAL", now())
        ok, total = can_release(ledger, spend, eps_max=EPS_MAX, delta_max=DELTA_MAX)
        assert ok, f"release {i} wrongly blocked at composed eps {total}"
        ledger.record(spend)

    # Fourth sequential release pushes composed eps to 2.2 > 2.0 -> must be blocked.
    over = Spend("r4", 0.7, 2e-6, "GLOBAL", now())
    ok, total = can_release(ledger, over, eps_max=EPS_MAX, delta_max=DELTA_MAX)
    assert not ok and total == pytest.approx(2.2), "over-spending release was not blocked"

    # The SAME epsilon on a DISJOINT partition is admissible: parallel composition.
    parallel = Spend("r4b", 0.7, 2e-6, "REGION_NORTH", now())
    ok, _ = can_release(ledger, parallel, eps_max=EPS_MAX, delta_max=DELTA_MAX)
    assert ok, "disjoint-partition release wrongly blocked"

The disjoint-partition assertion is the load-bearing subtlety: the gate must block 0.7 more on the global source yet admit the same 0.7 on a region that shares no records, because parallel composition costs the maximum, not the sum. A gate that treats every release as sequential is safe but needlessly starves the budget.

Edge Cases & Gotchas

Partitions that are not actually disjoint. Parallel composition only applies when no record appears in two partitions. If a spatial partition is defined by a bounding box and a moving object crosses the boundary, its record lands in both partitions and the two spends are no longer parallel — they must be summed. Antimeridian-spanning partitions are the classic trap: a box “east of 170°E” and one “west of 170°W” both claim the strip across the Pacific. Define partitions by a total, gap-free, overlap-free key (an H3 cell id, an administrative code) and assert the partition function is a true surjection before trusting the max rule.

Delta accumulates too, and advanced composition adds its own. It is easy to watch epsilon and forget delta, but delta sums under sequential composition and advanced composition introduces an additional slack term $\delta'$ beyond the sum of per-release deltas. A program that gates only on epsilon can satisfy the epsilon ceiling while the composed delta drifts above its own limit, weakening the failure-probability side of the guarantee. Gate on both, and if you use advanced composition account for the extra $\delta'$ explicitly.

Re-releasing a corrected dataset. Publishing a fixed version of a release over the same source is a new release, not a replacement — the adversary saw both. Deleting the buggy release from the ledger does not un-observe it. Mark superseded releases as still-spent rather than removing them, so the composed total reflects everything an adversary could have downloaded, including the version you wish you had never shipped.

Frequently Asked Questions

Related

• Privacy-Preserving Generation Frameworks — how a single run allocates the budget this ledger tracks over time.
• Implementing Differential Privacy for Coordinate Generation — the per-coordinate mechanics of spending each release’s epsilon.
• Differential Privacy Mechanisms Compared for Spatial Data — how mechanism choice changes composition behaviour and cost.
• Adversarial Privacy Testing for Synthetic Spatial Data — the empirical check that the tracked budget actually held.