Our objective is language-based search of large-scale image and video\ndatasets. For this task, the approach that consists of independently mapping\ntext and vision to a joint embedding space, a.k.a. dual encoders, is attractive\nas retrieval scales and is efficient for billions of images using approximate\nnearest neighbour search. An alternative approach of using vision-text\ntransformers with cross-attention gives considerable improvements in accuracy\nover the joint embeddings, but is often inapplicable in practice for\nlarge-scale retrieval given the cost of the cross-attention mechanisms required\nfor each sample at test time. This work combines the best of both worlds. We\nmake the following three contributions. First, we equip transformer-based\nmodels with a new fine-grained cross-attention architecture, providing\nsignificant improvements in retrieval accuracy whilst preserving scalability.\nSecond, we introduce a generic approach for combining a Fast dual encoder model\nwith our Slow but accurate transformer-based model via distillation and\nre-ranking. Finally, we validate our approach on the Flickr30K image dataset\nwhere we show an increase in inference speed by several orders of magnitude\nwhile having results competitive to the state of the art. We also extend our\nmethod to the video domain, improving the state of the art on the VATEX\ndataset.\n