SCOUT: Coupling-Free Bounds for Trillion-Scale Top-k Retrieval in Sparse Tensor Factorization

Ranked retrieval over massive implicit result spaces is a core query-processing problem in data management. A natural instance arises when using tensor factorization (TF) models for retrieval over sparse tensors, where candidate tuples correspond to unobserved higher-order interactions over a multiway Cartesian product and are scored by a learned TF model. Real-world tensors in domains such as biomedical analysis, recommendation, and temporal interaction modeling are sparse and incomplete, and the candidate space can reach the trillion scale, making exhaustive scoring and sorting infeasible. While most prior work focuses on improving TF training or model accuracy, scalable inference-time top- k ranked retrieval over learned multiway scores has been relatively underexplored. Moreover, existing pairwise top-k search techniques, such as Maximum Inner Product Search (MIPS), do not directly extend to TF due to coupled multiway scores and the combinatorial candidate space.

We propose

a scalable and compatible framework for top- k ranked retrieval over massive implicit tensor spaces.

Scout

reparameterizes TF scores into nonnegative per-mode potentials and a normalized interaction term, yielding a coupling-free product-form bound that enables ranked access, admissible pruning, and reliable candidate ordering, without mode-coupled materialization as in MIPS-style reductions. Using this bound,

Scout

performs an N -dimensional best-first traversal with deferred scoring, supporting budgeted anytime retrieval and certified stopping when exact top- k is required.

Scout

further verifies candidates in GPU-friendly block-wise batches, enabling high-throughput execution under memory and latency budgets. Experiments show that

Scout

achieves over 10 ³ x speedup over full enumeration for various TF methods and up to 11x over MIPS-based baselines, while maintaining comparable retrieval quality.