Dropout-Aware Marker Logic for Zero-Shot Cell Annotation

Biologists already know how to define many cell types in words: a regulatory T cell is a T cell that expresses CD4, lacks CD8, and expresses FOXP3 or IL2RA. Single-cell RNA sequencing measures gene activity one cell at a time, and it should let us check such definitions directly against every cell in an atlas. In practice this fails for two reasons. The measurement often misses transcripts that are actually present, an effect called dropout, so "CD8 not detected" is weak evidence that CD8 is off. And once hundreds of overlapping definitions are combined, computing how likely a cell is to satisfy exactly one of them becomes a hard counting problem. We propose to treat each gene's true on/off state as a hidden variable, estimate it with a noise-aware neural model, and compute the probability of each cell-type definition exactly, by counting over the hidden states. Doing this at the scale of a real ontology is a hard reasoning problem, and we plan to measure where exact computation stops being feasible and which approximations fail on which cell types.

The result would be annotation of cell types that have a written marker definition but no training cells, and every label would come with the marker pattern that justified it. The same setting tests scalable neuro-symbolic reasoning, meaning methods that combine neural networks with explicit logical rules, on something harder than digit puzzles: noisy, high-dimensional data in which the rarest classes are often the most important ones scientifically. That is where approximate reasoning is most likely to break.

Core Claim

We claim three things. First, when a cell-type rule is evaluated over probabilistic hidden marker states rather than over thresholded counts, zero-shot annotation of rule-defined types improves, especially for rules that contain negations. Second, in a real marker rule base built on the Cell Ontology, the variables interact sparsely enough (low treewidth) that most of the rule base can be compiled into a tractable circuit for exact probability computation. Third, the standard approximations used where exact computation fails, top-$k$ proof truncation and learned inference surrogates, lose accuracy mainly on rare cell types. That third claim is a testable prediction, and it cuts against the usual evidence for these approximations, which comes from balanced synthetic tasks.

Where This Sits

Two single-cell methods motivate the work. OnClass embeds the more than 2,300 Cell Ontology terms by running random walks over the ontology graph. It then projects expression profiles into the same space and labels cells, including cells of unseen types, by proximity to the term embeddings. It reports an AUROC of 0.87 with 50% of types held out and an Accuracy@5 of 0.55 on completely unseen types. Because OnClass uses only the graph's shape, it cannot use a definition such as "CD4 and not CD8." UNIFAN constrains an autoencoder's decoder with gene-to-pathway membership and adds a set-cover penalty. This lifts clustering on pbmc28k from an adjusted Rand index (ARI) of 0.38 with Leiden clustering to 0.81, which shows that symbolic biological priors help. Its symbolic part, however, is a single membership matrix plus a soft penalty, and it performs no deduction. Our proposal differs from both because it evaluates explicit logical definitions and returns a probability and a proof for each one. The closest work in spirit, the logic-incorporated gene regulatory network model, shows that the choice between AND and OR logic changes cell-fate behavior qualitatively. It hand-builds that logic into two-gene differential equations and cannot scale. We take its lesson that discrete logic matters, but apply it to annotation, where scale is reachable, rather than to regulatory dynamics.

The method comes from three neuro-symbolic lines. The complexity map of neurosymbolic classification shows that computing the probability that constraints hold becomes polynomial once the constraints are compiled into d-DNNF circuits, a form of Boolean circuit that supports fast exact counting. It shows that cardinality constraints compile efficiently and acyclic structure is tractable. It also identifies constraint classes, such as matchings, that cannot be compiled at polynomial size. That paper tells us which kinds of rule we can expect to compile. Scallop keeps only the $k$ most likely derivations of each fact and uses this to reach 84.22% accuracy on multi-hop visual question answering. It also reports that throughput degrades as knowledge bases grow. A-NeSI replaces exact inference with a neural network trained on synthetic beliefs, plus a pruner that removes impossible states. It scales MNIST addition to 15 digits, where exact methods fail after 4. We reuse these two approaches as fallbacks and as test subjects. The file itself warns that top-$k$ truncation may introduce systematic bias when rare tail states are decisive. Rare cell types are exactly such tail states, so single-cell annotation is a natural place to test that warning.

Research Program

The perception component is a dropout-aware generative model in the style of scVI, a variational autoencoder that models count noise and library size. It is pretrained without labels on all cells so that every gene is covered. For each cell $x$ and marker gene $g$ it outputs $p_g(x)$, the posterior probability that $g$ is truly expressed above a gene-specific level.

The symbolic component is a rule base. Each term $t$ receives a Boolean formula $\varphi_t$ over marker states. The formula is built by conjoining the formula of the term's parent in the is_a hierarchy with the term's own positive and negative markers, including "at least $j$ of set $A$" clauses where the curated definitions call for them. Assembling this rule base from Cell Ontology terms and curated marker lists is a deliverable in its own right. The research file does not document how many terms carry usable marker definitions, and we treat that coverage as a quantity to measure.

The label probability counts over hidden marker states $m \in \{0,1\}^G$. Here $G$ is the number of marker genes, and each $m$ is one assignment of on/off states. We weight each assignment by how likely the perception model thinks it is:

$$P(y=t \mid x) \propto \sum_{m \models \psi_t} \prod_{g=1}^{G} p_g(x)^{m_g}\,\big(1-p_g(x)\big)^{1-m_g}.$$

The sum runs over every assignment $m$ that satisfies $\psi_t = \varphi_t \wedge \neg \bigvee_{s \in \mathrm{ch}(t)} \varphi_s$. In words, $\psi_t$ says the cell meets $t$'s definition but none of the definitions of $t$'s children $\mathrm{ch}(t)$, so $t$ is the most specific type it satisfies. Normalization runs across all terms. This sum is a weighted model count. Because marker genes are shared across branches of the ontology, it does not factor into one term per cell type.

We compile the full theory, including an "exactly one most-specific type" cardinality constraint, into a d-DNNF circuit. We measure the treewidth of the graph that links markers appearing in the same rules, and we record compile time and circuit size as the rule base grows. Where compilation fails, we substitute Scallop-style top-$k$ provenance or an A-NeSI-style surrogate trained on Dirichlet-sampled marker beliefs.

The perception model is then fine-tuned end to end on seen types by maximizing $\log P(y \mid x)$, which is differentiable through the circuit. Unseen types need no cells, only formulas. As a by-product, when trained seen-type cells consistently violate a rule, the violation flags that rule as a candidate error in the curated definitions.

Baselines

The naive reference point is marker module scoring. For each type we score a cell as its average normalized expression of positive markers minus the average of its negative markers, and assign the best-scoring most-specific term. This uses exactly the same rule base with no probability model and no joint reasoning. Any gain over it must come from our machinery rather than from the marker knowledge itself. It needs no tuning, so its only budget is the choice of normalization, which we will match to ours.

The strongest existing method is OnClass. It is the only method in the file built for zero-shot annotation over the Cell Ontology, and its reported numbers are an AUROC of 0.87 with 50% of types unseen and an Accuracy@5 of 0.55 on unseen types. We will rerun it on Tabula Muris Senis under its own unseen-type splits, using the same seen/unseen partitions, the same input genes, and a matched hyperparameter search budget. We report results separately on the subset of unseen terms that have marker rules. Our method cannot label terms without rules, so the headline comparison is restricted to that subset, and we also report the full-ontology result for a hybrid that falls back to OnClass for terms without rules. Beating OnClass means exceeding its rerun Accuracy@5 and AUROC on rule-covered unseen types with non-overlapping bootstrap intervals, and matching it on the full ontology.

As a supervised ceiling for seen types, we train a classifier on scVI embeddings under the same data and tuning budget. It cannot label unseen types, but it shows how much accuracy on seen types the logical loss costs, if any.

Two ablations isolate the proposal's key ingredients. The first keeps the rules and the exact counting, but replaces the hidden probabilities $p_g(x)$ with observed binarized detection, so a gene counts as on if at least one transcript was seen. This isolates the dropout-aware hidden state. The second keeps the probabilities but scores each $\varphi_t$ independently as a product of literal probabilities, dropping the most-specific and exclusivity constraints. This isolates joint reasoning. For both ablations we compare against top-$k$ proofs at $k \in \{1, 5, 20\}$ and against the A-NeSI surrogate.

Why not just…?

Why not just threshold the markers and apply the rules as a lookup? This is the first ablation above. The reason to expect it to fail is that negated literals such as "not CD8" become false positives whenever CD8 drops out. Positive markers fail in the opposite direction. The file's evidence that cell-to-cell variation carries biological signal rather than pure noise, from the logic-incorporated GRN study and the deep-sequencing variance study, argues against discarding uncertainty. If thresholding matches our method on rules that contain negations, the core claim fails and we will say so.

Why not just use OnClass, or add a hierarchy-consistency step to a flat classifier? Enforcing is_a consistency alone is cheap, because the valid label sets in a DAG hierarchy can be enumerated in linear time, and a reviewer is right that no circuit is needed for that. Our contribution rests only on the marker formulas, which neither OnClass nor hierarchy repair can use. The real threat is that OnClass's graph embeddings already capture enough to match rule-based zero-shot accuracy. The restricted comparison on rule-covered unseen types settles this directly.

Why not just prompt a large language model with marker lists, or use a single-cell foundation model? Kedzierska et al. show that scGPT and Geneformer used zero-shot underperform scVI and simple highly-variable-gene baselines. For example, Geneformer reaches a median average silhouette width of 0.49 against 0.54 for scVI on Tabula Sapiens, and these models often group cells by batch. That makes a foundation model a weak zero-shot annotator in its current form. Prompting a language model is a more serious threat for small panels of clusters, because a model given a cluster's marker list can reason about the definition much as our rules do. We therefore include cluster-level prompting on pbmc28k as a baseline. No reported result was found on Lacuna for language-model prompting on these benchmarks, so we will report our own measurements. We expect prompting to lose on per-cell calibration and on hybrid states within a cluster rather than on cluster-level accuracy.

Proposed Experiments

The main benchmark is Tabula Muris Senis under the OnClass unseen-type protocol. Metrics are AUROC, Accuracy@5 on unseen types, and per-type recall stratified by type frequency. We use pbmc28k and PBMC 68k for fine immune subsets with negation-heavy definitions, where UNIFAN's reported ARI of 0.81 serves as a clustering reference once our labels are converted into partitions. Tabula Sapiens, with 483,000 cells, is the scale test for inference time and memory.

Three checks decide the outcome. The first is the thresholding ablation measured on unseen types whose rules contain negations. If the dropout-aware version does not win there, the proposal's premise is wrong. The second is the frequency-stratified comparison of exact counting against top-$k$ and A-NeSI. Our prediction is that recall for the rarest decile of types degrades for the approximations but not for exact counting. If the degradation is instead uniform across frequencies, or absent, the file's tail-bias concern does not hold in this domain, which would itself be a useful finding. The third is the compilation study, which plots compile time, circuit size, and treewidth against the fraction of the ontology included. If treewidth grows so quickly that exact compilation covers only a small corner of the ontology, the work becomes primarily a study of the approximations. The kill criterion is that neither exact nor approximate inference beats module scoring on rule-covered unseen types. In that case the marker knowledge, not the reasoning, is doing all the work.