refactor(cost-model): use linear costing for valueContains

[Unisay]

Summary

• Change valueContains costing from multiplied_sizes to const_above_diagonal with linear_in_x_and_y inner model
• Add LinearInXAndY constructor to SimpleJSON.hs for JSON parsing
• Update cost model visualization to support new model types
• Update V1/V2/V3 ParamName enums to match new cost model structure
• Improve benchmark data distribution (1000+ points → 570 points)

Motivation

The true complexity of valueContains is O(m*log(n/m+1)) where n is the container size and m is the contained size. Kenneth MacKenzie showed that this is bounded above by a linear function (m+n)/k for some constant k.

The new model better reflects this:

• Above diagonal (y > x): constant cost (early exit, returns False immediately)
• Below diagonal (x >= y): intercept + slope1*x + slope2*y

Benchmark Improvements

Addressed data distribution issues identified in code review:

• Reduced clustering: Below-diagonal sampling (numPolicies >= tokensPerPolicy) reduces oversampling at small sizes
• Symmetric ranges: Both container and contained now reach size 2047 (removed 1000 cap)
• Better coverage: 55 below-diagonal + 2 above-diagonal combinations (57 total)
• Fewer points: ~570 benchmark points (down from ~1000) → faster runtime
• Maintained structure: All sizes remain powers of 2 for worst-case saturated BST branches

Changes

File	Change
models.R	Update valueContainsModel to use const_above_diagonal with linear_in_x_and_y
SimpleJSON.hs	Add LinearInXAndY constructor for JSON parsing
utils.js	Add evaluators for linear_in_x_and_y and const_above_diagonal
Benchmarks/Values.hs	Improve valueContainsArgs distribution strategy
benching-conway.csv	Regenerated with improved benchmark data
builtinCostModel{A,B,C}.json	Regenerated with new model type and improved benchmarks
V{1,2,3}/ParamName.hs	Update ParamName enums from 2 to 4 CPU parameters to match new structure
Conformance tests	Updated budget expectations to match new cost parameters

New Cost Model Structure

"valueContains": {
  "cpu": {
    "arguments": {
      "constant": 358864,
      "model": {
        "arguments": {
          "intercept": 706629,
          "slope1": 2015,
          "slope2": 28294
        },
        "type": "linear_in_x_and_y"
      }
    },
    "type": "const_above_diagonal"
  },
  "memory": {
    "arguments": 32,
    "type": "constant_cost"
  }
}

Parameter Update

The new cost model structure required updating the ParamName enums in V1, V2, and V3:

Old (2 CPU parameters):

• ValueContains'cpu'arguments'intercept
• ValueContains'cpu'arguments'slope

New (4 CPU parameters):

• ValueContains'cpu'arguments'constant
• ValueContains'cpu'arguments'model'arguments'intercept
• ValueContains'cpu'arguments'model'arguments'slope1
• ValueContains'cpu'arguments'model'arguments'slope2

This fixes extractCostModelParamsLedgerOrder failures that occurred when the parameter count didn't match the expected structure.

Test plan

• Build passes
• Ledger API plugin tests pass (V1/V2/V3 validators)
• Conformance tests pass with updated budget expectations
• Cost model visualization works with new model type

Closes https://github.com/IntersectMBO/plutus-private/issues/1984

[github-actions]

PR Preview Action v1.6.3
🚀 View preview at https://IntersectMBO.github.io/plutus/pr-preview/cost-models/pr-7476/
Built to branch gh-pages at 2026-01-13 17:02 UTC. Preview will be ready when the GitHub Pages deployment is complete.

[zliu41]

👍 looks quite reasonable, but I'll leave it to @kwxm

[Unisay]

This PR replaces #7476

[kwxm]

The theoretical linear upper bound of k*(m+n) would have slope1 = slope2 here, but here the two slopes are very different! I think that's OK though: the theoretical bound is very conservative and this seems to fit the data very well.

[kwxm]

This looks good, but again I urge you to reduce the number of benchmarking inputs: see this earlier comment. We have over 1000 points here and that makes the benchmark take a very long time (> 90 minutes for just valueContains) and doesn't contribute anything to the accuracy of the model: you can see this by taking subsets of the existing data and fitting models to them. Also, the data is very unevenly distributed, which is probably not a good idea. There are 500 inputs with x<200 and y<200, so 1/25 of the space of inputs is contributing half of the datapoints, which will bias the model. Something like the below-diagonal part of a 25x25 or 30x30 grid of evenly spaced inputs (plus some points above the diagonal) would probably suffice and not lose any precision.

Also, the inputs aren't symmetric: the x values go up to 2047, but the y values only go up to 1000, so we're not always checking cases like a value containing itself, which might take some time. Can you remind me if there's some reason for this? We had earlier discussions about what the worst case would be, but I don't recall the details at the moment.

[kwxm]

Did you update the contents of benching-conway.csv"? It still contains 1052 results for ValueContains` but the new version of the benchmarks only has 607.

[Unisay]

Did you update the contents of benching-conway.csv"? It still contains 1052 results for ValueContains` but the new version of the benchmarks only has 607

My bad, fixed now:

[kwxm]

Thanks: I think we can merge this now! We'lll probably need @zliu41 to do it though.

[kwxm]

Sorry, I clicked Comment instead of Approve. Let's try try that again...