# Algorithm design: Model redundancy in tests

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 (:

• What are you trying to do ?
– user16034
May 16 at 13:47
• Pardon my stubbornness, but usually you resort to sorting for some purpose, such as finding bugs. When a test passes, all you can say is that it spotted no bug. When a test fails so finds a bug, the targeted software will be modified to solve the bug; then the test will no more reveal it (obviously). So globally, you never learn anything about the "power" of the tests.
– user16034
May 16 at 13:57
• I'd like to reduce the time it takes to run a test suite by finding redundant tests. If two tests always fail and pass in conjunction, just passing one is a good indication the other would succeed. So we can skip running the later test on a quick run for partial confidence. Does this make sense? May 16 at 17:37
• If you can't afford running all tests, select them randomly.
– user16034
May 16 at 18:28

# 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.

• I see. I agree it's hard to imagine the gains from a sophisticated strategy will merit the overhead. I was hoping there might be more literature or canonical approaches for the topic but it appears not. Thanks for the pointers to the filter stuff -- it seems pretty simple to try out so why not. May 16 at 20:07
• P.S. do you have any ideas for how to approach the boolean algebra question i.e. how to find $n$ boolean formulas over $m$ variables that match $k$ outputs? May 16 at 20:12
• @lyberius, can I encourage you to ask that as a separate question, and develop the question a bit more? What kinds of boolean formulas do you allow? (a CNF clause? any CNF formula?) What does it mean to match an output?
– D.W.
May 17 at 3:05