Is precomputation the same as caching?

They overlap. Precomputation prepares results ahead of demand; caching can also retain results after requests first produce them.

Must every possible input be covered?

No. A table can cover selected inputs, with a defined fallback for others.

Does it always improve speed?

No. The benefit depends on preparation cost, lookup cost, reuse and updates.

AI Glossary / Graphs and symbolic AI / Advanced

Precomputation

Definition

Precomputation means calculating information before the moment it is needed, then storing it for later reuse. In heuristic search, it can supply previously calculated path costs or lower bounds instead of deriving them repeatedly during search. The technique exchanges preparation time and storage for potentially faster subsequent work. Its usefulness depends on reuse and on whether the stored information remains valid.

What it means

A system answering many related questions may repeat the same expensive intermediate calculation. Precomputation moves that calculation into an earlier preparation stage. A route service, for example, might calculate distances to a fixed destination before individual requests arrive. The later request retrieves a stored value. This does not mean the whole computation disappears: its cost has moved, and the system must manage preparation, storage, lookup and changes to the underlying problem.

How it works

Identify values that can be shared across later operations, choose a representation and compute them under a defined set of assumptions. Store enough identifying information to match each lookup to the correct input, goal, rules and version. At use time, retrieve the value and apply it for its intended purpose.
In search, a pattern database stores exact costs for an abstraction or subproblem. When the abstraction is a suitable relaxation, those costs provide lower bounds for the original problem. A stored value may therefore be exact for the abstract problem without being the original problem's exact answer. Full-state distance tables are another possibility. Building either table requires appropriate treatment of transition directions and costs; storage alone does not establish correctness.

Three practical examples

A puzzle solver precomputes the moves required to solve selected pieces. During a larger search, it consults the corresponding pattern entry as a heuristic lower bound.
A fixed-map planning service stores costs to a frequently requested destination. It tracks the map and cost version so later queries do not silently use information from a different network.
An analytics service stores a calculated summary as a materialized view. Queries can read the summary quickly, while a refresh policy determines how current the stored result is. This illustrates the same preparation-and-reuse idea outside heuristic search.

Think of it this way

Imagine preparing a reference table before a busy service desk opens. Looking up common answers may be quicker than recalculating each one while a customer waits. The table still takes effort to prepare, may contain entries nobody requests, and needs revision when the underlying rules change.

Worked example

Consider a directed graph with nodes A, B, C and goal G. Its only edges and costs are A to B: 2; A to C: 5; B to C: 1; B to G: 6; and C to G: 2. All costs are nonnegative.
Precompute each node's minimum remaining cost to G. Store G = 0. From C, the cost is 2. From B, compare the direct cost 6 with going through C at 1 + 2 = 3, so store B = 3. From A, compare going through B at 2 + 3 = 5 with going through C at 5 + 2 = 7, so store A = 5.
Later queries can retrieve these values. The optimal route from A is A-B-C-G, costing 5. This tiny example uses exact full-graph distances, rather than abstract pattern-database estimates.
Now increase C-to-G's cost from 2 to 10. The new distances are C = 10, B = 6 and A = 8. The old A-B-C-G route now costs 13, while A-B-G costs 8. The old table is no longer an exact answer. Because this change only increases an edge cost, its old values still do not exceed the new optimal costs, so they remain lower bounds for this changed graph.
In a separate variation of the original graph, add A-to-G with cost 1. The old value A = 5 now overestimates the true remaining cost of 1. It cannot be treated as an admissible heuristic there. Different changes can invalidate different guarantees.

Illustrative case study

In a fictional route-planning project, analysts assume that building a table takes 120 milliseconds, calculating each answer afresh takes 8 milliseconds, and a lookup takes 0.2 milliseconds. These are illustrative timings, not measurements from the four-node graph.
For N queries, fresh computation costs 8N milliseconds, while preparation plus lookups costs 120 + 0.2N. Precomputation wins when 7.8N exceeds 120, so the first whole-number query count is 16. With 10 queries, the totals are 80 versus 122 milliseconds; with 100, they are 800 versus 140.
The team then measures its actual workload and includes rebuild frequency, memory use and loading time. Frequent map changes may erase the assumed advantage. The calculation provides a testable decision framework rather than a universal speedup claim.

Common misconceptions and mistakes

Precomputation is not automatically an approximation: it may store exact results. Conversely, an exact result for an abstraction is not necessarily exact for the original problem. Faster lookup does not imply lower total cost once preparation and maintenance are counted.
A common failure is treating a stale table as valid for every purpose. The edge-cost examples show why exact answers and lower-bound guarantees must be checked separately. Another mistake is adding several precomputed heuristic estimates without justification; shared costs can be counted twice. Taking their maximum preserves admissibility when each estimate is individually admissible.

Business use

Precomputation is useful to evaluate when similar queries recur and the relevant inputs remain stable long enough for preparation to pay off. Specify what is stored, its validity conditions and how changes trigger rebuilding or invalidation. Measure complete lifecycle cost alongside response latency. Distinguish a result that is unavailable from a legitimately stored zero. For the graph example, zero belongs to the goal; using zero as an undocumented missing-entry marker would blur two different situations.

Check your understanding

What is A's original stored distance?

Answer: Five.

After increasing C-to-G to 10, is that value still exact?

Answer: No; the new distance is 8.

Why is adding A-to-G at cost 1 different?

Answer: It makes the old value 5 an overestimate, invalidating its lower-bound role.

Related terms

Heuristic search
Admissible heuristic
Memoization
Materialized view
Preprocessing
Pattern database
lookup table
caching
space-time trade-off

Learn next

Recalculate the preparation example if the table must be rebuilt after every 12 queries. Then distinguish exact-answer freshness from whether an older value remains a valid search bound.

Sources

Korf, Analyzing the Performance of Pattern Database Heuristics: https://cdn.aaai.org/AAAI/2007/AAAI07-185.pdf PostgreSQL, materialized views: https://www.postgresql.org/docs/current/rules-materializedviews.html AIMA glossary, precomputation: https://github.com/aimacode/aima-glossary/blob/master/glossary.md

Previous: Precision-recall curve Next: Precomputed Features