Discrete Sequence Prediction and its Applications

Philip D. LairdAAAI 1992

Introduction

In the modern era of Large Language Models (LLMs), predicting the next item in a sequence is a task we often take for granted. However, in 1992, Philip Laird at NASA Ames Research Center introduced a practical and lightweight approach to this fundamental learning problem. His TDAG (Transition Directed Acyclic Graph) algorithm offers a mathematically sound alternative for discrete sequence prediction (DSP) that remains highly relevant for resource-constrained systems.

Laird argues that DSP—observing a stream of symbols and guessing the successor—is a core human capability. The challenge lies in creating an "on-line" algorithm that learns patterns as data arrives, without prior knowledge of the alphabet, while maintaining strict bounds on memory and processing time.

The TDAG Algorithm

The core contribution of the paper is the TDAG algorithm, which constructs a tree where each node represents a sequence of symbols observed in the past.

Core Mechanism

The algorithm maintains a "state" consisting of a FIFO queue of nodes representing the current context. As new symbols arrive, transition counts are updated. To make a prediction, TDAG identifies the deepest (most specific) context with sufficient statistical confidence and projects the most likely next symbol.

Practical Optimizations

To ensure efficiency, Laird implemented several key strategies:

  • Lazy Extension: The tree is not expanded for every new sequence. Instead, expansion occurs only after a context has been observed $N$ times and its probability exceeds a threshold $\Theta$.
  • Resource Bounding: Users can control the algorithm's footprint through parameters such as Height ($H$) for memory depth, Prediction Size ($P$) for the number of symbols returned, and a pruning threshold ($\Theta$) to eliminate noisy sequences.

Applications and Results

The versatility of TDAG was demonstrated across two very different domains: text compression and program execution optimization.

Text Compression

TDAG was evaluated against standard ASCII files, including C source code, English text, and Lisp code. The algorithm achieved compression ratios between 33% and 51%, frequently outperforming standard Unix utilities like compress (LZW-based) and compact (Huffman-based).

Table 1: Compression performance of TDAG compared to standard Unix utilities.

Program Optimization

Perhaps the most innovative application was using TDAG to optimize Prolog programs. By treating execution choices as a discrete sequence, the algorithm learns the most frequent paths. This allows for "unfolding" or reordering code to favor common execution traces.

Table 2: Performance improvements in Prolog programs using TDAG-based optimization.

As shown in Table 2, the CF Parser experienced a significant 41.1% improvement in CPU time. Other programs typically saw speedups between 10% and 20%. Notably, for complex problems like "Graph 3-Coloring" where patterns are scarce, the algorithm showed robustness, with performance remaining stable rather than degrading due to over-learning.

Insights and Future Directions

The paper's primary insight is the power of unified learning: the same mechanism used for data compression can effectively optimize software performance. By prioritizing "confidence over complexity"—using the longest statistically reliable sequence rather than just the longest possible one—TDAG achieves a balance between accuracy and efficiency.

While powerful, the 1992 version of TDAG assumes data stationarity. Future work suggested moving beyond "rote learning" of literal strings toward generalization, where the algorithm could recognize abstract patterns (e.g., "a digit followed by a letter"). Despite these limitations, TDAG remains a landmark example of how simple, well-constrained learning algorithms can solve complex real-world problems.

Summary updated

BibTeX
@inproceedings{laird1992discrete,
  author = {Philip D. Laird},
  title = {{Discrete Sequence Prediction and its Applications}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure