We present Caliber, an output-perturbation defense against model extraction that formulates noise selection as a calibration problem: how much the defense degrades the supervision signal used to train a surrogate, and the provable per-input query cost of recovering the clean logits. To defend against an attacker that uses returned scores for knowledge distillation, Caliber adds independent and identically distributed Gaussian noise to the internal logits. We establish two properties of the resulting perturbed predictions. Monotone agreement degradation: When the clean logits have a unique maximizer, agreement with the clean prediction decreases strictly with the noise scale, so every target in $(1/K,1)$ corresponds to a unique positive scale; task accuracy is bounded by computable lower and upper envelopes. Per-input recovery cost: We derive a closed-form minimax lower bound on the repeated queries needed to recover the clean logits for a fixed input. Caliber normalizes noise variance by the squared median top-two logit margin and fits the resulting noise-utility relationship with a logistic curve, either per model or shared within a task. Across more than thirty model-dataset combinations, per-model calibration achieves mean absolute relative errors of 0.6-1.4%. End-to-end experiments show that surrogate performance generally tracks the configured degradation, while fixed-input averaging follows the expected variance reduction.
Differential privacy (DP) ensures rigorous individual-level privacy guarantees against even the most knowledgeable attackers, but its worst-case nature can impose a costly privacy-accuracy tradeoff. We introduce privacy via predictability, a fine-grained framework that explicitly incorporates the attacker's core knowledge, a compromised portion of the dataset generated by a stochastic process, and a specified family of queries. Predictability measures privacy leakage as the incremental gain in an attacker's ability to predict sensitive information about unknown individuals after observing the algorithm's output, beyond what can already be inferred from the compromised data. We show that predictability and DP are generally incomparable: each can be small while the other is large. However, in the worst-case regime where all but one individual is compromised, and all binary queries are considered sensitive, predictability implies mutual-information DP. More generally, predictability provides a finer-grained privacy metric tailored to specific sensitive information and specific attacker models. We introduce a general framework, using the generalized method of moments (GMM), to analyze asymptotic predictability when the compromised data is generated by a stationary, ergodic, mixing process. Using this analysis, we derive a predictability-calibrated output perturbation scheme for ERM. Our approach is complementary to DP and can be used alongside DP to provide fine-grained privacy control.