in the expected search time:

$$\Lambda_{i}=\mathbb{E}\left[T^{s|\omega_{-}}-T^{s|\omega_{+}i}\right]\tag{7}$$

where ω− is the optimal ordering based on priors, and ω+i on values after updating Ti, pi. Computing new estimates (with overhead T
c) for values Ti, piis beneficial just when the net VOI is positive:
Vi = Λi − T
c(8)
To simplify estimation of Λi, the expected search time of an ordering is estimated as though the parameters are computed only for ω−(1) (essentially the metareasoning subtree independence assumption). Other value assignments are assumed to have the prior ("default") parameters Tdef, pdef. Assume w.l.o.g. that ω−(1) = 1:

$$T^{s|\omega_{-}}=T_{1}+p_{1}\sum_{i=2}^{|D_{k}|}T_{\rm def}p_{\rm def}^{i-2}=T_{1}+p_{1}T_{\rm def}\frac{1-p_{\rm def}^{(|D_{k}|-1)}}{1-p_{\rm def}}\tag{9}$$
(9)
and the intrinsic VOI of the ith deliberation action is:
$$\Lambda_{i}=\mathbb{E}\left[G(T_{i},p_{i})\,\Big{|}\,\frac{T_{i}}{1-p_{i}}<\frac{T_{1}}{1-p_{1}}\right]\tag{10}$$  $T_{i}=\mathbb{E}$ is the probability of the 
where G(Ti, pi) is the search time gain given the heuristically computed values Ti, pi:

$$G(T_{i},p_{i})=T_{1}-T_{i}+(p_{1}-p_{i})T_{\mathrm{def}}\frac{1-p_{\mathrm{def}}^{(|D_{k}|-1)}}{1-p_{\mathrm{def}}}\tag{11}$$

In some cases, H provides estimates only for the expected search time Ti. In such cases, the backtracking probability pi can be bounded by the Markov inequality as the probability for the given assignment that the time t to find a solution or verify that no solution exists is at least the time T
all ito find all solutions: pi = Pt ≥ T
all i≤Ti T
all i, and the bound can be used as the probability estimate:

 $\ p_i\approx\dfrac{T_i}{T_i^{all}}$  at in harder problems the prob. 
$$(12)^{\frac{1}{2}}$$
Furthermore, note that in harder problems the probability of backtracking from variable Xk is proportional to p
(|Dk|−1)
def ,
and it is reasonable to assume that backtracking probabilities above Xk (trying values for X1*, ..., X*k−1) are still significantly greater than 0. Thus, the "default" backtracking probability pdef is close to 1, and consequently:

$$T_{i}^{all}\approx T_{\rm def},\quad\frac{1-p_{\rm def}^{(|D_{k}|-1)}}{1-p_{\rm def}}\approx|D_{k}|-1\tag{13}$$  By substituting (12), (13) into (11), estimate (14) for 
G(Ti, pi) is obtained:
$$G(T_{i},p_{i})\approx T_{1}-T_{i}+(\frac{T_{1}}{T_{1}^{all}}-\frac{T_{i}}{T_{i}^{all}})T_{\rm def}\frac{1-p_{\rm def}^{(|D_{k}|-1)}}{1-p_{\rm def}}\tag{14}$$ $$\approx(T_{1}-T_{i})|D_{k}|$$  Finally, since (12), (13) imply that $T_{i}<T_{1}\Leftrightarrow\frac{T_{i}}{1-p_{i}}<\frac{T_{1}}{1-p_{1}}$,  $$\Lambda_{i}\approx\mathbb{E}\left[(T_{1}-T_{i})|D_{k}|\ \Big{|}\ T_{i}<T_{1}\right]\tag{15}$$

## 4 Voi Of Solution Count Estimates

The estimated solution count for an assignment may be used to estimate the expected time to find a solution for the assignment under the following assumptions1:
1. Solutions are roughly evenly distributed in the search space, that is, the distribution of time to find a solution can be modeled by a Poisson process.

2. Finding all solutions for an assignment Xk = yki takes roughly the same time for all assignments to the variable Xk. Prior work [Meisels *et al.*, 1997; Kask *et al.*, 2004]
demonstrates that ignoring the differences in subproblem sizes is justified.

3. The expected time to find all solutions for an assignment divided by its solution count estimate is a reasonable estimate for the expected time to find a single solution.
Based on these assumptions, Ti can be estimated as T
all |Dk|ni where T
all is the expected time to find all solutions for all values of Xk, and niis the solution count estimate for yki; likewise, T1 =T
all |Dk|nmax
, where nmax is the currently greatest ni. By substituting the expressions for Ti, T1 into (15), obtain as the intrinsic VOI of computing ni:

$$\Lambda_{i}=T^{a l l}\sum_{n=n_{\mathrm{max}}}^{\infty}\left(\frac{1}{n_{\mathrm{max}}}-\frac{1}{n}\right)P(n,\nu)\qquad\mathrm{(16)}$$

where P(*n, ν*) = e
−ν ν n n!

is the probability, according to the Poisson distribution, to find n solutions for a particular assignment when the mean number of solutions per assignment is ν =N
|Dk|
, and N is the estimated solution count for all values of Xk, computed at an earlier stage of the algorithm.

Neither T
all nor T
c, the time to estimate the solution count for an assignment, are known. However, for relatively low solution counts, when an invocation of the heuristic has high intrinsic VOI, both T
all and T
care mostly determined by the time spent eliminating non-solutions. Therefore, T
ccan be assumed approximately proportional to T
all |Dk|
, the average time to find all solutions for a single assignment, with an unknown factor γ < 1.

$$T^{c}\approx\gamma\frac{T^{all}}{|D_{k}|}\tag{17}$$

Then, T
all can be eliminated from both T
cand Λ. Following Equation (8), the solution count should be estimated whenever the net VOI is positive:

$$V(n_{\mathrm{max}})\propto|D_{k}|e^{-\nu}\sum_{n=n_{\mathrm{max}}}^{\infty}\left(\frac{1}{n_{\mathrm{max}}}-\frac{1}{n}\right)\frac{\nu^{n}}{n!}-\gamma\tag{18}$$

The infinite series in (18) rapidly converges, and an approximation of the sum can be computed efficiently. As done in 1We do not claim that this is a valid model of CSP search; rather, we argue that even with such a crude model one can get significant runtime improvements.