  Tree-based models underpin many modern semantic search engines and
recommender systems due to their sub-linear inference times. In industrial
applications, these models operate at extreme scales, where every bit of
performance is critical. Memory constraints at extreme scales also require that
models be sparse, hence tree-based models are often back-ended by sparse matrix
algebra routines. However, there are currently no sparse matrix techniques
specifically designed for the sparsity structure one encounters in tree-based
models for extreme multi-label ranking/classification (XMR/XMC) problems. To
address this issue, we present the masked sparse chunk multiplication (MSCM)
technique, a sparse matrix technique specifically tailored to XMR trees. MSCM
is easy to implement, embarrassingly parallelizable, and offers a significant
performance boost to any existing tree inference pipeline at no cost. We
perform a comprehensive study of MSCM applied to several different sparse
inference schemes and benchmark our methods on a general purpose extreme
multi-label ranking framework. We observe that MSCM gives consistently dramatic
speedups across both the online and batch inference settings, single- and
multi-threaded settings, and on many different tree models and datasets. To
demonstrate its utility in industrial applications, we apply MSCM to an
enterprise-scale semantic product search problem with 100 million products and
achieve sub-millisecond latency of 0.88 ms per query on a single thread -- an
8x reduction in latency over vanilla inference techniques. The MSCM technique
requires absolutely no sacrifices to model accuracy as it gives exactly the
same results as standard sparse matrix techniques. Therefore, we believe that
MSCM will enable users of XMR trees to save a substantial amount of compute
resources in their inference pipelines at very little cost.
