LAPRAS : Learning-Augmented PRivate Answering for linear query Streams

• URL: http://arxiv.org/abs/2605.01960v1
• Date: Sun, 03 May 2026 16:46:53 GMT
• Title: LAPRAS : Learning-Augmented PRivate Answering for linear query Streams
• Abstract summary: We present LAPRAS, which assumes access to an oracle that outputs a prediction set of queries likely to appear in the stream.<n>LAPRAS answers predicted queries using the offline-optimal Matrix Mechanism and answers the remaining queries online from a residual budget.<n> Empirically, over two real datasets, we validate the intended consistency--robustness trade-off.
• Score: 9.706153384025809
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Modern database workloads are highly predictable: query streams are dominated by recurring jobs and templates, even when their arrival order is not known in advance. This motivates a learning-augmented view of online differentially private (DP) analytics: can algorithms utilize predictions about which queries will occur to improve utility under a single global privacy budget, while remaining robust when predictions are wrong? We study online DP query answering, where a curator must answer a stream $Q$ of $S$ linear queries arriving in uniformly random order under privacy budget $(ε,δ)$. We present LAPRAS, which assumes access to an oracle that outputs a prediction set of queries likely to appear in the stream and uses it to guide privacy spending. LAPRAS answers predicted queries using the offline-optimal Matrix Mechanism and answers the remaining queries online from a residual budget. To pace spending across an unknown number of unpredicted queries, we introduce Smooth Allocation, which forms an unbiased stopping-time estimate $\widehat{B}$ from the first $T=Θ(\log^2 S)$ unpredicted queries and continuously recalibrates per-query expenditure. Empirically, over two real datasets, we validate the intended consistency--robustness trade-off: LAPRAS achieves near-offline utility under high overlap and degrades gracefully to baseline-level performance when overlap is low.

Related papers

• WISERouter: LLM Routing with Workload Budget Constraint [18.88807929206437]
  Large language models (LLMs) achieve impressive performance across multiple domains, but using the most capable model for every query is prohibitive at scale.<n>We introduce WISE (WR for short), a framework that supports offline learning from historical interactions as well as online learning with exploration.<n>WR-Online achieves comparable performance to the baselines, while using substantially less exploration data.
  arXiv  Detail & Related papers  (2026-07-26T17:20:39Z)
• Lower Bounds for PIR with Preprocessing from Blackbox Cryptography [57.20693707878285]
  We study the limits of single-server private information retrieval (PIR) with preprocessing.<n>Our work presents computation lower bounds for any single-server PIR with preprocessing.
  arXiv  Detail & Related papers  (2026-07-07T16:12:48Z)
• TopBench: A Benchmark for Implicit Prediction and Reasoning over Tabular Question Answering [80.93487993878836]
  A common class of real-world queries is implicitly predictive, requiring the inference of unobserved answers from historical patterns rather than mere retrieval.<n>These queries introduce two challenges: recognizing latent intent and reliable predictive reasoning over massive tables.<n>We introduce TopBench, a benchmark consisting of 779 samples across four sub-tasks, ranging from single-point prediction to decision making, treatment effect analysis, and complex reasoning.
  arXiv  Detail & Related papers  (2026-04-30T16:22:51Z)
• Pre-Execution Query Slot-Time Prediction in Cloud Data Warehouses: A Feature-Scoped Machine Learning Approach [0.0]
  Cloud data warehouses bill compute based on slot-time consumed.<n>In shared multitenant environments, query cost is variable and hard to estimate before execution.<n>We present a machine learning approach that predicts BigQuery slot-time before execution using only pre-execution observable signals.
  arXiv  Detail & Related papers  (2026-04-22T03:15:16Z)
• Continuous Semantic Caching for Low-Cost LLM Serving [29.887977985331972]
  caching responses so that they can be reused by users with semantically similar queries has become a vital strategy for reducing inference costs and latency.<n>Existing caching frameworks have proposed to decide which query responses to cache by assuming a finite, known universe of discrete queries.<n>We establish the first rigorous theoretical framework for semantic LLM response caching in continuous query space under uncertainty.
  arXiv  Detail & Related papers  (2026-04-21T21:56:43Z)
• Semantic Caching for Low-Cost LLM Serving: From Offline Learning to Online Adaptation [54.61034867177997]
  Caching inference responses allows them to be retrieved without another forward pass through the Large Language Models.<n>Traditional exact-match caching overlooks the semantic similarity between queries, leading to unnecessary recomputation.<n>We present a principled, learning-based framework for semantic cache eviction under unknown query and cost distributions.
  arXiv  Detail & Related papers  (2025-08-11T06:53:27Z)
• Conformal Information Pursuit for Interactively Guiding Large Language Models [68.16703423481935]
  This paper explores sequential querying strategies that aim to minimize the expected number of queries.<n>One such strategy is Information Pursuit (IP), a greedy algorithm that at each iteration selects the query that maximizes information gain or equivalently minimizes uncertainty.<n>We propose Conformal Information Pursuit (C-IP), an alternative approach to sequential information gain based on conformal prediction sets.
  arXiv  Detail & Related papers  (2025-07-04T03:55:39Z)
• Private Query Release via the Johnson-Lindenstrauss Transform [93.20051580730234]
  We introduce a new method for releasing answers to statistical queries with differential privacy. The key idea is to randomly project the query answers to a lower dimensional space. We answer the projected queries using a simple noise-adding mechanism, and lift the answers up to the original dimension.
  arXiv  Detail & Related papers  (2022-08-15T19:19:16Z)
• Interpretable by Design: Learning Predictors by Composing Interpretable Queries [8.054701719767293]
  We argue that machine learning algorithms should be interpretable by design. We minimize the expected number of queries needed for accurate prediction. Experiments on vision and NLP tasks demonstrate the efficacy of our approach.
  arXiv  Detail & Related papers  (2022-07-03T02:40:34Z)
• A Universal Error Measure for Input Predictions Applied to Online Graph Problems [57.58926849872494]
  We introduce a novel measure for quantifying the error in input predictions. The measure captures errors due to absent predicted requests as well as unpredicted actual requests.
  arXiv  Detail & Related papers  (2022-05-25T15:24:03Z)
• Online Caching with no Regret: Optimistic Learning via Recommendations [15.877673959068458]
  We build upon the Follow-the-Regularized-Leader (FTRL) framework to include predictions for the file requests. We extend the framework to learn and utilize the best request predictor in cases where many are available. We prove that the proposed optimistic learning caching policies can achieve sub-zero performance loss (regret) for perfect predictions.
  arXiv  Detail & Related papers  (2022-04-20T09:29:47Z)
• Progressive End-to-End Object Detection in Crowded Scenes [96.92416613336096]
  Previous query-based detectors suffer from two drawbacks: first, multiple predictions will be inferred for a single object, typically in crowded scenes; second, the performance saturates as the depth of the decoding stage increases. We propose a progressive predicting method to address the above issues. Specifically, we first select accepted queries to generate true positive predictions, then refine the rest noisy queries according to the previously accepted predictions. Experiments show that our method can significantly boost the performance of query-based detectors in crowded scenes.
  arXiv  Detail & Related papers  (2022-03-15T06:12:00Z)

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.