Bayesian Perspective on Memorization and Reconstruction

Haim Kaplan; Kobbi Nissim; Uri Stemmer; Yishay Mansour

REVIEW 3 major objections 4 minor 20 references

Bayesian Perspective on Memorization and Reconstruction

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Some statistical memorization provably resists reconstruction

desk verdict A real formal separation of statistical memorization from extractability, but the headline interpretive claim about FPC rests on a surprisal filter the authors openly concede is arbitrary. read the letter →

arxiv 2505.23658 v1 pith:IBQV2WXK submitted 2025-05-29 cs.CR cs.LG

Haim Kaplan , Yishay Mansour , Kobbi Nissim , Uri Stemmer This is my paper

classification cs.CRcs.LG

keywords Bayesianextraction-safetyreconstructionattacksmembershipinferencefingerprintingcodesstatisticalmemorizationdifferentialprivacysurprisalTardosprior

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that statistical memorization and computational extractability are different things: there are settings where a released statistic provably encodes a dataset (high mutual information, easy membership inference) yet no attacker, even unbounded, can reconstruct a training example from it. To make this precise, the authors introduce Bayesian extraction-safety, a security definition that counts an attack only if the recovered element was not already predictable from the attacker's side information, measured via surprisal. Under a well-known hard prior from fingerprinting-code attacks, they prove that releasing the exact average of a sample resists near-exact reconstruction, and that a per-coordinate noisy average resists reconstruction even when the attacker holds substantial side information. The upshot is that fingerprinting-code attacks should be classified as membership inference rather than reconstruction, and the impossibility results built on them do not apply if one only wants to prevent reconstruction.

What carries the argument

The machinery is a Bayesian redefinition of what counts as a successful reconstruction. The paper defines Bayesian extraction-safety by comparing success against a true sample $S$ with success against a fresh sample $T$ drawn from the same underlying distribution Nature, and, in the full definition, requires that the recovered element $z$ satisfy the surprisal condition $h(z|K,S\setminus\{z\}) \ge \xi \cdot h(z|S\setminus\{z\})$, meaning the attacker's side information $K$ did not already almost determine $z$. The proof engine combines concentration arguments on lukewarm columns (columns whose Hamming weight lies between $n/4$ and $3n/4$) with Laplace's rule of succession to show that any candidate row has surprisal $\Omega(d)$, and uses differential privacy of per-coordinate noise to bound the probability that the noisy average changes the identity of a recovered row. This is what lets the paper show both the positive results and the observation that the exact average fails under side information.

What would settle it

Set the fingerprinting-code prior with $N=10n$, large $d$, release either the exact or the noisy average, and give the attacker side information consisting of $n-1$ rows of the sample; if the attacker can recover the missing row with probability noticeably above the baseline while the recovered row satisfies the surprisal condition $h(z|K,S\setminus\{z\}) \ge \xi h(z|S\setminus\{z\})$, then the security claim fails. Observation 4.2 already shows the attack succeeds without the surprisal filter, so the concrete test is whether the same attack clears that filter.

Watch

Extended reading notes

Core claim

The paper's central claim is that there are well-established cases of statistical memorization in which extraction is provably impossible, and that if the goal is solely to prevent reconstruction—not membership inference—the impossibility results derived from fingerprinting-code attacks no longer apply. On the paper's own terms: for the marginals problem under the fingerprinting-code prior, the exact average is Bayesian extraction-safe with respect to Hamming-distance reconstruction for distances up to $d/25$, and with a bi-criteria relation it is safe for any radius $\gamma$ against a relaxed baseline; once arbitrary side information about the sample is allowed, the exact average fails, but a noisy average with independent per-coordinate Laplace noise is secure under the surprisal-based definition. Because this security is achieved with per-attribute differential privacy and requires no composition across the $d$ coordinates, the dataset size need not grow polynomially with dimension, in contrast with membership-inference defenses. The paper concludes that the documented necessity of memorization in stochastic convex optimization is better read as necessity of membership-inference vulnerability, not of extractability.

Load-bearing premise

The load-bearing premise is the definitional choice that an attack counts as reconstruction only when the recovered element has high surprisal given the attacker's side information—the paper itself notes in Remark 4.5 that this comparison is somewhat arbitrary.

Editorial extensions

If this is right

For the marginals problem under the fingerprinting-code prior, releasing the exact average provably prevents near-exact reconstruction, so unbounded attackers cannot recover a training row within Hamming distance $d/25$.
With the bi-criteria variant, reconstruction at radius $\gamma$ is prevented while the baseline allows only a slightly relaxed radius, so the release gives the attacker essentially no new reconstructive power.
If the attacker holds side information consisting of most of the sample, the exact average is not secure, but the noisy average with per-coordinate Laplace noise remains secure under the surprisal condition.
Protecting against reconstruction can be significantly easier than protecting against membership inference: the noisy-average construction needs no privacy-composition cost across the $d$ features, whereas membership-inference defenses under the same prior require dataset size to grow polynomially with $d$.
The paper's reinterpretation implies that polynomial lower bounds on dataset size for stochastic convex optimization stem from membership-inference vulnerability, not from the need to prevent extraction.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the surprisal threshold is accepted, many published extraction attacks on language and image models may be reclassified as membership inference when the target text or image is already predictable from context, which would change how memorization benchmarks are interpreted.
A testable extension is to apply the surprisal criterion to existing extraction attacks on trained models: check whether the extracted samples actually satisfy $h(z|K,S\setminus\{z\}) \ge \xi h(z|S\setminus\{z\})$, which would separate statistical memorization from reconstruction in practical settings.
Because the definition depends on a chosen meta-distribution Prior, applying it to real data requires modeling the attacker's prior explicitly; the framework provides a language for such modeling, but the formal guarantees only hold for priors like the fingerprinting-code prior studied here.
The per-coordinate privacy result hints that reconstruction-safe mechanisms could be built at much lower utility cost than membership-inference-safe mechanisms, potentially enabling practical data release with small sample sizes where full DP would demand too much noise.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know: this paper delivers a real formal result, but its headline interpretative claim rests on a definitional choice the authors concede is arbitrary. That doesn't sink the paper, but it changes what the reader is entitled to conclude.

What is actually new: the Bayesian extraction-safety definitions (3.1, 3.6, 4.4, 4.11) and the proofs that exact and noisy averages are secure under the Tardos prior. The idea of measuring the attacker's prior knowledge via surprisal is a genuine extension of Narcissus resiliency, and the marginals separation is proved, not asserted. The proof of Lemma 4.8 via per-attribute DP is cute: it shows reconstruction-safety can be much cheaper than membership-inference resistance, which is a real insight.

Where it gets soft: the claim that FPC attacks are 'membership inference, not reconstruction' is not an independent finding. It follows directly from Definition 4.4's requirement that a successful reconstruction have high surprisal given the side information. The pair attack in §4.2 illustrates the point: the attacker can reliably pick the element of S from a candidate pair, but the definition discards that attack because the target was already one of the two candidates, so its surprisal is tiny. Observation 4.2 shows that without the filter even the exact average fails. So the separation is real only for a specific, and admittedly arbitrary, choice of what counts as reconstruction. The stress-test note is accurate on this.

Also, Lemma 3.7 is dense and relies on concentration constants left implicit; I'd ask for a clean statement. The introduction's claim that the secure mechanism works 'under the same conditions' as Attias et al. is not backed by a reduction to their SCO setting. These are fixable, not fatal.

Who is this for? Privacy-theory people and anyone who cares whether memorization-impossibility results actually rule out extraction. It deserves a serious referee—the definitions are worth engaging even if the interpretive conclusion is contestable. I'd send it out, and instruct the referee to focus on whether Definition 4.4 is the right formalization and whether Remark 4.5 undercuts the FPC reclassification.

Referee Report

3 major / 4 minor

Summary. This paper proposes a Bayesian security definition, termed "Bayesian extraction-safe," that is intended to distinguish statistical memorization from computational extraction. The definition models the attacker's prior knowledge about a recovered element through surprisal (pointwise conditional entropy). Under the Tardos meta-prior, the paper proves that releasing the exact column average prevents near-exact Hamming reconstruction (Lemma 3.5), that a bi-criteria relaxation extends this to all Hamming radii (Lemma 3.7), and that a per-coordinate noisy average prevents exact reconstruction even in the presence of arbitrary side information, provided the recovered element has sufficiently high surprisal (Lemma 4.8). The paper then argues that fingerprinting-code attacks against such mechanisms are membership-inference attacks rather than reconstruction attacks, so FPC-based impossibility results for reconstruction do not apply. The formal results are presented with proofs that are mostly self-contained, and the paper is clearly written.

Significance. If the definitional choices are accepted, the paper makes a valuable conceptual contribution: it gives a concrete formal setting in which statistical memorization and computational extractability come apart, and it offers a new lens on the long-standing tension between memorization, reconstruction, and membership inference. The use of the Tardos prior connects the results directly to existing impossibility results, and the per-coordinate differential-privacy observation is an interesting technical point. The paper is honest about several modeling choices, notably in Remark 4.5, and does not hide free parameters. The main theorems are non-trivial and appear largely correct, although one quantitative step in Lemma 3.7 needs scrutiny. Overall, the paper is likely to stimulate further discussion, but its central interpretive claim depends heavily on the proposed surprisal filter.

major comments (3)

[Section 4.4, Definition 4.4 and Remark 4.5] The central claim that FPC attacks are "really membership inference" is load-bearing on a definitional choice that the paper itself calls "somewhat arbitrary" in Remark 4.5. The surprisal condition h(z|K,S\{z}) ≥ ξ·h(z|S\{z}) is what excludes the pair attack of §4.2, because the target is already one of the attacker's two candidates and hence h(z|K,S\{z}) is small. Lemma 4.8 therefore proves security only for a filtered notion of reconstruction, and the reclassification of FPC attacks follows from that filter, not from an independent argument. I recommend either tempering the abstract and introduction to say "under the proposed definition," or providing an independent justification for the surprisal threshold and demonstrating robustness to reasonable variants (e.g., ξ=0, or the variant in Remark 4.5.2 where the surprisal condition appears on both sides of the inequality).
[Section 3.2, proof of Lemma 3.7] The proof that Event G_2 occurs with probability 1−O(δ) appears to require a stronger parameter regime than the lemma states. The Hoeffding bound for a single row gives a tail probability of at most exp(−Ω(d·log(d/δ)/n)), because the threshold is Θ(d·sqrt(log(d/δ)/n)) while the variance of the sum is O(d). To make this tail O(δ/n), the parameters must satisfy d·log(d/δ)/n ≥ Ω(log(n/δ)), i.e., d ≥ Ω(n·log(n/δ)/log(d/δ)). The stated condition d ≥ Ω(log(n/δ)) is insufficient when n is much larger than d, so the claimed 1−O(δ) bound for G_2 does not follow. Please either supply a corrected argument or weaken the lemma statement to the parameter regime that the proof actually supports.
[Section 4.2 and Section 4.4] The paper does not clearly state that the exact average remains insecure under Definition 4.4. In Observation 4.2, take SideInfo(S) = S\{last}, so that K = S\{z} for the recovered element z. Then h(z|K,S\{z}) = h(z|S\{z}) because the conditioning information is redundant, so the surprisal condition is satisfied. The attack succeeds with probability 1 on the left-hand side while the right-hand side is at most about 1/N, showing that the exact average is not Bayesian extraction-safe even under the new side-information definition. The text "So the exact average is not secure ... How about a noisy average?" risks being read as if the surprisal definition repairs the exact average. Please add an explicit remark clarifying that Definition 4.4 only excludes attacks where K carries additional information about z beyond S\{z}, and not the attack where K equals S\{z}.

minor comments (4)

[Section 3.2, proof of Lemma 3.7] There are a few typographical issues: "for any fixture of" should be "for any fix of" or "for any fixing of," and "w.o.p." should presumably be "w.h.p." (with high probability).
[Section 3.2, Equations (3) and (4)] The notation "call it Event ST" inside the displayed equation is confusing because the event is defined inline after a large union. It would be clearer to define Event_ST before the equation and then refer to it in both (3) and (4).
[Section 4.4, Remark 4.5] The remark about the arbitrary choice of comparing h(z|K,S\{z}) with h(z|S\{z}) could be expanded by noting the degenerate case K = S\{z}, where the two quantities are equal; this connects directly to the status of the exact average under Definition 4.4.
[Section 4, Lemma 4.8 proof, equality (∗5)] The justification "z is a function (only) of K and S\{v}" is inaccurate because z is the randomized output of the attacker A applied to M(S\{v}) and K. The equality remains valid because z is independent of v given K and S\{v}; please correct the explanation.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the security theorems are genuine derivations from disclosed definitions, though the headline separation is definition-conditional.

full rationale

The paper contains no fitted parameters renamed as predictions and no theorem that assumes its own conclusion. Definitions 3.1, 3.6, and 4.4 are self-contained Bayesian reformulations; Lemmas 3.5 and 3.7 are proved by Chernoff/Hoeffding arguments over the Tardos prior, and Lemma 4.8 follows from per-coordinate differential privacy plus Claim 4.9, not from the target statement. The surprisal filter in Definition 4.4 is an explicit modeling choice: Remark 4.5 concedes that the comparison in the definition is 'somewhat arbitrary,' and the paper honestly shows in Observation 4.2 that the exact average fails under the stricter Definition 4.1. The claim that FPC attacks are membership inference rather than reconstruction is therefore conditional on the chosen definition of reconstruction, but that is a disclosed definitional boundary rather than a circular reduction. The only self-citation, Definition 2.1 from Cohen et al. 2025, supplies a definitional precursor and is not load-bearing unverified evidence. No derivation reduces to its inputs by construction.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No numerical parameters are fitted to data; n, d, N, delta, epsilon, xi, and gamma are problem or definition parameters, and asymptotic constants in proofs are analytical choices rather than fitted values. No new physical entities are introduced; the only invented object is the new security definition itself, which is explicitly proposed as a modeling choice.

assumptions (5)

domain assumption Attacker knows the meta-distribution Prior but not Nature or the sample S.
Invoked in Definition 3.1 and Section 1.3; this Bayesian setup is the foundation for measuring the attacker's lack of knowledge.
ad hoc to paper A successful reconstruction requires h(z|K,S\{z}) >= xi times h(z|S\{z}); attacks on low-surprisal elements do not count.
Definition 4.4; this is the key modeling choice that classifies FPC attacks as membership inference, and Remark 4.5 says the choice is somewhat arbitrary.
standard math Standard Chernoff and Hoeffding concentration bounds and Laplace's rule of succession.
Used in the proofs of Lemmas 3.5, 3.7, and Claim 4.9.
domain assumption The Tardos-Prior, Definition 3.3, is the relevant hard meta-distribution.
The security theorems are proven only for this prior, which is motivated by its role in fingerprinting-code lower bounds.
standard math The Laplace mechanism is (epsilon d, 0)-differentially private.
Cited as Theorem 4.7 from Dwork et al. 2006; used in the proof of Lemma 4.8.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Bayesian Perspective on Memorization and Reconstruction." pith.science (2026). https://pith.science/paper/IBQV2WXK

@misc{pith2026250523658,
  author       = {Pith},
  title        = {Pith review of: Bayesian Perspective on Memorization and Reconstruction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IBQV2WXK}},
  note         = {Machine review of arXiv:2505.23658}
}

read the original abstract

We introduce a new Bayesian perspective on the concept of data reconstruction, and leverage this viewpoint to propose a new security definition that, in certain settings, provably prevents reconstruction attacks. We use our paradigm to shed new light on one of the most notorious attacks in the privacy and memorization literature - fingerprinting code attacks (FPC). We argue that these attacks are really a form of membership inference attacks, rather than reconstruction attacks. Furthermore, we show that if the goal is solely to prevent reconstruction (but not membership inference), then in some cases the impossibility results derived from FPC no longer apply.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

20 extracted references · 18 canonical work pages

[1]

Idan Attias, Gintare Karolina Dziugaite, Mahdi Haghifam, Roi Livni, and Daniel M. Roy. Information complexity of stochastic convex optimization: Applications to generalization, memorization, and tracing. In ICML , 2024

work page 2024
[2]

Smith, and Kunal Talwar

Gavin Brown, Mark Bun, Vitaly Feldman, Adam D. Smith, and Kunal Talwar. When is memorization of irrelevant training data necessary for high-accuracy learning? In STOC , 2021

work page 2021
[3]

Deconstructing data reconstruction: Multiclass, weight decay and general losses

Gon Buzaglo, Niv Haim, Gilad Yehudai, Gal Vardi, Yakir Oz, Yaniv Nikankin, and Michal Irani. Deconstructing data reconstruction: Multiclass, weight decay and general losses. In NeurIPS, 2023

work page 2023
[4]

The secret sharer: Evaluating and testing unintended memorization in neural networks

Nicholas Carlini, Chang Liu, \' U lfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In USENIX Security , 2019

work page 2019
[5]

Extracting training data from large language models

Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In USENIX Security, 2021

work page 2021
[6]

Extracting training data from diffusion models

Nicholas Carlini, Jamie Hayes, Milad Nasr, Matthew Jagielski, Vikash Sehwag, Florian Tram \` e r, Borja Balle, Daphne Ippolito, and Eric Wallace. Extracting training data from diffusion models. In USENIX Security , 2023 a

work page 2023
[7]

Quantifying memorization across neural language models

Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tram \` e r, and Chiyuan Zhang. Quantifying memorization across neural language models. In ICLR , 2023 b

work page 2023
[8]

Data reconstruction: When you see it and when you don't

Edith Cohen, Haim Kaplan, Yishay Mansour, Shay Moran, Kobbi Nissim, Uri Stemmer, and Eliad Tsfadia. Data reconstruction: When you see it and when you don't. In ITCS , 2025

work page 2025

Show all 20 references

[9]

Cover and Joy A

Thomas M. Cover and Joy A. Thomas. Elements of information theory (2. ed.) . Wiley, 2006

2006
[10]

Calibrating noise to sensitivity in private data analysis

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC, 2006

2006
[11]

Smith, Thomas Steinke, Jonathan R

Cynthia Dwork, Adam D. Smith, Thomas Steinke, Jonathan R. Ullman, and Salil P. Vadhan. Robust traceability from trace amounts. In FOCS , 2015

2015
[12]

Does learning require memorization? a short tale about a long tail

Vitaly Feldman. Does learning require memorization? a short tale about a long tail. In STOC , 2020

2020
[13]

What neural networks memorize and why: Discovering the long tail via influence estimation

Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. In NeurIPS, 2020

2020
[14]

Reconstructing training data from trained neural networks

Niv Haim, Gal Vardi, Gilad Yehudai, Ohad Shamir, and Michal Irani. Reconstructing training data from trained neural networks. In NeurIPS, 2022

2022
[15]

Probability theory: The logic of science

Edwin T Jaynes. Probability theory: The logic of science. Cambridge university press, 2003

2003
[16]

A mathematical theory of communication

Claude E Shannon. A mathematical theory of communication. The Bell system technical journal, 27 0 (3): 0 379--423, 1948

1948
[17]

Membership inference attacks against machine learning models

Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In IEEE Symposium on Security and Privacy , 2017

2017
[18]

Optimal probabilistic fingerprint codes

G \'a bor Tardos. Optimal probabilistic fingerprint codes. J. ACM, 55 0 (2), 2008

2008
[19]

Sasha Voitovych, Mahdi Haghifam, Idan Attias, Gintare Karolina Dziugaite, Roi Livni, and Daniel M. Roy. On the dichotomy between privacy and traceability in _p stochastic convex optimization. CoRR, abs/2502.17384, 2025

2025 arXiv
[20]

Privacy risk in machine learning: Analyzing the connection to overfitting

Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learning: Analyzing the connection to overfitting. In IEEE computer security foundations symposium (CSF), 2018

2018

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Idan Attias, Gintare Karolina Dziugaite, Mahdi Haghifam, Roi Livni, and Daniel M. Roy. Information complexity of stochastic convex optimization: Applications to generalization, memorization, and tracing. In ICML , 2024

work page 2024

[2] [2]

Smith, and Kunal Talwar

Gavin Brown, Mark Bun, Vitaly Feldman, Adam D. Smith, and Kunal Talwar. When is memorization of irrelevant training data necessary for high-accuracy learning? In STOC , 2021

work page 2021

[3] [3]

Deconstructing data reconstruction: Multiclass, weight decay and general losses

Gon Buzaglo, Niv Haim, Gilad Yehudai, Gal Vardi, Yakir Oz, Yaniv Nikankin, and Michal Irani. Deconstructing data reconstruction: Multiclass, weight decay and general losses. In NeurIPS, 2023

work page 2023

[4] [4]

The secret sharer: Evaluating and testing unintended memorization in neural networks

Nicholas Carlini, Chang Liu, \' U lfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In USENIX Security , 2019

work page 2019

[5] [5]

Extracting training data from large language models

Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In USENIX Security, 2021

work page 2021

[6] [6]

Extracting training data from diffusion models

Nicholas Carlini, Jamie Hayes, Milad Nasr, Matthew Jagielski, Vikash Sehwag, Florian Tram \` e r, Borja Balle, Daphne Ippolito, and Eric Wallace. Extracting training data from diffusion models. In USENIX Security , 2023 a

work page 2023

[7] [7]

Quantifying memorization across neural language models

Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tram \` e r, and Chiyuan Zhang. Quantifying memorization across neural language models. In ICLR , 2023 b

work page 2023

[8] [8]

Data reconstruction: When you see it and when you don't

Edith Cohen, Haim Kaplan, Yishay Mansour, Shay Moran, Kobbi Nissim, Uri Stemmer, and Eliad Tsfadia. Data reconstruction: When you see it and when you don't. In ITCS , 2025

work page 2025