Great suggestion! That said, in light of your first paragraph, I'd like to point out a couple of issues. I came up with most of these by asking the questions "What exactly are you trying to encourage? What exactly are you incentivising? What differences are there between the two, and what would make those difference significant?"

You are trying to encourage prisons to rehabilitate their inmates. If, for a given prisoner, we use p to represent their propensity towards recidivism and a to represent their actual recidivism, rehabilitation is represented by p-a. Of course, we can't actually measure these values, so we use proxies; anticipated recidivism according to your algorithm and re-conviction rate (we'll call these p' and a', respectively).

With this incentive scheme, our prisons have three incentives: increasing p'-p, increasing p-a, and increasing a-a'. The first and last can lead to some problematic incentives.

To increase p'-p, prisons need to incarcerate prisoners which are less prone to recidivism than predicted. Given that past criminality is an excellent predictor of future criminality, this leads to a perverse incentive towards incarcerating those who were unfairly convicted (wrongly convicted innocents or over-convinced lesser offenders). If said prisons can influence the judges supplying their inmates, this may lead to judges being bribed to aggressively convict edge-cases or even outright innocents, and to convict lesser offenses of crimes more correlated with recidivism. (Counterpoint: We already have this problem, so this perverse incentive might not be making things much worse than they already are.)

To increase a-a', prisons need to reduce the probability of re-conviction relative to recidivism. At the comically amoral end, this can lead to prisons teaching inmates "how not to get caught." Even if that doesn't happen, I can see prisons handing out their lawyer's business cards to released inmates. "We are invested in making you a contributing member of society. If you are ever in trouble, let us know - we might be able to help you get back on track." (Counterpoint: Some of these tactics are likely to be too expensive to be worthwhile, even ignoring morality issues.)

Also, since you are incentivising improvement but not disincentivizing regression, prisons who are below-average are encouraged to try high-volatility reforms even if they would yield negative expected improvement. For example, if a reform has a 20% chance of making things much better but a 80% chance of making things equally worse, it is still a good business decision (since the latter consequence does not carry any costs).

Obvious, but worth mentioning: the recidivism index should not count the prisoners who didn't commit any more crimes because they died after they were released; otherwise it would appear lower than its actual value (and would create a hideous incentive).

I can see this system creating pressure to relax parole standards; if a minor deviance from the rules is not counted as recidivism, both the prison and the prisoner benefit.

The elephant in the room is that the US has radically higher incarnation rates than every other country. If you want to reform the systems it's worth paying attention to how the US system differs and what it does to get higher incarnation rates.

Jails compete for money: the more prisoners they house, the more they are paid and the longer they can continue to exist.

That sounds plausible at first glance but it might be more complicated. Have you looked in more detail about how prisons are currently payed?

Prisons love getting more money for doing the same amount of work so campaign contributions would stay stable or go up for politicians who support reduced recidivism bonuses.

Prisons itself don't want anything. There managers have interests. There are also workers. The union of those workers has political interests.

It's not that easy to get data about this but as far as I understand prison workers unions are a significant political player in the US.

To cut back on prison rape, some people have proposed segregating prisons by weight class. Using lean body mass would seem like a better idea. (To prevent short fat guys from being abused.) It would be easy to implement as well.

Letting prisoners choose which prison they will be housed in, and then paying prisons based on head count seems like an interesting idea to me. (The prisons could be privatized, or a bonus could be paid to wardens/staff/guards for each increase in enrollment. If a prison has a reputation for being dangerous or violent, just opt into a different prison (obviously within limits, like security level.) If one prison's population gets too low, a more successful prison could then take on management of it. Someone might be concerned that this would lead to prisons becoming too nice to work effectively as punishment. That could be corrected via regulations or just lowering the per-prisoner payment.

At minimum, each prisoner should be able to choose a private cell.

The core idea of incentivizing prisons to reduce recidivism seems very reasonable. If it's not currently being done, it definitely seems worth trying. At least for the experimental data of whether or not it's a good idea (although politicians wouldn't be able to admit to that reasoning).

Do you know if this is currently being done in any form? Are there other industries/contexts where similar things are being done? Successes? Failures?

This is really complex issue. What "should" be done depends on a lot of factors. You don't seem to have addressed/emphasized this. I think you should have.

However, I think people often use that sort of argument as a cop out, and I certainly won't do that. Relevant questions include "Do we expect that your proposal is better than what's currently being done (we don't need to be 100% sure for it to be worth trying)?". And "Do we expect that your proposal is better than other sensible proposals?" And "How 'high of a ceiling' does this idea have? How much upside? What's the best case scenario?".

I also want to point out that there are two separate questions at play here:

1) What policy would be best? If you had the power to snap your fingers and implement a policy, what would it be?

2) How practical is the proposal? Will it ever get adopted? What would have to happen in order for it to be adopted?

The first thing you suggest, creating a quality model of recidivism, would be eminently worthwhile. So much so, it has probably been done already a few times. Google "model of recidivism" and see how much stuff is out there. Read it.

There's an incentive you didn't mention, towards smallest prison populations, which is lowering costs and taxes.

You seem to take it for granted that the prison system will be largely private, but in many countries they are directly run by the state, which removes the profit and campaign donation incentives at a stroke.

What are the incentives for the powers-that-be to adopt your scheme?

Where will the "bonus" money come from? If from reduced expenses on dealing with crime, this is a direct threat to the jobs of cops, judges, prison guards, etc. etc. Crime is highly useful and profitable to many people. They will not want to reduce crime (or "crime") rates.

Missing actor/incentive structure:

Our current justice system is largely based on the idea of retribution, not rehabilitation. This is a trade-off where the State delivers vengeance for victims/families of victims to prevent vigilante justice. It may not make much sense in terms of impact today, but as a cultural norm it still exists and this idea does nothing to address that.

Other thoughts:

Does not really address "recidivism" of victimless crimes, including most drug crimes, except in the most general sense. Convincing people that smoking weed is morally wrong is much harder than convincing them that murder is morally wrong.

I predict that some amount of book-cooking will happen, but that the gains possible with book cooking are small compared to gains from actual improvements in their prison program.

Evidence? Given the history of attempts at rehabilitation programs, this is a rather dubious statement.

Police and judges retain the same incentives as before, for bonuses, prestige, and promotions. This is good for the system, because if their incentives were not running counter to the prisons and jails, then there would be a lot of pressure to cook the books by looking the other way on criminals til after the 60 day/1 year/5 year mark.

Police are also incentivised to not appear "racist", look what happened to Darren Wilson after he shot a black thug who was going for his gun. Thus it is in their interest to avoid patrolling high-crime ghettoes, e.g., what happened in Baltimore after the death of Freddie Gray.

Politicians compete for electability. Convicts can’t vote, prisons make campaign contributions and jobs, and appearing “tough on crime” appeals to a large portion of the voter base.

You seem to have forgotten why appearing "tough on crime" appeals to current voters.

Breif history lesson: During the 1960's and early 1970's politicans competed for electability by appearing compasionate to criminals, who were after all only "victims of society". The result was the massive crime wave of the 1970's. As a result the generation which grew up during that time learned that politicans promissing being compasion for criminals leads to an increased chance of them being mugged. Now that generation is the one in charge and they like politicans who are "tough on crime".