Modern host-based intrusion detection systems (HIDS) rely on querying provenance graphs—graph representations of activity history on a system—to detect and respond to security threats present on a system. However, as the complexity and number of applications running on a system increase, the size of provenance graphs also increase, and thus the latency to query them. State-of-the-art designs deliver query latencies that are impractical for modern threat detection. In this paper, we introduce a hyper-dimensional computing (HDC) approach to querying provenance graphs for HIDS. By encoding provenance graphs and attack patterns/signatures into hyper-dimensional vectors, we can implement a query engine using simple vector operations. Our approach is hardware accelerator compatible, providing further speedups under resource-constrained environments. Our evaluation on a real-world dataset shows that our approach achieves > 90% detection accuracy and up to 4, 242× speedups over the state-of-the-art. This shows that HDC-based approaches can effectively deal with scaling issues in modern HIDS.