Neuroevolution of Self-Attention Over Proto-Objects

1 Introduction

Visual attention mechanisms have emerged as a powerful solution for reducing computational complexity in high-dimensional perception tasks. By creating an information bottleneck between visual inputs and control networks, these mechanisms enable efficient processing of complex scenes [14]. Recent work has demonstrated that evolving a hard-attention module jointly with an LSTM [10] controller can produce remarkably efficient agents that operate solely on small image patches [22]. This approach not only yielded neural networks orders of magnitude smaller than competing methods but also achieved state-of-the-art results in challenging Reinforcement Learning environments like Car Racing and Doom Take Cover [3]. The success stems from the attention layer's ability to filter irrelevant input regions, simplifying the controller's task while providing robust generalization and noise resistance.

We advance this line of research by replacing fixed-size, uniformly distributed patches with proto-objects – coherent regions of locally uniform visual features [6] – obtained through image segmentation [7]. This shift in representation offers two key advantages. First, they provide a more compact representation, as most scenes decompose into fewer proto-objects than patches. Second, each proto-object encodes richer semantic information through a small descriptor vector capturing properties like shape, size, and color.

This proto-object approach enables a significantly streamlined architecture. The self-attention module becomes substantially smaller while processing higher-level features, leading to improved selection and better-filtered information for the controller, which can also be simplified. Our results in the Car Racing and Doom Take Cover environments [3] demonstrate that this more efficient architecture matches or exceeds the performance of patch-based implementations while reducing the parameter count by 62% with 2.6 times faster training.

2 Background

Modeling human visual attention has been an active research area over the past 35 years. Many different models of attention were proposed, which in addition to providing theoretical contributions to neuroscience and psychology, have demonstrated successful applications in computer vision and robotics [2]. Early computational models focused primarily on bottom-up, saliency-based attention, while more recent approaches have incorporated top-down influences and object-based selection mechanisms.

The biological visual system provides crucial insights for designing efficient artificial vision systems. A fundamental constraint is that neural resources are limited - Koch et al. [11] demonstrated that retinal ganglion cells balance metabolic costs against information transmission, achieving highly efficient coding despite using relatively low firing rates. This suggests an evolutionary pressure toward strategic information bottlenecks rather than attempting to process all input equally. Walther and Koch [28] showed that one such bottleneck occurs at the proto-object level, where coherent regions of the scene are selected for enhanced processing before full object recognition occurs. This allows the visual system to serialize complex scenes into manageable chunks while maintaining high coding efficiency.

2.1 Types of Visual Attention Mechanisms

Visual attention in biological systems operates through three primary mechanisms. Space-based attention operates on specific locations in the visual field, treating attention as a spotlight that enhances processing at selected spatial coordinates. Feature-based attention selectively enhances the processing of specific features (like color, orientation, or motion) across the entire visual field, regardless of spatial location. Object-based attention operates on perceptually grouped elements that form coherent objects, suggesting that attention selects entire object representations rather than just spatial locations or individual features [5, 25, 27].

2.2 Self-Attention

A key mechanism in modern computational attention is the self-attention layer. In its standard form [26], self-attention operates on a set of N input vectors, each of dimension d_in, linearly transforming them through learned weight matrices W_O and W_K to obtain Query (Q) and Key (K) matrices:

S = softmax( QK^T / √d_k )       (1)

where d_k is the dimension of the key vectors. The attention scores S show how related the input elements are. S is further combined with a matrix V, which is also a linear transformation of the input, to form the contextual representation A = SV, whose vectors contain the representation of each input considering the overall context.

2.3 Proto-Objects and Information Bottlenecks

Proto-objects are an intermediate representation between raw visual features and fully recognized objects [19, 28]. They are formed during pre-attentive processing and represent coherent regions of the visual field that share common visual properties. These structures serve as potential candidates for attention before full object recognition occurs [16], allowing the visual system to efficiently prioritize processing resources.

Information bottlenecks in visual processing serve to compress the high-dimensional visual input into more manageable representations while preserving task-relevant information [11, 23]. These bottlenecks can occur at various levels of processing, from early visual features to object recognition, and play a crucial role in managing the computational resources required for visual processing [29]. The formation of proto-objects itself represents a natural information bottleneck, as it reduces the complexity of the visual scene while maintaining behaviorally relevant information [28].

3 Related Work

Our approach builds upon and extends several lines of research in visual attention, reinforcement learning, and deep learning. Here we review the most relevant prior work that informs and contextualizes our contribution, focusing particularly on approaches that address the challenges of efficient visual processing and attention mechanisms.

3.1 Self-Interpretable Agents

Recent work by Tang et al. [22] explored the use of hard-attention mechanisms in reinforcement learning. Their approach divides the visual input into 7x7 patches and applies a modified self-attention mechanism to select only the top-k patches for processing (see Fig. 2). This creates an information bottleneck that forces the model to focus on the most relevant inputs while ignoring others. When applied to vision-based reinforcement learning tasks, this approach enabled agents to achieve better performance, interpretability and computational efficiency with far fewer parameters than conventional approaches. Our method differs mainly by using proto-objects instead of patches, reducing the number of tokens and their dimensionality while adding higher-level information to them.

3.2 Proto-Object Based Approaches

Orabona et al. [16] demonstrated the effectiveness of proto-objects as the basic units of visual attention. Their work showed that using proto-objects as an intermediate representation naturally corresponds to potential objects in the scene, allowing for efficient processing while maintaining meaningful visual features.

The idea of using higher-level information from blobs as input was further explored by Liang et al. [12] in their work on Blob-PROST (Pairwise Relative Offsets in Space and Time). Their approach demonstrated that visual features based on color blobs could achieve performance competitive with DQN [15] while using far fewer parameters. The core insight was representing game screens in terms of "blobs" - contiguous regions of same-color pixels that often correspond to game objects. This is a special case of our use of proto-objects, that are not restricted to same-color pixels. This representation was combined with position and relative offset features between blobs, capturing both spatial and temporal relationships. However, their representation consisted of more than 100 million binary features, while ours is based on compact representations of individual proto-objects that can be attented individually.

3.3 Object-Based Reinforcement Learning

While proto-object approaches focus on intermediate representations, some researchers have pushed further toward working with fully-fledged objects. Woof and Chen [30] experimented with representations of high-level objects (e.g. identifiable entities in a game screen) rather than end-to-end video game playing. However, they assume the objects are previously given, which requires access to the game engine or specific object detectors.

A more robust approach [1] demonstrated that operating directly on object-level representations can dramatically improve sample efficiency in reinforcement learning tasks. Their approach learns a succinct object representation from pixels without supervision by first oversegmenting images into primitive segments, modeling their dynamics, and then combining segments when they have similar dynamics. Their method leverages the insight that important events tend to occur when objects interact, using this to guide exploration toward states involving object contacts. While their approach achieves impressive results - learning up to 10,000 times faster than conventional deep RL methods and even outpacing human learning in some cases - it requires significant computational overhead for object detection and tracking. This motivates the exploration of proto-object approaches, which provide a balance between processing efficiency and representational power.

4 Proto-Object Attentional Agent

Our work builds upon and connects several research directions in computer vision, deep learning, and evolutionary computation. We combine insights from biological models of visual attention, efficient neural architectures, and classical computer vision techniques to create a hybrid system that leverages the strengths of each approach. We apply hard-attention mechanisms to proto-objects rather than raw pixels or arbitrary patches. This approach implements an information bottleneck similar to what Koch et al. [11] observed in biological systems, while operating on the semantically meaningful proto-objects described by [16, 19]. By selecting only the most relevant proto-objects for processing, we create an information bottleneck at a more semantically meaningful level than previous approaches.

This combination is particularly well-suited for neuroevolution, as the discrete selection of top-k proto-objects and the transfer of coordinates to the controller create nondifferentiable operations that are challenging for gradient-based methods but natural for evolutionary approaches. Additionally, by forcing the model to be explicitly selective about which parts of the visual input it processes, we gain direct interpretability – we can visualize exactly which proto-objects the model considers important for its decisions, providing insights into its decision-making process that are often lacking in traditional deep learning approaches.

4.1 Implementation

Our method consists of 5 main stages: convolution, quantization, segmentation, attention and control, described next.

4.1.1 Convolution

The convolution stage aims to shift, rescale, filter and/or mix the original image channels, providing a pre-processed representation for the next stages. Particularly, in our experiments, we use a single convolutional layer with 3 1x1 filters. The choice of 3 filters is necessary for compatibility with the residual connection. It is possible to add more convolutional layers as long as they keep the same image size. In this case, adding a final layer with 3 filters is enough to bring down the number of dimensions to the same number of channels in the image. After that, we add the original image to the convolution output, forming a residual connection [9], whose function will become clear in the next stage.

4.1.2 Quantization

Quantization aims to reduce the amount of information to be processed in the next stages. In our experiments, we perform simple uniform quantization of the convolution output using 1 bit per channel (could be more for more complex tasks, and could even be evolved). As a result, we obtain an image with at most 8 distinct colors, each representing a different kind of segment. Note that, besides it being a simple fixed quantization, its combination with the convolutional layer before it results in an adaptive segmentation and quantization mechanism.

This stage has synergy with the convolutions: the shift, rescale, and mix of the original image channels may put them into different quantization bins. But since there are discontinuous jumps in the evolution fitness surface necessary to find an appropriate segmentation, which can take some time for the evolutionary algorithm to figure out, we use the residual connection in the previous stage as a means to kickstart evolution from a trivial segmentation over the original image colors. Thus, the purpose of convolution is to change the segmentation away from the trivial one (if necessary).

4.1.3 Segmentation

Segmentation aims to create the proto-objects, i.e. descriptors for regions of semantically similar pixels received from the previous stages. In this work, we apply image labeling by color-connected regions [7, 20]. From each extracted region, a set of attributes can be obtained, resulting in d_in features (regions 1 pixel wide or tall are treated as noise and ignored).

After thorough experimentation, we ended up with a set of d_in = 11 features, namely: quantized segment color (R, G, B), center of mass (X,Y), total area in pixels, bounding box width, bounding box height, bounding box area, aspect ratio and extent (bounding box area divided by region area). All of those can be easily and efficiently computed from the obtained regions, and will help the next stage to make more informed decisions. Orientation (correlation among pixel coordinates) could also be useful, but it added too much runtime overhead to our model and was left out. All values are normalized between -1 and 1, and aspect-ratio is also log-transformed such that 1 and -1 correspond to extreme ratios, while 0 means equal sides:

NormAspectRatio = 2 * log(aspectRatio) / log(max(imageWidth, imageHeight)) - 1

4.1.4 Attention

The attention module aims to model relations among the proto-objects identified in the segmentation stage. The features for N proto-objects are fed to our model's attention layer as a set of N d_in-dimensional tokens, in the attention jargon [26]. The attention layer embeds these tokens into two d_q-dimensional vectors Q and K. There is, however, an additional touch in our implementation: we add a Parametric Rectified Linear Unit (PReLU) layer before and after the linear transformations. PReLU is a generalization of ReLU activation, where the slope of the negative part is adaptive (PReLU(x) = max(ax, x)) for each layer or neuron (the latter in our case). For only 15 additional parameters, this enables our attention layer to model more complex relations, as a single PReLU neuron was shown to solve the XOR problem [17]. In our case, it enables the selection of midrange values (like gray colors) when a is negative (making the function nonmonotonic), which is not possible with pure linear layers. More layers of traditional self-attention could instead be used, but we opted for the simpler PReLU solution in this work to keep the number of parameters and runtime low.

Proceeding with the usual self-attention procedure, an attention matrix is computed by Eq. 1, and then an importance vector is obtained by row-wise summation. Instead of the usual mixing of tokens with a V matrix performed in traditional self-attention, we simply perform top-k proto-object selection over the resulting row-wise sum.

We remark that the attention computation has quadratic asymptotic time complexity on the number of tokens N. Drastically reducing the number of tokens by using proto-objects instead of patches makes our attention module much faster.

In our experiments, we went to the extreme and set k = 1 (coordinates of a single proto-object is passed to the controller, described next). This is possible because our attention module is more expressive than the original and proto-objects contain higher-level information, making a single well-selected proto-object enough for the controller to make its decisions (better selection means less work to the controller). It is also more biologically plausible, as we focus on a single visual item at time [4].

4.1.5 Control

Finally, the control stage selects an action to perform in the environment. In our implementation, a transfer function f(n) is applied to each feature vector from the selected proto-objects and the results are concatenated and fed as input to an LSTM [10] controller, which is responsible for learning temporal associations and producing the control output.

In our case, f(n) just returns the coordinates of the proto-object center of mass. More elaborate transfer functions could be used to feed the controller with more properties of each selected proto-object, but the center of mass was enough for our problems. This is possible because the joint evolution of the attention end control modules results in an implicit "agreement": by always selecting the same kind of proto-object (grass, track, etc...), there is no need for the controller to guess which is it. If attention focused on different kinds of proto-objects each time, it would not be possible to distinguish them solely by their coordinates, unless they consistently appeared on specific regions of the screen, being distinguishable by position (like the head-up display always at the bottom of the screen). They could also be distinguished by the controller if the attention module consistently puts the same kinds of proto-objects into the same ranking spots (e.g., grass first, track second), but this is an additional piece of complexity to be learned.

4.2 Overview

A summary of the differences between our hyperparameter choices and the previous work based on image patches [22] is shown in Table 1, as well as the resulting number of learnable parameters in each model, showing that our model is significantly (62%) smaller in total, due to its compact attention layer and smaller bottleneck with k = 1. The complete process can be seen in Fig. 3. Although this model is non-differentiable, it is learnable via derivative-free optimization methods such as CMA-ES [8].

5 Experiments and Results

In order to compare our approach to the patch-based one of [22], we test it on the same environments of [22]: CarRacing and Doom-TakeCover [3]. For both, we run CMA-ES with a population of 128 solutions for 1000 generations and evaluate models on 8 seeds every generation. Seeds are based on generation and repetition numbers. We test models every 100 generations on 400 new seeds and extract means and variances to produce 95% confidence intervals. Statistical significance is obtained from two-sided Mann-Whitney U tests [13]. Note that the original experiments in [22] ran for 2000 generations with 16 seeds each and a population of 256 solutions, so they are not directly comparable. We halved each of those hyperparameters due to hardware limitations, and performed the original experiments again in this new setup for fair comparison.

Our experiments ran on the following hardware setup: AMD Ryzen 5950X CPU, 128GB DDR4 3200 RAM and Nvidia RTX 3090 GPU. Training was paralellized over 32 threads, limiting each evaluation to a single thread. The patch-based solution took advantage of the GPU, but our method was optimized for CPU, as multi-label connected-components analysis and labeling did not fit well with the GPU.

5.1 Car Racing

This is a top-down racing environment with randomly generated tracks (as seen in Figs. 1 and 2). It is visually simple enough to skip the convolution and quantization stages of our approach, but we perform them anyway in order to verify the generality of the method. The reward is -0.1 every frame, -100 for going far off-track (which also causes termination), and +1000/N for every track tile visited, where N is the total number of tiles visited in the track (tiles are visible as slightly distinct shades of gray), and it is considered solved above 900 points. This incentivizes the controller to be fast and accurate. There are 3 continuous actions: steering (-1 is full left, +1 is full right), gas and braking. There is a version V2 of this environment available ¹, but it uses Pygame 2, which is slow. We use V0, which is twice as fast by using OpenGL, and implement our own optimizations that adds a further 2x speedup. There are no significant differences between both versions except for compatibility with the new API [24] and better hardware and software compatibility.

Our method was more sample-efficient, with superior average score throughout the training, and achieved a significantly better (p = 1.1e-22) score of 910.39 after training (Fig. 4). Moreover, as Table 2 shows, it did so by using only 2% the number of tokens per frame as the patch-based solution and 62% less adjustable parameters. And despite running on CPU, it trained 2.7 times faster with respect to the patch-based method, which ran on GPU.

¹https://gymnasium.farama.org/environments/box2d/car_racing/
²https://www.pygame.org

An interesting aspect of this experiment is to observe the evolution of segmentation and attention, as Fig 5 shows. The solution starts with the trivial quantization over the task's original colors, but since the track is dark, it gets merged with the black head-up display (HUD) at the bottom of the screen. Nevertheless, it already knows how to focus on the smaller grass region, as it usually points at the direction the car must turn. At 300 generations it learns to separate the track from the HUD, while at 800 generations it separates the car and the red corner markings from the track. While the car is useless (it is always at the same place and was even merged with the track in other experiments), the red markings can reinforce the correct turning side by "voting" (as queries) on their adjacent grass region. At 900 generations, it learns to segment the track tiles, but discards it in the final solution. The final solution decomposed into its processing steps can be seen in Fig 6.

5.2 Doom Take Cover

This task is based on the game Doom, which is visually more complex and features much more colors than the previous task (see Fig. 8, top-left), making the convolution and quantization steps strictly necessary to prevent a huge number of segments. It takes place in a rectangular room. The agent is spawned along the wall, and monsters are constantly and randomly spawned along the opposite wall. They keep shooting fireballs at the agent, which must avoid them to survive. The agent gets 1 reward point for every tic alive and has 3 discrete actions: move left, right or stand still.

Learning curves are shown in Fig. 7. We observe that our approach had slightly lower sample-efficiency, needing more generations to match the patch-based model performance (p = 0.414). We also experimented with d_q = 4, k = 10 (same as the patch-based setup) and 3x3 convolutions (2671 parameters) and this solution had better sample-efficiency and achieved significantly (p = 2.8e-5) higher performance at a 1193 score in 55h of training. We hypothesize that the performance degradation was due to k = 1, meaning that the LSTM is under much harder work to keep up with multiple interest proto-objects on screen, or even missing some of them entirely, while also learning to discard the wall proto-objects that activate when there are no projectiles on screen.

Table 2 also shows that the number of extracted proto-objects was low for this environment as well, demonstrating that our pre-processing steps are effective in reducing and uniformizing the visual complexity of different domains, while keeping necessary information for decision making. The training time was 2.6 times faster for k = 1 and 1.6 times faster for k = 10.

The key processing stages in the Doom environment are illustrated in Fig. 7: image resizing, 1x1 convolution, color quantization, and attention (k = 1). Remarkably, the evolved agent adopts a surprisingly minimalist strategy, ignoring seemingly critical elements like incoming fireballs. Instead, it focuses exclusively on the right-most monster on screen while executing a rhythmic left-to-right movement pattern. This strategy matches the performance of the patch-based model, despite the latter attending to both fireballs and walls. The equivalence to our simple approach suggests that the patch-based model's LSTM might also be relying primarily on periodic movement and ignoring projectile coordinates. This strategy proves effective because the monsters' projectiles target the agent's current position - continuous movement therefore serves as a robust avoidance technique, regardless of the specific locations of incoming fire. However, our k = 10 agent seems more reactive to fireballs.

6 Conclusion and Future Works

We have presented a novel representation for bottleneck-attention-based agents in visual tasks that operates on proto-objects rather than raw pixels or image patches. By working with these pre-attentional primitive objects, obtained through classical computer vision methods, we achieved comparable or superior performance while dramatically reducing the number of tokens to attend and their dimensionality, as well as training time compared to previous solutions. The success of this hybrid approach highlights one of the key advantages of evolutionary methods for training such models: the freedom to combine differentiable and non-differentiable components without being constrained by the requirements of gradient-based optimization. Nevertheless, developing a fully differentiable version of our solution remains an attractive direction for future work, as it could substantially improve sample efficiency.

Our experiments revealed that bottleneck attentional models are susceptible to local maxima during evolution. The dual-module architecture (attention and control) makes it challenging to discover new attention strategies once an approach becomes established, as the controller adapts specifically to the current attention mechanism. Any significant changes to the attention module risk disrupting this delicate balance. We hypothesize that CMA-ES may be too greedy for this architecture, and alternatives like differential evolution [21] might be more suitable by allowing multiple attention strategies to evolve in parallel.

We demonstrated that by enhancing the attention layer, sending coordinates of a single proto-object to the controller is sufficient to produce effective policies. This works because the LSTM can maintain and update an internal state representation across frames, deciding what information to preserve or discard. This approach aligns well with biological eye movements, where focus necessarily shifts between individual locations or objects [4]. However, this simplified information flow comes at the cost of longer learning times when there are multiple relevant entities on screen, as the attention module must attend to them all and the controller must develop sophisticated memory management strategies. One potential solution is to decouple memory and control, possibly by implementing attention mechanisms over recently attended coordinates to generate fixed-size embeddings [18] for the controller. This could be further extended to include adaptive storage and retrieval from vector databases.

Several promising directions for future research emerge from this work. Feedback signals from the controller could modulate attention, enabling active top-down strategies. This would require enriching the information flow from the attention module to help the controller interpret incoming signals. Multi-head attention represents another natural extension. The approach could potentially scale to full object recognition by incorporating additional convolutional layers and processing depth (when available) and motion information. Self-attention mechanisms might enable autonomous grouping of regions into higher-level entities, while cross-attention could facilitate object tracking across frames.

Finally, a crucial next step is validating our approach on real-world images and determining whether increased complexity in the convolution and quantization stages is necessary, or if patch-based approaches prove more effective in such scenarios. Success in this domain could lead to more efficient robot and self-driving car systems, reducing computational requirements while enabling more sophisticated intelligence per processing unit.

How to Cite

@inproceedings{10.1145/3712256.3726451,
	author = {Pinto, Rafael and Tavares, Anderson},
	title = {Neuroevolution of Self-Attention Over Proto-Objects},
	year = {2025},
	isbn = {9798400714658},
	publisher = {Association for Computing Machinery},
	address = {New York, NY, USA},
	url = {https://doi.org/10.1145/3712256.3726451},
	doi = {10.1145/3712256.3726451},
	booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference},
	pages = {1300–1308},
	numpages = {9},
	keywords = {neuroevolution, representation learning},
	location = {NH Malaga Hotel, Malaga, Spain},
	series = {GECCO '25}
}