Regret-aware evidential cost compression
Implementation & benchmark of arXiv:2608.10650 — Decision-Aware Approximation of Belief Functions for Evidential Combinatorial Optimization
Source paper: Decision-Aware Approximation of Belief Functions for Evidential Combinatorial Optimization arXiv:2608.10650 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Attach an evidential cost head to a neural graph model, representing each edge cost by a weighted set of interval boxes, and compress this representation before the downstream shortest-path or routing solver. Instead of minimizing Jaccard or Jousselme distance between the original and compressed mass functions, choose merges that minimize the induced cost error on the currently selected route, while enforcing a conservative monotonicity condition so that the resulting path regret is bounded.
Formulas
Mathematical statement
For a finite feasible set $X\subseteq\{0,1\}^{n}$ and focal boxes $F=[\underline a_F,\overline a_F]$ with mass $m(F)$, the lower linear criterion is $\mathrm{Crit}(x;m)=\sum_F m(F)\underline a_F^\top x=\bar c^\top x$, where $x$ is a binary decision vector and $\bar c=\sum_Fm(F)\underline a_F$. Let $x^\star(m)=\arg\min_{x\in X}\mathrm{Crit}(x;m)$ and let $\hat x=x^\star(\hat m)$ be the decision under a compressed mass function. Define the compression error $\Delta(x)=\mathrm{Crit}(x;\hat m)-\mathrm{Crit}(x;m)$. Theorem 3.1 states that if $\Delta(x)\geq0$ for every feasible $x$ (criterion-monotone compression), then the decision regret $R(\hat m)=\mathrm{Crit}(\hat x;m)-\mathrm{Crit}(x^\star;m)$ satisfies $R(\hat m)\leq\Delta(x^\star)$. In a neural adaptation, represent the original expected lower edge-cost vector by $c\in\mathbb R_+^n$ and the compressed one by $\hat c\geq c$ componentwise; then $\Delta(x)=(\hat c-c)^\top x\geq0$ and $R(\hat x)\leq(\hat c-c)^\top x^\star$. The unavailable $x^\star$ can be approximated by the route produced before compression, $x_0$.
Implementation notes
(1) Integration point: place the compressor between a neural graph or edge-cost predictor and the exact or approximate shortest-path layer. For each graph edge $e$, make the network output $K$ interval focal elements $F_{e,k}=[l_{e,k},u_{e,k}]$ and nonnegative masses $m_{e,k}$ normalized over $k$. The downstream lower expected cost is $c_e=\sum_km_{e,k}l_{e,k}$. At inference, reduce each edge's focal elements to $K'<K$ before running Dijkstra, Bellman-Ford, beam search, or a differentiable path solver. (2) Pseudocode: compute $(l,u,m)$; compute $c_e=\sum_km_{e,k}l_{e,k}$; solve the uncompressed problem to obtain a provisional route $x_0$; for every candidate pair of focal elements $(i,j)$, form their merged interval $[\min(l_i,l_j),\max(u_i,u_j)]$ and merged mass $m_i+m_j$; recompute the compressed expected costs $\hat c$; reject any merge with some $\hat c_e<c_e$; score the remaining merge by $s_{ij}=(\hat c-c)^\top x_0+\lambda\|\hat c-c\|_1$; apply the lowest-score merge repeatedly until $K'$ remains; solve using $\hat c$. The first term is the empirical proxy for the paper's bound $\Delta(x^\star)$. (3) Compute from the mathematics: the lower expected criterion, the componentwise conservative condition, the route-local error, and the regret upper bound. Estimate empirically: $x^\star$ is unavailable after compression, so use the uncompressed route $x_0$, and optionally refresh $x_0$ every few merges. Compare against random pruning, highest-mass pruning, and Jaccard-distance focal-element merging. (4) First experiment: train a small message-passing GNN on random $20\times20$ grid graphs to predict edge-cost intervals from node and edge features, then evaluate shortest paths on held-out graphs. Use $K=16$ focal elements per edge and test $K'\in\{2,4,8\}$. Measure path regret under the original evidential costs, route-flip frequency, compressor runtime, and memory. Success means substantially fewer route flips and lower regret than Jaccard compression at the same $K'$, with no more than a modest increase in compression time; a useful target is at least 2x lower flip frequency at $K'=4$.
Verification
Stage 1 · Toy mechanism gate: Failed ✗
Stage 2 · Mechanism transferred to benchmark: Not tested
Stage 2 · Practical benchmark result: Not run
Methodology: Toy-system gate first; the benchmark stage runs only after a pass. How verification works
Stage 1 — Mechanism check agent confidence 9/10
Built a small exhaustive layered-graph MVP with conservative evidential-cost compression, theorem verification, route-local scoring, and baseline comparisons. The monotonicity condition held numerically and the regret bound had zero observed violations across 10 trials, but the required compression-level scaling did not manifest: K' values produced identical results, and regret-aware, Jaccard-like, and random baselines were indistinguishable in the tested runs. Therefore the mechanism was not demonstrated, and this is not a validated win.
- Agent confidence
- 9/10
- Baseline
- At K=8 to K'=2: mean regret 0.142435, flip rate 1.0 for the Jaccard-like baseline; random had the same mean regret and flip rate.
- Idea
- Theorem check: maximum bound violation 0.0, mean regret/bound ratio 0.1239. At K=8: mean regret 0.213400, flip rate 1.0, mean bound 1.688280, total inflation 4.054034; K'=1,2,3 unexpectedly gave identical values.
Limitations: No neural graph model was trained or integrated, no Dijkstra implementation or runtime or memory measurement was performed, interval upper endpoints were not used in the cost calculation, and the toy sweep exposed an implementation/design issue because compression targets did not affect the reported outcomes. The focal-element merge surrogate is therefore only a conservative cost approximation, not a faithful implementation of the proposed interval-box merge.
How to run: python3 fast_experiment.py
Verdict computed by deterministic test code from paired-seed statistics — not by the language model.
Artifacts
- fast_experiment.py 3.2 KB View Raw
- math_experiment.py 4.3 KB View Raw
- report.md 1.7 KB View