Memory Search as a Random Walk
The Walk Inside Your Head
The last two chapters built a machine: a Markov chain (Chapter 13), then a random walk on a network (Chapter 14). This chapter argues that the machine is not just a model of card decks and web pages — it is a model of you. Specifically, of how you search your own memory.
Try it right now, the way Chibany’s class did. Name as many animals as you can, out loud, for thirty seconds. Go.
Done? Look at the order they came out in. Almost certainly they arrived in bursts: a clump of pets — dog, cat, hamster — then a pause, then a clump of big animals — lion, tiger, zebra, giraffe — then a switch to, say, farm animals. People do not produce animals in random order; they come out in runs by category, with pauses between the runs. This is the semantic fluency task, and the clustering-and-switching pattern in it has been documented for eighty years (Bousfield & Sedgewick, 1944; Troyer, Moscovitch & Winocur, 1997).
Chibany: “My list did that exactly — three pets in a row, a pause, then a pile of zoo animals. Why?”
Alyssa: “And why those animals, in that order? That’s the real question.”
Here is the claim of this chapter, due to Abbott, Austerweil and Griffiths (2012): your semantic memory is a network, and recall is a random walk on it. The list you produce is the sequence of nodes the walk visits. The clusters are the walk lingering inside a densely-connected community of related concepts; the switches are the walk crossing a bridge edge to another community — exactly the Cat-the-bridge crossing from Chapter 14. No special “search strategy” required: the structure of the network plus the dead-simple walk produces the bursty, switching behaviour on its own.
Structure, Process, Behaviour
It is worth pausing on the shape of this explanation, because it is the same three-part shape that runs through the whole course:
- Structure — the semantic network. Which concepts are linked to which. Crucially, this is estimated from other data (word-association norms: ask thousands of people “what comes to mind when I say doctor?” and draw an edge to nurse, hospital, sick), not fitted to the fluency task we’re trying to explain.
- Process — the random walk. Memoryless, undirected, one step at a time. The same Markov chain as always.
- Behaviour — the fluency list. Which animals, in which order, with which pauses.
The bet is that structure + process jointly predict the behaviour — and they do, with no recall-specific machinery bolted on. That is a strong, falsifiable claim, and it is what makes this more than a story.
graph LR
Pet1["dog"] --- Pet2["cat"]
Pet1 --- Pet3["hamster"]
Pet2 --- Pet3
Pet2 --- Bridge["tiger"]
Bridge --- Afr1["lion"]
Afr1 --- Afr2["zebra"]
Afr1 --- Afr3["giraffe"]
Afr2 --- Afr3
classDef node fill:none,stroke:#9bbcff,stroke-width:2px,color:#fff
classDef bridge fill:#9bbcff,stroke:#9bbcff,stroke-width:2px,color:#111
class Pet1,Pet2,Pet3,Afr1,Afr2,Afr3 node
class Bridge bridge
linkStyle default stroke:#9bbcff,stroke-width:2px,color:#fffA walker rattling around the pets triangle produces a burst of pets; to reach the big animals it must cross the bridge (tiger); then it rattles around over there. Cluster, switch, cluster — straight out of the wiring, just as Chapter 14’s walk kept getting funnelled through Cat.
The Catch: the Walk Is Not the List
There is a problem, and facing it squarely is what makes the model real rather than hand-wavy. A raw random walk is not a fluency list, for two reasons:
- A walk revisits nodes — it will step onto dog again and again. But you don’t say “dog” five times; you say it once.
- A walk wanders through non-animals — to get from one animal cluster to another it may pass through house, food, fur, whatever concepts sit between them. But those never appear in your animal list either.
So the sequence of nodes the walk visits is longer and messier than the list you actually produce. Something has to map the latent walk onto the observed behaviour. That something is the censoring function, and it is the technical heart of the model.
The Censoring Function
The rule is beautifully simple: you report a word only the first time the walk lands on it, and only if it is an animal. Everything else — revisits, and every non-animal — is censored. (The word censoring is borrowed from statistics, where a censored observation is one that genuinely happened but went unrecorded — exactly our case: the walk really does step onto house and revisit dog, but those steps never make it into the spoken list.)
To make this measurable, define the first-hitting time $\tau(k)$: the timestep at which the walk reaches the $k$-th distinct animal for the first time. Walk through the paper’s own example. Suppose the walk produces
$$X_1 = \text{animal},\ X_2 = \text{dog},\ X_3 = \text{house},\ X_4 = \text{dog},\ X_5 = \text{cat}.$$Reading left to right and applying the rule: animal is the starting cue (not reported); dog at step 2 is a first-time animal — report it, and $\tau(1) = 2$; house at step 3 is not an animal — censor; dog again at step 4 is a revisit — censor; cat at step 5 is a first-time animal — report it, and $\tau(2) = 5$. The reported list is just “dog, cat” — two words distilled from a five-step walk.
Now the timing. The data a fluency experiment actually records is the inter-item response time (IRT) — the gap between producing one animal and the next. (This “IRT” is inter-item response time, not the item response theory of test design — same initials, unrelated idea.) The total time to produce a word has two parts that happen in sequence, so they add: the time to mentally travel to the word, plus the time to physically emit it. The travel time is how far the walk had to wander; the emit time we take to be the word’s length (longer words take longer to produce — in Hills et al.’s experiment people typed their answers, but the same holds roughly for saying them aloud). So
$$\text{IRT}(k) = \tau(k) - \tau(k-1) + L\big(X_{\tau(k)}\big),$$where $L(\cdot)$ is the length of the word. The first term, $\tau(k) - \tau(k-1)$, is how many steps the walk wandered between first-hitting animal $k-1$ and first-hitting animal $k$ — long if the walk had to leave a depleted cluster and cross a bridge, short if the next animal was right next door. (We’re being deliberately loose about units here: a walk-step and a letter-emission are both counted as one abstract “tick” of time, so the two terms can simply add. The point is the shape of the curve, not real milliseconds.) For our example,
$$\text{IRT}(\text{cat}) = \tau(\text{cat}) - \tau(\text{dog}) + L(\text{cat}) = 5 - 2 + 3 = 6.$$That is the whole link from the hidden walk to the observable data: wander-time between first-hits, plus word length. Hold onto the first term — it is where the famous result comes from. (One reassurance for when you do the exercises: only the difference $\tau(k) - \tau(k-1)$ ever enters, so it doesn’t matter whether you number the walk’s steps starting from 0 or from 1 — the origin washes out.)
The Signature: Slow Down, Then Switch
Here is the phenomenon the model has to explain. In the foraging language we’re about to meet, a cluster is called a patch (a “patch” of related animals, like a patch of berries). Hills, Jones and Todd (2012) lined up each animal a person produced by its position relative to a patch switch — position 1 being the first animal of a new patch (the moment you’ve just switched clusters), position 2 the second, and so on — and averaged the IRTs. The result (their Figure 1a) is striking and consistent:
- The first word of a new patch (position 1) is the slowest of all — its IRT sits above the person’s overall average.
- The second word (position 2) is the fastest — once you’re inside a fresh cluster, the next item tumbles out.
Hills et al. read this as evidence of optimal foraging: people treat memory like a patchy food environment, deliberately deciding to leave a depleted patch and pay a “switch cost” to find a new one. The rule for when to leave comes from the marginal value theorem of foraging ecology (Charnov, 1976): a forager should abandon its current patch the moment the patch’s return rate drops to the average return rate of the whole environment. Applied to the mind, you leave a cluster when relevant words stop coming faster than your overall pace. That account is elegant, but it needs two processes: one to explore within a patch, and a separate strategic decision (governed by the marginal value theorem) to switch.
Two processes, or one?
The optimal-foraging account posits clustering and switching as separate mechanisms, with a rational decision-rule choosing when to switch. The random-walk account posits one mechanism — a memoryless walk — and claims the “switch cost” falls out for free. Same data; the contest is about how many moving parts a mind needs. This is a recurring theme in cognitive science: the simpler model wins if it explains the data, because it assumes less.
…and the Random Walk Reproduces It
This is the payoff. Run the censored random walk — one memoryless process, with no switch rule anywhere in it — and compute the IRT-by-patch-position curve. It comes out with the same shape as the human data: position 1 slowest (above average), position 2 fastest.
Why does position 1 lag? Look back at the IRT formula. The first animal of a new patch is the one the walk reaches right after leaving a depleted cluster — it had to wander out of the old triangle, cross the bridge, and find the first new animal. That is a long $\tau(k) - \tau(k-1)$, hence a long IRT. The second animal of the patch is then sitting right next door (the walk is now inside the fresh, dense cluster), so its wander-time is tiny. The “switch cost” is not a decision — it is just the bridge-crossing time, and it emerges from the network’s structure alone.
So the deliberate, two-process forager and the mindless, one-process walker produce the same behavioural signature. The random walk gives the simpler, unified account: one process, not two. That is the headline of Abbott, Austerweil and Griffiths (2012).
GenJAX and JAX Implementation
We build a small semantic network with two animal clusters (pets and big animals) joined by a bridge, plus a few non-animal “distractor” nodes the walk can wander through. Then we sample many censored random walks, apply the censoring function, compute IRTs, and check that the position-1-slowest signature emerges — with no switch rule in the code.
The network
| |
Output:
network: 11 nodes, 15 edgesSample many walks (GenJAX-style, batched)
The walk is the same Markov chain as before. We sample one fixed-length walk with jax.lax.scan and vmap over many random keys so all the walks run at once.
| |
Output:
sampled 500 walks of 400 steps eachCensor, compute IRTs, and find the signature
The censoring function and the patch-position bookkeeping are plain Python — the interesting part is conceptual, not numerical. For each walk we keep each animal’s first visit, compute its IRT from the formula, and label it by its position within its patch (position 1 = first animal of a new patch). One bookkeeping choice worth stating: a “switch” means moving directly from a pets animal to a big-animals one (or vice versa); the bridge animal tiger is treated as in transit — it doesn’t count as starting a new patch. (This isn’t a thumb on the scale — the bridge is genuinely between clusters, belonging to neither, so it’s the crossing, not the destination. The signature below is just as strong if you assign tiger to one side or drop it; we keep it explicit so the labelling matches the network’s structure.)
| |
Output:
average IRT over all positions: 11.4
patch position 1: IRT / average = 1.69
patch position 2: IRT / average = 0.78
patch position 3: IRT / average = 0.82There it is. Patch position 1 sits well above the average, while positions 2 and 3 stay comfortably below it — the same shape as the human data from Hills et al. (2012): a slow first word, then fast ones, exactly as in their Figure 1a. (The precise ratios wobble from seed to seed — that’s why the validator allows a wide tolerance — so read the result as a reliable inequality: position 1 lands well above 1, positions 2–3 well below, every run. The two decimals are one sample, not a constant.) And this is reproduced by a memoryless random walk with a censoring function and no switch rule anywhere in the code. The “decision to switch” was never needed; the slow first word is just the time the walk spent crossing the bridge between clusters.
What you can do now
You can state the random-walk model of memory search, apply the censoring function (report each animal only on its first visit) to turn a latent walk into an observable list, compute inter-item response times from first-hitting times, and explain why the first word of a new patch is slowest without any switch rule — the “switch cost” is just bridge-crossing time. You’ve seen one memoryless process reproduce a signature that was taken as evidence for a deliberate, two-process forager: a concrete case of a simpler model explaining the same data.
Glossary: censoring function, semantic network, random walk.
Inverting the Walk: Estimating the Network from Behaviour
So far we have run the model forward: network → walk → censored fluency list. The deeper prize is to run it backward — given someone’s fluency lists, recover the network (or its structure) that produced them. That turns the model into a measurement instrument: estimate a person’s semantic organization from nothing but the animals they named, then compare people or groups.
There are two ways to attempt this inversion, and the contrast between them is instructive.
Why this is hard: the censoring stands in the way
The natural first thought is: write the censored walk as a generative @gen model and just condition on the observed list, the way we conditioned Bayes nets in Chapters 8–10. The forward model is easy and clean — it is exactly the walk we have been sampling. But conditioning is not easy, and the reason is the censoring function itself.
A Bayes net lets you condition on a variable because that variable is an addressable random choice. The fluency list is different: it is a deterministic function of the latent walk, with the walk’s path marginalized away. Many different paths — wandering through different non-animals, revisiting in different orders — produce the same reported list. To score how likely a network makes the observed list, you must sum over all those hidden paths. Generic conditioning (importance sampling on the raw choices) can’t do that: ask GenJAX to match the censored list directly and almost every sampled path disagrees somewhere, so the weights collapse to zero. The probability is real, but it is locked behind a sum over exponentially many paths.
This is exactly why the published estimator, U-INVITE (Zemla & Austerweil, 2018), is not a one-liner. It computes the censored-walk likelihood analytically, using the fundamental matrix of an absorbing Markov chain: it treats already-reported animals as absorbing states and the rest as transient, computes the expected first-passage probabilities, and — crucially — rebuilds that absorbing/transient split after every reported animal (each newly named animal moves from transient to absorbing). That bookkeeping is what correctly marginalizes the hidden path. It is powerful and exact, and it is also a lot of machinery.
A simpler sketch: simulation-based inference on cluster structure
If we don’t need the full network — only a coarse feature of it — we can sidestep the analytic likelihood entirely and let simulation do the work. Suppose we believe semantic memory is organized into $K$ known clusters (here $K = 3$), each fully connected internally, with a high within-cluster transition probability and a low between-cluster one. The single number that matters is the contrast $r = p_\text{out} / p_\text{in}$: small $r$ means tight, well-separated clusters; $r$ near 1 means no real cluster structure at all.
We can’t write down the censored likelihood, but we can simulate it — so we use simulation-based (likelihood-free) inference: for each candidate $r$, generate many fluency lists, measure a summary statistic, and keep the $r$ values whose simulated lists look like the observed one. A natural statistic is the clustering score: the fraction of consecutive reported animals that fall in the same cluster (high when the walk lingers in patches, low when it hops around).
| |
Now the inference. We generate “observed” data from a strong-cluster network ($r = 0.1$) and a weak-cluster one ($r = 0.7$), then run a simple ABC (approximate Bayesian computation) posterior over $r$ for each — weighting candidate $r$ values by how close their simulated clustering score is to the observed one.
| |
Output:
strong-cluster data: clustering score 0.55
weak-cluster data: clustering score 0.19
posterior over r (grid 0.1, 0.2, 0.4, 0.7, 1.0):
strong data -> [0.55 0.43 0.01 0. 0. ] MAP r = 0.1
weak data -> [0. 0. 0. 0.26 0.74] MAP r = 1.0The inference cleanly separates the two regimes: strong-cluster data concentrates the posterior on small $r$ (tight clusters — here the most likely $r$ is the true $0.1$), while weak-cluster data pushes all the mass to large $r$ (no real structure). With nothing but the censored lists, we recovered a real fact about the network that produced them.
What this sketch does and doesn’t do
This recovers the cluster contrast — strong vs. weak structure — reliably, and on this clean toy it even lands the right $r$. But it is a coarse tool, not a full estimator: it compresses an entire fluency list down to a single summary statistic (the clustering score), so it can speak to “how clustered” but not to which animals link to which, or how many clusters there are, or where the bridges sit. It also assumes $K$ is known and the blocks are clean and equal-sized. Recovering the whole network — every edge — is exactly what the analytic U-INVITE likelihood buys you over this simulation-based shortcut, at the cost of the fundamental-matrix machinery above. The lesson is the trade-off itself: a generative model is trivial to write and simulate but can be hard to condition on, and when censoring blocks direct conditioning you can still learn coarse structure by simulating instead of solving.
A digression: where this sketch sits, and a project for someone
The simulation-based sketch above is deliberately a toy, but it is worth saying precisely how it relates to the real methods literature — because it occupies a corner that the published estimators do not.
Zemla & Austerweil (2018) benchmark seven ways to turn fluency lists into a semantic network. Five are heuristics that assume “things named near each other are probably linked” — First Edge, Naïve Random Walk (and its thresholded variants), the Community Network, Pathfinder, and the Correlation-Based Network. The other two — U-INVITE and its hierarchical version — are process-model estimators: they invert the very censored random walk this chapter is built on, and U-INVITE is a consistent estimator (given enough data it converges on the true network). Every one of the seven estimates the full edge set — which of the $\binom{N}{2}$ possible links exist.
Our sketch is not a re-derivation of any of them. It shares U-INVITE’s premise — the censored random walk as the generating process — but inverts it the opposite way. U-INVITE writes the censored-walk likelihood down exactly (the fundamental matrix) and searches the enormous space of possible edge sets. Our sketch concedes that the likelihood is intractable to condition on directly, and instead does likelihood-free (simulation-based) inference on a low-dimensional description of the network — here a single block-structure parameter, $r$. So it answers a different, coarser question (“how modular is this memory?”) than “which edges exist?”, and it answers it by simulating rather than solving.
That corner — sampling-based inference of network structure from a censored walk — is exactly the one Zemla & Austerweil flag as unexplored: their search is a deterministic edge-toggling hill-climb, and they note that approximating the posterior by sampling (e.g. Gibbs) is left for future work. A genuine follow-up project lives here, and it is tractable:
An open project (if you’re looking for one)
Take the simulation-based idea off the toy and onto real data. Concretely:
- Scale to a real network. Use the USF free-association animal network (the same one U-INVITE is validated against) instead of nine synthetic nodes, with cluster labels from an existing animal taxonomy (e.g. Troyer’s subcategories, already used by Abbott et al. 2012).
- Drop the crutches. The sketch assumes $K$ is known and the blocks are clean and equal-sized. Infer $K$ too — a stochastic block model with a prior over the number of communities (a Chinese-restaurant-style prior, of the kind that powers the infinite mixtures of Chapter 6) — so the method discovers how many clusters memory has, not just how separated two given ones are.
- Ask the estimator’s questions. Is the block-model contrast estimate consistent and stable as you add more lists, the way U-INVITE is — or does it degrade like the heuristic methods? Does it recover community structure that matches U-INVITE’s full-network estimate on the same lists, at a fraction of the compute?
If it works, it is a complement to U-INVITE, not a competitor: U-INVITE for the whole graph, exact but expensive; simulation-based block inference for the coarse community structure, cheap and willing to say “I don’t know the edges.” If it doesn’t work, the reason will be instructive — a single summary statistic may simply throw away too much of the list. Either way it is a real, self-contained question that this chapter’s machinery is enough to start on.
Where This Goes Next
The model opens two doors worth naming, both active research:
Beyond this chapter
The clinical payoff. The inversion above is not just a curiosity. Run the full U-INVITE estimator on real fluency lists and the recovered network becomes a diagnostic: Zemla & Austerweil (2019) estimated networks from Alzheimer’s patients versus healthy controls and found structural differences (fewer associations per concept, more spurious links, less organization) — a clinical signature read straight off the words people name.
The toolkit. You don’t have to implement any of this from scratch. SNAFU — the Semantic Network and Fluency Utility — is an open-source Python package that automates fluency analysis (cluster sizes, switches, intrusions, perseverations) and implements U-INVITE and the other network estimators side by side. It’s on GitHub at github.com/AusterweilLab/snafu-py (pip install git+https://github.com/AusterweilLab/snafu-py), and the accompanying paper is Zemla, Cao, Mueller & Austerweil (2020), SNAFU: The Semantic Network and Fluency Utility, Behavior Research Methods 52(4), 1681–1699 (doi:10.3758/s13428-019-01343-w).
Sampling on purpose. Throughout these three chapters we have run a chain and watched where it settles — using a Markov chain to estimate a distribution. That is Monte Carlo, and it is the subject of the next part of the course. Chapter 16 starts there: estimate an expectation — or a whole posterior — by sampling and averaging. Then Chapter 18 supplies the twist that brings the chain back: instead of being handed a chain and finding its stationary distribution, we start from a distribution we want to sample (a Bayesian posterior) and design a chain whose stationary distribution is that target — Markov chain Monte Carlo (MCMC). The walk you just used to model memory is the same tool, pointed the other way.
Exercises
Try it yourself
- Trace the censoring by hand. A walk visits
animal → lion → grass → lion → zebra → zebra → giraffe. Which words are reported? What are $\tau(1), \tau(2), \tau(3)$? Compute $\text{IRT}$ for the second and third reported animals (use word lengths lion 4, zebra 5, giraffe 7). - Kill the bridge. In the code, delete the two bridge edges (
cat–tiger,tiger–lion) so the two clusters are disconnected. Re-run. What happens to the walks — can a single walk now report animals from both clusters? What does that do to the position-1 signature, and why? - Widen the gap. Add more distractor nodes between the two animal clusters (a longer bridge path). Predict, then check: does the position-1 IRT ratio go up or down? Relate your answer to the $\tau(k) - \tau(k-1)$ term in the IRT formula.
A companion notebook works through all of this interactively:
📓 Open in Colab: 15_memory_search.ipynb
References
- Austerweil, J. L., Abbott, J. T., & Griffiths, T. L. (2012). Human memory search as a random walk in a semantic network. In Advances in Neural Information Processing Systems, 25. https://proceedings.neurips.cc/paper/2012/hash/14d9e8007c9b41f57891c48e07c23f57-Abstract.html
- Bousfield, W. A., & Sedgewick, C. H. W. (1944). An analysis of sequences of restricted associative responses. The Journal of General Psychology, 30(2), 149–165. https://doi.org/10.1080/00221309.1944.10544467
- Charnov, E. L. (1976). Optimal foraging, the marginal value theorem. Theoretical Population Biology, 9(2), 129–136. https://doi.org/10.1016/0040-5809(76)90040-X
- Hills, T. T., Jones, M. N., & Todd, P. M. (2012). Optimal foraging in semantic memory. Psychological Review, 119(2), 431–440. https://doi.org/10.1037/a0027373
- Troyer, A. K., Moscovitch, M., & Winocur, G. (1997). Clustering and switching as two components of verbal fluency: Evidence from younger and older healthy adults. Neuropsychology, 11(1), 138–146. https://doi.org/10.1037/0894-4105.11.1.138
- Zemla, J. C., & Austerweil, J. L. (2018). Estimating semantic networks of groups and individuals from fluency data. Computational Brain & Behavior, 1(1), 36–58. https://doi.org/10.1007/s42113-018-0003-7
- Zemla, J. C., & Austerweil, J. L. (2019). Analyzing knowledge retrieval impairments associated with Alzheimer’s disease using network analyses. Complexity, 2019, 4203158. https://doi.org/10.1155/2019/4203158
- Zemla, J. C., Cao, K., Mueller, K. D., & Austerweil, J. L. (2020). SNAFU: The Semantic Network and Fluency Utility. Behavior Research Methods, 52(4), 1681–1699. https://doi.org/10.3758/s13428-019-01343-w
Special thanks to JPPCA for their generous support of this tutorial series.