Add an option to make the success probability estimation nonlinear #2547

TheBlueMatt · 2023-09-02T02:28:38Z

Our "what is the success probability of paying over a channel with
the given liquidity bounds" calculation currently assumes the
probability of where the liquidity lies in a channel is constant
across the entire capacity of a channel. This is obviously a
somewhat dubious assumption given most nodes don't materially
rebalance and flows within the network often push liquidity
"towards the edges".

Here we add an option to consider this when scoring channels during
routefinding. Specifically, if a new linear_success_probability
flag is set on ProbabilisticScoringFeeParameters, rather than
assuming a PDF of 1 (across the channel's capacity scaled from 0
to 1), we use (x - 0.5)^6.

This assumes liquidity is very likely to be near the edges, which
matches experimental results. Further, calculating the CDF (i.e.
integral) between arbitrary points on the PDF is trivial, which we
do as our main scoring function.

While this (finally) introduces floats in our scoring, its not
practical to exponentiate using fixed-precision, and benchmarks
show this is a performance regression, but not a huge one, more
than made up for by the increase in payment success rates.

~~Depends on #2176~~

TheBlueMatt · 2023-09-12T15:56:20Z

lightning/src/routing/scoring.rs

+
+/// min_zero_implies_no_successes signals that an `amount_msat` of 0 means we've not (recently)
+/// seen an HTLC successfully complete over this channel.
+fn success_probability(


We should think about making this pub so users can figure out what the probability is in the liquidity bounds model. Or we can expose the probability from that model directly.

TheBlueMatt · 2023-09-16T00:03:02Z

Rebased, now free-standing.

arik-so · 2023-09-17T06:30:58Z

lightning/src/routing/scoring.rs

+			let num = max_pow - (amount - 0.5).powi(3);
+			let den = max_pow - (min - 0.5).powi(3);
+
+			// Because our numerator and denominator max out at 2^-3 we need to multiply them by


both the numerator and denominator max out at 1/8th?

I showed the math instead - 0.5^3.

lightning/src/routing/scoring.rs

jkczyz

Still reviewing 99dc821.

lightning/src/routing/scoring.rs

jkczyz · 2023-09-18T21:13:25Z

lightning/src/routing/scoring.rs

@@ -1887,14 +1906,13 @@ mod bucketed_history {
 				}
 				let max_bucket_end_pos = BUCKET_START_POS[32 - highest_max_bucket_with_points] - 1;
 				if payment_pos < max_bucket_end_pos {
+					let (numerator, denominator) = success_probability(0, payment_pos as u64,
+						max_bucket_end_pos as u64, POSITION_TICKS as u64 - 1, params, true);


What's the reason for using POSITION_TICKS for the capacity parameter?

All the parameters here are scaled to POSITION_TICKS (i.e. because they're now pos', rather than msat amounts).

lightning/src/routing/scoring.rs

jkczyz · 2023-09-18T21:58:22Z

lightning/src/routing/scoring.rs

+	if min_zero_implies_no_successes && min_liquidity_msat == 0 &&
+		denominator < u64::max_value() / 21
+	{
+		// If we have no knowledge of the channel, scale probability down by ~75%
+		// Note that we prefer to increase the denominator rather than decrease the numerator as
+		// the denominator is more likely to be larger and thus provide greater precision. This is
+		// mostly an overoptimization but makes a large difference in tests.
+		denominator = denominator * 21 / 16
+	}


Could we instead have a separate function that delegates to success_probability rather than passing a bool?

I was trying to avoid it, since the singular method is really "the model", and how the "no data" bit is interpreted may change in the future to be a part of the greater math.

But it sounds like the parameter is only true for historical probabilities, right? We pass false for the current liquidity estimate.

Currently, yea. I think we probably want to change that in the future, but I didn't want to change everything in one go in the same model change.

jkczyz · 2023-09-18T22:04:06Z

lightning/src/routing/scoring.rs

@@ -1273,13 +1264,12 @@ impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> ScoreLookUp for Prob
 			_ => {},
 		}

-		let amount_msat = usage.amount_msat;
+		let amount_msat = usage.amount_msat.saturating_add(usage.inflight_htlc_msat);


Won't this affect calculations for parameters like base_penalty_amount_multiplier_msat, liquidity_penalty_amount_multiplier_msat, etc? Those help avoid fees dominating the channel cost, but those fees will be calculated using amount_msat.

It would, but the other way around - it would result in score penalties dominating fees, which I think is what we want - if we already have a pending payment for X over a channel, we want to be careful paying more.

Here, cost is penalty plus fees, so I think what I said was accurate, no?

Anyhow, we'll need to update the configuration docs now that this includes in-flight HTLCs.

Then I'm not quite sure what you're saying, I think. The docs dont look out of date given they dont mention how we handle in-flight HTLCs, though we could consider describing it.

There are a few places where we say "payment amount" and sometimes explicitly amount_msat, e.g.:

rust-lightning/lightning/src/routing/scoring.rs

Lines 457 to 464 in a7e3575

/// A multiplier used with the payment amount to calculate a fixed penalty applied to each

/// channel, in excess of the [`base_penalty_msat`].

///

/// The purpose of the amount penalty is to avoid having fees dominate the channel cost (i.e.,

/// fees plus penalty) for large payments. The penalty is computed as the product of this

/// multiplier and `2^30`ths of the payment amount.

///

/// ie `base_penalty_amount_multiplier_msat * amount_msat / 2^30`

I updated a few of them.

codecov-commenter · 2023-09-18T23:35:27Z

Codecov Report

Patch coverage: 86.98% and project coverage change: +0.52% 🎉

Comparison is base (53c8f89) 90.63% compared to head (f2b2920) 91.15%.
Report is 30 commits behind head on main.

❗ Your organization needs to install the Codecov GitHub app to enable full functionality.

Additional details and impacted files

@@            Coverage Diff             @@
##             main    #2547      +/-   ##
==========================================
+ Coverage   90.63%   91.15%   +0.52%     
==========================================
  Files         113      115       +2     
  Lines       59057    90304   +31247     
  Branches    59057    90304   +31247     
==========================================
+ Hits        53524    82321   +28797     
- Misses       5533     7497    +1964     
- Partials        0      486     +486

Files Changed	Coverage Δ
lightning/src/routing/scoring.rs	`92.45% <86.39%> (-1.83%)`	⬇️
lightning/src/routing/router.rs	`94.92% <100.00%> (+0.43%)`	⬆️
lightning/src/util/ser.rs	`85.95% <100.00%> (+0.35%)`	⬆️

... and 106 files with indirect coverage changes

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

lightning/src/routing/scoring.rs

jkczyz · 2023-09-18T23:56:38Z

lightning/src/routing/scoring.rs

+			// Because the integral is simply a constant times (x - 0.5)^3, this means we simply
+			// subtract the two bounds mius 0.5 to the 3rd power.


I did a little refresher on integrals, but I don't understand this sentence. What is the constant here? And how does the second half of the sentence follow from the first?

My understanding is that a 1/3 constant after integrating disappears because we are dividing two integrals.

errr, sorry, i had a constant multiple (to normalize to a total probability of 1) in my head but not in the above comment. I've removed it and reworded the comment to be both correct and clearer.

lightning/src/routing/scoring.rs

jkczyz · 2023-09-19T00:19:25Z

lightning/src/routing/scoring.rs

@@ -1051,8 +1051,10 @@ fn success_probability(
 			// the amount, divided by the same integral from the minimum to the maximum liquidity
 			// bounds.
 			//
-			// Because the integral is simply a constant times (x - 0.5)^3, this means we simply
-			// subtract the two bounds mius 0.5 to the 3rd power.
+			// Because the integral from x to y is simply (y - 0.5)^3 - (x - 0.5)^3, we can


Isn't the integral technically divided by 3? But then dividing the numerator by denominator eliminates it?

Yea, but in practice the actual CDF is N*((y - 0.5)^3 - (x - 0.5)^3) where N is a function of x and y, cause we have to have a total from min to max of 100%/1.

jkczyz

Commit message for b9e132a is wrong as it mixes up how linear_success_probability is interpreted.

TheBlueMatt · 2023-09-19T16:32:31Z

Fixed the commit message and no-std.

lightning/src/routing/router.rs

jkczyz

Feel free to squash the outstanding fixups.

jkczyz · 2023-09-19T20:50:09Z

lightning/src/routing/scoring.rs

@@ -1017,9 +1035,9 @@ impl<L: Deref<Target = u64>, BRT: Deref<Target = HistoricalBucketRangeTracker>,
 					score_params.liquidity_penalty_amount_multiplier_msat)
 				.saturating_add(score_params.considered_impossible_penalty_msat)
 		} else {
-			let numerator = (max_liquidity_msat - amount_msat).saturating_add(1);


Could you mention in the commit message why the plus one is removed?

Updated the commit message!

jkczyz · 2023-09-19T20:51:04Z

lightning/src/routing/scoring.rs

-						// Add an additional one in the divisor as the payment bucket has been
-						// rounded down.
-						(max_bucket_end_pos + 1) as u64;


Why is this no longer required?

There is still a + 1 in the denominator, so its actually still there for the linear scoring, but really we don't need it anymore because we have way more positions in the buckets. It doesnt really make sense now that we aren't doing the crazy sub-bucket positioning thing, but rather just making everything discrete against 16000 points.

lightning/src/routing/scoring.rs

Our "what is the success probability of paying over a channel with the given liquidity bounds" calculation is reused in a few places, and is a key assumption across our main score calculation and the historical bucket score calculations. Here we break it out into a function to make it easier to experiment with different success probability calculations. Note that this drops the numerator +1 in the liquidity scorer, which was added to compensate for the divisor + 1 (which exists to avoid divide-by-zero), making the new math slightly less correct but not by any material amount.

If we are examining a channel for which we have no information at all, we traditionally assume the HTLC success probability is proportional to the channel's capacity. While this may be the case, it is not the case that a tiny payment over a huge channel is guaranteed to succeed, as we assume. Rather, the probability of such success is likely closer to 50% than 100%. Here we try to capture this by simply scaling the success probability for channels where we have no information down linearly. We pick 75% as the upper bound rather arbitrarily - while 50% may be more accurate, its possible it would lead to an over-reliance on channels which we have paid through in the past, which aren't necessarily always the best candidates. Note that we only do this scaling for the historical bucket tracker, as there we can be confident we've never seen a successful HTLC completion on the given channel. If we were to apply the same scaling to the simple liquidity bounds based scoring we'd penalize channels we've never tried over those we've only ever fails to pay over, which is obviously not a good outcome.

jkczyz

LGTM. Feel free to squash.

TheBlueMatt · 2023-09-20T04:21:58Z

Squashed without further changes.

lightning/src/routing/scoring.rs

When we started considering the in-flight amounts when scoring, we took the approach of considering the in-flight amount as an effective reduction in the channel's total capacity. When we were scoring using a flat success probability PDF, that was fine, however in the next commit we'll move to a highly nonlinear one, which makes this a pretty confusing heuristic. Here, instead, we move to considering the in-flight amount as simply an extension of the amount we're trying to send over the channel, which is equivalent for the flat success probability PDF, but makes much more sense in a nonlinear world.

Our "what is the success probability of paying over a channel with the given liquidity bounds" calculation currently assumes the probability of where the liquidity lies in a channel is constant across the entire capacity of a channel. This is obviously a somewhat dubious assumption given most nodes don't materially rebalance and flows within the network often push liquidity "towards the edges". Here we add an option to consider this when scoring channels during routefinding. Specifically, if a new `linear_success_probability` flag is unset on `ProbabilisticScoringFeeParameters`, rather than assuming a PDF of `1` (across the channel's capacity scaled from 0 to 1), we use `(x - 0.5)^2`. This assumes liquidity is likely to be near the edges, which matches experimental results. Further, calculating the CDF (i.e. integral) between arbitrary points on the PDF is trivial, which we do as our main scoring function. While this (finally) introduces floats in our scoring, its not practical to exponentiate using fixed-precision, and benchmarks show this is a performance regression, but not a huge one, more than made up for by the increase in payment success rates.

TheBlueMatt · 2023-09-20T18:32:48Z

COrrected the docs one more time, but went ahead and squashed:

$ git diff-tree -U2 f25535b7 f2b2920b
diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs
index 638e8ddf6..6bdf59e85 100644
--- a/lightning/src/routing/scoring.rs
+++ b/lightning/src/routing/scoring.rs
@@ -494,6 +494,6 @@ pub struct ProbabilisticScoringFeeParameters {
 	/// The purpose of the amount penalty is to avoid having fees dominate the channel cost (i.e.,
 	/// fees plus penalty) for large payments. The penalty is computed as the product of this
-	/// multiplier and `2^20`ths of the payment amount, weighted by the negative `log10` of the
-	/// success probability.
+	/// multiplier and `2^20`ths of the amount flowing over this channel, weighted by the negative
+	/// `log10` of the success probability.
 	///
 	/// `-log10(success_probability) * liquidity_penalty_amount_multiplier_msat * amount_msat / 2^20`
@@ -530,6 +530,7 @@ pub struct ProbabilisticScoringFeeParameters {
 	///
 	/// The purpose of the amount penalty is to avoid having fees dominate the channel cost for
-	/// large payments. The penalty is computed as the product of this multiplier and the `2^20`ths
-	/// of the payment amount, weighted by the negative `log10` of the success probability.
+	/// large payments. The penalty is computed as the product of this multiplier and `2^20`ths
+	/// of the amount flowing over this channel, weighted by the negative `log10` of the success
+	/// probability.
 	///
 	/// This penalty is similar to [`liquidity_penalty_amount_multiplier_msat`], however, instead
$

TheBlueMatt added the blocked on dependent pr label Sep 2, 2023

TheBlueMatt added this to the 0.0.117 milestone Sep 2, 2023

TheBlueMatt mentioned this pull request Sep 7, 2023

Move the historical bucket tracker to 32 unequal sized buckets #2176

Merged

TheBlueMatt commented Sep 12, 2023

View reviewed changes

TheBlueMatt mentioned this pull request Sep 14, 2023

Some thoughts on payment splitting heuristics for multi part payments #2276

Open

TheBlueMatt removed the blocked on dependent pr label Sep 16, 2023

TheBlueMatt force-pushed the 2023-04-nonlinear-scoring branch from 210c193 to 01985b7 Compare September 16, 2023 00:02

TheBlueMatt force-pushed the 2023-04-nonlinear-scoring branch 4 times, most recently from 57a607e to 6af62f1 Compare September 16, 2023 23:06

arik-so reviewed Sep 17, 2023

View reviewed changes

TheBlueMatt force-pushed the 2023-04-nonlinear-scoring branch 2 times, most recently from 85514dc to 972b965 Compare September 18, 2023 16:52

jkczyz self-requested a review September 18, 2023 17:07

jkczyz reviewed Sep 18, 2023

View reviewed changes

TheBlueMatt force-pushed the 2023-04-nonlinear-scoring branch from 972b965 to e424cd6 Compare September 18, 2023 23:24

jkczyz reviewed Sep 18, 2023

View reviewed changes

TheBlueMatt force-pushed the 2023-04-nonlinear-scoring branch from e424cd6 to fa20962 Compare September 19, 2023 00:08

jkczyz reviewed Sep 19, 2023

View reviewed changes

TheBlueMatt force-pushed the 2023-04-nonlinear-scoring branch from fa20962 to 2057cf0 Compare September 19, 2023 01:21

jkczyz reviewed Sep 19, 2023

View reviewed changes

TheBlueMatt force-pushed the 2023-04-nonlinear-scoring branch 3 times, most recently from cff9d5d to 901e721 Compare September 19, 2023 17:25

jkczyz reviewed Sep 19, 2023

View reviewed changes

lightning/src/routing/router.rs Outdated Show resolved Hide resolved

TheBlueMatt force-pushed the 2023-04-nonlinear-scoring branch from 901e721 to 77342c4 Compare September 19, 2023 20:36

jkczyz reviewed Sep 19, 2023

View reviewed changes

TheBlueMatt added 2 commits September 19, 2023 21:22

TheBlueMatt force-pushed the 2023-04-nonlinear-scoring branch from 77342c4 to 689c2bc Compare September 19, 2023 21:23

jkczyz reviewed Sep 20, 2023

View reviewed changes

TheBlueMatt force-pushed the 2023-04-nonlinear-scoring branch from 689c2bc to f25535b Compare September 20, 2023 04:21

jkczyz previously approved these changes Sep 20, 2023

View reviewed changes

lightning/src/routing/scoring.rs Show resolved Hide resolved

lightning/src/routing/scoring.rs Show resolved Hide resolved

TheBlueMatt added 3 commits September 20, 2023 18:32

Avoid unnecessary newline in middle of log statement

f2b2920

TheBlueMatt dismissed jkczyz’s stale review via f2b2920 September 20, 2023 18:32

TheBlueMatt force-pushed the 2023-04-nonlinear-scoring branch from f25535b to f2b2920 Compare September 20, 2023 18:32

jkczyz approved these changes Sep 20, 2023

View reviewed changes

arik-so approved these changes Sep 20, 2023

View reviewed changes

TheBlueMatt merged commit f2fe95e into lightningdevkit:main Sep 20, 2023
14 of 15 checks passed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add an option to make the success probability estimation nonlinear #2547

Add an option to make the success probability estimation nonlinear #2547

TheBlueMatt commented Sep 2, 2023 •

edited

Loading

TheBlueMatt Sep 12, 2023

TheBlueMatt commented Sep 16, 2023

arik-so Sep 17, 2023

TheBlueMatt Sep 17, 2023

jkczyz left a comment

jkczyz Sep 18, 2023

TheBlueMatt Sep 18, 2023

jkczyz Sep 18, 2023

TheBlueMatt Sep 18, 2023

jkczyz Sep 19, 2023

TheBlueMatt Sep 19, 2023

jkczyz Sep 18, 2023

TheBlueMatt Sep 18, 2023

jkczyz Sep 19, 2023

TheBlueMatt Sep 19, 2023

jkczyz Sep 19, 2023

TheBlueMatt Sep 19, 2023

codecov-commenter commented Sep 18, 2023 •

edited

Loading

jkczyz Sep 18, 2023

TheBlueMatt Sep 19, 2023

jkczyz Sep 19, 2023

TheBlueMatt Sep 19, 2023

jkczyz left a comment

TheBlueMatt commented Sep 19, 2023 •

edited

Loading

jkczyz left a comment

jkczyz Sep 19, 2023

TheBlueMatt Sep 19, 2023

jkczyz Sep 19, 2023

TheBlueMatt Sep 19, 2023

jkczyz left a comment

TheBlueMatt commented Sep 20, 2023

TheBlueMatt commented Sep 20, 2023

	/// A multiplier used with the payment amount to calculate a fixed penalty applied to each
	/// channel, in excess of the [`base_penalty_msat`].
	///
	/// The purpose of the amount penalty is to avoid having fees dominate the channel cost (i.e.,
	/// fees plus penalty) for large payments. The penalty is computed as the product of this
	/// multiplier and `2^30`ths of the payment amount.
	///
	/// ie `base_penalty_amount_multiplier_msat * amount_msat / 2^30`

		// Because the integral is simply a constant times (x - 0.5)^3, this means we simply
		// subtract the two bounds mius 0.5 to the 3rd power.

Add an option to make the success probability estimation nonlinear #2547

Add an option to make the success probability estimation nonlinear #2547

Conversation

TheBlueMatt commented Sep 2, 2023 • edited Loading

Choose a reason for hiding this comment

TheBlueMatt commented Sep 16, 2023

Choose a reason for hiding this comment

Choose a reason for hiding this comment

jkczyz left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

codecov-commenter commented Sep 18, 2023 • edited Loading

Codecov Report

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

jkczyz left a comment

Choose a reason for hiding this comment

TheBlueMatt commented Sep 19, 2023 • edited Loading

jkczyz left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

jkczyz left a comment

Choose a reason for hiding this comment

TheBlueMatt commented Sep 20, 2023

TheBlueMatt commented Sep 20, 2023

TheBlueMatt commented Sep 2, 2023 •

edited

Loading

codecov-commenter commented Sep 18, 2023 •

edited

Loading

TheBlueMatt commented Sep 19, 2023 •

edited

Loading