In Virginia in 2004, a defendant convicted of capital murder, who was at least 16 years old at the time of his crime, would be punished by either death or life imprisonment without the possibility of parole, unless the judge suspended his sentence. After a Virginia jury convicted Lee Boyd Malvo of two counts of capital murder based on homicides that he committed in 2002 when he was 17 years old, it declined to recommend the death penalty, and he was instead sentenced in 2004 to two terms of life imprisonment without parole, in accordance with Virginia law.

Thereafter, Malvo, again seeking to avoid the death penalty, pleaded guilty in another Virginia jurisdiction to one count of capital murder and one count of attempted capital murder-both of which he also committed when 17 years old-and received two additional terms of life imprisonment without parole.

After Malvo was sentenced in those cases, the Supreme Court issued a series of decisions relating to the sentencing of defendants who committed serious crimes when under the age of 18. It held that such defendants cannot be sentenced to death; that they cannot be sentenced to life imprisonment without parole unless they committed a homicide offense that reflected their permanent incorrigibility; and that these rules relating to juvenile sentencing are to be applied retroactively, meaning that sentences that were legal when imposed must be vacated if they were imposed in violation of the Court's new rules. See Roper v. Simmons , 543 U.S. 551 , 125 S.Ct. 1183 , 161 L.Ed.2d 1 (2005) ; Graham v. Florida , 560 U.S. 48 , 130 S.Ct. 2011 , 176 L.Ed.2d 825 (2010) ; Miller v. Alabama , 567 U.S. 460 , 132 S.Ct. 2455 , 183 L.Ed.2d 407 (2012) ; Montgomery v. Louisiana , --- U.S. ----, 136 S.Ct. 718 , 193 L.Ed.2d 599 (2016).

In these habeas cases filed under 28 U.S.C. § 2254 , we conclude that even though Malvo's life-without-parole sentences were fully legal when imposed, they must now be vacated because the retroactive constitutional rules for sentencing juveniles adopted subsequent to Malvo's sentencings were not satisfied during his sentencings. Accordingly, we affirm the district court's order vacating Malvo's four terms of life imprisonment without parole and remanding for resentencing to determine (1) whether Malvo qualifies as one of the rare juvenile offenders who may, consistent with the Eighth Amendment, be sentenced to life without the possibility of parole because his "crimes reflect permanent incorrigibility" or (2) whether those crimes instead "reflect the transient immaturity of youth," in which case he must receive a sentence short of life imprisonment without the possibility of parole. Montgomery , 136 S.Ct. at 734 .

I

A

Over the course of almost seven weeks in the fall of 2002, Lee Malvo and John Muhammad-better known as the "D.C. Snipers"-murdered 12 individuals, inflicted grievous injuries on 6 others, and terrorized the entire Washington, D.C. metropolitan area, instilling an all-consuming fear into the community.

The violence began on September 5, 2002, when Malvo-who was at the time 17 years old-ran up to a man's car in Clinton, Maryland, shot him six times with a .22 caliber handgun, and stole his laptop and $3,500 in cash. See Muhammad v. Kelly , 575 F.3d 359 , 362 (4th Cir. 2009). Ten days later, again in Clinton, Maryland, Malvo approached a man who was in the process of closing a liquor store and shot him in the abdomen at close range with the handgun. Id.

Muhammad and Malvo then went south for a short period. On September 21, Muhammad used a high-powered, long-range Bushmaster assault rifle to shoot two women who had just closed a liquor store in Montgomery, Alabama. Malvo was seen approaching the women as the shots were being fired and then rummaging through their purses. One of the women died from her wounds. Muhammad , 575 F.3d at 362 . Two days after that, a woman in Baton Rouge, Louisiana, was fatally shot in the head with a Bushmaster rifle after closing the store where she worked. Again, Malvo was seen fleeing the scene with her purse. Id. at 362-63 .

Shortly thereafter, Muhammad and Malvo returned to the Washington, D.C. area and, from October 2 until their capture on October 24, embarked on a series of indiscriminate sniper shootings with the Bushmaster rifle that left 10 more people dead, 3 seriously wounded, and the entire region "gripped by a paroxysm of fear," convinced that "every man, woman, and child was a likely target." Muhammad v. State , 177 Md.App. 188 , 934 A.2d 1059 , 1065-66 (2007). On October 2, shortly after 6 p.m., they shot and killed a man while he was in a grocery store parking lot in Montgomery County, Maryland. Id. at 1066. The next day, they murdered five people-four in the morning at different locations in Montgomery County, and a fifth that evening in Washington, D.C. Id. at 1067-69. The following day, they shot and seriously wounded a woman in Spotsylvania County, Virginia, while she was loading goods into her car. Id. at 1070. On October 7, they shot and gravely injured a 13-year-old boy in Prince George's County, Maryland, while he was on his way to school; two days later, they shot and killed a man at a gas station in Prince William County, Virginia; two days after that, they shot and killed another man at a gas station in Spotsylvania County, Virginia; and three days after that, they shot and killed a woman outside a Home Depot store in Fairfax County, Virginia. Id. at 1070-72. On October 19, they shot and seriously wounded a man while he was leaving a restaurant in Ashland, Virginia, and on October 22, they shot and killed a bus driver in Montgomery County, Maryland, the last of their sniper shootings. Id. at 1068, 1072.

Malvo and Muhammad were apprehended in the early hours of October 24 at a rest area in Frederick County, Maryland, while sleeping in a blue Chevrolet Caprice. A loaded .223 caliber Bushmaster rifle was found in the car, and a hole had been "cut into the lid of the trunk, just above the license plate, through which a rifle barrel could be projected." Muhammad , 934 A.2d at 1075 . Modifications had also been made to the car's rear seat to allow access to the trunk area from the car's passenger compartment. Id. After his arrest, Malvo told authorities in Virginia that "he and his 'father,' John Allen Muhammad, had acted as a sniper team ... in an effort to extort ten million dollars from the 'media and the government' " and that he had been the triggerman in 10 of the shootings. Later, however, when testifying as a witness at Muhammed's first-degree murder trial in Montgomery County, Maryland, Malvo stated that "he had been the actual shooter of [the 13-year old boy] in Prince George's County and of [the bus driver] in Montgomery County" and that "Muhammad had been the actual triggerman on all other occasions." Id. at 1078.

In January 2003, a grand jury in Fairfax County, Virginia, returned an indictment charging Malvo as an adult with (1) capital murder in the commission of an act of terrorism, in violation of Va. Code Ann. § 18.2-31 (13) ; (2) capital murder for killing more than one person within a three-year period, in violation of § 18.2-31(8) ; and (3) using a firearm in the commission of a felony, in violation of § 18.2-53.1. The prosecutor in that case sought the death penalty. Malvo pleaded not guilty to the charges, and, to ensure an impartial jury pool, the case was transferred to the Circuit Court for the City of Chesapeake, Virginia.

At the trial, which took place during November and December 2003, Malvo acknowledged his involvement in the killings but asserted an insanity defense based on the theory that he had been indoctrinated by Muhammad during his adolescence and was operating under Muhammad's control. To that end, defense counsel presented testimony from more than 40 witnesses who collectively described how Malvo was physically abused and largely abandoned as a child growing up in Jamaica and Antigua; how, when he was 15 years old, he befriended John Muhammad, an American veteran who had taken his three children to live in Antigua without their mother's knowledge; how Muhammad became a surrogate father for Malvo and brought him illegally to the United States in May 2001; how Malvo briefly reunited with his mother in the United States but then moved across the country in October 2001 to rejoin Muhammad, who had recently lost custody of his children; and how Muhammad then intensively trained Malvo in military tactics for nearly a year, telling Malvo that he had a plan to get his children back and force America to reckon with its social injustices. The jury rejected Malvo's insanity defense and convicted him of all charges, including the two capital murder charges.

At the sentencing phase of trial, the jury was instructed to choose between the death penalty and life imprisonment without parole. During this phase, Malvo's counsel presented additional evidence on Malvo's background and history, and he stressed Malvo's youth and immaturity in arguing that Malvo should be spared the death penalty. The jury returned its verdict on December 23, 2003, finding "unanimously and beyond a reasonable doubt after consideration of [Malvo's] history and background that there [was] a probability that he would commit criminal acts of violence that constitute a continuing serious threat to society" and also "that his conduct in committing the offense was outrageously or wantonly vile, horrible or inhuman in that it involved depravity of mind." Nonetheless, the jury, "having considered all of the evidence in aggravation and mitigation of the offense," "fix[ed] his punishment at imprisonment for life" for each of his two capital murder convictions.

After the jury was excused and a presentence report was prepared, the court conducted a final sentencing hearing on March 10, 2004, sentencing Malvo to two terms of life imprisonment, as required by Virginia law. See Va. Code Ann. § 19.2-264.4 (A) (2004) (providing, for capital murder convictions, that where "a sentence of death is not recommended, the defendant shall be sentenced to imprisonment for life"). Under Virginia law, a defendant sentenced to life imprisonment for a capital murder offense committed on or after January 1, 1995, is ineligible for any form of parole. See Va. Code Ann. §§ 53.1-165.1 , 53.1-40.01. The court also sentenced Malvo to three years' imprisonment for the firearm conviction.

Following his conviction and sentencing in the Chesapeake City Circuit Court, Malvo entered an " Alford plea" pursuant to a plea agreement, see North Carolina v. Alford , 400 U.S. 25 , 91 S.Ct. 160 , 27 L.Ed.2d 162 (1970) (authorizing a defendant to waive trial and to consent to punishment without admitting participation in the acts constituting the crime), in the Circuit Court for the County of Spotsylvania, Virginia, pleading guilty to one count of capital murder, one count of attempted capital murder, and two counts of using a firearm in the commission of a felony. The plea agreement indicated that Malvo's attorney had advised Malvo that he faced death or imprisonment for a term of life for the capital murder charge and a sentence of 20 years to life imprisonment for the attempted capital murder charge. In the agreement, Malvo waived his "right to an appeal" and admitted that "the Commonwealth ha[d] sufficient evidence to convict [him]." The Commonwealth in turn agreed to dismiss two pending charges and agreed that sentencing Malvo to two terms of life imprisonment without parole, as well as eight years' imprisonment for the firearm offenses, was the "appropriate disposition in this case."

The Spotsylvania County Circuit Court held a plea and sentencing hearing on October 26, 2004, at which it confirmed that Malvo understood "that by pleading guilty [he was] giving up constitutional rights"-specifically, his "right to a trial by jury" and his "right to confront and cross examine [his accusers]"-and that he was also "probably giving up [his] right to appeal any decisions made by this Court." After ensuring that Malvo understood the nature of the charges against him and had concluded, after consulting with his lawyers, that his Alford plea was "in [his] best interests," the court accepted Malvo's guilty pleas, finding that they "were freely, voluntarily, and intelligently made." It also "accepted and approved" the plea agreement itself. The court then sentenced Malvo to two terms of life imprisonment without parole for his capital murder and attempted capital murder convictions, plus eight years' imprisonment for the firearm convictions.

B

Nearly eight years after the conclusion of Malvo's Virginia prosecutions, the Supreme Court held that the Eighth Amendment prohibits juvenile homicide offenders from receiving "mandatory life-without-parole sentences" and that, before sentencing such an offender to life without parole, the sentencing court must first consider the "offender's youth and attendant characteristics." Miller , 567 U.S. at 476, 483 , 132 S.Ct. 2455 . In light of Miller , Malvo filed two applications for writs of habeas corpus in the U.S. District Court for the Eastern District of Virginia pursuant to 28 U.S.C. § 2254 , one challenging the life-without-parole sentences imposed by the Chesapeake City Circuit Court and the other addressing the same sentences from the Spotsylvania County Circuit Court.

The district court denied and dismissed with prejudice both applications, concluding that Miller was not "retroactively applicable to cases on collateral review," 28 U.S.C. § 2244 (d)(1)(C), and that Malvo's habeas applications therefore were time-barred under § 2244(d) 's 1-year period of limitation. After Malvo appealed, his case was placed in abeyance while this court and the Supreme Court addressed whether Miller was to be applied retroactively. On January 25, 2016, the Supreme Court held that " Miller announced a substantive rule that is retroactive in cases on collateral review." Montgomery , 136 S.Ct. at 732 . Accordingly, we remanded Malvo's case comprising his two habeas applications to the district court for further consideration in light of Montgomery .

By memorandum and order dated May 26, 2017, the district court granted both of Malvo's habeas applications, vacating his four sentences of life imprisonment without parole and remanding to the Chesapeake City Circuit Court and the Spotsylvania County Circuit Court for resentencing in accordance with Miller and Montgomery . See Malvo v. Mathena , 254 F.Supp.3d 820 (E.D. Va. 2017). In entering that order, the district court rejected the Warden's argument that because the trial courts retained discretion under Virginia law to suspend Malvo's life sentences in whole or in part, those sentences were not mandatory and therefore were not covered by the Miller rule. The court explained that the constitutional rule announced in Miller and restated in Montgomery provided relief not only from mandatory life-without-parole sentences but also potentially from discretionary life-without-parole sentences. The district court also rejected the Warden's argument that in sentencing Malvo, the Chesapeake City Circuit Court had actually considered whether Malvo was one of those rare juvenile offenders whose crimes reflected irreparable corruption, as required by Miller . And finally, the court rejected the Warden's argument that Malvo, in entering the Alford plea in Spotsylvania County Circuit Court, waived the Eighth Amendment rights announced in Miller . In conclusion, the district court recognized that it was "completely possible that any resentencing conducted in accordance with Miller and Montgomery [might] result[ ] in the same sentences," id. at 834 , but it concluded that Malvo was entitled to the procedure described in those cases before being sentenced to life without parole.

From the district court's May 26, 2017 order, the Warden filed this appeal.

II

In its Eighth Amendment jurisprudence, the Supreme Court recognizes that persons under the age of 18 as a class are constitutionally different from adults for purposes of sentencing. Juveniles inherently lack maturity; they do not have a fully formed character and a fully developed sense of responsibility; and they are both more susceptible to external influences and less able to control their environment than are adults. Juveniles are also more capable of change than adults and therefore more capable of being reformed. Because of these attributes of youth, juveniles are not as morally culpable as adults when engaging in similar conduct. In light of these characteristics, the Court recognizes that juveniles as a class are less deserving of the most severe punishments. But it also recognizes that a rare few juveniles may nonetheless be found to be permanently incorrigible.

Giving effect to these observations, the Supreme Court has developed a juvenile-sentencing jurisprudence beginning with its 2005 decision in Roper , where it held that the death penalty cannot be imposed on juvenile offenders. See 543 U.S. at 571 , 125 S.Ct. 1183 . That decision was followed by Graham , where the Court held that "[t]he Constitution prohibits the imposition of a life without parole sentence on a juvenile offender who did not commit homicide." 560 U.S. at 82 , 130 S.Ct. 2011 . The Graham Court explained that "[a] State is not required to guarantee eventual freedom to a juvenile offender convicted of a nonhomicide crime," but it must give such defendants "some meaningful opportunity to obtain release based on demonstrated maturity and rehabilitation." Id. at 75 , 130 S.Ct. 2011 ; see also id. ("The Eighth Amendment does not foreclose the possibility that persons convicted of nonhomicide crimes committed before adulthood will remain behind bars for life," but "[i]t does prohibit States from making the judgment at the outset that those offenders never will be fit to reenter society").

Two years later in Miller , the Court held that a juvenile offender convicted of homicide cannot receive a mandatory sentence of life without parole. It explained, "Such mandatory penalties, by their nature, preclude a sentencer from taking account of an offender's age and the wealth of characteristics and circumstances attendant to it." Miller , 567 U.S. at 476 , 132 S.Ct. 2455 . The Court stated, moreover, that not only must "a judge or jury ... have the opportunity to consider mitigating circumstances before imposing the harshest possible penalty for juveniles," id. at 489 , 132 S.Ct. 2455 , but also the sentencer must actually "take into account how children are different, and how those differences counsel against irrevocably sentencing them to a lifetime in prison," id. at 480 , 132 S.Ct. 2455 . The Court did not, however, adopt "a categorical bar on life without parole for juveniles," id. at 479 , 132 S.Ct. 2455 , instead reserving the possibility that such a severe sentence could be appropriately imposed on "the rare juvenile offender whose crime reflects irreparable corruption," id. at 479-80 , 132 S.Ct. 2455 (quoting Roper , 543 U.S. at 573 , 125 S.Ct. 1183 ).

Finally, in 2016, the Court decided Montgomery , holding that Miller announced a new "substantive rule" of constitutional law that applies retroactively "to juvenile offenders whose convictions and sentences were final when Miller was decided." 136 S.Ct. at 725 , 732 ; see also Teague v. Lane , 489 U.S. 288 , 311, 109 S.Ct. 1060 , 103 L.Ed.2d 334 (1989) (plurality opinion) (recognizing that a new rule of constitutional law applies retroactively only if it qualifies as a substantive rule or a watershed rule of criminal procedure). Articulating the Miller rule, the Montgomery Court stated that " Miller requires that before sentencing a juvenile to life without parole, the sentencing judge [must] take into account 'how children are different, and how those differences counsel against irrevocably sentencing them to a lifetime in prison.' " 136 S.Ct. at 733 (quoting Miller , 567 U.S. at 480 , 132 S.Ct. 2455 ). It then stated:

Miller ... did more than require a sentencer to consider a juvenile offender's youth before imposing life without parole; it established that the penological justifications for life without parole collapse in light of the distinctive attributes of youth. Even if a court considers a child's age before sentencing him or her to a lifetime in prison, that sentence still violates the Eighth Amendment for a child whose crime reflects unfortunate yet transient immaturity. Because Miller determined that sentencing a child to life without parole is excessive for all but the rare juvenile offender whose crime reflects irreparable corruption, it rendered life without parole an unconstitutional penalty for a class of defendants because of their status-that is, juvenile offenders whose crimes reflect the transient immaturity of youth. As a result, Miller announced a substantive rule of constitutional law . Like other substantive rules, Miller is retroactive because it necessarily carr[ies] a significant risk that a defendant-here, the vast majority of juvenile offenders-faces a punishment that the law cannot impose upon him.

Id. at 734 (alteration in original) (emphasis added) (internal quotation marks and citations omitted); see also id. ("Before Miller , every juvenile convicted of a homicide offense could be sentenced to life without parole. After Miller , it will be the rare juvenile offender who can receive that same sentence"). The Court explained further that Miller contained both a substantive rule and a procedural component: " Miller 's substantive holding" was that "life without parole is an excessive sentence for children whose crimes reflect transient immaturity," and its procedural component implementing the substantive rule requires "[a] hearing where youth and its attendant circumstances are considered as sentencing factors" in order to "separate those juveniles who may be sentenced to life without parole from those who may not." Id. at 735 (internal quotation marks omitted).

III

In this appeal, the Warden contends that notwithstanding this new Eighth Amendment jurisprudence governing the sentencing of juveniles, the district court erred in awarding habeas corpus relief to Malvo, giving three reasons in support of his contention. First , he argues that "Malvo has no entitlement to relief under Miller " because " Miller 's new rule explicitly applies to mandatory life-without-parole sentences," whereas "the Virginia Supreme Court has conclusively held that Virginia does not impose mandatory sentences for any homicide offense" because judges retain the discretionary right to suspend sentences; second , that "Malvo received all that Miller would entitle him to during his trial in Chesapeake [City]" and therefore is not entitled to resentencing in that jurisdiction; and finally , that "Malvo's voluntary decision to enter into a plea agreement with stipulated sentences in Spotsylvania to eliminate the possibility of [the death penalty] waive[d] any claim he would have had under Miller " as to the two life-without-parole sentences he received in that jurisdiction. We consider these arguments in turn.

A

First, the Warden contends that because the Miller rule is limited to mandatory sentences of life imprisonment without parole, it does not implicate Malvo's sentences, which were, under Virginia law, subject to the sentencing court's discretion to suspend the sentence in whole or in part. He argues that because Malvo had the opportunity under Virginia law to request that his life sentences be suspended, he did not receive mandatory life-without-parole sentences and therefore is not entitled to any relief under Miller . Responding to the district court's conclusion that Montgomery clarified that the rule in Miller applies more broadly than only to mandatory life-without-parole sentences, the Warden contends that Miller itself did not sweep so broadly and that only the Miller rule applying to mandatory sentences was made retroactive in Montgomery . Indeed, he argues that the district court violated the rule established in Teague "by crafting a new rule of constitutional law based on Montgomery 's discussion of Miller and applying that new rule retroactively." In other words, as the Warden argues, "the principles of finality discussed in Teague prohibit federal courts from expanding new rules of constitutional law beyond their holdings," and "the correct approach is to recognize that ... Miller 's new rule is defined by Miller itself, not Montgomery ."

In response, Malvo contends that he did indeed receive mandatory life-without-parole sentences within the meaning of Miller because Virginia law provided then and still provides that when a jury declines to recommend the death penalty for a defendant convicted of capital murder, the defendant must be sentenced to life imprisonment without parole. See Va. Code Ann. § 19.2-264.4 (A) ; see also id. §§ 53.1-165.1, 53.1-40.01. He asserts further that Virginia trial courts were not aware at the time of his sentencings in 2004 that they were empowered to suspend capital murder sentences. Finally, he argues that, in any event, the Miller rule is not limited to mandatory life-without-parole sentences but also applies, as noted in Montgomery , to all life-without-parole sentences where the sentencing court did not resolve whether the juvenile offender was "irretrievably corrupt" or whether his crimes reflected his "transient immaturity."

As the Warden asserts, the Virginia Supreme Court has now twice recognized that Virginia trial courts have long had the authority to suspend life sentences in whole or in part even following a capital murder conviction-an interpretation of Virginia law that is, of course, binding here. See Jones v. Commonwealth ( Jones II ), 293 Va. 29 , 795 S.E.2d 705 , 712 (2017)

(reaffirming the holding in Jones v. Commonwealth ( Jones I ), 288 Va. 475 , 763 S.E.2d 823 , 824-25 (2014) (holding that when a Virginia trial court sentenced a juvenile homicide offender for capital murder in 2001, it had the authority to suspend part or all of his life sentence) ). But also, as Malvo asserts, it is far from clear that anyone involved in Malvo's prosecutions actually understood at the time that Virginia trial courts retained their ordinary suspension authority following a conviction for capital murder. We need not, however, resolve whether any of Malvo's sentences were mandatory because Montgomery has now made clear that Miller 's rule has applicability beyond those situations in which a juvenile homicide offender received a mandatory life-without-parole sentence.

To be sure, all the penalty schemes before the Supreme Court in both Miller and Montgomery were mandatory. Yet the Montgomery Court confirmed that, even though imposing a life-without-parole sentence on a juvenile homicide offender pursuant to a mandatory penalty scheme necessarily violates the Eighth Amendment as construed in Miller , a sentencing judge also violates Miller 's rule any time it imposes a discretionary life-without-parole sentence on a juvenile homicide offender without first concluding that the offender's "crimes reflect permanent incorrigibility," as distinct from "the transient immaturity of youth." Montgomery , 136 S.Ct. at 734 . And we are not free to conclude, as the Warden argues, that Montgomery 's articulation of the Miller rule was mere dictum. To the contrary, Montgomery stated clearly that, under Miller , the Eighth Amendment bars life-without-parole sentences for all but those rare juvenile offenders whose crimes reflect permanent incorrigibility. Indeed, this scope was the basis for its holding that Miller announced a substantive rule that applies retroactively to cases on collateral review. See id. And because Montgomery explicitly articulated the rule in Miller that it was retroactively applying, the district court could not have violated Teague in applying that rule. The Warden may well critique the Supreme Court's ruling in Montgomery -as did Justice Scalia in dissent, see Montgomery , 136 S.Ct. at 743 (Scalia, J., dissenting) ("It is plain as day that the majority is not applying Miller , but rewriting it")-but we are nonetheless bound by Montgomery 's statement of the Miller rule.

At bottom, we reject the Warden's argument that Malvo "has no entitlement to relief under Miller " on the ground that Miller applies only to mandatory life-without-parole sentences and instead conclude that Miller 's holding potentially applies to any case where a juvenile homicide offender was sentenced to life imprisonment without the possibility of parole.

B

The Warden next contends that even if Miller applies to discretionary life-without-parole sentences, "Malvo received all that Miller would entitle him to during his trial in Chesapeake," and thus the two life-without-parole sentences that he received in that proceeding must be permitted to stand. In advancing this argument, the Warden notes that "[o]ver the course of six weeks, the jury heard an enormous amount of mitigation evidence that was nearly all focused on [Malvo's] youth, upbringing, and impressionability," and that it also "heard from multiple expert witnesses who testified specifically about how Malvo's age and upbringing affected his competency." He argues further that "the trial court and the jury actually considered [Malvo's mitigation] evidence in imposing the sentences in this case" and that "the jury's finding of future dangerousness and vileness shows that Malvo is the 'rare juvenile offender whose crime reflect[ed] irreparable corruption.' " Moreover, according to the Warden, the fact "[t]hat Malvo chose not to use the evidence he introduced to argue for a sentence less than life without parole does not change the fact that he had the opportunity to present the relevant evidence and argue for leniency, which is all that the Eighth Amendment requires."

The problem with the Warden's argument, however, is that, as a matter of Virginia law, the jury was not allowed to give a sentence less than life without parole. It was charged with deciding between the death penalty and life without parole, and it selected the more lenient of the two. Thus, even though the jury did find future dangerousness and vileness, as the Warden notes, it also considered Malvo's mitigation evidence and found that he deserved the lighter of the two sentences that it could give-life without parole.

Moreover, the Chesapeake City jury was never charged with finding whether Malvo's crimes reflected irreparable corruption or permanent incorrigibility, a determination that is now a prerequisite to imposing a life-without-parole sentence on a juvenile homicide offender. Nor were Malvo's "youth and attendant circumstances" considered by either the jury or the judge to determine whether to sentence him to life without parole or some lesser sentence. Montgomery , 136 S.Ct. at 735 .

We thus conclude that Malvo's sentencing proceedings in the Chesapeake City Circuit Court did not satisfy the requirements of the Eighth Amendment as articulated in Miller and Montgomery .

C

Finally, the Warden contends that "Malvo's voluntary decision to enter into a plea agreement with stipulated [life-without-parole] sentences in Spotsylvania ... waive[d] any claim he would have had under Miller " as to those two sentences. The Warden notes that "Malvo received a substantial benefit" in "avoid[ing] a second trial at which he could have been sentenced to death" and contends that Malvo must therefore "be held to the terms of his bargain." He cites Brady v. United States , 397 U.S. 742 , 90 S.Ct. 1463 , 25 L.Ed.2d 747 (1970), and Dingle v. Stevenson , 840 F.3d 171 (4th Cir. 2016), to argue that both the "Supreme Court and this Court have made clear that guilty pleas are not open to revision when future changes in the law alter the calculus that caused the defendant to enter his plea."

At the outset, we conclude that the resolution of this issue is not governed by Brady or Dingle . In Brady , the defendant pleaded guilty to a crime that carried the possibility of the death penalty in order to avoid that penalty, receiving instead a 50-year sentence of imprisonment (later reduced to 30 years). When the Supreme Court later held that the death-penalty provision involved in Brady's case was unconstitutional, Brady sought to set aside his plea agreement as invalid. The Brady Court rejected Brady's argument, noting that "even if we assume that Brady would not have pleaded guilty except for the death penalty provision ..., this assumption merely identifies the penalty provision as a 'but for' cause of his plea," but it "does not necessarily prove that the plea was coerced and invalid as an involuntary act." 397 U.S. at 750 , 90 S.Ct. 1463 . Rather, "a plea of guilty is not invalid merely because entered to avoid the possibility of a death penalty," even one subsequently invalidated. Id. at 755 , 90 S.Ct. 1463 .

In Dingle , we applied Brady to similar circumstances, concluding that a plea agreement could not be set aside as involuntary and invalid because it was entered into by Dingle to avoid the death penalty when that penalty was later determined to be unconstitutional in the circumstances. We noted in Dingle that the Supreme Court had "not suggested that a substantive rule would stretch beyond the proscribed sentence to reopen guilty pleas with a different sentence." 840 F.3d at 174 .

Thus, in both Brady and Dingle , the defendants sought to use new sentencing case law to attack their convictions-their guilty pleas-without any claim that the sentences they actually received were unlawful. The question in both cases was thus whether to set aside the guilty-plea convictions when the penalties that induced the pleas were later found to be unconstitutional. In both cases that relief was denied, and the legality vel non of the avoided sentences was thus held not to cast doubt on the validity of the guilty plea. In this case, by distinction, Malvo seeks to challenge his sentences , not his guilty-plea convictions , on the ground that they were retroactively made unconstitutional under the rule announced in Miller . Thus, whereas the defendants in Brady and Dingle sought to use new sentencing law as a sword to attack the validity of their guilty pleas, here the Warden seeks to use Malvo's lawful guilty plea as a shield to insulate his allegedly unlawful life-without-parole sentences from judicial review. We conclude that Brady and Dingle do not provide him with that shield.

Nonetheless, that brings us to the more formidable question of whether Malvo waived his constitutional challenge to his sentences by signing the plea agreement.

In that agreement, Malvo agreed that Virginia's summary of the facts could be proven in the case were it to go to trial, accepting that summary "in lieu of presentation of any evidence by the Commonwealth." And, after expressly waiving his rights to a speedy and public trial by jury, to compel the production of evidence and attendance of witnesses, to have a lawyer, to not testify against himself, and to be confronted by his accusers, he entered an Alford guilty plea and waived his right to an appeal. With respect to punishment, he stated in his plea agreement, "I understand that the Commonwealth's Attorney has agreed that the following specific punishment is the appropriate disposition in this case": "life in prison without parole" for the offenses of capital murder and attempted capital murder and a term of years for the other offenses. Finally, he acknowledged that "the Court [could] accept or reject this plea agreement." It is noteworthy, however, that in the plea agreement, Malvo did not himself agree that life-without-parole sentences were appropriate punishments for his crimes. That is not to say, of course, that Malvo did not expect that he was avoiding the death penalty by receiving life sentences without parole. See Va. S. Ct. Rule 3A:8(c)(1)(C).

To begin, it is far from clear that a broad waiver of a substantive constitutional right, as the Warden maintains happened here, would even be enforceable. See Montgomery , 136 S.Ct. at 729, 734 (explaining that "[s]ubstantive rules ... set forth categorical constitutional guarantees that place certain criminal laws and punishments altogether beyond the State's power to impose" and that, "[l]ike other substantive rules, Miller is retroactive because it necessarily carr[ies] a significant risk that a defendant-here, the vast majority of juvenile offenders-faces a punishment that the law cannot impose upon him " (alteration in original) (emphasis added) (internal quotation marks omitted) ); see also United States v. Lemaster , 403 F.3d 216 , 220 & n.2 (4th Cir. 2005) (holding that, just as "a defendant may waive his right to appeal directly from his conviction and sentence," he may also "waive his right to attack his conviction and sentence collaterally, so long as the waiver is knowing and voluntary," but noting that there is a "narrow class of claims that we have allowed a defendant to raise on direct appeal despite a general waiver of appellate rights," including a claim that the "sentence imposed [was] in excess of the maximum penalty provided by statute," and indicating that "we see no reason to distinguish between waivers of direct-appeal rights and waivers of collateral-attack rights").

But, in any event, the plea agreement in this case does not provide any form of express waiver of Malvo's right to challenge the constitutionality of his sentence in a collateral proceeding in light of future Supreme Court holdings, nor was he advised during his plea colloquy that his Alford plea would have that effect. He did expressly waive constitutional rights relating to trial and his right to direct appeal, but nothing with respect to the right to pursue future habeas relief from his punishment. Consequently, the Warden's waiver argument must rest on some form of inherent or implied waiver of his right to challenge his sentences as unconstitutional.

In the circumstances, we decline to hold that Malvo implicitly waived his right to argue, based on intervening Supreme Court holdings, that his sentences were ones that the State could not constitutionally impose on him. Cf. Class v. United States , --- U.S. ----, 138 S.Ct. 798 , 804-05, 200 L.Ed.2d 37 (2018) (explaining that while "a guilty plea does implicitly waive some claims, including some constitutional claims," it "does not bar a claim on appeal 'where on the face of the record the court had no power to enter the conviction or impose the sentence' " (quoting United States v. Broce , 488 U.S. 563 , 569, 109 S.Ct. 757 , 102 L.Ed.2d 927 (1989) ) ). We thus conclude that, while Malvo's convictions remain valid, nothing in his plea agreement precludes him from obtaining habeas relief under the new rule in Miller . Accordingly, we reject the Warden's argument that Malvo waived his right to challenge his sentences.

IV

To be clear, the crimes committed by Malvo and John Muhammad were the most heinous, random acts of premeditated violence conceivable, destroying lives and families and terrorizing the entire Washington, D.C. metropolitan area for over six weeks, instilling mortal fear daily in the citizens of that community. The Commonwealth of Virginia understandably sought the harshest penalties then available under the law, and the Warden now understandably seeks to sustain the penalties that were then legally imposed with arguments that are not without substantial force.

But Malvo was 17 years old when he committed the murders, and he now has the retroactive benefit of new constitutional rules that treat juveniles differently for sentencing. Because we are bound to apply those constitutional rules, we affirm the district court's grant of habeas relief awarding Malvo new sentencings. We make this ruling not with any satisfaction but to sustain the law. As for Malvo, who knows but God how he will bear the future.

AFFIRMED