J. CLIFFORD WALLACE, Circuit Judge:
I.
On October 8, 2003, law enforcement personnel conducted surveillance of Preacely’s apartment, based on a tip that he was selling crack cocaine. Preacely and another man were seen leaving the apartment. Law enforcement officers attempted to question them and both fled. Preacely escaped, but the officers caught the other man and found he possessed crack cocaine. The other man told the officers that Preacely was selling crack cocaine. A search of Preacely’s apartment revealed more crack cocaine (about seven grams). A warrant was issued for Preacely’s arrest. Preacely was subsequently arrested, at which time police found 14.4 grams of crack cocaine and 1.32 grams of marijuana on his person. He was indicted for distributing and possessing with intent to distribute 50 grams or more of a substance containing cocaine base in violation of 21 U.S.C. § 841(b)(l)(A)(iii).
Pursuant to a cooperation agreement, Preacely pled guilty to distribution and possession with intent to distribute five grams or more of cocaine base in violation of 21 U.S.C. § 841(b)(l)(B)(iii), a crime which carries a mandatory minimum sentence of five years. However, federal law provides that, upon motion by the government, a court may impose a sentence below the statutory minimum “to reflect a defendant’s substantial assistance” in investigating or prosecuting other criminals. 18 U.S.C. § 3553(e); see also U.S.S.G. § 5K1.1 (permitting court to depart from Sentencing Guidelines upon motion of the government stating that the defendant has provided substantial assistance in the investigation or prosecution of another criminal). In the cooperation agreement here, the government agreed to file a motion pursuant to U.S.S.G. § 5K1.1 if Preacely provided substantial assistance to law enforcement, cooperated fully, and complied with the agreement’s terms. The government ultimately submitted a motion pursuant to the cooperation agreement, meaning that the sentencing court could consider imposing a sentence below the statutory minimum.
II.
Preacely’s Pre-Sentencing Report (PSR) indicates that his childhood was marred by poverty and substance abuse. He grew up in a “ramshackle” home with an alcoholic stepfather who verbally and physically abused his mother and threatened her with a gun “on a daily basis.” His mother was addicted to crack cocaine during some of Preacely’s teen years. Preacely became a heavy user of marijuana, starting at the age of 12 and abusing that drug continuously for most of his adult life.
Preacely was convicted of several crimes before his arrest in this case. At age 16, he was convicted of attempted criminal possession of a controlled substance (fifth degree). He was sentenced to a term of six months in custody and five years probation. Later that same year, however, he [76] was arrested for possessing crack cocaine and convicted of criminal possession of a controlled substance (seventh degree). For this additional conviction, and the violation of his earlier probation, he was sentenced to an additional eight months in custody. At age 18, Preacely was convicted of disorderly conduct and sentenced to time served. Later that year, he was again convicted of felony criminal sale of a controlled substance (fifth degree) and sentenced to a term of one year’s imprisonment. At age 21, he was convicted of misdemeanor assault, resulting in another one year sentence. At age 22, he was arrested for selling crack cocaine and yet again convicted for criminal sale of a controlled substance (fifth degree). For this conviction, he was sentenced to two to four years, and later paroled.
In the case before us, Preacely was arrested in June 2004. He was 27 at the time. He was incarcerated from the time of his arrest until June 6, 2006, at which time he was released on bail. He remained free on bail through his sentencing in May 2009.
Between arrest and sentencing, a period of approximately five years, Preacely underwent exceptional rehabilitation. First, Preacely worked to overcome his drug addiction. The PSR reflected that Preacely had abused marijuana for years, but had not used drugs since his arrest and wanted to be placed in a substance abuse program while in prison. After being released on bail, Preacely was required to report to the Pretrial Services Agency once a week and to submit to random drug testing. It is undisputed that, in the nearly three years between his June 2006 release and May 2009 sentencing, Preacely never failed a drug test and was “completely compliant” with all of the terms of his release.
Second, Preacely rendered significant assistance to the government. He was released “with the consent of the government ... so that he could purchase narcotics from specific targets and otherwise assist in investigations of drug dealers and others.” The government confirmed, by letter to the district court, that Preacely had “actively contributed to several successful criminal investigations.” The government’s section 5K1.1 motion also stated that Preacely began cooperating “very shortly after his arrest,” and provided “truthful and consistent information.” This information, according to the government, assisted in the arrest and/or conviction of persons suspected of drug dealing, firearms trafficking, credit card fraud, and multiple robberies, assisted in solving two murder cases, and assisted in the apprehension of a fugitive.
Third, Preacely transformed his professional life. Preacely had dropped out of school in ninth grade. Despite having received his GED in 2000, he had been employed only sporadically during his adult life. After his release on bail in June 2006, Preacely pursued employment and was one of the 18 (out of 90) candidates accepted into a competitive workforce development program sponsored by the county district attorney. The director of the program praised Preacely’s performance, observing that he completed all homework assignments, often took the lead in class discussions, and displayed genuine interest in the subject of the program. She stated that Preacely was “quick to grasp complex and difficult subject matter,” “willing to assist others,” and possessed the character traits that were valued in the classes and in the work environments for which he was preparing. Another district attorney, who was affiliated with the program, praised Preacely’s perfect attendance, “initiative and focus,” and “leadership ability and clear thinking.” She indicated that [77] Preacely had begun additional training with a local union on his own initiative, and it was anticipated that this would lead to full-time employment. Preacely completed the workforce development program and the union training program in November 2008. That same month, his employer wrote to the court, stating that Preacely was “one of [his] most trusted and dependable employee[s].”
Fourth, and finally, Preacely dramatically transformed his personal life. Preacely’s employer stated that he had “grown into a responsible man, husband and father.” Preacely not only attended voluntary counseling, but also counseled others through community programs. He worked with an initiative to close the drug market in his community. The Nassau County District Attorney also selected him to become a youth advisor for a gang prevention program. An addendum to the PSR reflected that Preacely married his longtime girlfriend and was providing support and care for their young daughter.
III.
At sentencing, the district judge accepted the PSR’s recommendations as to Preacely’s offense level and criminal history category for purposes of the Sentencing Guidelines. As to Preacely’s criminal history category, the PSR assigned points for prior criminal history as follows: no points for the 1993 convictions, two points for 1995 disorderly conduct conviction, two points for the 1995 controlled substance conviction, two points for the 1995 assault conviction, and three points for the 1999 drug conviction. The PSR added another three points because the crime in this case occurred less than two years after Preacely’s release from prison and while on parole for a prior offense, pursuant to U.S.S.G. § 4Al.l(d)-(e). This resulted in a total of twelve criminal history points, placing Preacely in criminal history Category V. However, because Preacely was over age 18 at the time of the current offense and had two prior felony convictions for controlled substance offenses, the PSR proposed that he qualified as a career offender under U.S.S.G. § 4Bl.l(b). As a career offender, Preacely would be placed in criminal history Category VI.
The PSR calculated Preacely’s base offense level as 26, under U.S.S.G. § 2Dl.l(c)(6). By application of the Career Offender Guideline, however, his base offense level was elevated to 34. U.S.S.G. § 4Bl.l(b)(B). The base offense level was reduced by three points for acceptance of responsibility under U.S.S.G. § 3E1.1, resulting in a final offense level of 31. With an offense level of 31 and a criminal history of Category VI, the Sentencing Guidelines suggested a range of 188-235 months’ imprisonment.
At Preacely’s sentencing hearing, his attorney asked the district judge to impose a term of two years’ imprisonment — the time he had already served' — -and six months of “community confinement” in a halfway house. Preacely’s counsel argued that the Career Offender Guideline overstated Preacely’s criminal history and the likelihood he would recidivate, resulting in a sentence far longer than necessary to serve the policies of the federal sentencing scheme. She also urged that “respect for the justice system would be enhanced” by a sentence that recognized Preacely’s rehabilitation and cooperation with authorities. Preacely spoke at his sentencing and thanked the prosecutor for “giving me a chance, the chance to improve myself.” He stated that he “tried very hard to do things in every way [other] than what I did in the past,” and that he was “thankful that I was able to do that and change my life around.”
[78] For its part, the government did not recommend a specific sentence, but submitted two documents prior to the sentencing hearing: a section 5K1.1 motion outlining the cooperation Preacely had provided, and a letter explaining that Preacely had been “completely compliant” with the terms of his 2006 release. At the sentencing hearing, the Assistant U.S. Attorney stated that Preacely’s cooperation was “extensive,” and that he had taken “his own initiative to better his life, which was certainly not ... required under the cooperation agreement” and “should be commended.” She said that the case agent who worked with Preacely “felt very strongly that Mr. Preacely really is someone that he has seen turn his life around.” She also stated her own opinion, that “I think he has shown that he does want to endeavor to be on the right path in the future.”
The district judge adopted the PSR’s recommendation to place Preacely in Criminal History Category VI and its calculation of an offense level of 31. Observing that the Guidelines recommended a sentence in the range of 188 to 235 months’ imprisonment, the district judge settled on a term of 94 months’ imprisonment, five years of post-release supervision, and a $100 special assessment. This term of imprisonment was exactly half of the low end of the range recommended by the Guidelines. The district judge gave Preacely credit for time served (approximately two years).
IV.
In sentencing Preacely, the district court was required to consider the factors set forth in section 3553(a) of the Sentencing Reform Act:
(1) the nature and circumstances of the offense and the history and characteristics of the defendant;
(2) the need for the sentence imposed—
(A) to reflect the seriousness of the offense, to promote respect for the law, and to provide just punishment for the offense;
(B) to afford adequate deterrence to criminal conduct;
(C) to protect the public from further crimes of the defendant; and
(D) to provide the defendant with needed educational or vocational training, medical care, or other correctional treatment in the most effective manner;
(3) the kinds of sentences available;
(4) the kinds of sentence and the sentencing range established for ... the applicable category of offense committed by .the applicable category of defendant as set forth in the guidelines....
(5) any pertinent policy statement ... issued by the Sentencing Commission ....
(6) the need to avoid unwarranted sentence disparities among defendants with similar records who have been found guilty of similar conduct; and
(7) the need to provide restitution to any victims of the offense.
18 U.S.C. § 3553(a).
We review a sentence “under a deferential abuse of discretion standard.” United States v. Hernandez, 604 F.3d 48, 52 (2d Cir.2010); see also Gall v. United States, 552 U.S. 38, 46, 128 S.Ct. 586, 169 L.Ed.2d 445 (2007) (review for “unreasonableness” amounts to review for abuse of discretion); United States v. Booker, 543 U.S. 220, 261, 125 S.Ct. 738, 160 L.Ed.2d 621 (2005) (review of a sentence is for “unreasonableness”). Appellate review of a sentence has two components: procedural review and substantive review. United States v. Cavera, 550 F.3d 180, 189 (2d Cir.2008) (en banc).
[79] [3-5] We must first determine whether the district court complied with the procedural requirements of the Sentencing Reform Act. Id. at 189-90; 18 U.S.C. § 3551 et seq., 28 U.S.C. § 991 et seq. The district court should ordinarily “begin all sentencing proceedings by correctly calculating the applicable Guidelines range,” Gall, 552 U.S. at 49, 128 S.Ct. 586, and then consider the factors listed in 18 U.S.C. § 3553(a). A district court commits procedural error, among other things, by failing to calculate the Guidelines range or by making a mistake in its Guidelines calculation; by treating the Guidelines as mandatory; by failing to consider the section 3553(a) factors; or by resting its sentence on a clearly erroneous finding of fact. Cavera, 550 F.3d at 190. “Moreover, a district court errs if it fails adequately to explain its chosen sentence, and must include an explanation for any deviation from the Guidelines range.” Id. (internal citations and quotation marks omitted); see also Rita v. United States, 551 U.S. 338, 339, 127 S.Ct. 2456, 168 L.Ed.2d 203 (2007).
As a matter of substantive review, we may not substitute our own judgment on what is sufficient to meet the section 3553(a) considerations in a particular case. Hernandez, 604 F.3d at 53.
We will instead set aside a district court’s substantive determination only in exceptional cases where the trial court’s decision cannot be located within the range of permissible decisions.... This degree of deference is only warranted, however, once we are satisfied that the district court complied with the Sentencing Reform Act’s procedural requirements, and this requires that we be confident that the sentence resulted from the district court’s considered judgment as to what was necessary to address the various, often conflicting, purposes of sentencing.
Id. (internal quotation marks omitted), quoting Cavera, 550 F.3d at 189-90. We do not presume that a Guidelines range sentence is reasonable. United States v. Fernandez, 443 F.3d 19, 27 (2d Cir.2006). Instead, we “take into account the totality of the circumstances, giving due deference to the sentencing judge’s exercise of discretion, and bearing in mind the institutional advantages of district courts.” Cavera, 550 F.3d at 190, citing Rita, 551 U.S. at 353, 127 S.Ct. 2456.
This case requires an understanding of the proper role of the Career Offender Guideline. Following Gall, 552 U.S. 38, 128 S.Ct. 586, and Kimbrough v. United States, 552 U.S. 85, 128 S.Ct. 558, 169 L.Ed.2d 481 (2007), we have held that it is “emphatically clear that the Guidelines are guidelines — that is, they are truly advisory.” Cavera, 550 F.3d at 189. While the Guidelines are “truly advisory,” district courts are not free to ignore them “or to treat them merely as a body of casual advice.” Id. (internal quotations omitted). The Sentencing “Guidelines provide the starting point and the initial benchmark for sentencing, ... and district courts must remain cognizant of them throughout the sentencing process.” Id. (internal citations and quotation marks omitted).
Of relevance here, a district court may impose a sentence outside the range called for by the Career Offender Guideline. United States v. Sanchez, 517 F.3d 651, 664-65 (2d Cir.2008). The district courts are not, however, free to ignore the Career Offender Guideline. The statute directing the Sentencing Commission to promulgate the Career Offender Guideline, 28 U.S.C. § 994(h), “reflects Congress’s policy judgment that violent felonies and drug trafficking felonies generally warrant more severe sentences [80] when committed by recidivists than when committed by first- or second-time offenders.” Sanchez, 517 F.3d at 668. As such, district courts should “take Congress’s views on repeat offenders into account in determining the appropriate sentence in light of’ the section 3553(a) factors. Id. at 665.
Preacely argues that the district judge gave inappropriate and overriding weight to the Career Offender Guideline. He submits that, although the district judge sentenced him below the Guidelines range, we cannot be sure that the judge understood that he could decline to treat Preacely as a career offender.
A.
The sentencing judge confirmed that he had read three letters from the defense and two letters from the government regarding Preacely’s sentencing. He listened to presentations by defense counsel, the defendant, and the government. He stated that he had taken into account all of the section 3553(a) factors and had “been over this record substantially.” The district judge observed “there is no question that [Preacely] has done a lot to improve his situation.” The judge stated, however:
I may not overlook the offense which we’re dealing with, or the offenses we’re dealing with here.... He is in a Category VI, which is a career offender category based on his prior record. And that puts him in the 188 to 235 months schedule under the guidelines. And I certainly commend him for his cooperation efforts, and the details that you have set forth in your plea for him. But I am dealing with a Category VI career offender, regardless of all of what you said. I don’t think I can — I’ll give him credit for time served, but I don’t think I can give him any less than 94 months in toto.... I’m here not only to protect the interests of your client, but I have to protect the interests of the public.... The minimum guideline is 188 months to 235 months. I’m cutting the guideline range in half to 94 months.... I have cut the guideline range from a Category VI. That is the highest.... It is the highest category for prior offenders. His record calls for that. And his record, unfortunately for you, calls for that sentence as I view it.
Our concern is the sentencing judge’s repeated emphasis on Preacely’s status as a Category VI career offender. We may generally assume “that the sentencing judge understood all the available sentencing options, including whatever departure authority existed in the circumstances of the case.” Id. at 665 (internal quotation marks omitted). However, we remain wary of making this assumption “where the judge’s sentencing remarks create ambiguity as to whether the judge correctly understood an available sentencing option, and we are more inclined, in the face of such ambiguity, to remand for clarification.” Id. (internal quotation marks, citations and alterations omitted). The question before us is whether this case reveals such an ambiguity.
B.
Here, it is unclear whether the sentencing judge understood that he could make a so-called “horizontal departure” from the Career Offender Guideline and adopt a lower criminal history category. See, e.g., United States v. Mishoe, 241 F.3d 214, 218-19 (2d Cir.2001) (“horizontal” departure from the Guideline criminal history category may be “based on an individualized consideration” of whether that Guideline “ ‘significantly over-represents the seriousness of [defendant’s] criminal history [and/]or the likelihood that [he] will [81] commit further crimes’ ”, quoting U.S.S.G. § 4A1.3(b)(l)). For example, the district judge could have placed Preacely in criminal history Category V, as indicated by the PSR’s calculation of his criminal history points. As calculated in the PSR, departure from the Career Offender Guideline would result in an offense level of 23. ■Using criminal history Category V and an offense level of 23 would yield an advisory Guidelines sentencing range of 84 to 105 months’ imprisonment.
The government correctly observes that the district judge understood that he could depart downward from the Sentencing Guidelines. The district court deviated from the advisory range by more than seven years, cutting the low-term of 188 months in half. Moreover, in discussing the government’s' motion pursuant to U.S.S.G. § 5K1.1, the district court stated that he had the authority to sentence Preacely to no imprisonment at all. Viewed in context, however, these comments show only that the judge understood his authority to depart from the statutory minimum pursuant to the government’s 5K1.1 motion. The district court ultimately concluded, it appears, that Preacely’s cooperation did not warrant no term of imprisonment but that Preacely’s cooperation warranted a sentencing reduction calculated by reference to the low end of the applicable Guidelines range. This is reinforced by the written statement attached to the judgment of conviction, in which the district court said that the sentence was “below the guidelines range based on a 5K1.1 motion filed by the Government.”
It is not clear that the district judge comprehended his authority to depart from the Career Offender Guideline, and therefore Preacely’s criminal history category, in calculating the advisory sentencing range under the Guidelines. Indeed, Preacely’s attorney sought to remind the sentencing judge that he could depart from the Career Offender Guideline if criminal history Category VI over-represented the seriousness of Preacely’s criminal history and/or his likelihood of recidivism. The judge replied:
I may not ignore his prior record. I may not ignore the guidelines. I’m cutting the guidelines in half, the minimum guideline for this offense in half. You look at the pages, upon pages of record here, and the category which is the highest category you can get.... I have given a lot of thought to this sentence. I realize what you — I understand what you said. But you’re asking me to depart from a sixth degree offender.... He is a career offender in the federal system.... I didn’t put him there. He put himself in that category.
It is ambiguous whether the sentencing judge understood that he was not required to treat Preacely as a “sixth degree offender” and that the Career Offender Guideline was not mandatory.
In this case, evidence of rehabilitation was particularly relevant to determining whether the Career Offender Guideline was appropriate. There was compelling evidence that Preacely embarked on a three-year course of rehabilitation, showing both his desire and his potential to live a productive life. By the government’s own admission, he went above and beyond the conditions of his release. The district court was required, as a procedural matter, to consider the evidence of Preacely’s rehabilitation. See, e.g., Hernandez, 604 F.3d at 53-55 (holding that a sentencing judge procedurally erred during resentencing where he failed to consider evidence of the defendant’s rehabilitation in the intervening years since the first sentencing). The sentencing judge acknowledged Preacely’s efforts “to improve his [82] situation,” yet emphasized Preacely’s categorization as a career offender: “I am dealing with a Category VI career offender, regardless of all of what you said.” The district judge’s statement, in light of the evidence of Preacely’s rehabilitation, reinforces our doubt that the district judge fully understood his authority to depart from Category VI if it “significantly overrepresented] the seriousness of [Preacely’s] criminal history [and/]or the likelihood that [he] will commit further crimes.” Mishoe, 241 F.3d at 218-19; U.S.S.G. § 4A1.3(b)(l). The record is at least ambiguous as to whether the sentencing judge believed the Career Offender Guideline was mandatory.
C.
As stated in Sanchez, we would probably not remand “if the record indicated clearly that the district court would have imposed the same sentence had it had an accurate understanding of its authority.” 517 F.3d at 665. But that is not the case here. The district judge selected a sentence of 94 months by taking the advisory range of 188 to 235 months (calculated in reliance on the Career Offender Guideline), and cutting the low term of that range in half. If the district court had adopted criminal history Category V and an offense level of 23, a Guidelines range of 84 to 105 months would result. If the district court applied the same methodology to this sentencing range, and halved the low-term advisory sentence of 84 months, a sentence of only 42 months would result. We do not suggest that is the proper sentence here. We provide this example to illustrate that it is not clear that the district judge would have reached the same sentence had he understood that he could depart from the Career Offender Guideline.
We offer no opinion as to whether the record in this case supports or requires a departure from the Career Offender Guideline. Instead, we remand so that the district court can consider that option, “based on an individualized consideration of factors relevant to an assessment of whether [Category] VI ‘significantly over-represents the seriousness of [his] criminal history [and/]or the likelihood that [he] will commit further crimes.’ ” Mishoe, 241 F.3d at 218-19, quoting U.S.S.G. § 4A1.3(b)(l).2
V.
The federal sentencing statute directs a court to impose “a sentence suffi[83] dent, but not greater than necessary, to comply with” the purposes outlined in 18 U.S.C. § 3553(a)(2):
(A) to reflect the seriousness of the offense, to promote respect for the law, and to provide just punishment for the offense;
(B) to afford adequate deterrence to criminal conduct;
(C) to protect the public from further crimes of the defendant; and
(D) to provide the defendant with needed educational or vocational training, medical care, or other correctional treatment in the most effective manner.
Even where a district court has not procedurally erred, we may reverse a sentence if it is substantively unreasonable in light of these purposes. See United States v. Rigas, 583 F.3d 108, 121-23 (2d Cir.2009). To do so, we need not conclude “that ‘no reasonable person’ would have imposed” the sentence at issue. Id. at 123 n. 5. Rather, we can “provide a backstop for those few cases that, although procedurally correct, would nonetheless damage the administration of justice because the sentence imposed was shockingly high, shockingly low, or otherwise unsupportable as a matter of law.” Id. at 123.
In this case, Preacely argues that his 94-month sentence was unreasonably long in light of the section 3553(a) factors, and “flouts the parsimony command” that the sentence be no greater than necessary. Because we conclude that his sentence must be vacated and remanded for procedural reasons, we need not decide whether Preacely’s sentence was also substantively unreasonable.
SENTENCE VACATED and case REMANDED for resentencing.