We present GNNAutoScale (GAS), a framework for scaling arbitrary\nmessage-passing GNNs to large graphs. GAS prunes entire sub-trees of the\ncomputation graph by utilizing historical embeddings from prior training\niterations, leading to constant GPU memory consumption in respect to input node\nsize without dropping any data. While existing solutions weaken the expressive\npower of message passing due to sub-sampling of edges or non-trainable\npropagations, our approach is provably able to maintain the expressive power of\nthe original GNN. We achieve this by providing approximation error bounds of\nhistorical embeddings and show how to tighten them in practice. Empirically, we\nshow that the practical realization of our framework, PyGAS, an easy-to-use\nextension for PyTorch Geometric, is both fast and memory-efficient, learns\nexpressive node representations, closely resembles the performance of their\nnon-scaling counterparts, and reaches state-of-the-art performance on\nlarge-scale graphs.\n