Explaining Models by Querying Compressed Samples

Some ways of explaining a classifier's prediction come with proofs of correctness. One kind names a minimal set of input features that is enough to fix the prediction. Another names a minimal set of features whose change would flip it. The two kinds are mathematically dual: each explanation of one kind is a minimal "hitting set" of all explanations of the other kind, meaning a smallest set that shares at least one feature with every one of them. A recent line of work makes these explanations model-agnostic by checking them against an empirical sample of labelled data rather than a symbolic encoding of the model. It reports polynomial-time algorithms that still take up to a minute per explanation on samples of a million rows, because every check rescans the raw table. This proposal observes that each such check is a small database query: "does any row of a different class agree with this instance on the chosen features?" Modern data systems answer queries like this orders of magnitude faster by running directly on compressed columns and never decompressing them. We propose to build the sample-based explanation checker as a compressed, instance-independent index over the sample. That index then serves as the checking step inside the hitting-set loop that enumerates explanations.

The payoff is practical. Auditing a model usually means explaining thousands of predictions, not one. The current algorithms pay the full cost of scanning the sample for every instance. An index built once and shared across instances turns explanation into query processing. The compression–computation trade-off then becomes a concrete design question: which encoding and which row order make explanation checks fastest, rather than the data smallest?

Core Claim

In Efficient and Rigorous Model-Agnostic Explanations, the authors define sample-based explanations over a sample $D$ with $n$ rows and $m$ features. A sample-based abductive explanation (sbAXp, a "why" explanation) is a feature set $S$ such that no row of $D$ with a different prediction agrees with the instance $x$ on every feature in $S$. The authors prove these are exactly the minimal hitting sets of the sample-based contrastive explanations (sbCXps, the "why not" explanations). The contrastive explanations are the subset-minimal sets of features on which some opposite-class row disagrees with $x$. The authors give an $O(mn)$ algorithm for one sbAXp and an $O(mn^2)$ algorithm for all sbCXps.

We restate the checking step as a query. Let $B_{j,v}$ be the set of rows whose feature $j$ takes value $v$, and let $O_c$ be the rows whose prediction differs from class $c$. The set $S$ is sufficient for $x$ exactly when

$$\bigcap_{j \in S} B_{j,x_j} \;\cap\; O_c = \emptyset .$$

The claim is that storing each $B_{j,v}$ as a run-length-encoded row set makes the cost of this check scale with the number of runs rather than with $n$. Here run-length encoding means storing consecutive identical entries as a single value and a count. The sets are built once for all instances, and the rows are sorted to lengthen runs on the features that explanation searches test most often. The check also returns a witness row whenever it fails. That row's disagreement set with $x$ is a new contrastive explanation, so the same index supplies counterexamples to a hitting-set enumerator at no extra cost. The index therefore does the checking work in both halves of the duality.

Relation to Prior Work

The motivating work is Efficient and Rigorous Model-Agnostic Explanations. It supplies the definitions, the duality proof and the benchmark. Its algorithms scan the uncompressed sample once per check and share nothing across instances. We keep its semantics exactly and change only how checks are answered.

The method comes from compressed-domain data systems. GPU Acceleration of SQL Analytics on Compressed Data runs filters and aggregates directly on run-length and index encodings using PyTorch tensor primitives, reporting up to 23.8x speedup over uncompressed GPU execution on TPC-H. It also notes that the speedup depends on row ordering. Tuple-oriented Compression for Large-scale Mini-batch Stochastic Gradient Descent stores rows in a prefix tree so that shared feature sequences are processed once. We borrow that idea for the enumeration phase: rows that share a prefix also share that part of their disagreement pattern with $x$. Neither system touches logic or explanations, and their access pattern differs from ours. They serve many unrelated analytical queries. We serve millions of highly correlated conjunctive queries that differ by one feature at a time, and that correlation is what makes incremental intersection and explanation-aware sorting possible.

Other work in the file shares the setting without supplying the method. The implicit hitting set loop is the standard way formal explanation tools alternate between a checker and a hitting-set optimizer. It is used in Most General Explanations of Tree Ensembles and From Contrastive to Abductive Explanations and Back Again. Efficient and Reliable Hitting-Set Computations for the Implicit Hitting Set Approach speeds up the optimizer half of this loop. We accelerate the checker half instead. Lossy Kernelization for (Implicit) Hitting Set Problems compresses hitting-set instances with bounded approximation loss. It is purely theoretical and is lossy, whereas our compression is lossless and leaves explanations unchanged.

Two cautions come from the file. Anytime Approximate Formal Feature Attribution shows that attribution computed from all abductive explanations is #P-hard even when all contrastive explanations are known. We therefore do not claim to make full enumeration tractable, only to make each oracle step cheaper. The data-dependence limits reported for tuple-oriented compression warn that dense, uncorrelated samples may compress poorly. We treat that as a measured risk, not an assumption.

Research Program

The first component is the index. We discretize features as the original paper does. We sort rows by a lexicographic key over a chosen feature order, then store each value's row set as run-length encoded intervals on GPU tensors. The prediction partition $O_c$ is stored the same way. Rarely occurring values fall back to explicit sorted row lists, following the index-encoding idea. A check intersects interval lists with a merge implemented through bucketize-style searches and stops at the first nonempty interval, which becomes the witness.

The second component is incremental search. A deletion-based sbAXp search starts with all features in $S$ and tries to drop them one at a time. We cache the running intersection over already-committed features, so each trial intersects only one extra set against a shrinking list. Many instances are processed together as a batch of such searches on the GPU.

The third component is enumeration through the duality. Witness rows yield disagreement sets. These are deduplicated and minimized over a prefix tree of the distinct opposite-class rows, which avoids the $n^2$ pairwise comparison when many rows repeat. They are then fed to an off-the-shelf hitting-set optimizer, which proposes candidate sufficient sets for the index to check.

The fourth component is the ordering question. We study how the sort key trades compressed size against check latency. We compare cardinality-based orders, which minimize total runs, against explanation-aware orders, which put first the features that deletion searches most often keep. Explanation-aware ordering is our hypothesized main contribution to the compression–computation trade-off. Its central test is whether the order that makes the data smallest differs from the order that makes explanation fastest.

Baselines

The naive reference point is the original implementation of Efficient and Rigorous Model-Agnostic Explanations, run unchanged on its 30-dataset benchmark. That paper reports a maximum of 71.3 seconds to find one sbAXp and 16.3 seconds to find one sbCXp across these datasets. We will rerun it on our hardware rather than quote those times. It is the reference because it defines the task and every competitor must reproduce its outputs.

The strongest simple competitor is per-instance bitmask deduplication. For each instance it builds a fixed-width bit vector of disagreements for every opposite-class row, removes duplicates, and answers checks with vectorized bitwise operations. This is the obvious engineering fix, and it is fast when few instances are explained. It will be implemented on the same GPU with the same batching, so that only amortization and compression differ.

The strongest existing systems competitor is an in-memory analytical column store executing each check as a SQL EXISTS query over the sample with the same discretization. We will give it the same rows and memory, and tune its settings for an equal amount of engineering time. The file reports no result on Lacuna for column stores on sample-based explanation checks. We will also run an uncompressed GPU brute-force scan to isolate the effect of compression from the effect of using a GPU.

Our key ingredient is explanation-aware compression, so three ablations isolate it: the same index stored as plain uncompressed bitmaps, run-length encoding with random row order, and run-length encoding with cardinality order.

Beating these baselines means producing identical explanations while delivering at least 10x higher explanation throughput than the best competitor. This must hold on batches of 10,000 instances, on the datasets with more than a million rows, and at no higher peak memory.

Why not just…?

Why not just load the sample into a database and run the checks as queries? This is the most serious threat, because the core observation is that checks are queries. The distinguishing features of our design are three. The index is shared across instances. Deletion searches reuse intersections across nearly identical queries. The row order is tuned to the explanation workload. A general query engine plans each query independently and exploits none of these. The column-store baseline settles it directly. If it comes within 2x of our system, the honest conclusion is that sample-based explanation should simply be run on a database, and that finding alone would change how these tools are built.

Why not just precompute disagreement bitmasks per instance? This costs $O(mn)$ per instance, the same bound as the original algorithm, and then answers checks quickly. For explaining a handful of predictions it may be the better choice. Its cost grows linearly with the number of instances, while ours pays for indexing once and then runs in time proportional to the number of runs. We will measure the crossover point in number of instances explained. If the crossover sits beyond realistic audit sizes, we will report that the index is not worth its complexity.

Why not just compress with LZ4 or Gzip and decompress on demand? Our checks touch every column millions of times, and repeated decompression is exactly the overhead that compressed-domain execution removes. The tuple-oriented compression paper reports its operations running up to 20,000x faster than pipelines that require Gzip decompression. We include a decompress-then-scan variant for completeness, but we do not expect it to be competitive.

Why not just use uncompressed GPU scans, given GPU memory bandwidth? On the samples in our benchmark this may well fit in GPU memory and perform well. The brute-force GPU baseline and the plain-bitmap ablation measure exactly this. Compression must earn its place through run-proportional cost, not through fitting in memory. If sorted run-length encoding does not beat plain bitmaps, the trade-off claim fails.

Proposed Experiments

The main experiment runs on the 30-dataset model-agnostic benchmark (1,000 to over 1,000,000 rows, 10 to 250 features), plus Adult, Lending, COMPAS, German Credit and Spambase from From Contrastive to Abductive Explanations and Back Again. For each dataset we train the same classifiers used in the original paper. We then explain every test prediction and record throughput in explanations per second, peak memory, index build time and compressed size. Every returned explanation is checked for exact equality against the original algorithm's output.

A second experiment measures full enumeration within a fixed time budget. It counts how many sbAXps and sbCXps are found for each system and records the time taken to reach the complete set of contrastive explanations.

The decisive checks are three. First, compressed-index throughput should scale with the number of runs rather than with $n$. We test this by replicating the rows of a dataset, which leaves runs nearly constant while raising $n$. Second, explanation-aware ordering should beat cardinality ordering on check latency even where it compresses worse. This would show that the best order for storage and the best order for explanation genuinely differ. Third, the system should keep a clear margin over the column-store and bitmask baselines on large batches. If the first check fails, the mechanism is wrong. If the third fails, the contribution reduces to an engineering note, and we will say so.