A correct rule costs time on integrands it never fires on, because a sub-answer lets a doomed search continue

[Rafael-SOWNet]

Four correct integration rules have now been written, verified, and not merged, each for the same reason. It is worth naming, because it is the thing standing between the integrator and a much larger rule set — and because the obvious fixes have been tried and measured, and do not work.

The shape

A rule answers a sub-integral that used to come back null. The rule is right; its answer differentiates back. But the search that asked for it used to stop there, and now carries on — into work that was always doomed, on an integrand the new rule never fires on.

So the cost lands somewhere other than where the rule is, and it is paid on inputs the rule does not touch.

Four instances

	the rule	what it gained	what it cost
#1244	Euler's substitution for sqrt(quadratic)	2 answers	7 problems from fast decline to full budget
#1245	tan/cot/sec/csc reach the half-angle substitution	26 answers	corpus wall clock roughly doubled
#1255	a constant factor out of a denominator	(merged)	1/(b^2cos^2 + a^2sin^2): 107 s → >400 s to decline
secant-powers	Rubi 4.5.1.1's secant/cosecant power reduction	2 answers, 28/28 on probe	sec(x)^6*tan(x)^3: 637 ms → >400 s to decline

The last is the clearest, because it is instrumented: on sec(x)^6*tan(x)^3 the new rule fires exactly twice, at n = 6 and n = 4, and terminates both times. The rule does almost no work. What changed is that two sub-integrals stopped failing.

What has been tried, and measured not to work

• A cap on the rule's own recursion. Does nothing where the recursion is already finite — the secant power never grows.
• A size bound on the rewritten integrand. Tried on Euler (400 nodes) and on the half-angle rewrite. Neither moved the number: sec(x)^6 is 25 nodes and 8.4 s, 1/(1 + cos(x)) is 10 nodes and 1 ms. Size does not predict cost.
• A structural guard on what the rule accepts. Tried twice on the constant-factor rule — rational-only, then symbolic-constant-only. Both measured no better than none, because the expensive firings are inside the rule's intended domain, not outside it.

What would

Two candidates, neither of which belongs inside any one rule:

A work budget. WorkBudget from #896 is the instrument that already exists. A rule handing a speculative sub-problem to the whole chain should be able to say how much of the remaining budget it will spend on it, and stop.

Or scope: answer what was asked, do not volunteer. A reduction like the secant one is the right answer when the caller asked for ∫sec^n and a distraction when it is offered into the middle of another rule's search. Firing only at the top of the descent would keep every gain in the table above and cost none of the time. That needs the descent depth, which is private to Integration, and it is a deliberate decision about what a rule is for rather than a guard.

The second is cheaper and probably more honest about the problem. The first is more general.

Why it matters more than four rules

Every one of these was a correct, tested, measured rule that had to be thrown away. Any serious attempt to widen coverage — porting more of Rubi's rules, which is MIT-licensed and organised to match the test suite already vendored here — will hit this on roughly every second rule. The rules are not the hard part; this is.

Branches, so the next attempt starts from code rather than a description: euler-substitution, secant-powers, trigrules-both.

🤖 Generated with Claude Code

https://claude.ai/code/session_012sonx8iAspMiwRwokT1Ura

[Rafael-SOWNet]

The second proposal is implemented and measured, in #1266, and it holds on the case that motivated the issue.

Integration.AnsweringTheQuestionAsked is descentDepth == 1 — the descent depth was already tracked, so the whole mechanism is one internal property and one call site. The secant power reduction consults it and declines anything it was not asked about directly.

On the instrumented case, sec(x)^6*tan(x)^3:

master	declines in 319 ms
ungated rule	does not return in 400 s
gated rule	declines in 273 ms

Not merely restored — slightly faster than master, because the rule reads the integrand and declines before the shapes behind it are tried.

The thirty-shape probe, every answer verified by differentiating back:

master      15/30 answered, 0 wrong
gated rule  28/30 answered, 0 wrong

and the corpus, 463-problem sample, both arms in the foreground:

master      230/463, 0 wrong, 3 timeouts
gated rule  231/463, 0 wrong, 3 timeouts

What the gate costs. One answer the ungated rule had: cot(x)^3*csc(x)^4, where the reduction was a sub-step rather than the question. That is the trade the scope makes, and it is the right side of it — the ungated version bought that one answer with a case that went from 637 ms to not returning.

What it does not answer. The other three rows in the table above are not fixed by this. Euler's substitution (#1244) and the half-angle reach (#1245) both produce a rewritten integrand and hand it back to the chain; they are not closed reductions, so "fire only at the top" does not describe them — the expensive firing genuinely is at the top. The constant-factor rule (#1255) is already merged and already fires at the top. So this closes one of the two proposals for one of the four instances, and the issue should stay open for the rest.

The distinction that came out of writing it, and which is worth recording: a rule that can run its own recursion to completion can be scoped; a rule that hands a rewritten problem back to the chain cannot. The reduction was rewritten as a loop with its base cases inline for exactly this reason — asking the integrator for ∫sec^(n-2) would put the rule's own recursion behind its own gate and stop it after one step. A budget, the first proposal, is still the only instrument that reaches the rewriting rules.

🤖 Generated with Claude Code

https://claude.ai/code/session_012sonx8iAspMiwRwokT1Ura

[Rafael-SOWNet]

Both remaining parked rules have now been put back on top of the merged scope and measured, and neither is rescued by it. Recording the numbers so the next attempt starts from them rather than from the idea.

Each arm is the same build with the rule switched by an environment variable, so nothing but the rule differs. Corpus is the 463-problem sample at a five-second budget; the uncapped times are a separate probe with no budget at all.

Euler's substitution (#1244)

	solved	wrong	timeouts
off	231/463	0	3
on	233/463	0	10
scoped to the top	233/463	0	8

Uncapped, scoped: 1/((4 + x^2)*sqrt(1 + 4x^2)) takes 51 s to decline and x*ln(x)/sqrt(-1 + x^2) does not return in 500 s. With the rule off, the same two are 200 ms and 25 ms.

The half-angle reach — tan/cot/sec/csc written as sine and cosine before the substitution

	solved	wrong	timeouts	corpus wall clock
off	231/463	0	3	152 s
on	234/463	0	6	237 s
scoped to the top	231/463	0	5	207 s

The scoped arm is strictly worse than off — the same answers, more timeouts, more time. That is the clearest single result here: the rewrite costs something at the top of every trigonometric integrand, and every answer it buys is bought below the top, so scoping keeps the whole cost and gives up the whole gain.

Uncapped, ungated:

	off	on
cot(2x)^3*csc(2x)^3	3.6 s to decline	324 s
tan(x)/sqrt(1 + sec(x)^3)	9 ms to decline	225 s

(Its gain is also smaller than when it was first measured: +3 here, not the +26 in the original note. Several rules merged since then answer those integrands directly, which is the better outcome and worth saying, because the rule is now buying much less than the note claims.)

What the three results together say

The line is not which rule or how big the rewrite is. It is whether the rule can finish on its own:

• The secant reduction runs its recurrence to completion in a loop and returns a finished answer. Scope is exactly right for it, and A power of the secant or cosecant is brought down by the recurrence, and a rule answers the question it was asked #1266 shows it costing nothing — sec(x)^6*tan(x)^3 declines slightly faster than before the rule existed.
• Euler and the half-angle reach both produce a rewritten integrand and hand it back to the chain. The chain then does unbounded work at depths the gate cannot see, so the gate can only decide whether that work starts, never how much of it runs.

So scope answers one of the four instances in the table above and cannot answer the other three, and a work budget — this issue's first proposal, with #896's WorkBudget as the instrument — is not an alternative to it but the other half. A rule handing a speculative sub-problem to the whole chain needs to be able to say how much of the remaining budget it will spend before it stops, and the numbers above are what that would have to bound: 51 s, 225 s, 324 s, all on integrands that decline in milliseconds without the rule.

Branches unchanged: euler-substitution, trigrules-both.

🤖 Generated with Claude Code

https://claude.ai/code/session_012sonx8iAspMiwRwokT1Ura

[Rafael-SOWNet]

The first proposal is now measured too, and it is not the answer either. Both halves of this issue are settled, and the remaining lever is a third thing neither of them names.

I built the work budget into the integrator — SpendAtMost(n) opening a scope a rule wraps its speculative hand-off in, one step charged per entry into the solver chain, exhaustion reported as descentTruncated so nothing is cached as unanswerable. WorkBudget from #896 already existed and the equation solver and the transformation layer already use it; the integrator did not.

It works, and it is measurable. On the half-angle rewrite, cot(2x)^3*csc(2x)^3:

budget
unlimited	70.6 s
6	3.8 s
3	3.6 s
1	3.5 s
(master, no rewrite)	0.39 s

and there is a window — a budget of 3 — where both answers the rewrite buys still come out and tan(x)/sqrt(1 + sec(x)^3) is declined in 49 ms rather than 52 s. So the instrument does what the proposal said it would.

It still does not make either rule shippable, for two different reasons.

The half-angle rewrite has been overtaken

Measured on the current master rather than on the one it was written against:

	solved	timeouts	wall clock
master	242/463	3	~150 s
with the rewrite, unlimited	237/463	6	234 s
with the rewrite, budget 3	234/463	2	146 s

It now loses answers — five with no budget at all, eight with one. #1268 and #1272 answer directly what it used to reach by rewriting, and its rewrite displaces them. Its worth has gone 26 → 3 → 2 → negative across the rules that have landed since it was written. It should be abandoned rather than parked, and trigrules-both is only of historical interest now.

Euler's cost is in its own body, where a budget on the hand-off cannot reach

This is the part that answers the proposal rather than the rule. With the budget set to 1 — the hand-off refused outright, so the chain does no work at all below the rule:

1/((4 + x^2)*sqrt(1 + 4x^2))     master 200 ms      Euler, budget 1     980 ms
x*ln(x)/sqrt(-1 + x^2)           master  25 ms      Euler, budget 1    > 399 s

Nothing below the rule ran. The time is the rule's own: the node scan, the quadratic read, the rewrite and the Simplify it does before it can tell whether it has anything — repeated on every integrand in the descent that carries a square root of a quadratic. A budget bounds what a rule asks for. It cannot bound what the rule does before asking.

x*ln(x)/sqrt(-1 + x^2) is the clearest case: it holds a logarithm, Euler can never answer it, and Euler should be able to say so in microseconds.

So the lever is a third one: make the rule cheap to decline

Not scope, not a budget on the sub-problem. SolveByEulerSubstitution decides whether it applies by doing most of the work — it rewrites and simplifies and only then finds out. A structural pre-check that costs nothing (is there a square root of a genuine quadratic, is the leading sign decidable, is there anything transcendental in the integrand that the substitution cannot carry) would refuse the great majority of what it is asked about before any of that runs.

That is a change to the rule rather than to the integrator, and it is the one I would try next. The budget mechanism is real and worked as designed; it has no rule left that needs it, so I have not opened a PR for it — a mechanism with no user is dead code. It is written down here so the next attempt starts from the measurement rather than from the idea.

Summary of the four instances this issue opened with:

	verdict
the secant reduction	fixed, by scope (#1266) — and #1268 has since answered its integrands directly
#1255's constant factor	merged; fires at the top already
the half-angle reach	abandon — now loses answers outright
Euler's substitution	still open; needs a cheap decline, not a budget

🤖 Generated with Claude Code

https://claude.ai/code/session_012sonx8iAspMiwRwokT1Ura