Does memoization always make a program faster?

No. Unique or cheap requests can incur lookup and storage overhead without enough reuse to compensate.

Is recursion required?

No. Any suitable repeatedly called computation can be memoized, although recursive examples make overlapping work easy to see.

Can cached answers be removed?

Yes. Eviction or invalidation can remove them, causing later requests to recompute the result when necessary.

AI Glossary / Graphs and symbolic AI / Beginner

Memoization

Definition

Memoization is an optimization that stores a function's previously computed results and reuses them when the same relevant inputs occur again. It can avoid repeated work, particularly in recursive algorithms with overlapping subproblems. The stored result must remain valid for the inputs and context represented by its cache key.

What it means

Suppose a planner repeatedly asks for the cost of solving the same subproblem. Without memoization, it may redo an expensive calculation every time. With memoization, the first request computes and stores the answer; later matching requests look it up.

The technique changes how work is performed, not what the function is intended to mean. It is most straightforward for deterministic functions whose outputs depend only on their explicit inputs. If the answer also depends on a changing database, model version, permission scope, or current time, that dependency must be handled before reusing a result safely.

How it works

Construct a cache key from the relevant input values. Before evaluating the function, look for that key. A hit returns the stored result. A miss runs the calculation and stores the result for future use.

The cache may grow without a size limit or evict entries according to a policy such as least recently used. Eviction changes how much work is repeated, but should not change a correctly implemented function's answers. In recursive memoization, calls for smaller subproblems must pass through the memoized function to benefit from stored results.

Memoization is a form of caching and is closely associated with top-down dynamic programming. Bottom-up dynamic programming instead computes a planned table of subproblem answers. Either approach requires a correct definition of the subproblem state.

Three practical examples

Parsing: reuse the result of analyzing a particular grammar rule at a particular position in an unchanged input sequence.
Planning: avoid solving an identical, fully specified subproblem reached through different branches of a search.
Feature processing: reuse a deterministic transformation for the same source content and transformation version when that input repeats.

Think of it this way

Think of writing a solved calculation in a notebook indexed by its exact question. When the identical question returns, you read the answer instead of solving it again.

The analogy fails if the question leaves out information that changes the answer. “What is the delivery cost?” is not an adequate index if destination, package size, service level, or the pricing version is missing. A fast lookup can be consistently wrong when its key is incomplete.

Worked example

Let W(n) count the ordered ways to climb n steps when each move climbs either one or two steps. Define W(0)=1 and W(1)=1. For n≥2, W(n)=W(n−1)+W(n−2), because the final move has one of those two sizes.

The values are W(2)=2, W(3)=3, W(4)=5, and W(5)=8. A naive recursive evaluation of W(5) repeatedly evaluates smaller inputs. If each invocation counts once, including base cases, the call counts satisfy T(0)=T(1)=1 and T(n)=1+T(n−1)+T(n−2). This gives T(2)=3, T(3)=5, T(4)=9, and T(5)=15.

With an initially empty, unbounded memoization cache, each function body for n=0 through 5 is evaluated once: six distinct computations. Requests can still occur more often, but repeats become cache hits. A subsequent request for W(6)=13 needs only one new body evaluation, reusing W(5) and W(4). These are direct recurrence calculations, not measured timing results, and the cache consumes space to store the six or seven answers.

Illustrative case study

Fictional case: a content platform memoizes document-formatting results using only a document identifier. Editors later update the document, but the identifier remains unchanged, so users see an older formatted result.

The team changes the key to include the document revision and formatting configuration. It also limits cache size and measures whether repeated requests justify the storage cost. The fictional case shows that memoization requires a validity model as well as a lookup table. It reports no measured speedup and does not assume that every formatting request repeats often enough to benefit.

Common misconceptions and mistakes

Memoization is not memorization by a machine-learning model. It stores computed results for reuse; it does not learn a general rule from examples. It also does not make an incorrect recurrence or incomplete state representation correct.

Avoid casually memoizing functions whose purpose is a side effect, such as sending a notification. A cache hit could skip the intended action. Mutable return objects can also cause surprises if callers change a cached object. Concurrent callers may duplicate work before the first result is stored, even when the cache's internal data structure is thread-safe.

Business use

The technique can reduce latency and repeated computation when workloads revisit the same inputs. Its value depends on the cost of calculation, frequency of reuse, lookup overhead, memory footprint, and how quickly results become stale.

Measure hit rates and end-to-end performance under realistic requests. Define the cache key, ownership, size policy, and invalidation behavior explicitly. For AI pipelines, include model and preprocessing versions when they affect the answer. Do not assume that two prompts that look similar are interchangeable: exact-result reuse and approximate semantic caching are different designs with different correctness requirements.

Check your understanding

a cached model prediction is keyed only by input text, and the model is then updated. Is the old cached result necessarily valid?

Answer: no. Model version affects the computation. Include it in the key or invalidate the relevant cache when updating, according to the intended reuse policy.

Related terms

Dynamic programming
Pure function
Caching
cache key
cache hit
cache miss
overlapping subproblems
invalidation
least recently used cache

Learn next

trace the repeated subproblems in the worked recurrence and compare memoized recursion with a bottom-up table. Then examine a function that reads changing external data and list every dependency its cache policy must address. Measure reuse before adopting memoization for a production workload.

Sources

Python documentation, functools.cache and functools.lru_cache: https://docs.python.org/3/library/functools.html. Primary documentation on memoizing wrappers, cache information, invalidation, side effects, and concurrency was read. The staircase call counts and document-revision case are original, directly reasoned examples; no runtime benchmark is claimed.

Previous: Membrane Next: Memory coherence