Epsilon-truncation for Conditional Distribution Prediction
Algorithms AIMech:EpsilonTruncationCDP DRAFT
Aliases: CDP epsilon-truncation
A modification of conditional distribution prediction for IDA* tree size that removes conditional child-type probabilities below a calibrated level-specific cutoff, renormalizes the surviving probabilities and uses the modified tables in node-count propagation.
Identity Notes & Concept Scope
Compared all 442 pinned AIO and 639 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 5, 0, 0 lines. All distinct match contents were inspected. Semantic matching covered 66 AIO and 345 native definitions, with every matched definition read. 12 full annotated AIO node/edge/generated contexts and 4 full native records were inspected. Retain the named CDP probability-table modification and calibrated per-level cutoff method. It changes an estimator, not the actual IDA* search tree or solution policy. Original CDP, lookup-based reuse, IDA*IM threshold control, score-margin sequence beam pruning and pruned topic-model Gibbs transitions have distinct targets. Generic epsilon-truncation outside this search-estimation context is not asserted equivalent.
Claims & Grounded Evidence
5 Claims
Mechanism
#level-specific-table-modification
For each prediction level and parent type, set conditional child-type probabilities strictly below the chosen cutoff to zero and divide the retained probabilities by their positive sum. Probabilities equal to the cutoff are retained. The source lowers a proposed cutoff if it would remove an entire conditional row. The resulting normalized table replaces the original table at that level of CDP count propagation; it does not prune nodes from an actual IDA* execution.
Mechanism
#offline-cutoff-calibration
The source estimates transition and branching statistics, then obtains per-level cutoff candidates using sampled start states and a supertype allocation procedure that groups related parent-child contexts. It looks for a prefix of small probability values that are set to zero in at least half of the sampled allocation solutions, then guards against empty retained rows. This offline approximation replaces solving an allocation problem during every prediction. The cutoff depends on the sampled contexts and depth; it is not a universal constant or a guarantee of optimal true expansion counts.
Limitation
#printed-calibration-boundaries
The printed calibration objectives use p^j(1-p)^(N-j) as the probability of an exact count j, omitting the binomial multiplicity required for N independent Bernoulli trials. The supertype count in Equation 4 also sums over parent-child pairs, whereas the preceding transition formula sums distinct parent types; a parent with multiple child types in the same group can be counted repeatedly under that literal reading. The record therefore describes the practical cutoff construction without certifying those printed formulas as an exact expected-error optimization or equivalent recurrence. These observations do not establish what uninspected author code computes.
Limitation
#aggregation-and-accuracy-limits
The method addresses errors that can arise when CDP propagates fractional expected counts through aggregated types, including settings where a more detailed type system predicts less accurately. Removing rare transitions is nevertheless an approximation: a rare child type can have a large descendant subtree, and truncation can worsen a previously exact count. The source reports degradations in some error metrics and explicitly does not guarantee unbiased predictions. Accurate global conditional probabilities alone do not ensure accurate counts for every start.
Limitation
#finite-evaluation-and-amortization
Evidence comes from configured sliding-tile, pancake and Rubik’s Cube experiments with selected heuristics, type systems, start sets and shallow-search radii. The paper separates aggregate prediction ratios, mean absolute relative error and root-mean-square relative error; these can rank settings differently. Sampling and cutoff calibration can be costly and are assumed amortized across predictions. Lookup CDP is a separate computational-reuse method; retaining identical predictions requires the same model and depth-dependent table context, not merely reusing a type label under a changed schedule.
⚠️ Curated Limitations & Negative Results
- This identity is the scoped CDP epsilon-truncation method. It is not generic numerical truncation, beam pruning, a cutoff in the actual IDA* search, lookup caching or an asserted exact new search algorithm.
- Each retained conditional row must have positive total mass. Equality follows the source’s retention rule; a cutoff that empties a row cannot be normalized.
- The printed count-probability and supertype aggregation formulas require the stated qualifications. No correction to author software is inferred, and neither the calibration objective nor heuristic cutoff is certified as an optimum of true expansion-count error.
- Finite empirical improvements do not establish unbiasedness, per-start accuracy, universal speedup or immunity to rare types with large subtrees. Absolute-depth-varying schedules must be preserved in any cached recurrence state.
- All 25 pages of the author-hosted journal personal copy were visually read. Earlier conference versions, author software and benchmark replication were not inspected or executed. Constructed rational examples test mathematical boundaries only.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:MarkovChain
Markov Chain
|
related_match | The method truncates and renormalizes the conditional transition law on CDP type contexts, potentially using a different law at each prediction level. This is a curator-inferred component relationship. Branching-count propagation and threshold pruning are not probability-preserving chain evolution, and compressed contexts need not make the actual search process Markov. The procedure is not asserted equivalent to or a subclass 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:39:32Z
Updated: 2026-10-13T18:39:32Z
Source File:
data/curated/EpsilonTruncationCDP.yaml