Complexity

Complexity and the Analyzer Tool

We recently published real benchmark numbers for SpiceGrinder. While running and analyzing our benchmarks, we ran into a small surprise: our own complexity score got two models backwards.

medium-8node.xml and small-5node.xml are two of our internal reference models. medium-8node has more nodes and more depth. small-5node is smaller and shallower. Our complexity score said medium-8node should cost more to run. The real, measured throughput — on every machine we tested — said the opposite. small-5node was consistently slower per observation, despite being the “simpler” model on paper.

So let’s step back and talk about how we define complexity, how we check that definition against reality, and what we did when reality disagreed with us.

Complexity isn’t node count

The obvious, but naive, way to score a model is to count its nodes. It’s tempting because it’s easy, but it’s wrong.

Not every node costs the same. A MultivariateNormal and a Constant are both “one node,” but one of them is sampling from a covariance matrix and the other is returning a fixed value. Any score that treats them identically is measuring graph size, not graph cost. SpiceGrinder’s analyzer assigns each component type a relative cost weight — some of those weights are flat, some scale with the component’s own configuration (a 20-dimensional distribution isn’t the same cost as a 3-dimensional one) — and the score is built out of those weights, not out of a plain node count.

Not every node runs every time. This is the part that surprises people, though it makes perfect sense once you look at what a model actually does. A model isn’t a static shape you can measure with a ruler — it’s a set of instructions for how observations get generated, and some of those instructions are conditional. A Mix node picks between its inputs probabilistically on every call; a branch selected 20% of the time only runs about a fifth as often as one that’s always evaluated. A Redimension node consumes its input at a different rate than it produces output, depending on how the dimensions are configured. If you’re counting “this node exists” instead of “this node runs, on average, this many times per observation,” you’re not modeling the graph — you’re modeling one possible case, usually the worst one.

So the analyzer doesn’t walk the graph once and count. It computes, for every node, an expected number of calls per observation — propagated down from the root, accounting for every branch and every reshaping node along the way — and weights each node’s cost by how often it’s actually expected to fire. A cheap node that always runs can easily outweigh an expensive node that rarely does.

That’s “model shape” and “probabilistic navigation,” in the terms we used when we first sketched this out: the score isn’t a photograph of the tree, it’s an estimate of how the tree actually gets traversed.

Where the weights come from: analyze

The per-component cost weights aren’t guesses. They come from real measurement, via the same throughput-sampling path exposed by SpiceGrinder’s analyze tooling: warm up the JVM, then run a tight loop pulling observations from a model and timing how long that takes. Run that against a model built almost entirely from one component type, and you get a real per-node cost for that type, relative to everything else measured the same way. Do that across a battery of reference models and a handful of different machines, and you get a set of weights that reflect real relative cost rather than an engineer’s intuition about which components “feel” expensive.

We don’t publish the exact weight values or the scoring arithmetic — they get recalibrated as we improve both the components themselves and the measurement process, and a specific number from today is the kind of detail that gets stale.

Regardless of future tunings, the purpose is still the same: rank two models by score, and you should get the same ordering you’d get by actually running them. That’s the whole point of the complexity score — it gives you an estimate on how a model will perform compared to a baseline so you can feel confident you have allocated the proper resources for what you are going to run.

Where our own formula got it wrong

For a long time, the score didn’t just weight components by cost — it also added terms for the graph’s depth: how deep the deepest chain was, how deep the shallowest one was, an average across branches. The reasoning seemed sound: a deeper graph does more sequential work per observation, so it should cost more.

Real data said otherwise. Across the machines we tested, adding those depth terms consistently made the score correlate worse with actual measured throughput than dropping them entirely did. The medium-8node vs. small-5node inversion was the clearest example: medium-8node is deeper, built mostly from components with cheap per-node cost. small-5node is shallower, but built from a couple of components with much higher per-node cost. The old formula rewarded depth regardless of what was sitting at each level, so it scored the deep-but-cheap model as more expensive than the shallow-but-costly one — backwards from what every machine we measured actually did.

We tried refitting the depth terms against real data instead of just dropping them. It nudged the aggregate correlation up slightly, but it didn’t fix the specific inversion, and with only a handful of structurally distinct reference models to fit against, refitting risked tuning the formula to those exact models rather than to anything generalizable. So depth came out of the score. What’s left is simpler than what it replaced, and it’s the version that actually agrees with measured reality — not the version that seemed more sophisticated.

Depth itself isn’t gone from the tool — min depth, max depth, and expected average depth are still computed and reported alongside the score, because they’re genuinely useful structural information that indicate semantic complexity from the standpoint of a person reading the model. They just don’t get folded into the performance-indicating score anymore, because doing that made the number worse at its job.

The part we haven’t finished

We’re not claiming the formula is set in stone. small-5node is still the one model in our reference set that costs more per complexity point than everything else — a smaller anomaly than the depth-term inversion we already fixed, but a real one, present on every machine we’ve tested it on. We don’t have a confirmed explanation yet, so we continue to look at it and what we can add to the formula to make observed data fit better.

We also recently found and fixed three subtle measurement bugs in analyze itself:

• The first sampling loop discarded the value each observation produced. A component with no side effects and a fixed return value doesn’t need to actually run to produce that return value — a modern JIT compiler can prove that and skip the loop’s body entirely, which meant we were sometimes measuring “how fast can this loop do nothing” rather than “how fast is this model.”
• Fixing that — folding each observation’s value into a running accumulator so the result can’t be optimized away — turned out to have its own bias. Accumulating a floating-point value is measurably more expensive than accumulating an integer, which meant every model built from discrete, count-style components was scored as artificially cheap relative to continuous ones.
• Even after that, one component (Constant) still measured as free: something that returns the exact same value on every single call. An accumulator fed the same bit pattern over and over is the same as no accumulator at all. The fix was to make the accumulation depend on which call it was, not just what value came back.

None of these were errors in the underlying models. They were errors in our ability to estimate how well they’d perform. Finding sampling errors and contuing to fit the models to real observed data are two ways in which we continuously improve our process and the resulting complexity score formula.

Why this matters if you’re building models

The complexity score exists so you can compare two models and have a high degree of confidence in how they’ll perform without actually generating from both and stopwatching the result. It’s an estimate, not a guarantee, but an educated estimate calibrated from actually-measured data. When it matters, measure the real thing. The computed complexity score gets you close as a starting point; analyze and a real run are how you confirm it.