# Parse Trees Guided LLM Prompt Compression

arXiv: https://arxiv.org/abs/2409.15395 · HTML: https://mlsanity.com/paper/2409.15395/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in Prompt and context compression, one of 12 directions in Efficient LLM inference and serving.
- Builds on 34 of its 57 references that are in the map.
- First posted on arXiv 23 Sep 2024.

## Placed in

- Efficient LLM inference and serving / [Prompt and context compression](https://mlsanity.com/inference/prompt-and-context-compression/)

## Builds on (most cited first, 30 of 34)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [BERTScore: Evaluating Text Generation with BERT](https://mlsanity.com/paper/1904.09675/) (2019)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Qwen2 Technical Report](https://mlsanity.com/paper/2407.10671/) (2024)
- [Survey of Hallucination in Natural Language Generation](https://mlsanity.com/paper/2202.03629/) (2022)
- [Mixtral of Experts](https://mlsanity.com/paper/2401.04088/) (2024)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [Automatic Chain of Thought Prompting in Large Language Models](https://mlsanity.com/paper/2210.03493/) (2022)
- [DeepSeek LLM: Scaling Open-Source Language Models with Longtermism](https://mlsanity.com/paper/2401.02954/) (2024)
- [LongLLMLingua: Accelerating and Enhancing LLMs in Long Context Scenarios via Prompt Compression](https://mlsanity.com/paper/2310.06839/) (2023)
- [LLMLingua-2: Data Distillation for Efficient and Faithful Task-Agnostic Prompt Compression](https://mlsanity.com/paper/2403.12968/) (2024)
- [CodeNet: A Large-Scale AI for Code Dataset for Learning a Diversity of Coding Tasks](https://mlsanity.com/paper/2105.12655/) (2021)
- [Compressing Context to Enhance Inference Efficiency of Large Language Models](https://mlsanity.com/paper/2310.06201/) (2023)
- [Natural Language Processing: State of The Art, Current Trends and Challenges](https://mlsanity.com/paper/1708.05148/) (2017)
- [Chain-of-Thought Hub: A Continuous Effort to Measure Large Language Models' Reasoning Performance](https://mlsanity.com/paper/2305.17306/) (2023)
- [Learning to Compose and Reason with Language Tree Structures for Visual Grounding](https://mlsanity.com/paper/1906.01784/) (2019)
- [Learning to Compress Prompt in Natural Language Formats](https://mlsanity.com/paper/2402.18700/) (2024)
- [Discrete Prompt Compression with Reinforcement Learning](https://mlsanity.com/paper/2308.08758/) (2023)
- [DiscoScore: Evaluating Text Generation with BERT and Discourse Coherence](https://mlsanity.com/paper/2201.11176/) (2022)
- [Leveraging Structured Information for Explainable Multi-hop Question Answering and Reasoning](https://mlsanity.com/paper/2311.03734/) (2023)
- [Semantic Compression With Large Language Models](https://mlsanity.com/paper/2304.12512/) (2023)

## Built on by (most cited first, 6 of 6)

- [SCOPE: A Generative Approach for LLM Prompt Compression](https://mlsanity.com/paper/2508.15813/) (2025)
- [Large Language Models for Bioinformatics](https://mlsanity.com/paper/2501.06271/) (2025)
- [Concept than Document: Context Compression via AMR-based Conceptual Entropy](https://mlsanity.com/paper/2511.18832/) (2025)
- [Mapping Text to Multiplex Graph: Prompt Compression as L'evy Walk-Guided Graph Pruning](https://mlsanity.com/paper/2607.01241/) (2026)
- [Every Time I Hire a Linguist, Inference Costs Go Down: On Linguistic Rules as Effective Prompt Compressors](https://mlsanity.com/paper/2607.25335/) (2026)
- [PC-SubMax: Efficient Prompt Compression via Regularized Submodular Maximization](https://mlsanity.com/paper/2609.32474/) (2026)

## Abstract (arXiv)

Offering rich contexts to Large Language Models (LLMs) has shown to boost the performance in various tasks, but the resulting longer prompt would increase the computational cost and might exceed the input limit of LLMs. Recently, some prompt compression methods have been suggested to shorten the length of prompts by using language models to generate shorter prompts or by developing computational models to select important parts of original prompt. The generative compression methods would suffer from issues like hallucination, while the selective compression methods have not involved linguistic rules and overlook the global structure of prompt. To this end, we propose a novel selective compression method called PartPrompt. It first obtains a parse tree for each sentence based on linguistic rules, and calculates local information entropy for each node in a parse tree. These local parse trees are then organized into a global tree according to the hierarchical structure such as the dependency of sentences, paragraphs, and sections. After that, the root-ward propagation and leaf-ward propagation are proposed to adjust node values over the global tree. Finally, a recursive algorithm is developed to prune the global tree based on the adjusted node values. The experiments show that PartPrompt receives the state-of-the-art performance across various datasets, metrics, compression ratios, and target LLMs for inference. The in-depth ablation studies confirm the effectiveness of designs in PartPrompt, and other additional experiments also demonstrate its superiority in terms of the coherence of compressed prompts and in the extreme long prompt scenario.