Petitioners James Ward, Jimmy E. Scroger, and Christopher Lamar Guido, former inmates at the Leavenworth Federal Prison Camp in Leavenworth, Kansas, brought these habeas actions against respondent J.W. Booker, the warden at Leavenworth, challenging a nationwide Bureau of Prisons (“BOP”) rule which initially denied them a sentencing reduction available to certain inmates who successfully completed a drug treatment program. The BOP’s rule initially denied the sentence reduction to petitioners because their sentences for drug offenses were enhanced under U.S.S.G. § 2Dl.l(b)(l) for possession of a firearm. The district court granted the three habeas petitions and ordered the BOP to reconsider each petitioner’s request for a sentence reduction, without regard to the petitioners’ receipt of § 2D1.1(b)(1) sentencing enhancements. The BOP did so, determined that there was no other basis for denying the requests, and reduced each petitioner’s sentence by one year.1 It now appeals, arguing the district court erred in invalidating its application of its rule to initially deny petitioners’ their sentence reductions. We affirm the district court.
BACKGROUND
I. Petitioners’ Convictions and Sentences:
James Ward was convicted of possession with intent to distribute and distribution of heroin, in violation of 21 U.S.C. § 841(a)(1). His sentence was enhanced under U.S.S.G. § 2Dl.l(b)(l) because an accessible firearm was found during a search of his residence. Jimmy Scroger was convicted of possession with intent to distribute and with attempted manufacture of methamphetamine, in violation of 21 U.S.C. § 841(a)(1). His sentence was enhanced under § 2Dl.l(b)(l) because loaded firearms were found at the residence where he was arrested. Christopher Guido was convicted of attempted possession with intent to distribute cocaine, in violation of 21 U.S.C. § 841(a)(1). His sentence was enhanced under § 2Dl.l(b)(l) because a loaded handgun was found on his person when he was arrested.
II. Statutory and Regulatory Provisions Relating to Drug Treatment Programs:
In the Violent Crime Control and Law Enforcement Act of 1994, Congress directed the BOP to make available to “eligible prisoners” residential substance abuse treatment programs. See 18 U.S.C. § 3621(e)(1). “Eligible prisoners” are defined as those “determined by the Bureau of Prisons to have a substance abuse problem” and who are “willing to participate in a residential substance abuse treatment program.” 18 U.S.C. § 3621(e)(5)(B). To provide an incentive for prisoners to participate in the treatment programs, Congress provided that:
The period a prisoner convicted of a nonviolent offense remains in custody after successfully completing a treatment program may be reduced by the Bureau of Prisons, but such reduction may not be more than one year from the term the prisoner must otherwise serve.
18 U.S.C. § 3621(e)(2)(B). The statute does not define the term “convicted of a nonviolent offense.” The statute also does not establish any additional criteria for determining eligibility for sentence reduction. The legislative history indicates Congress intended to give the BOP discretion to develop such additional criteria.2 *1252See Fristoe v. Thompson, 144 F.3d 627, 631 (10th Cir.1998) (“It is undisputed that the BOP has been delegated the authority to interpret § 3621(e)(2)(B).”).
Accordingly, to establish such criteria, the BOP promulgated a regulation in 1995 which excluded from eligibility inmates whose “current offense” is “a crime of violence” as that term is defined in 18 U.S.C. § 924(c)(3).3 See 28 C.F.R. § 550.58 (1995). The BOP also issued Program Statement No. 5162.02 on July 24, 1995, which further explained its interpretation of the term “crime of violence.” As this court noted in a prior decision addressing the validity of that Program Statement:
Section 9 of the Program Statement provide[d] that convictions ... obtained under 21 U.S.C. § 841 or § 846, should be considered convictions for a “crime of violence” if the sentencing court increased the base level of the sentence for possession of a dangerous weapon during the commission of the offense. Under the' rationale of the Program Statement and the regulation, then, [a conviction under § 841] was not a “nonviolent offense,” because of the sentencing enhancement and [the prisoner] was therefore ineligible for the sentence reduction.
Fristoe, 144 F.3d at 629-30. Thus, the initial Program Statement explicitly defined “nonviolent offense” under 18 U.S.C. § 3621(e)(2)(B) to exclude offenses where a sentence was enhanced based upon possession of a firearm.4
Inmates around the country began to challenge the Program Statement. Among them was the petitioner in Fristoe, who articulated his argument to this court as “whether the BOP has adopted a permissible construction of the statute [18 U.S.C. § 3621(e)(2)(B) ].” Fristoe, 144 F.3d at 630. We concluded it had not: “[t]he BOP’s interpretation violates the plain language of the statute and cannot be upheld.” Id. at 631. We noted that most other courts had reached the same conclusion. See Martin v. Gerlinski, 133 F.3d 1076, 1079-81 (8th Cir.1998); Bush v. Pitzer, 133 F.3d 455, 456-57 (7th Cir.1997); Roussos v. Menifee, 122 F.3d 159, 161-64 (3d Cir.1997); Downey v. Crabtree, 100 F.3d 662, 666-71 (9th Cir.1996); but see Pelissero v. Thompson, 170 F.3d 442, 445-48 (4th Cir.1999) (upholding the BOP’s Program Statement against a similar challenge); Venegas v. Henman, 126 F.3d 760, 761-63 (5th Cir.1997) (same).
Presumably in response to this judicial development, the BOP issued a new regu*1253lation and new Program Statement. These are the provisions applicable to and challenged by petitioners in this case. The current version of 28 C.F.R. § 550.58 provides in part as follows:
An inmate who was sentenced to a term of imprisonment ... for a nonviolent offense, and who is determined to have a substance abuse problem, and successfully completes a residential drug abuse treatment program during his or her current commitment may be eligible, in accordance with paragraph (a) of this section, for early release by a period not to exceed 12 months.
(a) Additional early release criteria.
(1) As an exercise of the discretion vested in the Director of the Federal Bureau of Prisons, the following categories of inmates are not eligible for early release:
(vi) Inmates whose current offense is a felony:
(A) That has as an element, the actual, attempted, or threatened use of physical force against the person or property of another, or
(B) That involved the carrying, possession, or use of a firearm or other dangerous weapon or explosives (including any explosive material or explosive device), or
(C) That by its nature or conduct, presents a serious potential risk of physical force against the person or property of another....
28 C.F.R. § 550.58. Additionally, on October 9, 1997, the BOP issued a new Program Statement, No. 5162.04, which states in pertinent part as follows:
As an exercise of the discretion vested in the Director, an inmate serving a sentence for an offense that falls under the provisions described below shall be precluded from receiving certain Bureau program benefits.
Inmates whose current offense is a felony that:
• has as an element, the actual, attempted, or threatened use of physical force against the person or property of another, or
• involved the carrying, possession, or use of a firearm or other dangerous weapon or explosives (including any explosive material or explosive device), or
• by its nature or conduct, presents a serious potential risk of physical force against the person or property of another,....
Program Statement 5162.04 at ¶ 7, Appellant’s Opening Br. Addendum R-2 at 8-9. Like the previous Program Statement, the new Program Statement contains the example of a 21 U.S.C. § 841 offense with a “Specific Offense Characteristic Enhancement” that renders the offender ineligible for sentence reduction. See supra n. 4. As it explicitly states, “[a]ecordingly, an inmate who was convicted of manufacturing drugs (21 U.S.C. § 841) and received a two-level enhancement for possession of a firearm has been convicted of an offense that will preclude him from receiving certain Bureau program benefits.” Id. at ¶ 7(b), Appellant’s Opening Br. Addendum R-2 at 12.
In sum, the new regulation and Program Statement lead to the same result as the prior, invalidated Program Statement, in that inmates whose sentences were enhanced because of firearms involvement are ineligible for the sentence reduction of 18 U.S.C. § 3621(e)(2)(B). However, they purport to accomplish that result as an exercise of the BOP’s discretion to determine eligibility criteria, not as an interpretation of the term “convicted of a nonviolent offense” under § 3621(e)(2)(B). The crucial question presented by this case is whether that difference in methodology is meaningful and significant, or whether the rationale of Fristoe dictates the conclusion that the revised regulation and new Program Statement are also invalid.
*1254DISCUSSION
As both parties agree, this case presents a purely legal question: whether the BOP’s new regulation and Program Statement—which deny sentence reductions to prisoners whose sentences for nonviolent drug offenses were enhanced because firearms were involved—are permissible as an exercise of BOP discretion under § 3621(e)(2)(B) or are invalid under Fristoe. The district court held they were invalid, determining that the rationale of our prior decision in Fristoe compelled that conclusion. We note that we have recently held that our obligation to follow prior decisions “includes not only the very narrow holdings of those prior cases, but also the reasoning underlying those holdings.” United States v. Meyers, 200 F.3d 715 (10th Cir.2000). We review the district court’s decision de novo and hold that the new regulation and Program Statement are invalid under the reasoning and rationale of Fristoe.
We begin by examining Fristoe. The petitioner in Fristoe was convicted of conspiracy to distribute cocaine in violation of 21 U.S.C. §§ 841 and 846. At sentencing, he received a two-level enhancement under § 2Dl.l(b)(l) for firearms possession. Although Fristoe addressed the earlier version of 28 C.F.R. § 550.58 and Program Statement 5106.02, we use the same legal analysis to examine the validity of the current version of the regulation and the current Program Statement (No. 5106.04). Accordingly, we “interpret!] the statute [18 U.S.C. § 3621(e)(2)(B) ] to determine whether the BOP exceeded its statutory authority.” Fristoe, 144 F.3d at 630-31.5 We employ a slightly different analysis, however, depending on the particular means by which the BOP presents its interpretation:
An agency’s interpretation of a statute by formal regulation or adjudication is entitled to deference, so long as the agency’s interpretation is based upon a permissible construction of the statute. Where the agency’s interpretation of the statute is made informally, however, such as by a “program statement,” the interpretation is not entitled to Chevron deference, but will instead be considered only to the extent that it is well-reasoned and has “power to persuade.”
Id. at 631 (citing Chevron, U.S.A., Inc. v. Natural Resources Defense Council, Inc., 467 U.S. 837, 843, 104 S.Ct. 2778, 81 L.Ed.2d 694 (1984)) (further citation omitted).
In Fristoe, we began by noting that “courts typically do not consider the predicate drug offense here, conspiracy to distribute cocaine, a ‘crime of violence.’ ” Id. We therefore deduced that the BOP’s classification of Mr. Fristoe’s nonviolent drug offense as a “crime of violence” under § 3621(e)(2)(B) “must rest entirely upon consideration of sentencing factors which are not implicated categorically by the nature of his underlying offense.” Id. Such “[rjeliance on sentencing enhancements ... conflicts with the plain language of the statute ... [which] refers to prisoners ‘convicted of a nonviolent offense.’” Id. As we explained in a subsequent opinion discussing Fristoe:
We reasoned that § 3621(e)(2)(B) simply does not authorize BOP to treat sentence enhancements or factors as if they were “convictions.” In other words, if the prisoner has not been convicted of a violent offense, BOP cannot use sentencing factors or enhancements to convert a nonviolent offense into a violent one for purposes of § 3621(e)(2)(B).
Martinez v. Flowers, 164 F.3d 1257, 1260 (10th Cir.1998) (quoting Fristoe, 144 F.3d at 632). Significantly, we provided no caveats to our condemnation of the BOP’s use of sentencing enhancements to convert nonviolent offenses into violent ones for eligibility purposes under the statute. Indeed, in Fristoe, we described our holding *1255as “any resort to sentencing factors in the absence of a conviction of an offense which constitutes a crime of violence is impermissible.” Fristoe, 144 F.3d at 632 n. 3 (emphasis added).
The BOP argues that, for two reasons, Fristoe does not control our disposition in this case. First, it argues that Fristoe addressed only the validity of a BOP Program Statement, not a regulation, and program statements are entitled to no deference. The BOP’s new rule, by contrast, rests upon both a program statement and a formal regulation, the latter of which is entitled to Chevron deference. Second, the BOP argues the prior Program Statement, invalidated in Fristoe, overtly attempted to define the statutory term “convicted of a crime of violence” to include convictions of nonviolent offenses with a firearms sentencing enhancement. The current regulation and Program Statement, by contrast, overtly reach the same result, but explicitly as an exercise of the discretion clearly bestowed upon the BOP to determine who may and may not participate in the sentence reduction program. Thus, the BOP argues, it has not engaged in improper statutory interpretation; rather it has simply exercised its discretion to develop eligibility criteria. We address each argument in turn.
I. Regulation vs. Program Statement:
We held in Fristoe that “the rationale of the Program Statement and the regulation” expressed the BOP’s view that a drug offense with a sentencing enhancement for firearms possession was not a “nonviolent offense” under § 3621(e)(2)(B). Fristoe, 144 F.3d at 630. Despite that reference to the rationale of both the regulation and the Program Statement, the focus of our analysis was on the Program Statement, which, unlike the regulation, explicitly held that prisoners with drug convictions with firearms sentencing enhancements were ineligible to participate in the early release program. Indeed, we applied the non-deferential review standard applicable to “informal” agency interpretations like program statements, holding that “[t]he BOP’s program statement definition of a ‘nonviolent offense’ is not well-reasoned, and fails to persuade us it is entitled to deference.” Id. at 631. We therefore assume, for purposes of this appeal, that Fristoe only clearly invalidated a program statement, not a regulation. We likewise assume, for purposes of this appeal, that we review in this case both the regulation and the new Program Statement.6 Accordingly, we apply the deferential review standard to the regulation and the non-deferential review standard to the Program Statement. See Fristoe, 144 F.3d at 631.
II. Validity of New Regulation and Program Statement:
The BOP argues that the new regulation and Program Statement, unlike the prior ones, do not attempt to define any statutory term, but merely express eligibility criteria clearly entrusted to the BOP’s discretion. We believe that the BOP relies upon “a distinction without a difference.” Kilpatrick v. Houston, 36 F.Supp.2d 1328, 1330 (N.D.Fla.), aff'd, 197 F.3d 1134 (11th Cir.1999).
*1256In Fristoe, we held that the operative statute, § 3621(e)(2)(B), plainly stated that prisoners convicted of nonviolent offenses were eligible for sentence reductions. We emphasized in that opinion and in Martinez that the statute addresses convictions, and that convictions for drug offense, are nonviolent. We held that any use of sentence enhancements to turn a conviction of a nonviolent offense into a violent offense for purposes of § 3621(e)(2)(B) was impermissible, simply because it ran afoul of the statute’s clear language.
The language of the statute remains unchanged and .its focus on convictions for nonviolent offenses still stands. The BOP’s new regulation and Program Statement, like the old ones, use sentencing enhancements to effectively override the statute’s clear statement that a prisoner is eligible if convicted of a nonviolent offense. Couching it as an exercise of discretion does not make it any less contrary to the statute. As a district court recently observed in an opinion affirmed by the Eleventh Circuit, to hold otherwise would render Fristoe “a trivial criticism of the Bureau’s drafting technique rather than a substantive ruling on the meaning of the statute and the scope of the Bureau’s authority thereunder.” Kilpatrick, 36 F.Supp.2d at 1330. See Samples v. Scibana, 74 F.Supp.2d 702, 707 (E.D.Mich.1999) (“This Court further agrees with other district courts that the amendments to both 28 C.F.R. § 550.58(a)(1) and Program Statement 5162.04 are an attempt by the BOP to disregard the line of federal circuit court cases that held that the BOP could not use a sentence enhancement to conclude that a prisoner had not been convicted of a nonviolent offense.”); Rodriguez v. Herrera, 72 F.Supp.2d 1229, 1231 (D.Colo.1999) (“[T]he revised provision runs afoul of Fristoe by declaring a category of statutorily eligible inmates ‘ineligible’ solely on the basis of sentencing factors implicated neither by the nature of the underlying offense nor by the definition of violent crimes set forth at 18 U.S.C. § 924(c)(3).”); Todd v. Sabana, 70 F.Supp.2d 779, 784 (E.D.Mich.1999) (“The amendments to both 28 C.F.R. § 550.58(a)(1) and P.S. 5162.04 appear to be an attempt by the BOP to circumvent the line of federal circuit court cases which hold that the BOP cannot use a sentence enhancement to conclude that a prisoner has not been convicted of a nonviolent offense.”); Nelson v. Crabtree, 59 F.Supp.2d 1081, 1084 (D.Or.1999) (“[The Ninth Circuit held] that the operative word of § 3621(e)(2)(B) is ‘conviction.’ A decision not to allow early release may only be based on the nature of the conviction; sentencing enhancements ... are irrelevant.”); Williams v. Clark, 52 F.Supp.2d 1145, 1151 (C.D.Cal.1999) (“The language of Section 3621(e)(2)(B) has not been' amended ... and it remains plain and clear; the BOP may not use a sentence enhancement to conclude that a prisoner has not been convicted of a nonviolent offense.”); Hicks v. Brooks, 28 F.Supp.2d 1268, 1272-73 (D.Colo.1998) (“[T]he BOP again has accomplished precisely what Fristoe said it may not, i.e., exclude categorically from consideration for early release upon completion of a drug treatment program those inmates convicted of a nonviolent offense whose sentence was enhanced for possession of a weapon and, once again, convert a conviction for a nonviolent offense into a violent one by considering the sentence enhancement.”); Gavis v. Crabtree, 28 F.Supp.2d 1264, 1266 (D.Or.1998) (“The inescapable result of this new program statement is that it reverses governing case law by looking to the underlying facts to exclude prisoners [with firearms sentencing enhancements] ... from early release consideration.”).
We recognize that in reaching this conclusion, we part company with the Eighth Circuit, which recently held that the new regulation and Program Statement were valid: “[w]e think that the BOP’s decision to exclude these additional categories of inmates from eligibility [i.e. those with sentencing enhancements because of firearms possession] represent a manifestly permissible construction of the statute and an *1257appropriate exercise of the BOP’s discretion.” Bellis v. Davis, 186 F.3d 1092, 1095 (8th Cir.1999), petitions for cert. filed,-U.S.L.W. -(U.S. Dec. 15, 1999) (Nos. 99-7504, 99-7558). The court simply dismissed as “of no relevance” its prior decision in Martin v. Gerlinski, 133 F.3d 1076 (8th Cir.1998), which invalidated the earlier regulation and Program Statement for the same reasons we did in Fristoe. Id. Nonetheless, we join the Eleventh Circuit and numerous district courts, whose reasoning we find more persuasive.
Thus, whether we review the current regulation or the current Program Statement, we conclude that they conflict with the clear language of § 3621(e)(2)(B). The regulation is therefore not “based upon a permissible construction of the statute.” Fristoe, 144 F.3d at 631; see also Martinez, 164 F.3d at 1259 (noting that we defer to agency’s interpretation of a statute through a formal regulation only “if it is based on a permissible constructions of the statute”).7 The Program Statement is not “well-reasoned” nor does it have “ ‘power to persuade.’ ” Id.
In reaching this conclusion, we in no way denigrate the BOP’s broad discretion to determine who among eligible prisoners may receive a sentence reduction following participation in a substance abuse treatment program. As the Seventh Circuit has observed, “[cjommission of a ‘nonviolent offense’ makes a prisoner eligible for consideration but does not require the Bureau to grant the boon he seeks. Eligibility is not entitlement.” Bush, 133 F.3d at 457; see also Samples, 74 F.Supp.2d at 708 (‘While early release under § 3621(e)(2)(B) is open to all prisoners who meet the statutory requirements, the statute vests the BOP with broad discretion to grant or deny sentence reductions to eligible prisoners.”); Rodriguez, 72 F.Supp.2d at 1231-32 (noting that “the fact Petitioners are eligible for consideration for early release under § 3621(e)(2)(B) does not mean they are entitled to early release”); Todd, 70 F.Supp.2d at 785 (“While eligibility for early release under section 3621(e)(2)(B) is open to all prisoners who meet the statutory requirements, the statute vests the BOP with broad discretion to grant or deny sentence reductions to eligible prisoners based upon factors other than the categorical restrictions currently imposed.”). We simply hold that the BOP may not disregard the statutory eligibility requirements by categorically excluding from sentence reduction eligibility prisoners convicted of nonviolent offenses whose sentences were enhanced because of firearms. In doing so, it has exceeded its statutory authority.
CONCLUSION
For the foregoing reasons, we AFFIRM the decisions of the district court.granting petitioners’ habeas relief.