A model with a million decisions sounds harder than a model with a thousand. Sometimes it is. But the number of variables is only one part of an optimization problem's difficulty.
A million independent choices may be easy. A thousand tightly coupled choices, where each affects many others, can create a remarkably difficult search.
This distinction helps explain why the size printed beside a benchmark does not by itself predict how a solver will perform.
A million easy decisions
Imagine choosing whether to accept each of a million independent offers. Each accepted offer has a known value and no offer affects another. If the goal is to maximize total value with no shared limits, every decision can be made separately: accept a positive-value offer, reject a negative-value one. The problem contains a million yes-or-no variables but does not require exploring every combination.
Now imagine selecting a much smaller set of jobs that compete for machines, staff and deadlines. Accepting one job may displace several others. The value of a decision depends on the whole collection. Local choices can lead to poor global outcomes.
The difficulty comes from interactions, not the mere existence of many variables.
The graph beneath the model
Many optimization problems can be pictured as graphs. Variables are nodes; relationships or constraints link them. If the graph separates into independent components, the problem may decompose into smaller pieces that can be solved separately and combined.
If the graph is densely connected, a change in one decision may propagate across a large part of the model. Graph structure, symmetry, coefficient patterns and the presence of tight global constraints can all influence computational difficulty.
Even a sparse model can be difficult when its few connections create a challenging global structure. Conversely, a huge sparse model may be approachable if its components are nearly independent or follow a regular pattern that an algorithm can exploit.
A QUBO makes those interactions visible as a graph. Each binary variable is a node, and an edge connects a pair whose joint choice affects the objective. Disconnected components can be solved independently; clusters joined by a small number of connections may offer opportunities for decomposition. More subtle graph properties, including separators and treewidth, help explain why sparse models with similar sizes can behave differently.
The graph alone is not the full story. Two models with the same connections may have very different coefficient patterns. Strongly competing interactions can produce many local minima, while regular relationships may enable specialized algorithms to make rapid progress. For a QUBO evaluation, the distribution of interaction strengths belongs alongside size and density in the description of the workload.
Size is not the same as memory demand
A model's practical resource use also depends on how its data are represented. A dense quadratic objective involving a million variables would contain an enormous number of possible pairwise terms. A sparse model of the same nominal size might store only a small fraction of those connections.
The number of nonzero coefficients, memory layout and operations needed per search step may matter as much as the advertised variable count. So do the time allowed and the quality of solution required.
This is why a meaningful QUBO benchmark, for example, should report the model family and structure alongside its variable count, not present a size figure as a universal measure of capability.
Measure the problems you actually have
Suppose an organization is planning a solver evaluation. It has ten ordinary instances, two extreme peak-season cases and one instance representing a new product line. A random selection of artificial problems with the same variable counts may miss the features that make those real cases difficult.
Better evaluation preserves relevant structure: connectivity, constraint tightness, coefficient distributions, scale and the pattern of changes between runs. It asks how quickly the solver produces a useful answer and how quality improves under a realistic budget.
The counterintuitive lesson is liberating. Complexity is not destiny. When an algorithm discovers structure that a naive search ignores, a vast problem can become manageable. Understanding that structure is one of the central arts of optimization.