When a network predicts a depth map or a segmentation, the errors it makes are not independent from pixel to pixel. If it misjudges the distance to a car, it misjudges the whole car. Capturing this requires a joint distribution over all pixels: a mean image plus a covariance matrix that says how each pixel's error moves with every other pixel's. That matrix has $N^2$ entries for $N$ pixels and costs $N^3$ to invert, so practical systems cut corners. Some keep only a low-rank part, a few hundred global "modes" of variation. Others keep a sparse precision matrix, the inverse covariance, whose zeros mean "these two pixels are independent once you know their neighbours", and they restrict its nonzeros to a 5×5 window. Under the window version, a distant pixel can influence another only through a long chain of neighbours. This is the same locality problem that convolutional networks have, now moved from the features into the uncertainty model.
We propose to build the sparsity pattern of the precision matrix the way criss-cross attention builds its receptive field. Each pixel's Cholesky factor (the triangular "square root" of the precision matrix) has nonzeros along its own row and column rather than in a small square. This structure has three useful properties. The log-determinant is still the sum of the logs of the diagonal entries. Sampling becomes a sweep across anti-diagonals with only $H+W-1$ sequential steps. And, by the same two-hop argument that gives recurrent criss-cross attention a global view, the resulting precision matrix couples almost every pair of pixels while the factor holds only $O(N\sqrt N)$ entries. The test that matters is whether conditioning on a few LiDAR points now corrects depth far from those points, which a 5×5 precision model cannot do in one step.
Core Claim
Let $y\in\mathbb{R}^N$ be the output image (depth or logits) on an $H\times W$ grid, with predicted mean $\mu$ and precision $\Lambda = LL^\top$. Here $L$ is lower-triangular in raster order. Its entry $L_{ij}$ may be nonzero only when pixel $j$ is pixel $i$ itself or an earlier pixel in the same row or the same column. Its diagonal is kept positive with a softplus. The negative log-likelihood is
$$ -\log p(y) = \tfrac{1}{2}\lVert L^\top (y-\mu)\rVert^2 - \sum_i \log L_{ii} + \tfrac{N}{2}\log 2\pi , $$
so evaluating it costs one sparse matrix-vector product and no factorization. Read as a directed model, each pixel's residual is a linear function of the earlier residuals on its cross, plus fresh noise.
The entries are not stored. They are generated on the fly as scaled dot products between a query at pixel $i$ and a key at pixel $j$, both predicted by the network. The covariance head is therefore literally a criss-cross attention layer, but its outputs are Cholesky coefficients rather than feature-mixing weights.
Sampling solves $L^\top x=\varepsilon$. Each pixel depends only on pixels that lie on earlier anti-diagonals in reverse order, so all pixels on one anti-diagonal can be solved in parallel. The total work is $O(N(H+W)d)$, where $d$ is the query width, and the depth is $O(H+W)$. Conditioning on sparse observations by Matheron's rule, the method Learning Structured Gaussians to Approximate Deep Ensembles uses for LiDAR, carries over unchanged because it needs only samples and solves.
The claim is twofold. First, at matched parameter and compute budgets, criss-cross support beats both square-window precision and low-rank covariance on tasks whose uncertainty is long-range. Second, the gain comes from the sparsity geometry itself, not from giving the network a more global backbone.
Relation to Prior Work
Two papers supply the method we modify. Structured Uncertainty Prediction Networks predicts a sparse Cholesky factor of the precision with a 5×5 support to fix the blurriness caused by diagonal likelihoods in autoencoders. Learning Structured Gaussians to Approximate Deep Ensembles uses the same 5×5 structure on KITTI depth to distill ensembles and to condition on sparse LiDAR. We keep their precision-domain formulation and their conditioning procedure, and replace only the support pattern. Their samplers rely on truncated Jacobi iterations, and that is exactly where long-range correlation has to be accumulated step by step.
Two papers frame the low-rank alternative and its limits. Stochastic Segmentation Networks puts a low-rank-plus-diagonal Gaussian on segmentation logits. Single Image Depth Prediction Made Better: A Multivariate Gaussian Take uses a rank-128 depth covariance on top of a Swin encoder. Flow Stochastic Segmentation Networks motivates our work: it shows that the effective rank of such low-rank models grows sublinearly with the nominal rank, and that a rank-2 model fails on MarkovShapes. Our structure is not low-rank at all. Its rank is full by construction, and its expressiveness is set by which pixel pairs may interact directly.
Flow-SSN reaches high rank through normalizing flows instead. That gives up an explicit precision matrix and closed-form conditioning, both of which we keep.
CCNet supplies the routing idea: row-plus-column attention, applied twice, reaches every pixel at $O(N\sqrt N)$ cost. Here that pattern defines the conditional-independence graph of a probability model rather than a feature aggregator. EccoMamba constrains the design. It documents that imposing a scan order on a 2D lattice introduces directional bias, and our raster ordering is such a scan, so we measure that bias explicitly (below). Multi-Dimensional Recurrent Neural Networks is the closest precedent for the anti-diagonal sweep. It applies the sweep to hidden states, not to Gaussian residuals.
Research Program
We will first implement the factor-generating head and a fused kernel. The kernel computes $L^\top r$ and the anti-diagonal triangular solve without materializing $L$, and we will report memory against the 5×5 sparse factor and the rank-128 factor at KITTI and CelebA resolutions. Because the entries are dot products of width-$d$ vectors, a factor that would otherwise need hundreds of millions of stored values at full KITTI resolution needs only $O(Nd)$ memory.
Second, we will characterize what the structure can represent. We will extend MarkovShapes with synthetic Gaussian fields whose correlation length and rank we control, and measure KL divergence to the true field as correlation length grows, for each support pattern at matched entry count.
Third, we will integrate the head into the SUPN depth pipeline on KITTI, the SUPN VAE on CelebA, and the SSN logit model on LIDC-IDRI. In each case we change only the covariance head.
Two variants address the ordering issue. In the first, training randomly flips the image so the network cannot exploit a fixed sweep direction. In the second, the precision is a sum of two factors with opposite orderings, and the log-determinant is estimated stochastically. We will adopt the second only if the first shows measurable asymmetry.
Baselines
The naive reference is a per-pixel diagonal Gaussian head on the same backbone, trained with the same likelihood. Any structured model must beat it on negative log-likelihood (NLL) and on conditioning gain. Otherwise the whole exercise is moot.
The strongest existing competitor for depth is the 5×5 sparse-precision model of Learning Structured Gaussians to Approximate Deep Ensembles. It is the only method in the file with explicit precision and closed-form LiDAR conditioning, and it reports RMSE of about 4.07 against about 3.85 for an 8-model ensemble on KITTI. With 100 random ground-truth pixels it reports AbsRel falling from 0.104 to 0.064. We will reproduce it with its backbone and training schedule and give our head the same parameter count and tuning budget. Beating it means two things: a lower conditioned AbsRel than the reproduced 0.064-level figure, and, more importantly, a larger error reduction in pixels far from any conditioning point, at equal or better unconditioned RMSE.
For image likelihood, the same SUPN structure reports a CelebA NLL of −8386 against −6079 for a diagonal VAE Structured Uncertainty Prediction Networks. We need a better NLL at matched size.
The low-rank competitor is the rank-128 head of Single Image Depth Prediction Made Better. The file gives it only as percentage gains (SILog improved by 4.43% on KITTI), with no reported absolute number on Lacuna. We will therefore retrain it on the same backbone and set its rank so its parameters match our head.
For segmentation, the competitors are SSN and Flow-SSN on LIDC-IDRI and REFUGE-MultiRater, measured by generalized energy distance (GED) and Hungarian-matched IoU. The file reports no absolute GED value on Lacuna for either, so we will retrain both under a shared protocol. Beating Flow-SSN on GED at lower sampling cost would be a strong result. Matching it while adding exact conditioning would be the realistic one.
The ablations isolate the key ingredient. The first keeps the 5×5 precision but swaps the CNN backbone for a criss-cross or Swin backbone. The second uses dilated-square and random sparsity patterns with exactly as many nonzeros per pixel as the criss-cross pattern. The third is one-sided support, row only, which removes the two-hop global coverage. The criss-cross pattern must beat all three for the geometry claim to stand.
Why not just…?
Why not just give the 5×5 precision model a global backbone? This is the most serious threat, because in Single Image Depth Prediction Made Better the global context lives entirely in the encoder. A better backbone improves the mean and can shape local coefficients using distant evidence. It cannot, however, make two distant pixels conditionally dependent. That zero pattern is fixed by the support, however the coefficients are computed. The global-backbone ablation, scored by conditioning gain as a function of distance to the nearest LiDAR point, settles this directly. If the binned curves coincide, our claim is wrong.
Why not just add a low-rank term to the local precision? A covariance that is low-rank plus the inverse of a local precision captures smooth global modes and local texture together, and might suffice for depth, where long-range structure is often planar. The effective-rank result in Flow Stochastic Segmentation Networks suggests the low-rank part saturates when long-range structure is itself high-rank, such as many independent objects. We will include this hybrid at matched parameters. The synthetic sweep over correlation rank should show where each model wins. If the hybrid matches us on KITTI, we will report that the advantage is confined to high-rank regimes.
Why not just run more Jacobi iterations or stack multiscale local precisions? More iterations propagate influence further but cost a full pass each and remain truncated. A coarse-to-fine pyramid of 5×5 precisions is a credible alternative that we include, scored at matched wall-clock time.
Why not just use flows? Flow-SSN is more flexible in shape and can be non-Gaussian. However, it offers no explicit precision for single-pass Matheron conditioning, and its continuous-time version needs an ODE solver. Where conditioning is not needed, it may well win on GED, and we will say so.
Proposed Experiments
The decisive check is on KITTI. We condition on 100 random LiDAR points and plot the reduction in AbsRel against distance to the nearest conditioning point, for all heads. Our model should keep a substantial reduction at distances beyond 20 pixels, where the 5×5 model's reduction should fall toward zero.
The second check is the synthetic correlation-length sweep, where we expect the square-window KL to grow with correlation length while ours stays flat. Third, CelebA NLL and LIDC-IDRI GED at matched size test whether the gain holds outside depth.
Finally, we measure directional bias by comparing NLL on horizontally and vertically flipped test images. A gap larger than the run-to-run noise across seeds would trigger the two-ordering variant. We will also report memory and latency against the 5×5 and rank-128 heads, so the sub-quadratic claim is checked rather than assumed.
References
- Learning Structured Gaussians to Approximate Deep Ensembles
- Structured Uncertainty Prediction Networks
- Stochastic Segmentation Networks: Modelling Spatially Correlated Aleatoric Uncertainty
- Single Image Depth Prediction Made Better: A Multivariate Gaussian Take
- Flow Stochastic Segmentation Networks
- CCNet: Criss-Cross Attention for Semantic Segmentation
- EccoMamba: Enhanced Cross-hierarchical Continuity Orthogonal Mamba for Medical Image Segmentation
- Multi-dimensional Recurrent Neural Networks