Which strongly suggests that one reason 4-year degrees have lost value, is the piece of paper has lost value. Because of (most?) people only getting a degree for the paper.

Two improvements then: Degrees that earn the reputation of not being given for anything less than excellence in studies. Where the earned reputation is used both to discourage the non-serious, and enhance the value of the degree.

And of course, bring down the costs. Create a high octane alumni network to match. Foster an opinionated high work ethic, college-as-daycare / party-scene repellent culture. Anything and everything rethought from scratch.

For instance, why are degrees based on years? Why so standardized when neither students or jobs are? Why not a skill chart that can be custom traversed per student - with students expected to move on whenever they choose to, or have a good opportunity. A high percentage of students leaving for good jobs after just one year would be a win.

For just one slice of education, to start.

As with anything complex, start with something small and focused. Like a low population cutting edge practice/research AI school. Start from scratch with the thing that is new, challenging and in high demand.

Then expand into other fast changing, high demand areas. Keep figuring out better ways, keep taking on more, keep reducing costs, as long as all three of those efforts tradeoffs are compatible.