Recent progress has been made on sparse dictionaries for the Bag-of-Visual-Words (BOVW) approach to object recognition and scene categorization. In particular, jointly encoded words have been shown to greatly enhance retrieval and categorization performance by both improving dictionary sparsity, which impacts efficiency of retrieval, and improving the selectivity of categorization. In this paper, we suggest and evaluate different functions for the “soft-pairing” of words, whereby the likelihood of pairing is influenced by proximity and scale of putative word pairs. The methods are evaluated in both the Caltech-101 database and the Pascal VOC 2007 and 2011 databases. The results are compared against spatial pyramids using BOVW descriptions, standard BOVW approaches, and across different parameter values of pairing functions. We also compare dense and keypoint-based approaches in this context. One conclusion is that word pairing provides a means towards attaining the performance of much larger dictionary sizes without the computational effort of clustering. This lends it to situations where the dictionaries must be frequently relearned, or where image statistics frequently change.