Naive Bayes-based Context Extension for Large Language Models

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

Introduction

In-Context Learning (ICL) has revolutionized how we interact with Large Language Models (LLMs), allowing them to adapt to new tasks through a few demonstrations. However, standard Transformer architectures suffer from a "context bottleneck" where computational costs scale quadratically with input length. This typically limits models to a fixed context window (e.g., 2048 tokens), restricting the number of examples that can be provided.

Naive Bayes-based Context Extension (NBCE) addresses this limitation. It is a training-free framework that enables LLMs to utilize significantly more demonstrations than their hardware-defined limits allow. By processing groups of examples in parallel and merging their predictions using a refined Naive Bayes formula, NBCE achieves superior performance and stability without expensive fine-tuning.

Methodology: The NBCE Framework

NBCE treats context extension as a probability estimation problem. The process involves four key steps:

  1. Window Splitting: Demonstrations are split into multiple "windows," each fitting within the LLM's native context limit.
  2. Parallel Processing: The LLM processes each window independently, keeping complexity linear relative to the number of examples.
  3. Naive Bayes Refinement: Outputs are combined based on the assumption that context windows are conditionally independent given the target output.
  4. De-biasing and Pooling: The final log-probability is calculated by subtracting the "context-less" prior to remove pre-training biases and using an entropy-based "Max Pooling" mechanism to select the most confident window.
The NBCE architecture: Parallel processing of context windows followed by a Naive Bayes-based merging of log-probabilities.

The core formula used is: $$\log p(T|S_1, \dots, S_n) = (\beta + 1)P[\log p(T|S)] - \beta \log p(T) + \text{constant}$$ where $\beta$ is a hyperparameter (typically 0.25) and $P$ represents the pooling mechanism.

Key Results and Insights

The researchers evaluated NBCE across 15 classification and 5 reasoning datasets using models like LLaMA and GPT-2.

Performance at Scale

NBCE consistently outperformed Vanilla ICL and other baselines like Parallel Context Windows (PCW). While PCW often sees performance degradation as more windows are added, NBCE remains stable or improves. Larger models, such as LLaMA-30B, showed the most substantial gains, indicating that NBCE effectively leverages the latent reasoning of larger LLMs.

Handling High-Cardinality Tasks

A significant finding was NBCE's effectiveness in tasks with many labels. There is a robust positive correlation between the number of unique classes in a dataset and the performance improvement provided by NBCE.

Correlation between the number of classes in a task and the performance improvement gained by using NBCE.

Conclusion

NBCE provides a scalable, training-free solution to the context bottleneck in LLMs. By assuming independence between context windows, it enables massive parallelization and effective de-biasing. While the independence assumption may limit its use in tasks requiring strict sequential reasoning (like long-form narrative generation), its success in classification and reasoning benchmarks makes it a powerful tool for extending the utility of existing LLMs.

Summary updated

BibTeX
@inproceedings{su2024naive,
  author = {Jianlin Su and Murtadha H. M. Ahmed and Bo Wen 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