VCRs with automatic ad-skipping (during playback or recording) appeared in the 90s, and had many orders of magnitude less processing power than even a typical smartphone today. They had to deal with ads embedded directly in the video stream, and worked reasonably well. Perhaps a similar approach will work very well with digital video today.

https://en.wikipedia.org/wiki/Commercial_skipping