Distributional signatures of computation: inferring mechanisms from computation time distributions
Abstract
Computational complexity theory provides a framework for analysing abstract models of computation, whereas computational systems operate as finite physical implementations whose behaviour is shaped by their architecture and physical substrate. In such systems, computational organisation cannot be directly characterised from algorithms or internal representations. Building on the use of reaction time distributions to constrain mechanisms in cognitive science, we introduce an empirical framework for investigating computation in physical systems by inferring computational mechanisms from observable computation time distributions. The framework combines empirical benchmarking, which characterises computational efficiency through the scaling of computation time with problem size, with distributional analysis, which treats computation time distributions as signatures of the stochastic dynamics generated by different computational mechanisms. We demonstrate the framework using a scalable visual search paradigm, comparing human performance with three computational models that employ distinct mechanisms of evidence accumulation. Benchmarking reveals broadly similar scaling behaviour for the models and human observers, whereas distributional analysis distinguishes between these models. We show that computation time distributions provide an empirical level of description linking observable computational behaviour to underlying computational mechanisms. This framework complements computational complexity theory by extending the empirical study of computation from measuring computational performance to characterising computational organisation. It provides an empirical approach for comparing finite computational systems across diverse physical implementations, including biological, classical, neuromorphic, and quantum systems, without requiring access to their internal algorithms or architectures.
Related
- Neural traveling waves in cortex: network mechanisms and potential roles in neural computation
- Neural mechanisms for resilient sensory computation under metabolic stress
- Thermodynamic and Statistical Signatures of Modality Changes in Concentration Distributions Driven by Stochastic Switching Between Two Activity States
- Integrating physiological and proteomics signatures for understanding drought, salinity and alkalinity stress tolerance mechanisms in lentil
- Integration of ATAC- and RNA-sequencing identifies chromatin and transcriptomic signatures in classical and non-classical zebrafish osteoblasts and indicates mechanisms of entpd5a regulation
BibTeX
@misc{valkenhoef2026distributional,
title = {{Distributional signatures of computation: inferring mechanisms from computation time distributions}},
author = {Céline van Valkenhoef and Catherine Schuman and Nikolaus Kriegeskorte and Philip Walther},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.23607},
eprint = {2610.23607},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.23607},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Distributional signatures of computation: inferring mechanisms from computation time distributions
AU - Céline van Valkenhoef
AU - Catherine Schuman
AU - Nikolaus Kriegeskorte
AU - Philip Walther
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.23607
UR - https://arxiv.org/abs/2610.23607
AB - Computational complexity theory provides a framework for analysing abstract models of computation, whereas computational systems operate as finite physical implementations whose behaviour is shaped by their architecture and physical substrate. In such systems, computational organisation cannot be directly characterised from algorithms or internal representations. Building on the use of reaction time distributions to constrain mechanisms in cognitive science, we introduce an empirical framework for investigating computation in physical systems by inferring computational mechanisms from observable computation time distributions. The framework combines empirical benchmarking, which characterises computational efficiency through the scaling of computation time with problem size, with distributional analysis, which treats computation time distributions as signatures of the stochastic dynamics generated by different computational mechanisms. We demonstrate the framework using a scalable visual search paradigm, comparing human performance with three computational models that employ distinct mechanisms of evidence accumulation. Benchmarking reveals broadly similar scaling behaviour for the models and human observers, whereas distributional analysis distinguishes between these models. We show that computation time distributions provide an empirical level of description linking observable computational behaviour to underlying computational mechanisms. This framework complements computational complexity theory by extending the empirical study of computation from measuring computational performance to characterising computational organisation. It provides an empirical approach for comparing finite computational systems across diverse physical implementations, including biological, classical, neuromorphic, and quantum systems, without requiring access to their internal algorithms or architectures.
ER -