# Memoization

Caching function results by their arguments so repeated calls return immediately, turning exponential recursion into polynomial work.

**Rests on:** Recursive Thinking

**Leads to:** Dynamic Programming, Space-Time Tradeoffs

*Machine Learning · Algorithms and Complexity*


## Why learn this

Imagine you are working on a complex report and realize you have already calculated the same set of numbers three times in different sections. You could spend another hour re-doing the work, or you could look up your previous notes and finish in minutes. Memoization is that act of looking up your notes so you never repeat an expensive calculation. It turns tasks that would take centuries to complete into ones that finish in milliseconds by remembering past results.


## The intuition

Memoization is the idea of remembering the answers to questions you've already answered, so you don't have to compute them again. Imagine you're a student solving a worksheet of arithmetic problems. Some problems are repeated. If you solve the same problem twice, you waste time. Instead, you keep a small notebook: every time you solve a problem, you write down the problem and its answer. The next time you see it, you just look it up, without doing the arithmetic again. Memoization is exactly that, but for functions in a program. When a function is called with the same arguments a second time, instead of recomputing the result from scratch, the program looks it up in a cache—a temporary storage area. This only works if the function is 'pure'—that is, the same input always gives the same output, and calling it doesn't change anything else in the world. If a function isn't pure, the cache would return stale or wrong answers. Memoization is a way to trade a little extra memory for a lot less time—a classic space-time tradeoff.


## An analogy

Think of a chef preparing a large meal. The recipe has many steps, and some steps are reused. For example, the chef needs to make a stock that is used in three different dishes. Instead of making the stock three times, the chef makes it once, stores it in a container, and then uses it from the container each time. The stock is the result of a function (make_stock) with no arguments. But imagine the stock recipe depends on the type of stock (chicken, vegetable, beef). If the chef is making both a chicken soup and a chicken sauce, both need chicken stock. The chef can make chicken stock once, label the container 'chicken stock', and reuse it. The label is the cache key; the container is the cache. The chef would not make it again unless it was needed for a different kind. This analogy holds until we consider that the stock might spoil—in a program, the cache doesn't spoil. But it can grow too large, so we might need to evict old entries, just like a chef might discard old stock to make room in the fridge. That's the eviction policy part of memoization.


## Definition

Memoization is a technique where a function's results are stored in a cache keyed by its arguments, so that repeated calls with the same arguments return the stored result immediately instead of recomputing it.


## How it connects

Memoization is a specific way to implement dynamic programming, which is a method for solving complex problems by breaking them into smaller, overlapping sub-problems. It is also a direct application of the space-time tradeoff you will study: you spend memory on a cache to save computation time.


## The mathematics

Memoization rests on the branch of mathematics known as computational complexity, which measures how the work required by an algorithm grows as the input size grows. The key mathematical idea is the concept of a 'function' — a rule that takes an input and always returns the same output. In memoization, we exploit a property called 'referential transparency': if a function is pure, we can replace a call to it with its stored result without changing the program's behavior. The mathematics of memoization is mainly about counting how many times a function is called. For a recursive function like the Fibonacci sequence, the number of calls explodes exponentially because the same subproblems are solved again and again. Memoization ensures that each distinct subproblem is solved only once, turning the exponential call tree into a linear one. This is the mathematics of overlapping subproblems: when a problem is decomposed into smaller subproblems that are reused, memoization reduces the total work to the number of distinct subproblems, times the cost of computing each from its own subproblems.

The general idea: define a function f with arguments (a, b, c, ...). Let cache be a dictionary mapping the argument tuple to the result. The memoized version checks if the argument tuple is in the cache; if so, return the stored value; otherwise, compute the result, store it, and return it. Mathematically, for a recursive function f, let T(n) be the time to compute f(n). Without memoization, T(n) can be exponential. With memoization, T(n) = O(number of distinct subproblems × cost per subproblem). For Fibonacci, this is O(n).


## A worked example

```
Consider the Fibonacci sequence: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) for n≥2. We want to compute F(5). We'll do it by hand, first without memoization, then with memoization, to see the difference.

Step 1: F(5) = F(4) + F(3)   # To compute F(5), we need F(4) and F(3).
Step 2: F(4) = F(3) + F(2)   # To compute F(4), we need F(3) and F(2). But F(3) is already needed above, so without memoization we recompute it.
Step 3: F(3) = F(2) + F(1)   # Again, F(2) appears multiple times.
Step 4: F(2) = F(1) + F(0) = 1 + 0 = 1   # Now we hit base cases.
Step 5: F(3) = F(2) + F(1) = 1 + 1 = 2   # Now we can compute F(3), but we already computed F(2) earlier, so we recompute it here.
Step 6: F(4) = F(3) + F(2) = 2 + 1 = 3   # Again, F(3) and F(2) are recomputed.
Step 7: F(5) = F(4) + F(3) = 3 + 2 = 5   # Final result.

Result: Without memoization, we made 8 calls to F (for n=5). With memoization, we would make only 5 calls (one for each n from 0 to 5), because each result is stored and reused.
```


## From scratch, in Python

```python
def fib_memo(n):
    cache = {0: 0, 1: 1}  # base cases

    def helper(k):
        if k in cache:
            return cache[k]
        # compute and store
        cache[k] = helper(k-1) + helper(k-2)
        return cache[k]

    return helper(n)

# Example usage
print(fib_memo(5))  # 5
print(fib_memo(10)) # 55
```


## What the code does

This code defines a function `fib_memo` that computes the nth Fibonacci number using memoization. First, we create a dictionary `cache` with the base cases: 0 maps to 0, 1 maps to 1. Then we define an inner function `helper` that takes an integer `k`. Inside `helper`, we first check `if k in cache:` — this is a dictionary lookup that tells us whether we've already computed the result for this `k`. If yes, we return it immediately, skipping all recalculation. If not, we compute it recursively: `helper(k-1) + helper(k-2)`. After computing, we store it in `cache` with `cache[k] = ...`. This means future calls for the same `k` will hit the cache. Finally, we call `helper(n)` from the outer function. Without the cache, `fib(5)` would expand into a tree of 15 calls; with the cache, each `k` from 0 to n is computed exactly once. The dictionary `cache` is the memoization table. Underneath, a dictionary is a hash table: it stores key-value pairs and can look up a key in constant time on average. So checking `k in cache` is fast.


## Common misconceptions

**Memoization is the same as caching** — Caching and memoization are basically the same thing, right?

Caching is a general term for storing data to speed up future access. Memoization is a specific kind of caching applied to pure functions, keyed by their arguments. In fact: Memoization is caching for pure functions: the key is the argument, and the value is the function's return value.

**Memoization works for any function** — I can memoize any function that takes a long time, like a function that reads from the network.

If the function has side effects (like sending a request or modifying a global variable), or its output depends on external state (like time), the cached result may be wrong or the side effect might be missed. In fact: Only pure functions — same input always same output, no side effects — can be safely memoized.

**Memoization always speeds things up** — Adding memoization will always make my program faster.

Memoization uses memory and has overhead for the lookup. For a function that is called each time with different arguments, the cache will miss every time and only add overhead. In fact: Memoization helps when the same arguments are called repeatedly. If arguments are unique each time, it may slow the program down.

**Memoization and dynamic programming are the same** — Memoization is just another name for dynamic programming.

Dynamic programming is the broader technique of solving problems by combining solutions to overlapping subproblems, and it can be implemented two ways: top-down (which uses memoization) or bottom-up (which uses a table filled iteratively). In fact: Memoization is the top-down implementation of dynamic programming. The bottom-up version is called tabulation.

**Memoization only works for recursive functions** — Memoization is only useful for recursive functions, because it's about recursion.

Any pure function can be memoized, whether it is recursive or not. For example, a function that computes a feature vector from a raw image can be memoized if called with the same image multiple times. In fact: Memoization can speed up any repeated pure function call, not just recursive ones.


## In short

Memoization caches the results of a pure function by its arguments, so repeated calls return instantly. It turns exponential recursion into polynomial time by ensuring each subproblem is computed once. The practical concerns are cache key design and eviction policy, and it only works for pure functions without side effects. It is the top-down implementation of dynamic programming.


## Where this is used

Memoization is used everywhere in AI systems. In large language models, inference can be slow because generating each token requires computing attention over all previous tokens. Some systems use memoization to cache the key and value tensors from the attention mechanism (the KV cache) so that when generating a new token, they don't recompute the representations of already-processed tokens — that's a form of memoization keyed on token position. In small language models running on phones, memory and compute are scarce; memoization helps by caching embeddings or intermediate features so that repeated prompts from the same session don't recompute them. In retrieval-augmented generation, the embedding vectors of documents are often cached: when the same query is asked again, the system doesn't need to recompute the similarity between the query and every document — it can use the cached results or the precomputed document embeddings. In agentic systems that plan and call tools, an agent might call the same tool with the same arguments multiple times — for example, fetching the weather for a city. Memoization prevents redundant external API calls, saving money and time. In everyday applied machine learning, memoization is used in feature engineering: when creating features from raw data, repeatedly computing the same feature (like a rolling average) can be memoized. Also, in hyperparameter tuning, the same evaluation result may be requested multiple times; caching it avoids retraining models. A developer writing Python might use `functools.lru_cache` (a built-in decorator) to memoize a function automatically. Underneath, `lru_cache` stores results in a dictionary and evicts the least-recently-used entries when the cache reaches a size limit. If memoization is done badly — for example, caching a function that reads from a file that changes — stale results are returned. If the cache grows unboundedly, it can exhaust memory. The two practical concerns are cache key design (what identifies a unique computation) and eviction policy (how to forget old entries).


---

Read this on the web: https://basavapurushottam.com/learn-ai/memoization
