Bounds on the computational complexity of neurons due to dendritic morphology

Thank you for your thoughtful and detailed review. We appreciate your comments and suggestions, especially regarding clarity around terminology and the relevance to machine learning architectures. Below, we respond to your main concerns and describe the changes we’ve made in the revised manuscript.

Entropy definition

You are absolutely right that the term “entropy” carries specific meanings in the context of Boolean function analysis, such as Fourier entropy. In our paper, we use entropy as defined by Mingard (2019), which is calculated over the output column. This definition maps to Shannon Entropy monotonically but non-linearly (ranges from 0 to 0.5 instead of 0 to 1). For a Boolean function with binary outputs, this corresponds to the uncertainty over whether the function returns 0 or 1 across the set of input configurations. We have now clarified this definition explicitly in the main text and noted that it differs from Fourier entropy as discussed in the reference by O'Donnell.

We also added a brief comment in the Discussion to highlight that future extensions could explore spectral characteristics of function realizability. This may be particularly useful when comparing with architectures that are biased toward or against specific frequency components in their learned representations.

Training procedure

Thank you for flagging this. We apologize for the lack of detail. We will follow your suggestion and add clear statements about training methods, which we detail below. It is important to note that we used two distinct approaches, gradient descent, as well as a non-gradient based method (DIRECT) in order to test for limitations of the learning algorithms.

For all training instances, which entailed learning the function mapping $f : \\{0,1\\}^n \rightarrow \\{0,1\\}$ in input dimension $n$, the input consisted of the full enumeration of $2^n$ input rows, with the target being the Y-column of the boolean function mapping. While training using the gradient-descent based approach, we used Binary Cross-Entropy as the loss function between the predicted and the target outputs during the training. We used an Adam optimizer with a fixed learning rate, with learning rates and epochs tuned according to the input dimension to ensure convergence (ranging from 6e4 epochs with lr = 5e-3 for $n_{dim} = 3$ to 6e6 epochs, lr = 1e-4 for $n_{dim} =8$. We also ran instances of training with an Adam optimizer with a learning rate scheduler, but that did not impact realizability trends shown in the paper.

For the DIviding RECTangles (DIRECT) optimization, we used Scipy's implementation which was based on Gablonsky et al 2001. Reasonable bounds on the learnable parameters were first set as input parameters for the optimization algorithm. The parameter space was constrained with weights bounded between -20 and 20, branch gains ($h$) between 0 and 10, thresholds ($\theta$) between -1 and 10, and output bias ($\Delta$) between -1 and 10. Both basal and apical cell architectures were trained using mean squared error loss between continuous sigmoid outputs and binary target labels. The DIRECT algorithm performed global optimization without gradients, exploring the 7*d +7 + 7 + 1 - dimensional parameter space (d input dimensions × 7 branches + 7 gains + 7 thresholds + 1 bias) to minimize classification error with a maximum of 2,000,000 function evaluations and zero volume tolerance for convergence. Training performance was evaluated using Hamming distance between binarized predictions (threshold 0.5) and ground truth binary labels.

For a broad overview on the evaluation of realizability of a boolean function by a given architecture, we point the reviewer to Supplemental Figure 1.

By reporting both training success rate and best-case realizability, we are able to distinguish between functions that are simply hard to train and those that are likely not realizable under the given morphology. We will revise Section 2 to make this workflow clearer.

On the simplicity of the analysis and relevance to real-world models

We agree that the framework is abstract by design. Our goal was to create a clean setting in which we could isolate the influence of dendritic topology on functional realizability and adaptability. That said, your question about how these insights transfer to modern architectures like transformers is well taken. It also aligns with questions raised by other reviewers, and we've started investigating this directly.

As a preliminary step, we adapted our “broad” and “hierarchical” architectural motifs to the layout of attention heads within a transformer. The total number of heads was held constant, but arranged in different patterns. Hierarchical configurations were deep and narrow, while broad ones were shallow and wide. We evaluated these models on four sequence-learning tasks: copying (short-term memory), reversal (long-range dependency), sorting (comparison), and pattern completion (reasoning). The training details are as follows: We compiled results from training with 8 tree attention architectures (4 hierarchical, 4 broad) across 4 sequence prediction tasks (copying, reversal, sorting, pattern completion). Models were trained with model dimension $d_{model}=128$, 3 layers, sequence length=12, vocabulary size=20, for 200 epochs using an Adam optimizer with learning rate=0.0005. Convergence was measured as the average number of epochs to stable validation loss. Transfer learning was evaluated via fine-tuning pre-trained models on new tasks compared to training from scratch, with negative values indicating performance degradation relative to baseline.

The exploratory analysis is summarized in the tables below.

Table: Tree Attention Architecture Performance Comparison

Results from 4 sequence prediction tasks. Convergence and transfer metrics averaged by architecture type.

Architecture Type Summary

Some early trends that emerge:

• Broad architectures performed better overall across most tasks. This is consistent with the idea that parallel architectures are better suited for handling high-sensitivity or high-throughput inputs.
• Hierarchical models, while performing worse on final accuracy, converged faster during training. They also performed significantly better during transfer learning, particularly when fine-tuned across tasks.

These findings parallel what we observe in our main paper. Shallow models perform well on fixed tasks but generalize less effectively. Deeper models, although less expressive in some regimes, are more flexible in how they adapt and reuse internal structure. We will include a summary of these early experiments in the Discussion. Although still exploratory, we believe this direction is promising and provides a bridge between our abstract neuron model and architectural questions in deep learning.

On hybrid models and broader implications

Your suggestion to consider implications for architectural motifs and pruning strategies is very much appreciated. We have added a few lines to the Discussion exploring how morphological constraints might inspire hybrid or modular designs. For example, one could imagine incorporating a mix of broad and hierarchical processing units in a transformer to balance robustness with adaptability. Similarly, knowing that certain architectures favor specific function classes might help guide structured pruning approaches or inform initialization strategies.

Limitations

We agree that the limitations of the current work should be stated more directly. We've added a brief "Limitations" section in the main paper that highlights some of the key boundaries of the current study, such as the use of synthetic functions, the limited input dimensionality, and the need for further validation in real-world tasks. Thank you again for your constructive feedback. We've clarified terminology, improved the description of our methods, and added a broader discussion of how these findings may transfer to machine learning models.

Thank you for your detailed response. I will adjust the score in light of this.

Thank you for your thoughtful and constructive feedback. We appreciate your recognition of the core ideas, especially the link between dendritic morphology and architectural trade-offs, and we agree that there are places where the exposition could be clearer. Below, we address each of your major concerns in turn, and we plan to revise the manuscript accordingly.

Modeling details

Thank you for pointing out that our modeling details are insufficiently fleshed out. We apologize for the lack of detail. We will follow your suggestion and add clear statements about training methods, which we detail below. It is important to note that we used two distinct approaches, gradient descent, as well as a non-gradient based method (DIRECT) in order to test for limitations of the learning algorithms.

For all training instances, which entailed learning the function mapping $f : \\{0,1\\}^n \rightarrow \\{0,1\\}$ in input dimension $n$, the input consisted of the full enumeration of $2^n$ input rows, with the target being the Y-column of the boolean function mapping. While training using the gradient-descent based approach, we used Binary Cross-Entropy as the loss function between the predicted and the target outputs during the training. We used an Adam optimizer with a fixed learning rate, with learning rates and epochs tuned according to the input dimension to ensure convergence (ranging from 6e4 epochs with lr = 5e-3 for $n_{dim} = 3$ to 6e6 epochs, lr = 1e-4 for $n_{dim} =8$. We also ran instances of training with an Adam optimizer with a learning rate scheduler, but that did not impact realizability trends shown in the paper.

For the DIviding RECTangles (DIRECT) optimization, we used Scipy's implementation which was based on Gablonsky et al 2001. Reasonable bounds on the learnable parameters were first set as input parameters for the optimization algorithm. The parameter space was constrained with weights bounded between -20 and 20, branch gains ($h$) between 0 and 10, thresholds ($\theta$) between -1 and 10, and output bias ($\Delta$) between -1 and 10. Both basal and apical cell architectures were trained using mean squared error loss between continuous sigmoid outputs and binary target labels. The DIRECT algorithm performed global optimization without gradients, exploring the 7*d +7 + 7 + 1 - dimensional parameter space (d input dimensions × 7 branches + 7 gains + 7 thresholds + 1 bias) to minimize classification error with a maximum of 2,000,000 function evaluations and zero volume tolerance for convergence. Training performance was evaluated using Hamming distance between binarized predictions (threshold 0.5) and ground truth binary labels.

For a broad overview on the evaluation of realizability of a boolean function by a given architecture, we point the reviewer to Supplemental Figure 1.

Model structure and fair comparisons

We agree that the distinctions between the linear, apical, and basal models could be better described. In the revised manuscript, we plan to clarify that the “linear” model is not simply a degenerate case of the basal architecture. All models - including the linear baseline - use the same total number of trainable parameters, and each receives the same number of input features. What differs is how those parameters are arranged structurally, and whether intermediate nonlinearities (e.g., dendritic compartments) are present. We plan to include a table/schematic to make this comparison explicit.

Boolean function diversity and usage

Thank you for pointing out that the description of the different Boolean function classes was not sufficiently clear. We’ve now clarified the definition of each class as well as their rationale in the revised Methods section. Briefly:

• Random Boolean functions: We devise a truth table that picks the output from $\{0,1\}$ with equal probability for each row of the truth table. Since this procedure equally weights each function, these functions will typically saturate known theoretical bounds on circuit complexity. Namely, they typically require an exponential number of gates. From this perspective, they can be considered the ``hard" functions. These functions tend to have high entropy and high sensitivity, making them difficult to implement for any fixed architecture. We have included a plot in the supplement that visualizes the sensitivity of random boolean functions, where we show that the sensitivity values are close to the theoretical maximum sensitivity of boolean functions.

• Fixed Entropy functions: Entropy of a boolean function is defined in the paper as the fraction min(number of input rows that map to 1, number of input rows that map to 0)/total number of input rows in the truth table [Mingard et al., 2019]. These functions are generated randomly by mapping the complete set of input columns to the output column with the output column generated using random sampling from the possibilities [0,1] with probability (p, 1-p), where p is the desired entropy. This family of functions provides for a parametric way to vary function complexity. The lowest entropy function is the constant function, whereas the highest is the Random Boolean functions.

• Fixed Sensitivity functions: The sensitivity of a boolean function is calculated according to definition 2.1 in the paper. We generate this class of functions using rejection sampling to select for functions with sensitivity in a given range near the required sensitivity. This family of functions provides for a parametric way to vary the degree to which the function output is sensitive to change in the input.

• Sensitivity and entropy are related, which allows us to sample high-sensitivity functions by sampling in the subspace of high entropy functions. We show this in Supplemental Figure 6

• In each experiment, we sample a large number of functions from each class at a given input dimensionality (e.g., 100-500 per class), and all architectures are trained and tested on the same sampled sets to ensure fairness.

• We have now included summary statistics and visualizations of sensitivity and entropy distributions for each function class.

Theoretical analysis

We agree that a complete theoretical account of this phase transition would strengthen the paper and we have been working towards that goal. We can offer a proof that there exists a dimension above which typical functions will be impossible to learn. Briefly, Shawe-Taylor, et al (1992) showed that the class $NN_k$ is contained in $AC_k$. $NN_k$ is the class of polynomial size neural networks of finite depth (with fixed bit precision in the weights). $AC_k$ is the familiar ``Alternating Circuit" class of Boolean functions of finite depth and polynomial number of gates. Given known bounds on the complexity of generic Boolean functions (namely, they require an exponential number of gates), this implies that there exists some dimension beyond which most functions will not be implementable by a given architecture of neural network. Our empirical results quantify this for specific architectures. This phase transition appears similar to that observed for 3SAT as a function of the ratio of literals to clauses. Intuitively, adding constraints that outnumber available configuration variables leads to unsolvability. We will add this argument to the revised manuscript.

Scalability to high-dimensional inputs

This is an important question. While our current results focus on input dimensions up to 8, the main limitation isn't in the models but in the function space, specifically, the exponential growth in the number of Boolean functions makes sampling and evaluation difficult beyond that point. That said, we're actively extending the framework to larger inputs using structured function classes with lower entropy, such as compositional rules or localized feature detectors, which are more representative of real neural coding regimes. We've added a paragraph outlining this extension and our ongoing work in this direction.

Clarifying retraining results and labeling

Thanks for pointing out the ambiguity in Section 5. We will clarify the branch indexing scheme in the text and caption, and add labels in Figure 4 to make it clearer which dendritic subtrees were frozen during retraining. The revised figure and caption will now make this explicit.

Summary

We've revised the manuscript to improve clarity on model design, training setup, function class definitions, and figure labeling. We also now include a clearer discussion of theoretical and experimental implications, and we've flagged ongoing work that will help address scalability and generalization beyond the current function set.

Thank you again for the detailed feedback. It’s helped us make the manuscript more precise, and we hope the revised version better communicates the motivation and scope of our work.

Thank you for your review and for raising important questions about dimensionality and realism. These are fair concerns, and we appreciate the chance to clarify our framing and explain where we see both the limits and utility of our approach.

On the question of dimensionality

You're absolutely right that real neurons receive high-dimensional, sparse inputs, and that their computation typically occurs in coordination with many other neurons. It remains an open question whether neurons can non-trivially coordinate these inputs, e.g. compute non-linearly separable functions of multiple inputs. This can include a relatively simple function such as XOR, a function of only two inputs, or more complicated functions such as feature binding. The dimensionality of inputs considered in these cases is not equal to the total dimensionality of the inputs a real neuron receives.

One reason to consider relatively low-dimensional inputs is tractability. Another is the observation that inputs to neurons are not typically highly synchronous or highly correlated. Analyzing random Boolean functions lets us consider functions of a kind of "worst-case" complexity and demonstrate that there is an upper bound here. Random Boolean functions are typically "hard". While the number of possible functions grows rapidly with input size, the complexity of randomly sampled functions is already very high at low dimensions. These functions tend to have high entropy (as defined in the paper) and high input sensitivity, which makes them difficult to learn regardless of architecture. In this sense, they serve as a kind of stress test. If a neuron can't learn a function in this regime, it likely wouldn't scale well to even more complex ones.

Similarly, realistic computations are often low-dimensional in practice. Even though a neuron may receive hundreds of inputs, many known examples of single-neuron computation (such as coincidence detection, sequence recognition, or spatially restricted integration) can be mapped to low-dimensional, low-sensitivity function classes. We are currently preparing a small table to clarify this point. It will show examples of computations that neurons are thought to perform and how they map onto specific Boolean function types.

On the value of studying single-neuron realizability

Thank you for the suggestion to discuss the network-level implications of this work. While we focus on single neuron computational complexity, these results have immediate impact on the complexity of entire circuits. A similar question arises in the domain of circuit complexity when considering Boolean circuits. In that case, one specifies a set of gates (e.g. AND/OR/NOT or simply NAND) that are "universal" in the sense that they and their compositions are sufficient to represent any function. While these sets do not affect membership in complexity classes such as NC or AC, they affect scaling prefactors and thus could have practical implications for network implementations. Similarly, in the present case, the difference between neurons that can represent functions of greater or lesser complexity can and will have an impact on the number of neurons necessary for a circuit to implement some function. These results thus have a direct consequence on the size of networks in both artificial and biological systems necessary to implement given functions.

We understand the concern that real learning happens in circuits, not only in isolated neurons. However, we believe it is still important to understand what individual neurons can and cannot compute based on their morphology (e.g. Beniaguev et al Cell 2021 mentioned by reviewer 2). Many cortical neurons differ significantly in their dendritic structures, and this variation likely constrains what role they can play within a network.

Our goal is not to suggest that neurons act merely as standalone classifiers. Instead, we are asking what kinds of computations a neuron is structurally capable of performing. We show, for example, that some architectures support broader function classes but may generalize poorly, while others show the reverse pattern. This kind of tradeoff could be important for understanding how neurons specialize or adapt during learning. We have added a short discussion of this point in the revised manuscript to make our scope clearer.

Thanks again for your thoughtful feedback. Your comments helped us sharpen the framing of the paper, and we have revised the manuscript to reflect those clarifications.

Thank you very much for the thoughtful and generous review. We are glad that the core message of the paper, "morphology sculpts computation, shaping not only what neurons do, but how they learn and adapt" , resonated with you, and we have added this line to the abstract as you suggested. Your comments on clarity, scope, and implications for both neuroscience and ML were encouraging, and we've aimed to improve the manuscript based on your specific suggestions.

Clarity of Figures (Fig. 3C and 4)

We appreciate your detailed suggestions here. We will revise Figure 3C to show a matrix-style heatmap that summarizes the average sensitivity for each input probability pair. This more compact format highlights the structure that was already implicit in the scatter-style plot and makes the architectural differences easier to interpret at a glance.

For Figure 4, we will increase the size of all panels and adjust the layout to improve readability. In particular, we will move the legend below the plot and expand the axes labels. These changes should help clarify how different architectures behave during re-training.

Citations and Neuroscience Context

We completely agree with your point that the paper could better acknowledge relevant neuroscience work, especially Beniaguev et al. (Cell, 2021). This was actually one of the key papers that inspired us to think about single neurons not just as shallow units with one hidden layer as previously thought, but potentially having a deeper architecture. While Beniaguev et al also focus on the role of receptors in increasing the effective depth of the single-neuron ANN, we focused on a simplified model that brought into focus the intrinsic depth vs breadth tradeoff in dendritic computation that arises due to the relative arrangement of a limited number of non-linearly integrating dendritic compartments - thus enabling the exploration of single-neuron dendritic integration in terms of computational complexity. We regret not citing it earlier and have now included a discussion of its relevance in the Introduction and Discussion sections.

In the revision, we also plan to highlight several recent experimental and theoretical works that inspired, and support, our framing. For example, Otor et al. (2022) demonstrate that layer 5 tuft dendrites exhibit morphologically defined compartmentalized computations during motor tasks. Their findings show that dendritic structure and NMDA-based nonlinearity shape how distinct motor variables are represented within the same dendritic tree - supporting the idea that morphology constrains local computation. Similarly, Gidon et al. (2020) discovered graded calcium-mediated dendritic spikes in human L2/3 pyramidal neurons, enabling single neurons to solve linearly non-separable tasks typically requiring multilayer networks. These studies reinforce the growing consensus that dendrites contribute substantially to single-neuron computational power.

We also appreciated the reviewer’s comment to consider hippocampal work. Recent studies by Li et al. (2023) and O’Hare et al. (2025) show that distal dendrites in hippocampal CA3 and CA1 neurons contribute to place field formation and memory flexibility, and are dynamically recruited during learning. These findings support the idea that dendritic subregions encode functionally distinct computations, possibly shaped by morphology and context. Building on our proposed framework, it could be useful to compare different cell types across brain regions in terms of their computational complexity, to understand whether region-specific cell types emerged to accomodate certain computational demands.

We also plan to cite recent reviews, such as Tye et al. (2024) which discusses how nonlinear mixed selectivity increases representational dimensionality. Their proposed mechanism - selective gating of variable mixtures echoes our architectural framing, where local nonlinear units gate combinations of inputs, effectively shaping inductive biases and generalization capacity. Finally, we acknowledge a broader body of modeling work (e.g., Kim et al., 2023, work by Poirazi group, Mel Group, Naud Group) that explores advanced computations enabled by dendritic trees through models of dendritic integration.

Given recent progress in in-vivo dendritic imaging, we foresee ample opportunity to test conclusions from this kind of analysis. For example, Aggarwal et al. (2023) introduced a method to track changes in synaptic activity in different dendritic compartments alongside somatic output. Techniques like this could help address questions such as:

• Do apical and basal dendrites show different learning dynamics during behavior?
• Do they support different levels of generalization across tasks?
• Are there differences in how synapses are rewired across dendritic domains during learning?

We plan to add a short section to the Discussion outlining these directions, and hope they’ll help bridge the gap between the theory we present and emerging experimental work.

Minor Fixes and Formatting

We have gone through the paper to fix:

• Inconsistent figure and equation references (e.g., “Figure 1a” vs. “Fig. 1A”).
• Typos, formatting issues, and spacing.
• Some unclear or crowded figure captions.

Thanks again for your thoughtful and constructive review. Your suggestions helped us strengthen both the framing and clarity of the paper, and we are hopeful that the revised version does a better job of connecting with both ML and neuroscience readers.

We thank the reviewer for the constructive feedback. We are glad that the motivation and clarity of the manuscript came through, and appreciate the reviewer’s interest in the broader significance of our findings. We address the weaknesses and questions listed by the reviewer below:

Training protocol

Thank you for the questions about our training protocol. We apologize for the lack of detail. We will follow your suggestion and add clear statements about training methods, which we detail below. It is important to note that we used two distinct approaches, gradient descent, as well as a non-gradient based method (DIRECT) in order to test for limitations of the learning algorithms.

For all training instances, which entailed learning the function mapping $f : \\{0,1\\}^n \rightarrow \\{0,1\\}$ in input dimension $n$, the input consisted of the full enumeration of $2^n$ input rows, with the target being the Y-column of the boolean function mapping. While training using the gradient-descent based approach, we used Binary Cross-Entropy as the loss function between the predicted and the target outputs during the training. We used an Adam optimizer with a fixed learning rate, with learning rates and epochs tuned according to the input dimension to ensure convergence (ranging from 6e4 epochs with lr = 5e-3 for $n_{dim} = 3$ to 6e6 epochs, lr = 1e-4 for $n_{dim} =8$). We also ran instances of training with an Adam optimizer with a learning rate scheduler, but that did not impact realizability trends shown in the paper.

For the DIviding RECTangles (DIRECT) optimization, we used Scipy's implementation which was based on Gablonsky et al 2001. Reasonable bounds on the learnable parameters were first set as input parameters for the optimization algorithm. The parameter space was constrained with weights bounded between -20 and 20, branch gains ($h$) between 0 and 10, thresholds ($\theta$) between -1 and 10, and output bias ($\Delta$) between -1 and 10. Both basal and apical cell architectures were trained using mean squared error loss between continuous sigmoid outputs and binary target labels. The DIRECT algorithm performed global optimization without gradients, exploring the 7*d +7 + 7 + 1 - dimensional parameter space (d input dimensions × 7 branches + 7 gains + 7 thresholds + 1 bias) to minimize classification error with a maximum of 2,000,000 function evaluations and zero volume tolerance for convergence. Training performance was evaluated using Hamming distance between binarized predictions (threshold 0.5) and ground truth binary labels.

For a broad overview on the evaluation of realizability of a boolean function by a given architecture, we point the reviewer to Supplemental Figure 1.

We agree that distinguishing between realizability and trainability is crucial. To clarify, our experiments include both “trainable realizability” (via supervised gradient descent or DIRECT optimization (Gablonsky J et al, 2001) and “best-case realizability”. In the revised version, we will explicitly describe our training setup in the main text, including the number of trials, optimizer used, convergence criteria, and the role of DIRECT as an alternative to backpropagation to confirm that the phase transition in realizability is independent of the training algorithm.

As the reviewer notes, some realizable functions may still be difficult to learn due to non-convexity or poor conditioning of the loss landscape. We agree and have made this distinction clearer in both the Results and Limitations sections. We believe that this also reflects a biologically-relevant constraint: real neurons must compute within the bounds of both their physical structure that impose constraints on parameter regimes and resolution. Our empirical results are thus best interpreted as a combination of architectural capacity and ease of access through plausible optimization, a point we now emphasize more clearly.

Network-level implications

Thank you for the suggestion to discuss the network-level implications of this work. While we focus on single neuron computational complexity, these results have immediate impact on the complexity of entire circuits. A similar question arises in the domain of circuit complexity when considering Boolean circuits. In that case, one specifies a set of gates (e.g. AND/OR/NOT or simply NAND) that are "universal" in the sense that they and their compositions are sufficient to represent any function. While these sets do not affect membership in complexity classes such as NC or AC, they affect scaling prefactors and thus could have practical implications for network implementations. Similarly, in the present case, the difference between neurons that can represent functions of greater or lesser complexity can and will have an impact on the number of neurons necessary for a circuit to implement some function. These results thus have a direct consequence on the size of networks in both artificial and biological systems necessary to implement given functions.

Minor points

• We have clarified the description of Figure 3B and improved the readability of Figure 4.
• We will also cite and briefly comment on work by Telgarsky (2016) and Rolnick and Tegmark (2018), and note how our setting differs (e.g., binary function realizability, fixed input dimension).
• The reviewer’s point about multiplicative interactions and gating is well-taken. As proposed in the review Payeur et al (2019), more complex models could be used to model such interactions. While outside our current scope, we agree this is a promising direction, and have included it in our extended discussion.