Finite-budget dimension-adaptive Smolyak surplus selection

Input: dimension $d\ge 1$; a finite downward-closed cap $\mathrm{\Gamma }\subseteq {\mathbb{N}}_0^d$ containing $0$; for each coordinate, the one-dimensional quadrature rules from a hierarchy as in Nested one-dimensional quadrature levels and differences through every level used by $\mathrm{\Gamma }$, with canonical node keys that agree exactly if and only if the real nodes agree and are totally ordered; a function $f$ evaluable at the nodes; and an integer evaluation budget $B\ge 0$. Admissible inputs supply all these rules and keys at every level required by $\mathrm{\Gamma }$.

Output: a current downward-closed index set $\mathrm{\Lambda }\subseteq \mathrm{\Gamma }$, its Smolyak value when the initial rule fits the budget, the computed detail surpluses, the distinct nodes actually sampled, and one status: budget-too-small, budget-exhausted, or frontier-exhausted.

1. An index $\mathrm{\ell }\in \mathrm{\Gamma }\setminus \mathrm{\Lambda }$ is admissible when every immediate predecessor $\mathrm{\ell }-e_j$ with ${\mathrm{\ell }}_j>0$ already belongs to $\mathrm{\Lambda }$. Its surplus is the exact detail value ${\delta }_{\mathrm{\ell }}(f)$ and its selection indicator is $\mathrm{\mid }{\delta }_{\mathrm{\ell }}(f)\mathrm{\mid }$.
2. Form the baseline node set $X_0^d$. If its cardinality exceeds $B$, return budget-too-small, an empty $\mathrm{\Lambda }$, no cubature value, and no sampled nodes. Otherwise set $\mathrm{\Lambda }:=\{0\}$, initialize the active candidate set as empty, evaluate $f$ once at every baseline node, and set the current value to $Q_{\{0\}}(f)$. Then process every initially admissible index in $\mathrm{\Gamma }\setminus \mathrm{\Lambda }$ in lexicographic order using step 3.
3. Visit newly admissible indices in lexicographic order, skipping any index already recorded as active, accepted, or uncomputed-budget. To compute one surplus, form its finite tensor-detail node set and the new keys not already sampled. If adding them would exceed $B$, record this candidate as uncomputed-budget without evaluating those nodes. Otherwise evaluate each new key once, store the values, compute ${\delta }_{\mathrm{\ell }}(f)$ from the finite signed weights, and add the index to the active candidate set.
4. If the active set is empty and an admissible uncomputed-budget candidate remains, return budget-exhausted. Otherwise, if the active set is empty, return frontier-exhausted.
5. Otherwise select the active index with largest absolute surplus, breaking ties lexicographically. Remove it from the active set, mark it accepted, add it to $\mathrm{\Lambda }$, update the cubature value by adding its signed surplus, and inspect its finite forward neighbors for newly admissible indices; process them by step 3. Repeat from step 4.

The evaluation budget counts the union of distinct keys sampled while computing both accepted and candidate surpluses. The indicator $\mathrm{\mid }{\delta }_{\mathrm{\ell }}(f)\mathrm{\mid }$ is a refinement heuristic only. A threshold on this indicator, or exhaustion of the finite candidate cap, is not an error certificate unless a separate omitted-tail bound applies.