Query intent classiﬁcation is crucial for web search and advertising. It is known to be challenging because web queries contain less than three words on average, and so provide little signal to base classiﬁcation decisions on. At the same time, the vocabulary used in search queries is vast: thus, classiﬁers based on word-occurrence have to deal with a very sparse feature space, and often require large amounts of training data. Prior efforts to address the issue of feature sparseness augmented the feature space using features computed from the results obtained by issuing the query to be classiﬁed against a web search engine. However, these approaches induce high latency, making them unacceptable in practice. In this paper, we propose a new class of features that realizes the beneﬁt of search-based features without high latency. These leverage cooccurrence between the query keywords and tags applied to documents in search results, resulting in a signiﬁcant boost to web query classiﬁcation accuracy. By pre-computing the tag incidence for a suitably chosen set of keyword-combinations, we are able to generate the features online with low latency and memory requirements. We evaluate the accuracy of our approach using a large corpus of real web queries in the context of commercial search.