🤖 machine learning

Byte Pair Encoding for Efficient Time Series Forecasting

This paper introduces a novel pattern-centric tokenization scheme inspired by Byte Pair Encoding that adaptively merges time series samples into motif-based tokens to significantly reduce computational overhead and improve forecasting accuracy, further enhanced by a lightweight conditional decoding optimization.

Original authors: Leon Götz, Marcel Kollovieh, Stephan Günnemann, Leo Schwinn

Published 2026-06-02

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Leon Götz, Marcel Kollovieh, Stephan Günnemann, Leo Schwinn

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a computer to predict the future based on a long, messy line of numbers (like stock prices, weather data, or energy usage). This line is called a time series.

Currently, most computers look at this line one single number at a time. It's like trying to read a novel by looking at one letter at a time, one by one. If the story has a long sentence like "The sky is blue," the computer has to process "T," "h," "e," " " (space), "s," "k," "y"... individually. This is slow, inefficient, and wastes a lot of brainpower.

This paper introduces a smarter way to read these numbers, inspired by how we compress text on our phones. Here is the breakdown using simple analogies:

1. The Problem: The "Letter-by-Letter" Bottleneck

Existing methods treat every single data point as a separate "token" (a unit of information).

The Analogy: Imagine you are sending a message that says "AAAAA" (five A's). The old way sends five separate letters: A, A, A, A, A.
The Issue: If your time series has long stretches of repeating patterns (like a flat line or a steady rhythm), the computer gets bogged down processing thousands of tiny, repetitive tokens. It's like carrying a heavy backpack full of single bricks instead of a few pre-assembled walls.

2. The Solution: "Motif" Compression (Byte Pair Encoding)

The authors propose a new method called Motif-Based Tokenization. They borrow an idea from language processing called "Byte Pair Encoding."

The Analogy: Instead of sending "A, A, A, A, A," the computer learns that "AAAAA" is a common pattern. It creates a special shortcut code for it, like a single sticker that says "5 A's."
How it works:
1. Quantization: First, they turn the smooth, continuous numbers into simple "bins" (like sorting colors into buckets: Light Blue, Medium Blue, Dark Blue).
2. Merging: Then, they scan the sequence. If they see a pattern that repeats often (like "Light Blue, Medium Blue, Light Blue"), they glue those together into a single "Motif" token.
3. The Result: A long, complex time series gets squished down into a much shorter list of these "Motif stickers."

The Benefit: The computer doesn't have to read every single brick; it just reads the pre-built walls. This makes the process 2,300% faster (according to the paper) and actually helps the computer predict the future better because it sees the bigger picture.

3. The Secret Sauce: "Conditional Decoding"

There is a catch. When you glue bricks together to make a wall, you lose a tiny bit of detail about the exact shape of the original bricks. This is called "discretization error."

The Analogy: Imagine you summarize a movie as "The hero saves the day." You lost the specific dialogue and facial expressions.
The Fix: The authors introduce Conditional Decoding. This is a lightweight "post-processing" step.
- It looks at the "Motif sticker" and asks, "Given that the previous sticker was 'X', what is the most likely exact number for this one?"
- It's like a smart editor who reads your summary and fills in the missing details based on context, without needing to re-watch the whole movie (no heavy computing required).
- This step removes the loss of detail, improving accuracy by up to 48% without slowing anything down.

4. What They Found (The Results)

The team tested this on a massive dataset of time series (like electricity usage, traffic, and weather) and compared it to the best existing models.

Speed: Their method was drastically faster because it had fewer tokens to process.
Accuracy: It predicted the future more accurately than the old "letter-by-letter" methods.
Adaptability: The method is flexible. If a pattern is simple (like a flat line), it compresses it heavily. If a pattern is complex and chaotic, it keeps it more detailed. It doesn't force a "one size fits all" approach.
Zero-Shot: They showed that a model trained on this method could predict new types of data it had never seen before, without needing extra training.

Summary

Think of this paper as inventing a smart compression tool for time travel.
Instead of forcing a computer to memorize every single second of history, it teaches the computer to recognize patterns (like "a steady rise," "a sudden drop," or "a repeating cycle"). It stores these patterns as single, efficient units. Then, it uses a clever trick to fill in the tiny details it might have missed. The result is a system that is both super fast and super smart at predicting what happens next.

Technical Summary: Byte Pair Encoding for Efficient Time Series Forecasting

Problem Statement

Current tokenization methods for time series forecasting, particularly those utilizing Transformer architectures, suffer from significant inefficiencies and inflexibility. Existing approaches predominantly fall into two categories:

Sample-based tokens: Treating every individual time step as a token. This results in excessively long sequences where each token captures minimal temporal information, imposing a substantial computational burden on Transformer models, especially for long sequences.
Patch-based tokens: Splitting time series into fixed-length subsequences (patches). While this mitigates sequence length issues, rigid patches cannot adapt to diverse temporal patterns of varying lengths and complexities. This lack of adaptability hinders the generalization capabilities of foundation models in zero-shot settings.

These limitations lead to suboptimal forecasting performance and high computational overhead, preventing efficient processing of long time series.

Methodology

The authors propose Byte Pair Encoding (BPE) for Time Series, the first pattern-centric tokenization scheme for this domain. The method operates in two primary stages, followed by a post-hoc optimization technique:

1. Adaptive Motif-Based Tokenization

Inspired by BPE in Natural Language Processing (NLP), the method compresses time series by merging recurring patterns into single tokens.

Discretization: The continuous time series $z$ is first quantized into a sequence of discrete symbols using a vocabulary $\Omega$ of equiprobable bins. This transforms the regression task into a classification task over a discrete vocabulary.
Motif Extraction: Using an iterative algorithm, the method identifies the most frequent adjacent token pairs in the discretized sequence and merges them into a new token ID. This process repeats hierarchically to build a vocabulary $\Psi$ of frequent time series motifs (patterns of variable length).
Compression: The quantized sequence is compressed by replacing recurring patterns with their corresponding motif tokens. This results in a variable-length token sequence where complex patterns are represented by single tokens, enabling adaptive compression. The algorithm has linear complexity $O(|\Psi| \cdot n)$ relative to sequence length.

2. Conditional Decoding

To address the discretization error introduced by quantizing continuous values, the authors introduce conditional decoding as a lightweight, post-hoc optimization method.

Mechanism: Instead of mapping a quantized token back to a fixed bin center, the decoding value is conditioned on the previous sample. Specifically, the reconstruction of a sample $z_i$ depends on the quantized value of the previous sample $z'_{i-1}$ .
Optimization: The parameters for this conditional mapping ( $\hat{\omega}_{j,k}$ ) are computed analytically as the mean of the underlying continuous samples for specific token transitions. This requires no gradient computation or additional training of the main model.
Efficiency: It adds negligible computational overhead during inference (equivalent to a dictionary lookup) and relies on a first-order Markov assumption with only $M^2$ parameters.

3. Model Architecture

The tokenized sequences are processed by standard Transformer architectures (specifically T5 variants). The model predicts the next token ID from the finite vocabulary $V = \Omega \cup \Psi \cup \{MASK, EOS\}$ using a categorical distribution, effectively transforming time series forecasting into a next-token prediction task.

Key Contributions

Adaptive Tokenization: A novel strategy that merges samples with underlying patterns into single tokens based on a discrete vocabulary of frequent motifs. This enables adaptive compression while maintaining a bounded discretization error.
Conditional Decoding: A lightweight, gradient-free post-hoc optimization method that exploits the continuous properties of time series to reduce discretization error, significantly improving forecasting quality without retraining the foundation model.
Empirical Validation: Extensive analysis demonstrating the method's adaptiveness to diverse temporal patterns, its generalization to unseen data, and the meaningfulness of the learned token representations (capturing statistical moments, trends, and motif lengths).

Experimental Results

The method was evaluated on the Chronos foundation model (trained on 11M time series) and compared against sample-based and patch-based baselines across 7 diverse datasets (ETTh1, ETTm1, Weather, Electricity, Traffic, Solar, Fev-bench) in a zero-shot setting.

Performance Gains: On the Chronos foundation model, the motif-based tokenization improved forecasting performance (MSE) by 40% on average compared to sample-based tokenization. With conditional decoding, MSE reductions reached up to 48%.
Efficiency: The approach boosted efficiency by an average of 2314% (approx. 23x speedup) by reducing the number of tokens and autoregressive steps required. In specific cases (e.g., Traffic dataset), acceleration reached 56.66x.
Comparison with SOTA: The proposed method outperformed or matched state-of-the-art foundation models (MOMENT, Moirai, Time-MoE, LightGTS) in zero-shot settings, achieving the best forecasts in 19 out of 25 cases without fine-tuning.
Adaptability: The tokenizer demonstrated variable compression ratios (e.g., from 3.30 on Traffic to 23.15 on Weather), adapting to pattern complexity within and across datasets. Longer, more complex motifs were found to correlate with better forecasting quality.
Robustness: The method showed superior robustness to noise and outliers compared to sample-based baselines, often falling back to sample-based tokenization for unknown transient patterns without catastrophic failure.

Significance and Claims

The paper claims to introduce the first pattern-centric tokenization scheme for time series, bridging the gap between the efficiency of NLP tokenization and the continuous nature of time series data. The authors assert that their method:

Reduces Computational Costs: By compressing time series into fewer, more informative tokens, it significantly lowers the inference time and resource consumption of large foundation models.
Enhances Generalization: The adaptive nature of the tokenization allows models to generalize better to unseen data and diverse temporal patterns compared to rigid patching.
Provides Meaningful Representations: The learned token embeddings are shown to capture distinct time series properties, including statistical moments (mean, standard deviation) and trends, validating the semantic value of the motifs.
Offers a Practical Optimization: Conditional decoding is presented as a universally applicable, low-cost method to enhance any pretrained model with a discrete output vocabulary.

The authors conclude that this approach contributes to more sustainable and efficient time series models, potentially reducing the environmental impact of training and deploying large foundation models. They acknowledge limitations regarding the lack of hyperparameter search for the T5 backbone due to computational costs and suggest future work could explore more recent transformer architectures.