{"id":"48808945-5ac0-42bd-903d-c50295bc5338","arxiv_id":"2608.10650","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A decision-aware belief function compressor targets the regret of the induced combinatorial decision, with a one-point regret bound and an exact scalar dynamic program, and flips the decision less often than representation-aware baselines.","lead":"The paper introduces a way to compress uncertain cost estimates, called belief functions, so that the compressed version preserves the best decision instead of merely staying close as a body of evidence. It proves a bound on decision regret and shows, on small random shortest-path problems, that decision-aware compression changes the chosen path far less often than standard distance-based compression.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The one-point bound is valid, but minimizing Δ(x*) is a surrogate whose optimum can have strictly larger regret than another safe merge; no guarantee relates the surrogate's optimum to the true regret minimizer, so the central 'one-solve' claim is unsupported.","rationale":"I read the paper in good faith. Theorem 1 is a correct one-sided regret bound, Proposition 1's contiguity argument is sound for the scalar case, and the text is unusually explicit about its limitations: monotonicity for minimax regret is flagged as open, the vector grouping is labeled a projection heuristic, and Oracle-DA is described as non-deployable. My concern targets the central algorithmic inference, not the theorem's validity. A one-sided upper bound does not make its minimizer a valid surrogate for the quantity it bounds; without a reverse inequality or a structural condition, minimizing Δ(x*) can be strictly worse in regret than other safe merges, including merges with zero regret. This is a load-bearing gap in the claim that regret minimization reduces to one true solve plus a cheap surrogate. The paper's own table shows a gap between the surrogate-based method and exact regret minimization, but the design conflates surrogate slack with projection-heuristic error. The proposed exhaustive check would settle whether the surrogate itself is faithful. Because the theorem is correct and the limitations are stated, I do not think rejection is warranted; the conditional verdict stands, with the surrogate question made an explicit condition.","tokens_in":7602,"tokens_out":19644,"duration_ms":216861,"concrete_test":"Enumerate all safe K-groupings for small instances (e.g., N=5..6 boxes, K=2, scalar and vector frames, lower expected cost). For each grouping compute the true regret R and the bound Δ(x*). Check whether argmin Δ equals argmin R; when they differ, record R(argmin Δ)/min_R and the fraction of instances with disagreement. Also search for a two-decision/two-merge counterexample where argmin Δ has positive regret while some other merge has zero regret. If such instances exist, the one-point bound is only an upper bound, not a decision-aware objective, and the central algorithmic claim must be demoted to a heuristic.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1's inequality chain is correct, but the passage from 'R ≤ Δ(x*)' to the algorithm 'solve once, then pick the merge that least distorts that decision' (Sec. 3, 'From bound to algorithms') is not justified. Δ(x*)=0 is sufficient for R=0 but not necessary: a safe merge can keep the decision unchanged while still raising the true optimum's criterion value, giving Δ(x*)>0 and R=0. A different merge with smaller Δ(x*) can flip the decision. Bound-DA minimizes Δ(x*), so it may select a strictly worse merge in regret. No approximation guarantee for this surrogate (e.g., R(Bound-DA) ≤ c·min_R, or an instance class where the two optima coincide) is provided. The static experiments do not isolate this issue because Bound-DA is implemented for vector instances as a projection heuristic, so the gap to Oracle-DA (2.5% vs 1.8% decision changes in Table 2) could be caused either by the surrogate being loose or by the heuristic failing to minimize Δ. Both sources of error are unquantified. This concern is orthogonal to the acknowledged open minimax-regret monotonicity: it arises already for the lower expected cost, where monotonicity holds.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes decision-aware approximation of belief functions for linear evidential combinatorial optimization. The decision maker solves a 0-1 linear program whose cost vector is described by a mass function, and reduces the number of focal elements by safely merging boxes that dominate both endpoints. The paper defines approximation regret R(hat m) = Crit(x*(hat m); m) - Crit(x*(m); m), proves a one-point bound R(hat m) <= Delta(x*(m)) for monotone approximations (Theorem 1), gives an exact O(N^2 K) dynamic program for the scalar case (Proposition 1), and presents an online version that prunes before the final cost is known. Experiments on evidential shortest-path instances compare the decision-aware compressors Bound-DA and Online-DA with representation-aware baselines (Jousselme, Jaccard, largest-mass, random) and report decision-change rates, regret quantiles, and confidence intervals.","tokens_in":7820,"tokens_out":15236,"duration_ms":158294,"significance":"If the result holds, the paper offers a useful conceptual shift: when a belief function is an intermediate object in a decision pipeline, representational distance is not the right target. Theorem 1 is a clean, parameter-free result whose proof is a short valid chain, and the scalar dynamic program is derived from the stated assumptions. The experiments report 95% confidence intervals, cover both lower and upper expected costs, and include a non-linear readout as an explicit out-of-theory stress test. The main limitation is that the proposed algorithms minimize the one-point bound rather than the regret itself; the paper does not justify this surrogate as more than a heuristic, and the static experiments do not isolate the resulting gap.","major_comments":[{"comment":"Theorem 1 establishes R(hat m) <= Delta(x*(m)), but the passage from this inequality to 'pick the merge that least distorts that decision' is not justified. Minimizing Delta(x*(m)) over safe merges need not minimize R. For example, with X={x1=(1,0), x2=(0,1)} and cbar=(1,2), a safe merge that raises the first coordinate by 1.9 and leaves the second unchanged has Delta=1.9 and flips the decision (x1 cost 2.9 > x2 cost 2), while a safe merge that raises the first coordinate by 2.5 and the second by 2.5 has Delta=2.5 and preserves x1 (3.5 < 4.5). Thus the smaller-Delta merge can be strictly worse in regret. Since Bound-DA is defined as the Delta-minimizer, the central 'one-solve' claim is a heuristic surrogate, not a consequence of Theorem 1. The paper should either state this explicitly and frame Bound-DA as a heuristic, or provide an approximation guarantee / an instance class where the two optima coincide. Relatedly, Proposition 1 solves the surrogate objective exactly, not regret minimization.","section":"§3, 'From bound to algorithms'"},{"comment":"Bound-DA is implemented for vector instances as a projection heuristic, so the reported gap to Oracle-DA (2.5% vs 1.8% decision changes) conflates two sources of error: the gap between minimizing Delta(x*) and minimizing R, and the heuristic's failure to minimize Delta. The paper does not quantify either. A scalar study where Bound-DA is the exact dynamic program would isolate the surrogate gap; alternatively, report the achieved Delta and the true R for the selected groupings. Without such evidence, the claim that Bound-DA 'nearly matches' Oracle-DA is not fully supported.","section":"§4, static study, Table 2"}],"minor_comments":[{"comment":"The sentence 'preserving the decision can matter more than preserving it' is ambiguous; replace the final pronoun with 'the mass function itself' or 'the original body of evidence.'","section":"§1, introduction"},{"comment":"The sentence 'the upper expected cost behaves identically (2.4% at K=2)' reports no confidence interval or table; add the corresponding table row or a confidence interval for this value.","section":"§4, static study"},{"comment":"For Bound-DA, q95(R)=0.00 while max R=2.21 can be confusing to readers; consider reporting a nonzero upper quantile (for example, the 99th percentile) alongside the maximum.","section":"Table 2"},{"comment":"The remark that the decision-aware bound 'still targets' a minimax-regret criterion under an open condition could be read as stronger than warranted; consider writing explicitly that for that criterion all guarantees are conditional on the conjectured monotonicity.","section":"§3, 'Monotonicity is the whole hypothesis'"},{"comment":"The phrase 'clearly lowest under the linear read-out' is slightly stronger than the reported 95% confidence intervals support at K=2, where the intervals for Online-DA and greedy-Jousselme overlap; qualify the wording.","section":"§4, online study, Table 3"}],"recommendation":"major_revision","confidential_remarks":"The unresolved point is the surrogate gap in the central algorithmic claim. I would be satisfied with a revision that explicitly frames Bound-DA and Online-DA as heuristics minimizing a bound, removes or qualifies the phrase 'one-solve surrogate,' and adds a focused experiment or discussion quantifying the gap between minimizing Delta(x*) and minimizing R. Theorem 1 itself appears sound and is a genuine contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThis is a clean, honest paper on a niche topic: compressing a belief function to keep the downstream combinatorial decision unchanged, rather than to keep the mass function close in some intrinsic distance. The core is a correct one-point bound (regret ≤ distortion at the true optimum), an exact scalar dynamic program, and experiments showing decision-flip rates drop from ~14–18% to 2.5% at K=2 for the lower expected cost. That is a genuine result for evidential decision making.\n\nThe main soft spot is the step from the bound to the algorithm. The theorem says regret is controlled by Δ(x*), but Bound-DA minimizes that quantity. That is a surrogate objective, and nothing guarantees the minimizer of Δ(x*) is the minimizer of regret—in fact Δ(x*)=0 is sufficient but not necessary for R=0. The paper never claims an optimality guarantee, so this is a limitation rather than a contradiction, but it deserves explicit discussion. The vector-case experiments complicate the picture: Bound-DA there uses an unproven projection heuristic, so the gap to Oracle-DA conflates surrogate looseness with heuristic error. This issue is independent of the acknowledged open monotonicity question; it appears even for the lower expected cost.\n\nTwo smaller points. The one-point bound is essentially the standard SPO regret inequality; an explicit acknowledgment would be appropriate. And no code or data are provided, limiting reproducibility.\n\nOn the plus side, the paper addresses the obvious objection—\"if you can solve once, why approximate?\"—by correctly stating that the goal is memory and online computation, not tractability. It is also transparent about the open monotonicity for minimax regret and the fact that Online-DA is only a proxy under non-linear read-outs.\n\nWho should read it: researchers in belief function approximation, evidential optimization, and decision-focused learning. It deserves serious peer review; I would send it to a venue that covers uncertainty reasoning and ask for a sharper treatment of the surrogate gap, ideally with a counterexample or a partial guarantee, and for data or code.\n\nBest.","headline":"Clean, honest paper on decision-aware belief function compression; correct one-point bound, but the surrogate minimization lacks a guarantee.","tokens_in":8355,"tokens_out":5847,"would_cite":false,"duration_ms":58600,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","90C39","68T37"],"pacs":[],"model":"deepseek-v4-flash","headline":"Compressing belief functions for combinatorial decisions should target the decision, not the evidence distance, and a one-point regret bound makes the right target cheap.","keywords":["belief functions","decision-aware approximation","evidential combinatorial optimization","decision regret","safe merge","one-point bound","dynamic programming","evidential shortest path"],"falsifier":"For lower expected cost on any small instance, enumerate all safe $K$-groupings and compute both $R(\\hat m)$ and $\\Delta(x^\\star(m))$; a single grouping with $R(\\hat m)>\\Delta(x^\\star(m))$ would contradict Theorem 1. To test the open monotonicity hypothesis, construct one safe merge and one feasible $x$ for a minimax-regret criterion with $\\mathrm{Crit}(x;\\hat m)<\\mathrm{Crit}(x;m)$.","tokens_in":7312,"feed_emoji":"🎯","tokens_out":7279,"duration_ms":70754,"temperature":0.7,"pith_summary":"The paper argues that when a belief function is only an input to a combinatorial optimization, compressing its focal elements should preserve the induced decision, not the body of evidence. It exhibits a shortest-path instance where the merge judged closest by Jaccard or Jousselme distance changes the optimal path, while a decision-aware merge keeps it, and shows such flips occur on a non-negligible fraction of random instances. The central result is a one-point bound: under monotonicity, the decision regret of any safe approximation is at most the criterion distortion at the true optimum, so regret control reduces to one true solve plus a cheap surrogate. An exact $O(N^2K)$ dynamic program solves the scalar case, and an online variant prunes focal elements before the final cost is known. If correct, this gives a memory- and latency-saving compression rule that changes downstream decisions much less often than distance-based compression.","feed_headline":"Preserve the decision, not the evidence distance","feed_subtitle":"A one-point regret bound lets cheap approximations keep combinatorial optima unchanged, flipping decisions far less often.","key_machinery":"The safe merge is the join in the cost-dominance order: merging boxes $A_i,A_j$ produces a box with lower endpoint $\\underline a_B = \\max(\\underline a_i, \\underline a_j)$, upper endpoint $\\bar a_B = \\max(\\bar a_i, \\bar a_j)$, and summed mass. Since both endpoints only rise, the criterion distortion $\\Delta(x)=\\mathrm{Crit}(x;\\hat m)-\\mathrm{Crit}(x;m)$ is nonnegative for $x\\ge 0$ under linear expected-cost criteria, and that monotonicity is exactly what Theorem 1 uses. The one-point bound localizes the regret at the single true optimum $x^\\star(m)$. For the scalar case, the program sorts boxes by the relevant bound and performs ordered clustering with block cost $\\mathrm{cost}(i,j)=a_j W(i,j)$, solved by the recurrence $D[j,K]=\\min_{i\\le j}\\{D[i-1,K-1]+\\mathrm{cost}(i,j)\\}$ in $O(N^2K)$. The online version substitutes a local sensitivity $w_t$ for the not-yet-known optimum, minimizing per-step drift; linear read-outs make distortion additive so per-step bounds telescope, while non-linear read-outs break additivity and leave the online rule a proxy.","core_discovery":"The core discovery is that representation fidelity and decision fidelity can diverge sharply: the approximation closest to the original mass function can be the one that destroys the decision, while a merge that is farther in evidence distance can have zero regret. The paper formalizes the right objective as approximation regret $R(\\hat m) = \\mathrm{Crit}(x^\\star(\\hat m); m) - \\mathrm{Crit}(x^\\star(m); m)$, and proves Theorem 1: for any safe approximation that is monotone for the criterion, $R(\\hat m) \\le \\Delta(x^\\star(m))$, where $\\Delta(x) = \\mathrm{Crit}(x; \\hat m) - \\mathrm{Crit}(x; m)$. Because safe merges raise both box endpoints, monotonicity holds for lower and upper expected cost. This turns regret minimization into a one-solve offline surrogate and, in the scalar case, an exact ordered-clustering dynamic program; the online variant replaces the unknown true optimum with a local sensitivity proxy. In experiments across 2500 random shortest-path instances, the bound-aware compressor changes the decision in about 2.5 percent of cases at $K=2$, versus roughly 13 to 18 percent for representation-aware baselines, nearly matching the clairvoyant oracle.","pith_inferences":["The one-point bound suggests a general principle for compression under uncertainty: any monotone surrogate that never lowers the true criterion admits a regret bound at the optimum, a property that may extend to other uncertainty representations besides belief functions.","For non-linear read-outs, replacing the linear surrogate with a local sensitivity derived from the read-out's own variation might restore a per-step guarantee under monotonicity and Lipschitz conditions.","The Monge structure of the scalar block costs hints at much faster acceleration for large focal sets, making the exact dynamic program practical well beyond the experiments reported.","In settings where the belief function is itself estimated from data, the same decision-aware objective could guide which evidence to keep or acquire, not just how to compress a fixed body of evidence."],"forward_implications":["A deployable compressor can solve the true problem once, then pick merges that least distort the criterion at that single optimum, avoiding re-solving for every candidate compression.","The guarantee transfers beyond shortest paths to any linear evidential $0$-$1$ problem, such as knapsack or assignment, whenever the criterion is monotone under safe merges and a deterministic solver is available.","Decision-aware and representation-aware compression are complementary: the right choice depends on whether the mass function is a final summary or an intermediate consumed by a decision.","The online variant gives an anytime method for streaming belief accumulation, with regret control for linear read-outs; non-linear read-outs are explicitly outside the guaranteed regime.","Because the same safe merge serves both lower and upper expected cost, the decision-aware compression also supports robust readings of the decision."],"supporting_citations":[{"why":"Supplies the transferable-belief-model view in which the mass function is the credal object and the approximation is a computational shortcut to a decision.","marker":"[10]"},{"why":"Provides the safe-merge operation used throughout, joining boxes in the cost-dominance order with masses added.","marker":"[11]"},{"why":"Defines the Jousselme distance used as the main representation-aware baseline that the decision-aware method is compared against.","marker":"[6]"},{"why":"Supplies the largest-mass approximation baseline, a standard focal-element reduction method used in the experiments.","marker":"[12]"},{"why":"The closest prior decision-driven approximation, which the paper distinguishes by noting it lacks a decision-regret guarantee and targets a single-attribute pignistic decision.","marker":"[1]"},{"why":"Shows the underlying evidential combinatorial problems are already tractable, which frames approximation as a memory and online-computation need rather than a tractability fix.","marker":"[14]"},{"why":"Provides the Dempster-Shafer foundation for mass functions and focal elements that the whole setting builds on.","marker":"[9]"}],"fun_headline_variants":["Decision-aware merge beats evidential closeness","Minimize regret, not distance, in evidential optimization","One-point regret bound keeps optima unchanged","Decision fidelity beats evidence fidelity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's guarantee rests on the approximation never lowering the criterion for any feasible solution; the authors prove this for lower and upper expected cost, but for minimax regret they leave it as a conjecture, so that case is conditional.","fun_headline_variants_meta":{"raw":{"variants":["Decision-aware merge beats evidential closeness","Minimize regret, not distance, in evidential optimization","One-point regret bound keeps optima unchanged","Decision fidelity beats evidence fidelity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000711,"raw_usage":{"total_tokens":3231,"prompt_tokens":1005,"completion_tokens":2226,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":621,"completion_tokens_details":{"reasoning_tokens":2172}},"tokens_in":621,"tokens_out":2226,"duration_ms":17866,"temperature":1.0,"reasoning_tokens":2172,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T20:08:24.735950+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For lower expected cost on any small instance, enumerate all safe $K$-groupings and compute both $R(\\hat m)$ and $\\Delta(x^\\star(m))$; a single grouping with $R(\\hat m)>\\Delta(x^\\star(m))$ would contradict Theorem 1. To test the open monotonicity hypothesis, construct one safe merge and one feasible $x$ for a minimax-regret criterion with $\\mathrm{Crit}(x;\\hat m)<\\mathrm{Crit}(x;m)$.","supporting_citations":[{"cited_title":"In: Belief Functions: The- ory and Applications (BELIEF 2021)","cited_arxiv_id":null,"evidence_quote":"Provides the safe-merge operation used throughout, joining boxes in the cost-dominance order with masses added."},{"cited_title":"Information Fusion2(2), 91–101 (2001).https://doi.org/10.1016/ S1566-2535(01)00026-4","cited_arxiv_id":null,"evidence_quote":"Defines the Jousselme distance used as the main representation-aware baseline that the decision-aware method is compared against."},{"cited_title":"Artificial Intelligence61(2), 315–329 (1993).https://doi.org/10.1016/ 0004-3702(93)90072-J","cited_arxiv_id":null,"evidence_quote":"Supplies the largest-mass approximation baseline, a standard focal-element reduction method used in the experiments."},{"cited_title":"Annals of Operations Research344, 383–412 (2025).https://doi.org/10.1007/s10479-024-06331-8","cited_arxiv_id":null,"evidence_quote":"Shows the underlying evidential combinatorial problems are already tractable, which frames approximation as a memory and online-computation need rather than a tractability fix."}],"review_version":1}