Temporal-Logic Specifications as Part Supervision

Fine-grained recognition, for example telling 200 bird species apart, depends on small parts such as the beak, crown or wing bar. The best-understood way to make networks attend to those parts is expensive: people draw a box or place a keypoint on every part of every image. Unsupervised alternatives either cluster network features into blobs or learn attention maps. These find parts statistically but never check how the parts relate to one another, so they cannot enforce that "the beak touches the head" or that "every wing patch borders the torso." This proposal replaces per-image part annotations with a handful of per-category specifications. These are short logical statements about how parts sit next to each other and nest inside each other. The specifications are written once for a category and evaluated as a differentiable training loss on every image.

The choice of logic comes from two theoretical literatures that have never met vision. Computation Tree Logic (CTL) is a language for properties of graphs, such as "from here you can eventually reach a state labelled q." Complexity theory has mapped out which pieces of CTL can be checked by shallow parallel computation and which are inherently sequential. Algebraic clone theory classifies constraint problems by their symmetry operations, and it identifies which part-labelling constraints can be decoded without search. Our central claim is that these classifications do more than describe worst-case difficulty. They predict which specifications train stably as losses and which decode tractably at test time. A negation-free fragment of CTL built from "next" and "eventually" operators is the practical choice for part supervision, because it is shallow, monotone and compositional.

Core Claim

Treat an image as a graph. Each image patch from a frozen self-supervised vision transformer (DINOv2) is a node, spatial adjacency gives the edges, and the network's soft part-assignment probabilities are the labels on each node. A part specification is then a CTL formula checked on this graph. Two examples: "every patch likely to be beak has a neighbour likely to be head," which is a next-step property; and "from any wing patch, torso is reachable through wing or torso patches," which is an eventually property.

We make three claims.

First, specifications in positive CTL restricted to the operators $\{EX, EF\}$ have a soft evaluation that is a shallow computation. EX means "some neighbour satisfies"; EF means "some reachable node satisfies"; positive means negation appears only on atomic labels. The soft evaluation of EF can be computed by repeated matrix squaring, so it takes logarithmically many steps. It is also monotone in the part probabilities, which means raising the probability of a part can never make the formula less true.

Second, adding negation between operators, or using the fixpoint operators EG and EU in nested form, produces losses that are deeper and non-monotone. EG means "along some path, always"; EU means "along some path, p until q". We predict these losses train worse and collapse part maps more often.

Third, if the discrete decoding constraints are tree-preserving over a part taxonomy, a cheap local consistency pass decodes a globally consistent part labelling without backtracking. Tree-preserving here means each constraint maps any subtree of the taxonomy to a subtree.

We expect the combination to reduce dependence on part annotations and to push past the part-count saturation that current attention methods report.

Where the Pieces Come From

The complexity lens comes from Model Checking CTL is Almost Always Inherently Sequential. That paper shows full CTL model checking is P-complete, meaning inherently sequential, for any non-empty operator set. It also shows positive CTL drops to LOGCFL-complete, a class solvable by log-depth parallel circuits, exactly when the operators lie within $\{EX, EF\}$ or $\{AX, AG\}$. The same paper proves that monotone, positive and atom-negated fragments are equivalent under constant-depth reductions. We rely on this so that negated atoms such as "not background" cost nothing. The model checking fingerprints of CTL operators sharpens this picture by pairing single operators with Boolean connective sets from Post's lattice. It finds EU the strongest operator, EX and EF weaker, and some conjunction-only or disjunction-only combinations NL-complete. The companion LTL classification, The tractability of model checking for LTL, plays the same role for linear time. All three papers are purely theoretical. None evaluates anything on data, and none asks whether complexity class correlates with how well a relaxed version trains. That question is ours.

We must be honest about one constraint from the same literature. When the formula is fixed, CTL model checking is NL-complete for every operator (Model Checking CTL is Almost Always Inherently Sequential). A single small specification is therefore never inherently sequential, whichever operators it uses. The separation we exploit is between specifications whose nesting grows with the depth of the part hierarchy and those whose nesting does not. It is also between monotone and non-monotone soft semantics. We treat the complexity classification as a hypothesis generator for trainability, not as a proof about it.

The decoding side comes from On Tree-Preserving Constraints. That paper links majority symmetries, meaning operations $M$ with $M(x,x,y)=M(x,y,x)=M(y,x,x)=x$, to tree-preserving constraint networks. It proves that partial path-consistency, a local constraint-propagation pass, solves such networks without backtracking. It then models 29 of the 39 trihedral junction types in classical line-drawing labelling this way. We take its algorithm and move it from hand-built junction catalogues to learned patch graphs. The domain becomes a part taxonomy tree, for instance bird → head → {beak, crown, eye}. The adjacency constraint becomes "neighbouring patches carry equal labels, parent/child labels, or background." We must verify that this relation is tree-preserving rather than assume it. The image of a subtree under "equal or parent/child" is that subtree plus its parent, which suggests it is.

On the vision side, Learning Multi-attention Convolutional Neural Network for Fine-Grained Image Recognition (MA-CNN) clusters feature channels into part attention maps. It reports that performance saturates at 4–6 parts and that the model does not model spatial relations between parts. That paper both motivates this proposal and supplies a baseline. PartCo clusters DINOv2 patch tokens into first- and second-order part correspondences and adds a correspondence loss at no inference cost. It is the closest existing method, and it supplies our backbone recipe. Its parts carry no relational constraints; ours add them. Neural Activation Constellations uses a rigid star-shaped geometry around the object centre. Our reachability specifications are topological rather than metric, so articulation should hurt them less.

Research Program

The system has four components.

A specification compiler turns a positive CTL formula over part names into a soft evaluator on the patch graph. Let $A$ be the $n \times n$ patch adjacency matrix, with self-loops, and let $p_q \in [0,1]^n$ be the probability that each patch belongs to part $q$. Soft EX is $(EX\,q)_i = \max_j A_{ij}\, (p_q)_j$. Soft reachability restricted to patches satisfying a guard $g$ uses the max-product closure

$$R_g = \big(\operatorname{diag}(p_g)\, A\big)^{\otimes 2^{\lceil \log_2 n \rceil}}, \qquad (EF_g\, q)_i = \max_j (R_g)_{ij}\,(p_q)_j,$$

where $\otimes$ denotes max-product matrix powering by repeated squaring. With the 256 patches of a 16×16 DINOv2 grid this takes eight squarings. The depth is logarithmic because repeated squaring of reachability is the standard log-depth reachability circuit behind the NL and LOGCFL upper bounds. Conjunction and disjunction are soft min/max or product/probabilistic-sum. The loss is one minus the soft truth value, averaged over the nodes the formula quantifies over.

A part head sits on frozen DINOv2 and predicts $K$ part maps. It is trained with a classification loss plus the specification loss. It uses no part boxes or keypoints.

A specification library holds five to ten formulas per dataset, written once per dataset rather than per image. For birds these cover taxonomy nesting, adjacency such as beak–head and wing–torso, and connectedness of each part region. Writing them should take minutes.

A decoder runs partial path-consistency over the tree-preserving adjacency network. It turns soft maps into a discrete labelling that is guaranteed to satisfy the decoding constraints. It is compared against greedy argmax and a generic backtracking solver.

The analysis half of the program makes the trainability prediction testable. We build a graded family of specifications with identical intended content, expressed in progressively stronger fragments. The first uses positive {EX, EF}. The second adds AG/AX duals mixed with EF, which leaves the LOGCFL fragments of Thomas et al. The third adds EG/EU. The fourth allows negation between temporal operators. For each, we measure gradient norm across training, the rate of part-map collapse (a part's total mass falling below 1% of patches), and final accuracy.

Baselines

The naive reference point is frozen DINOv2 with a linear or small MLP classifier on the class token, trained on the same splits. It shows whether any part machinery is worth having.

The first unsupervised-part baseline is PartCo-style clustering (PartCo): PCA foreground separation and k-means parts on the same frozen DINOv2, feeding the same classifier head. It is the strongest competitor because it uses the same backbone and the same annotation budget, zero part labels, and differs from us only in having no relational constraints.

The second is MA-CNN (Learning Multi-attention Convolutional Neural Network). It reports 86.5% accuracy on CUB-200-2011, 92.8% on Stanford Cars and 89.9% on FGVC-Aircraft. Those numbers come from an older convolutional backbone. We will cite them as published reference points and also re-implement its channel-grouping loss on our DINOv2 features, so the comparison isolates the part objective rather than the backbone. Bilinear pooling (Bilinear CNN Models, 84.1% on CUB, 91.3% on Stanford Cars) is included as a holistic, relation-free reference.

In the category-discovery setting, the strongest published result is PartCo combined with SelEx at 85.5% average accuracy on the Semantic Shift Benchmark, reported in PartCo. We add our specification loss on top of that pipeline. For fine-grained few-shot matching we found no directly comparable accuracy on CUB or Stanford Cars on Lacuna for Fine-grained Few-Shot Classification with Part Matching, so we do not claim to beat it there.

Every method gets the same frozen backbone, the same image resolution, the same number of part maps $K$, and an equal hyperparameter search budget of 20 configurations each on a held-out validation split. Results are averaged over three seeds.

Two ablations isolate the key ingredient. In the first, the same relational content is written as hand-coded differentiable penalties, such as a beak–head adjacency loss, instead of compiled formulas. In the second, the same content is expressed in the non-monotone, full-CTL form.

What counts as beating the baselines differs by setting. On CUB we must improve both accuracy and part localization over the PartCo-style baseline by more than seed variance. On the Semantic Shift Benchmark we must exceed 85.5% average accuracy.

Why not just…?

Why not just annotate a few keypoints instead of writing specifications? This is the honest competitor on the annotation-dependency question. We will measure it directly. CUB's keypoint annotations will be used to supervise part heads at 1%, 5%, 10% and 100% of training images, giving an annotation-budget curve. The specification-only model is placed on that curve, which expresses the value of the specifications in "equivalent annotated images." If five labelled images per class match the specifications, the specifications are not worth it. The proposal would then shrink to a combination method: specifications plus few keypoints.

Why not just hand-write relational losses, which is what MA-CNN does for compactness and diversity? This is a real threat. A hand-coded adjacency penalty may carry the same information as our compiled formula. The hand-coded-loss ablation settles it. If it matches our accuracy and localization, the contribution reduces to a compiler that writes such losses automatically, plus the decoding guarantee. Our reason for expecting a difference is composition. Nested properties such as "wing reachable from torso through wing patches" are awkward to hand-code correctly. They come for free, and stay monotone, in the positive fragment.

Why not just segment parts with a foundation segmenter and check rules afterwards? Post-hoc checking can reject bad parses but cannot improve the part detector. Fine-grained Few-Shot Classification with Part Matching shows such pipelines inherit the segmenter's failures. We will run Grounded-SAM part proposals through the same specification checker and report its violation rate and accuracy, but we do not expect it to change the conclusion.

Why not just allow full CTL and let optimization cope? That is exactly the graded-fragment experiment. If full-CTL specifications train as well as the positive {EX, EF} ones, our complexity-guided restriction is unnecessary. We will report that as a negative result about the link between complexity class and trainability.

Proposed Experiments

The main benchmarks are CUB-200-2011, Stanford Cars and FGVC-Aircraft for classification, and the Semantic Shift Benchmark for category discovery. CUB's keypoints are used only for evaluation, via the fraction of annotated keypoints that fall inside the predicted map for the matching part, and for the annotation-budget curve. Metrics are top-1 accuracy, part-hit rate, specification violation rate after decoding, and decoding time.

Four checks would settle the proposal.

The first tests saturation. MA-CNN saturates at 4–6 parts. We sweep $K$ from 4 to 16 with a hierarchical taxonomy specification. If accuracy keeps rising or holds flat beyond 6 while the PartCo-style baseline degrades, the specifications are curbing over-segmentation.

The second tests trainability. Across the graded fragment family we expect collapse rate and accuracy to worsen once we leave the positive {EX, EF} fragment. A flat response falsifies the complexity-as-trainability hypothesis.

The third tests decoding. After each tree-preserving adjacency relation has been formally verified, partial path-consistency should reach zero constraint violations without backtracking, faster than a generic solver. Any violation or backtrack would show the relation is not tree-preserving and would need its own analysis.

The fourth tests articulation. On a CUB subset stratified by pose, which we would curate ourselves, reachability specifications should degrade less than the constellation-style rigid geometry of Neural Activation Constellations.