💬 NLP

Lossless Prompt Compression via Dictionary-Encoding and In-Context Learning: Enabling Cost-Effective LLM Analysis of Repetitive Data

This paper introduces a training-free, lossless prompt compression method that enables Large Language Models to perform in-context learning on dictionary-encoded repetitive data, achieving up to 80% compression while preserving analytical accuracy and significantly reducing API costs and token limits.

Original authors: Andresa Rodrigues de Campos, David Lee, Imry Kissos, Piyush Paritosh

Published 2026-04-16

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Andresa Rodrigues de Campos, David Lee, Imry Kissos, Piyush Paritosh

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 have a massive library of books, but every single page is filled with the exact same boring sentences repeated over and over again. If you wanted to ask a super-smart librarian (an AI) to analyze these books, you'd have to read every single word aloud to them. Since the librarian charges you by the word you speak, this would cost a fortune and take forever.

This paper introduces a clever trick to solve that problem without losing any information. Here is how it works, explained simply:

The Problem: The "Word Tax"

Large Language Models (LLMs) are like brilliant detectives, but they have two big weaknesses:

They get tired: They can only read a certain amount of text at once (the "context window").
They are expensive: You pay for every single word (token) they process.

When dealing with repetitive data—like computer logs where the same error message appears 10,000 times—you are paying the "word tax" for the same information over and over again.

The Solution: The "Secret Code" Dictionary

The authors realized that instead of compressing the text into a format the AI can't read (like a ZIP file), they could teach the AI a secret code right before it starts reading.

Think of it like this:

The Old Way: You hand the AI a 100-page document where the phrase "System Error Code 404" appears 50 times. You pay for 500 words.
The New Way: You hand the AI a tiny note that says: *"Rule: Whenever you see the symbol , it means 'System Error Code 404'."*
Then, you hand them the document, but you've replaced every long phrase with the short symbol .

Now, the document is tiny. The AI reads the short symbols, remembers the rule you gave it, and understands the full meaning perfectly.

How They Did It (The "Smart Sorter")

The paper describes a computer program that acts like a super-efficient editor:

It scans the text: It looks for patterns that repeat, like "Error: Connection failed at 10:00 AM."
It checks the math: It asks, "Is this phrase long enough that replacing it with a short symbol will actually save money?" If the symbol is too long or the phrase doesn't repeat enough, it skips it.
It builds the dictionary: It creates a list of these shortcuts (e.g., <M1> = "Error: Connection failed...").
It swaps the text: It replaces the long phrases in the original text with the short symbols.

The "Magic" Part: In-Context Learning

The most impressive part is that they didn't have to retrain the AI.

Usually, to make an AI understand a new code, you have to spend months teaching it (fine-tuning). Here, they just put the dictionary in the AI's "instruction manual" (the system prompt) right before the task. The AI is so smart that it instantly learns the code, reads the compressed text, and gives you the exact same answer as if it had read the full, uncompressed text.

The Results: Saving Money Without Losing Quality

They tested this on millions of lines of computer logs.

Compression: They shrank the text by 60% to 80%. Imagine shrinking a 100-page book down to 20 pages.
Accuracy: When they asked the AI to analyze the compressed text, it got the answers right 99% of the time.
The Surprise: They found that how much they compressed the text didn't matter. Whether they compressed it a little or a lot, the AI's ability to understand it stayed the same. The only thing that mattered was how messy or repetitive the original data was.

Why This Matters

Cost: If you compress your data by 70%, you save 70% on your AI bill.
Speed: Smaller files mean the AI reads faster.
No Training: You don't need a team of engineers to retrain the model. You just use this "dictionary trick" and go.

In a nutshell: This paper teaches us how to speak a "shorthand" language to AI. By giving the AI a quick dictionary of shortcuts, we can feed it massive amounts of repetitive data for a fraction of the cost, and it understands it just as well as if we had spoken in full sentences.

1. Problem Statement

Large Language Models (LLMs) face significant cost and latency barriers when processing repetitive textual data, such as system logs, due to token-based pricing and context window constraints.

The Challenge: Traditional compression algorithms (e.g., ZIP, GZIP) achieve high compression ratios on repetitive data but render the data unreadable to LLMs, which cannot natively process binary or compressed formats.
The Gap: Existing LLM-specific compression methods often require lossy techniques (discarding information) or fine-tuning models to understand custom compression schemes. Fine-tuning is impractical for dynamic datasets where patterns evolve, and lossy methods risk degrading analytical accuracy.
The Goal: Develop a lossless, training-free method to compress prompt inputs that allows LLMs to analyze the compressed data directly without decompression, thereby reducing token counts and API costs while maintaining analytical fidelity.

2. Methodology

The authors propose a hierarchical dictionary-encoding approach that leverages the LLM's in-context learning capabilities. The system operates in two phases: a pre-processing compression phase and an in-context analysis phase.

A. Hierarchical Compression Algorithm

The algorithm identifies and replaces repetitive subsequences with compact "meta-tokens" (e.g., <M1>, <M2>).

Segmentation: Input text is split into word units.
Hierarchical Scanning: The algorithm iterates from the maximum subsequence length ( $L_{max}$ ) down to a minimum length (typically 2). It prioritizes longer patterns to maximize efficiency.
Frequency Analysis: It identifies subsequences occurring frequently ( $\ge f_{min}$ ).
Token Savings Optimization: A critical criterion ensures compression is only applied if it yields a net token reduction. The condition is:
$(1 + f) \cdot n_{token}(M) + n_{token}(S) < f \cdot n_{token}(S)$
Where $f$ is frequency, $S$ is the subsequence, and $M$ is the meta-token. This prevents the dictionary overhead from exceeding the savings.
Non-Overlapping Replacement: Selected subsequences are replaced with meta-tokens, and a dictionary mapping meta-tokens to original sequences is generated.
Batch Processing: For large datasets, compression is applied per batch with a batch-specific dictionary to optimize for local patterns.

B. In-Context Learning & Analysis

System Prompt: The generated dictionary is provided to the LLM in the system prompt.
User Prompt: The compressed text (containing meta-tokens) is provided as the user input.
Mechanism: The LLM learns the encoding key "in-context" (without fine-tuning) and performs analytical tasks (e.g., error detection, pattern mining) directly on the compressed representation, interpreting meta-tokens as their original semantic equivalents.

3. Key Contributions

Empirical Validation of In-Context Dictionary Learning: The paper demonstrates that LLMs can learn compression dictionaries solely from the system prompt and produce analytically equivalent outputs from compressed inputs. This eliminates the need for model fine-tuning.
Hierarchical Compression Algorithm: A novel algorithm that identifies patterns at multiple length scales, handles nested patterns, prevents overlapping replacements, and integrates a token-savings optimization criterion to ensure cost-effectiveness.
Training-Free Deployment: The approach works with standard API-based LLMs, addressing deployment constraints (token limits, costs) without requiring specialized infrastructure or retraining costs.

4. Experimental Results

The authors evaluated their approach using the LogHub 2.0 benchmark (14 diverse system log datasets) with Claude 3.7 Sonnet and Nova Premier.

A. Compression Efficiency

Ratios: Achieved compression ratios of 60%–80% for datasets with high structural regularity (e.g., Apache, OpenSSH, Linux).
Optimization: The token-savings criterion successfully prevented dictionary overhead from negating gains, even for datasets with complex patterns.

B. Decompression & Analytical Accuracy

Decompression was used as a proxy task to validate that the LLM understands the compressed data.

Template-Based Compression: Using known log templates, the LLM achieved >99% exact match rates (0.994 mean) across 12/14 datasets.
Algorithmic Compression: Using the hierarchical algorithm, the LLM achieved an average Levenshtein similarity score of 0.91 (and >0.90 for 12/14 datasets) even at high compression ratios (60–80%).
Scalability: Performance remained stable as dictionary sizes increased from 29 to 626 entries and dataset sizes scaled from 2k to 100k+ logs.

C. Key Finding: Compression vs. Quality

Independence: Linear regression analysis revealed that compression ratio explains less than 2% of the variance in reconstruction quality ( $R^2 < 0.02$ ).
Implication: High compression intensity does not degrade LLM performance. Performance variations are driven by dataset characteristics (e.g., presence of natural language context) rather than the degree of compression. Datasets with dense alphanumeric sequences lacking context (e.g., HPC, Thunderbird) were the only outliers.

5. Significance and Impact

Cost Reduction: A 60–80% reduction in token count translates directly to proportional reductions in API costs, making large-scale log analysis economically feasible.
Context Window Utilization: Allows more data to fit within fixed context windows, enabling comprehensive analysis without truncation or sampling.
Operational Simplicity: As a training-free method, it can be immediately deployed in production environments where data patterns change over time, avoiding the prohibitive costs of continuous model retraining.
Generalizability: While tested on logs, the method applies to any domain with repetitive textual patterns, including process mining, software engineering artifacts, and templated documents.

Conclusion

The paper establishes that lossless prompt compression via dictionary encoding is a viable, cost-effective strategy for LLMs. By leveraging in-context learning, LLMs can interpret compressed representations without fine-tuning, maintaining high analytical accuracy while drastically reducing token consumption. This solves a fundamental bottleneck in scaling LLM applications for repetitive data analysis.