Is lookup always constant time?

No. It depends on the structure, key processing, and operating conditions. Direct indexing and hashed retrieval have different assumptions.

Can a table change over time?

Yes. Updating entries is possible, but the update policy is separate from the retrieval operation.

Can it represent any finite mapping?

In principle, a complete table can explicitly list a finite mapping. Available memory and construction effort may make that impractical.

AI Glossary / Graphs and symbolic AI / Beginner

Table lookup

Definition

Table lookup is the retrieval of a stored output using an input as a key or index. Instead of deriving the answer from scratch, a system finds the corresponding entry in a prepared table. In AI, tables can store actions, class labels, values, or intermediate results. The method is straightforward for a manageable set of inputs, but a plain exact-match table does not automatically generalize to unseen cases.

What it means

A table represents a mapping: this input corresponds to that output. The table may be designed manually, computed in advance, or populated from observations. Looking up an entry is separate from deciding how that entry was obtained and whether it is correct.

The key must contain the distinctions needed for the task. A current observation may suffice in one application, while another needs an observation history or a state description. If two situations require different outputs but share the same key, no lookup implementation can recover the missing distinction.

How it works

Define the input representation and output type. Construct or load the mapping, then convert each query into a key using the same rules used when building the table. Retrieve the matching value and handle missing entries explicitly.

The implementation might use direct array indexing, hashing, or another search structure. These have different time, memory, and key-processing costs; “lookup” does not imply that every implementation has identical performance.

Determine whether the system permits updates and how it handles inconsistent stored results. If multiple observations give different labels for one key, an aggregation or conflict policy is needed. Approximate matching, interpolation, or a learned fallback can extend the system, but those add behavior beyond a plain exact lookup. Preserve the distinction so that users can tell a stored answer from an inferred one.

Three practical examples

1. Agent actions: a small simulation stores the action associated with each allowed percept history. The action comes from the table rather than a fresh planning calculation.

2. Classification baseline: a system memorizes labels for known feature combinations. Evaluating unseen combinations reveals where memorization alone fails to provide an answer.

3. Precomputed values: an application stores the results of an expensive calculation for a fixed finite input set. A later request retrieves the value, subject to the table's version and input assumptions.

Think of it this way

Think of a directory that pairs an exact reference code with an entry. If the code is present, the directory returns the recorded information. If it is absent, the directory does not invent a new entry from similar-looking codes.

The analogy has limits: a computer table may use complex keys, and some applications add approximate retrieval or computation. Those extensions need their own rules. The basic idea remains retrieving a stored association.

Worked example

Imagine a toy agent receiving one of three observations: A, B, or C. Its action depends on the entire observation history, and the episode lasts at most four observations. Assume every sequence is possible and an action is required after each nonempty history.

There are 3 histories of length one, 9 of length two, 27 of length three, and 81 of length four. A fully specified table therefore needs 3+9+27+81 = 120 entries. If each action code occupies one byte, the action values alone require 120 bytes; keys, indexing, metadata, and storage overhead are additional.

At ten observations, the corresponding count is 3+9+...+59049 = 88,572 entries. This is exponential growth in the maximum history length, even though the observation alphabet contains only three symbols.

Suppose histories AB and CB require different actions. A table keyed only by the latest observation B would merge them and could not satisfy both requirements. Conversely, if a proven sufficient state summary distinguishes everything relevant, a state-keyed table may be much smaller. That improvement depends on a justified representation change, not a faster lookup function.

Illustrative case study

Fictional case: LabelHarbor creates a simple support-routing baseline by storing decisions for known combinations of product code and issue code. It works predictably on those combinations, but a new product produces missing keys.

The team adds an explicit “unmapped” outcome and routes those cases for review. It versions the table and later evaluates a separate generalizing classifier against the same cases. The comparison distinguishes exact coverage from inferred performance. This case illustrates a design decision rather than claiming that a real routing service achieved a particular accuracy.

Common misconceptions and mistakes

A lookup table is not automatically a learned model. Its contents may be manually specified or computed by another method.

Memorizing observed examples does not guarantee correct outputs for new inputs. A fallback that chooses a nearby entry is an additional inference rule, not exact lookup.

Do not measure total memory by value size alone. Keys and indexing can dominate, especially for long histories.

Also avoid treating a retrieved value as timeless. A table can contain obsolete policies, old model outputs, or values computed under different assumptions. Retrieval correctness and content correctness are separate questions.

Business use

Table lookup is useful for small stable mappings, reproducible baselines, and precomputed subproblems. It can make individual decisions easy to trace because the system can identify the exact entry used.

Before choosing it, estimate coverage and table growth. Define ownership, update procedures, and missing-key behavior. Log the table version when reproducibility matters. Compare total preparation, storage, and maintenance cost with on-demand computation or a compact model. A hybrid design can be practical, but should make clear when it retrieves an entry and when it switches to another method.

Check your understanding

Why does the four-observation agent need 120 entries rather than only 81?

Answer: It must act after histories of lengths one, two, three, and four. The 81 count covers only the final length.

Related terms

Memoization
Generalization
Lookup table
table-driven agent
memorisation
caching
state representation
hash table
interpolation

Learn next

Study state representation and memoization next. Build a tiny three-observation mapping, then remove one entry and specify exactly what a query should return. Finally, identify whether a compact rule can reproduce the mapping without losing distinctions that affect the output.

Memoization

Sources

Primary reference: AIMA Java documentation, “TableDrivenAgentProgram,” https://aimacode.github.io/aima-java/aima3e/javadoc/aima-core/aima/core/agent/impl/aprog/TableDrivenAgentProgram.html. The primary algorithm description was read for percept-history lookup. The history counts, memory caveat, and routing case are original teaching examples; no runtime or storage benchmark is claimed.

Previous: Table 2 fallacy Next: Tabled logic programming