Can computation time distributions reveal underlying computational mechanisms?

Scaling curves constrain efficiency, not mechanism

The paper starts from a practical problem: many computational systems, from human cognition to neuromorphic or quantum hardware, cannot be characterised by reading off their algorithms or internal representations. Computational complexity theory classifies abstract models as problem size grows toward infinity, but finite physical systems are shaped by their architecture and substrate. The authors therefore ask whether observable computation time can carry information about how computation is organised.

Their first tool is empirical benchmarking: measure computation time across a range of problem sizes and fit how it scales. In the visual search task, input size was the total number of black-and-white pixels, varied from 400 to nearly 320,000 image locations. Mean reaction time increased approximately linearly with input size for the human data and for all three models. That shared trend is the central limitation of the benchmarking step: because model time steps are not intrinsically comparable to one another or to human reaction times in seconds, differences in slope cannot be mapped directly onto differences in mechanism.

The authors also superimposed linear and square-root benchmark curves on the distributions. Aligning these curves required arbitrary scaling factors that differed by system, and the interpretation depended strongly on those choices. Benchmarking therefore constrains broad computational efficiency and scaling behaviour, but it does not uniquely distinguish between the mechanisms tested here.

Three mechanisms differ in how evidence is sampled

The comparison rests on three models that all perform the same search but organise evidence accumulation differently. Two are drift diffusion models. In both, samples update log-likelihood maps for target-present and target-absent hypotheses until the posterior at some location exceeds a decision threshold; reaction time is the number of samples needed to get there. The random drift diffusion model (rDDM) draws each sample location uniformly at random and does not use its posterior map to guide sampling. The guided drift diffusion model (gDDM) instead samples at the location currently most likely to contain the target, so it fully exploits spatiotemporal memory.

The third model is a mechanistic neural network model (MNM) built from a shallow spiking neural network. It repeatedly places a foveated field of view over the image, letting many locations be processed in parallel. Rather than keeping a global posterior, it accumulates evidence locally: an initial placement is random, a confirmation pass repeats at the same location if output neurons fire, and a positive confirmation triggers verification against the true target coordinates. Reaction time counts evaluation and confirmation steps plus a verification cost that scales with image size.

The distinction matters because the drift diffusion models operate on abstract evidence samples rather than the image itself, while the MNM processes visual input directly and is therefore image-computable. All three, however, generate stochastic dynamics, and it is those dynamics that the distributional analysis is designed to read.

The full distribution carries what the mean discards

Classical visual search analysis compresses noisy data into mean reaction time as a function of set size. The authors argue that this compression discards distributional information that contains mechanistic insight, and that aggregating reaction times across participants can distort distribution shape. Their alternative treats the computation time distribution as a signature of the stochastic dynamics generated by a mechanism: how information is sampled, accumulated, and transformed.

To compare shapes across systems with different time units, they divide each reaction time by the number of image locations, producing reaction time per location. Under approximately linear scaling, this normalisation pools observations across input sizes and gives an aggregate estimate of profile shape with more statistical power than any single input size could provide. A participant-specific stretch factor then rescales model time to human time.

Two complementary comparisons were run on these characteristic distributions. A shape-based Kolmogorov–Smirnov analysis found, for each participant and model, the stretch factor minimising the distance between the participant's distribution and the model's, then compared pairwise distances with two-sided paired t-tests. A probabilistic leave-one-out marginal log-likelihood analysis fitted a Gamma distribution to each model's outputs and integrated over uncertainty in the stretch factor, using a prior built from all other participants so that a participant's own data were not double-used. Uncertainty in the summed differences was quantified by bootstrapping participants with 10,000 resamples.

Distributions separate models where benchmarks do not

The headline result is a contrast between the two analyses. Benchmarking found broadly similar scaling behaviour for the models and human observers, with approximately linear mean trends across the range tested. Distributional analysis distinguished between the models. In other words, the information that separated mechanisms was not in how fast mean computation time grew with problem size, but in the shape of the variability around that growth.

This is the paper's central claim about levels of description: computation time distributions provide an empirical level of description linking observable computational behaviour to underlying computational mechanisms. The authors present this as complementing computational complexity theory, extending the empirical study of computation from measuring performance to characterising organisation.

The claim is deliberately bounded. The authors state that although there is a causal link between a system's stochasticity and its distribution, a distinct profile cannot be claimed to uniquely identify the underlying mechanism. Distinct mechanisms might generate similar profiles, finite datasets must stand in for an infinite one, and a system might use multiple mechanisms at once, producing an ambiguous profile. The inference is therefore a comparative and empirical one, not a decoding of internal algorithm from distribution shape alone.

What the framework can and cannot compare

The demonstration used 94 participants recruited through quantum physics groups, the Cognitive Science Hub at the University of Vienna, and the Mental Calculation World Cup organisation: 55 males, 39 females, mean age 27.4 years, range 17 to 61. One participant contributed a large dataset of 1,398 trials used to illustrate distributional properties and was excluded from comparative analyses; the remaining participants contributed on average 171 trials, with a range of 150 to 200. The human comparison therefore rests on a nonprobability sample performing a pixel-based search task, not on a broad population estimate.

The authors position the framework as applicable to finite computational systems across biological, classical, neuromorphic, and quantum implementations, precisely because it does not require access to internal algorithms or architectures. They also sketch extensions: temporal inference for systems whose mechanisms change through learning or adaptation, and comparison of hybrid systems in which multiple mechanisms interact. These are proposed directions rather than results demonstrated in the visual search experiment.

The practical reading is a priority ordering. When the question is whether two systems differ in computational organisation, matching mean scaling curves is weak evidence, because arbitrary scaling choices and non-comparable time units leave the interpretation underdetermined. The distributional comparison, with its explicit stretch factor and its two independent fit criteria, is where the discriminating evidence sits in this study.

The distribution is the discriminating measurement

The paper's most useful takeaway is a comparison, not a verdict about which model is right. Benchmarking answered a question about broad efficiency and returned a near-tie: human observers and all three models showed approximately linear growth of mean reaction time with input size from 400 to nearly 320,000 locations. Distributional analysis answered a different question, about the stochastic dynamics of evidence accumulation, and that is where the rDDM, gDDM, and MNM came apart.

For readers evaluating claims about mechanism from timing data, the relevant threshold is therefore whether the analysis uses the full distribution or only its mean. The authors' own caveats set the boundary: similar profiles can arise from distinct mechanisms, finite datasets must represent an infinite one, and mixed mechanisms can blur a profile. Within those limits, the paper argues that computation time distributions, not scaling slopes alone, are the measurement that carries information about computational organisation.

Sources used in this answer