FrugalPrompt: Reducing Contextual Overhead in Large Language Models via Token Attribution

1. Problem Statement

Large Language Models (LLMs) have achieved remarkable performance by leveraging expansive input contexts. However, this verbosity creates significant inefficiencies:

• Economic & Environmental Costs: Processing redundant tokens increases monetary costs (API fees) and carbon footprints.
• Latency: Longer contexts lead to higher inference-time latency.
• Redundancy: Human language is inherently redundant (approx. 80% statistical redundancy). Much of the input consists of low-utility tokens (e.g., function words, filler phrases) that contribute little to the semantic meaning once the local context is established.
• The Gap: Current LLMs often process every token with equal weight, failing to mimic human cognitive efficiency where listeners reconstruct meaning from sparse, "telegraphic" cues.

Core Question: To what extent can LLMs reconstruct meaning from pragmatically sufficient cues rather than full linguistic explicitness, and can we filter redundant tokens without significant performance loss?

2. Methodology: FRUGALPROMPT

The authors propose FRUGALPROMPT, a training-free prompt compression framework that filters input tokens based on token attribution (saliency) scores. The pipeline operates as follows:

A. Token Attribution (Saliency Scoring)

Instead of using raw attention weights (which are known to be poor proxies for true token importance), the method employs two state-of-the-art token attribution techniques:

1. GlobEnc: Aggregates layer-wise analyses across the entire encoder using attention rollout and vector norms to quantify global token attribution.
2. DecompX: Propagates locally decomposed token representations globally, incorporating all model components, including non-linear feed-forward networks.

These methods assign a saliency score ($s_i$) to every token $t_i$ in an input sequence $T$, reflecting its relative contribution to the model's output for a specific task.

B. Ranking and Filtering

1. Ranking: Tokens are ranked in monotone decreasing order based on their attribution scores ($s_{\pi(1)} \geq s_{\pi(2)} \dots$).
2. Top-k Selection: The top $p = \lfloor \frac{k}{100} \cdot n \rfloor$ tokens are selected, where $k$ is the retention percentage (e.g., 50%, 60%, 80%).
3. Reordering: The selected indices are re-indexed in their original temporal order to preserve syntactic coherence.
4. Output: A "frugalized" prompt is generated containing only the most semantically significant tokens, discarding low-value discourse material and function words.

C. Theoretical Foundation

The paper establishes theoretical bounds for the performance degradation caused by token deletion:

• Deletion Effect: Defined as the difference in loss between the original and filtered sequence.
• Stability: Under assumptions regarding saliency upper-bounds and bounded pairwise interactions, the authors prove that the performance drop is upper-bounded by the sum of the saliency scores of the deleted tokens and a pairwise interaction term. This provides a theoretical guarantee that deleting low-saliency tokens results in predictable, bounded performance loss.

3. Key Contributions

1. Novel Framework: Introduction of a training-free, controllable prompt frugalization strategy that filters tokens based on pre-trained encoder saliency scores.
2. Theoretical Grounding: Derivation of theoretical bounds linking token retention percentages to performance stability, formalizing the trade-off between context sparsity and task accuracy.
3. Empirical Validation: Comprehensive evaluation across four diverse NLP tasks (Sentiment Analysis, Summarization, Commonsense QA, Mathematical Reasoning) and multiple model scales (from 8B to 70B parameters and proprietary models like o3-mini).
4. Insight into Task Contamination: Discovery of asymmetric performance patterns suggesting that some tasks (like classification) may suffer less from token reduction due to potential data contamination (models memorizing answers), whereas reasoning tasks rely heavily on full context.

4. Experimental Results

The study evaluated models including Llama-3 (8B/70B), GPT-3.5, Gemini 2.0 Flash Thinking, and o3-mini across retention levels of 50%, 60%, and 80%.

• Task Sensitivity:
  • Classification & QA: Highly robust to token reduction. At 80% retention, performance remained close to baseline. Even at 50%, accuracy drops were manageable (5-15%).
  • Summarization: Moderate sensitivity. Metrics like ROUGE-1 declined by 20-25% at 50% retention.
  • Mathematical Reasoning: Highly sensitive. Performance plummeted (pass@1 dropped below 15% at low thresholds) because reasoning relies on the sequential integrity of tokens and numerical connectors.
• Attribution Method Performance:
  • GlobEnc generally outperformed DecompX for classification, QA, and summarization.
  • DecompX showed superior results specifically for reasoning tasks, likely due to its ability to capture subword-level activations and linear components crucial for logical chains.
• Cost vs. Performance:
  • For smaller models (e.g., Llama-3 8B), the cost savings were negligible compared to the performance risk.
  • For larger, costlier models (e.g., o3-mini, Gemini), token reduction offered significant cost reductions with minimal performance degradation in non-reasoning tasks.
• Baseline Comparisons:
  • Random Filtering: Retaining random tokens resulted in significant performance drops, confirming that the selection of tokens matters.
  • Bottom-k Filtering: Retaining the lowest-saliency tokens caused catastrophic failure, validating the efficacy of the top-k approach.
  • Contamination Hypothesis: The fact that random filtering sometimes retained high performance in classification/QA suggests that test set answers may be memorized by models, reducing the need for full context.

5. Significance and Implications

• Efficiency: FRUGALPROMPT offers a practical method to reduce API costs and carbon footprints without requiring model retraining or architectural changes.
• Cognitive Alignment: The work bridges the gap between human communication efficiency (relying on inference and sparse cues) and LLM processing, suggesting LLMs can operate effectively with "telegraphic" inputs.
• Evaluation Integrity: The findings highlight a critical issue in LLM evaluation: Task Contamination. If models can solve tasks with only 50% of the prompt (or random tokens), it suggests the model is relying on memorized patterns rather than genuine reasoning, calling for contamination-free benchmarks.
• Future Directions: The authors propose adaptive frugalization strategies that dynamically adjust token retention based on task complexity and model confidence, moving beyond static $k\%$ thresholds.

Conclusion

FRUGALPROMPT demonstrates that a significant portion of input tokens in LLM prompts are redundant. By leveraging advanced token attribution methods to filter these tokens, the framework achieves substantial cost and latency reductions while maintaining high performance for many tasks, provided the task does not strictly require unbroken sequential logical chains (like complex math). The work fundamentally challenges the assumption that "more context is always better" and provides a theoretical and empirical basis for efficient, sparse prompting.