REINHARDT, Circuit Judge:

This case is the most recent in a series of challenges to the Bureau of Prisons' ("Bureau" or "BOP") implementing regulation governing early release of prisoners who successfully complete a residential substance abuse program. The relevant statute provides that the Bureau may reduce by up to one year the prison term of an inmate convicted of a non-violent felony if the prisoner successfully completes such a program. 18 U.S.C. § 3621(e)(2)(B). The Bureau's implementing regulation categorically excludes from eligibility for early release under the law those whose "current offense is a felony. . . . [t]hat involved the carrying, possession, or use of a firearm or other dangerous weapon or explosives[.]" 28 C.F.R. § 550.58(a)(1)(vi)(B)(2000). The question presented is whether the Bureau of Prisons violated Section 706(2)(A) of the Administrative Procedure Act ("APA") when it promulgated this regulation. We hold that it did.

I. Factual and Procedural Background

Title 18 U.S.C. § 3621 governs the imprisonment of persons convicted of federal crimes. In 1990, Congress amended the statute by directing the Bureau of Prisons to provide residential substance abuse treatment programs for prisoners determined to have a treatable condition of substance addiction or abuse. Crime Control Act of 1990, Pub.L. No. 101-647, § 2903, 104 Stat. 4789, 4913 (codified at 18 U.S.C. § 3621(b)). Four years later, in response to under-utilization of treatment programs, Congress again amended the statute to provide an early release incentive to encourage prisoner participation. Violent Crime Control and Law Enforcement Act of 1994, 103 Pub.L. No. 322, § 32001, 108 Stat. 1796, 1896-97. The statute provides that the Bureau may reduce by up to one year the sentence of a prisoner who (1) was convicted of a non-violent offense and (2) successfully completes a program of residential substance abuse treatment. 18 U.S.C. § 3621(e)(2)(B).

In May 1995, the Bureau promulgated its first rule and corresponding regulation detailing procedures to determine eligibility for early release under § 3621(e). 60 Fed.Reg. 27692 (May 25, 1995); 28 C.F.R. § 550.58 (1995). In defining "non-violent offense," the Bureau relied on the definition of "crime of violence" contained in 18 U.S.C. § 924(c)(3). The regulation rendered ineligible for early release those "inmates whose current offense is determined to be a crime of violence as defined in 18 U.S.C. § 924(c)(3)." 28 C.F.R. § 550.58 (1995). In a program statement issued several months later, the Bureau purported to further restrict eligibility under the statute by categorizing as "crimes of violence" firearms convictions under 18 U.S.C. § 922(g) as well as drug trafficking convictions under 21 U.S.C. § 841 or § 846, if the offender received a two-level enhancement for weapons possession under United States Sentencing Commission Guidelines Manual § 2D1.1(b)(1). Bureau of Prisons Program Statement No. 5162.02, §§ 7, 9 (July 24, 1995).

We subsequently held that neither of these disqualifications was for a "crime of violence" under the statutory definition contained in § 924(c)(3). See Davis v. Crabtree, 109 F.3d 566, 568-70 (9th Cir. 1997); Downey v. Crabtree, 100 F.3d 662, 666-70 (9th Cir. 1996). We concluded that the Bureau must consider eligible for early release as non-violent offenders those with convictions under 18 U.S.C. § 922(g) as well as those with convictions under 21 U.S.C. § 841 whether or not they received sentencing enhancements for weapons possession. See Davis, 109 F.3d at 569; Downey, 100 F.3d at 668. Four other circuits agreed. See Fristoe v. Thompson, 144 F.3d 627, 631 (10th Cir. 1998) (holding impermissible the Bureau's interpretation of § 3621(e) as precluding from eligibility for early release prisoners who received sentence enhancements for non-violent offenses); Byrd v. Hasty, 142 F.3d 1395, 1397-98 (11th Cir. 1998) (same); Martin v. Gerlinski, 133 F.3d 1076, 1079-80 (8th Cir. 1998) (same); Roussos v. Menifee, 122 F.3d 159, 162-64 (3d Cir. 1997) (same). Three circuits reached the opposite conclusion. See Pelissero v. Thompson, 170 F.3d 442, 447 (4th Cir. 1999) (holding Bureau's definition of crime of violence was permissible); Parsons v. Pitzer, 149 F.3d 734, 737-39 (7th Cir. 1998) (same); Venegas v. Henman, 126 F.3d 760, 763 (5th Cir. 1997) (same).

In response to the lack of consistency arising from the varying definitions of a non-violent offense, the Bureau changed course. The agency removed its reference to § 924(c)(3) from the regulation and abandoned its attempt to determine eligibility based on an interpretation of the phrase "non-violent offense." Instead, the Bureau issued an interim rule that asserted the agency's discretionary authority to determine eligibility for early release under § 3621(e). 62 Fed.Reg. 53690 (Oct. 15, 1997) ("1997 interim rule"). The Bureau then exercised its discretion to narrow the class of prisoners eligible for early release beyond "non-violent" offenders. The 1997 interim rule thereby purported to accomplish by different means what the Bureau set out to achieve in its 1995 program statement: the categorical exclusion from eligibility for early release of those prisoners convicted of an offense "involv[ing] the carrying, possession, or use of a firearm or other dangerous weapon or explosives." 62 Fed.Reg. at 53690; 28 C.F.R. § 550.58(a)(vi)(B) (1998).

Litigation once again ensued. This time challenges focused on whether the categorical exclusion rule was a permissible exercise of the agency's discretion. Two circuit courts, including our own, concluded that the 1997 interim rule was a permissible exercise of the Bureau's discretion to narrow the class of prisoners eligible for early release under § 3621(e). See Bellis v. Davis, 186 F.3d 1092, 1095 (8th Cir. 1999); Bowen v. Hood, 202 F.3d 1211, 1220 (9th Cir. 2000). Two circuit courts reached the contrary result. See Ward v. Booker, 202 F.3d 1249, 1256-57 (10th Cir. 2000); Kilpatrick v. Houston, 197 F.3d 1134, 1135 (11th Cir. 1999). The Supreme Court granted certiorari to resolve the circuit split. In Lopez v. Davis, the Court upheld the validity of the 1997 interim rule, reasoning that the Bureau permissibly exercised the discretion afforded the agency by the statute to narrow the class of prisoners eligible for early release. 531 U.S. 230, 239-41, 121 S.Ct. 714, 148 L.Ed.2d 635 (2001). Four years later, we struck down the rule on procedural grounds, holding that the Bureau failed to comply with the APA's notice and comment provisions. Paulsen v. Daniels, 413 F.3d 999, 1004 (9th Cir. 2005) (holding "[t]he Bureau plainly violated [Section 553 of] the APA in its promulgation of the 1997 interim regulation").

In December 2000, the Bureau promulgated a final rule. The final rule, identical to the 1997 interim rule, relied on the Bureau's discretion to narrow the class of prisoners eligible for early release by excluding those convicted of offenses involving the carrying, possession, or use of a firearm or other dangerous weapon or explosives. 65 Fed.Reg. 80745, 80747-748 (Dec. 22, 2000) (stating that "Congress did not man-date that all eligible inmates must receive the early release incentive. The reduction in sentence is an incentive to be exercised at the discretion of the Bureau of Prisons"). The Bureau offered the following explanation for its rule:

The first interim rule attempted to define the term "crime of violence" pursuant to 18 U.S.C. § 924(c)(3). Due to varying interpretations of the regulation and caselaw, the Bureau could not apply the regulation in a uniform and consistent manner.

The third interim rule sought to resolve this complication. In the third interim rule, we used the discretion allotted to the Director for granting a sentence reduction to exclude inmates whose current offense is a felony . . . that involved the carrying, possession, or use of a firearm or other dangerous weapon or explosives (including any explosive material or explosive device). . . .

Id. at 80747.

In 2005 and 2006, eighteen prisoners filed petitions for habeas corpus pursuant to 28 U.S.C. § 2241 challenging the Bureau's final rule. The petitioners are prisoners or former prisoners who were convicted of offenses involving the carrying, possession, or use of a firearm or other dangerous weapon or explosives, and who were sentenced to terms of imprisonment at the Federal Correctional Institution in Sheridan, Oregon. They argue that although the Bureau has the authority to implement a categorical exclusion of prisoners who are otherwise statutorily eligible for early release, the Bureau must provide a rationale for its decision to do so. The Bureau's failure to state a rationale for its categorical exclusion rule, they assert, renders the regulation arbitrary and capricious in violation of Section 706(2)(A) of the APA. The district court, relying on the Supreme Court's decision in Lopez, 531 U.S. at 230, 121 S.Ct. 714, denied relief. Arrington v. Daniels, 465 F.Supp.2d 1104, 1108 (D.Or. 2006) (concluding that "the 2000 Final Rule promulgated by the BOP is not in violation of the APA"). Because we find that the administrative record contains no rationale explaining the Bureau's decision to categorically exclude prisoners with convictions involving firearms from eligibility for early release under § 3621(e), we reverse.

II. Jurisdiction and Standard of Review

The district court had jurisdiction pursuant to 28 U.S.C. § 2241. We have jurisdiction pursuant to 28 U.S.C. § 1291 and § 2253(a).

We review de novo a district court's denial of a writ of habeas corpus pursuant to 28 U.S.C. § 2241. Bowen, 202 F.3d at 1218. In reviewing the Bureau's conduct, we consider whether the agency's promulgation of the final rule is "arbitrary, capricious, an abuse of discretion, or otherwise not in accordance with law." 5 U.S.C. § 706(2)(A).

III. Discussion A.

Section 706(2)(A) of the APA provides that a "reviewing court shall hold unlawful and set aside agency action, findings, and conclusions found to be arbitrary, capricious, an abuse of discretion or otherwise not in accordance with law." Under the arbitrary and capricious standard, our scope of review is narrow and deferential. A reviewing court must consider whether "the decision was based on a consideration of the relevant factors and whether there has been a clear error of judgment. . . . The court is not empowered to substitute its judgment for that of the agency." Citizens to Preserve Overton Park, Inc. v. Volpe, 401 U.S. 402, 416, 91 S.Ct. 814, 28 L.Ed.2d 136 (1971), overruled on other grounds by Califano v. Sanders, 430 U.S. 99, 105, 97 S.Ct. 980, 51 L.Ed.2d 192 (1977). Agency action is valid "if a reasonable basis exists for [the agency's] decision." Kern County Farm Bureau v. Allen, 450 F.3d 1072, 1076 (9th Cir. 2006) (internal quotations and citations omitted). A reasonable basis exists where the agency "considered the relevant factors and articulated a rational connection between the facts found and the choices made." Ranchers Cattlemen Action Legal Fund v. U.S. Dep't of Agriculture, 415 F.3d 1078, 1093 (9th Cir. 2005) (internal citation omitted). Although we may "`uphold a decision of less than ideal clarity if the agency's path may reasonably be discerned,'" Motor Vehicle Mfrs. Ass'n v. State Farm Mut. Auto. Ins. Co., 463 U.S. 29, 44, 103 S.Ct. 2856, 77 L.Ed.2d 443 (1983) (quoting Bowman Transp., Inc. v. Arkansas-Best Freight Sys., Inc., 419 U.S. 281, 286, 95 S.Ct. 438, 42 L.Ed.2d 447 (1974)), we may not "infer an agency's reasoning from mere silence." Pacific Coast Fed'n of Fishermen's Ass'ns v. U.S. Bureau of Reclamation, 426 F.3d 1082, 1091 (9th Cir. 2005).

In conducting our review, we may look only to the administrative record to determine whether the agency has articulated a rational basis for its decision. See State Farm Mut. Auto. Ins. Co., 463 U.S. at 50, 103 S.Ct. 2856 ("It is well established that an agency's action must be upheld, if at all, on the basis articulated by the agency itself."); SEC v. Chenery Corp., 318 U.S. 80, 87, 63 S.Ct. 454, 87 L.Ed. 626 (1943) ("The grounds upon which an administrative order must be judged are those upon which the record discloses that its action was based."); SEC v. Chenery Corp., 332 U.S. 194, 196, 67 S.Ct. 1575, 91 L.Ed. 1995 (1947). Post hoc explanations of agency action by appellate counsel cannot substitute for the agency's own articulation of the basis for its decision. Fed. Power Comm'n v. Texaco, Inc., 417 U.S. 380, 397, 94 S.Ct. 2315, 41 L.Ed.2d 141 (1974) ("[W]e cannot `accept appellate counsel's post hoc rationalizations for agency action'; for an agency's order must be upheld, if at all, `on the same basis articulated in the order by the agency itself.'") (quoting Burlington Truck Lines, Inc. v. United States, 371 U.S. 156, 168, 83 S.Ct. 239, 9 L.Ed.2d 207 (1962); Chenery Corp., 332 U.S. at 196, 67 S.Ct. 1575). With these guidelines in mind, we turn to our review of the agency action in the present case.

The district court found two rational bases for the Bureau's decision to categorically exclude from eligibility for early release those prisoners convicted of offenses involving the possession, carrying, or use of firearms: (1) the increased risk that offenders with convictions involving firearms might pose to the public and (2) the need for uniformity in the application of the eligibility regulation. Arrington, 465 F.Supp.2d at 1108. Neither of these bases withstands even our narrow and deferential standard of review under the APA.

The first rationale, that those convicted of offenses involving firearms pose a greater threat to public safety, is entirely absent from the administrative record. Rather, the Bureau articulated this rationale in its brief to the Supreme Court in Lopez, 531 U.S. at 236, 121 S.Ct. 714 ("The preconviction conduct of both armed offenders and certain recidivists, in the Bureau's view, `suggest[s] that they pose a particular risk to the public'" (quoting Brief for Respondents 30)). This argument is precisely the type of " post hoc rationalization" of appellate counsel that we are forbidden to consider in conducting review under the APA. Burlington Truck Lines, Inc., 371 U.S. at 168, 83 S.Ct. 239. We are limited to the explanations offered by the agency in the administrative record. See State Farm Mut. Auto. Ins. Co., 463 U.S. at 50, 103 S.Ct. 2856. Because no public safety rationale is present in the administrative record, the district court erred in relying on this explanation as a basis for its conclusion that the final rule withstands arbitrary and capricious review.

The second rationale identified by the district court, the need for uniformity in the application of the eligibility regulation, fares little better. Unlike the public safety rationale, this explanation is articulated by the Bureau in the administrative record, and therefore was properly considered by the district court. The Bureau explained that the final rule was adopted "[d]ue to varying interpretations of the regulation and caselaw [which prevented] the Bureau [from] apply[ing] the regulation in a uniform and consistent manner." 65 Fed.Reg. at 80747. We disagree with the district court, however, that this rationale justifies the Bureau's action. A general desire for uniformity provides no explanation for why the Bureau exercised its discretion to achieve consistency through the promulgation of a categorical exclusion rule. The Bureau's stated desire for uniformity could have been accomplished in any number of ways. For example, the Bureau could have achieved uniformity by categorically including prisoners with non-violent convictions involving firearms, thus making them eligible for early release: a result that would have been entirely consistent with the statute's aim of offering incentives for prisoner participation in residential substance abuse programs. Instead, it chose to achieve uniformity by categorically excluding such prisoners from eligibility. Although either choice in all likelihood would have withstood judicial scrutiny, the Bureau offered no explanation for why it exercised its discretion to select one rather than the other. The agency's lack of explanation for its choice renders its decision arbitrary and capricious. See, e.g., Burlington Truck Lines, Inc., 371 U.S. at 167, 83 S.Ct. 239 (striking down action for failure to explain why agency chose one of two available remedies where "[t]here are no findings and no analysis here to justify the choice made, no indication of the basis on which the [agency] exercised its expert discretion").

Although agencies enjoy wide discretion in fashioning regulations governing the statutes that they are charged with administering, section 706 of the APA requires that they articulate a rationale when they exercise that discretion. This is not an empty requirement. Because we may not substitute our own rationales for those of the agency, see Burlington Truck Lines, Inc., 371 U.S. at 169, 83 S.Ct. 239, when an agency fails to provide an explanation for its actions we are left with no means of reviewing the reasonableness of that action. Here, the Bureau failed to set forth a rationale for its decision to categorically exclude prisoners convicted of offenses involving the carrying, possession, or use of firearms from eligibility for a sentence reduction under § 3621(e). This failure renders the Bureau's final rule invalid under the APA.

B.

Our holding today is in no way foreclosed by the Supreme Court's decision in Lopez v. Davis, 531 U.S. at 230,

121 S.Ct. 714, or by our decision in Bowen v. Hood, 202 F.3d at 1211. Both cases addressed a distinct question: whether the Bureau had the authority to pass a rule categorically excluding otherwise eligible prisoners from a grant of early release under § 3621(e). Neither case addressed the question presented before us: whether the agency complied with the requirements of APA § 706 in promulgating the rule.

In Bowen, we considered the validity of the Bureau's interpretation of § 3621(e) as conferring upon the agency the authority to narrow the class of prisoners eligible for early release. Bowen, 202 F.3d at 1218. We concluded that the Bureau validly interpreted the statute as affording the agency "discretion to creat[e] categorical exclusions." Id. at 1219. The Bowen court did not consider the distinct question of whether the Bureau complied with the APA's procedural requirements in exercising that discretion. The Bureau's argument to the contrary relies on a passage in Bowen noting that we saw "nothing unreasonable in the Bureau's making the common-sense decision that there is a significant potential for violence from criminals who carry, possess or use firearms while engaged in their felonious employment, even if they have wound up committing a non-violent offense." Id., This argument, however, fails to take into account the question presented before the Bowen court: whether the Bureau had the authority to exercise its discretion under the statute by promulgating a categorical exclusion rule and not whether the Bureau's exercise of that authority comported with the APA. A rule may ultimately be reasonable in substance (as the Bowen court concluded that the 1997 interim rule was) but nevertheless fail APA review if the agency does not comply with its procedural responsibility to articulate in the administrative record the rational basis upon which it relied in promulgating the rule. Indeed, the Bowen court's reference to "common-sense," rather than to the administrative record, in drawing its conclusion that the categorical exclusion rule was a reasonable exercise of the agency's discretion evidences the fact that it was not engaged in § 706 review. See, e.g., SEC v. Chenery Corp., 332 U.S. at 196, 67 S.Ct. 1575 (requiring that a reviewing court judge the "propriety of [agency] action solely by the grounds invoked by the agency") (emphasis added).

Similarly, in Lopez, the Supreme Court considered "whether the Bureau has discretion to delineate, as an additional category of ineligible inmates, those whose current offense is a felony involving a firearm." 531 U.S. at 238, 121 S.Ct. 714 (emphasis added). As in Bowen, the inquiry in Lopez was limited to whether the Bureau had discretion to narrow the class of prisoners eligible for early release under § 3621(e). In deciding this question in the affirmative, the Court did not consider an APA challenge to the validity of the Bureau's 1997 interim rule. Indeed, the Court expressly declined the invitation of amici to consider whether the Bureau violated the APA's notice and comment requirements when it published the regulation because the "matter was not raised or decided below, or presented in the petition for certiorari." Lopez, 531 U.S. at 245 n. 6, 121 S.Ct. 714. Although the Lopez Court expressed agreement with the Bureau's position that "denial of early release to all inmates who possessed a firearm in connection with their current offense rationally reflects the view that such inmates displayed a readiness to endanger another's life[,]" id. at 240, 121 S.Ct. 714, this rationale, as discussed supra, was supported by citation not to the administrative record, but to the Bureau's brief. Id. at 236, 121 S.Ct. 714. The Lopez Court's reliance on the arguments of appellate counsel, rather than on the administrative record, evidences the fact that the Lopez Court, like the Bowen Court, was not engaged in § 706 review. See, e.g., Burlington Truck Lines, Inc., 371 U.S. at 168, 83 S.Ct. 239 (rejecting reliance on appellate counsel's " post hoc rationalizations" as the basis for agency action).

The question presented in Bowen and Lopez — whether the Bureau had the authority to pass a rule narrowing the class of prisoners eligible for early release under § 3621(e) — is distinct from the question whether the rule that the Bureau passed comports with the requirements of the APA. This distinction is starkly illustrated by our decision in Paulsen striking down on procedural grounds the very 1997 interim rule that Bowen and Lopez determined represented a legitimate exercise of agency discretion. See Paulsen, 413 F.3d at 1004 (holding that the interim rule "plainly violated the APA" notice and comment requirements). See also Gunderson, 268 F.3d at 1152 (noting that although after Bowen and Lopez "it is quite clear that the 1997 regulation and program statement are substantively sound. . . . [i]t is not clear . . . that [they] are immune from attack on procedural grounds"). Just as a rule can be invalidated for violating notice and comment requirements even if a court has determined that it represents an otherwise legitimate exercise of agency discretion, so too can a rule that survives a challenge to agency authority fail arbitrary and capricious review where the agency neglects to articulate a rational basis for the manner in which it exercises its discretion. Although the Bowen and Lopez decisions recognize that there are rational explanations for the 1997 interim rule, which is identical to the Bureau's final rule in this case, they do not address whether the agency itself articulated those rationales in promulgating the final rule as required by § 706. We now consider that question and hold that the Bureau's promulgation of the final rule was arbitrary and capricious because it failed to articulate a rationale for its categorical exclusion of a class of non-violent offenders from eligibility for early release.

IV. Conclusion

For twelve years, the Bureau has sought to exclude those convicted of offenses involving the carrying, possession, or use of a firearm or other dangerous weapon or explosives from eligibility for early release under § 3621(e). In that time, the Bureau has failed to adopt a valid regulation to support its exclusion policy. Its first attempt was struck down because the Bureau adopted an impermissible definition of "crime of violence." See Davis, 109 F.3d at 568-70; Downey, 100 F.3d at 666-70. Its second attempt was struck down on notice and comment grounds. See Paulsen, 413 F.3d at 1004. The final rule, like its predecessors, also falls short of meeting the governing legal standards. The Bureau has failed to set forth a valid rationale for its categorical exclusion rule. Section 706 of the Administrative Procedure Act requires that it do so. We therefore reverse the judgments of the district court in the consolidated cases and direct it to grant the habeas corpus petitions. See Paulsen, 413 F.3d at 1008.

REVERSED and REMANDED.