In this paper we present an algorithm for performing adaptive vector quantization with memory. By using memory between adjacent blocks which are encoded, we can take advantage of the correlation between adjacent blocks of pixels to reduce redundancy. We use finite state vector quantization to provide the memory. To further improve performance by exploiting nonstationarities in the image, we use variable block sizes in the encoding. This is done by using a quadtree data structure to represent an encoding based on using variable block sizes. To reduce encoding complexity, hierarchical table lookup schemes are used to replace all the full search encoders.