Fixed Probing Orders When Failures Are Expensive

Many screening problems share one shape. Each candidate, test, or box has a hidden state, and you pay time or money to look at it. An adaptive policy chooses the next item after seeing the last outcome. A non-adaptive policy commits to an order in advance and simply runs down the list until the budget runs out. Theory on stochastic probing (problems where items reveal a random state only when inspected) says the fixed order loses at most a factor of 2 for monotone submodular objectives, meaning objectives with diminishing returns. That result assumes inspection costs are deterministic. In real pipelines the cost of looking depends on what you find. A bad hire wastes a long interview. A failing diagnostic test takes the slow path. A dead-end lead consumes the most search time. The best existing guarantees for these state-dependent costs come from adaptive policies, and the strongest of them only holds when the expensive states are also the valuable ones.

This note proposes to settle whether a single precomputed order can stay within a constant factor of the best adaptive policy when an item's cost depends arbitrarily on its revealed state, including the case where failures cost the most. It also proposes to build that order in polynomial time. The central technical bet is that the budget, after truncation, turns into a deterministic knapsack constraint on how often each item is probed, and that this holds no matter how cost and quality are coupled. If that bet holds, the "cost equals quality" assumption is an artifact of the analysis, not of the problem. If it fails, we want an explicit family of instances showing that adaptivity becomes essential once failures are expensive.

Core Claim

The setting has $n$ items. Item $i$ has a random state $X_i$ drawn independently from a known discrete distribution. Its probing cost $C_i = c_i(X_i)$ is any function of that state. The process has a total budget $B$. The objective is a monotone submodular function $f$ of the (item, state) pairs that were probed and fit within the budget. An item whose realized cost exceeds the remaining budget contributes nothing and ends the process. A non-adaptive policy is a permutation of the items, run until the budget is exhausted.

We conjecture that the adaptivity gap in this model is bounded by an absolute constant, with no dependence on the correlation between $c_i$ and the state's contribution to $f$. We also conjecture that a list we call the truncated-cost stem list achieves such a constant using only a value oracle for $f$.

The anchor fact is standard and does not depend on any cost–quality coupling. Write $\mu_i = \mathbb{E}[\min(C_i, B)]$ for item $i$'s truncated mean cost, and $y_i$ for the probability that a given adaptive policy probes item $i$. Then

$$\sum_i y_i\,\mu_i \le 2B,$$

because the decision to probe $i$ is made before $C_i$ is revealed, and the realized truncated costs of all probed items sum to at most $2B$. This gives an upper-bound relaxation on the adaptive optimum that ignores how cost and value co-vary. The difficulty then sits entirely in the rounding step, where a fixed order must avoid spending its budget on expensive failures before reaching the items that pay off.

Relation to Prior Work

Two papers set the stage by proving that fixed orders are nearly optimal when costs are deterministic. Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions bounds the gap by 3. Its key tool is the "stem", the path an adaptive decision tree follows when every probed item comes back negative. (Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing tightens the gap to exactly 2 for multi-valued states using a random-walk strategy: sample one root-to-leaf path of the optimal tree and probe everything on it. Both arguments break here. A sampled path was feasible under the costs that happened along that path. Re-run with fresh cost draws, it can overflow early, and it tends to do so precisely on the expensive-failure items. We reuse their path-sampling idea but change what gets sampled.

Three papers handle stochastic or state-dependent costs, all with adaptive policies, and they set the bar we must meet without adaptivity. Adaptive Submodular Maximization under Stochastic Item Costs gives MIX, which blends cheap-item greedy with a best-single-item choice and guarantees $\frac{1}{6}(1-e^{-\beta/4})$. Constrained Stochastic Submodular Maximization with State-Dependent Costs gives the policy $\pi^{io}$, whose guarantee explicitly requires that higher-utility states cost more. The authors flag the costly-failure case as unhandled. Stochastic Submodular Probing with State-Dependent Costs reaches $1-1/e$ with StoCan, but only by allowing a rejection decision after each probe, which is adaptive. Our proposal differs from all three in two ways: the output is a single order, and no monotone link between cost and quality is assumed.

Two non-adaptive constructions supply the method we borrow. Non-Adaptive Stochastic Score Classification and Explainable Halfspace Evaluation builds one priority list in phases. Each phase solves two knapsack problems, one bounding progress from successes and one bounding progress from failures. We adapt this two-sided bookkeeping so that each phase budgets truncated cost separately for "productive" and "unproductive" states. Submodular maximization with uncertain knapsack capacity shows that a list built by doubling budget scales stays robust when the stopping point is unknown. That is also our situation, since a fixed order cannot know when realized costs will exhaust $B$.

One more paper constrains the design. Kawase et al. prove that without the ability to cancel an overflowing item, no constant robustness is possible when the capacity distribution is unknown. Our model has a known budget and known cost distributions, which is consistent with that impossibility result. We will state this boundary explicitly in the paper rather than leave it implicit.

Research Program

Step one: the relaxation. Maximize the concave closure of the expected value of $f$ over (item, state) pairs, subject to the truncated-cost constraint above. Split each state into "small" (cost at most $B/2$) or "large" (cost above $B/2$). At most one large state can ever be collected within budget, so the large-state contribution reduces to a single-winner problem in the spirit of Pandora's box. We handle it with a fixed order sorted by an index computed from $\mu_i$ and the large-state values, mirroring the singleton arm of MIX.

Step two: rounding the small-state part. Round the small-state part into a stem list. Group items into geometric phases by truncated cost: phase $j$ is allotted truncated-cost budget $2^{j}$ up to $B$, in the manner of the doubling construction. Within each phase, choose items by solving two knapsacks, following StochKnap. One knapsack caps the expected truncated cost spent in states that add value. The other caps the expected truncated cost spent in states that add nothing.

The second knapsack is the new ingredient. It prevents a phase from being dominated by items whose failures burn budget. That is exactly the case where analyses built on the cost-equals-quality assumption fail. The final policy flips a coin between the small-state list and the large-state order, or concatenates them; we will compare both.

Step three: the analysis. Use a stem-style induction in which the "all-no" path is replaced by a "cheap-or-no" path. The target lemma is that, at each phase boundary, the fixed list has spent at most a constant multiple of the adaptive policy's truncated cost while collecting a constant fraction of its marginal value.

Step four: the converse, attempted in parallel. We will search for instances in which an adaptive policy exploits an observed expensive failure, by switching to cheap items, in a way no order can imitate. If such a family drives the gap with $n$, the result becomes a separation theorem showing that the cost-equals-quality assumption is necessary for non-adaptive policies.

Baselines

Naive reference. The do-nothing reference is a random permutation run until the budget runs out, together with value-sorted order. Selection and Ordering Policies for Hiring Pipelines via Linear Programming proves that value-sorted order can be arbitrarily bad without a lower bound on values, so it should look worst in the costly-failure regime. Both run on identical instance draws.

Strongest classical heuristic. Order items by expected marginal value per truncated mean cost, $\mathbb{E}[\Delta f]/\mu_i$, mixed with the best single item. This is the natural non-adaptive reading of MIX and the classical stochastic-knapsack recipe. It is the competitor most likely to match us, because it already uses the truncation idea. Beating it means a statistically clear improvement in mean value (paired across 1,000 instance draws) in the regime where failure states cost more than success states. In the cost-equals-quality regime, a tie is expected and acceptable.

Strongest adaptive comparators. StoCan and $\pi^{io}$ serve as the adaptive reference points; MIX run adaptively is also included. They are implemented from the papers with the same value oracle and the same number of Monte Carlo samples for their continuous-greedy steps. The question is how much of their value a fixed order retains, not whether we beat them.

Exact optimum and upper bounds. For $n \le 12$, exact dynamic programming gives the true adaptive optimum and brute force gives the best permutation, so the gap is measured directly. For larger $n$, the truncated-cost relaxation provides the upper bound.

Key ablation. Remove the failure-cost knapsack, keeping only the single knapsack on productive cost. This isolates whether the two-sided bookkeeping is what does the work.

Published numbers. No reported result found on Lacuna for non-adaptive policies under state-dependent costs. The closest published empirical anchors are on neighboring problems. On the hiring benchmark, Hiring Under Uncertainty reports its sequential algorithm "often sitting very close to the LP upper bound", with no exact number given. For SSClass, the non-adaptive list's cost was "frequently within 50% of the information-theoretic lower bound."

Why not just…?

Why not just use the value-per-truncated-cost greedy order? This is the real threat, and the proposal is built to test it head on. Greedy by a ratio has no guarantee when a high-ratio item's expected cost is mostly spent in failure states. Its ratio averages over states, so it cannot tell "expensive and useful" apart from "expensive and useless" at the same mean. Purohit et al. show that simple greedy fails even with deterministic costs under deadlines. The ablation and the costly-failure regime will show whether the gap matters in practice. If the ratio greedy matches our list everywhere, the contribution shrinks to a proof that this simple rule is provably near-optimal, and we would say so.

Why not just run StoCan or $\pi^{io}$ adaptively? Adaptive policies need sequential feedback that blocks parallel execution and committed pipelines. Non-Adaptive Stochastic Score Classification and Explainable Halfspace Evaluation reports its non-adaptive list as 100 times faster than adaptive methods at 900 components. Moreover, $\pi^{io}$ has no guarantee once failures are costly. The experiments report the fraction of adaptive value retained, so a reader can weigh that loss against the operational gain.

Why not just optimize the permutation by Monte Carlo local search? On small instances this may match or beat our list empirically. That is why we include it at an equal simulation budget. It offers no guarantee and can stall on instances where a long prefix of cheap items must be placed before the payoff. We also test it seeded with our list, which is the practical recommendation if local search wins.

Why not just allow a few rounds of batched probing? The Power of Adaptivity for Stochastic Submodular Cover found 6–7 rounds on Epinions and 3 on WISER nearly as good as full adaptivity. That points to an extension rather than a replacement: a constant one-round gap is the base case any $r$-round analysis needs. We report 1-, 2-, and 3-round versions of our list, refreshing phases between rounds, to see where cost-state coupling makes extra rounds pay off.

Proposed Experiments

Hiring benchmark. The primary testbed extends the synthetic hiring pipeline benchmark used by Purohit et al. and Epstein and Ma: $n=100$ candidates, values $v_i \sim U[0,1]$, and the three regimes of correlation between value and acceptance (negative, positive, none). Each candidate's interview cost is drawn as a function of the realized outcome under three cost regimes:

  • cost increasing with quality, which is Tang's assumption;
  • cost independent of quality;
  • cost highest for rejecting or unqualified states.

The objective is a coverage-style submodular value over hired skill types, with budget $B$ swept from 5% to 50% of the total expected cost.

Coverage and diagnosis. The second testbed reuses the Epinions and Facebook coverage graphs and the WISER diagnosis scenarios from Ghuge et al. Here we attach state-dependent probing costs: probes that eliminate nothing take longer.

Metrics. We report expected value divided by the best available upper bound (the exact adaptive optimum for $n \le 12$, the relaxation otherwise), the empirical adaptivity gap, and wall-clock time.

Decisive checks. There are three. First, the measured gap on small exact instances must stay bounded as the cost–failure correlation is pushed to its extreme. Second, adversarial instance search, using hill-climbing on the distribution parameters to maximize the gap, must not find a gap that grows with $n$. If it does, the converse direction of the program takes over. Third, the two-sided list must beat its single-knapsack ablation and the ratio greedy specifically in the costly-failure regime, while tying them in the cost-equals-quality regime. A uniform win would suggest a tuning artifact. Having no regime-specific win would mean the mechanism is not doing what we claim.