Algorithm design: Model redundancy in tests

Question

I've run across an interesting problem at work that I'm not quite sure how to grapple.

Broadly, there is a suite of of $n$ tests to ensure the quality of a product. However, the tests are both time-intensive and frequently run so it's necessary to tradeoff confidence for performance.

Approach 1: knapsack

For any test $x_i$, let $t_i$ represent the time it takes to execute. If we can define some measure of the "quality" of a test, $q_i$, we can find the subset of tests that maximize $\sum q_i$ while $\sum t_i \leq T$ where $T$ is some time limit. Though, unlike $t_i$, $q_i$ is difficult to measure or even define. Perhaps $q_i$ is a correlation between $x_i$ passing and the whole suite passing? Or manually set to reflect the "importance" of a test? This doesn't feel right since the magnitudes of $q_i$ sharply affect the outcomes. The better estimate of $q_i$ would be rank-based.

Approach 2: probability

If a single test fails, the whole test run fails and can abort preemptively. Forgive an abuse of notation and let $\bar{x_i}$ represent the event test i fails. We can consider finding the permutation $j_1, j_2, \dots, j_n$ such that $j_1 = \max_i P(\bar{x_i})$ and $j_2 = max_i P(\bar{x_i}|x_{j_1})$ and so on. Then, I could truncate the test suite to run the first $m$ tests $x_{j_1}, x_{j_2}, \dots, x_{j_m}$. Factoring in the time of the tests and improving on the greedy method could be later adjustments.

Approach 3: boolean witchcraft

Suppose there was a latent set of boolean variables $I_1, I_2, \dots, I_m$ that fully described the system and its test performance. (I imagine this to correspond roughly whether or not certain subcomponents of the system are correct). Then each test $x_i$ could be understood as a boolean formula over those latent variables. Using historical data, we could try to reconstruct the most likely formulas and remove the tests that are "covered" by other tests e.g. if $x_3$ passes when $x_1$ passes AND $x_4$ passes, it can simply be removed. There are a couple worries I have with this approach. One, that beginning assumption was a strong one -- how do I pick $m$? Too large and the system is barely constrained; too small and the formulas barely predict the data. It feels like it requires the same divine revelation involved in picking the number of clusters in clustering. Two, how does one find the most likely boolean formulas, anyhow? Probably not by iterating over all ${2^{2^m}}$ possibilities, right?

Approach 4: clustering

Speaking of clustering, maybe something could work with the same subcomponents mental model as above. If we have $k$ historical test suite runs, we have a $k$-length vector $d_i$ which describes the test's historical results. One approach could be to cluster these vectors and only test tests closest to the $m$ centers. Again, there's a lot of faith with the $m$ parameter plus there's very little nuance to tune here.

Approach 5: principal analysis

Hey, if we have the vectors, why stop there? Together, they form a $k \times n$ data matrix $D$ and that reduces this to the trivial problem of feature selection. This post mentions some nice ways to extract high variance-explaining tests using some variants of PCA. The downside here is I'm abandoning the discrete structure of the problem and getting pretty deep in the weeds.

---

If anyone has wisdom into choosing between these approaches, fleshing them out, or suggesting a different one altogether, I'm all ears. This has been a fun jaunt in algorithm design, but I would like to implement something useful at the end of the day as well (:

Answer 1

Theoretical perspective

One reasonable approach is to sort tests by $t/p$, where $t$ is the time to execute the test and $p$ is the probability the test fails. One can prove that if tests fail independently, then there is a sense in which this algorithm is optimal; see What is the optimal strategy for filtering a large collection of items with multiple filter functions?, Determine what is the best order for running filters on a dataset.

Caveats

In practice, it might be difficult to estimate $p$, the probability of a test failing, for the reasons articulated by Yves Daoust. So it might be hard to do much better than setting $p$ to be the same for all tests; or, the effort to track the number of times that the test has failed in the past might not be worth the extra effort.

In practice, tests may not be independent, so this model may not be accurate and this schedule may not be optimal. However, characterizing the correlations between tests sounds complex to me, so the simple solution above might be a reasonable pragmatic choice.

Pragmatic perspective

Overall, in practice, it is not clear whether any sophisticated strategy is going to do sufficiently better than just running the tests in a random order that it is worth the extra implementation complexity to implement the sophisticated strategy.