tiercliff

Find every usage level where a tiered price table charges less for more, in exact arithmetic.

The problem

Usage-based price tables combine volume tiers, graduated tiers, flat fees, free allowances, package rounding, minimums, spend caps and per-line invoice rounding. Put together, they often make the total go down as usage goes up: a customer at 10,000 API calls pays 1,000.00 while one at 10,001 pays 800.08, so anyone between 8,001 and 10,000 calls should buy more than they need. Pricing teams find these by spot-checking a spreadsheet, which misses the boundaries nobody thought to test, and billing platforms validate the schema of a price table, not the function it defines. Scanning every quantity is exact but does not scale: a table reaching 10^12 units would take days to scan.

How it works

tiercliff reads a plan (TOML or JSON), compiles it into a sorted list of pieces, and analyses the pieces instead of the quantities.

1. Compilation. Every structural boundary is collected: the end of the free allowance, each tier bound (scaled by package size and shifted by the allowance) and the usage cap. Between two boundaries the billed tier is fixed, so the cost has the form

   cost(q) = base + slope * ceil((q - origin) / period)
   

   with slope >= 0. period is 1 for per-unit pricing and the package size for package pricing, which makes the piece a staircase. Each raw piece is then split where the minimum starts to bind and where the maximum is reached; those split points are solved for exactly, not searched.

2. The invariant. Validation rejects negative prices and fees, so the cost is nondecreasing inside every piece. A decrease can only happen between the last quantity of one piece and the first of the next. Checking cost(hi + 1) < cost(hi) at each piece boundary therefore finds every drop in 0..=10^12, and the work is proportional to the number of tiers, not the range.

3. Dominated range. For each run of drops, tiercliff walks back through the pieces and solves base + slope * steps(q) > landing for the smallest q. Every quantity from there to the cliff costs strictly more than buying one unit past it.

4. Invoice rounding. The rounded invoice (whole total or per line, in half-up, half-even, up or down) is nondecreasing inside each piece as well, so the same boundaries apply; the dominated range is found by binary search instead of algebra. The report lists drops that rounding introduces and drops that rounding hides.

5. Exact numbers. All amounts are rationals over i128 with checked arithmetic. Decimal literals like "0.10" are parsed straight to 1/10 and never pass through a float. Plan validation bounds quantities (10^12), unit prices (10^6), amounts (10^15) and the common denominator (10^9) so no intermediate value can overflow.

6. Comparison. compare sweeps all plans' pieces together. On each block where every plan is affine, the cheapest set can only change at the integers either side of a pairwise crossing, which is computed exactly. The output is the exact lower envelope: which plan is cheapest (or tied) for every quantity in the range.

Worked example, plans/volume.toml (0.10 up to 10,000 units, 0.08 up to 100,000, then 0.05 plus a 500 fee). The compiler produces four pieces: [0,0], [1,10000] slope 0.10, [10001,100000] slope 0.08, and [100001,10^12] slope 0.05 base 500. At the first boundary, cost(10,000) = 1000 and cost(10,001) = 800.08, a drop. Solving 0.10 q > 800.08 gives q >= 8,001, so 8,001 to 10,000 units are all dominated by buying 10,001.

Install and usage

Requires Rust 1.85 or newer. From a checkout of this repository:

cargo install --path .

or run it without installing via cargo run --release -- <args>.

tiercliff check <plan.toml|plan.json> [--json]
tiercliff compare <plan> <plan> [<plan>...] [--up-to N] [--json]
tiercliff eval <plan> <quantity>...

check exits 0 when neither the exact table nor the invoice ever decreases, 1 when cliffs exist, and 2 on invalid input, so it can gate a pricing change in CI.

Plan format

name = "api-volume"        # optional, defaults to the file name
currency = "USD"           # optional, label only
scheme = "volume"          # "volume" or "graduated" (required)
minor_units = 2            # decimals on the invoice, 0-4
included = 0               # free units deducted before billing
package_size = 1           # units per billed package, rounded up
minimum = 0                # the charge is never below this
maximum = 5000             # optional: the charge is never above this
unit_cap = 1000000         # optional: usage above this is not billed
rounding = "total"         # "total" or "per_line"
rounding_mode = "half_up"  # "half_up", "half_even", "up", "down"

[[tiers]]
up_to = 10000              # inclusive, in billed units; omit on the last tier
unit_price = "0.10"        # quote decimals or write them bare; "1/3" also works
flat_fee = 0

JSON uses the same keys ("tiers": [{...}]). Unknown keys are rejected so a typo cannot silently change a price.

A volume table with two cliffs

$ tiercliff check plans/volume.toml
api-volume: volume pricing, 3 tiers, USD
compiled into 4 pieces

price table: 2 cliffs
  10,000 -> 10,001 units: cost falls from 1000.00 to 800.08 (saves 199.92)
    8,001 to 10,000 units (2,000 quantities) all cost more than buying 10,001
  100,000 -> 100,001 units: cost falls from 8000.00 to 5500.05 (saves 2499.95)
    68,751 to 100,000 units (31,250 quantities) all cost more than buying 100,001

invoice rounding (total, half_up, 2 decimals):
  same cliffs as the price table
$ echo $?
1

A clean graduated table with a spend cap

$ tiercliff check plans/graduated.toml
storage-graduated: graduated pricing, 3 tiers, USD
compiled into 6 pieces

price table: no cliffs, cost never decreases

invoice rounding (total, half_up, 2 decimals):
  same cliffs as the price table

cost stops growing at 226,000 units (5000.00)

A cliff that only exists on the invoice

Per-line rounding: 3 units bill one line of 1.005, rounded to 1.01. 4 units bill 1.004 and a 0.004 fee, exactly 1.008, but each line rounds down, so the invoice says 1.00.

$ tiercliff check plans/per-line.toml
egress-per-line: volume pricing, 2 tiers, USD
compiled into 3 pieces

price table: no cliffs, cost never decreases

invoice rounding (per_line, half_up, 2 decimals):
  rounding introduces drops after: 3
  3 -> 4 units: cost falls from 1.01 to 1.00 (saves 0.01)
    3 units costs more than buying 4

--json prints the same report as one JSON object. Amounts are strings holding exact decimals (or n/d when the value has no finite decimal form):

$ tiercliff check plans/per-line.toml --json
{"plan":"egress-per-line","currency":"USD","pieces":3,"cliffs":[],"invoice_cliffs":[{"start":3,"end":3,"buy_up_to":4,"cost_before":"1.01","cost_after":"1","saving":"0.01","dominated_from":3}],"introduced_by_rounding":[3],"hidden_by_rounding":[],"plateau":null}

Comparing plans

$ tiercliff compare plans/starter.json plans/growth.toml
A = starter
B = growth

cheapest plan for 0..100,000 units:
        0..25,499  A       (at 0: A 0.00, B 49.00)
           25,500  A = B   (at 25,500: A 49.00, B 49.00)
  25,501..100,000  B       (at 25,501: A 49.002, B 49.00)

crossovers at: 25,500, 25,501

Without --up-to, the range is twice the last structural boundary of any plan (at least 10,000), so every feature of every plan is covered.

Evaluating single quantities

$ tiercliff eval plans/volume.toml 8000 8001 10000 10001
          8,000  exact 800  invoice 800.00
          8,001  exact 800.1  invoice 800.10
         10,000  exact 1000  invoice 1000.00
         10,001  exact 800.08  invoice 800.08

As a library

use tiercliff::{check, Plan};

let plan = Plan::from_toml(r#"
    scheme = "volume"
    [[tiers]]
    up_to = 10000
    unit_price = "0.10"
    [[tiers]]
    unit_price = "0.08"
"#, "example").unwrap();
let report = check(&plan);
assert_eq!(report.cliffs[0].dominated_from, 8_001);

Results

Correctness

The claim is that check finds exactly the drops a full scan would find. tests/oracle.rs tests that claim against a brute-force oracle, which re-implements pricing and rounding from the plan fields without calling the library's evaluator. Random plans mix both schemes, 1-5 tiers, allowances, packages, minimums, maximums, usage caps, every rounding mode and 0-3 decimal places, with prices having denominators 1, 3, 4, 100 and 1000. For each plan the oracle evaluates every quantity up to the last boundary plus a margin and asserts:

• every piece value and Plan::cost equal the oracle's cost;
• the reported exact and invoice drop points are exactly the oracle's;
• every cost_before, cost_after, saving and dominated_from matches;
• the drops introduced and hidden by rounding match, and total rounding introduces none;
• the plateau really is flat from its start and not before it.

256 random plans run with small tiers, 6 run with tiers of up to 40,000 units (around 10^5 quantities each), and 64 random two- or three-plan comparisons check the cheapest set at every quantity. tests/cli.rs checks the binary's output, exit codes and error messages, with the expected numbers worked out by hand in the comments.

cargo test

Speed

cargo run --release --example bench

Generated tables with evenly spaced tiers across 0..=10^12, random prices, occasional flat fees and a minimum of 5. Median of 11 runs, measured on an Apple Silicon Mac (aarch64-apple-darwin), rustc 1.94, release build:

scheme	tiers	pieces	cliffs	check time
volume	10	11	5	0.651 ms
volume	100	101	50	6.328 ms
volume	1000	1002	510	118.680 ms
graduated	10	12	0	0.047 ms
graduated	100	102	0	3.717 ms
graduated	1000	1001	0	377.269 ms

For contrast, scanning a 1,000-tier volume table one quantity at a time with the same exact evaluator ran 10^7 quantities in 3.13 s (3.2 million per second, with 0 drops in that prefix). At that rate the full 10^12 range takes about 87 hours. check covers the whole range in 0.12 s. Both schemes grow faster than linearly in the tier count: the invoice at each boundary is computed by the direct evaluator, which finds the tier by linear scan (volume) or sums every lower tier (graduated), and the graduated compiler does the same summation per piece.

Design notes

Pieces with a proven monotone interior, rather than sampling or symbolic algebra. The core decision is to reject negative prices and fees at validation time. That one rule makes the cost nondecreasing inside any range where the tier, the allowance and the cap are fixed. Every source of a drop (a volume tier switch, a flat fee that changes, a minimum that stops binding) must then sit on a boundary, and the set of boundaries is small and known ahead of time. This makes the search complete: it is not "we checked a lot of points" but "no other point can drop". The cost is expressiveness. Credits, discounts as negative lines, and prices that fall as a formula of usage within a tier cannot be modelled, because they would break the invariant that the proof rests on.

Exact rationals over i128 with hard input limits, rather than a bignum library or decimals. Billing bugs of one cent are exactly what this tool is for, so floats are out. Fixed-scale decimals cannot represent 1/3 per unit or the exact crossover point of two plans. A bignum crate would remove the limits but costs allocation on every operation and adds a dependency. The crate has no runtime dependencies at all; its TOML and JSON readers are small hand-written parsers for the subset plans need. The trade-off is that validation must bound quantities, amounts and the common denominator so that the largest intermediate product fits in 127 bits, and a plan outside those bounds is rejected rather than analysed. Arithmetic is still checked, so a mistake in those bounds panics instead of printing a wrong price.

Limitations

• Pricing models covered: volume and graduated tiers with per-unit prices and per-tier flat fees, one free allowance, one package size, a minimum, a maximum and a usage cap. Not covered: negative amounts (credits, discounts), per-tier package sizes, time-based proration, multiple metered dimensions priced together, and currencies or taxes applied after rounding.
• Quantities are whole units from 0 to 10^12. Fractional usage (for example GB-hours billed to three decimals) must be rescaled to integer units first.
• Unit prices are capped at 10^6, amounts at 10^15, and all denominators in a plan (or across compared plans) must share a common multiple of at most 10^9. Plans outside those bounds are rejected.
• compare is exact but visits each package step separately when a plan uses package rounding, and refuses ranges with more than 20 million steps; pass a smaller --up-to for those.
• The graduated compiler recomputes the fixed charge of all lower tiers for each piece, so compile time grows with the square of the tier count. It stays well under a second at 1,000 tiers.
• The TOML reader handles the subset plans use (key/value pairs, strings, numbers, [[tiers]] arrays, comments), not the full TOML specification.

License

MIT. See LICENSE.