Graphene oxide (GO) resistive memories offer the promise of low-cost environmentally sustainable fabrication, high mechanical flexibility and high optical transparency, making them ideally suited to future flexible and transparent electronics applications. However, the dimensional and temporal scalability of GO memories, i.e., how small they can be made and how fast they can be switched, is an area that has received scant attention. Moreover, a plethora of GO resistive switching characteristics and mechanisms has been reported in the literature, sometimes leading to a confusing and conflicting picture. Consequently, the potential for graphene oxide to deliver high-performance memories operating on nanometer length and nanosecond time scales is currently unknown. Here we address such shortcomings, presenting not only the smallest (50 nm), fastest (sub-5 ns), thinnest (8 nm) GO-based memory devices produced to date, but also demonstrate that our approach provides easily accessible multilevel (4-level, 2-bit per cell) storage capabilities along with excellent endurance and retention performance - all on both rigid and flexible substrates. Via comprehensive experimental characterizations backed-up by detailed atomistic simulations, we also show that the resistive switching mechanism in our Pt/GO/Ti/Pt devices is driven by redox reactions in the interfacial region between the top (Ti) electrode and the GO layer.