Naive Bayes-based Context Extension for Large Language Models

Jianlin Su, Murtadha H. M. Ahmed, Wen Bo, Luo Ao, Mingren Zhu, Yunfeng Liu

Abstract

In-Context Learning (ICL) allows Large Language Models (LLMs) to adapt to new tasks via few-shot demonstrations. However, the effectiveness of ICL is fundamentally limited by the model's context window and the quadratic computational cost of self-attention. We present Naive Bayes-based Context Extension (NBCE), a training-free framework that enables LLMs to utilize significantly more demonstrations than their native hardware limits allow. By partitioning examples into independent windows and aggregating their predictions using a refined Bayesian approach, NBCE achieves linear scaling and superior performance on complex, many-shot tasks without requiring additional fine-tuning.

Introduction

The "magic" of modern LLMs often stems from In-Context Learning, where a model performs a task simply by observing examples provided in the prompt. Despite its power, ICL faces a hard ceiling: the context window. Most models possess a fixed limit (e.g., 2,048 or 4,096 tokens), and the cost of processing these tokens grows quadratically. Consequently, providing a model with 100+ examples to improve accuracy on complex tasks is often impossible or leads to massive latency.

Previous attempts to solve this involved expensive retraining or architectural modifications. NBCE offers a different path, scaling ICL to "many-shot" scenarios efficiently by modifying the inference process rather than the model itself.

Methodology

NBCE operates on the principle of independent evidence. Instead of concatenating all demonstrations into a single, massive prompt, the framework breaks the process into four distinct stages:

  1. Window Partitioning: Demonstrations are divided into multiple equal-sized "windows," each small enough to fit comfortably within the model's native context limit.
  2. Independent Processing: The LLM processes each window—containing a subset of examples and the test query—independently. This shifts the computational complexity from quadratic to linear relative to the total number of examples.
  3. Entropy-based Voting: To identify which examples are most relevant to the query, NBCE employs a voting mechanism. It calculates the entropy of the model's output for each window; windows with the lowest uncertainty (lowest entropy) are prioritized in the final calculation.
  4. Bayesian Integration: The framework uses a refined version of Bayes' theorem to combine probability distributions from all windows.

A critical innovation in this integration is context-less subtraction. By subtracting the model's "prior" knowledge (its prediction given an empty context) from the combined conditional probabilities, the framework forces the model to rely more on the provided demonstrations and less on its internal pre-training biases.

Experimental Setup

The researchers evaluated NBCE across a diverse battery of benchmarks to test its versatility:

  • Text Classification: 15 datasets covering sentiment analysis (SST-2, CR), topic classification (AGNews, DBPedia), and intent detection (BANKING77, CLINIC150).
  • Reasoning and General Knowledge: 5 datasets including HellaSwag (commonsense), PIQA (physical reasoning), and MMLU.
  • Model Architectures: The framework was tested on GPT-2 (Large/XL), LLaMA (7B, 13B, 30B), and OPT (1.3B, 6.7B, 13B).

Key Results and Insights

Superior Performance in Many-Shot Scenarios

NBCE consistently outperformed existing methods like Parallel Context Windows (PCW) in many-shot settings. For example, on the TREC dataset using LLaMA-7B with 9 windows, NBCE achieved 88.8% accuracy, whereas PCW only reached 41.2%. The framework proved particularly effective for tasks with a high number of possible labels, such as CLINIC150 (150 classes), where the ability to see more examples is crucial for coverage.

Stability and Scaling

Standard ICL often becomes unstable as the number of shots increases, with performance fluctuating based on example ordering. NBCE maintained high stability across 30 different random seeds. Furthermore, the benefits of NBCE scaled with model size; larger models like LLaMA-30B showed more significant and stable improvements compared to smaller variants.

Efficiency and Bias Reduction

By treating windows independently, NBCE allows models to effectively "see" tens of thousands of tokens worth of context that would otherwise exceed memory limits. Additionally, the context-less subtraction mechanism successfully "de-biased" the models, ensuring that the final output was driven by the provided evidence rather than the most common words in the model's training data.

Limitations and Future Work

While NBCE is highly effective for classification and short-answer tasks, it has limitations:

  • Sequential Dependencies: Because it treats windows as independent, it is less suited for tasks where the order of information is vital, such as narrative tracking or complex code generation.
  • Task Saturation: On simpler completion tasks (like HellaSwag), adding more examples via NBCE occasionally led to diminishing returns, suggesting that some reasoning tasks have a saturation point where extra context no longer helps.

Future research may explore adapting NBCE for fine-tuning environments or developing methods to handle tasks that require more global, interrelated context across windows.

Summary updated

BibTeX
@inproceedings{su2024naive,
  author = {Jianlin Su and Murtadha H. M. Ahmed and Wen Bo and Luo Ao and Mingren Zhu and Yunfeng Liu},
  title = {{Naive Bayes-based Context Extension for Large Language Models}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2024},
  doi = {10.18653/v1/2024.naacl-long.431},
}
Figure