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

Andresa Rodrigues de Campos; David Lee; Imry Kissos; Piyush Paritosh

cs.CLMar 19, 2026

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

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

Organizations: Amazon.com.

Abstract

In-context learning has established itself as an important learning paradigm for Large Language Models (LLMs). In this paper, we demonstrate that LLMs can learn encoding keys in-context and perform analysis directly on encoded representations. This finding enables lossless prompt compression via dictionary encoding without model fine-tuning: frequently occurring subsequences are replaced with compact meta-tokens, and when provided with the compression dictionary in the system prompt, LLMs correctly interpret these meta-tokens during analysis, producing outputs equivalent to those from uncompressed inputs. We present a compression algorithm that identifies repetitive patterns at multiple length scales, incorporating a token-savings optimization criterion that ensures compression reduces costs by preventing dictionary overhead from exceeding savings. The algorithm achieves compression ratios up to 80 $\%$ depending on dataset characteristics. To validate that LLM analytical accuracy is preserved under compression, we use decompression as a proxy task with unambiguous ground truth. Evaluation on the LogHub 2.0 benchmark using Claude 3.7 Sonnet demonstrates exact match rates exceeding 0.99 for template-based compression and average Levenshtein similarity scores above 0.91 for algorithmic compression, even at compression ratios of 60 $\%$ -80 $\%$ . Additionally, compression ratio explains less than 2 $\%$ of variance in similarity metrics, indicating that decompression quality depends on dataset characteristics rather than compression intensity. This training-free approach works with API-based LLMs, directly addressing fundamental deployment constraints -- token limits and API costs -- and enabling cost-effective analysis of large-scale repetitive datasets, even as data patterns evolve over time.

Figures & tables

Figure 1: System overview showing hierarchical compression algorithm (right), subsequence finding detail (top left), and compressed output with dictionary (bottom left).

Figure 2: Compression ratios vs. $L_{max}$ without dictionary overhead (right) and with dictionary overhead (left). Most datasets show plateau behavior, while some exhibit optimal $L_{max}$ values beyond which dictionary overhead reduces compression efficiency.

Figure 3: Template-based decompression results comparing Claude 3.7 Sonnet and Nova Premier across LogHub 2k datasets. Each point represents the average metric score computed over 2,000 logs per dataset.

Dataset	Entries	Templates	Exact Match	Levenshtein	Hamming	Rouge
Apache	51,978	29	0.999	0.999	0.999	0.999
Mac	100,314	626	0.969	0.987	0.975	0.988

Table 1: LogHub Full Dataset Template-Based Results (Claude 3.7 Sonnet)

Figure 4: Compression ratios and decompression quality as a function of $L_{max}$ . Top-left: compression ratios by dataset. Remaining panels: Levenshtein, ROUGE, and BLEU scores. Most datasets maintain scores above 0.9 regardless of compression level; outliers (HPC, Thunderbird) show consistently lower scores across all $L_{max}$ values, indicating dataset-specific rather than compression-related effects.

Dataset	Levenshtein	ROUGE	BLEU
Apache	$0.925\pm 0.048$	$0.959\pm 0.026$	$0.918\pm 0.059$
BGL	$0.928\pm 0.026$	$0.957\pm 0.014$	$0.956\pm 0.029$
Hadoop	$0.945\pm 0.023$	$0.972\pm 0.010$	$0.997\pm 0.005$
HDFS	$0.963\pm 0.042$	$0.978\pm 0.023$	$0.978\pm 0.015$
HealthApp	$0.943\pm 0.028$	$0.973\pm 0.012$	$0.956\pm 0.020$
HPC	$0.823\pm 0.021$	$0.908\pm 0.012$	$0.840\pm 0.025$

Table 2: Decompression quality for algorithmic compression across

L_{max}

values 3–10. Metrics reported as mean

\pm

std across compression levels. Most datasets (12/14) achieve Levenshtein similarity above 0.90; outliers (HPC, Thunderbird) reflect dataset-specific characteristics discussed in Section 6 .

Figure 5: Relationship between compression ratio and decompression quality. Each point represents one (dataset, $L_{max}$ ) configuration. Dashed lines show linear regression fits; shaded regions indicate 95% confidence intervals. R 2 values below 0.02 for all metrics demonstrate that compression intensity does not predict reconstruction quality—performance variation is driven by dataset characteristics rather than compression level.

Dataset	Original Tokens
HPC	13,959
Zookeeper	27,878
BGL	32,951
Apache	36,449
HealthApp	37,533
Spark	39,604

Table 3: Original Token Counts for LogHub-2k Datasets

	Claude 3.7 Sonnet			Nova Premier
Dataset	Exact Match	Levenshtein	ROUGE	Exact Match	Levenshtein	ROUGE
Apache	$1.000$	$1.000$	$1.000$	$1.000$	$1.000$	$1.000$
BGL	$1.000$	$1.000$	$1.000$	$0.901\pm 0.007$	$0.958\pm 0.003$	$0.968\pm 0.003$
Hadoop	$1.000$	$1.000$	$1.000$	$0.898\pm 0.007$	$0.959\pm 0.003$	$0.970\pm 0.003$
HDFS	$1.000$	$1.000$	$1.000$	$0.949\pm 0.005$	$0.977\pm 0.002$	$0.984\pm 0.002$
HealthApp	$0.996\pm 0.001$	$1.000$	$1.000$	$0.874\pm 0.007$	$0.920\pm 0.005$	$0.928\pm 0.005$

Table 4: Per-dataset template-based decompression metrics for Claude 3.7 Sonnet and Nova Premier on LogHub-2k (2000 logs per dataset). Per-dataset values reported as mean

\pm

SEM; aggregate row reports mean

\pm

std across datasets.

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: Levenshtein similarity, ROUGE, and BLEU scores for algorithmic compression for Apache dataset and $L_{max}$ values.

Figure 7: Levenshtein similarity, ROUGE, and BLEU scores for algorithmic compression for BGL dataset and $L_{max}$ values.

Figure 8: Levenshtein similarity, ROUGE, and BLEU scores for algorithmic compression for HDFS dataset and $L_{max}$ values.

Figure 9: Levenshtein similarity, ROUGE, and BLEU scores for algorithmic compression for HPC dataset and $L_{max}$ values.

Figure 10: Levenshtein similarity, ROUGE, and BLEU scores for algorithmic compression for Hadoop dataset and $L_{max}$ values.

Figure 11: Levenshtein similarity, ROUGE, and BLEU scores for algorithmic compression for HealthApp dataset and $L_{max}$ values.

Figure 12: Levenshtein similarity, ROUGE, and BLEU scores for algorithmic compression for Linux dataset and $L_{max}$ values.

Figure 13: Levenshtein similarity, ROUGE, and BLEU scores for algorithmic compression for Mac dataset and $L_{max}$ values.

Figure 14: Levenshtein similarity, ROUGE, and BLEU scores for algorithmic compression for OpenSSH dataset and $L_{max}$ values.

Figure 15: Levenshtein similarity, ROUGE, and BLEU scores for algorithmic compression for OpenStack dataset and $L_{max}$ values.

Figure 16: Levenshtein similarity, ROUGE, and BLEU scores for algorithmic compression for Proxifier dataset and $L_{max}$ values.

Figure 17: Levenshtein similarity, ROUGE, and BLEU scores for algorithmic compression for Spark dataset and $L_{max}$ values.

Figure 18: Levenshtein similarity, ROUGE, and BLEU scores for algorithmic compression for Thunderbird dataset and $L_{max}$ values.

Figure 19: Levenshtein similarity, ROUGE, and BLEU scores for algorithmic compression for Zookeeper dataset and $L_{max}$ values.

Lossless Data Compression

See all 26 papers

Mar 6, 2026

Compression Method Matters: Benchmark-Dependent Output Dynamics in LLM Prompt Compression

Prompt compression is often evaluated by input-token reduction, but its real deployment impact depends on how compression changes output length and total inference cost. We present a controlled replication and extension study of benchmark-dependent output dynamics under aggressive compression, covering 5,400 API calls across three benchmarks and multiple providers. To explain conflicting prior observations, we formalize instruction survival probability (Psi), a structural metric that captures whether task-critical prompt segments remain after truncation. Results show a strong benchmark effect: under r=0.3, DeepSeek exhibits severe output expansion on MBPP (56x, Psi approx 0.15) but substantially lower expansion on HumanEval (5x, Psi approx 0.72), while GPT-4o-mini is comparatively stable across benchmarks. This reconciles the apparent discrepancy between previously reported extreme explosion and lower replication effects by identifying prompt structure, not provider identity alone, as the primary moderator. We introduce the Compression Robustness Index (CRI) for cross-benchmark evaluation and show that single-benchmark assessments can produce misleading conclusions about compression safety and efficiency. To contextualize energy claims, we incorporate companion direct NVML measurements from rented RunPod GPUs and show that token savings can overstate joule savings. These findings motivate benchmark-diverse testing and structure-aware compression policies for reliable, energy-conscious LLM deployment.

Warren Johnson

Plexor Labs Principal Researcher

Prompt Compression LLM Inference Efficiency Efficient Language Model Inference LLM Evaluation

Ask PDF

Apr 3, 2026

Prompt Compression in the Wild: Measuring Latency, Rate Adherence, and Quality for Faster LLM Inference

With the wide adoption of language models for IR -- and specifically RAG systems -- the latency of the underlying LLM becomes a crucial bottleneck, since the long contexts of retrieved passages lead large prompts and therefore, compute increase. Prompt compression, which reduces the size of input prompts while aiming to preserve performance on downstream tasks, has established itself as a cost-effective and low-latency method for accelerating inference in large language models. However, its usefulness depends on whether the additional preprocessing time during generation is offset by faster decoding. We present the first systematic, large-scale study of this trade-off, with thousands of runs and 30,000 queries across several open-source LLMs and three GPU classes. Our evaluation separates compression overhead from decoding latency while tracking output quality and memory usage. LLMLingua achieves up to 18% end-to-end speed-ups, when prompt length, compression ratio, and hardware capacity are well matched, with response quality remaining statistically unchanged across summarization, code generation, and question answering tasks. Outside this operating window, however, the compression step dominates and cancels out the gains. We also show that effective compression can reduce memory usage enough to offload workloads from data center GPUs to commodity cards, with only a 0.3s increase in latency. Our open-source profiler predicts the latency break-even point for each model-hardware setup, providing practical guidance on when prompt compression delivers real-world benefits.

Cornelius Kummer, Lena Jurkschat, Michael Färber +1

ScaDS.AI Dresden/Leipzig, CIDS, TU Dresden

Prompt Compression LLM Inference Efficiency LLM Inference Acceleration

Ask PDF

Apr 16, 2026

Compressing Sequences in the Latent Embedding Space: $K$ -Token Merging for Large Language Models

Large Language Models (LLMs) incur significant computational and memory costs when processing long prompts, as full self-attention scales quadratically with input length. Token compression aims to address this challenge by reducing the number of tokens representing inputs. However, existing prompt-compression approaches primarily operate in token space and overlook inefficiencies in the latent embedding space. In this paper, we propose K-Token Merging, a latent-space compression framework that merges each contiguous block of K token embeddings into a single embedding via a lightweight encoder. The compressed sequence is processed by a LoRA-adapted LLM, while generation remains in the original vocabulary. Experiments on structural reasoning (Textualized Tree), sentiment classification (Amazon Reviews), and code editing (CommitPackFT) show that K-Token Merging lies on the Pareto frontier of performance vs. compression, achieving up to 75% input length reduction with minimal performance degradation. Code is available at https://github.com/shsjxzh/K-Token-Merging.

Zihao Xu, John Harvill, Ziwei Fan +3

♢Rutgers University · ♡Mistral AI · ♠AWS AI Labs +3

Token Merging LLM Compression Embedding Compression Prompt Compression LLM Context Compression

Ask PDF

Abstract

Lossless Data Compression

Explore similar work

Compression Method Matters: Benchmark-Dependent Output Dynamics in LLM Prompt Compression

Prompt Compression in the Wild: Measuring Latency, Rate Adherence, and Quality for Faster LLM Inference

Compressing Sequences in the Latent Embedding Space: KKK-Token Merging for Large Language Models

Compressing Sequences in the Latent Embedding Space: $K$ -Token Merging for Large Language Models