Papers for

data infrastructure teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Ai auto-research aims to build trustworthy data systems with verifiable correctness

Toward Verifiable Auto-Research for Data Systems

Abstract: AI auto-research is poised to forge bespoke data systems, from key-value stores and indexes to query engines, each engineered for a specific workload and hardware platform. Yet this promise rests on fragile ground. An agent optimizes what it can measure, not necessarily what users need. Natural-language requirements leave ample room for specification gaming, producing systems that blaze through benchmarks while silently losing updates or violating consistency. Worse, each research iteration consumes tokens, while validating a candidate under real concurrency, memory pressure, and failure conditions can stretch the entire research process into weeks. In this paper, we envision a more cost-efficient and verifiable approach to auto-research. Precise and composable specifications anchor the search, lightweight performance critics prune costly dead ends, and falsification and deductive verification make correctness an integral part of the process rather than an afterthought. By treating correctness, performance, research time, and token cost as equally important objectives, we aim to transform AI-generated data systems from plausible artifacts into trustworthy, production-grade systems whose behavior can be understood, audited, and ultimately relied upon.

Mon 9 NovDatabases
The gist
Building custom data systems using AI can be tricky because the AI might optimize the wrong things, like speeding up benchmarks but causing errors or losing data. The authors discuss how vague user instructions can lead to systems that don’t work as expected. They propose a method to make the research process more reliable by using clear, precise requirements and checking correctness as part of building the system rather than after. This approach also aims to reduce the time and cost needed for research while ensuring the systems are safe to use in real life.
Open → 2611.12063v1

Softmax attention runs faster in fixed dimensions with any temperature

Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product Bounds

Abstract: Attention is central to modern AI models for language, vision, and scientific modeling. However, direct evaluation compares every query with every key, requiring quadratic time in the context length, which limits its scalability to long contexts. Consequently, characterizing the complexity bounds of attention is of fundamental importance. For every fixed dimension $d$, we give an algorithm for $m$ queries, $n$ key-value pairs, and additive error $\varepsilon$, with expected time $ \widetilde{\mathrm{O}}\bigl((mn)^{k/(k+1)}+m+n\bigr),\qquad k=\lfloor d/2\rfloor. $ For fixed dimension and a fixed number of value channels, soft-O hides factors of the form $\operatorname{poly}_d\bigl(b,\log(m+n),\log B,\log(1/\varepsilon)\bigr),$ where $b$ bounds input encoding lengths and $B$ bounds coordinate and value magnitudes. In particular, the dependence on $B$ and $1/\varepsilon$ is polylogarithmic, which allows arbitrary positive temperature. When $m=n$ and $d\ge2$, the bound is $\widetilde{\mathrm{O}}(n^{2-2/(\lfloor d/2\rfloor+1)})$: near-linear in dimensions two and three, with exponent $4/3$ in dimensions four and five and $3/2$ in dimensions six and seven. It improves the previous $\widetilde{\mathrm{O}}(n^{2-1/d})$ upper bound and matches the best known batch maximum-inner-product bound in each fixed dimension. Additionally, we reduce integer batch maximum inner product computation to one attention call with the same dimension and input sizes $m,n$.

Wed 4 NovData Structures and AlgorithmsComputational ComplexityComputational Geometry
The gist
The paper deals with speeding up a key step in AI models called attention, which compares many data points to each other and usually takes a lot of time. The authors found a faster method that works well for any fixed dimension of data and any softmax temperature, which controls smoothing in the process. Their method matches the best known speed limits for similar problems and improves previous results. This can help AI models handle longer inputs without slowing down too much.
Open → 2611.06055v1

Limitations of sketching methods for efficient regression with common data sizes

Sketching in Regression: Sketchy in Practice?

Abstract: The Johnson-Lindenstrauss (JL) lemma and its extensions provide tools for solving the $L_2$ regression problem in high-dimensional settings with $n>d$, by transforming a subspace of $\mathbb{R}^{n}$ to a subspace of $\mathbb{R}^{m}$, (where $m<n$) while approximately preserving the norms of elements of the subspace. In this paper, we study the theoretical guarantees made by various JL-based subspace embeddings critically and concretely to gauge their practical applicability. We derive concrete versions of results on subspace embeddings in the literature to establish lower bounds on the reduced dimension as well as to concretely analyze the complexity of the Fast JL, OSNAP Transforms among other embeddings. These analyses suggest that guaranteeing substantial computational savings while maintaining the accuracy of the sketched solution requires data dimensions larger than those typically encountered in practice. We also see that, for practically necessary accuracy requirements or for sparsity requirements for computational gain, existing theoretical guarantees lead to substantially large reduced dimensions. This leads to very stringent data requirements for establishing guarantees of any kind.

Mon 2 NovData Structures and Algorithms
The gist
Solving large regression problems quickly often involves shrinking data dimensions while keeping important details. The authors examined well-known mathematical tools for this shrinking and found that to keep accuracy and speed, the data needs to be much bigger than what is typical. Their analysis shows that current guarantees require a lot of data or result in less practical reductions. This means these methods may not be very useful for everyday datasets and usual accuracy needs.
Open → 2611.02808v1

GenDB-V creates fast verified database engines tailored to hardware

Stop Handcrafting Your Engine! GenDB-V: Towards AI-Generated and Formally Verified Database Systems

Abstract: For over 50 years, the database community has developed a wide range of successful engines to answer two fundamental questions: how can database systems run faster, and how can we ensure their correctness? Experience with these engines shows that performance depends on hardware and workloads. As both change over time, we repeatedly redesign and rebuild database systems, a time-consuming and expensive process. Correctness remains another long-standing challenge: recent studies continue to uncover wrong-answer bugs even in mature database engines, despite years of development and testing. To address these, we present GenDB-V, a system that enables AI agents to synthesize database engines specialized to hardware and workloads for performance, and formally verified for correctness. GenDB-V supports specialized implementations of SQL templates and general-purpose engines that accept any query within a supported SQL subset. First, we develop SQLSpec to formalize SQL semantics and deterministically construct fixed, implementation-agnostic synthesis targets. Second, we enable joint synthesis of fast code and formal proofs through storage--execution co-optimization, performance-first exploration, and three-layer modular proofs that bridge low-level execution to SQLSpec semantics. Third, we verify the synthesized code and proofs against the fixed synthesis targets in an isolated pipeline, proving SQL correctness and program safety. We evaluate GenDB-V on TPC-H and SEC-EDGAR. For verified template implementations, GenDB-V achieves geometric-mean speedups of 22.0-61.3x over DuckDB and Umbra. For a verified general-purpose engine, GenDB-V also achieves speedups of 1.27-3.4x on TPC-H. GenDB-V also achieves better performance than a testing-based LLM synthesis method, while our audit and tests expose incorrect answers in that method's implementations for 16 of 28 templates.

Mon 2 NovDatabasesArtificial IntelligenceComputation and Language
The gist
Database software is usually hard to build and must be redesigned often to keep up with new hardware and workloads. The authors created GenDB-V, a system that uses AI to build database engines that are both fast and mathematically proven to give correct answers. They also designed a way to precisely describe SQL queries so that the database code and its correctness proofs can be generated together. Their method outperforms existing systems and catches errors in other AI-generated databases.
Open → 2611.02779v1

Sparse expert routing helps recover models with fewer active experts

When Does Sparse Routing Help? The Geometry of Expert Separation in Mixture of Experts

Abstract: Sparse mixtures of experts combine multiple prediction models while evaluating only a small subset for each input. Although this architecture reduces computation, how expert separation and routing sparsity jointly govern expert recovery remains an open problem. In this paper, we address this question for location Gaussian mixtures of experts with a fixed number of experts by establishing how expert separation and spatial arrangement determine recovery rates. For dense models, our results reveal that when experts form well-separated clusters, the separation geometry is governed by the size of the largest cluster; without a prescribed cluster structure, this geometry is instead driven by the total number of experts. For sparse models, the separation geometry on retained routing regions is determined by the number of active experts, while the contribution of omitted regions is controlled by their total probability. Consequently, activating fewer experts reduces the separation complexity in these bounds. Furthermore, Top-1 routing yields a particularly striking result: experts can be recovered at a rate independent of the separation quantity. Our technical approach combines polynomial interpolation and Gaussian reproducing-kernel Hilbert space (RKHS) test functions with quantitative restriction inequalities that extend pointwise comparisons to expert functions.

Sun 1 NovMachine Learning
The gist
This paper looks at how choosing only a few prediction models (experts) to use for each input affects how well those models can be separated and understood. The authors show that when experts group well, the difficulty depends on the size of the biggest group, but if there are no clear groups, it depends on the total number of experts. When routing is sparse, meaning only a few experts are used, the complexity depends on how many are active and the probability of ignored areas. Notably, using only the top expert chosen (Top-1 routing) lets models be recovered without worrying about how separated they are. They combined mathematical tools to reach these conclusions.
Open → 2611.01602v1

Optimal coreset sizes for precise clustering in Euclidean spaces

Tight Coreset Bounds for Euclidean $(k,z)$-Clustering

Abstract: We study the optimal coreset size for Euclidean $(k,z)$-clustering, where $z\ge1$ is fixed. Huang, Li, and Wu (STOC 2024) proved a lower bound of $Ω_z(k\varepsilon^{-z-2})$ for $\varepsilon\gtrsim_z k^{-1/(z+2)}$, matching the known upper bound up to polylogarithmic factors. For $0<\varepsilon<k^{-1/(z+2)}$, the upper bound $\widetilde O_z(k^{(2z+2)/(z+2)}\varepsilon^{-2})$ remained unmatched. The previous lower bounds gave only $Ω_z(\max\{k\varepsilon^{-2},k^{(2z+3)/(z+2)}\varepsilon^{-1}\})$. We close this gap by proving a matching lower bound throughout $0<\varepsilon<k^{-1/(z+2)}$, including arbitrarily small $\varepsilon$. Together with known bounds, this determines the optimal worst-case coreset size as $$ \widetildeΘ_z\!\left(\min\left\{k^{(2z+2)/(z+2)}\varepsilon^{-2},\,k\varepsilon^{-z-2}\right\}\right) $$ for every integer $k\ge1$ and $0<\varepsilon<1$. In particular, the bounds are $\widetildeΘ(k^{4/3}\varepsilon^{-2})$ for $k$-median when $\varepsilon<k^{-1/3}$, and $\widetildeΘ(k^{3/2}\varepsilon^{-2})$ for $k$-means when $\varepsilon<k^{-1/4}$. Our construction uses projection levels to encode four-wise independent signs, allowing $k$ centers to detect omissions regardless of how the retained points are reweighted.

Sun 25 OctData Structures and AlgorithmsComputational Geometry
The gist
Clustering groups similar points together, but handling large data precisely needs summaries called coresets. The authors found the exact smallest size these summaries must be for a wide range of settings in Euclidean spaces. They solved a puzzle on how corest size depends on data accuracy and number of clusters. Their new math shows exactly how small these summaries can get without losing important information.
Open → 2610.34373v1

Uniform sampling can efficiently summarize k-means data sets

Coresets for $k$-Means: When Does Uniform Sampling Suffice?

Abstract: Data summarization techniques, such as coresets, are essential for scaling clustering algorithms to massive datasets. We study uniform sampling, which is an extremely simple and ultra-efficient method to construct coresets, in the context of weak, stable, and strong coresets for the $k$-means problem in Hilbert space. We begin with the fundamental case $k=1$, and establish matching upper and lower bounds on the sample complexity of stable and weak coresets, finding that the two notions require different sample complexities. As a consequence, we obtain tight bounds for stable $1$-median coresets in $\ell_1$ and $\ell_2$ (and thus also Kendall--tau and Jaccard metrics), removing the dimension dependence of Carmel and Krauthgamer (ICLR 2026). Our analysis is substantially simpler than prior work and reduces to bounding the deviation of the sample mean. For the general $k$-means problem on $ρ$-separated instances, a well-studied structural assumption on the input, we show that uniform sampling yields a stable coreset for all $O(1)$-approximate solutions, and a strong coreset if the instance additionally has bounded kurtosis. In all these results, the sample complexity is independent of the dimension and the instance size.

Thu 22 OctData Structures and AlgorithmsComputational Geometry
The gist
Clustering large sets of data into groups (called k-means) can be slow if the data is huge. The paper studies how simply picking random samples uniformly from the data can still give a good summary, called a coreset, which speeds up the process. The authors find exact conditions when uniform sampling works well, especially for one cluster and certain structured data. Their approach works without depending on the size or complexity of the data, making it simpler and more efficient than earlier methods.
Open → 2610.31491v1

Language models solve larger graphs with better scalable encoding

Scaling Graph Reasoning in Language Models with Learnable Graph Positional Encodings

Abstract: Solving reasoning tasks supported on graphs typically requires providing a Language Reasoning Model (LRM) with a serialized description of the graph. This approach results in the input length growing with the number of edges, which limits the size of the problems that can be solved. Furthermore, even when graphs fit in context, performance sharply decays as the graphs grow. We propose to address this by augmenting LRMs with scalable and permutation equivariant graph positional encodings that modulate attention logits. An additional post-fusion-style module incorporates structural information into hidden states. We compute these positional encodings using a GNN followed by a Graph Transformer. This eliminates the need for serialized adjacencies, reducing the context burden to $O(N)$. We jointly fine-tune the positional encoder and the LRM LoRA adapters using optimal solutions generated by graph-theoretic solvers, resulting in a computationally efficient method. Trained on small graphs, the model exhibits improved size-generalization across graph-theoretic tasks on graphs with up to 1,000 nodes, and produces fewer tokens than a conventional LRM. Additionally, we observe that our model remains robust to node relabelings. Evaluations on graph-theoretic benchmarks also show that performance on small graphs is preserved.

Tue 20 OctMachine LearningArtificial Intelligence
The gist
Graph reasoning tasks often require representing a graph in a way language models can understand, but this usually grows too big and slow as graphs get large. The authors propose a new technique that uses special graph position markers created by graph neural networks and transformers to help language models handle larger graphs more efficiently. This method reduces the input size and keeps performance high, even as graphs grow to thousands of nodes. Additionally, the model stays effective even if the labels of the graph nodes change.
Open → 2610.27439v1

Gnn knowledge improves mlp accuracy by preserving graph geometry

Distilling Graph Geometry: Knowledge Gap from GNNs to MLPs

Abstract: GNN-to-MLP distillation aims to retain the predictive accuracy of a message-passing teacher while deploying a graph-free MLP at inference. Existing methods mainly transfer node-wise predictions or use confidence-based reweighting, but they do not specify where the student should preserve the teacher's graph-induced geometry. We show that this omission leads to two spectral failure modes in the student's representation space. On sparse graphs, the student suffers from spectral underfit, missing high-energy teacher directions concentrated near boundary regions. On dense graphs, it suffers from spectral overfit, retaining spurious directions that the teacher has collapsed through aggregation. Motivated by an energy-weighted teacher-student alignment objective, we propose Graph Geometry-aware MLP (G^2MLP), a training-time distillation framework guided by Ollivier-Ricci curvature. Curvature identifies where the two spectral errors concentrate and is used to allocate supervision between prediction-level and representation-level alignment. The deployed model remains a standard MLP and requires no graph access at inference. Across node-classification benchmarks, G^2MLP consistently improves over graph-free distillation baselines, reduces the teacher-student rank gap in both regimes, and transfers without architectural changes to Graph Transformer teachers and link prediction.

Wed 7 OctMachine Learning
The gist
Graph neural networks (GNNs) use information about connections between nodes to make predictions, but they can be slow to run. The authors study how to train simpler neural networks called MLPs to copy GNNs without needing the graph during use. They find that existing methods miss important geometric details of the graph, causing errors depending on how dense or sparse the graph is. Their new method, based on a concept called curvature, guides training to keep these details, improving accuracy while still using fast MLPs without graphs at runtime.
Open → 2610.10520v1

Canopy improves multi-level search in language model tasks

Canopy: Exploiting Piecewise Smooth Tree Priors for Multi-Fidelity Bandits

Abstract: Many LLM inference problems, including model routing, prefix-cache management, prompt trimming, and test-time search, can be viewed as optimization over a tree. This structure arises naturally from autoregressive generation: every prefix defines a node, and its continuations form a subtree below it. Internal nodes of the tree provide cheap but biased estimates of a region's value, while leaf evaluations are expensive but accurate. Hierarchical bandit methods can exploit this structure, but typically require a specific smoothness schedule to be specified in advance, even though real objectives are often only piecewise smooth and their optima may lie near sharp boundaries. We introduce CANOPY, a multi-fidelity tree bandit that learns where the smoothness prior is valid rather than assuming it globally. CANOPY uses cheap random-path probes to construct an online certificate of local aggregation bias, then directs expensive leaf evaluations toward cells where the certificate detects a smoothness violation. We prove fixed-budget and regret guarantees whose additional cost is additive in the number of discontinuities, recovering the smooth-tree rate when no violations are present and approaching structure-blind search as violations become dense. Across routing, top-$k$ identification, test-time search, caching, and prompt trimming, CANOPY consistently improves matched-budget performance, including $2.9\times$ higher top-10 recall on a 1000-model pool, $1.6\times$ more SWE-bench Verified issues resolved than best-of-$N$, and $3.6\times$ lower median time-to-first-token with prefix caching.

Thu 24 SeptMachine LearningArtificial Intelligence
The gist
Many problems in using large language models can be thought of as searching a big tree where some parts are cheap to explore but less accurate, and other parts are expensive but precise. The authors noticed that previous methods assumed the tree's smoothness everywhere, which isn't true for real data that can suddenly change. They created Canopy, a method that learns which parts of the tree are smooth and focuses expensive checks where this assumption breaks down. This approach performs better on tasks like model selection, caching, and prompt shortening, saving time and improving results.
Open → 2609.30017v1

Simpler algorithms outperform complex methods for large L1 logistic models

Simpler Methods Work Better for L1 Penalized Logistic Models and Large Datasets

Abstract: Linear models with an $L_1$-norm penalty remain state-of-the-art for high-dimensional ($d > 1,000,000$) tasks, offering a straightforward method for solving real-world industry problems. Despite their widespread use in industry and utility, many $L_1$ solvers are not effective for general use, are prohibitively slow, and are ineffective in parallelization. This makes them difficult to train in an MLOps pipeline on large industry-scale corpora. In this work, we test several proposed ``state-of-the-art'' solutions from the literature and find that older methods are currently far superior for general use. We also identify several recommendations for academics to perform research that avoids erroneously overconfident results, which can prevent the transition to production use. Equally surprising, we find that a new and simple baseline, using LBFGS on a sub-gradient, is highly effective with minor tweaks, despite being dismissed in the literature for theoretical non-convergence. In practice, we find it is an easier-to-support and easier-to-scale method for production use.

Mon 21 SeptMachine Learning
The gist
Training certain statistical models that use a special kind of penalty, called L1 regularization, can be very slow and hard to run on big datasets. The authors tested various popular methods and found that older, simpler algorithms actually work better for general use. Surprisingly, they show that a straightforward technique called LBFGS applied to a sub-gradient works well in practice, even though theory says it might not converge. This method is easier to scale and maintain in real-world production systems.
Open → 2609.23995v1