LAPRAS — Learning-Augmented Private Answering for Linear Query Streams

The premise

Privacy budgets are finite. Predictions can stretch them.

Modern database workloads are highly predictable — recurring jobs, dashboards, templated drill-downs. Yet most online differentially-private mechanisms treat each query as if it arrived from nowhere. LAPRAS asks a sharper question: given an oracle hint about which queries are likely to arrive, can we spend privacy budget like the offline Matrix Mechanism — and still degrade gracefully when the oracle is wrong?

Without predictions

Online DP mechanisms add independent noise per query, so error scales linearly with stream length. The optimal Matrix Mechanism sits offline, out of reach, because the workload isn't known in advance.

→

With LAPRAS

An oracle predicts a likely query set P. LAPRAS runs the Matrix Mechanism on P offline, caches its low-noise releases, and adapts to the unpredicted remainder online from a residual budget.

🎯

Consistency

When the oracle is accurate (high overlap), LAPRAS approaches near-offline-optimal utility — over an order of magnitude lower MAE than online baselines on Adult and Gowalla.

🛡️

Robustness

When the oracle is wrong (low overlap), LAPRAS stays comparable to standard online Independent-Noise mechanisms. No catastrophic failure when predictions don't materialize.

🌊

Smooth Allocation

An online stopping-time estimator from T = ceil(log2 S)^2 bad-query positions continuously recalibrates per-query spend — without violating composition.

(ε, δ)-Differential Privacy Matrix Mechanism Negative Hypergeometric Estimator Adaptive Composition Consistency + Robustness

The framework

How LAPRAS works

Step through the algorithm — from oracle prediction to adaptive online streaming.

Oracle / Predictor

history · ML · heuristic

→

Predicted set P

queries likely to appear

→

Realized stream S

arrives in random order

LAPRAS treats the oracle as a black box — any predictor is admissible. Quality is summarized by prediction overlap ρ: the fraction of stream queries also in P. Queries in P ∩ S are good (G); queries in S \ P are bad (B = S − G). We assume the realized stream is a uniformly random permutation — the load-bearing assumption behind the unbiased stopping-time estimator.

Predicted set P

Budget ε_MM

→

Matrix Mechanism
offline · SDP-optimal A

→

Cached answers

low-noise · correlated

Before the stream begins, LAPRAS solves the Matrix-Mechanism SDP (Li, Hay, Rastogi, Miklau & McGregor, 2010) on P with budget ε_MM, producing a low-noise correlated release. When a good query later arrives, it is answered from the cache — at zero additional privacy cost by post-processing.

Matrix Mechanism release y_hat_MM = W A+ ( A x + N(0, sigma^2 I) ), sigma ~ ||A||_col * sqrt(2 ln(2/delta)) / eps_MM

Queries arrive one by one. Good = predicted (free via the cache). Bad = unpredicted (consumes residual budget).

Good (∈ P) — free via MM cache

Bad (∉ P) — spends from bad pool

The challenge: the residual budget ε − ε_MM must cover an unknown number of bad queries. LAPRAS exploits the random-order assumption to estimate that count online (see the next panel and the interactive sandbox below).

⚓ Static — fixed allocation

Static

ε_MM

ε_init

ε_bad

ε_res

🌊 Smooth — merged residual pool

Smooth

ε_MM

ε_pool · merged

ε_init

ε_bad

ε_res

ε_MM · matrix mechanism on P

ε_init · warmup (T bad queries)

ε_bad · per-query bad pool

ε_res · safety reserve

Practical guidance. Use query-heavy when ρ ≤ 0.5 (more budget for surprises) and matrix-heavy when ρ ≥ 0.8 (the MM investment dominates). Smooth merges the three online pools, allowing per-query ε to be derived from a single running estimator rather than four pre-committed slices.

⚓ LAPRAS Static

Per-bad-query ε fixed using B-hat = S * (T - 1) / (n - 1) at the T-th bad arrival.
Conservative: locks one density estimate and never re-fits.
Wins below ρ ≈ 0.5 — uniform allocation avoids committing to wrong predictions.

🌊 LAPRAS Smooth

Per-query ε = eps_pool / (B-hat_rem + 1), updated after every bad query.
The +1 ratchet regularizes early estimates against overspending.
Wins above ρ ≈ 0.5 — up to 40% lower MAE than Static at high overlap.

Both methods converge identically at ρ = 1.0 (no bad queries). The crossover at ρ ≈ 0.5 holds across all four budget strategies — a remarkable invariant we explore in the experiments below.

Interactive sandbox

The stopping-time estimator

The novel theoretical contribution of LAPRAS: an unbiased online estimator B-hat = S * (T - 1) / (n - 1) of the unknown total bad-query count B, formed from the position n at which the T-th bad query arrives, with T = ceil(log2 S)^2. Adjust the controls below to see it lock and converge.

Sandbox parameters

Stream length S 100

Bad-query rate 0.50

Budget strategy matrix-heavy

Stream speed 120 q/s

T = ceil(log2 S)^27

n (current)0

B (true)50

B-hat (locked at T)—

Bad seen · b0

Static · post-warmup eps_per_bad = eps_bad / (B-hat - T)

Smooth · per query b eps_b = eps_rem / (B-hat_rem + 1)

Live stream tape

B-hat(b) convergence vs true B

Per-bad-query eps · Static vs Smooth (log scale)

What's happening. Bad queries arrive at random positions. When the T-th one lands at position n, the unbiased estimator B-hat = S * (T - 1) / (n - 1) locks. Static commits to that estimate for the rest of the stream; Smooth keeps recalibrating B-hat_rem after every subsequent bad query, redistributing the residual budget on the fly.

Experiments

LAPRAS vs the baselines

Evaluated on Adult, Gowalla, and IDEBench/Flights workloads (ε = 1.0, δ ∈ {10⁻⁵, 10⁻¹⁰}, 5 runs per setting, error bars = ±1σ). Baselines: Offline MM (knows the full stream — theoretical optimum), Online IndepNoise (independent Gaussian noise per query).

10×+

MAE reduction at high overlap (Adult)

~0.5

Crossover overlap, Static → Smooth

61%

Smooth gain on IDEBench at ρ = 0.5

≤1.6×

Bounded degradation under adversarial order

Budget strategy

MAE vs prediction overlap — Gowalla

P=50 · Q=50 · ε=1.0 · δ=10⁻¹⁰ · ±1σ over 5 runs

LAPRAS Smooth — strategy comparison

How budget allocation reshapes Smooth's error profile across overlaps

At high overlap (ρ ≈ 1): LAPRAS Smooth approaches the offline-optimal Matrix Mechanism, reducing MAE by an order of magnitude over Online IndepNoise. At low overlap (ρ ≈ 0): performance stays within a few percent of IndepNoise — robustness intact.

Static vs Smooth — every strategy crosses at ρ ≈ 0.5

P=50 · Q=50 · matrix-heavy split shown · the crossover invariant

Smooth's improvement over Static (% reduction in MAE)

Same setting, expressed as relative gain — peaks at ~+40% near ρ = 0.9

The crossover is remarkably stable. Across equal, matrix-heavy, query-heavy, and reallocate, Smooth begins outperforming Static at ρ ≈ 0.5 and the gap monotonically widens — culminating in ~40% lower MAE at ρ = 0.9 under matrix-heavy.

MAE vs overlap by predicted-set size P

P ∈ {50, 100} · matrix-heavy · LAPRAS Smooth · larger P helps at high ρ

SDP precompute time vs P · ~O(P^1.5)

Matrix-Mechanism setup cost · query_heavy · S=100

Overlap dominates; P is secondary. Doubling P at fixed overlap barely moves MAE, but the SDP precompute scales superlinearly: ~186s @ P=50 → ~875s @ P=500. Pick P just large enough to cover expected good queries; further padding burns CPU without significant utility return.

Adversarial ordering · bad queries arrive first

P=100 · Q=100 · matrix-heavy · breaks the random-order assumption deliberately

Smooth / Static MAE ratio under bad-first

Worst-case ≈ 1.6× at ρ = 0.6 — degrades gracefully, not catastrophically

Worst-case ordering doesn't break Smooth. The estimator assumes uniform random order, but even when all bad queries are front-loaded, Smooth's degradation versus Static stays bounded at ≈1.6×. Matrix-heavy is the most adversarially-resilient split — the heavy MM investment provides a stable answer floor.

Static vs Smooth vs Smooth+Cache

P=100 · Q=50 · matrix-heavy · bad queries projected onto cached span at zero cost

Cache win-rate by budget strategy (MAE, P=100, Q=50)

Smooth+Cache wins majority of overlap points; matrix-heavy benefits most

Reusing prior answers as a linear span. Smooth+Cache projects each bad query onto already-released MM and bad-query answers via least-squares; if the residual is small, the answer is post-processing and costs zero additional ε. Most effective at moderate-to-high overlap — the MM-rich cache is hardest to escape.

IDEBench / Flights · ORIGIN_STATE_ABR family

P=50 · Q=100 · matrix-heavy · 159-query universe from real interactive exploration

MAE at ρ = 0.5 — the headline IDEBench claim

Smooth's 61% reduction over Static, with Offline MM as reference

Real-world workload, same trends. Derived from the IDEBench interactive-exploration benchmark via the CacheDP reduction (each visualization → its constituent linear count queries). At ρ = 0.5 LAPRAS Smooth hits MAE 50.4 vs Static's 129.7 — a 61% reduction. Both methods converge at ρ = 1.0 to MAE ≈ 11.5.

More results · CacheDP, normalized metrics, strategy heatmap

LAPRAS vs CacheDP · NMAE (lower is better)

Adult / country · ε=1.0 · δ=10⁻¹⁰ · same global budget · CacheDP-warmed-with-P

Strategy heatmap · Smooth MAE

Gowalla · which strategy wins at each overlap

ρ	LAPRAS Static · NMAE	LAPRAS Smooth · NMAE	Offline MM · NMAE	CacheDP · NMAE
0.0	0.0019	0.0026	0.0002	0.2076
0.5	0.0007	0.0011	0.0001	0.1242
1.0	0.0014	0.0014	0.0002	0.0588

CacheDP splits ε across many independent releases, accumulating noise per query; LAPRAS jointly optimizes the predicted-set workload via the Matrix Mechanism, achieving roughly two orders of magnitude lower normalized error at the same global budget.

LAPRAS: Learning-Augmented Private Answering for Linear Query Streams