Lookup Conditional Distribution Prediction
Algorithms AIMech:LookupConditionalDistributionPrediction DRAFT
Aliases: Lookup CDP
A computational variant of conditional distribution prediction that precomputes or memoizes fixed-model subtree expansion-count estimates for type and remaining-cost contexts, then reuses those estimates when predicting a complete IDA* iteration from a shallow search frontier.
Identity Notes & Concept Scope
Compared all 442 pinned AIO and 640 native IDs, names, aliases and scoped synonyms; no normalized identity match. Ignored- and hidden-inclusive fixed-string searches of the recovery, older discovery and original Documents checkouts returned 27, 0, 0 lines. All distinct match contents were inspected. Semantic matching covered 66 AIO and 346 native definitions, with every matched definition read. 9 full annotated AIO node/edge/generated contexts and 3 full native records were inspected. Retain the named lookup-based computational variant of CDP. It precomputes or memoizes fixed-model subtree-count predictions for reuse, whereas epsilon-truncation modifies model probabilities and IDA*IM integrates online prediction into threshold-controlled search. It is not a solution path cache, transposition table or claim that all search trees sharing a compressed type have identical sizes.
Claims & Grounded Evidence
5 Claims
Mechanism
#cached-subproblem-predictions
The method stores predicted subtree counts for type and remaining-bound subproblems. In the source’s unit-cost formulation, smaller remaining bounds are computed before larger bounds using dynamic programming. When requested bounds are not known beforehand, results can instead be cached as queries arrive. Values are predictions from a specified CDP model, not necessarily exact subtree sizes for all concrete states with the same type.
Mechanism
#shallow-frontier-accounting
For a query start and bound d, explicitly search a shallow region to radius r, collect its surviving frontier and sum the cached predictions at remaining bound d−r for those frontier types. Add the expanded nodes strictly before that frontier. Pruning, root inclusion and the count convention must agree between the prefix search and cached recurrence; counting a frontier node in both terms duplicates it. The prefix search remains part of prediction work.
Scope
#fixed-model-equivalence
With the same transition and branching tables, type contexts, threshold pruning and initialization, lookup evaluation reorganizes the CDP recurrence and preserves its mathematical prediction. This equivalence does not improve CDP’s statistical accuracy, eliminate aggregation error or make predictions equal to true counts for every start. Floating-point evaluation order can also affect implementation-level numerical equality.
Limitation
#cache-context-boundary
A reusable cache must identify every model feature that changes a subproblem result. If epsilon-truncation varies with absolute prediction level, the level or an equivalent fixed schedule context is needed in addition to type and remaining bound unless that context is uniquely recoverable. Cached values must also remain tied to the same transition estimates and pruning conventions. The paper’s type/bound description is not a guarantee that a cache remains valid across changed models or differently indexed schedules.
Limitation
#runtime-and-evaluation-boundaries
The source contrasts a dense CDP query cost of O(|T|²(d−r)+Q_r) with O(Q_r) lookup prediction after preprocessing, where Q_r is the shallow-prefix work and lookups are treated as constant time. Table size depends on the represented types and bounds, and additional contexts can enlarge it. Finite puzzle experiments show large gains in some shallow-prefix regimes and much smaller gains when prefix search dominates. Sampling and cache construction must be counted or amortized; the method does not guarantee a faster first query or universal speedup.
⚠️ Curated Limitations & Negative Results
- Lookup CDP is a computational reuse method for a count estimator, not IDA* itself, online threshold selection, a concrete-state solution cache or probability-table truncation.
- Same-model mathematical recurrence equality does not certify true node counts. Type aggregation, parameter estimation, ancestor pruning and complete-iteration semantics retain their original limitations.
- Absolute-level-dependent probability modifications require an adequate cache key or fixed recoverable schedule context. Reusing stale values across changed models is outside the asserted equivalence.
- The reported query complexity excludes offline sampling and cache construction and assumes suitable lookup operations. Larger type/state spaces, many thresholds and detailed cache contexts consume memory; shallow-prefix work can dominate.
- All25 pages of the author-hosted journal copy were visually inspected. Author implementation, earlier conference full texts and benchmark replication were not inspected or executed. Rational recurrence and cost examples are constructed checks, not measured performance.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:MarkovChain
Markov Chain
|
related_match | The reused CDP recurrence contains conditional transition laws on type contexts. This is a curator-inferred component relationship, not an assertion that count propagation with branching and pruning is a probability-preserving Markov chain. Lookup reuse neither guarantees Markov sufficiency of compressed search types nor changes the abstraction level of the pinned network class. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
lelis2013prediction
|
Levi H. S. Lelis, Sandra Zilles, Robert C. Holte
|
primary paper
full_text
|
ID: doi:10.1016/j.artint.2013.01.001
sha256:ee16910b3529…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-13T18:56:53Z
Updated: 2026-10-13T19:02:55Z