Partition-Keyed Caching for Exact Rashomon Sets of Gene-Expression Decision Trees

Gene-expression studies measure about 20,000 genes on a few hundred patients at most. In that regime many different small models explain the data equally well, because co-regulated genes carry nearly the same information. A method that returns one gene signature therefore hides the others. The ideal output is the full set of near-best models, called the Rashomon set, so that a biologist can see which genes are interchangeable and which are essential. Exact search for small decision trees can produce this set. It does so through memoization: each sub-problem (here, "find the best subtree for this group of patients") is solved once and stored. But these searches choke when the number of features is large. This note argues that, for gene expression, the very fact that strangles the search can be turned around.

With only $n$ patients, a threshold on any gene can only split them into one of a limited number of groups. Thousands of genes induce the same split, or nearly the same one. The proposal is to key the cache on the split of patients itself rather than on the gene and threshold that produced it. Genes that induce identical splits then collapse into one search branch. Near-identical splits are merged under a provable bound on how much the loss can change. The result is a compact, factorized Rashomon set: a set of tree shapes over patient splits, each node annotated with the list of genes that could sit there. That list is an exact, tree-structured version of the "statistically equivalent signatures" that biologists already ask for.

Core Claim

Exact sparse-tree search on data where features far outnumber samples is limited by the number of distinct patient partitions at each node, not by the number of genes times thresholds. Partitions repeat heavily when $n$ is small. They repeat even more deeper in the tree, where only a handful of patients reach a node. A cache keyed on the pair (patients reaching this node, partition of those patients) makes Rashomon-set enumeration feasible on genome-wide data without throwing genes away beforehand. A gene-equivalence annotation then falls out of the cache at no extra cost.

The approach extends to near-duplicate partitions. Suppose two candidate splits at a node send the same patients left and right except for $d$ of them, out of $n$ training patients in total. Then any subtree evaluated under one split has misclassification loss within $d/n$ of the same subtree under the other. Only the $d$ patients that switch sides can change their predicted label, and each contributes at most $1/n$. A near-match can therefore reuse a cached solution while charging $d/n$ against the Rashomon tolerance $\epsilon$, the allowed loss gap from the best tree. Recall is never silently lost: a tree is excluded only if its certified loss exceeds the budget.

Relation to Prior Work

Two methods supply the machinery here. GOSDT solves optimal sparse decision trees by dynamic programming with bounds. It identifies each sub-problem by its "support set", the patients reaching a node, so that different paths to the same patients share one cached answer. Its authors note that it scales with the number of samples but degrades as the number of features grows. PRAXIS enumerates near-optimal trees using 64-bit fingerprints of data subsets, budget refinement across sibling subtrees, and fast proxy bounds. It has been evaluated on binarized benchmarks such as News, Higgs and Churn, never on gene expression. Both methods cache the patients reaching a node. Neither de-duplicates the candidate splits at that node, and that is where a $p \gg n$ problem spends its time.

The proposal reuses their support-set caching unchanged. It adds a second cache layer keyed on the induced partition, plus the $d/n$ near-match rule. In spirit this mirrors canonicity in knowledge compilation, where a canonical form for each sub-formula lets the compiler detect a repeated sub-problem with a pointer comparison. Here the canonical form is a sorted bitmask over the patients present at the node.

A tension in the literature motivates the design. CODT omits caching entirely because "repeated subproblems are rare with continuous features." That is true when the cache key is a gene and threshold. It should be false when the key is the partition and $n$ is small. The proposal makes this a measurable prediction rather than an assertion.

On the biology side, MXM's SES algorithm supplies both the motivation and the closest competitor. It shows that expression data harbor many equivalent signatures, with median performance variation under 5% across signatures. It groups interchangeable genes into "equivalence queues" via conditional-independence tests. However, SES is greedy, depends on a significance threshold and a maximum conditioning size, and gives no completeness guarantee. The proposed method gives exact equivalence classes with a certified loss bound.

The only prior bridge between caching and gene networks is Bryce and Kim. They detect duplicate belief states during search for intervention plans on small binarized networks such as WNT5A. Their problem is control, not signature discovery, and they never face thousands of continuous genes. PerturbCausal constrains the design in a different way. It finds that large virtual-cell models inflate perturbation effects about 23-fold and lose to a sparse linear model. That supports building on transparent sparse models rather than learned representations, and it is why no deep baseline is central here.

Research Program

The build has three layers on top of a PRAXIS-style enumerator.

The first layer is candidate generation. For the patients $S$ reaching a node, each gene is sorted over $S$. Only thresholds at boundaries where the class label changes are kept. Each resulting partition is converted to a bitmask over $S$ and stored in canonical form, with the side containing the lowest-index patient marked "left". The bitmask is hashed to a 64-bit fingerprint. Genes with equal fingerprints, after verifying the full bitmask to rule out hash collisions, form one equivalence class. The search branches once per class.

The second layer is near-match merging. Classes whose bitmasks are within Hamming distance $d_{\max}$ of a cluster representative are merged, and the $d/n$ charge is recorded on the merged edge. This layer has two consequences. The Rashomon set is reported as certified-in, meaning loss is within $\epsilon$ even after the charge, or as possibly-in. The final membership of possibly-in trees is resolved by exact re-evaluation, which is cheap because there are few such trees. Finding representatives for the clustering uses locality-sensitive hashing on the bitmasks.

The third layer is memory control. The two-level cache, keyed on support set and then on partition, is bounded by an eviction policy. Following Majercik and Littman, whose "Smart LRU" variant (least-recently-used eviction restricted to sub-problems of moderate difficulty) cut CPU time by up to 37% over plain LRU, sub-problems on very small support sets are not cached. Recomputing them is cheaper than looking them up.

The output is a factorized Rashomon set. Its size, counted in gene-level trees, is the sum over shapes of the product of class sizes. That count can be astronomically large while storage stays small. Analysis tools then compute, for each gene, the fraction of near-optimal trees in which it is replaceable. They also map classes onto pathway annotations to ask whether interchangeable genes share a pathway.

Baselines

The naive reference point is a single greedy classification tree (CART) of the same depth plus a cross-validated LASSO. Both are run on identical train/test splits. This shows what one arbitrary model achieves and how unstable its gene choice is across splits.

The strongest existing enumerator is PRAXIS. Its reported figures are a Rashomon recall averaging at least 0.98 on its benchmark suite, a 700-second search versus 1.3 days on News, and 40 minutes on Higgs where no competitor finished in 90 hours (Heile et al.). No reported result was found on Lacuna for PRAXIS, or for GOSDT, on gene-expression data. PRAXIS will be run in two modes:

  • Naive mode: PRAXIS on all genes, binarized at the same label-change thresholds the proposed method uses.
  • Prefilter mode: the practitioner's version, keeping the top-$k$ genes by univariate test before running PRAXIS, with $k$ tuned over the same compute budget.

Both PRAXIS modes, and the proposed method, get the same wall-clock limit, memory cap, depth limit, sparsity penalty and $\epsilon$. Beating PRAXIS means two things. First, completing genome-wide enumeration where it times out or exhausts memory. Second, at equal runtime, recovering a strictly larger certified Rashomon set, measured as recall against exact ground truth where that ground truth is computable.

The strongest biology-side competitor is SES from MXM. On its breast cancer and Vijver-2002 datasets it reports a median coefficient of variation below 5% across equivalent signatures. No accuracy figure for those datasets is given in the file. SES will be run with its $\alpha$ and $k$ tuned by the same cross-validation budget. Beating it means matching held-out accuracy while recovering more of the planted equivalent genes in synthetic data, and producing equivalence classes that are more stable across resampled splits.

Two ablations isolate the key ingredient:

  • Feature-keyed caching: keeps support-set caching but keys candidate splits by gene and threshold. This is essentially GOSDT/PRAXIS, and it tests whether partition keying is what buys the speedup.
  • Exact-only matching: sets $d_{\max}=0$, to measure what near-match merging adds on real, noisy data.

Why not just…?

Why not just prefilter to a few hundred genes and run PRAXIS? This is the most serious threat. If the Rashomon set over the top 300 genes matches the genome-wide one, the contribution shrinks to engineering. The prediction is that prefiltering by univariate signal drops genes that are weak alone but strong conditional on an upstream split. Such genes are common in trees, since deeper nodes see different patients. If so, prefiltered sets will miss trees and undercount equivalence classes. The planted-module synthetic experiment and the genome-wide breast cancer comparison settle this directly. If the prefiltered sets reach 0.98 recall at $k \le 500$, the paper should report that honestly as a negative result for the method.

Why not just cluster genes by correlation and keep one representative per cluster? Correlation is a global property. Partition identity is local to the patients at a node. Two genes correlated at 0.6 across the cohort can induce identical splits among the 15 patients at a depth-3 node. Conversely, highly correlated genes can split differently at the specific threshold that matters. Correlation clustering also offers no loss guarantee. The comparison runs correlation-representative PRAXIS at several clustering cutoffs and measures missed Rashomon members.

Why not just use LASSO or ElasticNet, or stability selection on top of them? These are fast and convex, and PerturbCausal shows that sparse linear models are hard to beat. But they return linear combinations, not equivalence classes. Lagani et al. report LASSO picking 148 variables against SES's 7 at equal accuracy on AquaticTox, which shows how arbitrary its choice among correlated features is. LASSO remains in the comparison as the accuracy floor. If depth-limited trees lose substantially to it in held-out accuracy, the interpretability argument weakens, and that will be reported.

Why not just rely on SES? SES is the closest existing answer to the biological question. Its limits are greediness and threshold sensitivity, not a wrong goal. The planted-module experiment tests whether exact enumeration recovers equivalences that SES's conditioning order misses.

Proposed Experiments

The first check is a direct test of the CODT tension. On the 17,816-gene breast cancer dataset from MXM and on the 257-sample TCGA LUAD cohort used by Wang et al., compute the ratio of distinct partitions to gene-threshold candidates at each depth. The method's premise predicts this ratio falls steeply with depth. If root-level partitions are almost all distinct and the ratio barely falls, exact-only caching is useless and everything rests on the near-match bound. Both outcomes are informative.

The second check is recall against ground truth. Random gene subsets of size 100 to 2,000 are sampled so that exact brute-force enumeration (no approximation, no near-match merging) is feasible. Certified recall and the runtime curve are then measured against $p$, alongside PRAXIS. The prediction is that runtime grows with the number of distinct partitions, roughly flat in $p$ once $p \gg n$, while PRAXIS grows with $p$.

The third check is a synthetic planted benchmark. Real expression matrices are taken and the label is replaced by a depth-2 or depth-3 tree over planted gene modules: groups of genes perturbed to induce the same or nearly the same split, with controlled noise. Success means recovering module membership as equivalence classes with higher precision and recall than SES and correlation clustering.

The fourth check is biological sanity on real tasks: breast cancer tumor type, Vijver-2002 survival dichotomized at a fixed horizon, and ARID2-mutant versus wild-type LUAD. The ARID2 task is a deliberately hard, imbalanced case at about 7% prevalence. The test asks whether equivalence classes are enriched for shared GO or KEGG pathway membership relative to size-matched random gene sets, and whether class membership is stable across bootstrap splits.

The decisive outcome is the comparison between the genome-wide run and prefiltered PRAXIS at matched compute. If the full partition-keyed search finds certified near-optimal trees, or equivalence-class members, that prefiltering provably excludes, the method earns its place. If it does not, partition keying is still a speed result, but the biological claim should be withdrawn.