Marr's Three Levels

David Marr studied vision, and his lasting idea was not about eyes. He argued that a system that processes information is only understood once you can describe it at three separate levels: what it computes and why, how it computes it, and what physically does the work. I use the framing for thinking about systems of all kinds. It is most useful when a discussion goes in circles, because the two sides are often answering questions at different levels.

The idea

The computational level says what problem the system solves and why that is the right problem. It describes a mapping from inputs to outputs and the constraints that make it sensible, without saying anything about steps.

The algorithmic level says how. It picks a representation for the inputs and outputs, and a procedure that turns one into the other.

The implementation level says with what: the physical stuff that runs the procedure, whether that is neurons, transistors, a browser's JavaScript engine or a rack of GPUs.

Marr's own example was a cash register. What it computes is addition, and the properties of addition explain why the order you ring up items cannot change the total. How it adds could be decimal digits with carrying, or binary. What it adds with could be gears or a chip. Each level can change without the others: one computation has many algorithms, and one algorithm has many implementations.

That looseness is the point. Knowing every transistor in a chip would not tell you it is adding, and knowing it adds would not tell you whether it carries in base ten. Marr made the argument against studying vision only through neurons, but it fits machine learning just as well. A loss function and a target sit at the computational level. The model class, the features and the optimiser are algorithmic. The hardware, the numerical precision and the libraries are implementation. When someone asks for an explanation of a model, it helps to ask which of the three they want, because the answers are not interchangeable.

The formal core

Marr's levels are a framing rather than a theorem, but each level has a precise object you can write down. The computational level is a function from an input space to an output space. For the widget below it is the median of an odd-length list, the middle order statistic.

f : \mathcal{X} \to \mathcal{Y}, \qquad \operatorname{median}(x_1, \dots, x_n) = x_{\left(\frac{n+1}{2}\right)} \quad \text{for odd } n

The spec has to settle the awkward cases. For an even-length list, which middle? The widget keeps n odd to avoid the question.

The algorithmic level is a procedure $A$ , and the only link to the level above is correctness. Any procedure that returns $f(x)$ on every input counts.

A \text{ is correct for } f \iff A(x) = f(x) \;\; \text{for every } x \in \mathcal{X}

Correct procedures differ in cost. Counting basic steps gives a measure that belongs to the algorithm and its input, not to any machine.

T_{\text{insertion}}(n) = O(n^2), \quad T_{\text{merge}}(n) = O(n \log n), \quad \mathbb{E}\,T_{\text{quickselect}}(n) = O(n), \quad T_{\text{counting}}(n) = O(n + m)

Counting is only available because the values are whole numbers from 0 to 99. A choice of representation opens up an algorithm.

The implementation level turns steps into time, and the conversion is a measurement, not a formula. A rough model has a cost per step $c$ and a fixed overhead $t_0$ , both set by the device, the language runtime and how the data sits in memory.

t_{\text{wall}} \approx c \cdot T_A(n) + t_0

Big-O hides c and t₀. Two algorithms can swap places on a real machine when their constants differ enough.

Try it

The widget finds the median of a seeded list of whole numbers from 0 to 99, four different ways. Use the level switch to read the same table one column at a time.

List size

Order

Seed 1

Read the table at

Algorithmic level. The step counts differ by orders of magnitude for the same answer: Counting needs 1,049 steps, Insertion sort needs 246,802.

Four algorithms on the same 1,001 shuffled values from 0 to 99.
Algorithm	Median	Steps	Time per run
Insertion sortsort, take the middle	47	246,802	not timed
Merge sortsort, take the middle	47	8,714	not timed
Quickselectpartition towards the middle	47	3,290	not timed
Countingtally 0 to 99, walk to half	47	1,049	not timed

Steps are comparisons, or tallies for counting. Bars use a log scale, so each tick of length is a multiple, not a difference.

All four find the median 47 of 1,001 shuffled values. Counting takes the fewest steps (1,049) and Insertion sort the most (246,802). The time column is empty until you time it.

The list is seeded, so the median and every step count are fixed for a given setting. Only the time column comes from your device.

Read at What. Every row reports the same median. At the computational level the four algorithms are one thing.
Read at How with 1,001 shuffled values. Insertion sort makes about 247,000 comparisons, while counting needs about 1,000 tallies.
Switch the order to Sorted. Insertion sort falls to 1,000 comparisons, the fewest of the four, because each new value is already in place. A step count belongs to an algorithm and its input together.
Pick 5,001 shuffled values and time them. Merge sort makes about a hundred times fewer comparisons than insertion sort. Check whether it runs a hundred times faster on your device. It builds new arrays at every level of the recursion, a cost no comparison count sees.
Time the same setting twice. The times shift a little and the step counts never move. Implementation numbers are measurements, algorithm numbers are counts.

Where I used it

Easy to get wrong

Five traps

Treating one level as the real explanation. A full account needs all three, and none can be derived from the others. Marr's complaint was that the computational level was the one most often skipped.
Starting at How before pinning down What. If two algorithms disagree on some input, either one of them is wrong or the spec never said what to return. The median of an even-length list is the classic gap.
Answering at the wrong level. "It runs on eight GPUs" does not explain a prediction, and "the loss is cross-entropy" does not explain why training is slow.
Reading step counts as times. Big-O drops the constants, and memory allocation, caches and the runtime can outweigh a large gap in steps at practical sizes.
Thinking the levels are fixed layers. Where one level ends depends on what you are explaining. The merge step inside merge sort has its own spec, algorithm and implementation.

Sources

VisionMarr, W. H. Freeman, 1982. MIT Press edition, 2010. Chapter 1.The original statement of the three levels, with the cash register example. The first chapter stands on its own.
From Understanding Computation to Understanding Neural CircuitryMarr and Poggio, MIT AI Memo 357, 1976.The earlier memo where the idea of separate levels of understanding first appears, before the book.
The levels of understanding framework, revisedPoggio, Perception 41(9), 2012, pp. 1017–1023.Marr's collaborator revisits the framework decades later and argues that it needs a level for learning.
Marr's three levels: A re-evaluationMcClamrock, Minds and Machines 1, 1991, pp. 185–196.A philosopher's re-examination of the three levels and what each one is really asking.