🤖 machine learning

Semantic Space Search Trajectory Networks

This paper introduces Semantic Space Search Trajectory Networks, a graph-based methodology that discretizes model predictions to visualize and compare learning dynamics across diverse algorithms and training regimes, revealing distinct structural patterns in how models generalize on real versus randomized data.

Original authors: Julian Agudelo, Alberto Tonda, Gabriela Ochoa, Vincent Guigue, Cristina Manfredotti, Evelyne Lutton

Published 2026-07-29

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Julian Agudelo, Alberto Tonda, Gabriela Ochoa, Vincent Guigue, Cristina Manfredotti, Evelyne Lutton

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to recognize a cat. You show it thousands of pictures, and it starts guessing. But how does it actually learn? Is it just blindly stumbling around in the dark, or is it following a hidden map? For decades, scientists have tried to answer this by looking at the robot's "brain" (its internal numbers and weights). But that's like trying to understand a symphony by staring at the sheet music of a single violinist while the orchestra plays; it's messy, confusing, and misses the big picture.

To make sense of this, researchers use a tool called a Search Trajectory Network (STN). Think of an STN as a subway map of the learning process. Instead of tracking every tiny step the robot takes, it groups similar moments together into "stations" (nodes) and draws lines (edges) showing how the robot moves from one station to the next. This helps us see if the robot is taking a direct highway to the answer or getting lost in a maze. The problem is, traditional subway maps only work for simple, low-dimensional problems. When the robot gets complicated (like a modern AI), the map becomes so crowded and high-dimensional that the lines all blur together, making it impossible to read.

This is where the concept of a Semantic Space comes in. Instead of looking at the robot's internal gears, we look at what it says. If the robot is looking at a picture of a cat, does it say "dog"? Does it say "cat"? Does it say "car"? The collection of all its guesses across a set of test pictures forms a "semantic vector." It's like a fingerprint of the robot's current understanding. By mapping the robot's journey through these fingerprints rather than its internal gears, we can create a clear, readable map even for the most complex AI. This paper asks: Can we use these "fingerprint maps" to compare how different types of learning algorithms think, and can they tell us if an AI is truly learning or just memorizing?

The Paper's Big Idea: Mapping the Journey, Not the Gearbox

The authors, Julian Agudelo and his team, introduce a new way to build these subway maps, which they call Semantic Space Search Trajectory Networks. Their main goal is to visualize how different machine learning algorithms (like neural networks, decision trees, and symbolic regression) "think" as they solve problems.

Usually, comparing a neural network to a decision tree is like comparing a race car to a bicycle; they have different engines and parts, so you can't easily line them up to see who is faster or how they navigate. But the authors realized that no matter what kind of machine you use, they all produce the same thing: predictions. By ignoring the internal mechanics and focusing solely on the predictions (the semantic vectors), they can put all these different algorithms on the same playing field.

How They Built the Map

To turn these continuous predictions into a readable map, the team had to solve a tricky problem: how do you group similar predictions together when there are millions of them?

Discretization (Turning Numbers into Categories): For regression tasks (predicting numbers like house prices), they chopped the continuous range of answers into 10 "bins" based on how often certain values appear (quantiles). For classification (guessing labels like "cat" or "dog"), they just used the final label. This turned a messy, continuous cloud of data into a set of distinct, countable categories.
Clustering (Grouping the Stations): They used a method called agglomerative clustering. Imagine you have a pile of sand grains (each grain is a prediction state). You start by treating every grain as its own island. Then, you slowly merge the two closest islands together. You keep merging the closest pairs until the distance between any two remaining islands gets too big (controlled by a threshold called $\tau$ ). The final islands become the "stations" on your subway map.
Drawing the Lines: As the algorithm learns, it moves from one prediction state to another. They tracked these moves and drew arrows between the corresponding stations. The thicker the arrow, the more often different training runs took that specific path.

What They Found: The "Funnel" vs. The "Star"

The team tested this method on several datasets, including recognizing handwritten digits (MNIST), fashion items (Fashion-MNIST), and predicting car prices. They compared three very different algorithms: MLPs (neural networks), XGBoost (a powerful tree-based method), and Symbolic Regression (which tries to find mathematical formulas).

The Discovery:
When the algorithms were learning on real data (where there is a true pattern to find), the maps looked remarkably similar, regardless of the algorithm used. They formed a "funnel" shape.

The Funnel: The journey started at many different points (random initial guesses), but the paths quickly merged into a few common "highways" and funneled down into a single, tight cluster of "best" stations. This suggests that when there is a real pattern to learn, different algorithms tend to discover the same intermediate steps and converge on the same solution.
The Difference: While the overall shape was similar, the "traffic" looked different. Neural networks seemed to get stuck in a "basin of attraction" where they bounced around a bit before settling, while XGBoost was more direct, almost like a greedy robot that just kept tightening its grip on the answer. Symbolic Regression, however, was the odd one out; it didn't funnel down. It explored the map in many different directions, rarely converging on a single path, which matches its nature of randomly searching for formulas.

The "Memorization" Test: Does the Map Reveal Cheating?

The most exciting part of the paper comes from a famous experiment by Zhang et al. (2017), which showed that neural networks can "memorize" random data just as well as real data. If you scramble the labels (tell the AI that a picture of a cat is actually a "dog"), the AI can still learn to predict perfectly on the training set, but it fails miserably on new data. This is the "memorization" regime.

The authors used their Semantic Space STNs to see if the shape of the learning journey could tell the difference between learning (generalization) and memorizing (random guessing).

Real Labels (Learning): The map was dense, efficient, and centralized. It looked like a busy city with a central hub where everyone met. The paths were interconnected, suggesting the algorithm was building a structured understanding.
Shuffled Labels (Memorizing): The map looked like a star. The paths were isolated, disjointed, and scattered. There was no central hub. Each training run ended up in its own lonely corner, never meeting the others.

The Conclusion:
The paper suggests that the structure of the learning journey reveals the truth. When an AI is truly learning a pattern, the paths converge and connect. When it is just memorizing noise, the paths stay isolated. They measured this using graph metrics like global efficiency and density. For example, on the "Bioresponse" dataset, the "real label" map had a density of 0.0157, while the "shuffled label" map was much sparser at 0.0049.

They also tested what happens if you slowly corrupt the data, replacing 20%, 40%, up to 100% of the labels with random noise. As the corruption increased, the "funnel" slowly fell apart, turning into the "star" shape. The graph metrics (like global efficiency) dropped steadily, showing a smooth transition from learning to memorizing.

Why This Matters

This work suggests that we don't need to look inside the black box of a neural network to understand if it's learning or cheating. We just need to look at the map of its predictions. If the map is a connected, efficient network, the AI is likely learning something real. If it's a scattered collection of isolated paths, it's probably just memorizing.

The authors are careful to note that this is a simulation-based observation and a qualitative tool for analysis, not a magic bullet that solves the mystery of generalization. They suggest that this method offers a new, behavioral perspective that complements existing theories. It's a new pair of glasses that lets us see the "shape" of intelligence, showing us that whether you're a neural network or a decision tree, if you're learning the truth, your journey looks the same.

Technical Summary: Semantic Space Search Trajectory Networks

Problem Statement
Search Trajectory Networks (STNs) are established graph-based tools for visualizing and characterizing optimization algorithms by mapping search states to nodes and transitions to edges. However, traditional STN construction relies on discretizing the explicit search space (e.g., parameter vectors). This approach faces significant limitations in high-dimensional settings due to the "curse of dimensionality," where distance concentration and sparse neighborhoods make defining meaningful discretization and neighborhoods difficult. Consequently, STNs have largely been confined to low-dimensional or combinatorial optimization problems. Furthermore, comparing learning dynamics across heterogeneous algorithm families (e.g., neural networks vs. gradient-boosted trees vs. symbolic regression) is challenging because their parameter spaces are structurally incomparable.

Methodology
The authors propose constructing STNs within semantic spaces, defined as the space of a model's predictions on a fixed sample set. This shifts the representation from model parameters to functional behavior. The methodology involves the following steps:

Semantic Vector Generation: For a given dataset $D = \{(x^{(i)}, y^{(i)})\}$ , an iterative learner produces a sequence of semantic vectors $\langle \hat{y}_0, \dots, \hat{y}_T \rangle$ , where $\hat{y}_t$ contains the model's predictions for all samples at optimization step $t$ .
Discretization Strategy: To handle high-dimensional semantic vectors, the authors employ a clustering-based discretization:
- Classification: Predictions are converted to discrete class labels (using argmax for logits).
- Regression: Continuous predictions are discretized into global quantile-based bins computed across all semantic vectors.
- Clustering: Agglomerative clustering with complete linkage is applied using normalized Hamming distance. Clusters are merged iteratively until the maximum pairwise distance between elements of two clusters exceeds a threshold $\tau$ .
Network Construction: The resulting clusters define the nodes of the STN. Transitions between consecutive semantic vectors in the optimization trajectory are mapped to directed edges between their corresponding cluster assignments. Edge weights reflect transition frequencies.
Hyperparameter: The only tunable hyperparameter is the clustering threshold $\tau$ , which controls the granularity of the aggregation.

Key Contributions

High-Dimensional STN Construction: Introduction of a clustering-based discretization strategy that enables STN construction in high-dimensional semantic spaces, bypassing the need for explicit parameter-space discretization.
Cross-Algorithm Comparison: Demonstration that semantic space STNs allow for the qualitative and quantitative comparison of learning dynamics across fundamentally different algorithm families (MLPs, XGBoost, Symbolic Regression) by unifying them under a common functional representation.
Generalization Analysis: Application of semantic space STNs to contrast standard training with the label randomization regime (Zhang et al. [22]), revealing structural differences in learning dynamics that correlate with generalization capabilities.

Results
The authors applied the methodology to benchmark classification and regression tasks using Multi-Layer Perceptrons (MLPs), XGBoost, and Symbolic Regression (SR).

Algorithm Comparison:
- MLPs and XGBoost: Both gradient-based methods exhibited "funnel-like" behaviors where diverse starting points converged toward a common region of the semantic space before reaching a final best node. MLPs often showed a basin of attraction with interconnected nodes, while XGBoost trajectories were more deterministic, converging to a single best node.
- Symbolic Regression: SR displayed markedly different, more exploratory dynamics, with end nodes distributed across a wide range of semantic locations, reflecting its stochastic, non-gradient-based search.
Generalization vs. Memorization:
- Structural Differences: STNs trained on real labels consistently formed denser, more efficient, and more centralized graphs (funnel topology) compared to those trained on shuffled labels, which resulted in sparse, disjoint, star-shaped topologies with isolated trajectories.
- Quantitative Metrics: Graph-theoretic descriptors (density, global efficiency, closeness centrality, PageRank) consistently separated the two regimes. Real-label training yielded higher values across these metrics.
- Label Corruption: Progressive corruption of labels (interpolating between real and random) showed a monotonic decrease in graph connectivity and efficiency, visually transforming the dense generalization structure into isolated trajectories as information was destroyed.
Robustness: The overall topology of the semantic space STNs remained stable across varying numbers of sampled trajectories (runs), suggesting the method captures persistent aspects of optimization dynamics.

Significance and Claims
The paper claims that semantic space STNs provide a tool for analyzing and comparing learning dynamics across machine learning models and training regimes that are otherwise incomparable. By focusing on the space of predictions rather than parameters, the method captures functional training dynamics arising from the interaction between learning algorithms and data.

Specifically regarding generalization, the authors propose a behavioral view: the structural differences observed in semantic space STNs (dense/centralized vs. sparse/disjoint) reflect the presence or absence of an underlying function governing the data. When a true relationship exists, optimization discovers structured intermediate states that lead to clustered convergence. When labels are random, trajectories fragment. The authors position semantic space STNs as a complement to existing loss-landscape analyses, offering a global perspective on the optimization process that is distinct from local minima analysis. The work bridges perspectives from evolutionary computation and deep learning to offer a unified framework for studying optimization behavior.