Ilmu Komputer & AI editorial
Open AccessOA2026
ReBound: Reuse-Aware Privacy For Interactive Decision Support
A cache-graph framework that reuses differentially private query results to answer related queries at reduced or zero additional privacy cost
Nada Lahjouji; Shufan Zhang; Xi He; Sharad Mehrotraยท 2026ยท DOI 10.48550/arXiv.2607.13441
The core problem
Differentially private decision support frameworks answer complex aggregate threshold queries with formal bounds on false negative and false positive rates. However, these frameworks treat each query independently, with no memory of past results. In real-world interactive analysis, analysts issue sequences of related queries that refine bounds, adjust thresholds, or derive new functions from previous ones. This independence leads to unnecessary privacy budget consumption and reduced utility. ReBound addresses this gap by reusing cached results from previous queries to answer new queries at reduced or zero additional privacy cost, while maintaining formal utility guarantees. The work is motivated by the need for efficient, privacy-preserving interactive decision support where analysts iteratively explore data.
Innovation
The authors evaluate ReBound on interactive decision support workloads, demonstrating significant privacy budget savings and improved utility. By reusing cached results, ReBound answers sequences of related queries with reduced or zero additional privacy cost, while maintaining the formal false negative and false positive guarantees. The cache graph enables efficient lookup, and the negotiation mechanism successfully handles infeasible bound requests by proposing achievable alternatives. Experimental results show that ReBound outperforms baseline approaches that treat each query independently, particularly in scenarios with many related queries. The framework preserves the formal utility guarantees of the underlying differentially private decision support system, ensuring that the false negative and false positive rates remain within specified bounds.
Differentially private decision support frameworks answer complex aggregate threshold queries with formal bounds on false negative and false positive rates. However, these frameworks treat each query independently, with no memory of past results. In real-world interactive analysis, analysts issue sequences of related queries that refine bounds, adjust thresholds, or derive new functions from previous ones. This independence leads to unnecessary privacy budget consumption and reduced utility. ReBound addresses this gap by reusing cached results from previous queries to answer new queries at reduced or zero additional privacy cost, while maintaining formal utility guarantees. The work is motivated by the need for efficient, privacy-preserving interactive decision support where analysts iteratively explore data.
ReBound comprises three key components: (1) a reuse framework supporting multiple refinement types, (2) a cache graph structure for efficient lookup of reusable results, and (3) a negotiation mechanism for when requested bounds cannot be met within budget. The reuse framework formalizes how results from one query can be leveraged to answer another. For example, if a query with threshold and error bounds has been answered, a subsequent query with a relaxed threshold and looser bounds
may be answerable using the cached result of without additional privacy cost. The cache graph encodes relationships between queries, where nodes represent cached results and edges represent refinement operations. This graph enables efficient lookup: given a new query, ReBound traverses the graph to find a cached result that can be reused or adapted. The negotiation mechanism handles cases where the requested bounds are infeasible under the remaining privacy budget; it proposes alternative bounds that are achievable, allowing the analyst to decide whether to accept them or adjust the query.
Why it matters
ReBound's reuse-aware approach represents a shift from independent query answering to interactive, memory-based privacy. By leveraging cached results, it reduces the privacy cost of refinement queries, which are common in exploratory analysis. The cache graph provides a structured way to manage reusable results, and the negotiation mechanism adds flexibility when privacy budget is tight. However, the effectiveness of ReBound depends on the availability of reusable results, which may be limited if queries are highly diverse. Future work could explore adaptive caching strategies and extensions to other query types. Overall, ReBound offers a practical solution for interactive decision support, balancing privacy and utility in multi-query settings.
Who should read this
CS practitioners and researchers
Opening member contentโฆ