💻 computer science

Revisiting Incremental Linearization for Nonlinear Integer Arithmetic

This paper presents a revised axiomatization for incremental linearization in nonlinear integer arithmetic that significantly improves convergence on high-degree polynomial constraints, demonstrating competitive performance against state-of-the-art solvers, particularly on benchmarks dominated by such constraints.

Original authors: Marek Dančo, Karel Chvalovský, Mikoláš Janota

Published 2026-08-06

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Marek Dančo, Karel Chvalovský, Mikoláš Janota

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but the clues you are given are written in a language that changes its meaning depending on how you look at them. This is the world of Satisfiability Modulo Theories (SMT), a branch of computer science where software tries to figure out if a set of logical rules can ever be true at the same time. Think of it as a super-smart puzzle solver that checks if a program will crash, if a secret code can be cracked, or if a robot's path is safe.

Most of the time, these puzzles are easy because they only involve straight lines and simple addition (like $x + y = 5$ ). Computers are amazing at this. But life gets messy when you introduce nonlinear arithmetic—rules where things get multiplied together or raised to powers (like $x \times y$ or $x^3$ ). Suddenly, the rules curve and twist, and the math becomes incredibly hard to solve. In fact, for whole numbers, it's mathematically impossible to create a perfect, 100% complete method that solves every single one of these puzzles. Because of this, computer scientists build "good enough" detectives that use clever shortcuts to find answers quickly, even if they can't promise to solve every impossible case.

The paper you are about to read introduces a new detective, named qfn2l, which is better at solving these tricky, curvy puzzles than the ones we had before. The authors, researchers from the Czech Technical University in Prague, realized that the old shortcuts were struggling with a specific type of difficult puzzle: those involving powers (like $x^3$ ) and mixed products (like $x^2y$ ). They decided to upgrade the detective's toolkit with a fresh set of rules that act like a tighter net, catching the bad guesses that used to slip through.

The Old Way: Guessing with Uninterpreted Functions

To understand the upgrade, let's look at how the previous detectives worked. Imagine you have a mysterious box labeled $f(x, y)$ . You don't know what's inside, but you know that if you put the same numbers in, you get the same number out. The old method treated every multiplication, like $x \times y$ , as this mysterious box. The computer would guess a value for the box, check if it made sense, and if it didn't, it would add a rule to fix the guess.

This worked okay for simple cases, but it was like trying to guess the weight of a watermelon by only knowing it's "heavy." It was too vague. When the puzzle involved high powers, like $x^3$ , the old rules were too loose. The detective would guess a value, the computer would say, "Nope, that doesn't fit," and then add a very weak rule to fix it. The detective would have to guess, fail, and guess again hundreds of times, often running out of time before finding the answer.

The New Trick: Tightening the Net with Secants

The authors of this paper decided to stop treating these powers as mysterious boxes and instead treat them as fresh constants—just plain, simple numbers that represent the result of the power. But the real magic is in the new rules they added to check these numbers.

They discovered that for any whole number, say $v$ , the function $x^k$ (like $x^3$ ) behaves in a very predictable way between $v$ and $v+1$ . They created a new set of rules based on secant lines. Imagine a curve on a graph. A secant line is a straight line that connects two points on that curve. The authors realized that if you draw a straight line between the point $(v, v^k)$ and the next integer point, that line creates a very tight "fence" around the curve.

Here is the analogy:

The Old Way: The detective drew a huge, loose circle around the possible answers. It was easy to draw, but it let in a lot of wrong guesses.
The New Way: The detective draws a series of tight, straight fences (secant lines) that hug the curve of the answer very closely. If a guess falls outside these tight fences, the detective immediately knows it's wrong and adds a rule to push the guess back inside.

Because these fences are so tight, the detective doesn't have to guess as many times. It converges on the right answer much faster, especially for puzzles involving cubes and mixed products.

The "Sum of Three Cubes" Challenge

To prove their new detective was working, the authors tested it on a famous class of puzzles called the "sum of three cubes." These are problems that ask: "Can you find three whole numbers that, when you cube them and add them up, equal a specific number?"

For example, the puzzle might be: $x^3 + y^3 + z^3 = 79$ .

This is a nightmare for standard solvers. The numbers can be huge, and the relationships are complex. The authors tested their new solver, qfn2l, against the best existing solvers (like Z3, cvc5, and MathSAT).

The other solvers tried to solve the $x^3 + y^3 + z^3 = 79$ puzzle but gave up after 3 minutes (they "timed out").
The new solver, qfn2l, found the answer— $x = -19, y = 35, z = -33$ —in just 20 seconds.

The Results: A Competitive New Challenger

The researchers ran their solver on a massive collection of 25,444 puzzles from a standard library called SMT-LIB. Here is what they found:

Overall Performance: The new solver is competitive with the best tools out there. It solved about 14,000 puzzles in total, which is close to the top performers, though it didn't beat the very best (like Z3) on every single type of puzzle.
The Sweet Spot: The new solver absolutely shines on the puzzles dominated by powers and mixed products. On the "MathProblems" family (which includes the sum of cubes), it solved about 53% of the instances (585 to 587 out of 1,100). The other solvers struggled significantly more with these specific types of problems.
The Trade-off: The authors tested a version of their solver that tried to be extra careful about checking if different parts of the puzzle were consistent (called "congruence axioms"). They found that this extra checking actually slowed the solver down on general puzzles, solving about 1,600 fewer instances overall. This suggests that for most problems, the tight fences (secant bounds) are enough, and you don't need the extra heavy lifting of checking every single consistency rule.

Why This Matters

The paper doesn't claim to have solved the unsolvable. They admit that because the problem is mathematically undecidable, no computer can solve every single case. However, they have shown that by changing how we approximate these curvy, nonlinear rules—specifically by using these tight, secant-based fences—we can make the "good enough" detectives much smarter.

They have built a tool that is open-source and runs on top of an existing engine (Z3), proving that a smarter strategy can beat a brute-force approach on the hardest types of integer puzzles. For anyone trying to verify that a piece of software won't crash or that a cryptographic protocol is secure, this new method offers a faster, more reliable way to check the math behind the scenes.

In short, the authors took a messy, curvy problem and drew tighter lines around it, allowing computers to find the truth much faster than before.

Technical Summary: Revisiting Incremental Linearization for Nonlinear Integer Arithmetic

Problem Statement
The paper addresses the satisfiability problem for Quantifier-Free Nonlinear Integer Arithmetic (QF_NIA). This theory is central to automated reasoning tasks such as program verification and cryptographic protocol analysis. However, QF_NIA is undecidable, and even its rational relaxation (QF_NRA) requires doubly exponential procedures in the worst case. Consequently, practical solvers must rely on incomplete but effective techniques. While SMT solvers have achieved significant success in linear integer arithmetic (QF_LIA), extending these capabilities to nonlinear arithmetic remains a substantial challenge.

Methodology
The authors propose a revised approach to Incremental Linearization, a Counterexample-Guided Abstraction Refinement (CEGAR) strategy. Unlike prior work that abstracts nonlinear terms using uninterpreted function symbols (UFLIA), this approach abstracts each nonlinear subterm (monomials $x^k$ and mixed products $x^k y^l$ ) as a fresh constant (termed a "pure"). This allows the solver to work entirely within the domain of QF_LIA.

The algorithm proceeds as follows:

Purification and Normalization: Nonlinear monomials are normalized and replaced by fresh constants. For example, $x^2$ is replaced by a constant $p$ , and the constraint $x^2 \leq x$ becomes $p \leq x$ .
Abstraction and Solving: The abstracted formula is solved using a QF_LIA solver.
NIA Check: If a model is found, it is checked against the original nonlinear semantics.
Refinement: If the model is spurious (i.e., the pure constant's value does not match the actual nonlinear evaluation), the solver identifies the offending terms. Instead of relying solely on uninterpreted function congruence, the solver adds explicit linear axioms to the abstraction to rule out the spurious model.
Model Repair: Before regenerating axioms, a heuristic "Model-Fix" attempts to patch the spurious model by pinning irrelevant variables and running restricted LIA iterations.

Key Contributions
The primary contribution of this work is a new family of secant-based linear axioms specifically designed for monomials $x^k$ and mixed products $x^k y^l$ .

Secant-Based Bounds: The authors observe that on any unit integer interval $[v, v+1]$ , the function $t \mapsto t^k$ admits tight piecewise-linear over- and under-approximations. By instantiating these bounds at the current model values, the solver generates significantly tighter linearizations than the general-purpose axioms (sign, zero, neutrality, proportionality, and tangent-plane) used in prior work.
Handling Higher-Degree Monomials: These axioms are particularly effective for constraints dominated by higher-degree monomials (powers and mixed products), a class of problems where previous axiomatizations often failed to converge within practical time limits.
Congruence Handling: By using pure constants rather than uninterpreted functions, congruence is not enforced automatically by the solver. Instead, the system adds congruence axioms only when violations are observed. Experimental results suggest such violations are rare, making this overhead negligible.
Implementation: The authors implemented a standalone solver, qfn2l, built on top of the Z3 QF_LIA backend.

Experimental Results
The solver was evaluated on the full QF_NIA benchmark suite from SMT-LIB against state-of-the-art solvers: Z3, cvc5, Yices 2, and MathSAT.

Overall Performance: On the full benchmark set, qfn2l is competitive with other solvers, though it trails behind Z3 and MathSAT on general instances. The authors attribute this to the fact that competing solvers utilize complementary techniques (e.g., bit-blasting) that are highly effective for large-variable instances with shallow nonlinear structures.
Polynomial Constraints: The approach substantially outperforms state-of-the-art solvers on benchmarks dominated by polynomial constraints, specifically sums of cubes.
- Example: On the "sum of three cubes" benchmark ( $x^3 + y^3 + z^3 = 79$ ), Z3, cvc5, MathSAT, and Yices all timed out (3-minute limit), whereas qfn2l found the solution in approximately 20 seconds.
- On the MathProblems family (1,100 instances involving number-theoretic problems), qfn2l solved 585–587 instances (53%), a direct result of the improved convergence on cubic constraints provided by the secant-based axioms.

Significance and Claims
The paper claims that the explicit treatment of power terms with fixed exponents as first-class abstractions yields a measurable advantage on problems where such expressions occur. The authors emphasize that while the problem is undecidable and no complete procedure exists, their approach improves the practical effectiveness of incremental linearization for a specific, challenging class of nonlinear constraints.

The work demonstrates that refining the axiom set with secant-based bounds allows the solver to converge on hard polynomial benchmarks that previously stymied general-purpose incremental linearization approaches. The authors position their contribution not as a replacement for all existing techniques (acknowledging the strength of bit-blasting for certain instance types) but as a specialized, effective enhancement for handling higher-degree monomials within the incremental linearization framework.

The Old Way: Guessing with Uninterpreted Functions

The New Trick: Tightening the Net with Secants

The "Sum of Three Cubes" Challenge

The Results: A Competitive New Challenger

Why This Matters

More like this