💻 computer science

Towards an Automated Reasoning Tool for Complexity Analysis of Automated Reasoners

This paper presents the theoretical foundation for an automated tool that analyzes the complexity of reasoning algorithms by combining user-provided insights with a novel higher-order abstract interpretation technique to extract recurrence equations, which are then solved and verified using pre/postfixpoint-based methods and SMT solvers.

Original authors: Louis Rustenholz, Manuel V. Hermenegildo, Pedro Lopez-Garcia, Alessio Mansutti, Félix Ridoux, Niki Vazou

Published 2026-06-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Louis Rustenholz, Manuel V. Hermenegildo, Pedro Lopez-Garcia, Alessio Mansutti, Félix Ridoux, Niki Vazou

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 trying to figure out exactly how long a very complicated recipe will take to cook. In the world of computer science, this is called "complexity analysis." Usually, when the recipes (algorithms) are simple, you can guess the time. But when the recipes are incredibly complex—like those used to solve difficult math problems involving logic and numbers—figuring out the time usually requires a human expert to write a massive, tedious proof by hand. It's like trying to count every single grain of sand on a beach by hand, one by one.

This paper introduces a new automated tool designed to do this counting for us, specifically for the complex "recipes" used in automated reasoning. Here is how the tool works, broken down into three simple steps using an analogy of a factory assembly line:

Step 1: The Blueprint and the "Cheat Sheet"

First, the human expert (the algorithm designer) hands the tool the "blueprint" of the algorithm. However, the tool doesn't just get the blueprint; it also gets a "cheat sheet" from the human.

The Metrics: The human tells the tool what to measure (e.g., "count the number of pages," or "measure the size of the numbers").
The Lemmas: Sometimes, the math gets too tricky for the machine to figure out on its own. The human provides a few "creative hints" or rules (lemmas) that say, "Trust me, this part behaves this way."
The Translation: The tool takes this blueprint and the cheat sheet and translates them into a simpler, standardized language (an Intermediate Representation) that the machine can easily understand. Think of this as translating a complex architectural drawing into a simple list of instructions for a robot.

Step 2: The "Magic Translator" (Abstract Compilation)

Now the tool needs to figure out how the size of the data changes as the recipe runs.

The Problem: Some measurements are easy (like the length of a list), but others are tricky (like the number of unique items in a list).
The Solution: The tool uses a special "Magic Translator" based on a technique called Abstract Interpretation.
- If the measurement is straightforward, the tool automatically figures out the rules.
- If the measurement is too complex, the tool makes a "best guess" (an over-approximation) to keep things moving.
- The Human Touch: If the tool's guess is too loose, it looks back at the "cheat sheet" (the lemmas) the human provided earlier to tighten the guess and make it more accurate.
The Output: The result of this step is a set of Recurrence Equations. Imagine these as a set of mathematical "if-then" rules that describe exactly how the workload grows at every single step of the process.

Step 3: Solving the Puzzle (Finding the Limit)

Finally, the tool has a set of rules (equations) and needs to find the final answer: "What is the maximum time this will ever take?"

The Challenge: Sometimes, standard math software (like a calculator) can solve these rules instantly. But often, these rules are so weird and complex that they have no simple "closed-form" answer (like a neat formula).
The Strategy: Instead of trying to find the perfect formula, the tool plays a game of "Guess and Check."
- It proposes a candidate answer (a "bound").
- It then uses advanced logic engines (called SMT solvers) to verify if this guess is safe. It asks, "If I start with this much work, will the rules ever let the work grow beyond this limit?"
- If the guess holds up, the tool accepts it as the answer. If not, it tries a different guess.
The Future: The authors are also looking at borrowing tricks from a field called "termination analysis" (which checks if a program ever stops) to help the tool find these answers even faster.

Why This Matters

Currently, analyzing these complex algorithms is a slow, manual process that requires writing pages of proofs. If a researcher changes the algorithm slightly, they often have to rewrite the whole proof from scratch.

This tool aims to automate the "boring" and "tedious" parts of that process. It lets the human expert focus on the creative, hard parts of the math, while the machine handles the heavy lifting of translating the code into rules and checking if the final time limits are correct. It's like giving a master chef a robot assistant that can count ingredients and time the oven perfectly, so the chef can focus on inventing new dishes.

Technical Summary: Towards an Automated Reasoning Tool for Complexity Analysis of Automated Reasoners

Problem Statement

The complexity analysis of algorithms in computational logic, particularly those involving automated reasoning (e.g., super-exponential quantifier elimination in real and integer arithmetic), is currently performed almost exclusively by hand. This manual workflow involves deriving recurrence equations to capture metric evolution during execution and proving bounds on these recurrences, often via induction. These proofs can span tens of pages and require significant human ingenuity. Furthermore, any modification to the algorithm, the set of tracked metrics, or the invariants necessitates repeating the entire tedious analysis. The authors identify a need to automate the "tedious" parts of this process while acknowledging that full automation is unrealistic for highly non-linear, non-polynomial problems, thus requiring an interactive workflow between theorem provers and automated analyzers.

Methodology

The proposed tool implements a three-stage pipeline designed to automate the extraction and solving of complexity recurrences:

1. Input and Metric Definition

The process begins by translating an algorithm from an Interactive Theorem Prover (ITP) environment (currently implemented with LiquidHaskell as a frontend) into an Intermediate Representation (IR).

Metrics: The user defines "size metrics" (integer-valued functions on data types) and provides lemmas to guide the analysis.
Catamorphic vs. Non-Catamorphic: The tool distinguishes between catamorphic metrics, where the size of a term depends only on the sizes of its constructor arguments, and non-catamorphic metrics.
- For catamorphic metrics, the tool performs fully automated recurrence extraction.
- For non-catamorphic metrics, the tool automatically generates catamorphic over-approximations, which may lose precision. To recover precision, the user provides lemmas in the ITP environment, which are assumed true in the IR to sharpen the analysis.

2. Abstract Compilation and Recurrence Extraction

The second stage employs a novel higher-order abstract interpretation technique based on operator semantics to extract generalized recurrence equations.

Operator Semantics: Instead of comparing fixed points (solutions), the tool compares the operators themselves. A program $P$ is assigned an operator $\llbracket P \rrbracket_\Phi$ .
Galois Connections: The method utilizes Galois connections to map concrete programs (viewed as operators on symbolic functions) to purely numerical programs.
Abstract Compilation: This transformation converts the symbolic IR into simplified numerical representations, such as recurrence equations on interval-valued functions or numerical logic programs. The tool supports compilation to first-order logic programs over extended integer arithmetic, which offers higher precision than interval equations.

3. Recurrence Solving and Verification

The final stage focuses on solving the extracted recurrence equations.

Beyond CAS: Recognizing that precise equations often lack closed-form solutions solvable by standard Computer Algebra Systems (CAS), the tool adopts an order-theoretical approach.
Pre/Postfixpoint Search: The tool searches for pre- and postfixpoints of the operator $\Phi$ $Φ$ to discover inductive bounds.
- If $\Phi(\hat{f}) \leq \hat{f}$ , then $\hat{f}$ is an upper bound (postfixpoint).
- If $\hat{f} \leq \Phi(\hat{f})$ , then $\hat{f}$ is a lower bound (pre-fixpoint), provided termination assumptions hold.
Verification: Verifying the inductivity condition $\forall \vec{n}, \Phi(\hat{f})(\vec{n}) \leq \hat{f}(\vec{n})$ is treated as a decision problem. The authors propose leveraging recent advances in SMT solvers, specifically integrating Yices-TRA (an extension supporting nonlinear and transcendental arithmetic), to verify candidate bounds involving polynomials, exponentials, and logarithms.

Key Contributions

Novel Abstract Compilation: The paper introduces a method for the abstract compilation of symbolic programs into numerical recursive representations using operator semantics and Galois connections, specifically tailored for catamorphic metrics.
Handling Non-Catamorphic Metrics: The framework provides a mechanism to handle complex, non-catamorphic metrics by combining automated over-approximation with user-provided lemmas to restore precision.
SMT-Based Bound Verification: The work proposes moving beyond traditional CAS for recurrence solving by utilizing SMT solvers capable of handling transcendental arithmetic to verify inductive bounds.
Interactive Workflow: The architecture explicitly supports an interactive loop where human experts provide metrics and lemmas, bridging the gap between fully manual proofs and fully automated analysis.

Results and Current Status

The paper is presented as an extended abstract describing a tool currently under development. Consequently, it does not present experimental results, benchmark comparisons, or case studies with quantitative data.

Implementation Status: The authors report that the translation from LiquidHaskell to IR is being implemented. The abstract interpreter for the IR, featuring higher-order abstract domains and a "size lifter," has been conceptualized and is in progress.
Integration: The integration of Yices-TRA as a backend for the verification phase is noted as a current activity.

Significance

The authors position this work as a step toward automating the "tedious" components of complexity analysis for complex algorithms in automated reasoning, such as quantifier elimination procedures. By formalizing the extraction of recurrences via abstract compilation and leveraging modern SMT capabilities for bound verification, the tool aims to reduce the manual burden on algorithm designers. The significance lies in its potential to handle the "creative" parts of analysis (via user lemmas) while automating the derivation and verification of the resulting bounds, thereby addressing open problems in recurrence-based cost analysis regarding non-linear invariants and broad metric classes.