P301 A shared algorithmic bound for human and machine performance on a hard inference task

Daniele Tirinnanzi*1, Rudy Skerk1, Jean Barbier1,2, Eugenio Piasini1

1International School for Advanced Studies (SISSA), Trieste, Italy
2International Centre for Theoretical Physics, Trieste, Italy

*Email: dtirinna@sissa.it

Introduction

Recently, a successful approach in neuroscience has been to train deep nets (DNs) on tasks that are behaviorally relevant for humans or animals, with the goal of identifying emerging patterns in the implementation of key computations [1, 2], or to formulate compact hypotheses for physiological and perceptual phenomena [3, 4]. However, less attention has been given to the comparison of the limitations on the space of algorithms that are accessible to human cognition and DNs, as a method to generate (rather than test) hypotheses on shared architectural or learning constraints. Here we compare the performance of humans and DNs on the planted clique problem (PCP), a well-studied abstract task with known theoretical performance bounds [5, 6].
Methods
The PCP consists in detecting a set of K interconnected nodes (a “clique”) in a random graph of N nodes. We represent graphs as adjacency matrices and analyze performance across different N values. Four DNs are trained and tested on a binary classification task at 9 N values: a multilayer perceptron (MLP), a convolutional neural network (CNN) and two Visual Transformers [7], one pretrained (ViTpretrained) and one trained from scratch (ViTscratch). Fifteen human subjects perform a two-alternative forced choice task at 2 N values, selecting which of two presented graphs contains the clique. For each N, we measure accuracy for varying K values and fit a sigmoid to extract the clique detection threshold (K₀), used to compare agent performance.
Results
As shown in Figure 1, the CNN exhibits the lowest K₀ (highest clique detection sensitivity) at all N values except N = 200, 300 and 400. At these N values, the CNN performs poorly, making it impossible to estimate K₀. At all N values, the ViTpretrained and ViTscratch perform similarly, while the MLP consistently shows the lowest sensitivity, except at N = 100. Human performance in the task is comparable to that of DNs, with sensitivity at N = 300 closely matching that of the ViTpretrained and ViTscratch. Performance of all agents, both biological and artificial, falls far from the theoretical bounds of the problem.
Discussion
Our results show that different DNs achieve comparable performance in the PCP. This performance level, far from the problem’s theoretical bounds, is also observed in humans, suggesting a shared algorithmic limit between artificial and biological agents. Large-scale human experiments will help further characterize this threshold across all N values.
With its well-defined bounds, the PCP provides a novel framework for investigating the space of algorithms accessible to humans and DNs in simple visual inference tasks. Such interdisciplinary efforts - combining theoretical, computational, and behavioral perspectives - are essential for deepening our understanding of intelligence in both artificial and biological systems [8, 9].



Figure 1. clique detection thresholds (K₀, log-scaled, y axis) as a function of the number of nodes (N, x axis) for humans (pink triangles) and DNs (MLP: red dots; ViTpretrained: dark green dots; ViTscratch: purple dots; CNN: light green dots). The green and the yellow lines indicate the statistical [5] and computational [6] bounds, respectively.
Acknowledgements
The HPC Collaboration Agreement between SISSA and CINECA granted access to the Leonardo cluster. DT is a PhD student enrolled in the National PhD program in Artificial Intelligence, XXXIX cycle, course on Health and life sciences, organized by Università Campus Bio-Medico di Roma.
References
● https://doi.org/10.1038/nn.4244
● https://doi.org/10.48550/arXiv.1803.07770
● https://doi.org/10.1038/s41593-019-0520-2
● https://doi.org/10.1016/j.cub.2022.12.044
● https://doi.org/10.1017/S0305004100053056
● https://doi.org/10.48550/arXiv.1304.7047
● https://doi.org/10.48550/arXiv.2010.11929
● https://doi.org/10.1017/S0140525X16001837
● https://doi.org/10.1038/s41593-018-0210-5