arXiv:2610.27249v1 Announce Type: new Abstract: Graph pebbling is the model in which the memory cost of memory-hard functions and proofs of space is measured, and pebbling lower bounds are the main way to argue that such constructions are secure. It has long seemed that the model is faithful to reality. It is known that it is not exact: an adversary who stores encoded information instead of whole values can do better, but so far only by small factors: a factor of 1.5 in the work that introduced entangled pebbling (Alwen, Chen, Kamath, Kolmogorov, Pietrzak and Tessaro) and, recently, a factor of about log n/log log n (de Rezende, Engstr\"om and Reyzin). One could still hope that pebbling is right up to such small factors. In pure pebbling, memory consists of whole labels; entangled pebbling also allows encoded state, such as XORs of labels. We show that the two models can differ polynomially. We study the setting in which proofs of space and data-dependent memory-hard functions are used: a state is prepared in advance, a random challenge has to be answered from it, and memory is paid for as long as it is held. Our graphs are explicit and have indegree two, and on them a pure adversary can do no better, up to a constant factor, than storing every possible answer in advance. Still, an adversary who keeps XORs instead of labels pays polynomially less. This ends the hope that pure pebbling is a faithful model of memory up to small factors. The heart of the paper is a simple combinatorial game, together with a special class of graphs found by Alon, Moitra and Sudakov.