Combinatorial Reasoning: Selecting Reasons
in Generative AI Pipelines via Combinatorial Optimization

Large Language Models (LLMs) are machine learning models that are trained to receive and recognize text as input and produce text as output. Distinguished from simpler language models by their immense parameter count, these models are capable of general purpose language processing tasks. GPT 3.5-turbo, the LLM used in our experiments, is part of a series of models developed by OpenAI for generating human-like natural language text (?). Many LLMs including GPT 3.5-turbo are capable of receiving and following a set of system instructions while responding to a query. System instructions differ from the user content that queries an LLM for a response, and we refer to the latter as a ‘prompt’ throughout this work. System instructions define the characteristics of the language model’s output, and constrain it to fit requested behavior (?). For our experiments, we use temperature sampling - a popular method for decoding LLMs in text generation tasks. Adjusting the temperature causes the probability distribution of each subsequent token to be modified, affecting the variability of the responses (?). High sampling temperatures result in diversity while lower temperatures provide more reproducible generations.

There have been many papers that suggest that LLMs can indeed reason (?; ?). For each subsequent revision of LLMs - GPT4 / Gemini / and Llama3, reasoning benchmarks such as BIG-Bench-Hard, HellaSwag, and MMLU show ever improving results. However, these results are not a good indicator for the autonomous reasoning capabilities of the model. In each case, the benchmarks are performed using in-context learning, with few-shot (specific examplars) or Chain of Thought (CoT), for which humans manually develop exemplars using labeled datasets to improve performance.

The latest language models do not report the zero-shot performance on these benchmark as in seen Table 1 since the performance is likely poorer than those with manual prompts. Thus we believe the next milestone for LLMs is automatic prompt generation with correct reasoning.

The main inspiration for our work comes from Yan LeCun’s review (?) which suggests multiple models need to work together to emulate general intelligence and that human brain possibly calculates a “cost function” for reasoning in a gradient-free manner - similar to combinatorial optimization.

It is well known that challenging combinatorial optimization problems arise in multiple industrial domains, such as finance, logistics, manufacturing, drug design  (?; ?; ?; ?). State-of-art solution methods often consist of a patchwork of heuristic techniques tuned to the problem class of interest. Interestingly, for many of these problems efficient mappings of the cost-function $H$ to a binary, quadratic, unconstrained formulation exist (QUBOs (?; ?)). Equivalently, the problems can be framed in “physics terms” as approximating as much as possible the ground state of an interacting, disordered classical Ising spin energy function:

where $x_{i}\in\{0,1\}$; $s_{i}\in\{-1,+1\}$ and $J_{ij}$, $h_{i}$, $Q_{ij}$ are real-valued coefficients that specify the problem instance. While the QUBO and Ising forms are equivalent, in this paper we will formulate everything in terms of the QUBO form. Clearly, the search space for the minimum of Eq. 1 scales as $2^{N}$ as the number of variables $N$ increases.

The existence of these mappings has ignited a lively research community that, in the last ten years, has devised hardware implementation of the Ising model as well as physics-inspired algorithmic strategies meant to cool down interacting spins close to their least energetic configuration. Collectively, these methods are often referred to as “Ising Machines”  (?; ?; ?) or sometimes “quantum-inspired” solvers - considering the fact that the most popular and visible methods have a connection to quantum mechanics (?; ?; ?; ?).

Digital implementation of Ising machines are currently the most scalable approach to tackle large problems. This includes GPU/FPGA emulations of solution principles inspired by oscillator synchronization (such as Kuramoto models (?), coherent optics with or without dissipation (e.g Coherent Ising Machines (?) and Bifurcation Machines (?)) and thermal relaxation (e.g. probabilistic bits (“p-bits”) variations (?; ?)). Benchmarks of these systems have consistently performed well in paradigmatic benchmarks of combinatorial optimization, especially in absence of hard constraints. Indeed, there is accumulated empirical evidence that on NP-Hard problems such as fully-connected Spin Glasses the time-to-solution scales as a stretched exponential with the increase of the number of binary variables, on typical instances (i.e. $O(N)\propto\exp(\sqrt{N})$), while other methods seem to struggle (?; ?).

Given a question from the dataset, we prepare $N$ identical input prompts (see appendix B) and query an LLM at a fixed temperature. Following the system instructions, each of the $N$ outputs will contain a set of reasons . Among these, there are duplicate reasons that are semantically equivalent. We use a Sentence Transformer from HuggingFace (all-mpnet-base-v2) to embed each reason into a normalized 768 dimensional vector. Defining a similarity metric between two reasons as the dot product of the corresponding embedded vectors, we count two reasons as the same if this metric is greater than $\bf{\zeta}$. Using this procedure as our method for counting, we can reduce the set of all sampled reasons into a smaller set of distinct reasons and a collection, $\{\bf{\gamma}_{i}\}$, of embedded vectors. We define:

• •

  $\{s$} : Set of samples each with an answer and set of reasons

• •

  $\{r_{total}$} : Set of all reasons sampled from the LLM

• •

  $\{r_{distinct}$}: Set of independent reasons selected by Sentence Transformer

• •

  $n_{i}$: The number of times each independent reason, indexed by $i$, appears in our $N$ samples

• •

  $n_{ij}$: The number of times a pair of independent reasons, indexed by $i$ and $j$, appear together within any one of our $N$ samples

These counts are the basis of combinatorial reasoning, and we use these to compute quantities essential in the QUBO mapping. From here on, we refer to independent reasons as reasons for the sake of brevity. Using these counts as well as the acquired embeddings, we denote $m_{i}$ as the average similarity that each reason shares with every reason, i.e.

Finally, to clarify our notation, for a given collection $\{\xi_{\mu}\}$, we use $\bar{\xi}$, $\bar{\bar{\xi}}$, and $\delta\xi$ to denote the mean, median, and standard deviation.

This stage processes deterministically the collection of answers and their distinct reasons to formulate a quadratic unconstrained integer optimization problem. The procedure that we decide to investigate is inspired by the QUBO mappings to Markowitz portfolio optimization (?) where the goal is to select the optimal assets (i.e. reasons, in our case) out of a finite universe (all distinct reasons) maximizing some metric. Importantly, this is just one of the many possible cost-functions that could be designed to try to capture the correlations between good and consistent reasons outputted by an LLM after an ensemble of queries, as it will be discussed in Section 5. Each distinct reason is associated to an integer variable $z_{i}$. The integer bound for the variables is a parameter to be chosen as the maximum power of two in order to leverage the binary encoding $z_{i}=\sum_{w=0}^{W-1}2^{w}x_{iw}$ where $x_{iw}$ are binary variables. We now construct two functions that will compose a total objective $H=-(L+Q)$. The first term is meant to select reasons based on their frequency of appearance $n_{i}/N$:

where $\mathrm{p}_{i}$ is a measure of “popularity”, i.e. of the relative deviation with respect to the mean frequency of appearance of a reason. $\mathrm{r}_{i}$ is a measure of the standard deviation module around the frequency (in analogy to the concept of risk in portfolio optimization):

The real parameters $\mu$ and $\alpha$ needs to be chosen empirically. If this was the only objective function (i.e. $H=-L$) then $z_{i}$ will either be $0$ or maxed out depending on whether $l_{i}(\mu,\alpha)$ is positive or negative.

We measure the potential relationship between two reasons by evaluating $c_{ij}$ as the connected correlation between two reasons defined as:

This function assumes values between $-1+N^{-1}$ and $1/4$. It is zero if one of the two reasons appears all the time (meaning it is trivially right - its selection should be handled by linear terms). It is negative when reasons $i$, $j$ are frequent but rarely appearing in the same answer $s$. It hits the maximum positive value when reasons $i$ and $j$ appears all the time together but are not necessarily obvious ($n_{i}=n_{j}=N/2$).

Using the connected correlation functions, we construct the second term in $H$ to be sensitive to the correlation between reasons that appear jointly more or less frequently than the average:

The parameter $\beta$ is a real valued hyperparameter of the mapping, appearing as a prefactor to the standard deviation of $c_{ij}$. For $\beta=0$, if $c_{ij}$ is positive then $q_{i,j}$ will be positive and increasing with the number of times we observe reasons $i$ and $j$ occur together when this number is greater than the observed average. In a symmetric way, it will be negative and decreasing if $c_{ij}$ is negative and the joint appearance is less frequent than the average. The $L+U$ function is straightforwardly converted to QUBO form Eq. 1 by means of the binary encoding formula:

Despite the simplicity of $L$ and $Q$, it was empirically determined in our study that it is beneficial to use a slightly modified version of the function $\tilde{L}$ introducing flexibility on the mapping of the single non-interacting reasons. Per result of trial and error in our early investigations, the popularity portion was modulated favoring “crucial” reasons with low semantic similarity, and the risk portion of the mapping was modified with an additional tuning parameter $\kappa$, as well as other quadratic terms in $x_{iw}$ to modify the integer encodings:

The final QUBO that we send to the solver is then tackling the objective function $\tilde{H}=-(\tilde{L}+Q)$.

The QUBO instance is processed by an Ising machine configured with a pre-defined parameter setting strategy (?) aimed to find the most appropriate solution to the $x_{i}$ variables. Ideally, the solver identifies the global optimum of $\tilde{H}$, i.e.

however, an approximate solution might be sufficient as discussed in Section 6.1. We denote as $\{r_{selected}$} the set of reasons selected by QUBO solver. From the binary encoding formula we obtain the $z_{i}$ variables. We then compose a list including all reasons such that $z_{i}>0$ in the returned solution, and we associate to each of them a real weight $w$-$value=z_{i}/Z$ where $Z=\sum_{i}z_{i}$.

Once the best candidate solution to the QUBO problem has been found, it is mapped back to set of reasons $\{r_{selected}$} each prepended with their $w$-$value$. The LLM is instructed to treat the $w$-$value$ as a level of relative importance for each reason. These reasons are sorted according to their $w$-$value$s (highest first) and alphabetically. The concatenated string is used to form a prompt (see appendix B). This final prompt inherit the benefits of CoT thanks to these additional reasons, and is used to query the LLM in a zero-shot fashion at temperature = 0 (greedy decoding).

We list the following straightforward improvement ideas to the baseline framework: