TL;DR: Measure the stage breakdown before changing anything, because the fix is usually concentrated in one or two stages. The standard wins are dependency and layer caching, parallelising independent work, running only affected tests, and right-sizing runners. The trust problem is usually flakiness rather than duration, and that needs quarantine and a flake rate, not speed.
How to approach it
Split the two complaints in your first sentence: 45 minutes is a speed problem, "stopped trusting it" is a reliability problem, and they have different fixes. Then measure.
A strong answer
Start with data. Break the pipeline into stages and get the p50 and p95 of each over the last few hundred runs. Almost always two stages own most of the wall clock, and everything else is noise. Optimising without this is how people spend a week saving forty seconds.
The wins, roughly in order of return per unit of effort.
Caching. Dependency caches (npm, Maven, Go modules, pip) keyed on the lockfile plus relevant OS, architecture, runtime and package-manager versions. Native dependencies and toolchain changes can invalidate a cache even when the lockfile is unchanged. For container builds, order the Dockerfile so that dependency installation sits above source copy, which is what makes layer caching work at all, and use BuildKit with a registry-backed cache so cold runners still benefit. A cold dependency install repeated on every job is the single most common waste.
Parallelism. Independent stages should not be sequential. Lint, unit tests and security scans have no ordering relationship, and most CI systems will fan them out if you express the dependency graph honestly. Test suites can shard across runners, ideally split by recorded duration rather than by file count so the shards finish together.
Do less. For a monorepo, run only what the change affects, determined by the build graph rather than by path guesswork. This is the biggest possible win and the most work to set up.
Runner sizing. Sometimes it is simply an under-provisioned runner doing a compile that is CPU-bound. Comparing the same job on a larger runner takes ten minutes and occasionally ends the investigation.
Now the trust half, because a fast pipeline nobody believes is still broken. Trust is usually destroyed by flaky tests: a failure that a re-run clears teaches everyone to re-run, and once re-running is the habit, a real failure gets re-run too. Track a flake rate per test, quarantine anything above a threshold so it reports without blocking, and give it an owner and a deadline. Keep high-risk coverage blocking through a reliable replacement check, or accept an explicit temporary risk exception; quarantine must not silently remove a security or payments gate. Also check that failures are legible: a 45-minute pipeline that fails at minute 43 with an unreadable log is worse than a slower one that fails fast with a clear message, so cheap checks belong first.
The target worth naming: use ten minutes as an initial feedback budget, then measure interruption and failure-detection time with the team. Slow specialist checks can still be valuable outside the shortest feedback path.
What interviewers probe next
"How do you keep it fast as the repo grows?" Budget it. Alert when p95 crosses a threshold, the same as any other production regression.
"Are self-hosted runners worth it?" Often, for warm caches and bigger machines. You take on capacity management and the security of the runner, which is a real trade rather than a free win.
"What do you not parallelise?" Anything sharing mutable state, notably integration tests against one database. Fix by isolating per shard, not by serialising.
Common mistakes
Optimising before measuring, which reliably targets the wrong stage.
Treating flakiness as a speed problem. It is a trust problem and it needs a different intervention.
Caching the wrong thing, such as a cache key that never invalidates, which produces stale builds that are far more expensive than slow ones.