Lower Bounds for the Algorithmic Complexity of Learned Indexes

• URL: http://arxiv.org/abs/2601.06629v1
• Date: Sat, 10 Jan 2026 17:28:57 GMT
• Title: Lower Bounds for the Algorithmic Complexity of Learned Indexes
• Abstract summary: Learned index structures aim to accelerate queries by training machine learning models to approximate the rank function associated with a database attribute.<n>While effective in practice, their theoretical limitations are not fully understood.<n>We present a general framework for proving lower bounds on query time for learned indexes, expressed in terms of their space overhead and parameterized by the model class used for approximation.
• Score: 5.964436882344729
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learned index structures aim to accelerate queries by training machine learning models to approximate the rank function associated with a database attribute. While effective in practice, their theoretical limitations are not fully understood. We present a general framework for proving lower bounds on query time for learned indexes, expressed in terms of their space overhead and parameterized by the model class used for approximation. Our formulation captures a broad family of learned indexes, including most existing designs, as piecewise model-based predictors. We solve the problem of lower bounding query time in two steps: first, we use probabilistic tools to control the effect of sampling when the database attribute is drawn from a probability distribution. Then, we analyze the approximation-theoretic problem of how to optimally represent a cumulative distribution function with approximators from a given model class. Within this framework, we derive lower bounds under a range of modeling and distributional assumptions, paying particular attention to the case of piecewise linear and piecewise constant model classes, which are common in practical implementations. Our analysis shows how tools from approximation theory, such as quantization and Kolmogorov widths, can be leveraged to formalize the space-time tradeoffs inherent to learned index structures. The resulting bounds illuminate core limitations of these methods.

Related papers

• Exact Algebraic Computation of Learning Coefficients for Two-Dimensional Singular Models [0.5735035463793009]
  We present the first deterministic algorithm that computes local RLCT exactly for any two-dimensional computation whose Kullback-Leibler model is contact equivalent to a distance.<n>Our algorithm reveals exact structure in learning coefficients that sampling cannot and out-speeds it in the shallow regime.
  arXiv  Detail & Related papers  (2026-08-20T15:40:50Z)
• The Simulacrum: Decision-Theoretic Pretraining for Near-Optimal Time-Series Forecasting and Inference [0.3437656066916039]
  We introduce a neural network-based framework for learning time series estimators through a process we term decision-theoretic pretraining.<n>Analysts specify a generative world, a distribution over data-generating processes, and a target decision objective.<n>A neural network trained on stratified simulations from this world approximates the corresponding optimal decision rule.
  arXiv  Detail & Related papers  (2026-06-26T04:25:09Z)
• Algorithmic Recourse of In-Context Learning for Tabular Data [17.763934545409498]
  We present the first study of algorithmic recourse for tabular data under in-context learning (ICL)<n>We propose a novel zeroth-order recourse framework, Adaptive Subspace Recourse for In-Context Learning (ASR-ICL), that efficiently generates actionable and sparse recourse for black-box ICL models.
  arXiv  Detail & Related papers  (2026-05-29T13:04:18Z)
• Scalable Gaussian process modeling of parametrized spatio-temporal fields [2.005299372367689]
  We develop a scalable framework for learning of parametized equations over fixed or parameter-temporal domains.<n>A key feature of our approach is the efficient computation of the posterior variance at essentially the same computational cost as the posterior mean.<n>Results establish the proposed framework as an effective tool for data-driven surrogate modeling, particularly when uncertainty estimates are required for downstream tasks.
  arXiv  Detail & Related papers  (2026-02-27T20:16:21Z)
• General bounds on the quality of Bayesian coresets [13.497835690074151]
  This work presents general upper and lower bounds on the Kullback-Leibler (KL) Lower bounds are applied to obtain fundamental limitations on the quality of coreset approximations. The upper bounds are used to analyze the performance of recent subsample-optimize methods.
  arXiv  Detail & Related papers  (2024-05-20T04:46:14Z)
• It's All in the Mix: Wasserstein Classification and Regression with Mixed Features [2.2685251390114565]
  We develop and analyze distributionally robust prediction models that faithfully account for the presence of discrete features.<n>We demonstrate that our models can significantly outperform existing methods that are agnostic to the presence of discrete features.
  arXiv  Detail & Related papers  (2023-12-19T15:15:52Z)
• Structured Radial Basis Function Network: Modelling Diversity for Multiple Hypotheses Prediction [51.82628081279621]
  Multi-modal regression is important in forecasting nonstationary processes or with a complex mixture of distributions. A Structured Radial Basis Function Network is presented as an ensemble of multiple hypotheses predictors for regression problems. It is proved that this structured model can efficiently interpolate this tessellation and approximate the multiple hypotheses target distribution.
  arXiv  Detail & Related papers  (2023-09-02T01:27:53Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Spectral Representation Learning for Conditional Moment Models [33.34244475589745]
  We propose a procedure that automatically learns representations with controlled measures of ill-posedness. Our method approximates a linear representation defined by the spectral decomposition of a conditional expectation operator. We show this representation can be efficiently estimated from data, and establish L2 consistency for the resulting estimator.
  arXiv  Detail & Related papers  (2022-10-29T07:48:29Z)
• HyperImpute: Generalized Iterative Imputation with Automatic Model Selection [77.86861638371926]
  We propose a generalized iterative imputation framework for adaptively and automatically configuring column-wise models. We provide a concrete implementation with out-of-the-box learners, simulators, and interfaces.
  arXiv  Detail & Related papers  (2022-06-15T19:10:35Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  This work demonstrates a simple approach to reduce the computational and memory complexity of a large class of structured models. Experiments with neural parameterized structured models for language modeling, polyphonic music modeling, unsupervised grammar induction, and video modeling show that our approach matches the accuracy of standard models at large state spaces.
  arXiv  Detail & Related papers  (2022-01-08T00:47:50Z)
• Instance-Based Neural Dependency Parsing [56.63500180843504]
  We develop neural models that possess an interpretable inference process for dependency parsing. Our models adopt instance-based inference, where dependency edges are extracted and labeled by comparing them to edges in a training set.
  arXiv  Detail & Related papers  (2021-09-28T05:30:52Z)
• Spatial Classification With Limited Observations Based On Physics-Aware Structural Constraint [18.070762916388272]
  spatial classification with limited feature observations has been a challenging problem in machine learning. This paper extends our recent approach by allowing feature values of samples in each class to follow a multi-modal distribution. We propose learning algorithms for the extended model with multi-modal distribution.
  arXiv  Detail & Related papers  (2020-08-25T20:07:28Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.