search engine engineers

Abstract: Local PageRank algorithms seek sparse approximations with work independent of graph size. We give a deterministic algorithm for regularized personalized PageRank with additive objective accuracy $ε$ in $\widetilde{\mathcal{O}}(1/(ρ\sqrtα))$ local work, where $α$ is the lazy teleportation parameter and $ρ$ is the regularizer. Accuracy enters only polylogarithmically. The bound charges discovery, repeated neighborhood scans, numerical updates, certification, and output, without graph-wide preprocessing or a supplied solution support. The algorithm combines regularization continuation with accelerated corrections constrained by a degree-scaled box and a mass cap. Two energies for the same recurrence control objective convergence and the response that activates coordinates. A selected-flow argument bounds cumulative scanned volume, and a sparse threshold reporter realizes the bound. We also specify a bounded-arithmetic implementation for rational inputs. A second, randomized algorithm uses support-safe threshold batches. A block-Cholesky and Chebyshev argument bounds their depth, and certified SDD solves give expected work $\widetilde{\mathcal{O}}(V_*\min\{k_*,α^{-1/2}\})$, where $k_*$ and $V_*$ are the optimal support's cardinality and degree volume. Both methods imply the corresponding accelerated degree-normalized PPR approximation. The concurrent September 2026 preprint of Cui, Wei, and Yang also attains the randomized work scale. Our principal distinction is deterministic local acceleration with only polylogarithmic overhead and no SDD oracle.

Abstract: Approximate Nearest Neighbor (ANN) algorithms achieve high efficiency through interdependent phases across index construction and query execution. This coupling allows upstream performance loss to propagate downstream, affecting execution behavior and measurable outputs. Existing component-level analyses mainly compare isolated design choices, while end-to-end benchmarks report aggregate metrics; neither traces loss propagation across dependent phases, hindering root-cause attribution and automated redesign. We present SmartANN, a framework based on the object causal model (OCM) for ANN bottleneck attribution and automated redesign. SmartANN represents an ANN workflow as eight ordered, replaceable objects and diagnoses them with a sequential diagnose-and-replace loop. At each iteration, it identifies the first object deviating from expected behavior or output as a bottleneck. Because an upstream bottleneck can obscure downstream ones, SmartANN replaces it with a test oracle when available, or with an implementation producing a better outcome, then continues downstream diagnosis. From the diagnosed bottlenecks and failure causes, SmartANN composes compatible actions from a pluggable action library to generate an optimized end-to-end ANN design. We instantiate SmartANN for IVF-PQ and HNSW, covering partition-and-quantization and graph-based ANN families. Experiments on eight real-world datasets show that SmartANN improves Recall by 0.24--74.20%, and increases QPS by 28.8--256.5% at comparable Recall, with low diagnosis and auto-design overhead. The code is available at https://github.com/zhouyutong20/SmartANN.

Abstract: Late-interaction models such as ColBERT achieve strong effectiveness by representing each document with many token-level vectors, but this expressivity leads to large indexing cost, storage footprints and expensive MaxSim scoring. We show that late-interaction representations exhibit an intrinsic low-rank structure: document token embeddings concentrate in a low-dimensional subspace that preserves most of the retrieval signal. Leveraging this observation, we introduce EigenLI, a spectral approximation framework that compresses late-interaction representations via document-specific low-dimensional subspaces. Unlike clustering or pooling methods, EigenLI identifies the dominant eigendirections of each document and uses them to construct reduced interaction representations. Empirically, $k$-EigenLI with $k \le 32$ outperforms k-means and Ward clustering based pooling methods on ColBERTv2 and AnswerAI-ColBERT-small; GTE-ModernColBERT exhibits a different tradeoff at $k=32$, where clustering methods perform better. The same spectral construction also yields EigenLI-SV, an ANN-compatible single-vector representation derived from the second-order summary of the reduced structure. Across multiple datasets and all three text models, EigenLI-SV consistently outperforms comparable single-vector surrogates such as MUVERA.