{"id":"aa56c3ec-a57a-4eb3-9d55-92d5cd2c033c","arxiv_id":"2411.17915","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":10,"one_line_summary":"A new linearization and partitioning framework lets stochastic package queries with value-at-risk or conditional-value-at-risk constraints run on millions of tuples in minutes.","lead":"This paper presents a method to run risk-aware optimization queries over uncertain data on very large databases, scaling to millions of rows in minutes. It combines a new linearization of risk constraints with a divide-and-conquer solver, reporting speedups of orders of magnitude over the prior state of the art.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem E.1's (1−ε)² guarantee is not actually proven: its proof quantifies over the optimal package while the statement quantifies over the returned package, and Theorem F.1's sketch-feasibility bound relies on an unjustified uniform-CVaR assumption.","rationale":"The central claim is that RCL plus Stochastic SketchRefine scales SPQs to millions of tuples while producing packages that are near-optimal in a formal sense. The formal sense is the (1−ε)² bound of Theorem E.1, so a defect in that theorem is load-bearing even though the empirical results are strong. I read the proof carefully: the inequality chain in E.1 reaches ω*_sk ≥ ω* − d_o Pmax via Σ_i E[t_i.O] x*_i ≥ ω*, which is only true for the optimal package, not for an arbitrary returned package. The theorem's own hypothesis is about the returned package, so the proof and statement do not match. This is an internal correctness issue, not a disagreement with the field's consensus. The paper's own admission that F.1's assumption is strong, and the fact that F.1 is the only route to sketch feasibility, compounds the problem; without F.1 the near-optimality guarantee is conditional on an event that may not occur. I agree with the reader's conditional verdict: the scaling experiments, ablation studies, and the DistPartition design are valuable and appear to support the practical claim of fast, good-quality packages, especially on the tested workloads. The theoretical guarantee, however, needs correction or careful restatement. This is addressable and not a reason to reject the paper's empirical contribution, so I would keep the CONDITIONAL verdict rather than accept the guarantee at face value.","tokens_in":39825,"tokens_out":8531,"duration_ms":75491,"concrete_test":"Independently re-derive Theorem E.1 with explicit quantifiers: let x^o be an optimal package of Q(S) and let ṽx be the package returned by Stochastic SketchRefine. Apply the mapping λ to x^o and check whether ω*_sk ≥ ω* − d_o Pmax follows from the diameter bound and the sketch feasibility of x^o. If the theorem's hypothesis is instead 'the returned package ṽx is sketch feasible', the proof step Σ_i E[t_i.O] ṽx_i ≥ ω* is unjustified, so the stated (1−ε)² guarantee has no valid derivation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Stochastic SketchRefine's headline near-optimality claim rests on Theorem E.1, but this theorem is not established as stated. In the proof, the lower bound ω*_sk ≥ ω* − d_o Pmax is derived from Σ_i E[t_i.O] x*_i ≥ ω*. That inequality only holds if x* is the optimal package of Q(S), whereas the theorem's hypothesis is that Stochastic SketchRefine returns a non-NULL package x* and that this returned package is sketch feasible. If x* is merely the returned package, its original objective can be well below ω*, so the chain to ω*_sk has no basis. The statement therefore needs either a corrected quantifier over the optimal package or a new argument linking the returned package to ω*. The only support for sketch feasibility, Theorem F.1, assumes the CVaR values of tuples in each partition are independently and uniformly distributed around the representative's CVaR. The paper itself calls this assumption strong, and it is not derived from the MAD/diameter conditions: Theorem 5.1 gives only an absolute-difference bound, not uniformity or independence. For C independent constraints, F.1's probability can be as low as 1/2^C, and no evidence is given that the uniform model holds on the GBM or Gaussian datasets. Without that, the (1−ε)² guarantee is conditional on an unverified event, and a feasible but uncontrolled suboptimal package (or NULL) is possible. The experiments give credible evidence of empirical scalability, but they do not supply the missing derivation.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two mechanisms for scaling stochastic package queries (SPQs) over uncertain relations. RCL-Solve replaces VaR/CVaR risk constraints with linearized CVaR (L-CVaR) constraints, so that the resulting SAA/ILP problem size does not grow with the number of Monte Carlo scenarios. Stochastic SketchRefine extends deterministic SketchRefine by partitioning the relation with DistPartition, building correlated duplicates of partition representatives, solving a sketch problem over the duplicates, and then refining the sketch solution back to actual tuples. The paper claims that RCL alone outperforms SummarySearch, that RCL plus Stochastic SketchRefine scales to millions of tuples in minutes, and that Stochastic SketchRefine enjoys a (1-epsilon)^2 approximation guarantee under a sketch-feasibility condition. The experimental section reports 16-run averages on two workloads (portfolio and TPC-H) with up to 6M tuples, ablation studies for duplicates and partitioning, and robustness checks.","tokens_in":40246,"tokens_out":10723,"duration_ms":91169,"significance":"If the formal guarantees were valid, this would be an important step toward practical in-database optimization under uncertainty, since it attacks both the scenario dimension and the tuple dimension simultaneously. The experimental evidence is extensive and reproducible in spirit: 16-run error bars, two datasets, up to 6M tuples, and ablations. The paper also provides a new language construct (L-CVaR) and a partitioning method (DistPartition) with sub-quadratic complexity, which are of independent interest. However, as detailed below, the main approximation theorem is not proven as stated, and the sketch-feasibility probability result rests on an explicitly strong, unverified distributional assumption. The practical claims may survive, but the theoretical contribution needs substantial repair.","major_comments":[{"comment":"The proof of Theorem E.1 does not establish the stated guarantee. In the proof, after deriving the chain for the mapped package, the text asserts \"Σ_i E[t_i.O] x*_i – d_o Σ_i x*_i ≥ ω* – d_o Pmax\". This inequality uses Σ_i E[t_i.O] x*_i ≥ ω*, which holds only when x* is an optimal package for Q(S). But the theorem statement quantifies over the package x* returned by Stochastic SketchRefine, and the returned package is not assumed to be optimal for Q(S). Consequently, the derived lower bound ω*_sk ≥ ω* – d_o Pmax has no basis for an arbitrary returned package, and the chain to ω ≥ (1−ε)^2(ω* – d_o Pmax) collapses. The theorem needs either a corrected quantifier over the optimal package (with a separate argument linking the returned package to the optimal package), or a new derivation that uses the objective value of the returned package itself and proves a meaningful comparison to ω*. As written, the headline (1−ε)^2 guarantee is not established.","section":"Appendix E, Theorem E.1"},{"comment":"The only probabilistic support for sketch feasibility, Theorem F.1, relies on assumption (ii): the CVaR values of tuples in each partition are independently and uniformly distributed around the CVaR of the representative. This assumption is not implied by the MAD/diameter conditions used elsewhere in the paper; Theorem 5.1 provides only a deterministic bound |CVaR_α(t1.C) − CVaR_α(t2.C)| ≤ d_C/α, with no uniformity or independence. The paper itself calls the assumption strong, and indeed for C independent constraints the resulting sketch-feasibility probability can be as low as 1/2^C, as the paper notes. No empirical evidence is given that the uniform model holds for the GBM or Gaussian datasets. Therefore the statement in Section 5 that \"use of MAD allows us to formally guarantee that Stochastic SketchRefine achieves a (1−ε)^2-optimal solution\" is not supported: the guarantee is conditional on an unverified event. The authors should either derive a high-probability bound from the MAD/diameter properties (which does not seem possible without additional assumptions), or explicitly reframe the contribution as an empirical method with a conditional guarantee that is clearly stated.","section":"Appendix F, Theorem F.1"},{"comment":"The paper's own caveats undermine the unconditional form of the near-optimality claim. Section 3 states that if the alternating-parameter search fails, RCL-Solve \"will return the best validation-feasible package encountered so far, but with no optimality guarantees,\" and that while this behavior is theoretically possible it did not occur in the experiments. Appendix G similarly states that \"Stochastic SketchRefine usually provides a similar guarantee in the order of (1±ε)^2\". These qualifications are appropriate, but they should be reflected in the abstract and in the formal statement of guarantees. As written, the abstract's claim that solving the linearized ILPs \"gives us feasible and near-optimal packages\" is stronger than what is proven. The paper should either prove the missing success conditions for the parameter search, or clearly present the guarantee as conditional on the search not failing, with the experimental frequency of success reported.","section":"Section 3 and Appendix G"}],"minor_comments":[{"comment":"The proposed O(d) transformation for generating correlated normal samples does not appear to produce the stated covariance structure. For example, using the definitions in Algorithm 3, Cov(s'_1, s'_2) evaluates to −λ1 − λ2 rather than the target correlation κ. Please verify the normalization and the eigenvector representation, and either provide a corrected formula or point to the code used in the experiments.","section":"Appendix C, Algorithm 3"},{"comment":"The theorem statement uses the bound floor(s/2 − δα/d_C), while the proof derives the Irwin-Hall CDF with argument x = s/2 − δα/(2d_C). The factor of 2 in the denominator is inconsistent between the statement and proof. Please align the expression.","section":"Appendix F, Theorem F.1 statement vs. proof"},{"comment":"The text reports \"relative integrality gap in the 0.94–0.99 range\" for RCL-Solve, but the metric defined in Section 6.1 is (ω − ω*)/ω*, which is non-positive for any feasible package with ω ≤ ω*. The reported numbers appear to be approximation ratios (ω/ω*), not gaps. Please reconcile the terminology.","section":"Section 6.2"},{"comment":"The notation for the upper bound on the optimal objective is garbled: the text says \"we use an upper bound ω≥ω\" and later \"above (1−ε)ω\". Please use distinct symbols (e.g., ω̄ for the upper bound and ω* for the true optimum) throughout.","section":"Section 3"},{"comment":"The word \"embarassingly\" should be \"embarrassingly\". Also, the conservative diameter test 2·d̂_A ≤ d_A is asserted without proof; a brief justification would help readers understand why the factor 2 is safe.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"This is a strong systems paper with compelling experimental results, and the practical contribution is likely to be of interest to the database community. However, the formal guarantee currently rests on a proof quantifier error in Theorem E.1 and an unverified, explicitly strong distributional assumption in Theorem F.1. The authors need to repair the theorem statement/proof, and ideally provide an empirical validation of sketch feasibility for their datasets, or clearly demote the theoretical guarantee to a conditional statement. I also noticed the Appendix C covariance formula appears incorrect; this should be clarified before publication, though the experiments may still be valid if the implementation differs from the pseudocode. I would support acceptance after a thorough major revision addressing these points."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth reading for the empirical results, but the headline theory does not hold up as stated. The stress-test note is correct: Theorem E.1's proof derives ω*_sk ≥ ω* − d_o Pmax by assuming x* is the optimal package, whereas the theorem's hypothesis only says x* is the returned package. There is no justification that the returned package has objective anywhere near ω*, so the (1−ε)² chain collapses. The statement needs a re-quantified hypothesis (e.g., the optimal package is sketch-feasible) or a genuinely new argument. Theorem F.1's uniform-and-independent-CVaR assumption is likewise a real gap; it is not derivable from the MAD/diameter bounds, and the resulting probability can be minuscule for multiple constraints. The authors admit it is strong, but they do not test it on the GBM or Gaussian data. That said, the empirical contribution is substantial. RCL is a clean idea that makes ILP size independent of scenario count, and Stochastic SketchRefine's correlated duplicates are a sensible, non-obvious adaptation of deterministic sketch-refine. DistPartition is sub-quadratic and evidently works. The experiments are extensive: 16 runs, error bars, ablations (duplicates, partitioning schemes), robustness checks, and up to 6M tuples. The quality ratios in the 0.92–0.97 range are credible, and the runtime gains over SummarySearch are large. The missing code is a fair complaint, though not fatal. The integrality-gap metric is a bit ill-defined (what exactly is the relaxed optimum?), so I would want that clarified. Overall, this is a good systems paper that tries to claim a stronger theory than it earned. The empirical claims are believable, the theoretical guarantee needs either fixing or honest downgrading to a conjecture. I would send it to serious referees with a clear request to fix the theory; the experiments deserve to see the light, but not with the current abstract's unqualified near-optimality claim.","headline":"Credible empirical systems paper with an overclaimed theoretical guarantee: the (1−ε)² bound as stated is not proven, but the experiments stand on their own.","tokens_in":40754,"tokens_out":1701,"would_cite":true,"duration_ms":18074,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P15","90C10","90C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Risk-constrained stochastic package queries over uncertain relations can be solved near-optimally at million-tuple scale by combining risk-constraint linearization with a stochastic divide-and-conquer sketch-refine framework.","keywords":["stochastic package queries","Value-at-Risk","Conditional Value-at-Risk","risk-constraint linearization","sketch-refine","integer linear programming","uncertain databases","in-database optimization"],"falsifier":"Construct a partition where all tuples have CVaR values systematically above or below their representative's CVaR — for example by adding a common shift within the diameter bound — and run a query whose optimal package uses several tuples from that partition. If Stochastic SketchRefine returns NULL or a package whose objective falls below $(1-\\epsilon)^2$ of the relaxed optimal value, then sketch feasibility or Theorem F.1's uniformity assumption has failed. A reader can also simulate the paper's own bound: with $C$ independent constraints at $\\delta = 0$, Theorem F.1 gives sketch-feasibility probability $1/2^C$, so a workload with several such constraints should show failures at a measurable rate if the assumption is wrong.","tokens_in":39606,"feed_emoji":"📊","tokens_out":6797,"duration_ms":58455,"temperature":0.7,"pith_summary":"This paper tries to show that risk-constrained stochastic package queries — choosing a bag of tuples that maximizes an expected objective while keeping tail risks such as Value-at-Risk (VaR) or Conditional Value-at-Risk (CVaR) within limits — can be solved near-optimally at million-tuple scale. The obstacle was that standard Monte Carlo formulations grow with both the number of scenarios and the number of tuples, so prior solvers take hours or fail outright. The paper's two mechanisms are risk-constraint linearization (RCL), which replaces each nonlinear risk constraint with a linearized CVaR constraint, and Stochastic SketchRefine, which partitions the relation into small similar groups, solves a sketch problem over correlated duplicate representatives, and then refines the solution back to actual tuples. Experiments show orders-of-magnitude runtime improvements over the prior state of the art and successful query execution on relations with millions of tuples. If correct, this makes in-database stochastic optimization practical for portfolio selection, procurement, and similar decisions under uncertainty.","feed_headline":"Stochastic package queries solve on millions of tuples in minutes","feed_subtitle":"Risk-constraint linearization plus sketch-refine beats prior solvers by orders of magnitude.","key_machinery":"The machinery is the linearized CVaR (L-CVaR) constraint, defined as the sum over package tuples of each tuple's own CVaR times its multiplicity, plus the two-phase Stochastic SketchRefine pipeline built on partitions of similar tuples. The L-CVaR constraint converts each VaR or CVaR risk condition into a single linear inequality, so the SAA ILP's size stops growing with the number of scenarios; the sketch phase solves a small ILP over duplicated representatives of each partition, and the refine phase replaces those duplicates with actual tuples partition by partition. The argument's load-bearing identities are Theorem 2.1 (an L-CVaR constraint is stricter than the corresponding CVaR constraint, which is stricter than the VaR constraint), Theorem 3.1 (the alternating parameter search reaches the optimal L-CVaR parameterization in the idealized setting), and Theorem E.1 (if the optimal package is sketch-feasible, the returned package attains at least $(1-\\epsilon)^2$ times the optimal objective minus a diameter-dependent term).","core_discovery":"The paper's central claim is that stochastic package queries with VaR and CVaR constraints can be evaluated near-optimally at million-tuple scale in minutes by solving integer linear programs whose size does not depend on the number of Monte Carlo scenarios. Risk-constraint linearization searches for L-CVaR parameter values so that the reshaped feasible region contains a validation-feasible and epsilon-optimal package, and Stochastic SketchRefine divides the relation into small similar partitions, solves a sketch problem over correlated duplicate representatives, then refines the solution back to real tuples. The paper reports that the combined method produces packages of quality comparable to the prior state of the art while running orders of magnitude faster, and that it handles relations with up to 4.8 to 6 million tuples where previous methods time out or exhaust memory.","pith_inferences":["Not claimed in the paper: the same L-CVaR linearization could be lifted out of the database setting and applied to any chance-constrained MILP where VaR/CVaR constraints currently burden the scenario count, so the technique may generalize to supply-chain and energy scheduling problems.","Not claimed in the paper: the uniformity and independence assumption in Theorem F.1 is the point most worth stress-testing; an empirical study measuring within-partition CVaR deviation distributions on real uncertain data would show how often the sketch-feasibility condition actually holds.","Not claimed in the paper: the refine phase's partition groups are independent once the sketch package is fixed, so the approach should parallelize almost linearly across cores, making the reported minute-scale runtimes a conservative ceiling rather than a floor.","Not claimed in the paper: DistPartition's MAD distance, which already accounts for correlation between tuples, could be reused as a general clustering distance for uncertain data well beyond package queries."],"forward_implications":["Risk-constrained package queries over high-variance relations become practical: workloads that previously took hours or failed are reported to run in minutes.","The number of optimization scenarios no longer drives ILP size for VaR/CVaR constraints, so the scenario blowup that plagued prior methods is removed rather than merely compressed.","In-database decision-making can now include coherent CVaR risk constraints without a separate optimization stack, because the SPaQL language is extended to express them.","Package quality is tunable: the user's error bound $\\epsilon$ limits the final objective to at least $(1-\\epsilon)^2$ of the relaxed optimum, provided partitions are tight enough for sketch feasibility.","The method inherits the deterministic SketchRefine benefit of keeping every ILP subproblem small enough for in-memory solvers, avoiding the memory crashes that limit prior methods on million-tuple relations."],"supporting_citations":[{"why":"The prior stochastic package query method (SummarySearch) that RCL and Stochastic SketchRefine must beat on runtime and scale.","marker":"[7]"},{"why":"The deterministic SketchRefine divide-and-conquer approach that Stochastic SketchRefine extends with duplicate representatives and stochastic partitioning.","marker":"[5]"},{"why":"The Sample Average Approximation framework that defines how scenarios turn the SPQ into an optimization problem.","marker":"[27]"},{"why":"The source of the CVaR definition and its conditional-expectation form used for risk-constraint linearization.","marker":"[29]"},{"why":"The risk-management reference that motivates CVaR as a coherent risk measure and justifies adding CVaR constraints to SPaQL.","marker":"[33]"},{"why":"The NORTA method used to generate correlated duplicate representatives for stochastic sketch construction.","marker":"[18]"},{"why":"The workload-generation and query-hardness methodology used in the experimental evaluation.","marker":"[28]"},{"why":"The Monte Carlo database background that motivates scenario-based uncertain data and variable-generation functions.","marker":"[26]"}],"fun_headline_variants":["SketchRefine scales stochastic queries to millions of tuples fast","Orders-of-magnitude speedup for uncertain data package queries","Million-tuple decision-making under uncertainty in minutes","Near-optimal stochastic packages at scale, minutes not hours"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The near-optimality guarantee holds only if the optimal package can be mapped into the sketch without violating feasibility, and the paper's only probability bound for that event assumes that, within each partition, tuple CVaR values are uniformly and independently scattered around the representative's CVaR, an assumption the paper itself calls strong.","fun_headline_variants_meta":{"raw":{"variants":["SketchRefine scales stochastic queries to millions of tuples fast","Orders-of-magnitude speedup for uncertain data package queries","Million-tuple decision-making under uncertainty in minutes","Near-optimal stochastic packages at scale, minutes not hours"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000776,"raw_usage":{"total_tokens":3443,"prompt_tokens":965,"completion_tokens":2478,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":581,"completion_tokens_details":{"reasoning_tokens":2410}},"tokens_in":581,"tokens_out":2478,"duration_ms":16993,"temperature":1.0,"reasoning_tokens":2410,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:43:19.033020+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a partition where all tuples have CVaR values systematically above or below their representative's CVaR — for example by adding a common shift within the diameter bound — and run a query whose optimal package uses several tuples from that partition. If Stochastic SketchRefine returns NULL or a package whose objective falls below $(1-\\epsilon)^2$ of the relaxed optimal value, then sketch feasibility or Theorem F.1's uniformity assumption has failed. A reader can also simulate the paper's own bound: with $C$ independent constraints at $\\delta = 0$, Theorem F.1 gives sketch-feasibility probability $1/2^C$, so a workload with several such constraints should show failures at a measurable rate if the assumption is wrong.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The deterministic SketchRefine divide-and-conquer approach that Stochastic SketchRefine extends with duplicate representatives and stochastic partitioning."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The Sample Average Approximation framework that defines how scenarios turn the SPQ into an optimization problem."},{"cited_title":"McNeil, Rüdiger Frey, and Paul Embrechts","cited_arxiv_id":null,"evidence_quote":"The source of the CVaR definition and its conditional-expectation form used for risk-constraint linearization."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The NORTA method used to generate correlated duplicate representatives for stochastic sketch construction."},{"cited_title":"Mai, Pengyu Wang, Azza Abouzied, Matteo Brucato, Peter J","cited_arxiv_id":null,"evidence_quote":"The workload-generation and query-hardness methodology used in the experimental evaluation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The Monte Carlo database background that motivates scenario-based uncertain data and variable-generation functions."}],"review_version":1}