Understanding complexity via network theory:
a gentle introduction

Vaiva Vasiliauskaite1,2 and Fernando E. Rosas1,3,4

Centre for Complexity Science1

Theoretical Physics Group, Department of Physics2

Center for Psychedelic Research, Department of Brain Science3

Data Science Institute4

Imperial College London, London SW7 2AZ, U.K.

###### Abstract

Network theory provides tools which are particularly appropriate for assessing
the complex interdependencies that characterise our modern connected world.
This article presents an introduction to network theory, in a way that doesn’t
require a strong mathematical background. We explore how network theory
unveils commonalities in the interdependency profiles of various systems,
ranging from biological, to social, and artistic domains. Our aim is to enable
an intuitive understanding while conveying the fundamental principles and aims
of complexity science. Additionally, various network-theoretic tools are
discussed, and numerous references for more advanced materials are provided.

##  1 Introduction

_Interdependency_ , represented by links that connect different elements, is a
fundamental notion that is widely applicable when studying complex systems.
For example, a group of friends are connected via friendship links, whereas
cities are linked via train lines. Similarly, an entity—a city, a person, a
cell—can be linked to other entities in a wide variety of ways: physical
vicinity, friendship, common genes, shared ideology, and so on. Interestingly,
underneath the diversity of entities and variety of their linkages, there tend
to exist interesting commonalities in the organisational structure. In fact,
these complex, seemingly random systems, as dissimilar as biological,
economic, sociological and physical systems, seem to share structural
regularities. It is those regularities what _network theory_ attempts to
capture.

Network theory also provides efficient tools to exploit the so-called “big
data”. While communication technologies enable the gathering of unprecedented
(and ever-increasing) amounts of information, data by themselves don’t tend to
reveal meaningful insights easily. Why there is so much inequality in the
distribution of wealth in many societies? What makes some diseases spread much
faster than others? How important is a particular species for maintaining the
stability of an ecosystem? These questions are challenging as they involve not
only properties of the object itself, but also its relationships with the
surroundings. Addressing such questions is where network theory methods,
combined with big data, shine at their fullest.

Because network theory is built upon analytical foundations, some mathematical
knowledge is often needed to access many of the available resources. To help
fill this gap, this article provides a gentle introduction to network theory
without mathematical formulas. We give an intuitive presentation which avoids
unnecessary technicalities, yet still conveys the spirit and fundamental
principles of complexity science through the network viewpoint. Hence, it is
our hope that this overview provides the reader with conceptual and
suggestions for practical applications, and will enable them to employ this
framework in order to make sense of our complicated interconnected world.

The rest of this article is organised as follows. First, Section 2 introduces
the fundamental notions of complexity science, and sets the conceptual basis
for the rest of the review. Then Section 3 explores the fundamental principles
of network theory, and discusses a set of examples that illustrate these
principles. Section 4 presents tools to characterise different networks and
better understand their various properties. Section 5 reviews a number of
network architectures, which are used for network modelling. Finally, Section
6 concludes this article with future perspectives of network theory, gives
suggestions of further reading, and also reviews a number of limitations of
this approach.

##  2 Complexity

In order to prepare the ground for subsequent sections, here we introduce some
fundamental concepts from complexity science. In the following we discuss the
difference between complex and complicated, the relationship between
reductionism and complexity, and the role of synergy and emergence. Please
note that some of our terminology is not standard.

###  2.1 Complicated does not implies complex

Complex and complicated might sometimes be used interchangeably in our daily
life; however, it is useful to draw a technical difference between these two
terms.

We define a system to be complicated if it cannot be characterised by any
short description. As descriptions might depend on the language employed, it
is important to distinguish between apparent and intrinsic complicated-ness:
the former takes place when a long description is a consequence of an ill-
suited language, while the latter corresponds to the case when there is no
language that allows a short description. A classic example of apparent
complexity is describing a square shaped wave: using Fourier analysis requires
an infinite number of sine-waves to describe a square wave, while an
alternative description based on modern wavelet analysis is much briefer. In
contrast, intrinsically complicated objects cannot be properly described
succinctly in any language.

A simple approach to study intrinsic complicated-ness is based on the notion
of “inability to compress,” this being related to high Shannon entropy, c.f.
[1]. However, this approach does not work directly on concrete objects but
over models that may generate such objects. Unfortunately, inferring models
from objects always requires strong assumptions, and hence any study based on
Shannon’s entropy depends critically on them. A more direct approach to study
complicated-ness that avoids such assumptions relies on the idea of Kolmogorov
complexity, which quantifies the length of the shortest computer program
capable of generating the object of interest [2]. Unfortunately, the
Kolmogorov complexity is usually uncomputable in most practical scenarios, and
hence one needs to rely in approximations [2].

###  2.2 Complexity science as a complement of reductionism

A big portion of contemporary science is driven by the spirit of reductionism,
which under the motto of divide et impera studies hard problems by dividing
them into easier problems. When studying a multi-agent system, reductionist
approaches first focus on understanding the nature and properties of each
agent in isolation, and only when this is solved, it proceeds to see how
agents act together.

While reductionism has provided satisfactory results in a wide range of
scenarios, it has proven ineffective in a number of important problems. For
example, claims exist that a number of important social and economical issues
of our modern world—including climate change and wealth inequality—are
unlikely to be solved by reductionist approaches [3]. As another prominent
example, some neuroscientists argue that high brain functions and
consciousness might be related to irreducible relationships that take place in
the orchestrated activity of a number of different brain areas, a result that
would be invisible to reductionistic approaches [4, 5].

Complexity science provides a view that complements reductionism (see Fig. 1).
In effect, while reductionism studies first the parts and then their
interactions, complexity science first considers the patterns of interactions
to only then try to understand individual agents. Accordingly, we define a
complex system as one that cannot be fully understood via reductionist
analyses, being better suited to analyses that take as a start point the
patterns of interactions.

Figure 1: A network might represent an abstract multi-agent system, and the
red and blue arrows illustrate reductionism and emergentism. Reductionism
corresponds to the red arrow, which builds up from individual agents;
emergentism is represented by the blue arrow, which starts considering
patterns of collective interactions and only afterwards attempts to understand
specifics aspects of the system.

###  2.3 Synergy and networks

Technically, _synergistic phenomena_ are those than can be seen in the whole
of a system but not in the parts [6, 7]. As a matter of fact, it is the
presence of synergistic phenomena the reason why reductionist approaches
sometimes fail. Therefore, synergy lies at the very heart of complex systems.

Some synergistic phenomena are especially persistent, even gaining apparent
agency. Those cases are referred to as _emergent_ , which alludes to the fact
that macroscopic variables with apparent agency “emerge” spontaneously from
the underlying substrate. The literature about emergent phenomena is diverse
and unclear, and the subject is more discussed in the literature of philosophy
than in quantitative sciences. For good introductions to the theory of
emergent phenomena please refer to [8]. Recent attempts to quantify emergence
include the work reported in [9, 10, 11].

A popular method to study collective properties associated with synergistic
phenomena is network theory. Networks allow us to focus less in the matter and
more in the patterns, i.e. in the “shape” of the arrangement of
interdependencies across a system of interest. How this is done, and it
implications, is the subject of the rest of this text.

##  3 Networks

This section covers the fundamental concepts of network theory. After a brief
introductory discussion outlined in Section 3.1, in Section 3.2 basic
definitions of complex network analysis are introduced. In Section 3.3 we
present a selection of real-world networks, which in many ways motivate and
illustrate the main concepts introduced in previous subsections.

###  3.1 What is a network?

A network is often not an object in and of itself, but a way to represent a
system. In effect, we believe the question “is this a network?” is normally
ill-posed, whereas “would it make sense to model this as a network?” would be
a more useful one. In effect, in this presentation we consider networks to be
a tool or a metaphor, i.e. a way of describing systems composed of many sub-
units. Hence, a network is an abstraction that depicts the interdependencies
that exist in a given system of interest.

Just as a map neglects aspects of the territory in order to focus on
particular features of interest, a network takes away most of the richness of
individual sub-units of the system and only retains the structure of their
interdependencies. Networks allow us to study the collective properties of
these dependencies. Additionally, as seemingly unrelated systems might have
similar networks of interdependencies, networks sometimes allow us to
establish non-trivial relationships between systems that share similar
dependency structures.

###  3.2 Basic definitions

A network is a collection of vertices and edges: a vertex (or a node)
represents a particular sub-unit of the system, and edges connect sub-
units/vertices that interact with each other. Networks, hence, depict
bilateral relationships between objects. Note that in general each vertex has
a unique identity, but no further internal structure.

Many analyses start from a dataset, which in itself has no network
representation. Therefore, a crucial initial task for a researcher is to
define nodes and a relationship criterion to establish edges. The goal is to
find a representation which beholds the information needed to address a
particular question of interest. The reduction of data that takes place when
building a network representation leads to an inevitable loss of information.
This is a price one needs to pay in order to obtain a simplified
representation of the interdependencies seen in the data.

Networks are studied in mathematics under the name of graphs. In effect, graph
theory is a branch of pure mathematics that is concerned with general
properties of graphs. Network science builds on top of graph theory, greatly
expanding its scope by including methods and approaches from statistical
physics.

The type of a network described so far is the most basic: there is only one
type of node, and the connections between nodes are binary: an edge either
exists or does not. However, in some situations one might want to employ more
sophisticated models which provide more flexibility. For example, one can
assign values to the network’s edges and obtain a weighted network. The weight
of an edge represents its strength: the larger the weight, the stronger the
connection between nodes. Moreover, one can allocate a sign to these values,
and generate a signed network whose edges can have either positive or negative
weights. Similarly, assigning directionality to edges makes a network
directed. Furthermore, if one wants to describe non-binary relations between
nodes, hypergraphs can be employed. In such network an edge joins more than
two nodes together. Lastly, multidimensional networks entail several different
types of connections.

Labels and categories can also be added to nodes. For example, bipartite
networks consist of exactly two types of nodes, connected in such a way that
edges can only take place between nodes of different types. Multilayer
networks are a generalisation of bipartite networks in which multiple types of
nodes exist. Finally, one can also assign a location to the nodes (and edges)
and obtain a spatial network.

The definition of a network is very flexible. Thus this approach enables one
to model a wide range of real systems. Given a complex system one simply needs
to find the most natural network representation.

###  3.3 Examples of networks

There are numerous examples of complex systems that can be modelled as
networks. Network analysis has been useful in studies of technological,
social, biological, chemical, physical structures and systems.

Social scientists have used the concept of a social network since the early
$20^{\textrm{th}}$ century. In effect, many network analysis tools and
methodologies root back to and build upon sociometry (or social network
analysis, SNA), a term coined by social scientists for a study of complex
social systems [12, 13]. A social network is typically a network composed of
individuals (or groups of individuals) as nodes and their interactions,
represented as edges [14]. Perhaps the simplest social network is composed of
individuals, represented as vertices, joined by edges if they are friends—a
so-called “friendship” network. However friendships are not the only type of
social relations between individuals. One can similarly model collaborative
relationships between artists [15] or scientists [16, 17, 18], or even
evaluate how much our genes impact our social interactions [19]. In an
organisation, people usually have a position in an official hierarchy at work,
so a worker may be linked to his/hers boss, or linked to people that sit
nearby in the office. It has been shown that important links could come from
occasional meetings of people in other parts of the organisation or even in
rival companies (the so-called “strength of weak ties” [20]).

Networks are also useful for characterising the interdependencies that take
place in biological systems. The structures we observe in nature unfold layers
upon layers of complexity, ranging from microscales that explain cellular
behaviour, to macroscales where they give insights about animal interactions
in an ecosystem [21]. Given high-throughput experimental results, nowadays
scientists are able to model inter- and intra-cellular interactions, relations
of genomes, and observe biomass flow from one species to another as food webs.
For instance, protein-protein interactions have been extensively studied as
networks [22, 23]. In this network, proteins are represented as nodes, which
are pairwise connected if they participate in the same interaction.

Let us move from “natural”, organic networks, to cyber-networks, which are
numerous as well. A remarkable example of a digital network is the Internet
(see Fig. 2 for visualisation). In this network, nodes are physical computers,
linked by cables. The large-scale topology of the internet is complex, as it
is a self-organizing system whose properties cannot be traced back to any
global blueprint or chart [24, Chapter 3]. The World Wide Web is a virtual
network of information, living on the structure of the Internet. One can find
many different types of networks in this system. Perhaps the most obvious one
is the network of web pages as vertices, in which an edge indicates a
hyperlink from one web page to another. Alternatively, one can look at a
“semantic” network of the World Wide Web in which two web pages are connected
with an edge if their most common words are similar. Lastly, one can link two
pages with an edge if they both point to the same third web page, to produce a
“co-citation” network.

One may also construct numerous networks by considering spatial positions of
some elements—spatial networks, described briefly in 3.2. A so-called “urban”
network can be constructed by considering street intersections as network
nodes. One obvious network of such nodes can be obtained by calling portions
of streets between intersections to be edges. A bit less-intuitive is a street
network, in which the spatially straight street sections are vertices and
intersections between them are edges.

These are just a few examples of the numerous systems that can be studied as
networks.

Figure 2: Partial map of the Internet based on data from November
$24^{\mathrm{rd}}$ 2003, taken from http://opte.org/maps (accessed on February
$5^{\mathrm{th}}$ 2020). Each line is drawn between two nodes, representing
two IP addresses. The length of the line is indicative of the delay between
the two connected nodes. Lines are colour-coded based on Class A allocation of
IP space (Asia Pacific - Red Europe/Middle East/Central Asia/Africa - Green
North America - Blue Latin American and Caribbean - Yellow RFC1918 IP
Addresses - Cyan Unknown - White).

##  4 Features, properties and tools for networks

A network model enables mathematical and numerical analyses which give
insights into the observed structures. One can use them to understand
questions related to the origin of the network (what processes lead to the
observed network structure?), evolution of the network (i.e. its growth in
time or space), dynamical processes on the network (e.g. epidemics). The tools
presented in the following discussion may also help characterise different
types of networks and allow us to study their emergent properties.

Results of a given analysis strongly depend on the scale at which the network
is studied. If one looks at a network at the level of individual node
relationships, macroscopic, local, and somewhat static properties about the
network are revealed. On the other hand, looking at higher-order structures
one gains information about non-local interaction of nodes, which can further
be linked to some macroscopic dynamics. So it may be possible to demonstrate
how the microscopic (bilateral) interactions lead to cooperative phenomena and
emergent properties of some dynamical processes, such as diffusion,
broadcasting, synchronisation, if present in the system.

We finish this section by discussing how, having learnt about the structure of
the observed networks, synthetic networks that mimic some certain important
features can be built.

###  4.1 Visual inspection

A simple first step that often helps towards understanding a particular
network is direct visual inspection. Besides being a sanity-check of the data,
visual inspection can provide some basic insights about the network of
interest. In effect, a well-done presentation of any data can give useful
insights, or at the very least be visually pleasing. Please note that network
visualisation is both an art as well as a science; automated methods alone
rarely produce the most effective visualisations.

Network visualisation software are numerous, much of which are also freely
available online. Some examples of stand-alone software for network
visualisation inlude Gephi, Graphviz, Neo4j, Visone, nodexl, cytoscape.
Various network-oriented libraries, available in different programming
languages also include visualisation functionality. Examples of such libraries
are Boost (C++), igraph (Python and R), networkx (Python), JUNG (Java).

Representing a network graphically is a more complicated task than it may seem
first, as vertices and edges do not in general have any coordinates in space.
When drawing them one may place vertices anywhere, provided that one connects
vertices faithfully. However, one might quickly find crossing edges, and
eventually the visualisation can easily become confusing or even misleading.
Large network visualisations, which sometimes don’t convey much information,
are sometimes called “spaghetti monsters” (the reader can decide if Fig. 2
falls into this category or not). These monsters can still be analysed using
other techniques, which are discussed below.

###  4.2 Differentiation

The network structure describes how nodes are related directly through edges
and indirectly through chains of relationships. So a natural question to ask
is if nodes group together in differentiated clusters/communities. The
“grouping” of nodes can be assessed in different ways, some of which are
explored in what follows.

Here we present several network observables that allow us to differentiate
network structures. On macroscales, one can compare the amount of clustering
of nodes into groups via the modularity; whereas on microscale the information
about the density of triangles as well as motifs reveals the characteristic
local structure of a network. From these complementary angles, these
approaches provide some light over the network’s functional abilities.

####  4.2.1 Clustering coefficient and motif analysis

Measuring a clustering coefficient is a common first step towards assessing
the structure of the links within a network. This quantity captures the
propensity of nodes that are connected to a common node to be connected
between themselves as well. For instance, in a friendship network, if “a
friend of a friend is also a friend”, it is represented by a triangle.
Therefore, the clustering coefficient operationalises this notion by counting
for “triangles” (triples of nodes, all connected pairwise with edges).
Technically, the clustering coefficient is defined as the ratio of actual
triangles in a network and the number of potential triangles—three nodes
connected by two or three edges. Social networks tend to have quite high
clustering coefficients [25]. The values of the clustering coefficient can
range from zero to one, but for many (although not all) real world networks,
the observed clustering coefficient is significantly larger than one would
expect by chance. For instance, a co-authorship network of physics researchers
has a clustering coefficient of 0.45. This value indicates that there is a
$45\%$ probability that two neighbours of a vertex are neighbours themselves.
If edges were placed at random in the network, the clustering coefficient
would have yielded a mere 0.0023 [25]. Other networks that show larger-than-
expected clustering coefficients include a film actor collaboration network
[26] and a network of company directors [27]. Some networks, that do not seem
to have a significantly clustered structure include a network software package
dependencies, and metabolic networks [25, Table 8.1].

Triangles, used in the aforementioned clustering coefficient, are not the only
small groups of vertices that are commonly encountered in networks. Distinct,
dominant (and usually small) structures of any form are collectively called
motifs. A motif can be any set of nodes, connected in a specific way, given
that we observe this arrangement in our network repetitively. The over-
representation of specific motifs in networks, such as gene regulatory
networks and neural networks, may signal their importance for the organisms
involved [18]. In particular, they may act as “circuit elements”, such as
filters, important to perform certain tasks [25].

To study motifs, one first defines the motifs of interest and counts their
appearance in a network of interest. To assess if these motifs are appearing
significantly often, one counts their occurrence on a randomised network which
acts as a null model111In randomised networks one does not expect to see any
preponderance of particular patterns; see Section 5 for a discussion on random
graph models.. One can declare the motif to be present in the network if the
number of occurrences is much higher than in the randomised networks.

Motifs have recently gathered much attention as a useful concept to uncover
structural design principles of complex networks. Indeed, very frequently
occurring motifs in networks such as genetic regulatory network are thought to
be related to its functional properties and perhaps they are an the result of
evolution, beneficial for the organisms involved [28]. More specifically, much
experimental work has been devoted to understanding network motifs in gene
regulatory networks. These networks control which genes are expressed in a
cell in response to some biological signals.

####  4.2.2 Modularity and community detection

If the clustering coefficient of a network varies significantly from one
region to another in the network, it is likely that the network is modular.
The characteristic feature of such networks is the presence of densely
connected groups of vertices, known as communities or clusters, with sparser
connections between these groups. Many real networks exhibit modular
structures, including social networks, computer networks, and metabolic and
regulatory networks [26].

To quantify how well defined these groups are, one may calculate the value of
a so-called modularity function. The idea behind this modularity measure is
that true community structure in a network corresponds to a statistically
surprising arrangement of edges. So in modularity the number of edges falling
within groups is compared to the expected number in an equivalent network with
edges placed at random [26] (other null models can be employed; we will
discuss some of them in Section 5). The more “surprising” the arrangement of
edges, the larger the modularity score. Community is intuitively defined as a
group of nodes which are more closely connected with each other, rather than
with the rest of the network.

Social networks are typical examples of graphs with communities. The word
“community” itself refers to a social context. People naturally tend to form
groups, within their work environment, family, friends. We show an example of
a network with apparent communities in Fig. 3. Biological networks also
exhibit modular structures. For instance, protein interaction networks,
fundamental for multiple processes in any cell, are also composed of parts
that are more interconnected and less so. Communities are thought to
correspond to functional groups, for instance, proteins having the same or
similar functions, which are expected to be involved in the same processes
[29]. Some other examples of modular networks are: the World Wide Web,
scientific collaborator networks, mobile phone communication networks [30],
and networks from social media websites such as Twitter or Facebook, see
Section 17 in [29].

Figure 3: An example of a random modular network, composed of 100 nodes which
have an average degree of 10.3. Degree distribution is Poissonian. Nodes in
the same community are of the same colour. The network was generated using the
methodology in [31], and communities were found using Louvain algorithm [30]).
Modularity of this partition is $0.63$.

The ability to discover groups or clusters can be a useful tool to reveal
structure and organisation within networks at a scale larger than that of a
single vertex, or a triangle, or a small motif. If a network is small, a
visual inspection is enough to find if communities are in the network and if
present, what distinguishes the different groups. When the networks are large,
algorithms are more practical to find where the communities lie.

There are many different approaches to community detection. A classic, hard
algorithmic problem, called graph partitioning, is a close predecessor of
community detection algorithms. It is assumed that the number of underlying
communities and so their typical size is known. The goal of graph partitioning
is to find a partition of nodes such that the edges between those communities
are minimal. Finding the exact solution is essentially impossible (it is in
the category of NP-hard problems), so typically solutions to the graph
partitioning problem are derived using heuristics or approximate algorithms.
Graph partitioning is a fundamental issue in parallel computing, circuit
partitioning and layout, and in the design of many serial algorithms,
including techniques to solve partial differential equations and sparse linear
systems of equations. For current state-of-the-art and the review of
traditional graph partitioning methods please refer to [32].

When the number and size of communities are not known, the task we have at
hands is known as community detection. An early attempt at identifying
communities in a network was made by Girvan and Newman [33], who developed
their homonymous algorithm based on edge betweenness centrality for uncovering
a hierarchical community structure in networks. Their algorithm is based on
the maximisation of a modularity function, which compares the network to a
null model. If the found communities are “high-quality”, the modularity
function returns a high score. To find “the best” communities, optimisation
algorithms are used, such as Louvain [30], Infomap [34], and so on.

One of the criticisms that community detection methods get is that some
optimisation algorithms are subject to a resolution limit [35]: sometimes
communities might remain undetected, whereas other times nodes might be
grouped together even if they should not belong to the same community.
Alternatively, methods based on machine learning are useful when the number of
communities is known [36]. To address the number of communities, recent work
of Newman and Reinert [37] have proposed methods based on inference to
estimate the number of communities in a network.

###  4.3 Integration

A concept that is complementary to differentiation is integration, which
refers to the “well-connectedtedness” and “navigatability” of the network.
Similar to the differentiation of a network, the intuitive notion of
integration can be implemented in a number of different ways. We now examine
some of them.

####  4.3.1 Shortest paths

A walk in a graph is a sequence of vertices, such that there is an edge from
each vertex to the next vertex in the sequence. Intuitively, one can imagine a
walk as the “trail of a walker” on the graph. A walker is allowed to make a
step from one node to the next only if there is an edge connecting the nodes.
A path is a walker’s trajectory where she/he doesn’t visit any node twice. One
can characterise a given network in different ways according to various types
of paths. For example, one can find the paths which are the shortest in length
between given nodes.

The properties and statistics of various paths yield interesting insights on
particular networks. For instance, the distribution of the shortest paths
between nodes relates to the efficiency of communication in our network. More
so, the longest of all shortest paths, the diameter of a network, represents a
linear size of a network. Small diameter is also thought to be related to
large heterogeneity of degrees and small amounts of synchronisation in the
network [38]. Furthermore, as we will see in Section 5, so-called “small-
world” networks are defined as networks with large clustering coefficient, yet
small diameter.

To study dynamics of processes on networks one can employ various stochastic
methods, for example random walk techniques. Random walks are often used as a
model for diffusion, and there has been intense research on the impact of
network architecture on the dynamics of random walks. The finiteness of a
network—along with properties such as degree heterogeneity, community
structure, amongst others—can make diffusion on networks both quantitatively
and even qualitatively different from diffusion on regular or infinite
lattices. Thus the statistics and dynamical properties of a random walk
statistics can reveal the structural properties of a network to us.
Furthermore, different variations of random walks can be used to describe
multiple dynamical processes on networks, such as diffusion, broadcasting, to
name a few [39].

####  4.3.2 Centrality

In the simplest examples, nodes in a network are equivalent; they have no
internal structure and represent the same type of entities. However, the
structural positions of nodes within a given network make them far from
equivalent: some are positioned in structurally important (central) parts of a
network, and some are tucked away in peripheral areas. The centrality of a
node evaluates its positional importance with respect to the rest of network’s
topology. Centrality is thought to answer the question of which nodes are the
more important ones—according to an agreed definition of importance.

Interestingly, the notion of centrality can be defined in multiple ways. To
evaluate centrality of a node, various types of information about its position
in a network and relation to other nodes are taken into account.

The simplest centrality measure is degree: how many links are adjacent to a
node. For example, Garfield used degree centrality in a citation network to
quantify the quality of a publication by the number of citations it had [20].
A node’s betweenness centrality [40] is defined as the ratio of shortest paths
in the network that travel via that specific node. Closeness centrality is a
measure of how long it takes to reach all the other nodes in the network from
a specific node. It is defined as an inverse of a mean shortest path distance
from that node to others. Other centrality measures are based on various types
of walks. For instance, Katz centrality accounts for all paths, adjacent to a
node and the score is proportional to the number of walks which end at the
node from any starting vertex, scoring shorter walks higher than longer paths
[41].

Centrality has found many uses in real-world networks. For example, Brin and
Page developed PageRank centrality measure to rank websites based on their
importance in the hyperlink network of the World Wide Web [42]. In this
network, an edge between two websites represents that one website features a
hyperlink to another. The more often the website is pointed to by important
websites, the more central it is. This centrality measure was the fundamental
building block of Google search queries.

Bavelas [43] first remarked in his experiments that centrality is related to
group efficiency in problem solving. This idea of centrality being related to
other group processes was well investigated in the following decades by
sociologists [44, 45, 46], later adapted to other sciences and is used to
study, for example, biological systems [47] and is applied to recommendation
systems [48].

For further reading about centrality, refer to [49] and references therein, as
well as any general books, such as [25].

##  5 Network Models

The previous sections have given us plenty of tools to study networks of
interest. Equipped with this knowledge, we now explore some popular models
used in network theory, which have proven useful when studying diverse real-
world scenarios. These models also allow us to deepen our understanding on how
various network properties may affect the behaviour of a system.

Technically speaking, most network models are random graphs, in which some
parameters are fixed but other features vary (e.g. by shuffling connections
between nodes). One can think of a universe of equivalent networks—an
ensemble—which determines each model; from this set one may pick a particular
network and study its properties. Properties that one might fix include number
of nodes, number of edges, degree of each node, diameter, clustering
coefficient, etc.

In the following sections we review some of the most important network models
in the literature of network theory.

(a) An Erdös-Rényi graph, obtained by connecting each pair of nodes with a
probability of $13\%$.

(b) A 2-dimensional lattice graph, in which each node is connected to its
three nearest neighbours.

(c) Watts-Strogatz (small world) graph, in which each node connects to its 4
nearest neighbours. 30% of edges are then randomised.

(d) Barabási-Albert graph. A new node connects to three older nodes in the
network preferentially based on their degree.

Figure 4: Comparison between different network models. The intensity of the
colour reflects the number of edges adjacent to the node.

###  5.1 Erdös-Rényi graph

The Erdös-Rényi network model [50] is one of the simplest network models, the
essential element of which is its randomness. In this model one assumes no
prior knowledge about the network, nodes and edges. To build a representative
network of this model, one follows a simple rule: consider each pair of nodes,
and with some probability $p$ build an edge between them.

Erdös-Rényi network is a “structure-less” network, being rather dissimilar
from most real-world networks. As such, it typically serves as null model to
contrast various properties of the latter. For example, the degree
distribution of the real-world networks is often “fat-tailed” (see Section
4(c) for a discussion of networks with fat-tailed degree distribution), which
is not the case in an in Erdös-Rényi graph. Furthermore, the clustering
coefficient, as well as typical shortest path lengths tend to be smaller in
Erdös-Rényi than in real-world networks.

###  5.2 Lattice graphs

Lattice graphs are a polar opposite of the Erdös-Rényi graphs, having an
extremely regular, “symmetric”, tile-like shape. To build a lattice graph, one
can take a single connection pattern (e.g. a triangle, or a square) and repeat
it, stitching each element to others in the same way each time.

These networks tend to have very long average path lengths, high clustering
coefficient and only one type of dominant motif—the one connection pattern the
network is based on. These graphs provide a contrast to the Erdös-Rényi graph
as a null model, as together they are extreme ends of a spectrum within which
many real-world networks lie.

###  5.3 Small world networks

Often, the networks which we observe are called “small-world”. The
characteristic property of these networks is that most nodes are not immediate
neighbours, but any node can be reached from any other node with only a few
hops.

One useful way of visualising a small-world network is by depicting it as a
circular graph, in which nodes are connected to two other nodes, nearest to
them on the circle. This network is a rather “large world”, as the shortest
path between two nodes on the opposite sides of the circle are quite long. To
obtain a small-world network from this circular graph one randomly adds a
number of “shortcuts”—i.e. edges connecting random pairs of nodes. The
inclusion of these shortcuts significantly decreases the length of the
shortest path between most pairs of nodes. A network model which yields such
properties is the Watts-Strogatz model [51].

One of the most interesting examples of a small-world network can be found in
the well-known Milgram’s experiment [52]. In it, Stanley Milgram, psychologist
at Yale University, sent out packages to some people across the United States.
These people were not the recipients of these packages but rather were asked
to pass them along to other people they knew well and who may know the
recipients (if they did not know them themselves). It turned out that the
average path length that a letter travelled was around six—the six degrees of
separation. The conclusion was, that, although the social network (people in
the country) is large, everyone is separated by a comparably much smaller
number of people—six.

###  5.4 Scale-free networks

A network whose degree distribution follows a power law are called scale-free.
That means that the probability that a node is observed with a degree $k$
decreases (exponentially) as the degree increases. The term scale-free means
that there is no typical number of edges. As a result, we have many nodes with
very small degree (close to one), and very few “winners”—nodes with very large
degrees (we say that the degree heterogeneity is large).

Scale-free networks are abundant. De Solla Price was the first to point out
that scale-free behaviour is apparent in citation networks [45]. These
networks are composed of publications as nodes and citations between papers as
edges. Thus de Solla Price pointed out that most papers are poorly cited,
whereas a few are very well-cited. Other networks that are thought to be
scale-free include protein-protein interaction networks, collaboration
networks (such as between actors who made films together), the Internet and
the World Wide Web to name but a few. In general, systems that are created by
“rich-get-richer” phenomena tend to be scale-free.

The most famous mechanism to generate scale-free networks is preferential
attachment. In preferential attachment, the more connected a node is, the
quicker it acquires more new connections. This phenomenon has long been known
in non-networks contexts and has many different names, including the Pareto
principle or the 80-20 rule ($19^{\mathrm{th}}$ cent. ), the Matthew effect
(Matthew’s gospel: “For everyone who has will be given more”), Yule’s
distribution (1925) emerging from a description of biological taxa and
subtaxa, and Simon’s model for the frequency of words in text.

One of the most well-known generative model for scale-free networks is the
Barabási-Albert model of preferential attachment. The growing network model
follows very simple rules. It is initiated with a small initial graph. At each
time step, a new node is introduced to a network and connect it to $m$ older
nodes. The connection happens preferentially, that is, a newly introduced node
prefer to connect to large-degree nodes. By growing the network in this way we
obtain the scale-free structure222Please note that while preferential
attachment generates edge distributions that follow power laws, the reciprocal
is not necessarily true; there are many ways of obtaining power laws that do
not relate to preferential attachment..

##  6 Discussion, future perspectives, and further reading

The previous sections have introduced various types of networks, and discussed
aspects of how to study them. This brief account of network theory certainly
is not exhaustive; our goal was to intrigue the reader about the network
approach to complex systems, as a thorough review of everything this field has
to offer is beyond the scope of this work.

We invite the curious reader to further explore various aspects of network
theory in the following texts. Foremost, there are many popular science books
that discuss complex networks, including [53, 54, 55, 56]. For more technical,
mathematical overview, please refer to handbooks such as [25, 57, 58, 59].
There are also several more specific review papers the on various topic
discussed in this article. For a review of network visualisation see [60] or
also explore internet outlets such as Towards Data Science. For comparison of
community detection algorithms, please consider reviews such as [61, 62, 63].
Detailed discussions of centrality measures can be found in [49, 64], and
visualised in schochastics.net.

Networks provide one of the best and most efficient tools to develop insights
over complex datasets. While traditional statistical methods are effective in
discovering relationships between variables, network theory is particularly
well-suited to study how these relationships are structured, i.e. finding
“patterns within the patterns” In doing so, network theory provide a route
towards assessing synergistic properties that might take place within complex
systems of interest (c.f. Section 2.3). Additionally, networks seem to embody
the spirit of our times, being pervasive in the way many things are understood
today. Complex networks have come to replace other metaphors in a number of
fields of science, and now represent a fundamental element of our worldview.

Having said that, network theory also have important limitations. First, is
important to note that a network generated from data is only as good as the
data used to build it. In particular, if the data is extremely noisy or
untrustworthy, then a network analysis will follow the garbage-in/garbage-out
principle and provide similarly untrustworthy results. Another important
limitation of traditional networks is that they focus on pairwise (i.e.
binary) relationships, and then perform inferences on the collective structure
of a system based on the relative arrangement of these. However, it has been
shown that there exist numerous high-order relationships that cannot be
captured by binary measures. These networks can be captured by hypergraphs,
whose “hyperlinks” can relate more than two nodes [65]. However, the large
number of hyperlinks even in relatively small hypergraphs make them
computationally challenging. A popular sub-class of hypergraphs, called
simplicial complexes, have been shown to have favourable properties efficient
algorithms for it processing and storage [66]. Simplicial complexes are
finding diverse applications in recent studies, and we expect them to grow in
popularity in the coming years.

Finally, complexity science has many other methods that are not related to
networks. Despite its recent popularity, network theory is definitely not a
universal solution for social systems and other approaches are sometimes
preferable. An overview on complementary methods can be found in general books
about complexity science, including [67, 68].

It is our hope that this review might serve as inspiration of creative uses of
network theory and complexity science in the future, fostering novel
applications of these tools in fields that have not yet been explored. In
particular, we believe that there are plenty of opportunities for using
network tools in the fields of arts, both for fostering creative endeavours
and guiding analyses of existent material. Nowadays, complexity science is
pushing forward the boundaries of our knowledge, and we strongly believe that
including arts in this endeavour will bring mutual—and synergistic—benefits to
arts and science.

## References

  * [1] T. M. Cover and J. A. Thomas, Elements of information theory.  John Wiley & Sons, 2012.
  * [2] M. Li, P. Vitányi, et al., An introduction to Kolmogorov complexity and its applications, vol. 3.  Springer, 2008.
  * [3] P. M. Senge, B. Smith, N. Kruschwitz, J. Laur, and S. Schley, The necessary revolution: Working together to create a sustainable world.  Broadway Books New York, NY, 2010.
  * [4] J. S. Kelso, Dynamic patterns: The self-organization of brain and behavior.  MIT press, 1995.
  * [5] D. J. Chalmers, The conscious mind: In search of a fundamental theory.  Oxford university press, 1996.
  * [6] F. Rosas, V. Ntranos, C. Ellison, S. Pollin, and M. Verhelst, “Understanding interdependency through complex information sharing,” Entropy, vol. 18, no. 2, p. 38, 2016.
  * [7] F. E. Rosas, P. A. M. Mediano, M. Gastpar, and H. J. Jensen, “Quantifying high-order interdependencies via multivariate extensions of the mutual information,” Phys. Rev. E, vol. 100, p. 032305, Sep 2019.
  * [8] J. H. Holland, Emergence: From chaos to order.  OUP Oxford, 2000.
  * [9] A. K. Seth, “Measuring autonomy and emergence via granger causality,” Artificial life, vol. 16, no. 2, pp. 179–196, 2010.
  * [10] E. P. Hoel, L. Albantakis, and G. Tononi, “Quantifying causal emergence shows that macro can beat micro,” Proceedings of the National Academy of Sciences, vol. 110, no. 49, pp. 19790–19795, 2013.
  * [11] P. A. Mediano, F. Rosas, R. L. Carhart-Harris, A. K. Seth, and A. B. Barrett, “Beyond integrated information: A taxonomy of information dynamics phenomena,” arXiv preprint arXiv:1909.02297, 2019.
  * [12] J. L. Moreno, “Who shall survive?: A new approach to the problem of human interrelations.,” 1934.
  * [13] L. C. Freeman, The Development of Social Network Analysis: A Study in the Sociology of Science.  Empirical Press, 2004.
  * [14] E. Otte and R. Rousseau, “Social network analysis: a powerful strategy, also for the information sciences,” Journal of Information Science, vol. 28, pp. 441–453, dec 2002.
  * [15] P. M. Gleiser and L. Danon, “Community structure in jazz,” Advances in complex systems, vol. 6, no. 04, pp. 565–573, 2003.
  * [16] M. Perc, “Growth and structure of slovenia’s scientific collaboration network,” Journal of Informetrics, vol. 4, no. 4, pp. 475–482, 2010.
  * [17] R. Guimera, B. Uzzi, J. Spiro, and L. A. N. Amaral, “Team assembly mechanisms determine collaboration network structure and team performance,” Science, vol. 308, pp. 697–702, apr 2005.
  * [18] J. Moody, “The structure of a social science collaboration network: Disciplinary cohesion from 1963 to 1999,” American Sociological Review, vol. 69, pp. 213–238, apr 2004.
  * [19] J. H. Fowler, C. T. Dawes, and N. A. Christakis, “Model of genetic variation in human social networks,” Proceedings of the National Academy of Sciences, vol. 106, pp. 1720–1724, jan 2009.
  * [20] E. Garfield, “Citation frequency as a measure of research activity and performance,” Essays of an Information Scientist, vol. 1, no. 2, pp. 406–408, 1973.
  * [21] R. Cofre, R. Herzog, D. Corcoran, and F. Rosas, “A comparison of the maximum entropy principle across biological spatial scales,” 2019.
  * [22] V. Colizza, A. Flammini, A. Maritan, and A. Vespignani, “Characterization and modeling of protein–protein interaction networks,” Physica A: Statistical Mechanics and its Applications, vol. 352, pp. 1–27, jul 2005\.
  * [23] T. Nepusz, H. Yu, and A. Paccanaro, “Detecting overlapping protein complexes in protein-protein interaction networks,” Nature methods, vol. 9, no. 5, p. 471, 2012.
  * [24] R. Pastor-Satorras and A. Vespignani, Evolution and Structure of the Internet: A Statistical Physics Approach.  New York, NY, USA: Cambridge University Press, 2004.
  * [25] M. Newman, Networks.  Oxford University Press, mar 2010.
  * [26] M. E. J. Newman, “Modularity and community structure in networks,” Proceedings of the National Academy of Sciences, vol. 103, pp. 8577–8582, may 2006.
  * [27] G. F. Davis, M. Yoo, and W. E. Baker, “The small world of the american corporate elite, 1982-2001,” Strategic Organization, vol. 1, pp. 301–326, aug 2003.
  * [28] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, “Network motifs: Simple building blocks of complex networks,” Science, vol. 298, pp. 824–827, oct 2002.
  * [29] S. Fortunato, “Community detection in graphs,” Physics Reports, vol. 486, pp. 75–174, 2010.
  * [30] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,”
  * [31] P. Sah, L. O. Singh, A. Clauset, and S. Bansal, “Exploring community structure in biological networks with random graphs,” BMC Bioinformatics, vol. 15, no. 1, p. 220, 2014.
  * [32] A. Buluc, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz, “Recent advances in graph partitioning,”
  * [33] M. Girvan and M. E. Newman, “Community structure in social and biological networks,” Proceedings of the national academy of sciences, vol. 99, no. 12, pp. 7821–7826, 2002.
  * [34] M. Rosvall, D. Axelsson, and C. T. Bergstrom, “The map equation,” The European Physical Journal Special Topics, vol. 178, pp. 13–23, nov 2009.
  * [35] S. Fortunato and M. Barthelemy, “Resolution limit in community detection,” Proceedings of the National Academy of Sciences, vol. 104, pp. 36–41, dec 2006.
  * [36] T. C. Silva and L. Zhao, Machine Learning in Complex Networks.  Springer International Publishing, 2016.
  * [37] M. Newman and G. Reinert, “Estimating the number of communities in a network,” Physical Review Letters, vol. 117, aug 2016.
  * [38] T. Nishikawa, A. E. Motter, Y.-C. Lai, and F. C. Hoppensteadt, “Heterogeneity in oscillator networks: Are smaller worlds easier to synchronize?,” Physical Review Letters, vol. 91, jul 2003.
  * [39] N. Masuda, M. A. Porter, and R. Lambiotte, “Random walks and diffusion on networks,” Physics Reports, vol. 716-717, pp. 1–58, nov 2017.
  * [40] L. C. Freeman, “Centrality in social networks conceptual clarification,” Social Networks, vol. 1, no. 3, pp. 215 – 239, 1978.
  * [41] L. Katz, “A new status index derived from sociometric analysis,” Psychometrika, vol. 18, pp. 39–43, mar 1953.
  * [42] S. Brin and L. Page, “The anatomy of a large-scale hypertextual web search engine,” Computer Networks and ISDN Systems, vol. 30, no. 1, pp. 107 – 117, 1998.  Proceedings of the Seventh International World Wide Web Conference.
  * [43] A. Bavelas, “A mathematical model for group structures,” Human Organization, vol. 7, no. 3, pp. 16–30, 1948.
  * [44] K. D. Mackenzie, “Structural centrality in communications networks,” Psychometrika, vol. 31, no. 1, pp. 17–25, 1966.
  * [45] D. J. de Solla Price, “Networks of scientific papers,” Science, vol. 149, no. 3683, pp. 510–515, 1965.
  * [46] M. A. Beauchamp, “An improved index of centrality,” Behavioral Science, vol. 10, no. 2, pp. 161–163, 1965.
  * [47] M. Ashtiani, A. Salehzadeh-Yazdi, Z. Razaghi-Moghadam, H. Hennig, O. Wolkenhauer, M. Mirzaie, and M. Jafari, “A systematic survey of centrality measures for protein-protein interaction networks,” BMC Systems Biology, vol. 12, jul 2018.
  * [48] L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation ranking: Bringing order to the web,” 1999.
  * [49] A. Landherr, B. Friedl, and J. Heidemann, “A critical review of centrality measures in social networks,” Business & Information Systems Engineering, vol. 2, pp. 371–385, oct 2010.
  * [50] P. Erdős and A. Rényi, “On the evolution of random graphs,” in Publication of the Mathematical Institute of the Hungarian Academy of Sciences, pp. 17–61, 1960.
  * [51] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,” Nature, vol. 393, pp. 440–442, jun 1998.
  * [52] S. Milgram, “The small world problem,” Psychology today, vol. 2, no. 1, pp. 60–67, 1967.
  * [53] J. Fowler and N. Christakis, Connected: The Surprising Power of Our Social Networks and How They Shape Our Lives.  Recorded Books, 2010.
  * [54] N. A. Christakis, Blueprint: The Evolutionary Origins of a Good Society.  Little, Brown US, 2019.
  * [55] N. Ferguson, The Square and the Tower: Networks, Hierarchies and the Struggle for Global Power.  penguin uk, 2018.
  * [56] D. Watts, Six Degrees: The Science of a Connected Age.  W. W. Norton, 2004.
  * [57] G. Caldarelli and M. Catanzaro, Networks: A Very Short Introduction.  Oxford University Press, oct 2012.
  * [58] E. Estrada, The Structure of Complex Networks: Theory and Applications.  New York, NY, USA: Oxford University Press, Inc., 2011.
  * [59] V. Latora, V. Nicosia, and G. Russo, Complex Networks.  Cambridge University Press, sep 2017.
  * [60] M. Withall, I. Phillips, and D. Parish, “Network visualisation: a review,” IET Communications, vol. 1, no. 3, p. 365, 2007.
  * [61] S. Fortunato, “Community detection in graphs,” Physics Reports, vol. 486, pp. 75–174, feb 2010.
  * [62] M. El-Moussaoui, T. Agouti, A. Tikniouine, and M. E. Adnani, “A comprehensive literature review on community detection: Approaches and applications,” Procedia Computer Science, vol. 151, pp. 295–302, 2019.
  * [63] Z. Yang, R. Algesheimer, and C. J. Tessone, “A comparative analysis of community detection algorithms on artificial networks,” Scientific Reports, vol. 6, aug 2016.
  * [64] F. A. Rodrigues, “Network centrality: an introduction,”
  * [65] C. Berge, Hypergraphs: combinatorics of finite sets, vol. 45.  Elsevier, 1984.
  * [66] H. Edelsbrunner and J. Harer, Computational topology: an introduction.  American Mathematical Soc., 2010.
  * [67] Y. Bar-Yam, Dynamics of complex systems.  CRC press, Massachusetts, 1999.
  * [68] S. Thurner, R. Hanel, and P. Klimek, Introduction to the theory of complex systems.  Oxford University Press, 2018.


# Towards Optimizing with Large Language Models

Pei-Fu Guo
<EMAIL_ADDRESS>Ying-Hsuan Chen
<EMAIL_ADDRESS>Yun-Da Tsai
<EMAIL_ADDRESS>Shou-De Lin
<EMAIL_ADDRESS>
###### Abstract

In this work, we conduct an assessment of the optimization capabilities of
LLMs across various tasks and data sizes. Each of these tasks corresponds to
unique optimization domains, and LLMs are required to execute these tasks with
interactive prompting. That is, in each optimization step, the LLM generates
new solutions from the past generated solutions with their values, and then
the new solutions are evaluated and considered in the next optimization step.
Additionally, we introduce three distinct metrics for a comprehensive
assessment of task performance from various perspectives. These metrics offer
the advantage of being applicable for evaluating LLM performance across a
broad spectrum of optimization tasks and are less sensitive to variations in
test samples. By applying these metrics, we observe that LLMs exhibit strong
optimization capabilities when dealing with small-sized samples. However,
their performance is significantly influenced by factors like data size and
values, underscoring the importance of further research in the domain of
optimization tasks for LLMs.

##  I Introduction

In recent years, Large Language Models have demonstrated exceptional
capabilities in reasoning across a variety of natural language-based tasks
[5]. However, their potential extends beyond multiple-choice questions or
single-question answering. This work explores LLMs’ effectiveness in
optimization across diverse tasks and data sizes. Optimization, in this
context, refers to the process of iteratively generating and evaluating
solutions to improve upon a given objective function.

Our research assesses how well LLMs perform in interactive optimization
settings, where each optimization step involves the generation of new
solutions based on past solutions and their associated values. We conduct our
study with four different types of optimization algorithms: Gradient Descent,
Hill Climbing, Grid Search, and Black Box Optimization. In order to provide a
comprehensive evaluation of LLM performance, we introduce three distinct
metrics. These metrics provide a multifaceted view of task performance and are
applicable across a broad spectrum of optimization tasks, reducing sensitivity
to sample variations.

Our preliminary findings indicate that LLMs exhibit impressive optimization
capabilities, particularly when confronted with tasks involving small-sized
data samples. However, the performance of these models is notably influenced
by factors, including the sample size and the range of values involved in the
process. These observations underscore the need for further research and
exploration within the domain of optimization tasks tailored for Large
Language Models.

To summarize, we aim to make the following contributions in this preliminary
study: (1) Exploring LLMs in interactive optimization scenarios with iterative
prompting. (2) Introduce three novel evaluation metrics designed to provide a
comprehensive assessment of LLM performance in optimization tasks. (3) Delve
into factors that influence LLM performance in optimization, with a particular
emphasis on the impact of data size and task type.

##  II Related Work

In various optimization scenarios, the utilization of Large Language Models
(LLMs) has become indispensable for the development of optimization algorithms
or agent systems capable of handling complex and informative text-based
feedback [1, 3, 6]. In this section, we summarize three significant related
works that leverage LLMs to tackle optimization and reinforcement learning
challenges:

  1. 1.

Optimization by PROmpting (OPRO): OPRO harnesses LLMs as versatile optimizers
by describing optimization tasks in natural language prompts. It iteratively
generates and evaluates solutions from these prompts, demonstrating superior
performance on tasks like linear regression and traveling salesman problems.
OPRO outperforms human-designed prompts by up to 50% on challenging tasks.

  2. 2.

Reflexion: Reflexion introduces a novel framework for training language agents
that rely on linguistic feedback rather than traditional reinforcement
learning. It achieves remarkable results, such as a 91% pass@1 accuracy on
coding tasks, surpassing previous state-of-the-art models by 11%.

  3. 3.

EvoPrompt: EvoPrompt automates prompt optimization by connecting LLMs with
evolutionary algorithms. This approach outperforms human-designed prompts by
up to 25% and existing automatic prompt generation methods by up to 14%. It
highlights the synergy between LLMs and conventional algorithms.

These works collectively showcase the adaptability and effectiveness of LLMs
in addressing optimization and learning challenges across various domains.

##  III Methodology

We demonstrate that LLMs with iterative prompting can serve as optimizers and
could be formulated similarly to different types of optimization algorithms.
In particular, we present a case study on Gradient-Descent, Hill-Climbing
(Heuristic), Grid-Search, and Black-Box Optimization (LLMs as a black box
optimizer) and conduct an assessment of the optimization capabilities of Large
Language Models across a range of distinct parameter search tasks.

### 3-1 Tasks

We design four optimization tasks that require the model to algorithmically
search for the optimal value of parameters. These tasks encompass Gradient-
Descent, Hill-Climbing, Grid-Search, and Black-Box Optimization, each
representing unique optimization domains: gradient-based, meta-heuristics,
decision-theoretic, and Bayesian. In terms of parameter types, Grid-Search and
Hill-Climbing involve discrete search spaces, while Gradient-Descent and
Black-Box Optimization tackle continuous search spaces.

In the Gradient-Descent task, we instruct Large Language Models to undertake a
conventional gradient descent optimization process based on the loss function
they have defined. Language Models need to compute the gradient and update the
parameters using the gradient information and the learning rate given. This
task assesses the model’s proficiency in advanced calculations and its grasp
of the principles of gradient descent.

In the Hill-Climbing task, we introduce custom instructions in the search
algorithm to evaluate the LLM’s capability to adhere to predefined rules they
have not seen before. LLMs start with an initial solution and iteratively
explore nearby solutions by making small incremental changes. In our task,
neighboring solutions are generated by selecting a specific element within the
solution and either increasing or decreasing it by one each time.
Subsequently, the neighbor solution with the minimum loss is chosen as the new
solution and passed to the next iteration.

In the Grid-Search task, Large Language Models are tasked with generating all
grid points and systematically searching for the point that results in the
lowest loss according to the given loss function. This task assesses the LLM’s
ability to conduct exhaustive searches and locate optimal solutions within a
predefined search space.

In the Black-Box Optimization task, we treat the LLMs as black boxes that try
to fit an unknown loss function. We provide the LLM with a limited set of
solutions, each paired with its respective true loss value. The LLM’s
objective is to discover a new solution that has a lower loss than the
existing solutions in each iteration by themselves. This task evaluates the
LLM’s ability to make informed decisions and optimize in a less transparent or
more abstract problem-solving context.

Figure 1: Overview of our prompting strategy. (1) Define the loss function.
(2) Given instruction prompt, LLM generates solution and pass result to next
iteration. (3) Evaluate LLM final output.

### 3-2 Prompting Strategy

We applied Chain of Thoughts as our prompting method. The Language model will
accomplish each step with reasoning thoughts as intermediate outputs. Each
optimization iteration is composed of three steps: (1) Define the loss
function. (2) Given an instruction prompt, LLM generates a solution and passes
the result to the next iteration. (3) Evaluate LLM final output. In each of
these tasks (optimization algorithm), LLMs are initially required to formulate
a loss function based on the provided sample. Following the formulation of
this loss function, they embark on a process of iterative exploration to
determine the optimal values for the variables that will minimize the loss
associated with the function. Figure 1 shows an overview of how LLM performs
optimization in interactive settings. The following illustrates a sample meta-
prompt for the prompting strategy. Detailed meta prompt instructions can be
found in Appendix A. Complete prompt examples for each optimization algorithm
can be found in Appendix B.

Gradient-Descent

*Define Loss function
User :
Given the data points (y1, y2, y3) = (2,6,0), what is the MSE loss function
with respect to the ŷs for a hypothetical set of predicted ŷs values?
LLM :
The MSE loss function for the given data points (y1, y2, y3) = (2,6,0) with
respect to ŷs is:
$\frac{1}{3}[(\hat{y}_{1}-2)^{2}+(\hat{y}_{2}-6)^{2}+(\hat{y}_{3}-0)^{2}]$

*First Iteration
User :
Please minimize the loss function using gradient descent with learning rate of
0.1 at point (ŷ1, ŷ2, ŷ3, …..) = (2,3,4). What is the point we eventually end
up after one update? Your answer includes two parts an explanation with
calculation and a short answer of result.
LLM :
Explanation : To minimize the Mean Squared Error (MSE) loss function using
gradient descent …
Short Answer: After calculation, the next update point is (ŷ$1_{new}$,
ŷ$2_{new}$, ŷ$3_{new}$) = (1.92, 3.05, 3.94)

*Second Iteration
User :
Please minimize the loss function using gradient descent with learning rate of
0.1 at point (ŷ1, ŷ2, ŷ3, …..) = (1.92, 3.05, 3.94). What is the point we
eventually end up after one update? Your answer includes two parts an
explanation with calculation and a short answer of result.
LLM :
Explanation : To minimize the Mean Squared Error (MSE) loss function using
gradient descent …
Short Answer: After calculation, the next update point is (ŷ$1_{new}$,
ŷ$2_{new}$, ŷ$3_{new}$) = (1.81, 3.12, 3.41)
⋮

##  IV Experimental

### 4-1 Dataset

In the experiment, we generate synthetic datasets where each instance belongs
to $[0,10]^{d}$. In the experiments, we create five datasets with $d$ values
chosen from the set $\\{3,6,12,24,48\\}$ in order to investigate sensitivity
to the size of input data points.
We then apply these data to a loss function (Mean Squared Error) and find the
true solution for each parameter search task. These true solutions and their
losses serve as the ground truth for the tasks and are used as a benchmark to
compare with the solutions found by Large Language Models afterward.

### 4-2 Detailed Settings

In our experiment, we performed five repetitions of the test for each sample
in the dataset, with the LLM conducting ten iterations of parameter search in
each repetition. We excluded excessively biased results to prevent our metrics
from being skewed by a minority of poorly performing test outcomes. All the
samples have been confirmed to exhibit a significant reduction in their
respective loss within ten iterations when optimized by the ground truth
algorithm.

We assess the performance of Large Language Models: GPT-turbo-3.5, GPT-4. To
create an interactive environment, we utilize the chat-mode of GPTs, where the
entire conversation history serves as the prompt. This approach enables the
LLMs to retain the memory of prior search results and reasoning paths from
past interactions. With each iteration, new instructions are added to the
ongoing conversation records and the entire dialogue is presented as the
prompt. If the dialogue exceeds the token limit, we will remove the earliest
portions of the conversation to ensure compliance with the limit. See Appendix
B for detailed examples.

We set the model temperature to 0.8, which adds randomness to the generated
responses. This intentional randomness helps us evaluate the stability of LLM
solutions when provided with identical initial settings in the search. Due to
resource and token length limitations, we only test the Gradient Descent task
and BlackBox Optimization task on all datasets and LLMs. For Grid Search and
Hill Climbing tasks, experiments are conducted only on datasets with sample
sizes 3, 6, and 12 and exclusively run on GPT-turbo-3.5.

##  V Metric Design

To comprehensively evaluate task performance from different aspects, we
designed three distinct metrics. The first is the $goal$ $metric$, gauging the
LLM’s advancement in accomplishing the optimization task. The second is the
$policy$ $metric$, assessing the proximity of the final model output to the
ground truth. Lastly, the $uncertainty$ $metric$, which quantifies the level
of variability in the LLM’s solutions when exposed to identical conditions.

These metrics have the advantage of being versatile in evaluating LLM
performance across various optimization tasks, streamlining the process for
practitioners to assess multiple task performances concurrently. Additionally,
these metrics are less sensitive to variations in test samples because of the
use of ratio measures rather than difference measures.

### 5-1 Goal Metric

One of our objectives in this study is to evaluate the optimization
capabilities of Large Language Models. To achieve this, we employ the goal
metric, which serves as a quantitative measure of the extent to which the
optimization process leads to improvements in objective function values. We
define the goal metric of a test sample $j$ as :

$\displaystyle
G_{j}=\frac{1}{N}\sum_{i=1}^{N}\frac{loss_{LLM,init}-loss_{LLM,i}}{loss_{LLM,init}}$

where $loss_{LLM,init}$ is the initial solution loss of sample $j$,
$loss_{LLM,i}$ is the LLM output loss of trial $i$, and $N$ is the number of
trials per sample. The higher the metric value, the greater the progress in
optimization. The goal metric plays a crucial role in our evaluation
framework, particularly in scenarios where ground truth is absent, such as the
Black-Box optimization scenarios.

### 5-2 Policy Metric

Beyond self-improvement, it’s essential to evaluate the Large Language Models’
ability to function akin to a truth model algorithm. The metric designed for
this evaluation is the policy metric, which serves as an indicator of the
LLM’s proficiency in adhering to task-specific instructions. We define the
policy metric of a test sample $j$ as :

$\displaystyle
P_{j}=\frac{1}{N}\sum_{i=1}^{N}\frac{loss_{LLM,i}-loss_{truth}}{loss_{truth}}$

where $loss_{LLM,i}$ is the LLM output loss of trial $i$, $loss_{truth}$ is
the ground truth of sample $j$ and $N$ is the number of trials. The policy
metric measures the disparity between the ground truth and the LLM’s output. A
lower policy metric value indicates a more effective alignment of the LLM’s
actions with the prescribed guidelines. When the value is negative, it means
that LLM’s performance surpasses the ground truth.

### 5-3 Uncertainty Metric

Stability is a crucial characteristic in optimization tasks. We hope that the
LLMs produce identical results in every trial involving the same sample, even
under conditions with temperatures greater than zero. We define the
uncertainty metric of a test sample $j$ as :

$\displaystyle
U_{j}=\frac{1}{N}\sum_{i=1}^{N}(loss_{LLM,i}-\overline{loss_{LLM}})^{2}$

where $loss_{LLM,i}$ is the LLM output of the i-th trial,
$\overline{loss_{LLM}}$ is the mean of the trial outputs and $N$ is the number
of trials. A stable LLM can be more trusted for tasks that demand consistent
and reproducible results. In our case, if the language model truly understands
the context of problems, the final optimal output should be identical in every
trial of the same sample.

##  VI Results and Analysis

We summarize the outcomes of our experiment and subsequently examine the
common trends observed across all experiments. In every plot, the x-axis
displays the number of data points within each sample. In the case of the goal
metric and policy metric plots, the y-axis illustrates the average metric
value for the respective tasks, while the shaded area in a lighter color
delineates the confidence interval of the metric, denoted as $[value-
std,value+std]$. As for the uncertainty metric plot, the y-axis showcases the
uncertainty metric value, which corresponds to the standard deviation of the
LLM final solution loss.

### 6-1 Results

Figure 2 presents the performance of GPT-turbo-3.5 across all tasks. The Grid-
Search task doesn’t appear in the goal metric graph due to its non-iterative
nature. Similarly, Black-Box Optimization isn’t represented in the policy
metric graph because ground truth is unattainable.

Figure 2: GPT-turbo-3.5 average zero-shot performance across tasks

We can see that GPT-turbo-3.5 exhibits optimization capabilities in most
cases. Impressively, in the Gradient-Descent task, GPT-turbo-3.5 even
surpasses the ground truth, particularly in the case of the 6 data points
sample. It’s also surprising that the model achieves respectable results in
the Grid-Search task, considering it must compute a vast number of grid
points, which increase exponentially as the data per sample expands. The model
faces challenges in the Hill-Climbing task, evident from a policy metric
significantly exceeding zero. This suggests that meta-heuristics may pose
greater difficulty for LLMs compared to other tasks.

Remarkably, GPT-turbo-3.5 and GPT-4 excel at performing Black-Box tasks in
small-size samples. From Figure 3, we can see that GPT-turbo-3.5 performs
notably with three data points, whereas GPT-4 excels at three and six data
points. Interestingly, as the number of data points increases, the performance
of both models gradually diminishes. Eventually, GPT-4 establishes itself as
the superior performer.

Figure 3: GPTs average performance of Black-Box Task

In the context of the Gradient-Descent Task, both models exhibit strong
performance, with GPT-4 edging out GPT-turbo-3.5 by a slight margin. Figure 4
underscores this by revealing a policy metric that consistently hovers near
zero, signifying a remarkable alignment between the LLM’s output and the
ground truth. Despite a decline in the goal metric as the sample size
increases, the consistently low and stable value of the policy metric
underscores the fact that GPT’s performance in the gradient-descent task is
nearly on par with the truth model or algorithm.

Figure 4: GPTs average performance of Gradient-Descent Task

### 6-2 Analysis

LLMs showcase optimization prowess across diverse domains. While not all
solutions consistently achieve substantial improvements or align perfectly
with ground truth, the predominantly positive goal metric values across most
tasks and datasets indicate their capability for optimization. Among these
tasks, Gradient Descent emerges as the leading performer, while the Hill-
Climbing task poses greater challenges. Remarkably, GPT-4 even surpasses
ground truth in a dataset comprising six data points, underscoring its
exceptional aptitude for calculus. This underscores the notion that LLMs
possess a versatile capacity to optimize within various problem spaces, which
allows for the possibility of switching between different optimization methods
within a single task.

LLM can be real optimizers. In the Black-Box Optimization task, LLMs are
treated as black-box optimizers, which try to fit an unknown loss function. In
each iteration, they are asked to offer their preferred solutions based on the
discovered solutions and their true scores. Notably, when there are three data
points, a more pronounced optimization capability is observed. Despite the
performance decline with an increase in data points (variables), this
observation intriguingly suggests that LLMs may possess inherent optimization
capabilities of their own.

Data quantity influence stability. In cases where samples have fewer data
points, it’s common to observe high uncertainty metric values accompanied by
significant variations in policy and goal metrics. This suggests that while
Large Language Models generally perform well in most trials, we may still
encounter instances of failure, such as getting stuck in neither global nor
local optima, optimizing in the wrong direction, and regenerating solutions
that already appeared when attempting the same task again with the same
sample. Figure 2 and 5 both highlight the conspicuous pattern of uncertainty,
where the uncertainty initially rises and then gradually decreases. This
behavior is consistent across different tasks and models, warranting further
investigation to fully understand its underlying causes.

Figure 5: Uncertainty Metric of different tasks and models

Prompting methods may contribute to stability. In the Gradient-Descent task,
we employ the self-consistency technique [4], where we conduct five
repetitions for each iteration and select the solution that emerges most
frequently. From Figure 6, we can see that GPT-4 performances increase
largely, and the confidence interval for both the policy-metric and goal-
metric narrows, indicating improved stability and reliability. Nonetheless,
this approach does not yield favorable outcomes when applied to GPT-turbo-3.5.
This suggests the need for further investigation within the realm of variance
reduction to better understand the contributing factors to these results.

Figure 6: Average Performance of Gradient-Descent Task with Self-Consistency

Sensitivity to data samples. It’s worth considering that the aforementioned
results may be influenced by the inherent randomness in the generation of test
samples. Previous research has indicated that Large Language Models (LLMs) may
demonstrate preferences for particular numbers, words, and symbols [2], which
can introduce a level of bias in their responses. Given the high sensitivity
of LLMs to the input prompt, the initial starting points and data provided can
exert a significant influence on their outputs. In essence, the impact of
instruction description and data initialization should be carefully considered
when interpreting the results of LLM-based experiments to ensure a more
accurate assessment of their performance.

##  VII Conclusion

In this paper, we present our in-depth examination of assessing Large Language
Models (LLMs) within the realm of optimization. We investigate LLMs’
performance across four optimization tasks that necessitate their
comprehension of algorithmic instructions and their ability to generate new
solutions based on previous solutions and their corresponding values.

Our evaluation shows that LLMs showcase optimization prowess across diverse
domains. Among the four tasks we examined, LLMs exhibit their greatest
strengths in the Gradient-Descent task, displaying remarkable proficiency in
this area. However, they encounter more pronounced difficulties in the meta-
heuristics task, where they must adhere to predefined rules that they have not
encountered previously. Furthermore, LLMs demonstrate impressive skills in the
grid search task, showcasing their ability to conduct exhaustive searches
effectively. In the Black-Box task, LLMs excel, particularly when dealing with
limited sample sizes, suggesting inherent optimization abilities within them.

Interestingly, in cases where samples have fewer data points(variables), it’s
common to observe a higher variance in solution quality. The notable pattern
of uncertainty is characterized by an initial surge followed by a gradual
decrease as data size increases and persistence across tasks and models.

In conclusion, our exploration of Large Language Models (LLMs) for
optimization has unveiled a host of unresolved questions that beckon future
research. Chief among these challenges is the quest to mitigate the
sensitivity of LLMs to both data value and size, a paramount concern for
enhancing their practical utility.

## References

  * [1] Qingyan Guo, Rui Wang, Junliang Guo, Bei Li, Kaitao Song, Xu Tan, Guoqing Liu, Jiang Bian, and Yujiu Yang.  Connecting large language models with evolutionary algorithms yields powerful prompt optimizers.  In arXiv:2309.08532, 2023.
  * [2] Alex Renda, Aspen Hopkins, and Michael Carbin.  Can llms generate random numbers? evaluatingllm sampling in controlled domains.  2023\.
  * [3] Noah Shinn, Federico Cassano, Beck Labash, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao.  Reflexion: Language agents with verbal reinforcement learning.  In arXiv:2303.11366, 2023.
  * [4] X. Wang, J. Wei, D. Schuurmans, Q. Le, E. Chi, and D Zhou.  Self-consistency improves chain of thought reasoning in language models.  In arXiv preprint arXiv:2203.11171, 2022.
  * [5] J. Wei, X. Wang, D. Schuurmans, M. Bosma, E. Chi, Q. Le, and D Zhou.  Chain of thought prompting elicits reasoning in large language models.  In arXiv preprint arXiv:2201.11903, 2022.
  * [6] Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V. Le, Denny Zhou, and Xinyun Chen.  Large language models as optimizers.  In arXiv preprint arXiv:2309.03409, 2023.

## APPENDIX

##  Appendix A Instruction Prompts

Objective Function Prompt :

Q :
Given the data points (y1, y2, …) = $\\{$data$\\}$, what is the MSE loss
function with respect to the ŷs for a hypothetical set of predicted ŷs values?
A :
The MSE loss function for the given data points (y1, y2, …) = $\\{$data$\\}$
with respect to ŷs is:

Gradient-Descent Prompt :

Q :
Please minimize the loss function using gradient descent with learning rate of
0.1 at point (ŷ1, ŷ2, ŷ3, …..) = $\\{$point$\\}$. What is the point we
eventually end up after one update? Your answer includes two parts an
explanation with calculation and a short answer of result.
A :
Explanation : Lets think step by step …
Short Answer: After calculation, the next update point is (ŷ$1_{new}$,
ŷ$2_{new}$, ŷ$3_{new}$, …..) =

Grid-Search Prompt (Create Grid Points) :

Q :
I want to do grid search on the ŷs and the range of them are the integers of
$\\{$low_bound$\\}$ to $\\{$high_bound$\\}$. Generate all possible
combinations of ŷs values from the specify range. What are the combinations?
Your answer includes two parts an explanation with calculation and a list
containing all the combinations.
A :
Explanation : Lets think step by step …
List : $[$write all the combinations here$]$

Grid-Search Prompt (Select) :

Q :
For every combinations of ŷs, calculate its MSE loss. Which combination has
the smallest MSE loss? Your answer includes two parts an explanation with
calculation and a list containing the combination with the smallest MSE loss.
A :
Explanation : Lets think step by step
List : [write the combination with smallest MSE loss]

Hill-Climbing Prompt (Generate Neighbors) :

Q :
I want to minimize the loss function using hill climbing. Generate neighboring
solutions by either adding 1 or minus 1 to a specific element in the current
solution. The current solution is solution. Your answer includes two parts an
explanation with calculation and a list containing all neighbor solutions(eg.
[(ŷ1, ŷ2,….), (ŷ1, ŷ2,….), …]).
A :
Explanation : Let’s think step by step …
List : [write neighbor solutions here]

Hill-Climbing Prompt (Select) :

Q :
For every neighbor solution, calculate its MSE loss. Which neighbor has the
smallest MSE loss? Your answer includes two parts an explanation with
calculation and a list containing the smallest MSE loss neighbor solution(eg.
[(ŷ1, ŷ2,….)]).
A :
Explanation : Lets think step by step …
List : [write best neighbor solution here]

Black-Box Prompt :

Q :
You want to minimize an unknown MSE loss function by guessing the values of
the ŷs. When you guess, you should take consider of the past guessing result
so that your new guess will have smaller loss than the past results. Pass
guessing result are $\\{$pass_result$\\}$. Base on the previous guesses, what
is your next guess?
A :
(ŷ1, ŷ2,….) = [your answer]

##  Appendix B Examples

For tasks except Black Box Optimization, we use the whole dialogue as a
prompt. Take the gradient-descent task as an example, the first prompt will be
the Define Loss Function section, the second prompt will be the Define Loss
Function section plus the First Iteration section and so on.

Gradient-Descent :

*Define Loss function
User :
Given the data points (y1, y2, y3) = (2,6,0), what is the MSE loss function
with respect to the ŷs for a hypothetical set of predicted ŷs values?
LLM :
The MSE loss function for the given data points (y1, y2, y3) = (2,6,0) with
respect to ŷs is:
$\frac{1}{3}[(\hat{y}_{1}-2)^{2}+(\hat{y}_{2}-6)^{2}+(\hat{y}_{3}-0)^{2}]$

*First Iteration
User :
Please minimize the loss function using gradient descent with learning rate of
0.1 at point (ŷ1, ŷ2, ŷ3) = (2,3,4). What is the point we eventually end up
after one update? Your answer includes two parts an explanation with
calculation and a short answer of result.
LLM :
Explanation : To minimize the Mean Squared Error (MSE) loss function using
gradient descent …
Short Answer: After calculation, the next update point is (ŷ$1_{new}$,
ŷ$2_{new}$, ŷ$3_{new}$) = (1.92, 3.05, 3.94)

*Second Iteration
User :
Please minimize the loss function using gradient descent with learning rate of
0.1 at point (ŷ1, ŷ2, ŷ3) = ((1.92, 3.05, 3.94). What is the point we
eventually end up after one update? Your answer includes two parts an
explanation with calculation and a short answer of result.
LLM :
Explanation : To minimize the Mean Squared Error (MSE) loss function using
gradient descent …
Short Answer: After calculation, the next update point is (ŷ$1_{new}$,
ŷ$2_{new}$, ŷ$3_{new}$) = (1.81, 3.12, 3.41)
⋮

Grid-Search :

*Define Loss function
User :
Given the data points (y1, y2, y3) = (2,6,0), what is the MSE loss function
with respect to the ŷs for a hypothetical set of predicted ŷs values?
LLM :
The MSE loss function for the given data points (y1, y2, y3) = (2,6,0) with
respect to ŷs is:
$\frac{1}{3}[(\hat{y}_{1}-2)^{2}+(\hat{y}_{2}-6)^{2}+(\hat{y}_{3}-0)^{2}]$

*Create Grid Points
User :
I want to do grid search on the ŷs and the range of them are the integers of 2
to 3. Generate all possible combinations of ŷs values from the specify range.
What are the combinations? Your answer includes two parts an explanation with
calculation and a list containing all the combinations.
LLM :
Explanation : To generate all the grid points, you should …
List : [(2, 2, 2), (2, 2, 3), (2, 3, 2), (2, 3, 3), (3, 2, 2), (3, 2, 3), (3,
3, 2), (3, 3, 3)]

*Select Best
User :
For every combinations of ŷs, calculate its MSE loss. Which combination has
the smallest MSE loss? Your answer includes two parts an explanation with
calculation and a list containing the combination with the smallest MSE loss.
LLM :
Explanation : To select the grid points with smallest MSE value …
List : [(2, 3, 3)]
⋮

Hill-Climbing :

*Define Loss function
User :
Given the data points (y1, y2, y3) = (2,6,0), what is the MSE loss function
with respect to the ŷs for a hypothetical set of predicted ŷs values?
LLM :
The MSE loss function for the given data points (y1, y2, y3) = (2,6,0) with
respect to ŷs is:
$\frac{1}{3}[(\hat{y}_{1}-2)^{2}+(\hat{y}_{2}-6)^{2}+(\hat{y}_{3}-0)^{2}]$

*Generate Neighbors
User :
I want to minimize the loss function using hill climbing. Generate neighboring
solutions by either adding 1 or minus 1 to a specific element in the current
solution. The current solution is (10,10,10). Your answer includes two parts
an explanation with calculation and a list containing all neighbor
solutions(eg. [(ŷ1, ŷ2,….), (ŷ1, ŷ2,….), …]).
LLM :
Explanation : To generate all the neighbors …
List : [(11, 10, 10), (10, 11, 10), (10, 10, 11), (9, 10, 10), (10, 9, 10),
(10, 10, 9)].

*Select Best
User :
For every neighbor solution, calculate its MSE loss. Which neighbor has the
smallest MSE loss? Your answer includes two parts an explanation with
calculation and a list containing the smallest MSE loss neighbor solution(eg.
[(ŷ1, ŷ2,….)]).
LLM :
Explanation : To select the neighbor solution with smallest MSE value …
List : [(9, 10, 10)]
⋮

As for the Black-Box task, the first prompt will be the Loss Function section
and for the subsequent iterations, the prompt will be the Loss Function
section and the prompt with new past results.

Black-Box Optimization :

*Define Loss function
User :
Given the data points (y1, y2, y3) = (2,6,0), what is the MSE loss function
with respect to the ŷs for a hypothetical set of predicted ŷs values?
LLM :
The MSE loss function for the given data points (y1, y2, y3) = (2,6,0) with
respect to ŷs is:
$\frac{1}{3}[(\hat{y}_{1}-2)^{2}+(\hat{y}_{2}-6)^{2}+(\hat{y}_{3}-0)^{2}]$

First Iteration
User :
You want to minimize an unknown MSE loss function by guessing the values of
the ŷs. When you guess, you should take consider of the past guessing result
so that your new guess will have smaller loss than the past results. Pass
guessing result are $f(2,4,6)=10$, $f(1,5,0)=2$. Base on the previous guesses,
what is your next guess?
LLM :
(ŷ1, ŷ2, ŷ3) = [$1,3,5$]

Second Iteration
User :
You want to minimize an unknown MSE loss function by guessing the values of
the ŷs. When you guess, you should take consider of the past guessing result
so that your new guess will have smaller loss than the past results. Pass
guessing result are $f(2,4,6)=10$, $f(1,5,0)=2$, $f(1,3,5)=5$. Base on the
previous guesses, what is your next guess?
LLM :
(ŷ1, ŷ2, ŷ3) = [$1,1,1$]
⋮