Skip to content
Strategy Cost Tables

Strategy Cost Tables

⚠ not yet verified

2026 — values checked against the current sources (key.core and key.ncore.calculus).

This appendix collects every cost constant for reference. See Strategy Costs and the Cost-Band Ladder for what the layers mean and how to choose a cost.

Cost bands

The shared cross-theory ladder (CostBand, key.ncore.calculus):

BandValueMeaning
BLOCK_CONTRACTLong.MIN_VALUEapply a block/loop contract instead of executing the block
LOOP_INVARIANT−20000apply a loop invariant instead of unrolling
CLOSE−15000close the goal (eager closure is completeness-neutral)
REWRITE−11000one-step simplification and decidable ground rewrites (concrete)
SUBST−10000force a pending substitution / eager equality (try_apply_subst)
ELIMINATE−8000eliminate updates and literals
DECOMPOSE−7000non-splitting sequent decomposition (alpha rules, update-apply-on-update)
TYPE−6000type reasoning (delta rules, type hierarchy)
NORMALIZE−5000canonicalize / order / commute terms
SIMPLIFY−4500safe, size-reducing definitional simplification and SE steps
EXECUTE−4000a symbolic-execution program step / state merge
SOLVE−3000solve direct (in)equations; apply query axioms
ENLARGE−2000useful but size-increasing simplification (e.g. comprehension / map unfolding)
PREFER−500minor local structural preference
DEFAULT0no strategic bias — apply in due (age) order
DEFER500lazy definitional unfolding, applied only when needed
DEFER_STRONG10000strongly defer
LAST_RESORT1000000finite last resort — reachable, but only when nothing else applies

Combination costs

Costs whose meaning involves more than one theory (CombinationCost, key.core):

ConstantValueMeaning
ORDERED_REWRITING−4000demodulation — apply an oriented equation as a rewrite (apply_equations); shared by the FOL and integer strategies
CNF_CONVERSION−150priority of CNF conversion (apply_equations_andOr, and FOL’s conjNormalForm)
APPLY_SELECT_EQ_EFFECTIVE−5700tuned effective cost of the applyEq taclet (apply_equations + heap apply_select_eq, summed)

Theory-local costs

Each component strategy keeps its internal ordering in one or more holders.

First-order logic — FOLStrategy

FOLCost:

ConstantValueMeaning
QUANTIFIER_DISTRIBUTION−300distrQuantifier, swapQuantifiers
CNF_RESTRUCTURE−35CNF associativity / distribution (cnf_orAssoc, cnf_andAssoc, cnf_dist)
REPLACE_KNOWN_UNDER_CONNECTIVE100defer replace_known_right under an implication/equivalence
CUT_DIRECT_STANDARD100standard cost of a direct cut
PULL_OUT_QUANTIFIER−20preferred direction of the pullOutQuantifier* rules
PULL_OUT_QUANTIFIER_REVERSE−40dispreferred direction of the pullOutQuantifier* rules

Integer arithmetic — IntegerStrategy

Split into sub-holders that anticipate a future split of the integer strategy into separate sub-strategies.

PolynomialCost — polynomial normal-form canonicalisation:

ConstantValueMeaning
EXPAND−120elimSubNeg, homo, pullOutFactor, elimOneLeft/Right
MUL_ORDER−100multiplication ordering
MUL_ASSOC−80multiplication associativity
ADD_ORDER−60addition ordering
ADD_ASSOC−10addition associativity
DISTRIBUTE−35polySimp_dist (the distLeft sub-case is DISTRIBUTE + 20)
PULLOUT_GCD−2250pull out the gcd of a polynomial

LinearEquationCost — polynomial equation solving:

ConstantValueMeaning
BALANCE−30polySimp_balance, polySimp_normalise
APPLY_EQ_MONOMIAL_TIEBREAK1tie-break rider on ORDERED_REWRITING for polySimp_applyEq; the rigid variant is + 1

LinearInequationCost — Omega / Fourier-Motzkin inequation solving:

ConstantValueMeaning
PROPAGATION−2400propagate inequations
PULLOUT_GCD_CONFLUENT−2150general gcd normalisation — confluent, applied eagerly
SATURATE−1900saturate the inequation set
FOR_NORMALISATION−1100bring an inequation into normal form
MOVE_LEFT−90move a summand to the left
MAKE_NON_STRICT−80turn a strict inequation non-strict
CONTRAD−60detect a contradiction
COMMUTE−40commute
STRENGTHEN−30strengthen
ANTISYMM−20antisymmetry
PULLOUT_GCD_ANTEC_NONCONFLUENT−10antecedent-specialised gcd pull-out — not confluent, applied opportunistically

NonlinearArithmeticCost — cross-multiplication and case distinctions:

ConstantValueMeaning
MULTIPLY1000cross-multiplication base (inEqSimp_nonLin); case-distinction offsets are MULTIPLY + n
DIVIDE_INEQUATION−1400divide an inequation by a bounded factor (the inverse of cross-multiplication)
SPLIT_EQ−100split an equation into two inequations

DivModCost — division / modulo and DefOps expansion:

ConstantValueMeaning
EXPAND_RANGES−8000expand integer range predicates
MOD_HOMO_EQ−5000modulo homomorphism on an equation
INLINE−5000inline jdiv/jmod for a literal numerator (eager, concrete)
MOD−4000literal-only division / modulo
MOD_EXPAND−3500modulo expansion for a polynomial modulus
POLY_DIVISION−2250polynomial division
EXPAND_MODULO−600expand a modulo term
EXPAND_NUMERIC_OP−500expand a defined numeric operator
BELOW_MODALITY200extra cost for defOps_div/jdiv below a modality

Symbolic execution — SymExStrategy

SymExCost:

ConstantValueMeaning
MODAL_TAUTOLOGY−10000close a modal tautology
MERGE_RULE−4000apply the merge rule
MERGE_POINT_SKIP−5000delete a merge point in skip mode (MERGE_RULE − 1000)
BOX_DIAMOND_CONV−1000convert a box/diamond towards the antecedent-polarity program
PROGRAM_STEP−100a cheap concrete program step
METHOD_CONTRACT_PREFERENCE−20preference for the method-contract feature
LOOP_CONTRACT_INTERNAL_TIEBREAK42prefer the external loop contract over the internal one
SPLIT_IF50mildly defer split_if
METHOD_EXPAND100expand a method body (in expand mode)
PROGRAM_STEP_BELOW_QUANTIFIER200a program step underneath a quantifier
THROWING_PROGRAM_STEP500a program step that would raise a tracked exception
LOOP_SCOPE_EXPAND1000expand a loop scope (in the loop-scope-expand treatment)
METHOD_EXPAND_REPRESSED2000expand a method body when contracts are preferred

Strings — StringStrategy

StringCost (negative = eager normalisation, positive = deferred unfolding; the unfolding ladder itself uses CostBand.DEFER.at(..)):

ConstantValueMeaning
INTEGER_TO_STRING−10000translate an integer to its string representation
REPLACE_INLINE−2500inline a replace when all arguments are literals
CHAR_TO_INT_LITERAL−100convert a char literal to an int literal
BELOW_MODALITY500penalty for unfolding a string definition below a modality

Heap / JavaDL — JavaCardDLStrategy

JavaCardDLCost — axiom / observer / comprehension / induction reasoning:

ConstantValueMeaning
AUTO_INDUCTION−6500apply auto-induction (like a delta rule)
JAVA_INTEGER_SEMANTICS−5000insert the java integer operator definitions
AUTO_INDUCTION_LEMMA−300apply an auto-induction lemma
CLASS_AXIOM−250apply a class axiom
LIMIT_OBSERVER−200limit an observer symbol (must beat CLASS_AXIOM)
USER_TACLET_HIGH_PRIORITY−50user taclet set to high priority
COMPREHENSION−50ordinary comprehension handling
IN_REACHABLE_STATE100inReachableState implication
DEPENDENCY_CONTRACT250apply a dependency contract
COMPREHENSION_ENLARGE10000expensive comprehension application
USER_TACLET_LOW_PRIORITY10000user taclet set to low priority
LOCSET_CNF_COMMUTE−800loc-set CNF commutation
COMPREHENSION_SIMPLIFY−5000cheap comprehension application

HeapSelectCost — the pull-out-select simplification pipeline (a candidate for a future heap/select sub-strategy):

ConstantValueMeaning
PULL_OUT_SELECT_BELOW_UPDATE−4200pull out a select below an update
PULL_OUT_SELECT−1900pull out a select otherwise
APPLY_SELECT_EQ−1700replace a select by its skolem constant (APPLY_SELECT_EQ_EFFECTIVE − ORDERED_REWRITING)
SIMPLIFY_SELECT−5600simplify the select term in the pulled-out equation
APPLY_AUXILIARY_EQ−5500replace the skolem constant by its computed value
HIDE_AUXILIARY_EQ−5400hide the auxiliary equation after replacement
HIDE_AUXILIARY_EQ_CONST−500hide the auxiliary equation, constant case