  For language model classification, would you prefer having only one workable
class or having every class working? The latter makes more practical uses.
Especially for large language models (LLMs), the fact that they achieve a fair
overall accuracy by in-context learning (ICL) obscures a large difference in
individual class accuracies. In this work, we uncover and tackle language
models' imbalance in per-class prediction accuracy by reconceptualizing it as
the Contextual Oddity Bias (COBias), and we are the first to engage nonlinear
integer programming (NIP) to debias it. Briefly, COBias refers to the
difference in accuracy by a class A compared to its ''odd'' class, which holds
the majority wrong predictions of class A. With the COBias metric, we reveal
that LLMs of varied scales and families exhibit large per-class accuracy
differences. Then we propose Debiasing as Nonlinear Integer Programming (DNIP)
to correct ICL per-class probabilities for lower bias and higher overall
accuracy. Our optimization objective is directly based on the evaluation scores
by COBias and accuracy metrics, solved by simulated annealing. Evaluations on
three LLMs across seven NLP classification tasks show that DNIP simultaneously
achieves significant COBias reduction ($-27\%$) and accuracy improvement
($+12\%$) over the conventional ICL approach, suggesting that modeling pairwise
class accuracy differences is a direction in pushing forward more accurate,
more reliable LLM predictions.
